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.
