A taxonomy for the crossover operator for real-coded genetic algorithms: An experimental study. (English) Zbl 1048.68067
Summary: The main Real-Coded Genetic Algorithm (RCGA) research effort has been spent on developing efficient crossover operators. This study presents a taxonomy for this operator that groups its instances in different categories according to the way they generate the genes of the offspring from the genes of the parents. The empirical study of representative crossovers of all the categories reveals concrete features that allow the crossover operator to have a positive influence on RCGA performance. They may be useful to design more effective crossover models.
Software:
GenocopReferences:
| [1] | Goldberg, Genetic algorithms in search, optimization, and machine learning (1989) · Zbl 0721.68056 |
| [2] | Holland, Adaptation in Natural and Artificial Systems (1992) |
| [3] | Michalewicz, Genetic Algorithms + Data Structures = Evolutionary Programs (1992) · Zbl 0763.68054 · doi:10.1007/978-3-662-02830-8 |
| [4] | Deb, Multi-objective optimization using evolutionary algorithms (2001) · Zbl 0970.90091 |
| [5] | Herrera, Tackling real-coded genetic algorithms: Operators and tools for behavioural analysis, Artif Intell Rev 12 (4) pp 265– (1998) · Zbl 0905.68116 · doi:10.1023/A:1006504901164 |
| [6] | Lucasius CB Kateman G Applications of genetic algorithms in chemometrics Schaffer JD San Mateo, CA Morgan Kaufmann Publishers 1989 170 176 |
| [7] | Blanco, A real-coded genetic algorithm for training recurrent neural networks, Neural Netw 14 (1) pp 93– (2001) · doi:10.1016/S0893-6080(00)00081-2 |
| [8] | Zamparelli, Genetically trained cellular neural networks, Neural Networks 10 (6) pp 1143– (1997) · doi:10.1016/S0893-6080(96)00128-1 |
| [9] | Hajela, Soft computing in multidisciplinary aerospace design-new directions for research, Prog Aerospace Sci 38 (1) pp 1– (2002) · doi:10.1016/S0376-0421(01)00015-X |
| [10] | Lin, Parameter design for a guidance and control system using genetic approach, Aerospace Sci Technol 5 (6) pp 425– (2001) · Zbl 1004.93037 · doi:10.1016/S1270-9638(01)01121-X |
| [11] | Oyama, Real-coded adaptive range genetic algorithm applied to transonic wing optimization, Appl Soft Comput 1 (3) pp 179– (2001) · doi:10.1016/S1568-4946(01)00017-5 |
| [12] | Périaux, Genetic Algorithms in Engineering and Computer Science pp 370– (1995) |
| [13] | Roubos, An evolutionary strategy for fed-batch bioreactor optimization; concepts and performance, J Biotechnol 67 (2-3) pp 173– (1999) · doi:10.1016/S0168-1656(98)00174-6 |
| [14] | Arfiadi, Optimal direct (static) output feedback controller using real coded genetic algorithms, Comp Struct 79 (17) pp 1625– (2001) · doi:10.1016/S0045-7949(01)00041-4 |
| [15] | Huang P-Y Chen Y-Y Design of PID controller for precision positioning table using genetic algorithms 1997 Piscataway, NJ IEEE Press 2513 2514 |
| [16] | Kawabe T Tagami T A real coded genetic algorithm for matrix inequality design approach of robust PID controller with two degrees of freedom 1997 Piscataway, NJ IEEE Press 119 124 |
| [17] | Duffy, Approximating and simulating the stochastic growth model: Parameterized expectations, neural networks, and the genetic algorithm, J Econ Dyn Control 25 (9) pp 1273– (2001) · Zbl 0981.91069 · doi:10.1016/S0165-1889(99)00077-9 |
| [18] | Harris, Automatic design of frequency sampling filters by hybrid genetic algorithm techniques, IEEE Trans Sig Process 46 (12) pp 3304– (1998) · doi:10.1109/78.735305 |
| [19] | Caorsi, A computational technique based on a real-coded genetic algorithm for microwave imaging purposes, IEEE Trans Geosci Remote Sens 38 (4) pp 1697– (2000) · doi:10.1109/36.851968 |
| [20] | Lu Y Cai X Gao Z Optimal design of special corner reflector antennas by the real-coded genetic algorithm 2000 1457 1460 |
| [21] | Qing, Microwave imaging of a perfectly conducting cylinder using a real-coded genetic algorithm, Microwaves, Antennas Propagation, IEE Proc 146 (6) pp 421– (1999) · doi:10.1049/ip-map:19990674 |
| [22] | Shi, Speed estimation of an induction motor drive using an optimized extended Kalman filter, IEEE Trans Indust Electron 49 (1) pp 124– (2002) · doi:10.1109/41.982256 |
| [23] | Azariadis, An evolutionary algorithm for generating planar developments of arbitrarily curved surfaces, Comp Industry 47 (3) pp 357– (2002) · doi:10.1016/S0166-3615(01)00155-5 |
| [24] | Thomas, Using real-coded genetic algorithms for Weibull parameter estimation, Comput Indust Eng 29 (1-4) pp 377– (1995) · doi:10.1016/0360-8352(95)00102-7 |
| [25] | Turcanu, A genetic approach to limited data tomographic reconstruction of time-resolved energy spectrum of short-pulsed neutron sources, Pattern Recognition Lett 23 (8) pp 967– (2002) · Zbl 1015.68235 · doi:10.1016/S0167-8655(02)00026-0 |
| [26] | Chang, Real-coded genetic algorithm for rule-based flood control reservoir management, Water Resource Manag 12 (3) pp 185– (1998) · doi:10.1023/A:1007900110595 |
| [27] | De Jong, A formal analysis of the role of multi-point crossover in genetic algorithms, Ann Math Artif Intell 5 (1) pp 1– (1992) · Zbl 1004.68538 |
| [28] | Kita, A comparison study of self-adaptation in evolution strategies and real-coded genetic algorithms, Evol Comput J 9 (2) pp 223– (2001) · doi:10.1162/106365601750190415 |
| [29] | Lin G Yao X Analysing crossover operators by search step size Piscataway, NJ IEEE Press 1997 13 16 |
| [30] | Liepins, Characterizing crossover in genetic algorithms, Ann Math Artif Intell 5 (1) pp 27– (1992) · Zbl 1034.68074 |
| [31] | Fernandes C Rosa A A study on non-random mating and varying population size in genetic algorithms using a royal road function Piscataway, NJ IEEE Press 2001 60 66 |
| [32] | Huang C-F An analysis of mate selection in genetic algorithms San Mateo, CA Morgan Kaufmann 2001 766 |
| [33] | Ronald E When selection meets seduction Forrest S San Mateo, CA Morgan Kaufmann 1993 167 173 |
| [34] | Deb K Joshi D Anand A Real coded evolutionary algorithms with parent-centric recombination Piscataway, NJ IEEE Press 2002 61 66 |
| [35] | Herrera, Fuzzy connectives based crossover operators to model genetic algorithms population diversity, Fuzzy Set Syst 92 (1) pp 21– (1997) · doi:10.1016/S0165-0114(96)00179-0 |
| [36] | Wright, Foundations of Genetic Algorithms 1 pp 205– (1991) |
| [37] | Kita H Kobayashi S Multi-parental extension of the unimodal normal distribution crossover for real-coded genetic algorithms Piscataway, NJ IEEE Press 1999 646 651 |
| [38] | Ortiz D Hervas C Muñoz J Genetic algorithm with crossover based on confidence intervals as an alternative to least squares estimation for nonlinear models 2001 343 347 |
| [39] | Tsutsui S Yamamura M Higuchi T Multi-parent recombination with simplex crossover in real-coded genetic algorithm San Mateo, CA Morgan Kaufmann 1999 657 664 |
| [40] | Esquivel S Leiva A Gallard R Multiple crossover per couple in genetic algorithms Piscataway, NJ IEEE Press 1997 103 106 |
| [41] | Esquivel, Enhanced evolutionary algorithms for single and multiobjective optimization in the job shop scheduling problem, J Knowledge Based Systems 15 (1-2) pp 12– (2002) |
| [42] | Satoh H Yamamura M Kobayashi S Minimal generation gap model for GAs considering both exploration and exploitation 1996 494 497 |
| [43] | Eshelman LJ Caruana A Schaffer JD Biases in the crossover landscape Schaffer JD San Mateo, CA Morgan Kaufmann Publishers 1989 86 91 |
| [44] | Syswerda G Uniform crossover in genetic algorithms Schaffer JD San Mateo, CA Morgan Kaufmann Publishers 1989 2 9 |
| [45] | Michalewicz Z Nazhiyath G Michalewicz M A note on usefulness of geometrical crossover for numerical optimization problems Cambridge, MA MIT Press 1996 305 312 |
| [46] | Bremermann, Natural Automata and Useful Simulations pp 3– (1966) |
| [47] | Eshelman LJ Schaffer JD Real-coded genetic algorithms and interval-schemata Whitley LD Foundations of Genetic Algorithms 2 San Mateo, CA Morgan Kaufmann Publishers 1993 187 202 |
| [48] | Eshelman LJ Mathias KE Schaffer JD Crossover operator biases: Exploiting the population distribution Bäck T San Mateo, CA Morgan Kaufmann 1997 354 361 |
| [49] | Schlierkamp-Voosen D Strategy adaptation by competition 1994 1270 1274 |
| [50] | Deb, Simulated binary crossover for continuous search space, Complex Syst 9 pp 115– (1995) · Zbl 0843.68023 |
| [51] | Voigt HM Mühlenbein H Cvetkovic D Fuzzy recombination for the breeder genetic algorithm Eshelman L San Mateo, CA Morgan Kaufmann Publishers 1995 104 111 |
| [52] | Herrera, Dynamic and heuristic fuzzy connectives based crossover operators for controlling the diversity and convergence of real-coded genetic algorithms, Int J Intell Syst 11 pp 1013– (1996) · Zbl 0869.68052 |
| [53] | Beyer, On self-adaptive features in real parameter evolutionary algorithms, IEEE Trans Evolut Comp 5 (3) pp 250– (2001) · doi:10.1109/4235.930314 |
| [54] | Deb, Self-adaptive genetic algorithms with simulated binary crossover, Evol Comput J 9 (2) pp 195– (2001) |
| [55] | Kita H Yamamura M A functional specialization hypothesis for designing genetic algorithms 1999 Piscataway, NJ IEEE Press 579 584 |
| [56] | Fogel, A note on empirical evaluation of intermediate recombination, Evol Comput J 3 (4) pp 491– (1995) |
| [57] | Higuchi T Tsutsui S Yamamura M Theoretic analysis of simplex crossover for real-coded genetic algorithms Parallel Problem Solving from Nature VI Berlin Springer 2000 365 374 |
| [58] | Kita H Ono I Kobayashi S Theoretical analysis of the unimodal normal distribution crossover for real-coded genetic algorithms Piscataway, NJ IEEE Press 1998 529 534 |
| [59] | Nomura T An analysis on linear crossover for real number chromosomes in an infinite population size Piscataway, NJ IEEE Press 1997 111 114 |
| [60] | Nomura, An analysis of two-parent recombinations for real-valued chromosomes in an infinite population, Evol Comput J 9 (3) pp 283– (2001) · doi:10.1162/106365601750406000 |
| [61] | Nomura T Behavior analysis of real-valued evolutionary algorithms for independent loci in an infinite population San Mateo, CA Morgan Kaufmann 2001 774 |
| [62] | Qi, Theoretical analysis of evolutionary algorithms with an infinite population size in continuous space. Part II: Analysis of the diversification role of crossover, IEEE Trans Neural Netw 5 (1) pp 120– (1994) · doi:10.1109/72.265966 |
| [63] | Baker JE Adaptative selection methods for genetic algorithms Grefenstette JJ Hillsdale, MA L. Erlbraum Associates 1987 14 21 |
| [64] | Baker JE Reducing bias and inefficiency in the selection algorithm Grefenstette JJ Hillsdale, NJ Lawrence Erlbaum 1987 14 21 |
| [65] | De Jong KA An analysis of the behavior of a class of genetic adaptive systems 1975 |
| [66] | Tsutsui, Search space boundary extension method in real-coded genetic algorithms, Inform Sci 133 pp 229– (2001) · Zbl 0981.68739 · doi:10.1016/S0020-0255(01)00087-1 |
| [67] | Herrera, Advances in Artificial Intelligence-IBERAMIA 2002, LNAI 2527 pp 392– (2002) |
| [68] | Ono I Kobayashi S A real-coded genetic algorithm for function optimization using unimodal normal distribution crossover Bäck T San Mateo, CA Morgan Kaufmmann 1997 246 253 |
| [69] | Ono I Yamamura M Kobayashi S A genetic algorithm with characteristic preservation for function optimization 1996 511 514 |
| [70] | Someya H Yamamura M Genetic algorithm with search area adaptation for the function optimization and its experimental analysis Piscataway, NJ IEEE Press 2001 933 940 |
| [71] | Sakuma J Kobayashi S Extrapolation-directed crossover for real-coded GA: Overcoming deceptive phenomena by extrapolative search Piscataway, NJ IEEE Press 2001 655 662 |
| [72] | Nomura, Lecture Notes in Artificial Intelligence 1152, in: Fuzzy Logic, Neural Networks, and Evolutionary Computation pp 55– (1996) |
| [73] | Schwefel, Numerical Optimization of Computer Models (1981) |
| [74] | Törn, Lecture Notes in Computer Science 350, in: Global Optimization (1989) |
| [75] | Griewangk, Generalized descent of global optimization, J Optimiz Theor Applicat 34 pp 11– (1981) |
| [76] | Whitley, Test driving three 1995 genetic algorithms: New test functions and geometric matching, J Heuristic 1 pp 77– (1995) · Zbl 0853.68106 |
| [77] | Eshelman LJ Mathias KE Schaffer JD Convergence controlled variation Belew R Vose M Foundations of genetic algorithms 4 San Mateo, CA Morgan Kaufmann Publishers 1997 203 224 |
| [78] | Tsutsui S Fujimoto Y Forking genetic algorithm with blocking and shrinking modes Forrest S San Mateo, CA Morgan Kaufmann Publishers 1993 206 213 |
| [79] | Storn, Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces (1995) |
| [80] | Ackley, A connectionist machine for genetic hillclimbing (1987) |
| [81] | Reynolds RC Chung C Knowledge-based self-adaptation in evolutionary programming using cultural algorithms Piscataway, NJ IEEE Press 1997 71 76 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
