Abstract
This contribution presents a new memetic algorithm for continuous optimization problems, which is specially designed for applying intense local search methods. These local search methods make use of explicit strategy parameters to guide the search, and adapt these parameters with the purpose of producing more effective solutions. They may achieve accurate results, at the cost of requiring high intensity, making more difficult their application into a memetic algorithm. Our memetic algorithm approach assigns to each individual a local search intensity that depends on its features, by chaining different local search applications. With this technique of search chains, at each stage the local search operator may continue the operation of a previous invocation, starting from the final configuration reached by this one. The proposed memetic algorithm integrates the CMA-ES algorithm as their local search operator. We compare our proposal with other memetic algorithms and evolutionary algorithms for continuous optimization, showing that it presents a clear superiority over the compared algorithms.
This is a preview of subscription content, log in via an institution to check access.
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
Davis, L.: Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York (1991)
Goldberg, D.E., Voessner, S.: Optimizing global-local search hybrids. In: Banzhaf, W., et al. (eds.) Proceedings of the Genetic and Evolutionary Computation Conference 1999, pp. 220–228. Morgan Kaufmann, San Mateo (1999)
Moscato, P.: On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Technical report, Technical Report Caltech Concurrent Computation Program Report 826, Caltech, Pasadena, California (1989)
Moscato, P.: Memetic algorithms: a short introduction, pp. 219–234. McGraw-Hill, London (1999)
Merz, P.: Memetic Algorithms for Combinatorial Optimization Problems: Fitness Landscapes and Effective Search Strategies. PhD thesis, University of Siegen, Germany
Hart, W.: Adaptive Global Optimization With Local Search. PhD thesis, Univ. California, San Diego, CA (1994)
Hansen, N., Ostermeier, A.: Adapting Arbitrary Normal Mutation Distributions in Evolution Strategies: The Covariance Matrix Adaptation. In: Proceeding of the IEEE International Conference on Evolutionary Computation (ICEC 1996), pp. 312–317 (1996)
Hansen, N., Müller, S., Koumoutsakos, P.: Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES). Evolutionary Computation 1(11), 1–18 (2003)
Hansen, N., Kern, S.: Evaluating the CMA Evolution Strategy on Multimodal Test Functions. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.-P. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 282–291. Springer, Heidelberg (2004)
Auger, A., Hansen, N.: Performance Evaluation of an Advanced Local Search Evolutionary Algorithm. In: 2005 IEEE Congress on Evolutionary Computation, pp. 1777–1784 (2005)
Suganthan, P., Hansen, N., Liang, J., Deb, K., Chen, Y., Auger, A., Tiwari, S.: Problem definitions and evaluation criteria for the CEC 2005 special session on real parameter optimization. Technical report, Nanyang Technical University (2005)
Hansen, N.: Compilation of Results on the CEC Benchmark Function Set. In: 2005 IEEE Congress on Evolutionary Computation (2005)
Auger, A., Schoenauer, M., Vanhaecke, N.: LS-CMAES: a second-order algorithm for covariance matrix adaptation. In: Yao, X., Burke, E.K., Lozano, J.A., Smith, J., Merelo-Guervós, J.J., Bullinaria, J.A., Rowe, J.E., Tiňo, P., Kabán, A., Schwefel, H.-P. (eds.) PPSN 2004. LNCS, vol. 3242, pp. 182–191. Springer, Heidelberg (2004)
Whitley, D.: The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best. In: Proc. of the Third Int. Conf. on Genetic Algorithms, pp. 116–121 (1989)
Land, M.S.: Evolutionary Algorithms with Local Search for Combinational Optimization. PhD thesis, Univ. California, San Diego, CA (1998)
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)
Fernandes, C., Rosa, A.: A Study of non-Random Matching and Varying Population Size in Genetic Algorithm using a Royal Road Function. In: Proc. of the 2001 Congress on Evolutionary Computation, pp. 60–66 (2001)
Mülenbein, H., Schlierkamp-Voosen, D.: Predictive Models for the Breeding Genetic Algorithm in Continuous Parameter Optimization. Evolutionary Computation 1, 25–49 (1993)
Lozano, M., Herrera, F., Krasnogor, N., Molina, D.: Real-coded Memetic Algorithms with Crossover Hill-climbing. Evolutionary Computation 12(2), 273–302 (2004)
Tang, J., Lim, M., Ong, Y.: Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Computing 11(9), 873–888 (2007)
García, S., Molina, D., Lozano, M., Herrera, F.: A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: A case study on the cec 2005 special session on real parameter optimization. Journal of Heuristics (in press, 2008)
Noman, N., Iba, H.: Accelerating differential evolution using an adaptive local search. In: IEEE Transactions on evolutionary Computation (in press, 2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Molina, D., Lozano, M., García-Martínez, C., Herrera, F. (2008). Memetic Algorithm for Intense Local Search Methods Using Local Search Chains. In: Blesa, M.J., et al. Hybrid Metaheuristics. HM 2008. Lecture Notes in Computer Science, vol 5296. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88439-2_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-88439-2_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-88438-5
Online ISBN: 978-3-540-88439-2
eBook Packages: Computer ScienceComputer Science (R0)