Класичний та бінарний генетичні алгоритми для знаходження глобального оптимуму в задачах невипуклої оптимізації
Date
2018
Journal Title
Journal ISSN
Volume Title
Publisher
ДВНЗ «Київський національний економічний університет імені Вадима Гетьмана»
Abstract
Розглянуто класичний і бінарний підходи до імплементації генетичного алгоритму оптимізації. Генетичний алгоритм оптимізації
дозволяє знаходити глобальний мінімум як випуклих функцій (таких, що
мають лише один мінімум), так і функцій, що мають кілька екстремумів.
Це дозволяє застосовувати його в погано поставлених задачах, де існує
нескінченна множина розв`язків. Окрім того алгоритм не вимагає диференційованості функції в усіх точках і може використовуватись як ефективна альтернатива градієнтному спуску у вирішенні задач, де необхідний розрахунок багатовимірних градієнтів. Проведено
експериментальне дослідження з порівняння ефективності класичного
та бінарного підходів. Експеримент застосовано до двох фукнцій: квадратичної функції (випукла функція) та функції Растригіна (приклад ні випуклої, ні впуклої функції). До параметрів цих функцій застосовано генетичні оператори селекції (відбору), мутації та схрещення. Після цього
для результуючих параметрів розраховано функцію прийняття, яка перевіряє, чи параметр досі задовольняє умовам задачі. Цільова функція
визначає, чи оптимальне рішення знайдено. Для оцінки ефективності
двох підходів використано дві міри: середня кількість ітерацій до збіжності та час збіжності (у мілісекундах). Окрім цього ми варіювали коефіцієнт мутації аби знайти таке його значення, за якого дві дані міри мінімізуються. Виявлено, що за зменшення парматера мутації збіжність
класичного алгоритму покращується, проте після досягнення ним певного рівня є ризик того, що алгоритм почне розходитись. При цьому не
було виявлено явної залежності міє збіжністю бінарного алгоритму та
параметром мутації, що робить його універсальнішим у використанні.
Зроблено висновок, що класичний підхід у рамках даної програмної реалізації є ефективнішим за часом виконання та має вищу точність, хоча і є
складнішим в реалізації.
Classic and binary approaches to implementation of genetic
algorithm of optimization are proposed. Genetic algorithm allows to find a
minima of both convex functions (such that have only one minima) and
functions that have multiple minimums. Thus it can be applied to ill-posed
problems where there is an infinite number of solutions. Moreover the algorithm
does not require differentiability of the optimized function and can be used as
efficient alternative to gradient descent in problems that require calculation of
multi-dimensional gradients. We conducted experimental research in
comparison of efficiency of classic and binary approaches. Experiment is
applied to two functions: quadratic function (convex) and Rastrigin function (as
an example of neither convex nor concave function). Then genetic operators of
selection, mutation and crossover are applied to function’s parameters.
Resulting parameters are then used to calculate the acceptance function that
checks if the parameters still satisfy problem’s conditions. Cost function is used
to check if the optimal solution is found. To compare the efficiency of both
approaches we used two measures: average number of iterations to
convergence and time of convergence (in miliseconds). We also varied the
mutation coefficient to find such its value that minimizes value of both
measures. It turned out that decreasing mutation parameter improves
convergence of classic algorithm but after reaching certain level it can cause
divergence. No correlation between convergence of binary algorithm and
mutation parameter was found so binary algorithm turns out to be more generic
in use. Concluded that classic approach within current program implementation
is more efficient in terms of execution time and has bigger precision despite of
being more complex.
Description
Keywords
генетичний алгоритм, оптимізація, стохастична оптимізація, мутація, схрещування, відбір, genetic algorithm, optimization, stochastic optimization, mutation, crossover, selection
Citation
Бондаренко М. В. Класичний та бінарний генетичні алгоритми для знаходження глобального оптимуму в задачах невипуклої оптимізації / Бондаренко М. В., Бондаренко В. М. // Моделювання та інформаційні системи в економіці : зб. наук. пр. / М-во освіти і науки України, ДВНЗ «Київ. нац. екон. ун-т ім. Вадима Гетьмана» ; [редкол.: В. К. Галіцин (голов. ред.) та ін.]. – Київ : КНЕУ, 2018. – Вип. 95. – С. 44–56.