SCIENCE & EDUCATION

Article file: SE-BMSTU...o142.pdf (1431.61Kb)

1 Bauman Moscow State Technical University, Moscow, Russia

In recent decades, evolutionary algorithms have proven themselves as the powerful optimization techniques of search engine. Their popularity is due to the fact that they are easy to implement and can be used in all areas, since they are based on the idea of universal evolution. For example, in the problems of a large number of local optima, the traditional optimization methods, usually, fail in finding the global optimum. To solve such problems using a variety of stochastic methods, in particular, the so-called population-based algorithms, which are a kind of evolutionary methods. The main disadvantage of this class of methods is their slow convergence to the exact solution in the neighborhood of the global optimum, as these methods incapable to use the local information about the landscape of the function. This often limits their use in large-scale real-world problems where the computation time is a critical factor.
One of the promising directions in the field of modern evolutionary computation are memetic algorithms, which can be regarded as a combination of population search of the global optimum and local procedures for verifying solutions, which gives a synergistic effect. In the context of memetic algorithms, the meme is an implementation of the local optimization method to refine solution in the search.
The concept of memetic algorithms provides ample opportunities for the development of various modifications of these algorithms, which can vary the frequency of the local search, the conditions of its end, and so on. The practically significant memetic algorithm modifications involve the simultaneous use of different memes. Such algorithms are called multi-memetic.
The paper gives statement of the global problem of nonlinear unconstrained optimization, describes the most promising areas of AI modifications, including hybridization and meta-optimization. The main content of the work is the classification and review of existing varieties of memetic algorithms.
The results show that, despite the successful application of various memetic algorithms in various applications, there are a large number of directions for their modification and study. These are, for example, a more detailed study of self-adaptation methods of memetic algorithms, development of methods to assess the meme ability to refine the solution at a particular stage of the working algorithm. Besides the problem of selecting memes, there are also problems associated with the duration of local search. The solution is a balance of computing time between the local and global search. For a fixed computing time it allows to allocate time between global and local search in the solution of the optimization problem, which will increase the efficiency of the algorithms.

