Guided hybrid genetic algorithm for solving global optimization problems

Abstract

EN: Context. One of the leading problems in the world of artificial intelligence is the optimization of complex systems, which is often represented as a nonlinear function that needs to be minimized. Such functions can be multimodal, non-differentiable, and even set as a black box. Building effective methods for solving global optimization problems raises great interest among scientists. Objective. Development of a new hybrid genetic algorithm for solving global optimization problems, which is faster than existing analogues. Methods. One of the crucial challenges for hybrid methods in solving nonlinear global optimization problems is the rational use of local search, as its application is accompanied by quite expensive computational costs. This paper proposes a new GBOHGA hybrid genetic algorithm that reproduces guided local search and combines two successful modifications of genetic algorithms. The first one is BOHGA that establishes a qualitative balance between local and global search. The second one is HGDN that prevents re-exploration of the previously explored areas of a search space. In addition, a modified bump-function and an adaptive scheme for determining one of its parameters – the radius of the “deflation” of the objective function in the vicinity of the already found local minimum – were presented to accelerate the algorithm. Results. GBOHGA performance compared to other known stochastic search heuristics on a set of 33 test functions in 5 and 25-dimensional spaces. The results of computational experiments indicate the competitiveness of GBOHGA, especially in problems with multimodal functions and a large number of variables. Conclusions. The new GBOHGA hybrid algorithm, developed on the basis of the integration of guided local search ideas and BOHGA and HGDN algorithms, allows to save significant computing resources and speed up the solution process of the global optimization problem. It should be used to solve global optimization problems that arise in engineering design, solving organizational and management problems, especially when the mathematical model of the problem is complex and multidimensional. UK: Актуальність. Провідною проблемою в світі штучного інтелекту є оптимізація складних систем, що нерідко подається у вигляді нелінійної функції, яку необхідно мінімізувати. Такі функції можуть виявитися мультимодальними, недиференційованими, і навіть, заданими у формі чорної скриньки. Побудова ефективних методів розв’язання задач глобальної оптимізації і сьогодні викликав значний інтерес серед науковців. Мета. Розробка нового гібридного генетичного алгоритму розв’язання задачі безумовної глобальної оптимізації, швидшого за існуючі аналоги. Методи. Одним з важливих викликів, з якими стикаються гібридні методи під час розв’язування задач нелінійної глобальної оптимізації, є раціональне використання локального пошуку, оскільки його реалізація супроводжується достатньо коштовними обчислювальними витратами. В даній роботі запропонований новий гібридний генетичний алгоритм GBOHGA, який відтворює керований локальний пошук, і поєднує дві успішні модифікації генетичних алгоритмів, перша з яких BOHGA встановлює якісний баланс між локальним та глобальним пошуком, друга – HGDN – запобігає повторному дослідженню раніше вже розвіданої області пошукового простору. Окрім цього, було запропоновано модифіковану bump-функцію та адаптивну схему визначення її параметру – радіусу області «дефляції» цільової функції в околі вже знайденого локального мінімуму – задля прискорення роботи алгоритму. Результати. Роботу GBOHGA з іншими відомими стохастичними пошуковими евристиками на наборі із 33 тестових функцій в 5 та 25 вимірному просторах. Результати обчислювальних експериментів свідчать про конкурентну спроможність GBOHGA, особливо в задачах з мультимодальними функціями і великою кількістю змінних. Висновки. Новий гібридний алгоритм GBOHGA, розроблений на основі інтеграції ідей керованого локального пошуку і алгоритмів BOHGA та HGDN, дозволяє значно економити обчислювальні ресурси та прискорювати розв’язання задачі глобальної оптимізації. Його варто застосовувати для розв’язання задач глобальної оптимізації, що виникають в інженерному проектуванні, вирішення організаційно-управлінських проблем, особливо коли математична модель задачі є складною і має високу розмірність.