zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification: overview and progress report. (English) Zbl 1173.90590
Summary: Nowadays, a promising way to obtain hybrid metaheuristics concerns the combination of several search algorithms with strong specialization in intensification and/or diversification. The flexible architecture of evolutionary algorithms allows specialized models to be obtained with the aim of providing intensification and/or diversification. The outstanding role that is played by evolutionary algorithms at present justifies the choice of their specialist approaches as suitable ingredients to build hybrid metaheuristics.This paper focuses on hybrid metaheuristics with evolutionary algorithms specializing in intensification and diversification. We first give an overview of the existing research on this topic, describing several instances grouped into three categories that were identified after reviewing specialized literature. Then, with the aim of complementing the overview and providing additional results and insights on this line of research, we present an instance that consists of an iterated local search algorithm with an evolutionary perturbation technique. The benefits of the proposal in comparison to other iterated local search algorithms proposed in the literature to deal with binary optimization problems are experimentally shown. The good performance of the reviewed approaches and the suitable results shown by our instance allow an important conclusion to be achieved: the use of evolutionary algorithms specializing in intensification and diversification for building hybrid metaheuristics becomes a prospective line of research for obtaining effective search algorithms.
MSC:
90C59Approximation methods and heuristics
Software:
CMA-ES
References:
[1]Alba, E.; Tomassini, M.: Parallelism and evolutionary algorithms, IEEE trans evol comput 6, No. 5, 443-462 (2002)
[2]Alba, E.; Luna, F.; Nebro, A.; Troya, J. M.: Parallel heterogeneous genetic algorithms for continuous optimization, Parallel comput 30, No. 5 – 6, 699-719 (2004)
[3]Alba, E.; Dorronsoro, B.: The exploration/exploitation tradeoff in dynamic cellular genetic algorithms, IEEE trans evol comput 9, No. 2, 126-142 (2005)
[4]Alba E, editor. Parallel metaheuristics: a new class of algorithms. New York: Wiley; 2005.
[5]Auger, A.; Hansen, N.: Performance evaluation of an advanced local search evolutionary algorithm, , 1777-1784 (2005)
[6]Auger, A.; Hansen, N.: A restart CMA evolution strategy with increasing population size, , 1769-1776 (2005)
[7]Bäck, T.: Evolutionary algorithms in theory and practice, (1996)
[8]Bäck, T.; Fogel, D. B.; Michalewicz, Z.: Handbook of evolutionary computation, (1997)
[9]Beyer, H. -G.; Schwefel, H. -P.: Evolution strategies: a comprehensive introduction, Nat comput 1, 2-52 (2002) · Zbl 1014.68134 · doi:10.1023/A:1015059928466
[10]Blum, C.: ACO applied to group shop scheduling: a case study on intensification and diversification, Proceedings of the third international workshop ANTS. Lecture notes in computer science 2463, 14-27 (2002)
[11]Blum, C.; Roli, A.: Metaheuristics in combinatorial optimization: overview and conceptual comparison, ACM comput surv 35, No. 3, 268-308 (2003)
[12]Bonissone, P. P.; Subbu, R.; Eklund, N.; Kiehl, T. R.: Evolutionary algorithms + domain knowledge = real-world evolutionary computation, IEEE trans evol comput 10, No. 3, 256-280 (2006)
[13]Chaiyaratana, N.; Piroonratana, T.; Sangkawelert, N.: Effects of diversity control in single-objective and multi-objective genetic algorithms, J heuristics 13, No. 1, 1-34 (2007)
[14]Chelouah, R.; Siarry, P.: Genetic and Nelder – Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions, Eur J oper res 148, 335-348 (2003) · Zbl 1035.90062 · doi:10.1016/S0377-2217(02)00401-0
[15]Chen, X.; Li, Y.: A modified PSO structure resulting in high exploration ability with convergence guaranteed, IEEE trans syst man cybern B 37, No. 5, 1271-1289 (2007)
[16]Cordeau, J. -F.; Laporte, G.; Pasin, F.: An iterated local search heuristic for the logistics network design problem with single assignment, Int J prod econ 113, No. 2, 626-640 (2008)
[17]Cordón, O.; Damas, S.: Image registration with iterated local search, J heuristics 12, No. 1 – 2, 73-94 (2006) · Zbl 1122.90066 · doi:10.1007/s10732-006-4983-4
[18]Dorigo, M.; Stützle, T.: Ant colony optimization, (2004)
[19]Eiben, A. E.; Smith, J. E.: Introduction to evolutionary computing, (2003)
[20]El-Abd, M.; Kamel, M.: A taxonomy of cooperative search algorithms, Hybrid metaheuristics. Lecture notes in computer science 3636, 32-41 (2005)
[21]Eshelman, L. J.: The CHC adaptive search algorithm: how to have safe search when engaging in non-traditional genetic recombination, Foundations of genetic algorithms, vol. 1 1, 265-283 (1991)
[22]Fernandes, C.; Rosa, A.: A study on non-random mating and varying population size in genetic algorithms using a royal road function, , 60-66 (2001)
[23]Fogel, D. B.: Evolutionary computation: toward a new philosophy of machine intelligence, (1995)
[24]Forrest, S.; Mitchell, M.: Relative building block fitness and the building block hypothesis, Foundations of genetic algorithms, vol. 2 2, 109-126 (1993)
[25]Gang, P.; Iimura, I.; Nakayama, S.: Application of genetic recombination to genetic local search in TSP, Int J inf technol 13, No. 1, 57-66 (2007)
[26]García-Martínez, C.; Lozano, M.; Herrera, F.; Molina, D.; Sánchez, A. M.: Global and local real-coded genetic algorithms based on parent-centric crossover operators, Eur J oper res 185, 1088-1113 (2008) · Zbl 1146.90532 · doi:10.1016/j.ejor.2006.06.043
[27]García-Martínez, C.; Lozano, M.: Local search based on genetic algorithms, Advances in metaheuristics for hard optimization, 199-221 (2008) · Zbl 1211.90304
[28]Glover F, Kochenberger G, editors. Handbook of metaheuristics. Massachusetts: Kluwer Academic Publishers, 2003.
[29]Goldberg, D. E.: Genetic algorithms in search, optimization, and machine learning, (1989) · Zbl 0721.68056
[30]Goldberg, D. E.; Korb, B.; Deb, K.: Messy genetic algorithms: motivation, analysis, and first results, Complex syst 3, 493-530 (1989) · Zbl 0727.68097
[31]Goldberg, D. E.; Deb, K.; Horn, J.: Massively multimodality, deception, and genetic algorithms, Proceedings of the international conference on parallel problem solving from nature, 37-46 (1992)
[32]Goldberg, D. E.; Wang, L.: Adaptive niching via coevolutionary sharing, Genetic algorithms in engineering and computer science, 21-38 (1997)
[33]Grosan, C.; Abraham, A.: Hybrid evolutionary algorithms: methodologies, architectures, and reviews, Hybrid evolutionary algorithms, 1-17 (2007)
[34]Hansen, P.; Mladenović, N.: Variable neighborhood search, Handbook of metaheuristics, 145-184 (2003) · Zbl 1102.90371 · doi:10.1007/0-306-48056-5_6
[35]Hansen, N.; Müller, S. D.; Koumoutsakos, P.: Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES), Evol comput 11, No. 1, 1-18 (2003)
[36]Hansen, N.; Ostermeier, A.: Completely derandomized self-adaptation in evolution strategies, Evol comput 9, No. 2, 159-195 (2001)
[37]Hansen N. Compilation of results on the CEC benchmark function set. Technical Report, Institute of Computational Science, ETH Zurich, Switzerland; 2005. Available at nbsp;http://www.ntu.edu.sg/home/epnsugan/indexfiles/CEC-05/compareresults.pdfnbsp;.
[38]Hansen, N.; Kern, S.: Evaluating the CMA evolution strategy on multimodal test functions, Proceedings of the international conference on parallel problem solving from nature. Lecture notes in computer science 3242, 282-291 (2004)
[39]Hart WE. Adaptive Global Optimization with Local Search. Ph.D. thesis, University of California, San Diego, California; 1994.
[40]Hart WE, Krasnogor N, Smith JE, editors. Recent advances in memetic algorithms. Studies in fuzzyness and soft computing, vol. 166. Berlin, Heidelberg, New York: Springer; 2004.
[41]Hart, W. E.; Krasnogor, N.; Smith, J. E.: Editorial introduction special issue on memetic algorithms, Evol comput 12, No. 3, v-vi (2004)
[42]Heitktter J. SAC-94 Suite of 0/1-multiple-knapsack problem instances, 2001. Available at nbsp;http://elib.zib.de/pub/Packages/mp-testdata/ip/sac94-suitenbsp;.
[43]Herrera, F.; Lozano, M.: Gradual distributed real-coded genetic algorithms, IEEE trans evol comput 4, No. 1, 43-63 (2000)
[44]Ho, S. L.; Yang, S.; Ni, G.; Wong, H. C.: A particle swarm optimization method with enhanced global search ability for design optimizations of electromagnetic devices, IEEE trans magn 42, No. 4, 1107-1110 (2006)
[45]Hoos, H. H.; Stützle, T.: Stochastic local search: foundations and applications, (2004)
[46]García S, Molina D, Lozano M, Herrera F. A study on the use of nonparametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization. J Heuristics 2009; in press.
[47]Hu, J.; Goodman, E.; Seo, K.; Fan, Z.; Rosenberg, R.: The hierarchical fair competition (HFC) framework for sustainable evolutionary algorithms, Evol comput 13, No. 2, 241-277 (2005)
[48]Jones, T.: Crossover, macromutation, and population-based search, Proceedings of the sixth international conference on genetic algorithms, 73-80 (1995)
[49]Kazarlis, S. A.; Papadakis, S. E.; Theocharis, J. B.; Petridis, V.: Microgenetic algorithms as generalized Hill-climbing operators for GA optimization, IEEE trans evol comput 5, No. 3, 204-217 (2001)
[50]Katayama, K.; Narihisa, H.: Iterated local search approach using genetic transformation to the travelling salesman problem, Proceedings of the genetic and evolutionary computation conference, 321-328 (1999)
[51]Katayama, K.; Narihisa, H.: A new iterated local search algorithm using genetic crossover for the travelling salesman problem, , 302-306 (1999)
[52]Kemenade, C. H. M.: Cluster evolution strategies, enhancing the sampling density function using representatives, , 637-642 (1996)
[53]Kennedy, J.; Eberhart, R. C.: Swarm intelligence, (2001)
[54]Koumousis, V. K.; Katsaras, C. P.: A saw-tooth genetic algorithm combining the effects of variable population size and reinitialization to enhance performance, IEEE trans evol comput 10, No. 1, 19-28 (2006)
[55]Koza, J. R.: Genetic programing, (1992)
[56]Krasnogor, N.; Smith, J. E.: A memetic algorithm with self-adapting local search: TSP as a case study, , 987-994 (2000)
[57]Krasnogor, N.; Smith, J. E.: A tutorial for competent memetic algorithms: model, taxonomy, and design issue, IEEE trans evol comput 9, No. 5, 474-488 (2005)
[58]Krishnakumar, K.: Micro-genetic algorithms for stationary and nonstationary function optimization, , 289-296 (1989)
[59]Langdon, W. B.; Poli, R.: Evolving problems to learn about particle swarm optimizers and other search algorithms, IEEE trans evol comput 11, No. 5, 561-578 (2007)
[60]Lima, C. F.; Pelikan, M.; Sastry, K.; Butz, M.; Goldberg, D. E.; Lobo, F. G.: Substructural neighborhoods for local search in the Bayesian optimization algorithm, Proceedings of the international conference on parallel problem solving from nature. Lecture notes in computer science 4193, 232-241 (2006)
[61]Lozano, M.; Herrera, F.; Krasnogor, N.; Molina, D.: Real-coded memetic algorithms with crossover Hill-climbing, Evol comput 12, No. 3, 273-302 (2004)
[62]Lozano, M.; Herrera, F.; Cano, J. R.: Replacement strategies to maintain useful diversity in steady-state genetic algorithms, Inf sci 178, 4421-4433 (2008)
[63]Lourenço, H. R.; Martin, O. C.; Stützle, T.: Iterated local search, Handbook of metaheuristics, 321-353 (2003)
[64]Meloni, C.; Naso, D.; Turchiano, B.: Multi-objective evolutionary algorithms for a class of sequencing problems in manufacturing environments, , 8-13 (2003)
[65]Merz P. Memetic algorithms for combinatorial optimization problems: fitness landscapes and effective search strategies. Dissertation, University of Siegen, Germany; 2000.
[66]Milano, M.; Roli, A.: MAGMA: a multiagent architecture for metaheuristics, IEEE trans syst man cybern B 33, No. 2, 925-941 (2004)
[67]Molina D, Lozano M, García-Martínez C, Herrera F. Memetic algorithms for continuous optimization based on local search chains. Evol Comput 2009; in press.
[68]Moscato, P.; Cotta, C.: A gentle introduction to memetic algorithms, Handbook of metaheuristics, 105-144 (2003) · Zbl 1107.90459 · doi:10.1007/0-306-48056-5_5
[69]Mühlenbein, H.; Schomisch, M.; Born, J.: The parallel genetic algorithm as function optimizer, Proceedings of the international conference on genetic algorithms, 271-278 (1991)
[70]Mühlenbein, H.; Schlierkamp-Voosen, D.: Predictive models for the breeder genetic algorithm I. Continuous parameter optimization, Evol comput 1, 25-49 (1993)
[71]Mutoh, A.; Tanahashi, F.; Kato, S.; Itoh, H.: Efficient real-coded genetic algorithms with flexible-step crossover, IEEJ electron inf syst 126, No. 5, 654-660 (2006)
[72]Nagata, Y.; Kobayashi, S.: Edge assembly crossover: a high-power genetic algorithm for the traveling salesman problem, Proceedings of the international conference on genetic algorithms, 450-457 (1997)
[73]Noman, N.; Iba, H.: Accelerating differential evolution using an adaptive local search, IEEE trans evol comput 12, No. 1, 107-125 (2008)
[74]Ong, Y. S.; Krasnogor, N.; Ishibuchi, H.: Guest editorial: special issue on memetic algorithms, IEEE trans systems man cybern part B: cybern 37, No. 1, 2-5 (2007)
[75]O’reilly, U. M.; Oppacher, F.: Hybridized crossover-based search techniques for program discovery, , 573-578 (1995)
[76]Papadakis, S. E.; Theocharis, J. B.: A GA-based fuzzy modeling approach for generating TSK models, Fuzzy sets syst 131, No. 2, 121-152 (2002) · Zbl 1010.93500 · doi:10.1016/S0165-0114(01)00227-5
[77]Parthasarathy, P. V.; Goldberg, D. E.; Burns, S. A.: Tackling multimodal problems in hybrid genetic algorithms, Proceedings of the genetic and evolutionary computation conference, 775 (2001)
[78]Pelikan, M.; Goldberg, D. E.; Cantú-Paz, E.: Linkage problem, distribution estimation, and Bayesian networks, Evol comput 8, No. 3, 1063-6560 (2000)
[79]Pelikan, M.; Hartmann, A.; Lin, T. K.: Parameter-less hierarchical Bayesian optimization algorithm, Parameter setting in evolutionary algorithms, SCI, vol. 54 54, 225-239 (2007)
[80]Petrowski, A.: A clearing procedure as a niching method for genetic algorithms, , 798-803 (1996)
[81]Potts, J. C.; Giddens, T. D.; Yadav, S. B.: The development and evaluation of an improved genetic algorithm based on migration and artificial selection, IEEE trans syst man cybern 24, 73-86 (1994)
[82]Preux, Ph.; Talbi, E. -G.: Towards hybrid evolutionary algorithms, Int. trans oper res 6, No. 6, 557-570 (1999)
[83]Raidl, G. R.: A unified view on hybrid metaheuristics, Hybrid metaheuristics. Lecture notes in computer science 4030, 1-126 (2006)
[84]Randall, M.: Search space reduction as a tool for achieving intensification and diversification in ant colony optimisation, Advances in applied artificial intelligence. Lecture notes in computer science 4031, 254-261 (2006)
[85]Rodriguez-Martin, I.; Salazar-Gonzalez, J. J.: An iterated local search heuristic for a capacitated hub location problem, Hybrid metaheuristics. Lecture notes in computer science 4030, 70-81 (2006)
[86]Sastry, K.; Goldberg, D. E.: Designing competent mutation operators via probabilistic model building of neighborhoods, Proceedings of the genetic and evolutionary computation conference. Lecture notes in computer science 3103, 114-125 (2004)
[87]Schlierkamp-Voosen, D.; Mühlenbein, H.: Strategy adaptation by competing subpopulations, Proceedings of the international conference on parallel problem solving from nature. Lecture notes in computer science 866, 199-208 (1994)
[88]Seront, G.; Bersini, H.: A new GA-local search hybrid for continuous optimization based on multi level single linkage clustering, Proceedings of the genetic and evolutionary computation conference, 90-95 (2000)
[89]Sheskin, D. J.: Handbook of parametric and nonparametric statistical procedures, (2003)
[90]Sinha A, Goldberg DE. A Survey of hybrid genetic and evolutionary algorithms. ILLIGAL Technical Report 2003004; 2004.
[91]Soak, S. -M.; Lee, S. -W.; Mahalik, N. P.; Ahn, B. -H.: A new memetic algorithm using particle swarm optimization and genetic algorithm, Knowledge-based intelligent information and engineering systems. Lecture notes in computer science 4251, 122-129 (2006)
[92]Stützle, T.: Iterated local search for the quadratic assignment problem, Eur J oper res 174, 1519-1539 (2006) · Zbl 1103.90066 · doi:10.1016/j.ejor.2005.01.066
[93]Talbi, E. -G.: A taxonomy of hybrid metaheuristics, J heuristics 8, No. 5, 541-565 (2002)
[94]Talbi, E. -G.; Bachelet, T.: COSEARCH: a parallel cooperative metaheuristic, J math model algorithms 5, 5-22 (2006) · Zbl 1099.68742 · doi:10.1007/s10852-005-9029-7
[95]Tang, L. X.; Luo, J. X.: A new ILS algorithm for parallel machine scheduling problems, J intell manuf 17, No. 5, 609-619 (2006)
[96]Tang, J.; Lim, M. H.; Ong, Y. S.: Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems, Soft comput 11, No. 9, 873-888 (2007)
[97]Thierens, D.: Adaptive mutation rate control schemes in genetic algorithms, , 980-985 (2002)
[98]Thierens, D.: Population-based iterated local search: restricting neighborhood search by crossover, Proceedings of the genetic and evolutionary computation conference. Lecture notes in computer science 3103, 234-245 (2004)
[99]Tounsi, M.; Ouis, S.: An iterative local-search framework for solving constraint satisfaction problem, Appl soft comput 8, No. 4, 1530-1535 (2008)
[100]Tsutsui, S.; Ghosh, A.; Corne, D.; Fujimoto, Y.: A real coded genetic algorithm with an explorer and an exploiter population, , 238-245 (1997)
[101]Wei, L.; Zhao, M.: A niche hybrid genetic algorithm for global optimization of continuous multimodal functions, Appl math comput 160, No. 3, 649-661 (2005) · Zbl 1062.65065 · doi:10.1016/j.amc.2003.11.023
[102]Weicai, Z.; Jing, L.; Mingzhi, X.; Licheng, J.: A multiagent genetic algorithm for global numerical optimization, IEEE trans systems man cybern part B 34, No. 2, 1128-1141 (2004)
[103]Whitley, D.; Rana, S.; Dzubera, J.; Mathias, E.: Evaluating evolutionary algorithms, Artif intell 85, 245-276 (1996)
[104]Zar, J. H.: Biostatistical analysis, (1999)
[105]Zhang, Q.; Sun, J.; Tsang, E. P. K.: Evolutionary algorithm with the guided mutation for the maximum clique problem, IEEE trans evol comput 9, No. 2, 192-200 (2005)
[106]Zhang, Q.; Sun, J.: Iterated local search with guided mutation, , 924-929 (2006)