Аналіз алгоритмів оптимізації обчислення локального мінімуму функції Розенброка



Анотація. В роботі демонструється аналіз алгоритмів оптимізації обчислення на прикладі функції Розенброка з використанням інструменту LabView. Були обрані метод градієнтного спуску та генетичний алгоритм. Описано принцип роботи алгоритмів. Проведено обчислення локального мінімума функції Розенброка. Була порівняна кількість виконаних ітерацій для кожного алгоритму. Кращу швидкість виконання показав генетичний алгоритм. Ключові слова: функція Розенброка, генетичний алгоритм, метод градієнтного спуску, LabView, оптимізація.

Писаренко Олег Анатолійович

НТУУ “КПІ ім. І. Сікорського»

Київ, Україна

oa.pisarenko@gmail.com

Optimization algorithms analysis by solving Rosenbrock function

Abstract. The work demonstrates an analysis of optimization algorithms by solving Rosenbrock function using the LabView tool. A Downhill Simplex method and Genetic Algorithm were chosen. The principle of algorithms work is described. The local minimum of Rosenbrock function is calculated. The number of iterations performed for each algorithm was compared. The best rate of performance has been shown by using Genetic Algorithm. Keywords: Rosenbrock function, Genetic Algorithm, Downhill Simplex, LabView, optimization.

Oleh Pysarenko

Faculty of Informatics and Computer Technology Igor Sikorsky Kyiv Polytechnic Institute

Kyiv, Ukraine

oa.pisarenko@gmail.com

Вступ

В сучасному світі для вирішення багатьох проблем в галузях промисловості та автоматики не рідко піднімається проблема оптимізації. Оптимізація – пошук набору параметрів, що мінімізують функцію. Наприклад, оптимізацію можна використати для визначення певних параметрів для створенні систем управління або пошуку умов, які можуть мінімізувати вартість процесу виробництва. В даній роботі розглядаються метод градієнтного спуску та генетичний алгоритм та виконується їх порівняння на основі кількості ітерацій, що необхідні для знаходження локального мінімуму функції Розенброка.

Функція Розенброка

Для реалізації та тесту обраних алгоритмів була взята функція Розенброка [1] – невипукла функція, яка викорис-товується для оцінки продуктивності алгоритмів оптимі-зації.

Функція Розенброка для двох змінних визначається так:

\[f(x,y)={{(1-x)}^{2}}+100{{(y-{{x}^{2}})}^{2}}\qquad(1)\]

Локальний мінімум функції Розенброка знаходиться в точці (x, y) = (1, 1), де f(x,y) = 0. Графічне зображення функції наведене на рис. 1

Рис. 1. Графік функції Розенброка

Метод градієнтного спуску

Метод градієнтного спуску – також відомий як метод деформованого багатогранника і симплекс-метод, – метод безумовної оптимізації функції від декількох змінних, а тому легко застосовується до негладких і / або зашумле-них функцій [2]. Суть методу полягає в послідовному переміщенні і де-формації симплекса навколо точки екстремуму. Градієнтний спуск працює в просторах будь-якої кіль-кості розмірів, навіть у нескінченновимірних. Також, алгоритм може вимагати багато ітерацій для обчислення локального мінімуму з необхідною точністю, якщо кривизна в різних напрямках для даної функції дуже відрізняється. Метод знаходить локальний екстремум і може «застря-гти» в одному з них. Якщо все ж потрібно знайти глобаль-ний екстремум, можна пробувати вибрати інший початко-вий симплекс. Більш розвинений підхід до виключення локальних екстремумів пропонується в алгоритмах, за-снованих на методі Монте-Карло, а також в еволюційних алгоритмах.

Генетичний алгоритм

