×

Global and local real-coded genetic algorithms based on parent-centric crossover operators. (English) Zbl 1146.90532

Summary: Parent-centric real-parameter crossover operators create the offspring in the neighbourhood of one of the parents, the female parent. The other parent, the male one, defines the range of the neighbourhood. With the aim of improving the behaviour of these crossover operators, we present three processes that are performed before their application. First, a female and male differentiation process determines the individuals in the population that may become female or/and male parents. Then, two different selection mechanisms choose the female and male parents from each group. In addition, we tackle the election of the most adequate evolution model to take out profit from these parent selection mechanisms. The experimental results confirm that these three processes may enhance the operation of the parent-centric crossover operators.

MSC:

90C59 Approximation methods and heuristics in mathematical programming

Software:

Genocop; CMA-ES; CIXL2
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bäck, T., 1994. Selective pressure in evolutionary algorithms: A characterization of selection mechanisms. In: Proc. of the First IEEE Conference on Evolutionary Computation, pp. 57-62.; Bäck, T., 1994. Selective pressure in evolutionary algorithms: A characterization of selection mechanisms. In: Proc. of the First IEEE Conference on Evolutionary Computation, pp. 57-62.
[2] Bäck, T., Evolutionary Algorithms in Theory and Practice (1996), Oxford University Press · Zbl 0877.68060
[3] Ballester, P. J.; Carter, J. N., Real-parameter genetic algorithms for finding multiple optimal solutions in multi-modal optimization, (Cantú-Paz, Erick; etal., Proc. of the Genetic and Evolutionary Computation Conference. Proc. of the Genetic and Evolutionary Computation Conference, LNCS, vol. 2723 (2003), Springer), 706-717 · Zbl 1028.68668
[4] Ballester, P. J.; Carter, J. N., An effective real-parameter genetic algorithm with parent centric normal crossover for multimodal optimisation, (Proc. of the Genetic and Evolutionary Computation Conference. Proc. of the Genetic and Evolutionary Computation Conference, LNCS, vol. 3102 (2004), Springer), 901-913
[5] Bandyopadhyay, S.; Pal, S. K.; Maulik, U., Incorporating chromosome differentiation in genetic algorithms, Information Sciences, 104, 293-319 (1998)
[6] Beyer, H.-G.; Deb, K., On self-adaptive features in real-parameter evolutionary algorithms, IEEE Transactions on Evolutionary Computation, 5, 3, 250-270 (2001)
[7] Beyer, H.-G.; Schwefel, H.-P., Evolution strategies, Natural Computing, 1, 3-52 (2002) · Zbl 1014.68134
[8] Bonham, C. R.; Parmee, I. C., An investigation of exploration and exploitation within cluster oriented genetic algorithms (COGAs), (Proc. of the Genetic and Evolutionary Computation Conference 1999 (1999), Morgan Kaufmann: Morgan Kaufmann San Francisco, California), 1491-1497
[9] Branke, J.; Cutaia, M.; Dold, H., Reducing genetic drift in steady state evolutionary algorithms, (Banzhaf, W.; etal., Proc. of the Genetic and Evolutionary Computation Conference (1999), Morgan Kaufmann: Morgan Kaufmann San Francisco, California), 68-74
[10] Cedeño, W.; Vemuri, V.; Slezak, T., Multi-niche crowding in genetic algorithms and its application to the assembly of DNA restriction-fragments, Evolutionary Computation, 2, 4, 321-345 (1995)
[11] Chelouah, R.; Siarry, P., A continuous genetic algorithm designed for the global optimization of multimodal functions, Journal of Heuristic, 6, 2, 191-213 (2000) · Zbl 0969.68641
[12] Chelouah, R.; Siarry, P., Genetic and Nelder-Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions, European Journal of Operational Research, 148, 335-348 (2003) · Zbl 1035.90062
[13] Craighurst, R.; Martin, W., Enhancing GA performance through crossover prohibitions based on ancestry, (Eshelman, L. J., Proc. 6th International Conference on Genetic Algorithms (1995), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 130-137
[14] Davis, L., Handbook of Genetic Algorithms (1991), Van Nostrand Reinhold: Van Nostrand Reinhold New York
[15] Deb, K., Multi-Objective Optimization using Evolutionary Algorithms (2001), John Wiley & Sons: John Wiley & Sons New York · Zbl 0970.90091
[16] Deb, K., A population-based algorithm-generator for real-parameter optimization, Soft Computing, 9, 4, 236-253 (2005) · Zbl 1062.90075
[17] Deb, K.; Agrawal, R. B., Simulated binary crossover for continuous search space, Complex System, 9, 115-148 (1995) · Zbl 0843.68023
[18] Deb, K.; Beyer, H., Self-adaptive genetic algorithms with simulated binary crossover, Evolutionary Computation Journal, 9, 2, 195-219 (2001)
[19] Deb, K.; Anand, A.; Joshi, D., A computationally efficient evolutionary algorithm for real-parameter evolution, Evolutionary Computation Journal, 10, 4, 371-395 (2002)
[20] De Jong, K.A., 1975. An analysis of the behavior of a class of genetic adaptive systems. Doctoral dissertation, University of Michigan, Ann Arbor. Dissertation Abstracts International 36(10), 5140B (University Microfilms No. 76-9381).; De Jong, K.A., 1975. An analysis of the behavior of a class of genetic adaptive systems. Doctoral dissertation, University of Michigan, Ann Arbor. Dissertation Abstracts International 36(10), 5140B (University Microfilms No. 76-9381).
[21] De Jong, K. A.; Sarma, J., Generation gaps revisited, (Whitley, L. D., Foundations of Genetic Algorithms, vol. 2 (1993), Morgan Kaufmann: Morgan Kaufmann San Mateo, California), 19-28
[22] De Jong, K. A.; Spears, W. M., A formal analysis of the role of multi-point crossover in genetic algorithms, Annals of Mathematics and Artificial Intelligence, 5, 1, 1-26 (1992) · Zbl 1004.68538
[23] De Jong, E. D.; Watson, R. A.; Pollack, J. B., Reducing bloat and promoting diversity using multi-objective methods, (Spector, L.; etal., Proc. of the Genetic and Evolutionary Computation Conference (2001), Morgan Kaufmann: Morgan Kaufmann San Francisco, California), 11-18
[24] Eberhart, R.C., Kennedy, J., 1995. A new optimizer using particle swarm theory. In: Proc. of the 6th International Symposium on Micromachine and Human Science, Nagoya, Japan, pp. 39-43.; Eberhart, R.C., Kennedy, J., 1995. A new optimizer using particle swarm theory. In: Proc. of the 6th International Symposium on Micromachine and Human Science, Nagoya, Japan, pp. 39-43.
[25] Eiben, A. E.; Hinterding, R.; Michalewicz, Z., Parameter control in evolutionary algorithms, IEEE Transactions on Evolutionary Computation, 3, 2, 124-141 (1999)
[26] Eshelman, L. J., The CHC adaptive search algorithm: How to have safe search when engaging in non-traditional genetic recombination, (Rawlin, G. J.E., Foundations of Genetic Algorithms, vol. 1 (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, California), 265-283
[27] Eshelman, L. J.; Schaffer, J. D., Preventing premature convergence in genetic algorithms by preventing incest, (Belew, R.; Booker, L. B., Proc. of the Fourth International Conference on Genetic Algorithms (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, California), 115-122
[28] Eshelman, L. J.; Mathias, K. E.; Schaffer, J. D., Convergence controlled variation, (Belew, R.; Vose, M., Foundations of Genetic Algorithms, vol. 4 (1997), Morgan Kaufmann: Morgan Kaufmann San Mateo, California), 203-224
[29] Fernandes, C.; Rosa, A., A Study on non-random mating and varying population size in genetic algorithms using a royal road function, (Proc. of the 2001 Congress on Evolutionary Computation (2001), IEEE Press: IEEE Press Piscataway, New Jersey), 60-66
[30] Fogel, D. B., Evolutionary programming: An introduction and some current directions, Statistics and Computing, 4, 113-129 (1994)
[31] Fogel, D. B., Evolutionary Computation: Toward a New Philosophy of Machine Intelligence (1995), IEEE Press: IEEE Press Piscataway, New York
[32] Ghosh, A.; Tsutsui, S.; Tanaka, H., Function optimization in nonstationary environment using steady state genetic algorithms with aging of individuals, (Proc. of the 1998 IEEE International Conference on Evolutionary Computation (1998), IEEE Press: IEEE Press New York), 666-671
[33] Goh, K. S.; Lim, A.; Rodrigues, B., Sexual selection for genetic algorithms, Artificial Intelligence Reviews, 19, 123-152 (2003)
[34] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine Learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[35] Goldberg, D. E.; Deb, K., A comparative analysis of selection schemes used in genetic algorithms, (Rawlins, G. J.E., Foundations of Genetic Algorithms (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, California), 69-93
[36] Hansen, N., Ostermeier, A., 1996. Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In: Proc. of the 1996 IEEE Conference on Evolutionary Computation, pp. 312-317.; Hansen, N., Ostermeier, A., 1996. Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In: Proc. of the 1996 IEEE Conference on Evolutionary Computation, pp. 312-317.
[37] Hansen, N.; Ostermeier, A., Completely derandomized self-adaptation in evolution strategies, Evolutionary Computation, 9, 2, 159-195 (2001)
[38] Hansen, N.; Müller, S. D.; Koumoutsakos, P., Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES), Evolutionary Computation, 11, 1, 1-18 (2003)
[39] Harik, G., Finding multimodal solutions using restricted tournament selection, (Eshelman, L. J., Proc. 6th International Conference on Genetic Algorithms (1995), Morgan Kaufmann: Morgan Kaufmann San Mateo, California), 24-31
[40] Herrera, F.; Lozano, M., Gradual distributed real-coded genetic algorithms, IEEE Transactions on Evolutionary Computation, 4, 1, 43-63 (2000)
[41] Herrera, F.; Lozano, M.; Verdegay, J. L., Tackling real-coded genetic algorithms: Operators and tools for the behavioral analysis, Artificial Intelligence Reviews, 12, 4, 265-319 (1998) · Zbl 0905.68116
[42] Herrera, F.; Lozano, M.; Sánchez, A. M., A taxonomy for the crossover operator for real-coded genetic algorithms. An experimental study, International Journal of Intelligent Systems, 18, 3, 309-338 (2003) · Zbl 1048.68067
[43] Herrera, F.; Lozano, M.; Sánchez, A. M., Hybrid crossover operators for real-coded genetic algorithms: An experimental study, Soft Computing, 9, 4, 280-298 (2005) · Zbl 1066.68155
[44] Hervás-Martínez, C.; Ortiz-Boyer, D., Analyzing the statistical features of CIXL2 crossover offspring, Soft Computing, 9, 4, 270-279 (2005) · Zbl 1066.68156
[45] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), The University of Michigan Press, The MIT Press, London, 1992
[46] Hutter, M., Fitness uniform selection to preserve genetic diversity, (Proc. of the 2002 Congress on Evolutionary Computation (2002), IEEE Press: IEEE Press Piscataway, New Jersey), 783-788
[47] Ichikawa, Y., Ishiiolland, Y., 1993. Retaining diversity of genetic algorithms for multivariable optimization and neural network learning. In: Proc. IEEE International Conference on Neural Networks, San Francisco, California, pp. 1110-1114.; Ichikawa, Y., Ishiiolland, Y., 1993. Retaining diversity of genetic algorithms for multivariable optimization and neural network learning. In: Proc. IEEE International Conference on Neural Networks, San Francisco, California, pp. 1110-1114.
[48] Kazarlis, S. A.; Papadakis, S. E.; Theocharis, J. B.; Petridis, V., Microgenetic algorithms as generalized hill-climbing operators for GA Optimization, IEEE Transaction on Evolutionary Computation, 5, 3, 204-217 (2001)
[49] van Kemenade, C. H.M.; Kok, J. N.; Eiben, A. E., Raising GA performance by simultaneous tuning of selection pressure and recombination disruptiveness, (Proc. of the 2nd IEEE World Conference on Evolutionary Computation (1995), IEEE Press), 345-351
[50] Kennedy, J., Eberhart, R.C., 1995. Particle swarm optimization. In: Proc. of the IEEE International Conference on Neural Networks, Piscataway, New Jersey, pp. 1942-1948.; Kennedy, J., Eberhart, R.C., 1995. Particle swarm optimization. In: Proc. of the IEEE International Conference on Neural Networks, Piscataway, New Jersey, pp. 1942-1948.
[51] Kirkpatric, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680 (1983) · Zbl 1225.90162
[52] Kita, H., A comparison study of self-adaptation in evolution strategies and real-coded genetic algorithms, Evolutionary Computation Journal, 9, 2, 223-241 (2001)
[53] Kuo, T.; Hwang, S. Y., A genetic algorithm with disruptive selection, IEEE Transactions on Systems, Man, and Cybernetics, 26, 2, 299-307 (1996)
[54] Lee, C.-Y., Entropy-Boltzmann selection in the genetic algorithms, IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics, 33, 1, 138-149 (2003)
[55] Lee, C.-Y.; Yao, X., Evolutionary programming using mutations based on the Levy probability distribution, IEEE Transactions on Evolutionary Computation, 8, 1, 1-13 (2004)
[56] Liang, J.J., Qin, A.K., Suganthan, P.N., Baskar, S., 2004a. Particle swarm optimization algorithms with novel learning strategies. In: Proc. of the IEEE International Conference on Systems Man and Cybernetics, The Netherlands, pp. 3659-3664.; Liang, J.J., Qin, A.K., Suganthan, P.N., Baskar, S., 2004a. Particle swarm optimization algorithms with novel learning strategies. In: Proc. of the IEEE International Conference on Systems Man and Cybernetics, The Netherlands, pp. 3659-3664.
[57] Liang, J. J.; Qin, A. K.; Suganthan, P. N.; Baskar, S., Evaluation of comprehensive learning particle swarm optimizer, Lecture Notes in Computer Science, 3316, 230-235 (2004)
[58] Lozano, M.; Herrera, F.; Krasnogor, N.; Molina, D., Real-coded memetic algorithms with crossover hill-climbing, Evolutionary Computation Journal, 12, 3, 273-302 (2004)
[59] Mahfoud, S.W., 1995. Niching methods for genetic algorithms. IlliGAL report 95001, University of Illinois at Urbana-Champaign, IL, Illinois Genetic Algorithms Laboratory.; Mahfoud, S.W., 1995. Niching methods for genetic algorithms. IlliGAL report 95001, University of Illinois at Urbana-Champaign, IL, Illinois Genetic Algorithms Laboratory.
[60] Matsui, K., 1999. New selection method to improve the population diversity in genetic algorithms. Proc. IEEE International Conference on Systems, Man, and Cybernetics, pp. 625-630.; Matsui, K., 1999. New selection method to improve the population diversity in genetic algorithms. Proc. IEEE International Conference on Systems, Man, and Cybernetics, pp. 625-630.
[61] Michalewicz, Z., Genetic Algorithms+Data Structures=Evolution Programs (1992), Springer-Verlag: Springer-Verlag New York · Zbl 0763.68054
[62] Mori, N.; Yoshida, J.; Tamaki, H.; Kita, H.; Nichikawa, Y. A., Thermodynamical selection rule for genetic algorithms, (Proc. of the 2nd IEEE Conference on Evolutionary Computation (ICEC’95) (1995), IEEE Press: IEEE Press New York), 188-192
[63] Moscato, P. A., Memetic algorithms: A short introduction, (Corne, D.; Dorigo, M.; Glower, R., New Ideas in Optimization (1999), McGraw-Hill: McGraw-Hill London), 219-234
[64] Renders, J-M.; Flasse, S. P., Hybrid methods using genetic algorithms for global optimisation, IEEE Transactions on Systems, Man, and Cybernetics, 26, 2, 243-258 (1996)
[65] Schwefel, H.-P., Evolution and Optimum Seeking (1995), Wiley: Wiley New York
[66] Shimodaira, H., A new genetic algorithm using large mutation rates and population-elitist selection (GALME), (Proc. of the International Conference on Tools with Artificial Intelligence (1996), IEEE Computer Society), 25-32
[67] Shimodaira, H., A diversity control oriented genetic algorithm (DCGA): Development and experimental results, (Proc. of the Genetic and Evolutionary Computation Conference 1999 (1999), Morgan Kaufmann: Morgan Kaufmann San Francisco, California), 603-611
[68] Siarry, P.; Berthiau, G.; Durbin, F.; Haussy, J., Enhanced simulated annealing for globally minimizing functions of many-continuous variables, ACM Transactions on Mathematical Software, 23, 2, 209-228 (1997) · Zbl 0887.65067
[69] Solis, F. J.; Wets, R. J.B., Minimization by random search techniques, Mathematical Operations Research, 6, 19-30 (1981) · Zbl 0502.90070
[70] Someya, H.; Yamamura, M., A robust real-coded evolutionary algorithm with toroidal search space conversion, Soft Computing, 9, 4, 254-269 (2005) · Zbl 1066.68033
[71] Storn, R.; Price, K., Differential evolution – a simple and efficient heuristic for global optimization over continuous spaces, Journal of Global Optimization, 11, 4, 341-359 (1997) · Zbl 0888.90135
[72] Syswerda, G., Uniform crossover in genetic algorithms, (David Schaffer, J., Proc. of the Third International Conference on Genetic Algorithms (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo), 2-9
[73] Takahashi, O., Kobayashi, S., 2001. An adaptive neighboring search using crossover-like mutation for multi modal function optimisation. In: IEEE International Conference on Systems, Man, and Cybernetics, pp. 261-267.; Takahashi, O., Kobayashi, S., 2001. An adaptive neighboring search using crossover-like mutation for multi modal function optimisation. In: IEEE International Conference on Systems, Man, and Cybernetics, pp. 261-267.
[74] Ting, C.-K.; Li, S.-T.; Lee, C., On the harmonious mating strategy through tabu search, Information Sciences, 156, 189-214 (2003)
[75] Toffolo, A.; Benini, E., Genetic diversity as an objective in multi-objective evolutionary algorithms, Evolutionary Computation, 11, 2, 151-167 (2003)
[76] Tsutsui, S.; Fujimoto, Y., Forking genetic algorithm with blocking and shrinking modes, (Forrest, S., Proc. of the Fifth International Conference on Genetic Algorithms (1993), Morgan Kaufmann Publishers: Morgan Kaufmann Publishers San Mateo San Mateo, CA), 206-213
[77] Voigt, H. M.; Mühlenbein, H.; Cvetkovic, D., Fuzzy recombination for the breeder genetic algorithm, (Eshelman, L., Proc. of the Sixth International Conference on Genetic Algorithms (1995), Morgan Kaufmann: Morgan Kaufmann San Francisco), 104-111
[78] Whitley, D., The GENITOR algorithm and selection pressure: Why rank-based allocation of reproductive trials is best, (David Schaffer, J., Proc. of the Third International Conference on Genetic Algorithms (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo), 116-121
[79] Winter, G.; Galvan, B.; Alonso, S.; Gonzalez, B.; Jiménez, J. I.; Greiner, D., A flexible evolutionary agent: Cooperation and competition among real-coded evolutionary operators, Soft Computing, 9, 4, 299-323 (2005) · Zbl 1066.68157
[80] Yang, J.-M.; Kao, C.-Y., Integrating adaptive mutations and family competition into genetic algorithms as function optimiser, Soft Computing, 4, 89-102 (2000)
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.