Efficient selection methods in evolutionary algorithms

• Autorzy: Stańczak Jarosław

Identyfikatory

DOI

10.7494/csci.2024.25.1.5330

• Języki publikacji: EN

Abstrakty

EN

Evolutionary algorithms mimic some elements of the theory of evolution. The survival of individuals and the ability to produce off spring play significant rolesin the process of natural evolution. This process is called natural selection.This mechanism is responsible for eliminating weaker members of the population and provides the opportunity for the development of stronger individuals.The evolutionary algorithm, an instance of evolution in the computer environment, also requires a selection method – a computerized version of natural selection. Widely used standard selection methods applied in evolutionary algorithms are usually derived from nature and prefer competition, randomness, and some kind of “fight” among individuals. But the computer environment is quite different from nature. Computer populations of individuals are typically small, making them susceptible to premature convergence towards local extremes. To mitigate this drawback, computer selection methods must incorporate features distinct from those of natural selection. In the computer selection methods randomness, fight, and competition should be controlled or influenced to operate to the desired extent. This work proposes several new methods of individual selection, including various forms of mixed selection, interval selection, and taboo selection. The advantages of incorporating theminto the evolutionary algorithm are also demonstrated, using examples basedon searching for the maximum α-clique problem and traditional Traveling Salesman Problem (TSP) in comparison with traditionally considered highly efficient tournament selection, deemed in effective proportional (roulette) selection, and other classical methods.

Słowa kluczowe

EN

evolutionary algorithms; selection methods; adaptive evolutionary algorithms

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2024
• Tom: T. 25 (1)
• Strony: 95--122
• Opis fizyczny: Bibliogr. 23 poz., rys., tab., wykr.

Twórcy

autor

Stańczak Jarosław

• Systems Research Institute PAS, Newelska 6, 01-447 Warsaw

Bibliografia

• [1] Aho A.V., Hopcroft J.E., Ullman J.D.:The Design and Analysis of Computer Algorithm, Addison-Wesley Publishing Company, 1974.
• [2] Arabas J., Michalewicz Z., Mulawka J.: GAVaPS – a genetic algorithm with vary-ing population size. In: Proceedings of The First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, vol. 1, pp. 73–78, 1994.
• [3] Back T.: Selective Pressure in Evolutionary Algorithms: A Characterization of Selection Mechanisms. In: Proceedings of the First IEEE Conference on Evolutionary Computation. IEEE World Congress on Computational Intelligence, vol. 1, pp. 57–62, 1994.
• [4] BHOSLIB – Network Data Repository. http://www.nlsde.buaa.edu.cn/kexu/benchmarks/graph-benchmarks.htm.
• [5] Blickle T., Thiele L.:A Comparison of Selection Schemes used in Genetic Algo-rithms, Computer Engineering and Communication Networks Lab (TIK), SwissFederal Institute of Technology (ETH), 1995. TIK-Report Nr. 11.
• [6] Blickle T., Thiele L.: A Mathematical Analysis of Tournament Selection. In: Proceedings of the 6th International Conference on Genetic Algorithms, vol. 1,pp. 9–16, 1995.
• [7] Cantú-Paz E.: Selection Intensity in Genetic Algorithms with Generation Gaps. In: Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation (GECCO’00), vol. 1, pp. 911–918, 2000.
• [8] Cichosz P.: Systemy uczące się, WNT, Warszawa, 2000.
• [9] ELIB: MP-TESTDATA – The TSPLIB Symmetric Traveling Salesman Problem Instances. http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html.
• [10] Goldberg D.E., Deb K.: A comparative analysis of selection schemes used ingenetic algorithms, Foundations of Genetic Algorithms, vol. 1, pp. 69–93, 1991.
• [11] Holland J.J.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence, MITPress, USA, 1992.
• [12] Moscato P.: On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. Technical Report C3P 826, CaltechCon-Current Computation Program 158-79, California Institute of Technology, Pasadena, 1989.
• [13] Muhlenbein H., Schlierkamp-Voosen D.: Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization, Evolutionary Computation,vol. 1(1), pp. 25–49, 1993. doi: 10.1162/evco.1993.1.1.25.
• [14] Potrzebowski H., Stańczak J., Sęp K.: Separable Decomposition of Graph Using α-cliques. In: Computer Recognition Systems 2, vol. 1, pp. 386–393, 2007.
• [15] Rogers A., Prugel-Bennett A.: Genetic Drift in Genetic Algorithm Selection Schemes. In: IEEE Transactions on Evolutionary Computation, vol. 3, pp. 298–303, 1999.
• [16] Rudolph G.: Takeover Times and Probabilities of Non-Generational Selection Rules. In: Proceedings of the 2nd Annual Conference on Genetic and Evolutionary Computation, pp. 903–910, 2000.
• [17] Stańczak J.: Biologically inspired methods for control of evolutionary algorithms, Control and Cybernetics, vol. 32(2), pp. 411–433, 2003.
• [18] Stańczak J., Potrzebowski H., Sęp K.: Evolutionary approach to obtain graphcovering by densely connected subgraphs, Control and Cybernetics, vol. 40(3),pp. 849–875, 2011.
• [19] Stańczak J., Trojanowski K.: Non-stationary optimization with multi-population evolutionary algorithm. In: J. Arabas (ed.), Evolutionary Computation and Global Optimization, pp. 251–260, Oficyna Wydawnicza Politechniki Warszawskiej, Warszawa, 2007.
• [20] Sutton R.S., Barto A.G.:Reinfor cement Learning: An Introduction,1st ed., MITPress, USA, 1998.
• [21] Sysło M.M., Deo N., Kowalik J.: Discrete Optimization Algorithms with Pascal Programs, Dover Publications, USA, 2006.
• [22] Thierens D., Goldberg D.: Convergence Models of Genetic Algorithm Selection Schemes. In: Y. Davidor, H. Schwefel, R. Männer (eds.), Parallel Problem Solving from Nature – PPSN III, Lecture Notes in Computer Science, vol. 866, pp. 119–129, Springer, Berlin, Heidelberg, 1994. doi: 10.1007/3-540-58484-6_256.
• [23] Zhong J., Hu X., Zhang J., Gu M.: Comparison of Performance between Different Selection Strategies on Simple Genetic Algorithms. In: International Conference on Computational Intelligence for Modelling, Control and Automation and International Conference on Intelligent Agents, Web Technologies and Internet Commerce (CIMCA-IAWTIC’06), vol. 2, pp. 1115–1121, 2005. doi: 10.1109/CIMCA.2005.1631619

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2024).