Одним із еволюційних алгоритмів є генетичний – алгоритм пошуку, який використовується для вирішення за-вдань оптимізації та моделювання шляхом випадкового підбору, комбінування і варіації шуканих параметрів. Він є різновидом еволюційних обчислень, за допомогою яких вирішуються оптимізаційні задачі з використанням мето-дів природної еволюції, таких як успадкування, мутації, відбір і кросинговер (генетичний оператор) [3]. Відмінною особливістю генетичного алгоритму є акцент на використання оператора «схрещування», який виробляє операцію рекомбінації рішень-кандидатів, роль якої аналогічна ролі схрещування в живій природі. Рішення, знайдене генетичним алгоритмом, називаєть-ся «хромосомою» [4]. Хромосома складається з генів, і її значення може бути числовим, бінарни або символьним, в залежності від проблеми, яку потрібно вирішити. Ці хромосоми проходять через фітнес-функцію (функцію пристосування), для визначення придатності рішення, створеного генетичним алгоритмом, з задачею. З отриманої множини рішень, беручи до уваги значення «пристосованості» обираються рішення до яких застосовується кро-синговер, в результаті чого отримуються нові рішення. Для них також обраховується значення пристосованості, а потім проводиться відбір кращих рішень в наступне покоління. Цей набір дій повторюється ітеративно і моделює еволюційний процес, що продовжується декілька життєвих циклів, доки не буде виконана умова зупинки алгоритму. Однієї із таких умов зупинки є знаходження локального або глобального екстремуму.

Оптимізація обчислень функції Розенброка

Для реалізації обраних алгоритмів та обчислення за допомогою них функції Розенброка був обраний програм-ний засіб LabView. Він надає можливості, що спеціально призначені для задач моделювання, оптимізації, управління і автоматизації, прискорюючи процес розробки. Інструмент LabView дозволяє реалізувати базові алгоритми оптимізації власними, завчасно створеними об’єктами. Для методу градієнтного спуску існує стандартний віртуальний інструмент (програма, скорочено VI) Downhill Simplex nD VI. Для коректного запуску алгоритму треба підключити необхідні вхідні параметри та вивести на передню панель можливість задавати дані та відображення результатів. Для реалізації генетичного алгоритму на базі LabVIEW була обрана стороння бібліотека Waptia – genetic optimization algorithm. Вона намагається знайти мінімальне значення заданої функції, використовуючи функцію пристосованості [5].
Генетичний алгоритм є більш складним в реалізації за базовий, який розглядався вище, але дозволяє більш гнучко і точно налаштувати роботу алгоритму для досягнення бажаних результатів. Після реалізації методу градієнтного спуску та генетичного алгоритму було проведено 5 експерементних обчислень для пошуку локального мінімуму для функції Розенброка. Результати обчислення для кожного алгоритму наведені в табл. 1.

Таблиця 1

Кількість ітерацій для знаходження мінімуму функції Розенброка

Висновки

В результаті виконання даної роботи було розглянуті два алгоритми оптимізації. А саме базовий – градієнтного спуску та сучасний – генетичний алгоритм. Алгоритми були програмно реалізовані в інструменті LabView. Як можна побачити з результатів виконання роботи алгоритмів для обчислення локального мінімуму функції Розенброка, метод градієнтного спуску для знаходження мінімуму функції зробив понад 700 обчислень. В той же час, для досягнення такого ж результату генетичний алгоритм зробив лише близько 20 обчислень. Можна зробити висновок, що базовий алгоритм не підходить для оптимізації складних функцій і для цього краще використовувати більш сучасний і кращий генетичний алгоритм, який дає більше можливостей для конфігурації його роботи та по-казує малу кількість ітерацій для знаходження екстрему-мів функції.

Література

$1.$ https://en.wikipedia.org/wiki/Rosenbrock\_function (да-та звернення 03.04.2018)

$2.$ Nelder J.A. A simplex method for function minimization / J.A. Nelder, R. Mead // Computer Journal. – 1965. – vol. 1, is. 7. – P. 308-313.

$3.$ Sivanandam S. N. Introduction to Genetic Algorithms / S. N. Sivanandam, S. N. Deepa. – Berlin: Springer, 2007. – С. 127.

$4.$ Kramer O. Genetic Algorithm Essentials / Oliver Kramer. – Oldenburg: Springer, 2017. – C. 50.

$5.$ https://towardsdatascience.com/how\-to\-define\-a\-fitness\-function\-in\-a\-genetic\-algorithm\-be572b9ea3b4 (дата звернення 10.04.2018

May 16, 2018