Selecting survivors in genetic algorithm using tabu search strategies
Tóm tắt
Genetic algorithm (GA) is well-known for its effectiveness in global search and optimization. To balance selection pressure and population diversity is an important issue of designing GA. This paper proposes a novel hybridization of GA and tabu search (TS) to address this issue. The proposed method embeds the key elements of TS—tabu restriction and aspiration criterion—into the survival selection operator of GA. More specifically, the tabu restriction is used to prevent inbreeding for diversity maintenance, and the aspiration criterion is activated to provide moderate selection pressure under the tabu restriction. The interaction of tabu restriction and aspiration criterion enables survivor selection to balance selection pressure and population diversity. The experimental results on numerical and combinatorial optimization problems show that this hybridization can significantly improve GAs in terms of solution quality as well as convergence speed. An empirical analysis further identifies the influences of the TS strategies on the performance of this hybrid GA.
Tài liệu tham khảo
Abdinnour-Helm S (1998) A hybrid heuristic for the uncapacitated hub location problem. Eur J Oper Res 106: 489–499
Ackley DH (1987) A connectionist machine for genetic Hillclimbing. Kluwer, Boston
Aranha C, Iba H (2009) The memetic tree-based genetic algorithm and its application to portfolio optimization. Memetic Comput 1(2): 139–151
Bersini H, Dorigo M, Langerman S, Seront G, Gambardella L (1996) Results of the first international contest on evolutionary optimisation. In: Proceedings of the Third IEEE conference on evolutionary computation, pp 611–615
Chin AJ, Kit HW, Lim A (1999) A new GA approach for the vehicle routing problem. In: Proceedings of the 11th IEEE international conference on tools with artificial intelligence, pp 307–310
De Jong K (1975) An analysis of the behavior of a class of genetic adaptive systems. Ph.D. thesis, University of Michigan
Eiben AE, Smith JE (2003) Introduction to evolutionary computing. Natural Computing. Springer, Heidelberg
Gandomkar M, Vakilian M, Ehsan M (2005) A genetic-based tabu search algorithm for optimal DG allocation in distribution networks. Elect Power Compon Syst 33(12): 1351–1361
Glover F, Kelly JP, Laguna M (1995) Genetic algorithms and tabu search: hybrid for optimization. Computers Ops Res 22(1): 1–134
Glover F, Languna M (1997) Tabu search. Kluwer, Boston
Griewank AO (1981) Generalized descent for global optimization. J Optim Theory Appl 34(1): 11–39
Hageman JA, Wehrens R, van Sprang HA, Buydens LMC (2003) Hybrid genetic algorithm-tabu search approach for optimising multilayer optical coatings. Anal Chim Acta 490: 211–222
Handa K, Kuga S (1995) Pollycell placement for analog lsi chip designs by genetic algorithms and tabu search. In: IEEE int. conf. evol. comput., pp 716–721
Hart WE, Krasnogor N, Smith JE (2004) Recent advances in memetic algorithms. Springer, Heidelberg
Hasan SMK, Sarker R, Essam D, Cornforth D (2009) Memetic algorithms for solving job-shop scheduling problems. Memetic Comput 1(1): 69–83
Holland J (1975) Adaptation in natural and artificial systems. University of Michigan Press, Michigan
Ishibuchi H, Yoshida T, Murata T (2003) Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evol Comput 7(2): 204–223
Jiang T, Cui Q, Shi G, Ma S (2003) Protein folding simulations of the hydrophobic–hydrophilic model by combining tabu search with genetic algorithms. J Chem Phys 119(8): 4592–4596
Liaw CF (2000) A hybrid genetic algorithm for the open shop scheduling problem. Eur J Oper Res 124: 28–42
Nara K (1997) Genetic algorithm for power systems planning. In: Proceedings of the fourth international conference on advances in power system control, operation and management, pp 11–14
Neri F, Tirronen V (2009) Scale factor local search in differential evolution. Memetic Comput 1(2): 153–171
Ong YS, Lim MH, Zhu N, Wong KW (2006) Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst Man Cybern Part B Cybern 36(1): 141–152
Ozdamar L, Birbil SI (1998) Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions. Eur J Oper Res 110: 525–547
Rastrigin LA (1974) Systems of extremal control. Nauka, Moscow
Gerhard Reinelt. TSPLIB http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ (1995)
Schwefel HP (1981) Numerical optimization of computer models. Wiley, New York
Shin DJ, Kim JO, Kim KT, Choo JB, Singh C (2004) Optimal service restoration and reconfiguration of network using genetic-tabu algorithm. Elect Power Syst Res 71: 145–152
Ting CK, Li ST, Lee C (2001) Tga: a new integrated approach to evolutionary algorithms. In: Proc. of the IEEE congress on evolutionary computation, pp 917–924
Ting CK, Li ST, Lee CN (2003) On the harmonious mating strategy through tabu search. Inform Sci 156: 189–214
Vilcot G, Billaut JC (2008) A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem. Eur J Oper Res 190: 398–411
Whitley D (1989) The genitor algorithm and selection pressure: Why rank-based allocation of reproductive trials is best. In: Proc. of the 3rd international conference on genetic algorithms, pp 116–121, San Mateo, CA
Xian B, Li T, Sun G, Cao T (2004) The combination of principal component analysis, genetic algorithm and tabu search in 3d molecular similarity. Mol Struct 674: 87–97
Yu X, Tang K, Chen T, Yao X (2009) Empirical analysis of evolutionary algorithms with immigrants schemes for dynamic optimization. Memetic Comput 1(1): 3–24