Abstract
Genetic Algorithms have been seen as search procedures that can quickly locate high performance regions of vast and complex search spaces, but they are not well suited for fine-tuning solutions, which are very close to optimal ones. However, genetic algorithms may be specifically designed to provide an effective local search as well. In fact, several genetic algorithm models have recently been presented with this aim. In this chapter, we call these algorithms Local Genetic Algorithms.
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
Beasley JE (1998) Heuristic algorithms for the unconstrained binary quadratic programming problem. Tech. Rep., Management School, Imperial College, London, UK.
Beasley JE (1990) The Journal of the Operational Research Society 41(11):1069–1072. (http://people.brunel.ac.uk/ mastjjb/jeb/info.html)
Blum C, Roli A (2003) ACM Computing Surveys 35(3):268–308
Boese KD, Muddu S (1994) Operations Research Letters 16:101–113
De Jong K, Potter MA, Spears WM (1997) Using problem generators to explore the effects of epistasis. In: Bäck T (ed) Proc. of the Seventh International Conference on Genetic Algorithms. Morgan Kaufmann
Dietzfelbinger M, Naudts B, Van Hoyweghen C, Wegener I (2003) IEEE Transactions on Evolutionary Computation 7(5):417–423
Elliott L, Ingham DB, Kyne AG, Mera NS, Pourkashanian M, Wilson CW (2004) An informed operator based genetic algorithm for tuning the reaction rate parameters of chemical kinetics mechanisms. In: Deb K, Poli R, Banzhaf W, Beyer H-G, Burke EK, Darwen PJ, Dasgupta D, Floreano D, Foster JA, Harman M, Holland O, Lanzi PL, Spector L, Tettamanzi A, Thierens D, Tyrrell AM (eds) Proc. of the Genetic and Evolutionary Computation Conference, LNCS 3103. Springer, Berlin Heidelberg
Feo T, Resende M (1995) Journal of Global Optimization 6:109–133.
Fernandes C, Rosa A (2001) 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, IEEE Press, Piscataway, New Jersey
Festa P, Pardalos PM, Resende MGC, Ribeiro CC (2002) Optimization Methods and Software 17(6):1033–1058
Fischer I, Gruber G, Rendl F, Sotirov R (2006) Mathematical Programming 105(2–3): 451–469
García-Martínez C, Lozano M, Molina D (2006) A Local Genetic Algorithm for Binary-coded Problems. In: Runarsson TP, Beyer H-G, Burke E, Merelo-Guervós JJ, Whitley LD, Yao X (eds) 9th International Conference on Parallel Problem Solving from Nature, LNCS 4193. Springer, Berlin Heidelberg
García-Martínez C, Lozano M, Herrera F, Molina D, Sánchez AM (2007) Global and local real-coded genetic algorithms based on parent-centric crossover operators. European Journal of Operational Research. In Press, Corrected Proof, Available online 18 October 2006
Gendreau M, Potvin J-Y (2005) Annals of Operations Research 140(1):189–213
Glover F, Laguna M (1999) Operational Research Society Journal 50(1):106–107
Goldberg DE, Korb B, Deb K (1989) Complex Systems 3:493–530
Goldberg DE (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.
Gulati VP, Gupta SK, Mittal AK (1984) European Journal of Operational Research 15:121–125
Harik G (1995) Finding multimodal solutions using restricted tournament selection. In: Eshelman LJ (ed) Proc. of the 6th International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, California
Helmberg C, Rendl F (2000) Siam Journal of Optimization 10(3):673–696
Herrera F, Lozano M, Verdegay JL (1998) Artificial Intelligence Revue 12(4):265–319
Herrera F, Lozano M (2000) IEEE Trans. on Evolutionary Computation 4(1):43–63
Herrera F, Lozano M, Sánchez AM (2003) International Journal of Intelligent Systems 18(3):309–338
Holland JH (1992) Adaptation in Natural and Artificial Systems. The MIT Press Cambridge, MA, USA
Karp RM (1972) Reducibility among combinatorial problems. In: Miller R, Thatcher J (eds), Complexity of Computer Computations. Plenum Press, New York
Katayama K, Tani M, Narihisa H (2000) Solving large binary quadratic programming problems by effective genetic local search algorithm. In: Whitley D, Goldberg D, Cantu-Paz E, Spector L, Parmee I, Beyer H-G (eds) Proc. of the 2000 Genetic and Evolutionary Computation Conference. Morgan Kaufmann
Katayama K, Narihisa H (2001) Trans. IEICE (A) J84-A(3):430–435
Kauffman SA (1989) Lectures in the Sciences of Complexity 1:527–618
Kazarlis SA, Papadakis SE, Theocharis JB, Petridis V (2001) IEEE Transactions on Evolutionary Computation 5(3):204–217
Lourenço HR, Martin O, Stützle T (2002) Iterated local search. In: Glover F, Kochenberger G (eds) Handbook of Metaheuristics. Kluwer Academic, Boston, MA, USA
Lozano M, Herrera F, Krasnogor N, Molina D (2004) Evolutionary Computation Journal 12(3):273–302
Meloni C, Naso D, Turchiano B (2003) Multi-objective evolutionary algorithms for a class of sequencing problems in manufacturing environments. Proc. of the IEEE International Conference on Systems, Man and Cybernetics 1
Merz P (2002) Nk-fitness landscapes and memetic algorithms with greedy operators and k-opt local search. In: Krasnogor N (ed) Proc. of the Third International Workshop on Memetic Algorithms (WOMA III)
Merz P, Katayama K (2004) Bio Systems 79(1–3):99–118
Mladenovic N, Hansen P (1997) Computers in Operations Research 24:1097–1100
Moscato P (1999) Memetic algorithms: a short introduction. In: Corne D, Dorigo M, Glover F (eds), New Ideas in Optimization. McGraw-Hill, London
Nasimul N, Hitoshi I (2005) Enhancing differential evolution performance with local search for high dimensional function optimization. In: Beyer HG, O’Reilly UM, Arnold DV, Banzhaf W, Blum C, Bonabeau EW, Cantu-Paz E, Dasgupta D, Deb K, Foster JA, De Jong ED, Lipson H, Llora X, Mancoridis S, Pelikan M, Raidl GR, Soule T, Tyrrell AM, Watson J-P, Zitzler E (eds) Proc. of the Genetic and Evolutionary Computation Conference. ACM Press, New York
Papadakis SE, Theocharis JB (2002) Fuzzy Sets and Systems 131(2):121–152
Potter MA. http://www.cs.uwyo.edu/∼wspears/nk.c
Potts JC, Giddens TD, Yadav SB (1994) IEEE Transactions on Systems, Man, and Cybernetics 24:73–86
Resende MGC, Ribeiro CC (2003) International Series in Operations Research and Management Science 57:219–250
Smith K, Hoos HH, Stützle T (2003) Iterated robust tabu search for MAX-SAT. In: Carbonell JG, Siekmann J (eds) Proc. of the 16th conference on the Canadian Society for Computational Studies of Intelligence, LNCS 2671. Springer, Berlin Heidelberg
Spears WM. http://www.cs.uwyo.edu/∼wspears/epist.html
Sywerda G (1989) Uniform crossover in genetic algorithms. In: Schaffer JD (ed) Proc. of the Third International Conference on Genetic Algorithms, Morgan Kaufmann, San Francisco, CA, USA
Tanese R (1987) Parallel genetic algorithms for a hypercube. In: Grefenstette JJ (ed) Proc. of the Second International Conference on Genetic Algorithms Applications. Hillsdale, NJ, Lawrence Erlbraum
Thierens D (2004) Population-based iterated local search: restricting neighborhood search by crossover. In: Deb K, Poli R, Banzhaf W, Beyer H-G, Burke EK, Darwen PJ, Dasgupta D, Floreano D, Foster JA, Harman M, Holland O, Lanzi PL, Spector L, Tettamanzi A, Thierens D, Tyrrell AM (eds) Proc. of the Genetic and Evolutionary Computation Conference, LNCS 3103. Springer, Berlin Heidelberg
Tsutsui S, Ghosh A, Corne D, Fujimoto Y (1997) A real coded genetic algorithm with an explorer and an exploiter population. In: Bäck T (ed) Proc. of the Seventh International Conference on Genetic Algorithms. Morgan Kaufmann Publishers, San Francisco
Weicai Z, Jing L, Mingzhi X, Licheng J (2004) IEEE Transactions on Systems, Man, and Cybernetics - Part B: Cybernetics 34(2):1128–1141
Whitley D (1989) The GENITOR algorithm and selection pressure: why rank-based allocation of reproductive trials is best. In: Schaffer JD (ed) Proc. of the Third International Conference on Genetic Algorithms, Morgan Kaufmann, San Francisco, CA, USA
Ye Y. http://www.stanford.edu/ yyye/yyye/Gset/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
García-Martínez, C., Lozano, M. (2007). Local Search Based on Genetic Algorithms. In: Siarry, P., Michalewicz, Z. (eds) Advances in Metaheuristics for Hard Optimization. Natural Computing Series. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-72960-0_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-72960-0_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-72959-4
Online ISBN: 978-3-540-72960-0
eBook Packages: Computer ScienceComputer Science (R0)