Abstract
Genetic algorithms (GAs) have proved to be a versatile and effective approach for solving combinatorial optimization problems. Nevertheless, there are many situations in which the simple GA does not perform particularly well, and various methods of hybridization have been proposed. These often involve incorporating other methods such as simulated annealing or local optimization as an ‘add-on’ extra to the basic GA strategy of selection and reproduction.
Here, we explore an alternative perspective which views genetic algorithms as a generalization of neighbourhood search methods. It is not the intention to present a fully worked-out statement as to what sort of neighbourhood search a GA is. Rather, it is to investigate some of the parallels, and to suggest some areas for further research which may enhance our understanding of both neighbourhood search and genetic algorithms.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
E.Falkenauer and A.Delchambre (1992) A genetic algorithm for bin packing and line balancing. In Proceedings of the IEEE International Conference on Robotics and Automation.
C.R.Reeves (1993) Hybrid genetic algorithms for bin-packing and related problems. (submitted to Annals of OR).
C.R.Reeves (1993) A genetic algorithm for flowshop sequencing. To appear in Computers & Ops.Res.
J.L.BlantonJr. and R.L.Wainwright (1993) Multiple vehicle routing with time and capacity constraints using genetic algorithms. In [37].
P.Jog, J.Y.Suh and D. VanGucht (1991) The effects of population size, heuristic crossover and local improvement on a genetic algorithm for the travelling salesman problem. In [38].
D.Whitley, T.Starkweather and D.Shaner (1991) The traveling salesman and sequence scheduling: quality solutions using genetic edge recombination. In [39].
A.Homaifar, S.Guan and G.E.Liepins (1993) A new approach on the travelling salesman problem by genetic algorithms. In [37].
J.H.Holland (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press,Ann Arbor.
D.E.Goldberg (1989) Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, Mass.
C.R.Reeves (Ed.) (1993) Modern Heuristic Techniques for Combinatorial Problems. Blackwell Scientific Publications, Oxford.
C.R.Reeves (1994) Genetic algorithms and combinatorial optimization. In Proceedings of the UNICOM Seminar on Adaptive Computing and Information Processing, Brunei University, UK.
H.Mühlenbein (1991) Evolution in time and space—the parallel genetic algorithm. In [40].
N.L.J.Ulder, E.H.L.Aarts, H.-J.Bandelt, P.J.M.Laarhoven and E.Pesch (1991) Genetic local search algorithms for the travelling salesman problem. In H.-P.Schwefel and R.MÄnner (1991) (Eds.) Parallel Problem-Solving from Nature. Springer-Verlag, Berlin.
P.Prinetto, M.Rebaudengo and M. SonzaReorda (1993) Hybrid genetic algorithms for the travelling salesman problem. In [41].
N.J.Radcliffe (1991) Forma analysis and random espectful recombination. In [42].
N.J.Radcliffe (1991) Equivalence class analysis of genetic algorithms. Complex Systems, 5, 183–205.
D.Orvosh and L.Davis (1993) Shall we repair? Genetic algorithms, combinatorial optimization and feasibility constraints. In [37].
F.Glover and M.Laguna (1993). Tabu Search. In [10].
R.J.M.Vaessens, E.H.LAarts and J.K.Lenstra (1992) A local search template. In [43].
V.J.Rayward-Smith (1994) A unified approach to tabu search, simulated annealing and genetic algorithms. In Proceedings of the UNICOM Seminar on Adaptive Computing and Information Processing, Brunei University, UK.
J.Antonisse (1989) A new interpretation of schema notation that overturns the binary encoding constraint. In [38], 86–91.
N.J.Radcliffe (1992) Non-linear genetic representations. In [43].
P.Kanerva (1988) Sparse Distributed Memory. MIT Press, Cambridge, Mass.
M.D.Vose (1993) Modeling simple genetic algorithms. In [44].
L.D.Whitley (1993) An executable model of a simple genetic algorithm. In [44].
L.B.Booker (1987) Improving search in genetic algorithms. In [46].
A.Fairley (1991) Comparison of methods of choosing the crossover point in the genetic crossover operation. Dept. of Computer Science, University of Liverpool.
G.Syswerda (1991) A study of reproduction in generational and steady-state genetic algorithms. In [40].
C.L.Bridges and D.E.Goldberg (1987) An analysis of reproduction and crossover in a binary-coded genetic algorithm. In [45].
S.J.Louis and G.J.E.Rawlins (1993) Syntactic analysis of convergence in genetic algorithms. In [44].
L.J.Eshelman (1991) The CHC adaptive search algorithm: how to have safe search when engaging in non-traditional genetic recombination. In [40].
G.Syswerda (1993) Simulated crossover in genetic algorithms. In[44].
L.J.Eshelman and J.D.Schaffer (1993) Crossover's niche. In [37].
C.Höhn and C.R.Reeves (1994) Heuristic genetic search methods for graph partitioning. To be presented at the International Conference on Systems Engineering, Coventry University, September 1994.
N.J.Radcliffe and F.A.W.George (1993) A study in set recombination. In [37].
C.R.Reeves (1993) Diversity and diversification in genetic algorithms: some connections with tabu search. In [41].
S.Forrest (Ed.) (1993) Proceedings of 5 th International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA.
J.D.Schaffer (Ed.) (1989) Proceedings of 3 rd International Conference on Genetic Algorithms. Morgan Kaufmann, Los Altos, CA.
L.Davis (Ed.) (1991) Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York.
G.J.E.Rawlins (Ed.) (1991) Foundations of Genetic Algorithms. Morgan Kaufmann, San Mateo, CA.
R.F.Albrecht, C.R.Reeves and N.C.Steele (Eds.) (1993) Proceedings of the International Conference on Artificial Neural Networks and Genetic Algorithms, Springer-Verlag, Vienna.
R.K.Belew and L.B.Booker (Eds.) (1991) Proceedings of 4 th International Conference on Genetic Algorithms. Morgan Kaufmann, San Mateo, CA.
R.MÄnner and B.Manderick (Eds.) (1992) Parallel Problem-Solving from Nature, 2. Elsevier Science Publishers, Amsterdam.
L.D.Whitley (Ed.) (1993) Foundations of Genetic Algorithms 2, Morgan Kaufmann, San Mateo, CA.
J.J.Grefenstette(Ed.) (1987) Proceedings of the 2nd International Conference on Genetic Algorithms. Lawrence Erlbaum Associates, Hillsdale, NJ.
L.Davis (Ed.) (1987) Genetic Algorithms and Simulated Annealing. Morgan Kauffmann, Los Altos, CA.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Reeves, C.R. (1994). Genetic algorithms and neighbourhood search. In: Fogarty, T.C. (eds) Evolutionary Computing. AISB EC 1994. Lecture Notes in Computer Science, vol 865. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58483-8_10
Download citation
DOI: https://doi.org/10.1007/3-540-58483-8_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58483-4
Online ISBN: 978-3-540-48999-3
eBook Packages: Springer Book Archive