Випуск № 95

Permanent URI for this collection

https://ir.kneu.edu.ua/handle/2010/30974

Browse

Browsing Випуск № 95 by Author "Bondarenko, Victor"

Now showing 1 - 1 of 1
  • Thumbnail Image
    Item
    Класичний та бінарний генетичні алгоритми для знаходження глобального оптимуму в задачах невипуклої оптимізації
    (ДВНЗ «Київський національний економічний університет імені Вадима Гетьмана», 2018) Бондаренко, Максим В.; Bondarenko, Maksym; Бондаренко, Віктор М.; Bondarenko, Victor
    Розглянуто класичний і бінарний підходи до імплементації генетичного алгоритму оптимізації. Генетичний алгоритм оптимізації дозволяє знаходити глобальний мінімум як випуклих функцій (таких, що мають лише один мінімум), так і функцій, що мають кілька екстремумів. Це дозволяє застосовувати його в погано поставлених задачах, де існує нескінченна множина розв`язків. Окрім того алгоритм не вимагає диференційованості функції в усіх точках і може використовуватись як ефективна альтернатива градієнтному спуску у вирішенні задач, де необхідний розрахунок багатовимірних градієнтів. Проведено експериментальне дослідження з порівняння ефективності класичного та бінарного підходів. Експеримент застосовано до двох фукнцій: квадратичної функції (випукла функція) та функції Растригіна (приклад ні випуклої, ні впуклої функції). До параметрів цих функцій застосовано генетичні оператори селекції (відбору), мутації та схрещення. Після цього для результуючих параметрів розраховано функцію прийняття, яка перевіряє, чи параметр досі задовольняє умовам задачі. Цільова функція визначає, чи оптимальне рішення знайдено. Для оцінки ефективності двох підходів використано дві міри: середня кількість ітерацій до збіжності та час збіжності (у мілісекундах). Окрім цього ми варіювали коефіцієнт мутації аби знайти таке його значення, за якого дві дані міри мінімізуються. Виявлено, що за зменшення парматера мутації збіжність класичного алгоритму покращується, проте після досягнення ним певного рівня є ризик того, що алгоритм почне розходитись. При цьому не було виявлено явної залежності міє збіжністю бінарного алгоритму та параметром мутації, що робить його універсальнішим у використанні. Зроблено висновок, що класичний підхід у рамках даної програмної реалізації є ефективнішим за часом виконання та має вищу точність, хоча і є складнішим в реалізації. 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.