Abstract
Parallel memetic algorithms (PMAs) are a class of modern parallel meta-heuristics that combine evolutionary algorithms, local search, parallel and distributed computing technologies for global optimization. Recent studies on PMAs for large-scale complex combinatorial optimization problems have shown that they converge to high quality solutions significantly faster than canonical GAs and MAs. However, the use of local learning for every individual throughout the PMA search can be a very computationally intensive and inefficient process. This paper presents a study on two diversity-adaptive strategies, i.e., (1) diversity-based static adaptive strategy (PMA-SLS) and (2) diversity-based dynamic adaptive strategy (PMA-DLS) for controlling the local search frequency in the PMA search. Empirical study on a class of NP-hard combinatorial optimization problem, particularly large-scale quadratic assignment problems (QAPs) shows that the diversity-adaptive PMA converges to competitive solutions at significantly lower computational cost when compared to the canonical MA and PMA. Furthermore, it is found that the diversity-based dynamic adaptation strategy displays better robustness in terms of solution quality across the class of QAP problems considered. Static adaptation strategy on the other hand requires extra effort in selecting suitable parameters to suit the problems in hand.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bambha NK, Bhattacharyya SS, Teich J, Zitzler E. (2004). Systematic integration of parameterized local search into evolutionary algorithms. IEEE Trans Evoluti Comput. 8(2):137–155
Bradwell R, Brown K (1999) Parallel asynchronous memetic algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference, Evolutionary Computation and Parallel Processing Workshop, Orlando, Florida
Burkard RE, Karisch SE, Rendl F (1997) QAPLIB—A quadratic assignment problem library. J Global Optimi, 10:391–403. Available from <http://www.opt.math.tu-graz.ac.at/qaplib/>
Cotta C, Mendes A, Garcia V, Franca P, Moscato P (2003) Applying memetic algorithms to the analysis of microarray data. In: Application of evolutionary computing. Raidl G. et al (eds) Lecture notes in computer science, vol 2611 pp. 22–32. Springer, Berlin Heidelberg New York
Dawkins R. (1976). The selfish gene. Oxford University Press, New York
Digalakis JG, Margaritis KG. (2004). Performance comparison of memetic algorithms. J Appl Math Comput. 158(25):237–252
Eiben AE, Hinterding R, Michalewicz Z. (1999). Parameter control in evolutionary algorithm. IEEE Trans Evolut Comput. 3(2):124–141
Goldberg DE. (1989). Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading MA
Goldberg D, Voessner S (1999) Optimizing global-local search hybrids. In: Banzhaf W et al. (eds) Proceedings of the genetic and evolutionary computation conference. Morgan Kaufmann, pp. 220–228
Hart WE. (1994). Adaptive global optimization with local search. PhD. Thesis, University of California, San Diego
Holland JH. (1975). Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor
Ishibuchi H, Yoshida T, Murata T. (2003). Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Trans Evolut Comput. 7(2):204–223
Knowles J, Corne D. (2004). Memetic algorithms for multiobjective optimization: issues, methods and prospects. In: Krasnogor N. et al. (eds). Recent advances in memetic algorithms. Springer, Berlin Heidelberg New York, pp. 313–352
Koopmans TC, Beckmann MJ. (1957). Assignment problems and the location of economic activities. Econometrica 25:53–76
Krasnogor N (2002) Studies on the theory and design space of memetic algorithms. PhD. Thesis, University of the West of England, Bristol
Ku KWC, Mak MW, Siu WC. (2000). A study of the Lamarckian evolution of recurrent neural networks. IEEE Trans Evolut Comput. 4(1):31–42
Land MWS (1998) Evolutionary algorithms with local search for combinatorial optimization. PhD. Thesis, University of California, San Diego
Li Y, Pardalos PM, Resende MGC (1994) A greedy randomized adaptive search procedure for the quadratic assignment problem. In: Pardalos P et al. (eds) Quadratic assignment and related problems. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 16, pp 173–187 AMS, Providence, RI
Lim MH, Yuan Y, Omatu S. (2000). Efficient genetic algorithms using simple genes exchange local search policy for the quadratic assignment problem. Comput Optim Appl. 15:249–268
Lim MH, Yuan Y, Omatu S. (2002). Extensive testing of a hybrid genetic algorithm for quadratic assignment problem. Comput Optim Appl. 23:47–64
Mascato P (1989) On evolution, search, optimization, genetic algorithms and martial arts: toward memetic algorithms. Tech. Rep. Caltech Concurrent Computation Program, Report. 826, California Institute of Technology, Pasadena, CA, USA
Merz P, Freisleben B. (1999). Fitness landscapes and memetic algorithm design. In: Corne D. et al. (eds). New ideas in optimization. McGraw-Hill, London, pp. 245–260
Merz P, Freisleben B (1999) A comparison of memetic algorithms, tabu search, and ant colonies for the quadratic assignment problem. In: Proceedings of the 1999 international congress of evolutionary computation, pp 2063–2070 IEEE Press
Merz P, Freisleben B. (2000). Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans Evolut Comput. 4(4):337–352
Ong YS, Keane AJ. (2004). Meta-lamarckian in memetic algorithm. IEEE Trans on Evolut Comput. 8(2):99–110
Ong YS, Lim MH, Zhu N, Wong KW. (2006). Classification of adaptive memetic algorithms: a comparative study. IEEE Trans Syst, Man Cybernet. 36(1):141–152
Rosca J (1995) Entropy-driven adaptive representation. In: Rosca J. (Ed) Proceedings of the workshop on genetic programming: from theory to real-world applications, Tahoe City, CA, USA, pp 23–32
Skorin-Kapov J. (1990). Tabu search applied to the quadratic assignment problem. ORSA J Comput. 2(1):33–45
Solimanpur M, Vrat P, Shankar R. (2004). Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing. Eur J Oper Res. 157(3):592–606
Suzuki J. (1995). A Markov chain analysis on simple genetic algorithms. IEEE Trans Syst Man Cybernet. 25(4):655–659
Taillard ED. (1991). Robust tabu search for the quadratic assignment problem. Parallel Comput. 17:443–455
Taillard ED. (1995). Comparison of iterative searches for the quadratic assignment problem. Locat Sci. 3:87–105
Tan KC, Lee TH, Khor EF. (2001). Evolutionary algorithms with dynamic population size and local exploration for multiobjective optimization. IEEE Trans Evolut Comput. 5(6):565–588
Tang J, Lim MH, Ong YS (2003) A parallel hybrid GA for combinatorial optimization using grid technology. In: Proceedings of IEEE congress on evolutionary computation, Canberra, Australia, vol. 3, pp 1895–1902 IEEE
Tang J, Lim MH, Ong YS, Er MJ (2004) Study of migration topology in island model parallel hybrid-GA for large scale quadratic assignment problems. In: The Eighth International Conference on Control, Automation, Robotics and Vision (ICARCV2004), Special Session on Computational Intelligence on the Grid, December 6–9, Kunming, China
Thonemann UW, Bolte A (1994) An improved simulated annealing algorithm for the quadratic assignment problem. Technical Report, School of Business, Department of Production and Operations Research, University of Panderborn, Germany
Wilhelm MR, Ward TL. (1987). Solving quadratic assignment problems by simulated annealing. IIE Trans. 19(1):107–119
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Tang, J., Lim, M.H. & Ong, Y.S. Diversity-adaptive parallel memetic algorithm for solving large scale combinatorial optimization problems. Soft Comput 11, 873–888 (2007). https://doi.org/10.1007/s00500-006-0139-6
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00500-006-0139-6