ALGORITHM FOR DETERMINING THE PARAMETERS OF BIO-INSPIRED SEARCH BASED ON BORROWING THE RESULTS OF PREVIOUSLY SOLVED PROBLEMS
Abstract
The problem of selecting the most effective hardware architecture in the implementation of genetic algorithms that solve NP-complete problems is considered. The peculiarity of this kind of problems is the unproven existence of algorithms capable of finding an exact solution in polynomial time. Evolutionary algorithms used to solve such problems are stochastic in nature, which makes it difficult to plan the computational process effectively. The aim of the work is to find ways to reduce the search time by analyzing the results obtained in solving similar problems considered earlier and choosing an effective architecture that implements this evolutionary algorithm. The relevance of the work is due to the exponential growth of the dimensions of the optimization problems to be solved. The scientific novelty lies in the use of knowledge about previously solved problems to optimize the parameters of the genetic algorithm that solves the current problem, and the choice of an effective hardware architecture on which this algorithm will be implemented. The exact boundary, as a function of the number of individuals processed by the stochastic algorithm, of the most appropriate architecture cannot be determined precisely. For this reason, the boundary of the most efficient hardware architecture is defined as a fuzzy set. The problem statement is: to accelerate the process of solving the current task, using the a priori parameter settings of genetic algorithm based on the analysis of the results of decisions previously discussed tasks, and choosing efficient hardware architecture. An approach to the selection of effective hardware architecture is proposed, consisting of three stages: analysis of the results of solving the previously considered problems, determining the number of individuals that must be generated to obtain an acceptable solution by the evolutionary algorithm, selection of hardware architecture on which the evolutionary algorithm will be implemented.
References
тия ЮФУ. Технические науки. – 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.
