Preview

Математика и математическое моделирование

Расширенный поиск

Исследование эффективности мульти-меметического алгоритма эволюции разума

https://doi.org/10.24108/mathm.0617.0000090

Полный текст:

Аннотация

При решении практически значимых задач глобальной оптимизации целевая функция зачастую имеет высокую размерность и вычислительную сложность, а также нетривиальный ландшафт. Исследования показывают, что зачастую одного метода оптимизации недостаточно для эффективного решения такого рода задач – необходима гибридизация нескольких методов оптимизации.

Одним из перспективных современных направлений в этой области являются меметические алгоритмы, МА, который можно рассматривать как сочетание популяционного поиска глобального оптимума и процедур локального уточнения решений (мемов), которое дает синергетический эффект. Поскольку существует относительно немного теоретических исследований, посвященных тому, какую конфигурацию МА рекомендуется использовать для решения black-box задач оптимизации, многие исследователи склоняются именно к адаптивным алгоритмам, которые в процессе поиска самостоятельно подбирают наиболее эффективные методы локальной оптимизации для определённых областей пространства поиска.

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

По результам исследования с использованием метода мульти-старта успешными оказались комбинации мемов, включающих в себя метод Хука-Дживса. Данные результаты свидетельствуют о быстрой сходимости метода к локальному оптимуму по сравнению с другими мемами, так как все методы выполняют не более фиксированного числа итераций.

Анализ среднего числа итераций показывает, что использование наиболее эффективных наборов мемов позволяет отыскать оптимальное решение за меньшее число итераций по сравнению с менее эффективными наборами. Дополнительно следует отметить, что не наблюдается зависимости общего числа итераций алгоритма от количества используемых мемов.

Результаты исследования демонстрируют, что метод Хука-Дживса оказался наиболее эффективным для выбранных функций, так как его наличие в наборе мемов позволяет существенно улучшить качество получаемого решения.  При этом результаты статистических тестов показывают, что использование дополнительных методов в наборе мемов, зачастую не оказывает значительного влияния на результаты работы алгоритма.

Об авторах

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

Сахаров Максим Константинович

РК6, Старший преподаватель, 

(SPIN-код): 2424-6202



А. В. Поноренко
МГТУ им. Н.Э. Баумана, Москва
Россия

Поноренко Андрей Вячеславович

Ассистент



Список литературы

1. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой: учеб. пособие. М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. 446 с.

2. Weise T. Global optimization algorithms: Theory and application. Kassel: Univ. of Kassel, 2008. 758 p.

3. Krasnogor N. Studies on the theory and design space of memetic algorithms: Doct. diss. Bristol: Univ. of the West of England, 2002.

4. Handbook of memetic algorithms / Ed. by Neri F., Cotta C., Moscato P. B.: Springer, 2012. 368 p. DOI: 10.1007/978-3-642-23247-3

5. Dawkins R. The selfish gene. N.Y.: Oxf. Univ. Press, 1976. 224 p.

6. Sakharov M.K., Karpenko A.P. New parallel multi-memetic MEC-based algorithm for loosely coupled systems // Optimization and applications: VII Intern. conf. on optimization methods and applications: OPTIMA-2016 (Petrovac, Montenegro, Sept. 25th - October 2nd, 2016): Proc. Moscow, 2016. Pp. 124-126.

7. Yew-Soon Ong, Meng-Hiot Lim, Ning Zhu, Kok-Wai Wong. Classification of adaptive memetic algorithms: A comparative study // IEEE Trans. on Systems, Man, and Cybernetics. Pt. B. 2006. Vol. 36. Iss. 1. Pp. 141-152. DOI: 10.1109/TSMCB.2005.856143

8. Handbook of test problems in local and global optimization / Floudas C.A. a.o. Dordrecht; Boston: Kluwer, 1999. 441 p.

9. Chengyi Sun, Yan Sun, Wanzhen Wang. A survey of MEC: 1998-2001 // 2002 IEEE intern. conf. on systems, man and cybernetics: IEEE SMC 2002 (Hammamet, Tunisia, October 6-9, 2002): Proc. Vol. 6. N.Y.: IEEE, 2002. Pp. 445-453. DOI: 10.1109/ICSMC.2002.1175629

10. Jing Jie, Jianchao Zeng, Youzhi Ren. Improved mind evolutionary computation for optimizations // 5th world congress on intelligent control and automation: WCICA 2004 (Hangzhou, China, June 15-19, 2004): Proc. N.Y.: IEEE, 2004. Pp. 2200 – 2204. DOI: 10.1109/WCICA.2004.1341978

11. Jing Jie, Chongzhao Han, Jianchao Zeng. An extended mind evolutionary computation model for optimizations // Applied Mathematics and Computation. 2007. Vol. 185. No. 2. Pp. 1038 – 1049. DOI: 10.1016/j.amc.2006.07.037

12. Sakharov M.K., Karpenko A.P. Performance investigation of mind evolutionary computation algorithm and some of its modifications // 1st intern. scientific conf. “Intelligent information technologies for industry”: IITI’16 (Sochi, Russia, May 20-31, 2016): Proc. Vol. 1. Z.: Springer, 2016. Pp. 475 – 486. DOI: 10.1007/978-3-319-33609-1_43

13. Nguyen Q.H., Ong Y.S., Krasnogor N. A study on the design issues of memetic algorithm // IEEE congress on evolutionary computation: CEC 2007 (Singapore, Singapore, September 25-28, 2007): Proc. N.Y.: IEEE, 2007. Pp. 2390-2397. DOI: 10.1109/CEC.2007.4424770

14. Карпенко А.П., Сахаров М.К. Мультимемеевая глобальная оптимизация на основе алгоритма эволюции разума // Информационные технологии. 2014. № 7. С. 23-30.

15. Nelder J.A., Mead R. A simplex method for function minimization // Computer J. 1965. Vol. 7. No. 4. Pp. 308-313. DOI: 10.1093/comjnl/7.4.308

16. Hooke R., Jeeves T.A. “Direct search" solution of numerical and statistical problems // J. of the Association for Computing Machinery (ACM). 1961. Vol. 8. No. 2. Pp. 212–229. DOI: 10.1145/321062.321069

17. Tukey J.W. Comparing individual means in the analysis of variance // Biometrics. 1949. Vol. 5. No. 2. Pp. 99–114. DOI: 10.2307/3001913


Для цитирования:


Сахаров М.К., Поноренко А.В. Исследование эффективности мульти-меметического алгоритма эволюции разума. Математика и математическое моделирование. 2017;(6):70-82. https://doi.org/10.24108/mathm.0617.0000090

For citation:


Sakharov M.K., Ponorenko A.V. Investigating the Multi-memetic Mind Evolutionary Computation Algorithm Efficiency. Mathematics and Mathematical Modeling. 2017;(6):70-82. (In Russ.) https://doi.org/10.24108/mathm.0617.0000090

Просмотров: 342


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2412-5911 (Online)