АЛГОРИТМ ОПРЕДЕЛЕНИЯ ПАРАМЕТРОВ БИОИНСПИРИРОВАННОГО ПОИСКА НА ОСНОВЕ ЗАИМСТВОВАНИЯ РЕЗУЛЬТАТОВ РЕШЕННЫХ РАНЕЕ ЗАДАЧ
Аннотация
Рассмотрена проблема выбора наиболее эффективной аппаратной архитектуры при
реализации генетических алгоритмов, решающих NP-полные задачи. Особенность подобно-
го рода задач – недоказанность наличия алгоритмов, способных находить точное решение
за полиномиальное время. Используемые для решения подобных задач эволюционные алго-
ритмы являются стохастическими по своей сути, что затрудняет эффективное планиро-
вание вычислительного процесса. Цель работы состоит в нахождении способов сокраще-
ния времени поиска за счет анализа результатов, полученных при решении аналогичных
задач, рассмотренных ранее, и выбора эффективной архитектуры, реализующей данный
эволюционный алгоритм. Актуальность работы обусловлена экспоненциальным ростом
размерностей решаемых оптимизационных задач. Научная новизна заключается в исполь-
зовании знаний о решенных ранее задачах для оптимизации параметров генетического
алгоритма, решающего текущую задачу, и выбора эффективной аппаратной архитекту-
ры, на которой будет реализован данный алгоритм. Точная граница, как функция от числа
обрабатываемых стохастическим алгоритмом особей, наиболее приемлемой архитектуры
может быть определена только приближенно. По этой причине, граница наиболее эф-
фективной аппаратной архитектуры задается в виде нечеткого множества. Постановка
задачи состоит в следующем: ускорить процесс решения текущей задачи, используя апри-
орные настройки параметров генетического алгоритма, основываясь на анализе резуль-
татов решений, рассмотренных ранее задач, и выборе эффективной аппаратной архи-
тектуры. Предложен подход к выбору эффективной аппаратной архитектуры, состоя-
щий из трех этапов: анализа результатов решения рассмотренных ранее задач, определе-
ния количества особей, которые необходимо сгенерировать для получения приемлемого
решения эволюционным алгоритмом, выбора аппаратной архитектуры, на которой будет
реализован эволюционный алгоритм.
Литература
тия ЮФУ. Технические науки. – 2012. – № 7 (132). – С. 92-98.
2. Deb K., Myburgh C. Breaking the Billion-Variable Barrier in Real-World Optimization Using
a Customized Evolutionary Algorithm // Proceedings of Genetic and Evolutionary Computation
Conference. – 2016. – P. 653-660.
3. Родзин С.И., Скобцов Ю.А., Эль-Хатиб С.А. Биоэвристики: теория, алгоритмы и при-
ложения: монография. – Чебоксары: ИД «Среда», 2019. – 224 с.
4. Курейчик В.М., Данильченко В.И. Генетический алгоритм планирования размещения
СБИС // Известия ЮФУ. Технические науки. – 2019. – № 2 (204). – C. 26-34.
5. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. – М.: Физматлит,
2006, 2010. – 386 с.
6. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохнов-
ленные природой. – М.: Изд-во МГТУ им. Н.Э. Баумана, 2014. – 446 с.
7. Пантелеев А.В., Метлицкая Д.В., Алешина Е.А. Методы глобальной оптимизации. Ме-
таэвристические стратегии и алгоритмы. – М.: Вузовская книга, 2013. – 244 с.
8. Пантелеев А.В. Применение эволюционных методов глобальной оптимизации в задачах оп-
тимального управления детерминированными системами. – М.: Изд-во МАИ, 2013. – 160 с.
9. Курейчик В.М. Гибридные генетические алгоритмы // Известия ЮФУ. Технические нау-
ки. – 2007. – № 2 (77). – C. 5-12.
10. Агибалов О.И., Венцов Н.Н. Оценка зависимостей времени работы генетического алгоритма,
выполняемого на CPU и GPU // Кибернетика и программирование. – 2017. – № 6. – С. 1-8.
– DOI: 10.25136/2306-4196.2017.6.24509. – URL: http://e-notabene.ru/kp/article_24509.html.
11. Чернышев В.О., Грабауров В.А. Системный подход к управлению субъектами хозяйст-
вования / под ред. Ф.А. Романюка. – Минск: БНТУ, 2014. – 272 с.
12. Fan Zhang, Zheng Li, Bingnan Wang, Maosheng Xiang, Wen Hong. Hybrid general-purpose
computation on GPU (GPGPU) and computer graphics synthetic aperture radar simulation for
complex scenes // International Journal of Physical Sciences. – 16 February, 2012. – Vol. 7
(8). – P. 1224-1234.
13. Shell J., Coupland S. Fuzzy Transfer Learning: Methodology and Application // Preprint submitted
to Information Sciences. – May 23, 2014. – 27 p.
14. Samitha Herath, Mehrtash Harandi, Basura Fernando, Richard Nock. Min-Max Statistical
Alignment for Transfer Learning // Proceedings of the IEEE Conference on Computer Vision
and Pattern Recognition. – 2019. – P. 9288-9297.
15. Yiyang Li, Guanyu Tao, Weinan Zhang, Yong Yu, Jun Wang. Content Recommendation by Noise
Contrastive Transfer Learning of Feature Representation // Proceedings of the 2017 ACM on Conference
on Information and Knowledge Management, ACM. – 2017. – P 1657-1665.
16. Pan S.J., Yang Q. IEEE Transactions on knowledge and data engineering // Institute of Electrical
and Electronics Engineers, Inc., NY, 2010. – Vol. 22 (10). – P 1345-1359.
17. Сапрыкин А.Н., Акинина К.Д., Сапрыкина Е.Н. Нахождение оптимального числа полез-
ных особей в популяции и конвергируемых поколений генетического алгоритма опти-
мизации простых многоэкстремальных функций // Actualscience. – 2016. – Т. 2. № 11.
– С. 168-169.
18. Zadeh L.A. Fuzzy sets // Information and Control. – 1965. – Vol. 8. – P. 338.
19. Нечеткие множества в моделях управления и искусственного интеллекта / под ред.
Д.А. Поспелова. – М.: Наука, 1986 – 312 c.
20. Курейчик В.М., Данильченко В.И. Классификация и анализ методов решения задачи раз-
мещения СБИС // Информатика, вычислительная техника и инженерное образование.
– 2018. – № 1 (32). – C. 21-40.
