Summary
It is well known that the choice of parameter settings for meta-heuristic algorithms has a dramatic impact on their search performance and this has lead to considerable interest in various mechanisms that in some way attempt to automatically adjust the algorithm’s parameters for a given problem. Of course this raises the spectre of unsuitable parameters arising from a poor choice of learning/adaptation technique. Within the field of Evolutionary Algorithms, many approaches have been tried, most notably that of “Self-Adaptation”, whereby the heuristic’s parameters are encoded alongside the candidate solution, and acted on by the same forces of evolution. Many successful applications have been reported, particularly in the sub-field of Evolution Strategies for problems in the continuous domain. In this chapter we examine the motivation and features necessary for successful self-adaptive learning to occur. Since a number of works have dealt with the continuous domain, this chapter focusses particularly on its aspects that arise when it is applied to combinatorial problems. We describe how self-adaptation may be use to control not only the parameters defining crossover and mutation, but also how it may be used to control the very definition of local search operators used within hybrid evolutionary algorithms (so-called memetic algorithms). On this basis we end by drawing some conclusions and suggestions about how this phenomenon might be translated to work within other search metaheuristics.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adapting operator settings in genetic algorithms. Evolutionary Computation 6(2), 161–184 (1998)
Angeline, P.J.: Adaptive and self-adaptive evolutionary computations. In: Computational Intelligence, pp. 152–161. IEEE Press, Los Alamitos (1995)
Arabas, J., Michalewicz, Z., Mulawka, J.: Gavaps - a genetic algorithm with varying population size, pp. 73–78 (1994)
Bäck, T.: The interaction of mutation rate, selection and self-adaptation within a genetic algorithm. In: Männer, R., Manderick, B. (eds.) Proceedings of the 2nd Conference on Parallel Problem Solving from Nature, pp. 85–94. North-Holland, Amsterdam (1992)
Bäck, T.: Self adaptation in genetic algorithms. In: Varela and Bourgine [82], pp. 263–271
Bäck, T.: Optimal mutation rates in genetic search. In: Forrest [23], pp. 2–8
Bäck, T.: Evolutionary Algorithms in Theory and Practice. Oxford University Press, Oxford (1996)
Bäck, T.: Self-adaptation. In: Bäck, T., Fogel, D.B., Michalewicz, Z. (eds.) Evolutionary Computation 2: Advanced Algorithms and Operators, ch. 21, pp. 188–211. Institute of Physics Publishing, Bristol (2000)
Bäck, T., Eiben, A.E., van der Vaart, N.A.L.: Proceedings of the 6th Conference on Parallel Problem Solving from Nature. In: Deb, K., Rudolph, G., Lutton, E., Merelo, J.J., Schoenauer, M., Schwefel, H.-P., Yao, X. (eds.) PPSN 2000. LNCS, vol. 1917, pp. 315–324. Springer, Heidelberg (2000)
Bäck, T., Fogel, D.B., Michalewicz, Z. (eds.): Handbook of Evolutionary Computation. Institute of Physics Publishing, Bristol, and Oxford University Press, New York (1997)
Bäck, T., Hofmeister, F., Schwefel, H.P.: A survey of evolution strategies. In: Belew and Booker [13], pp. 2–9
Bäck, T., Schütz, M.: Intelligent mutation rate control in canonical genetic algorithms. In: Ras, Z. (ed.) Proceedings of the Ninth International Symposium on Methodologies for Intelligent Systems, pp. 158–167. Springer, Heidelberg (1996)
Belew, R.K., Booker, L.B. (eds.): Proceedings of the 4th International Conference on Genetic Algorithms. Morgan Kaufmann, San Francisco (1991)
Beyer, H., Deb, K.: On self-adaptive features in real-parameter evolutionary algorithms. IEEE Transactions on Evolutionary Computation 5(3), 250–270 (2001)
Beyer, H.-G.: The Theory of Evolution Strategies. Springer, Berlin (2001)
2003 Congress on Evolutionary Computation (CEC 2003). IEEE Press, Piscataway (2003)
Davis, L.: Adapting operator probabilities in genetic algorithms. In: Schaffer [54], pp. 61–69
De Jong, K.A.: An Analysis of the Behavior of a Class of Genetic Adaptive Systems. PhD thesis, University of Michigan (1975)
Deb, K., Goldberg, D.E.: Analyzing deception in trap functions. In: Whitley, L.D. (ed.) Foundations of Genetic Algorithms 2, pp. 93–108. Morgan Kaufmann, San Francisco (1992)
Eiben, A.E., Hinterding, R., Michalewicz, Z.: Parameter control in evolutionary algorithms. IEEE Transactions on Evolutionary Computation 3(2), 124–141 (1999)
Eiben, A.E., Smith, J.E.: Introduction to Evolutionary Computation. Springer, Heidelberg (2003)
Fogel, D.B.: Evolutionary Computation. IEEE Press, Los Alamitos (1995)
Forrest, S. (ed.): Proceedings of the 5th International Conference on Genetic Algorithms. Morgan Kaufmann, San Francisco (1993)
Glickman, M., Sycara, K.: Evolutionary algorithms: Exploring the dynamics of self-adaptation, pp. 762–769 (1998)
Glickman, M., Sycara, K.: Reasons for premature convergence of self-adaptating mutation rates. In: 2000 Congress on Evolutionary Computation (CEC 2000), pp. 62–69. IEEE Press, Piscataway (2000)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading (1989)
Goldberg, D.E., Korb, B., Deb, K.: Messy genetic algorithms: Motivation, analysis, and first results. Complex Systems 3(5), 493–530 (1989)
Grefenstette, J.J.: Optimisation of control parameters for genetic algorithms. IEEE Transaction on Systems, Man and Cybernetics 16(1), 122–128 (1986)
Guervós, J.J.M., Adamidis, P.A., Beyer, H.-G., Fernández-Villacañas, J.-L., Schwefel, H.-P. (eds.) PPSN 2002. LNCS, vol. 2439. Springer, Heidelberg (2002)
Hansen, N.: An analysis of mutative σ-self-adaptation on linear fitness functions. Evolutionary Computation 14(3), 255–275 (2006)
Hansen, N., Ostermeier, A.: Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation 9(2), 159–195 (2001)
Harik, G., Goldberg, D.E.: Learning linkage. Technical Report IlliGAL 96006, Illinois Genetic Algorithms Laboratory, University of Illinois (1996)
Hesser, J., Manner, R.: Towards an optimal mutation probablity in genetic algorithms. In: Schwefel, H.-P., Männer, R. (eds.) PPSN 1990. LNCS, vol. 496, pp. 23–32. Springer, Heidelberg (1991)
Hinterding, R., Michalewicz, Z., Peachey, T.C.: Self adaptive genetic algorithm for numeric functions. In: Voigt et al. [83], pp. 420–429
Proceedings of the 1996 IEEE Conference on Evolutionary Computation. IEEE Press, Piscataway (1996)
Jain, A., Fogel, D.B.: Case studies in applying fitness distributions in evolutionary algorithms. II. Comparing the improvements from crossover and Gaussian mutation on simple neural networks. In: Yao, X., Fogel, D.B. (eds.) Proc. of the 2000 IEEE Symposium on Combinations of Evolutionary Computation and Neural Networks, pp. 91–97 (2000)
Julstrom, B.A.: What have you done for me lately?: Adapting operator probabilities in a steady-state genetic algorithm. In: Eshelman, L.J. (ed.) Proceedings of the 6th International Conference on Genetic Algorithms, pp. 81–87. Morgan Kaufmann, San Francisco (1995)
Kargupta, H.: The gene expression messy genetic algorithm. In: ICEC-96 [35], pp. 814–819
Kargupta, H., Bandyopadhyay, S.: A perspective on the foundation and evolution of the linkage learning genetic algorithms. J Computer Methods in Applied Mechanics and Engineering 2186, 266–294 (2000)
Kauffman, S.A.: Origins of Order: Self-organization and Selection in Evolution. Oxford University Press, New York (1993)
Krasnogor, N.: Coevolution of genes and memes in memetic algorithms. In: Wu, A.S. (ed.) Proceedings of the 1999 Genetic and Evolutionary Computation Conference Workshop Program (1999)
Krasnogor, N.: Studies in the Theory and Design Space of Memetic Algorithms. PhD thesis, University of the West of England (2002)
Krasnogor, N.: Self-generating metaheuristics in bioinformatics: The protein structure comparison case. Genetic Programming and Evolvable Machines 5(2), 181–201 (2004)
Krasnogor, N., Blackburne, B.P., Burke, E.K., Hirst, J.D.: Multimeme algorithms for protein structure prediction. In: Guervos et al. [29], pp. 769–778
Krasnogor, N., Gustafson, S.: Toward truly “memetic” memetic algorithms: discussion and proofs of concept. In: Corne, D., Fogel, G., Hart, W., Knowles, J., Krasnogor, N., Roy, R., Smith, J., Tiwari, A. (eds.) Advances in Nature-Inspired Computation: The PPSN VII Workshops, pp. 9–10. University of Reading, Reading, UK (2002); PEDAL (Parallel, Emergent & Distributed Architectures Lab)
Krasnogor, N., Gustafson, S.M.: A study on the use of “self-generation” in memetic algorithms. Natural Computing 3(1), 53–76 (2004)
Krasnogor, N., Smith, J.E.: Emergence of profitable search strategies based on a simple inheritance mechanism. In: Spector et al. [78], pp. 432–439
Lee, M., Takagi, H.: Dynamic control of genetic algorithms using fuzzy logic techniques. In: Forrest [23], pp. 76–83
Liang, K.-H., Xao, X., Liu, Y., Newton, C., Hoffman, D.: An experimental investigation of self-adaptation in evolutionary programming (1998)
Lis, J.: Parallel genetic algorithm with dynamic control parameter. In: ICEC-96 [35], pp. 324–329
Meyer-Nieberg, S., Beyer, H.G.: Self-adaptation in evolutionary algorithms. In: Parameter Setting in Evolutionary Algorithms, pp. 47–75 (2007)
Ong, Y.S., Lim, M.H., Zhu, N., Wong, K.W.: Classification of adaptive memetic algorithms: A comparative study. IEEE Transactions on Systems Man and Cybernetics Part B 36(1) (2006)
Rudolph, G.: Self-adaptive mutations lead to premature convergence. IEEE Transactions on Evolutionary Computation 5, 410–414 (2001)
Schaffer, J.D. (ed.): Proceedings of the 3rd International Conference on Genetic Algorithms. Morgan Kaufmann, San Francisco (1989)
Schaffer, J.D., Caruana, R.A., Eshelman, L.J., Das, R.: A study of control parameters affecting online performance of genetic algorithms for function optimisation. In: Schaffer [54], pp. 51–60
Schaffer, J.D., Eshelman, L.J.: On crossover as an evolutionarily viable strategy. In: Belew Booker [13], pp. 61–68
Schaffer, J.D., Morishima, A.: An adaptive crossover distribution mechanism for genetic algorithms. In: Grefenstette, J.J. (ed.) Proceedings of the 2nd International Conference on Genetic Algorithms and Their Applications, pp. 36–40. Lawrence Erlbaum, Hillsdale (1987)
Schlierkamp-Voosen, D., Mühlenbein, H.: Strategy adaptation by competing subpopulations. In: Davidor, Y., Männer, R., Schwefel, H.-P. (eds.) PPSN 1994. LNCS, vol. 866, pp. 199–209. Springer, Heidelberg (1994)
Schwefel, H.-P.: Numerische Optimierung von Computer-Modellen Mittels der Evolutionsstrategie. ISR, vol. 26. Birkhaeuser, Basel/Stuttgart (1977)
Schwefel, H.-P.: Numerical Optimisation of Computer Models. Wiley, New York (1981)
Smith, J.E.: Self Adaptation in Evolutionary Algorithms. PhD thesis, University of the West of England, Bristol, UK (1998)
Smith, J.E.: Modelling GAs with self-adaptive mutation rates. In: Spector et al. [78], pp. 599–606
Smith, J.E.: Co-evolution of memetic algorithms: Initial investigations. In: Guervos et al. [29], pp. 537–548
Smith, J.E.: On appropriate adaptation levels for the learning of gene linkage. J. Genetic Programming and Evolvable Machines 3(2), 129–155 (2002)
Smith, J.E.: Co-evolving memetic algorithms: A learning approach to robust scalable optimisation. In: CEC 2003, [16], pp. 498–505 (2003)
Smith, J.E.: Parameter perturbation mechanisms in binary coded gas with self-adaptive mutation. In: Rowe, P., De Jong, Cotta (eds.) Foundations of Genetic Algorithms 7, pp. 329–346. Morgan Kaufmann, San Francisco (2003)
Smith, J.E.: Protein structure prediction with co-evolving memetic algorithms. In: CEC 2003 [16], pp. 2346–2353 (2003)
Smith, J.E.: The co-evolution of memetic algorithms for protein structure prediction. In: Hart, W.E., Krasnogor, N., Smith, J.E. (eds.) Recent Advances in Memetic Algorithms, pp. 105–128. Springer, New York (2004)
Smith, J.E.: Co-evolving memetic algorithms: A review and progress report. IEEE Transactions in Systems, Man and Cybernetics, part B 37(1), 6–17 (2007)
Smith, J.E.: Credit assignment in adaptive memetic algorithms. In: Proceedings of Gecco, the ACM-SIGEVO conference on Evolutionary computation, pp. 1412–1419 (2007)
Smith, J.E., Fogarty, T.C.: An adaptive poly-parental recombination strategy. In: Fogarty, T.C. (ed.) Evolutionary Computing 2, pp. 48–61. Springer, Berlin (1995)
Smith, J.E., Fogarty, T.C.: Adaptively parameterised evolutionary systems: Self adaptive recombination and mutation in a genetic algorithm. In: Voigt et al. [83], pp. 441–450
Smith, J.E., Fogarty, T.C.: Recombination strategy adaptation via evolution of gene linkage. In: ICEC-96 [35], pp. 826–831 (1996)
Smith, J.E., Fogarty, T.C.: Self adaptation of mutation rates in a steady state genetic algorithm. In: ICEC-96 [35], pp. 318–323 (1996)
Smith, J.E., Fogarty, T.C.: Operator and parameter adaptation in genetic algorithms. Soft Computing 1(2), 81–87 (1997)
Smith, R.E., Smuda, E.: Adaptively resizing populations: Algorithm, analysis and first results. Complex Systems 9(1), 47–72 (1995)
Spears, W.M.: Adapting crossover in evolutionary algorithms. In: McDonnell, J.R., Reynolds, R.G., Fogel, D.B. (eds.) Proceedings of the 4th Annual Conference on Evolutionary Programming, pp. 367–384. MIT Press, Cambridge (1995)
Spector, L., Goodman, E., Wu, A., Langdon, W.B., Voigt, H.-M., Gen, M., Sen, S., Dorigo, M., Pezeshk, S., Garzon, M., Burke, E. (eds.): Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001). Morgan Kaufmann, San Francisco (2001)
Stephens, C.R., Garcia Olmedo, I., Moro Vargas, J., Waelbroeck, H.: Self-adaptation in evolving systems. Artificial Life 4, 183–201 (1998)
Stone, C., Smith, J.E.: Strategy parameter variety in self-adaption. In: Langdon, W.B., Cantú-Paz, E., Mathias, K., Roy, R., Davis, D., Poli, R., Balakrishnan, K., Honavar, V., Rudolph, G., Wegener, J., Bull, L., Potter, M.A., Schultz, A.C., Miller, J.F., Burke, E., Jonoska, N. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), July 9–13, 2002, pp. 586–593. Morgan Kaufmann, San Francisco (2002)
Syswerda, G.: A study of reproduction in generational and steady state genetic algorithms. In: Rawlins, G. (ed.) Foundations of Genetic Algorithms, pp. 94–101. Morgan Kaufmann, San Francisco (1991)
Varela, F.J., Bourgine, P. (eds.): Toward a Practice of Autonomous Systems: Proceedings of the 1st European Conference on Artificial Life. MIT Press, Cambridge (1992)
Voigt, H.-M., Ebeling, W., Rechenberg, I., Schwefel, H.-P. (eds.): Proceedings of the 4th Conference on Parallel Problem Solving from Nature. PPSN 1996. LNCS, vol. 1141. Springer, Heidelberg (1996)
Wolpert, D.H., Macready, W.G.: No Free Lunch theorems for optimisation. IEEE Transactions on Evolutionary Computation 1(1), 67–82 (1997)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Smith, J.E. (2008). Self-Adaptation in Evolutionary Algorithms for Combinatorial Optimisation. In: Cotta, C., Sevaux, M., Sörensen, K. (eds) Adaptive and Multilevel Metaheuristics. Studies in Computational Intelligence, vol 136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-79438-7_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-79438-7_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-79437-0
Online ISBN: 978-3-540-79438-7
eBook Packages: EngineeringEngineering (R0)