1. Karpenko A.P. Sovremennye algoritmy poiskovoi optimizatsii. Algoritmy, vdokhnovlennye prirodoi [Modern algorithms of search engine optimization. Nature-inspired optimization algorithms]. Moscow, Bauman MSTU Publ., 2014. 446 p. (in Russian)
2. Karpenko A.P., Sakharov M.K. Multi-Memes Global Optimization Based on the Algorithm of Mind Evolutionary Computation. Informacionnye Tehnologii = Information Technologies , 2014, no. 7, pp. 23-30. (in Russian).
3. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning . Addison-Wesley, 1989, p. 372.
4. Dawkins R. The Selfish Gene . Oxford University Press, 1976, p. 224.
5. Sakharov M.K., Karpenko A.P., Velisevich Ya.I. Multi-Memetic Mind Evolutionary Computation Algorithm for Loosely Coupled Systems of Desktop Computers. Nauka i obrazovanie MGTU im. N.E. Baumana = Science and Education of the Bauman MSTU , 2015, no. 10, pp. 438-452. DOI:10.7463/1015.0814435
6. Krasnogor N., Blackburne B., Hirst J.D., Burke E.K. Multimeme Algorithms for the Structure Prediction and Structure Comparison of Proteins. In book: Guervos J.J.M. et al, eds. Parallel Problem Solving from Nature – PPSN VII . Springer Berlin Heidelberg, 2002, pp. 769-778. DOI: 10.1007/3-540-45712-7_74 (Ser . Lecture Notes in Computer Science ; vol. 2439.).
7. Ong Y.S., Keane A.J. Meta-Lamarckian learning in memetic algorithms. IEEE Transactions on Evolutionary Computation , 2004, vol. 8, no. 2, pp. 99-110. DOI: 10.1109/TEVC.2003.819944
8. Ong Y.S. Artificial Intelligence Technologies in Complex Engineering Design. Ph.D. Thesis . School of Engineering Science, University of Southampton, United Kingdom, 2002.
9. Krasnogor N. Studies on the Theory and Design Space of Memetic Algorithms. Ph.D. Thesis . Faculty of Computing, Mathematics and Engineering, University of the West of England, Bristol, U.K., 2002.
10. Davis L., ed. Handbook of genetic algorithms . Van Nostrand Reinhold, New York, 1991. 385 p.
11. Moscato P. On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms . Caltech Concurrent Computation Program 158-79, California Institute of Technology, Pasadena, California, USA. 1989. 67 p.
12. Zhu N., Ong Y.S., Wong K.W., Seow K.T. Using memetic algorithms for fuzzy modeling. Australian Journal of Intelligent Information Processing Systems , 2004, vol . 8, no. 3, pp. 147-154.
13. Burke E.K., Kendall G., Soubeiga E. A Tabu-Search Hyperheuristic for Timetabling and Rostering. Journal of Heuristics , 2003, vol . 9, no. 6, pp. 451-470. DOI:10.1023/B:HEUR.0000012446.94732.b6
14. Bin Li, Zheng Zhou, Weixia Zou, Dejian Li. Quantum Memetic Evolutionary Algorithm-Based Low-Complexity Signal Detection for Underwater Acoustic Sensor Networks. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews , 2012, vol. 42, no. 5, pp. 626-640. DOI: 10.1109/TSMCC.2011.2176486
15. Maolin Tang, Xin Yao. A Memetic Algorithm for VLSI Floorplanning. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics , 2007, vol. 37, no. 1, pp. 62-69. DOI: 10.1109/TSMCB.2006.883268
16. Molina D., Lozano M., Herrera F. Memetic algorithm with local search chaining for continuous optimization problems: A scalability test. In ISDA. Proceedings of the 2009 Ninth International Conference on Intelligent Systems Design and Applications (ISDA’09). IEEE Publ., 2009, pp. 1068-1073. DOI: 10.1109/ISDA.2009.143
17. Ang J.H., Tan K.S., Mamun A.A. An evolutionary memetic algorithm for rule extraction. Expert Systems with Applications , 2010, vol. 37, is. 2, pp. 1302-1315. DOI: 10.1016/j.eswa.2009.06.028
18. Bhowmik P., Rakshit P., Konar A., Nagar A.K., Kim E. DETDQL: an adaptive memetic algorithm. 2012 IEEE Congress on Evolutionary Computation (CEC) . IEEE Publ., 2012, pp. 1-8. DOI: 10.1109/CEC.2012.6256573
19. Qin K., Suganthan P.N. Self-adaptive differential evolution algorithm for numerical optimization. Proceedings of the 2005 IEEE Congress on Evolutionary Computation. Vol. 2 . IEEE Publ., 2005, pp. 1785-1791. DOI: 10.1109/CEC.2005.1554904
20. Knowles J., Corne D., Wu A. A comparison of diverse approaches to memetic multiobjective combinatorial optimization. Proceedings of the 2000 Genetic and Evolutionary Computation Conference. 1st Workshop Memetic Algorithms . San Francisco: Morgan Kaufmann Publishers, 2000, pp.103-108.  
21. Moscato P. Memetic algorithms for molecular conformation and other optimization problems. International Union of Crystallography, Newsletter of the Commission for Powder Diffraction , 1998, no. 20, pp. 32-33.
22. Neri F., Cotta C., Moscato P. Handbook of Memetic Algorithms . Springer Berlin Heidelberg, 2011. 368 p. DOI: 10.1007/978-3-642-23247-3 (Ser. Studies in Computational Intelligence ; vol. 379).
23. Moscato P., Corne D., Glover F., Dorigo M. Memetic algorithms: A short introduction. In book: New Ideas in Optimization . McGraw-Hill, 1999 , pp. 219-234.
24. Neri F., Cotta C. Memetic algorithms and memetic computing optimization: A literature review. Swarm and Evolutionary Computation , 2012, vol. 2, pp. 1-14. DOI:10.1016/j.swevo.2011.11.003
25. Liang K., Yao X., Newton C. Lamarckian evolution in global optimization. Proc. of the 26th Annual Conference of the IEEE Industrial Electronics Society (IECON 2000). Vol. 4 . IEEE Publ., 2000, pp. 2975-2980. DOI: 10.1109/IECON.2000.972471
26. Houck C., Joines J. Kay M. Utilizing Lamarckian Evolution and the Baldwin Effect in Hybrid Genetic Algorithms. NCSU-IE Technical Report 96-01 . Meta-Heuristic Research and Applications Group, Department of Industrial Engineering, North Carolina State University, 1996, pp. 96-101.
27. Wolpert D., Macready W. No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation , 1997, vol. 1, no. 1, pp. 67-82 . DOI:10.1109/4235.585893
28. Krasnogor N., Smith J. A tutorial for competent memetic algorithms: model, taxonomy, and design issues. IEEE Transactions on Evolutionary Computation , 2005, vol. 9, is. 5, pp. 474-488. DOI: 10.1109/TEVC.2005.850260
29. Yi Mei, Ke Tang, Xin Yao. Decomposition-Based Memetic Algorithm for Multiobjective Capacitated Arc Routing Problem. IEEE Transactions on Evolutionary Computation , 2011, vol . 15, is. 2, pp. 151-165. DOI: 10.1109/TEVC.2010.2051446
30. Miller J.A., Potter W.D., Gandham R.V., Lapena C.N. An evaluation of local improvement operators for genetic algorithms. IEEE Transactions on Systems, Man and Cybernetics , 1993, vol. 23, is. 5, pp. 1340-1351. DOI: 10.1109/21.260665
31. Ishibuchi H., Yoshida T., Murata T. Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling. IEEE Transactions on Evolutionary Computation , 2003, vol . 7, is. 2, pp. 204-223. DOI: DOI: 10.1109/TEVC.2003.810752
32. Bambha N.K., Bhattacharyya S.S., Teich J., Zitzler E. Systematic integration of parameterized local search into evolutionary algorithms. IEEE Transactions on Evolutionary Computation , 2004, vol . 8, is. 2, pp. 137-154. DOI: 10.1109/TEVC.2004.823471
33. Tang J., Lim M.H., Ong Y.S. Diversity-Adaptive Parallel Memetic Algorithm for Solving Large Scale Combinatorial Optimization Problems. Soft Computing: A Fusion of Foundations, Methodologies and Applications , 2007, vol. 11, is. 9, pp. 873-888. DOI:10.1007/s00500-006-0139-6
34. Merz P., Freisleben B. et al. Fitness landscapes and memetic algorithm design. In book: Corne D. et al, eds. New Ideas in Optimization . New York, McGraw-Hill, 1999, pp. 245-260.
35. Ong Y.S., Keane A.J. A domain knowledge based search advisor for design problem solving environments. Engineering Applications of Artificial Intelligence , 2002, vol . 15, no. 1, pp. 105-116 . DOI:10.1016/S0952-1976(02)00016-7
36. Ong Y.S., Lim M.H., Zhu N., Wong K.W. Classification of adaptive memetic algorithms: A comparative study. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics , 2006, vol. 36, is. 1, pp. 141-152. DOI: 10.1109/TSMCB.2005.856143
37. Hart W., Krasnogor N., Smith J. Recent Advances in Memetic Algorithms . Springer Berlin Heidelberg , 2004. 410 p. DOI:10.1007/3-540-32363-5
38. Smith J., Hart W., Krasnogor N. Editorial Introduction Special Issue on Memetic Algorithms. Evolutionary Computation , 2004, vol . 12, no. 3, pp. 273-353 . DOI:10.1162/1063656041775009
39. Hart W.E. Adaptive Global Optimization with Local Search. PhD Thesis . University of California, San Diego, 1994. 135 p.
40. Hinterding R., Michalewicz Z., Eiben A.E. Adaptation in Evolutionary Computation: A Survey. IEEE International Conference on Evolutionary Computation . IEEE Press, 1997, pp. 65-69. DOI: 10.1109/ICEC.1997.592270
41. Gutin G., Karapetyan D. A selection of useful theoretical tools for the design and analysis of optimization heuristics. Memetic Computing , 2009, vol. 1, no. 1, pp. 25-34. DOI:10.1007/s12293-008-0001-8
42. Kendall G., Cowling P., Soubeiga E. Choice function and random hyperheuristics. Proc. of the 4th Asia-Pacific Conference on Simulated Evolution and Learning (SEAL 2002) , Singapore, Nov. 2002, pp. 667-671.
43. Smith J. Co-evolving Memetic Algorithms: Initial Investigations. In book: Guervos J.J.M. et al, eds. Parallel Problem Solving from Nature – PPSN VII . Springer Berlin Heidelberg, 2002, pp. 537-546. DOI: 10.1007/3-540-45712-7_52 (Ser. Lecture Notes in Computer Science ; vol. 2439.).
44. Qin K., Suganthan P.N. Self-adaptive differential evolution algorithm for numerical optimization. Proceedings of the 2005 IEEE Congress on Evolutionary Computation. Vol. 2 . IEEE Publ., 2005, pp. 1785-1791. DOI: 10.1109/CEC.2005.1554904
45. Smith J.E. Coevolving Memetic Algorithms: A Review and Progress Report. IEEE Transactions on Systems, Man, and Cybernetics, Part B , 2007, vol. 37, is. 1, pp. 6-17. DOI: 10.1109/TSMCB.2006.883273
46. Smith J.E. Estimating meme fitness in adaptive memetic algorithms for combinatorial problems. Evolutionary Computation , 2012, vol. 20, is. 2, pp. 165-188. DOI: 10.1162/EVCO_a_00060
47. Krasnogor N., Gustafson S. A study on the use of self-generation in memetic algorithms. Natural Computing , 2004, vol. 3, is. 1, pp. 53-76. DOI:10.1023/B:NACO.0000023419.83147.67
48. Smith J.E. Co-evolving memetic algorithms: A learning approach to robust scalable optimization. The 2003 Congress on Evolutionary Computation (CEC’03). V ol. 1 . IEEE Press, 2003, pp. 498-505. DOI: 10.1109/CEC.2003.1299617
49. Krasnogor N. Coevolution of genes and memes in memetic algorithms. In: Wu A., ed. Proceedings of the 1999 Genetic and Evolutionary Computation Conference Workshop Program . 1999 , p. 371.
50. Meuth R., Lim M.H., Ong Y.S., Wunsch II D.C. A proposition on memes and meta-memes in computing for higher-order learning. Memetic Computing , 2009, vol. 1, is. 2, pp. 85-100. DOI:10.1007/s12293-009-0011-1
51. Cao Y.J., Wu Q.H. Convergence analysis of adaptive genetic algorithm. Second International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications (GALESIA 97). (Conf. Publ. No. 446). IEEE Publ., 1997, pp. 85-89. DOI: 10.1049/cp:19971160
52. Knowles J., Corne D. M-PAES: A memetic algorithm for multiobjective optimization. Proceedings of the 2000 Congress on Evolutionary Computation (CEC2000). Vol . 1 . IEEE Publ., 2000, pp. 325-332 . DOI:10.1109/CEC.2000.870313
53. Krasnogor N., Mocciola P., Pelta D., Ruiz G., Russo W. A runnable functional memetic algorithm framework. Proceedings of the Argentinian Congress on Computer Sciences . Universidad Nacional del Comahue , 1998, pp. 525-536 .
54. Tang J., Lim M.H., Ong Y.S. Parallel Memetic Algorithm with Selective Local Search for Large Scale Quadratic Assignment. International Journal of Innovative Computing, Information and Control , 2006, vol. 2, no. 6, pp. 1399-1416. 
55. Hart W., Krasnogor N., Smith J.E. Memetic Evolutionary Algorithms. In book: Recent Advances in Memetic Algorithms . Springer Berlin Heidelberg, 2005, pp. 3-27. DOI:10.1007/3-540-32363-5_1 (Ser. Studies in Fuzziness and Soft Computing ; vol. 166.).