НАУКА и ОБРАЗОВАНИЕ

Файл статьи: SE-BMSTU...o142.pdf (1431.61Кб)

УДК 519.6

1 МГТУ им. Н.Э. Баумана, Москва, Россия

В последние десятилетия, эволюционные алгоритмы зарекомендовали себя как мощные методы поисковой оптимизации. Их популярность обусловлена тем, что они легко реализуются и могут применяться в любых сферах, поскольку в их основе лежит универсальная идея эволюции. Например, в задачах с большим числом локальных оптимумов, традиционные методы оптимизации обычно не справляются с поиском глобального оптимума. Для решения такого рода задач используют различные стохастические методы, в частности, так называемые популяционные алгоритмы, являющиеся разновидностью эволюционных методов. Основным недостатком данного класса методов является их медленная сходимость к точному решению в окрестности глобального оптимума, так как эти методы не способны использовать локальную информацию о ландшафте исследуемой функции. Это часто ограничивает их использование в масштабных реальных задачах, где время вычислений является критическим фактором.
Одним из перспективных современных направлений в области эволюционных вычислений являются меметические алгоритмы, которые можно рассматривать как сочетание популяционного поиска глобального оптимума и процедур локального уточнения решений, которое дает синергетический эффект. В контексте меметических алгоритмов, мем является реализацией какого-либо метода локальной оптимизации, уточняющего решение в процессе поиска. МА.
Концепция меметических алгоритмов предоставляет широкие возможности для разработки различных модификаций этих алгоритмов, которые могут отличаться частотой выполнения локального поиска, условиями его окончания и так далее. Практически значимые модификации меметических алгоритмов предполагают одновременное использование различных мемов. Такие алгоритмы называют мультимемеевыми.
В работе дана постановка задачи нелинейной глобальной безусловной оптимизации, описаны наиболее перспективные направления модификации МА, включая гибридизацию и мета-оптимизацию. Основное содержание работы представляет классификация и обзор существующих разновидностей меметических алгоритмов.
Результаты исследования показывают, что, несмотря на успешное применение различных меметических алгоритмов в разнообразных прикладных задачах, существует большое число направлений для их модификации и изучения. Например, более подробное изучение методов самоадаптации меметических алгоритмов, разработка методов оценки способности мема уточнять решение на конкретном этапе работы алгоритма. Помимо проблемы выбора мемов, существуют также проблемы, связанные с продолжительностью локального поиска. Решением является некий баланс вычислительного времени между локальным и глобальным поисками. При фиксированном времени вычислений это позволяет распределять время между глобальным и локальным поиском в процессе решения задачи оптимизации, что увеличит эффективность алгоритмов.

1. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с.
2. Карпенко А.П., Сахаров М.К. Мультимемеевая глобальная оптимизация на основе алгоритма эволюции разума // Информационные технологии. 2014. № 7. С . 23-30.
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 // Наука и образование . МГТУ им. Н.Э. Баумана. Электрон. журн . 2015. № 10. С . 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: Parallel Problem Solving from Nature – PPSN VII / ed. by J.J.M. Guervos et al. Springer Berlin Heidelberg, 2002. P. 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. P. 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. V ol. 8, no. 3. P. 147-154.
13. Burke E.K., Kendall G., Soubeiga E. A Tabu-Search Hyperheuristic for Timetabling and Rostering // Journal of Heuristics. 2003. V ol. 9, no. 6. P. 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. P. 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. P. 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. P. 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. P. 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. P. 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. P. 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. P.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. P . 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 . P. 219-234.
24. Neri F., Cotta C. Memetic algorithms and memetic computing optimization: A literature review // Swarm and Evolutionary Computation. 2012. Vol. 2. P. 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. P. 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. P. 96-101.
27. Wolpert D., Macready W. No free lunch theorems for optimization // IEEE Transactions on Evolutionary Computation. 1997. Vol. 1, no. 1. P. 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. P. 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. V ol. 15, is. 2. P. 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. P. 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. V ol. 7, is. 2. P. 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. V ol. 8, is. 2. P. 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. P. 873-888. DOI:10.1007/s00500-006-0139-6
34. Merz P., Freisleben B. et al. Fitness landscapes and memetic algorithm design // In book: New Ideas in Optimization / ed. by D. Corne et al. New York: McGraw-Hill, 1999. P. 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. V ol. 15, no. 1. P. 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. P. 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. V ol. 12, no. 3. P. 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. P. 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. P. 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. P. 667-671.
43. Smith J. Co-evolving Memetic Algorithms: Initial Investigations // In book: Parallel Problem Solving from Nature – PPSN VII / ed. by J.J.M. Guervos et al. Springer Berlin Heidelberg, 2002. P. 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. P. 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. P. 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. P. 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. P. 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) . Vol. 1. IEEE Press, 2003. P. 498-505. DOI: 10.1109/CEC.2003.1299617
49. Krasnogor N. Coevolution of genes and memes in memetic algorithms // Proceedings of the 1999 Genetic and Evolutionary Computation Conference Workshop Program / ed. by A. Wu. 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. P . 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. P. 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. P. 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. P. 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. P. 1399-1416. 
55. Hart W., Krasnogor N., Smith J.E. Memetic Evolutionary Algorithms // In book: Recent Advances in Memetic Algorithms. Springer Berlin Heidelberg, 2005. P. 3-27. DOI: 10.1007/3-540-32363-5_1 (Ser. Studies in Fuzziness and Soft Computing; vol. 166.).