Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2021
Hauptverfasser:	Гулаєва, Н.М., Шило, В.П.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2021
Schriftenreihe:	Кібернетика та комп’ютерні технології
Schlagworte:	Методи оптимізації та екстремальні задачі
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/181346
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації / Н.М. Гулаєва, В.П. Шило, М.М. Глибовець // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 3. — С. 5-14. — Бібліогр.: 12 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-181346
record_format	dspace
spelling	irk-123456789-1813462021-11-13T01:26:05Z Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації Гулаєва, Н.М. Шило, В.П. Методи оптимізації та екстремальні задачі Мета роботи. Показати, що генетичні алгоритми, зазвичай класифіковані як метаевристичні, популяційні, імітаційні тощо, по суті є стохастичними чисельними методами прямого пошуку. Результати. Наведено варіанти постановки задачі оптимізації, дано огляд класифікацій оптимізаційних задач із зазначенням основних методів їх розв’язування. Описано суть класифікації методів оптимізації на аналітичні та чисельні та показано, що схема генетичного алгоритму може бути подана як схема чисельного методу прямого пошуку. Дано спосіб зведення заданої оптимізаційної задачі до задачі, розв’язуваної за допомогою генетичного алгоритму, та окреслено клас задач, які можуть бути розв’язані за допомогою генетичних алгоритмів. Цель работы. Показать, что генетические алгоритмы, обычно классифицируемые как метаэвристические, популяционные, имитационные и т. д., в действительности являются стохастическими численными методами прямого поиска. Результаты. Приведены варианты постановки задачи оптимизации, дан обзор классификаций оптимизационных задач с указанием основных методов их решения. Описана суть классификации методов оптимизации на аналитические и численные и показано, что схема генетического алгоритма может быть представлена как схема численного метода прямого поиска. Дан способ сведения заданной оптимизационной задачи к задаче, решаемой с помощью генетического алгоритма, и очерчен класс задач, которые могут быть решены с помощью генетических алгоритмов. The purpose is to show that genetic algorithms, usually classified as metaheuristic, population-based, simulation, etc., are inherently the stochastic numerical methods of direct search. Results. Alternative statements of optimization problem are given. An overview of existing classifications of optimization problems and basic methods to solve them is provided. The heart of optimization method classification into symbolic (analytical) and numerical ones is described. It is shown that a genetic algorithm scheme can be represented as a scheme of numerical method of direct search. A method to reduce a given optimization problem to a problem solvable by a genetic algorithm is described, and the class of problems that can be solved by genetic algorithms is outlined. 2021 Article Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації / Н.М. Гулаєва, В.П. Шило, М.М. Глибовець // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 3. — С. 5-14. — Бібліогр.: 12 назв. — укр. 2707-4501 DOI: https://doi.org/10.34229/2707-451X.21.3.1 http://dspace.nbuv.gov.ua/handle/123456789/181346 519.854:004.023 uk Кібернетика та комп’ютерні технології Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Методи оптимізації та екстремальні задачі Методи оптимізації та екстремальні задачі
spellingShingle	Методи оптимізації та екстремальні задачі Методи оптимізації та екстремальні задачі Гулаєва, Н.М. Шило, В.П. Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації Кібернетика та комп’ютерні технології
description	Мета роботи. Показати, що генетичні алгоритми, зазвичай класифіковані як метаевристичні, популяційні, імітаційні тощо, по суті є стохастичними чисельними методами прямого пошуку. Результати. Наведено варіанти постановки задачі оптимізації, дано огляд класифікацій оптимізаційних задач із зазначенням основних методів їх розв’язування. Описано суть класифікації методів оптимізації на аналітичні та чисельні та показано, що схема генетичного алгоритму може бути подана як схема чисельного методу прямого пошуку. Дано спосіб зведення заданої оптимізаційної задачі до задачі, розв’язуваної за допомогою генетичного алгоритму, та окреслено клас задач, які можуть бути розв’язані за допомогою генетичних алгоритмів.
format	Article
author	Гулаєва, Н.М. Шило, В.П.
author_facet	Гулаєва, Н.М. Шило, В.П.
author_sort	Гулаєва, Н.М.
title	Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації
title_short	Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації
title_full	Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації
title_fullStr	Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації
title_full_unstemmed	Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації
title_sort	генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2021
topic_facet	Методи оптимізації та екстремальні задачі
url	http://dspace.nbuv.gov.ua/handle/123456789/181346
citation_txt	Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації / Н.М. Гулаєва, В.П. Шило, М.М. Глибовець // Кібернетика та комп’ютерні технології: Зб. наук. пр. — 2021. — № 3. — С. 5-14. — Бібліогр.: 12 назв. — укр.
series	Кібернетика та комп’ютерні технології
work_keys_str_mv	AT gulaêvanm genetičníalgoritmiâkobčislûvalʹnímetodiskínčennovimírnoíoptimízacíí AT šilovp genetičníalgoritmiâkobčislûvalʹnímetodiskínčennovimírnoíoptimízacíí
first_indexed	2025-07-15T22:21:17Z
last_indexed	2025-07-15T22:21:17Z
_version_	1837753256903704576
fulltext	МЕТОДИ ОПТИМІЗАЦІЇ ТА ЕКСТРЕМАЛЬНІ ЗАДАЧІ ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.3 5 КІБЕРНЕТИКА та КОМП'ЮТЕРНІ ТЕХНОЛОГІЇ Дано огляд основних класів екстремальних задач та алгоритмів їх розв’язання. Окресле- но клас задач, які можуть бути розв’язані за допомогою генетичних алгоритмів, та пока- зано спосіб зведення заданої оптимізаційної задачі до задачі, розв’язуваної за допомогою генетичного алгоритму. Показано, що гене- тичні алгоритми розв’язання екстремальних задач є стохастичними чисельними метода- ми прямого пошуку. Ключові слова: задача математичного про- грамування, задача безумовної оптимізації, задача умовної оптимізації, задача багато- екстремальної оптимізації, чисельні методи, генетичні алгоритми, метаевристичні алго- ритми.   Н.М. Гулаєва, В.П. Шило, М.М. Глибовець, 2021 УДК 519.854:004.023 DOI:10.34229/2707-451X.21.3.1 Н.М. ГУЛАЄВА, В.П. ШИЛО, М.М. ГЛИБОВЕЦЬ ГЕНЕТИЧНІ АЛГОРИТМИ ЯК ОБЧИСЛЮВАЛЬНІ МЕТОДИ СКІНЧЕННОВИМІРНОЇ ОПТИМІЗАЦІЇ Постановка задачі оптимізації. В загальному випад- ку під скінченновимірною екстремальною задачею розуміють задачу відшукання точної верхньої чи нижньої межі деякої функції :f X R , де nX R . Нагадаємо основні визначення. Функція :f X R , nX R , називається обмеже- ною знизу (зверху) на множині X, якщо існує дійсне число M таке, що : ( ) ( ( ) ).x X f x M f x M    Нехай функція ( )f x – обмежена знизу на множині nX R . Тоді дійсне число f* називається точною нижньою межею функції ( )f x на X, якщо викону- ються дві умови: 1) : ( )x X f f x   ; 2) для будь-якого як завгодно малого числа 0  знайдеться точка x X така, що ( )f x f    . Якщо функція ( )f x – не обмежена знизу на X, то точна нижня межа вважається f   . Точна нижня межа f функції ( )f x на X позначається inf ( ) x X f x  . Аналогічно вводяться поняття точної верхньої межі функції ( )f x на nX R . Якщо функція ( )f x – не обмежена зверху на X, то точна верхня межа вва- жається f   . Точна верхня межа f функції ( )f x на X позначається sup ( ) x X f x  . Точка x X називається точкою локального міні- муму функції ( )f x на множині X, якщо існує число 0  таке, що ( ) : ( ) ( )x X O x f x f x    , (1) де ( )O x –  -окіл точки x . Точка x X називається точкою глобального мінімуму функції ( )f x на множині X, якщо : ( ) ( ).x X f x f x   (2) https://doi.org/10.34229/2707-451X.21.3.1 Н.М. ГУЛАЄВА, В.П. ШИЛО, М.М. ГЛИБОВЕЦЬ 6 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 3 При цьому записують: ( ) min ( ) x X f x f x   або * argmin ( ) x X x f x   . Множину всіх точок глобального мінімуму позначають так: * Argmin ( ) { \| ( ) min ( )} x Xx X f x x X f x f x     . Точка глобального мінімуму завжди є точкою локального мінімуму, але не навпаки. Якщо нерівність в (1), (2) виконується як строга за ,x x то x називається відповідно точкою строго- го локального чи строгого глобального мінімуму. Замінюючи в наведених означеннях слово «мінімум» на «максимум» і знак нерівності в (1), (2) на протилежний, отримаємо поняття точок глобального та локального максимумів, а також поняття точок строгого локального та строгого глобального максимумів. Зауважимо, що максимум і міні- мум об’єднуються єдиним терміном екстремум. Очевидно, що inf ( ) x X f x  та sup ( ) x X f x  завжди існують, в той час як min ( ) x X f x  та max ( ) x X f x  існують не завжди. Залежно від властивостей множини X та функції ( )f x множина всіх точок глобального мінімуму (максимуму) Argmin ( ) x X f x  ( Argmax ( ) x X f x  ) може бути скінченною, нескін- ченною або пустою. В загальному випадку скінченновимірну екстремальну задачу записують так: ( ) inf (sup), .nf x x X R   (3) Найбільш широко вживаними трактуваннями поняття «розв’язок» задачі (3) є такі: A) визначити точну нижню (верхню) межу inf ( ) x X f f x   ( * sup ( ) x X f f x   ); B) визначити точну нижню (верхню) межу * inf ( ) x X f f x   ( * sup ( ) x X f f x   ), якщо множина точок глобального мінімуму (максимуму) не є пустою, знайти хоча б одну точку * argmin ( ) x X x f x   ( * argmax ( ) x X x f x   ); C) визначити точну нижню (верхню) межу * inf ( ) x X f f x   ( * sup ( ) x X f f x   ), якщо множина точок глобального мінімуму (максимуму) не є пустою, знайти всі точки Argmin ( ) x X f x  ( Argmax ( ) x X f x  ); D) знайти всі точки локальних мінімумів (максимумів) та значення функції у цих точках. Часто буває відомо, що множина точок Argmin ( ) x X f x   ( Argmax ( ) x X f x   ). У цьому разі визначення екстремальної задачі та поняття розв’язку цієї задачі відрізняється. Задачу мінімізації функції ( )f x на множині X записують у вигляді ( ) min,f x x X  або min ( ) x X f x  . (4) Функція ( )f x називається цільова функція, множина X називається допустима множина, будь-який елемент x X називається допустима точка цієї множини. Якщо nX R , ГЕНЕТИЧНІ АЛГОРИТМИ ЯК ОБЧИСЛЮВАЛЬНІ МЕТОДИ СКІНЧЕННОВИМІРНОЇ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.3 7 то задача пошуку мінімуму називається задача безумовної мінімізації; якщо nX R , то задача пошуку мінімуму називається задача умовної мінімізації або задача з обмеженнями на змінні. Поняття розв’язку задачі (4) за аналогією з розв’язком задачі (3) визначають так: B’) знайти хоча б одну точку * argmin ( ) x X x f x   ; C’) знайти всі точки Argmin ( ) x X f x  ; D’) знайти всі точки локальних мінімумів та значення функції у цих точках. Зауважимо, що у варіантах C’), D’) загалом вимагається знайти не одну точку, а цілу множину точок, тому задачу (4) у варіантах C’), D’) ще називають задачею багатоекстремальної оптиміза- ції (multimodal optimization). Тут слід відмітити певну неоднозначність у термінології: у вітчизня- ній літературі часто під задачею багатоекстремальної оптимізації розуміють задачу в постановці B’) для випадку, коли цільова функція ( )f x має багато екстремумів. За аналогією з (4) задачу максимізації функції ( )f x на множині X записують у вигляді ( ) max,f x x X  або max ( ) x X f x  . (5) Очевидно, що max ( ) min( ( )) x Xx X f x f x     , отже, для задачі максимізації (5) та задачі мінімізації ( ) min,f x x X   , множини глобальних та локальних екстремумів збігаються, таким чином, задача максимізації – еквівалентна задачі мінімізації. Тому надалі розглядатимемо лише задачі мінімізації. Класифікація задач оптимізації. Класифікацію задач оптимізації проводять за такими озна- ками: тип і властивості цільової функції, способи подання та властивості допустимої множини. Залежно від класу задачі, на основі апріорної інформації про властивості задачі обирають конкрет- ний метод її розв’язання. Серед основних класів оптимізаційних задач виділимо такі. Класичну задачу на умовний екстремум: допустима множина X визначається системою рівнянь. Як правило, задачу записують у вигляді ( ) min(max)f x  , ( ) 0, 1,ig x i m  . Найпоширеніший метод розв’язання цієї задачі за умови неперервності та неперервної диференційовності функцій ( )f x , ( )ig x , 1,i m , це метод множників Лагранжа. Задачу математичного програмування: допустима множина X визначається системою нерів- ностей та рівнянь. Цю задачу записують у вигляді ( ) min(max)f x  , ( ) 0, 1,ig x i k  , ( ) 0, 1,ig x i k m   , ( ) 0, 1,ig x i m s   , nx P R  . Залежно від властивостей функцій ( )f x , ( )ig x серед задач математичного програмування виділяють такі класи задач. Задачу лінійного програмування: функції ( )f x , ( )ig x , 1,i s – лінійні. Основний метод розв’язування задач цього класу – симплекс-метод. Задачу нелінійного програмування: функції ( )f x та/або ( )ig x – нелінійні. Серед цих задач найбільш добре вивченими є задачі опуклого програмування. Залежно від диференційованості цільової функції розглядають задачі диференційованої або гладкої оптимізації, задачі недиферен- ційованої або негладкої оптимізації. Для розв’язування задач негладкої опуклої оптимізації використовують, наприклад, субградієнтні і ε-субградієнтні методи, метод проекції субградієнта Н.М. ГУЛАЄВА, В.П. ШИЛО, М.М. ГЛИБОВЕЦЬ 8 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 3 тощо. Серед задач опуклого програмування виділяють задачі квадратичного програмування та задачі сепарабельного програмування. Важливе місце серед прикладних задач математичного програмування посідають задачі дис- кретної оптимізації. В цих задачах допустима множина nX R – дискретна. Якщо всі невідомі змінні можуть набувати лише цілочислових значень, nX Z , йде мова про задачу цілочислового програмування. Умова цілочисельності обумовлена, перш за все, практичною природою задач, адже в умовах реальності багато ресурсів може набувати лише цілих значень (верстати, машини, рулони тощо). Якщо {0,1}nX  , йде мова про задачу булевої оптимізації, при цьому, у разі ( )f x R , говорять про псевдобулеву оптимізацію. В задачах комбінаторної оптимізації значення цільової функції залежать від певної комбінації об’єктів зі скінченного набору, їх розміщення або способу упорядкування. Незважаючи на поширеність задач комбінаторної оптимізації, формальне визначення цього класу задач запропоновано нещодавно в [1]. Серед методів розв’язання задач дискретного програмування виділимо метод відтинання, метод гілок і меж, метод динамічного програмування, послідовний аналіз варіантів («київський віник»). Ґрунтовний огляд сучасного стану та методів розв’язання задач дискретної оптимізації дано в [1–3]. Існують також інші класи задач оптимізації: параметричні, детерміновані, стохастичні, нечіткі та інші. Бібліографію методів розв’язання різних класів задач математичного програмуван- ня можна знайти в [4]. Класифікація методів розв’язання задач оптимізації. Методи розв’язання задач оптимізації класифікують за різними характеристиками. Один з найпоширеніших це поділ методів оптимізації на такі: 1) аналітичні, які ґрунтуються на використанні умов екстремуму; 2) методи обчислювальної оптимізації (чисельні методи), в яких для організації процесу пошуку розв’язку проводять вимірювання (обчислення) значень локальних характеристик цільових функцій та функцій обмежень (тобто значень функцій, градієнтів, гессіанів). Аналітичні методи не завжди застосовні на практиці, оскільки вимоги, що накладаються на цільову функцію та функції-обмеження (аналітичний вид функції, кускова гладкість, можливість обчислення похідної та ін.) на практиці виконуються дуже рідко. Прикладами аналітичних методів є методи Лагранжа, Куна – Таккера. Чисельний метод у загальному випадку є ітераційною процедурою, яка в точках пошукового простору здійснює обчислення певних характеристик функції (значення функції, її градієнта, гессіана). Залежно від того, які саме характеристики функцій обчислюються, чисельні методи по- діляють на методи прямого пошуку, першого порядку (градієнтні), другого порядку. Слідуючи [5], називатимемо операцію обчислення характеристик функції у точці пошуковим випробуванням, а сукупність значень характеристик у цій точці – результатом випробування або пошуковою інфо- рмацією. В методах прямого пошуку в точках пошукового простору обчислюють тільки значення цільової функції, тобто результатом випробування є значення цільової функції у точці випробу- вання. За [5], прямий чисельний метод c розв’язання оптимізаційної задачі (4) з класу Φ можна подати набором { },{ },{ }k k kc G E H , (6) де { kG }, k = 1,2,… – сім’я функціоналів, яка описує сукупність правил вибору точок випробувань, { kE }, k = 1,2,… – послідовність відображень, яка задає сукупність правил побудови наближеного розв’язку, { kH }, k = 1,2,… – сукупність правил зупинки обчислювального процесу. Загальна схема прямого чисельного методу така. ГЕНЕТИЧНІ АЛГОРИТМИ ЯК ОБЧИСЛЮВАЛЬНІ МЕТОДИ СКІНЧЕННОВИМІРНОЇ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.3 9 1. Обрати точку першого випробування: 1 1( )x G X   . 2. Нехай обрано точку k-го випробування ( )k kx G X   , 1k  . Після обчислення значення цільової функції у цій точці ( )k ky f x , отримаємо пошукову (апостеріорну) інформацію про функцію f: 1 1 2 2{( , ),( , ),...,( , )}.k k k x y x y x y  Отримана інформація дозволяє звузити клас Φ, до якого належить функція f(x), до множини ( ) { : ( ) ,1 }i i k x y i k        . 3. Визначити поточну оцінку екстремуму (наближений розв’язок): ( , )k k ke E   . 4. Обчислити точку наступного випробування: 1 1( , )k k kx G X     . 5. Визначити величину ( , ) {0,1}k k kh H    . Якщо 1kh  , то збільшити номер кроку k на одиницю та перейти на п. 2. Інакше ( 0kh  ) зупинити обчислення. Розв’язок задачі має оцінку ke . Наприклад [5], метод перебору значень по вузлах рівномірної сітки для розв’язування одно- вимірної задачі мінімізації ( ) min, [ , ]f x x a b R   , можна описати так (n – кількість вузлів сітки): Φ – клас функцій, визначених на відрізку [a, b] та обчислюваних у кожній точці цього відрізку, 1( )G a  , 1 1 ( , )k k b G a k n       , 1,k  0, 1 ( , ) 1, 1 k k k n H k n            , * 1 ( , ) min ( )i k k k i k E f f x       . Генетичні алгоритми як чисельні методи оптимізації. Генетичні алгоритми, в основу яких покладено ідею еволюції живої природи, широко використовуються для розв’язання різноманітних задач оптимізації. Генетичні алгоритми не вимагають аналітичного завдання цільової функції та не накладають жодних обмежень на її властивості (неперервність, диференційовність та ін.), єдиним обмеженням, що накладається на цільову функцію, є обчислюваність у кожній точці пошукового простору. Серед основних властивостей генетичних алгоритмів зазначимо такі [6]: понятійний апарат запозичений з біології, кожен допустимий розв’язок задачі кодується у вигляді хромосоми та представляється особиною популяції, для оцінювання якості розв’язку обчислюють його коефі- цієнт пристосованості (за допомогою функції пристосованості), пошук розв’язків здійснюється одночасно цілою популяцією особин, причому для генерації нового розв’язку використовують аналоги природних генетичних операторів. В загальному випадку генетичні алгоритми не можуть бути застосовними до задач, для яких множина Argmin ( ) x X f x   , отже, генетичні алго- ритми застосовні лише до задач в постановці B’), C’), D’). Розглянемо задачу безумовної оптимізації ( ) min, .nf x x X R   (7) Для розв’язування задачі (7) за допомогою генетичного алгоритму необхідно визначити: 1) відображення (бієктивне) : X S  , яке зіставляє кожному допустимому розв’язку задачі nx X R  код s S ; очевидно, обернене відображення 1 : S X  за кодом s S відновлюва- тиме розв’язок x X . Множина S може збігатись з множиною X або бути визначеною, напри- клад, як множина послідовностей довжини n елементів певної множини; 2) функцію пристосованості ( ),F s s S , яка має задовольняти таким вимогам [6]: Н.М. ГУЛАЄВА, В.П. ШИЛО, М.М. ГЛИБОВЕЦЬ 10 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 3 - адекватність задачі: 1 1 1 2 1 1 2 2, , ( ), ( )s s x s x s      виконується 1 2( ) ( )F s F s  1 2( ) ( )f x f x  , де 1 2,s s – закодовані значення розв’язків 1 2,x x , F – функція пристосованості, f – цільова функція оптимізаційної задачі; - маловитратність (невисока складність обчислення); - різноманітний рельєф. Часто покладають ( ) ( )F s f x , де s – хромосома, що кодує значення розв’язку x ( ( )s x ). Розв’язування задачі (7) зводиться до розв’язування за допомогою генетичного алгоритму задачі ( ) min, .F s s S  (8) Якщо s – розв’язок задачі (8), то розв’язком задачі (7) буде 1 ( )x s  . Генетичні алгоритми природно розглядати як чисельні методи прямого пошуку. Розглянемо, наприклад, генетичний алгоритм турнірного витиснення з гауссовою мутацією, запропонований в [7] для розв’язування задач (4), (5) в постановці D’), 1 2 ... nX X X X    , [ , ] 1,i i iX a b R i n    . Схему цього алгоритму для розв’язання задач в постановці B’) можна подати так. 1. Кодування в дійсних числах ( S X ): кожен ген хромосоми 1 2( , ,..., ) n nx x x x R  – дійсна змінна [ , ] .i i ix a b R  2. Генерація початкової популяції за рівномірним розподілом. 3. Обчислення коефіцієнта пристосованості всіх особин популяції, функція пристосованості збігається з цільовою функцією. 4. Породження L нащадків кожною особиною шляхом застосування оператора гауссової му- тації до кожного гена хромосоми: (0, )i i ix x N   , де (0, )iN  – стандартна нормально розподіле- на випадкова величина. 5. Обчислення коефіцієнта пристосованості отриманих нащадків. 6. Формування нової популяції за допомогою турнірного відбору, група для кожного турніру формується з батька та усіх його нащадків. 7. Якщо кількість ітерацій дорівнює G, завершення роботи алгоритму (розв’язком задачі є найкраща особина популяції), інакше перехід на крок 4. Наведений алгоритм можна подати як паралельне виконання N екземплярів алгоритмів, кожен з яких описується схемою прямого чисельного методу c (6): Φ – клас функцій, визначених на nR та обчислюваних у кожній точці, 1( )G   , де ξ – послідовність випадкових дійсних чисел,  1 1 1, , 1,2,..., ( , ) argmin ( ), min { ( (0, ),..., (0, ))}k k k k k k k i n n i i L G f x f x N x N         , 1k  , 0, ( , ) 1, k k k G H k G          , , 1 ( , ) min ( )k l k k k l N E f f x       , де ,k lx – точка випробування l-го алгоритму на k-ій ітерації. Генетичний алгоритм турнірного витиснення з гауссовою мутацією легко транслюється у схе- му прямого чисельного методу завдяки таким особливостям: кодування у дійсних числах (кожен параметр задачі задається відповідним геном хромосоми), відсутність оператора кросинговеру, локальний відбір особин у наступну популяцію (проводять турнірні змагання між батьками та їх власними нащадками). В загальному випадку S X , для породження нащадків використовується не лише оператор мутації, але й кросинговер, для реалізації відбору слід урахувати інформацію ГЕНЕТИЧНІ АЛГОРИТМИ ЯК ОБЧИСЛЮВАЛЬНІ МЕТОДИ СКІНЧЕННОВИМІРНОЇ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.3 11 про всіх особин популяції. Тому для подання довільного генетичного алгоритму як прямого чисе- льного методу наведена схема прямого чисельного методу c (6) вимагає певних модифікацій. При проведенні модифікації схеми важливо також урахувати паралелізм генетичних алгоритмів, адже в генетичних алгоритмах пошук розв’язків здійснюється одночасно популяцією особин. Іншими словами, на кожній ітерації роботи генетичного алгоритму аналізується множина точок пошуково- го простору, кількість таких точок дорівнює розміру популяції та є сталою. Отже, для представ- лення довільного генетичного алгоритму розв’язування задачі (8) як чисельного методу необхідно, щоб у схемі прямого чисельного методу c (6) на кожному кроці розглядалась не одна, а N точок випробування. Пропоновану модифікацію схеми c подано далі. 1. Обрати множину точок першого випробування (в термінах генетичного алгоритму: згене- рувати початкову популяцію): 1 1 1 1 2, ,..., Ns s s  , 1 1( )i is G    , де i – випадкова величина (залеж- но від множини S це може бути випадкове дійсне число, послідовність довжини n випадкових дійсних чисел, випадкова двійкова послідовність довжини n та ін.). 2. Нехай обрано множину точок k-го випробування 1 2, ,...,k k k Ns s s  , 1k  . Після обчислення значення функції пристосованості в кожній з цих точок ( )k k i iy F s отримаємо пошукову (апосте- ріорну) інформацію про функцію F: 1 1 2 2{( , ), ( , ),..., ( , )}k k k k k k k N Ns y s y s y  . Звернемо увагу, що апостеріорна інформація про функцію F містить тільки інформацію, отриману на поточному кроці роботи алгоритму (на відміну від оригінальної схеми c, в якій запам’ятовується вся інформація, отримана від початку роботи алгоритму). 3. Визначити поточну оцінку екстремуму: 1 ( , ) min k k k k i i N e E y       . 4. Для обчислення множини точок наступних випробувань до поточної множини точок 1 2, ,...,k k k Ns s s  застосувати послідовність операторів: відбір до батьківського пулу 1 2 1 1 2, ,..., ( , ,..., , ),k k k SEL k k k N k N kp p p G s s s     кросинговер 1 2 1 1 2, ,..., ( , ,..., ),k k k CROS k k k N k Nc c c G p p p    мутація 1 1 1 1 2, ,...,k k k Ns s s    = 1 1 2( , ,..., )MUT k k k k NG c c c   . Іншими словами, 1( , )k kG    – послідовність спеціальних генетичних операторів. Відбір відкидає деякі «невдалі» розв’язки, та, натомість, дуб- лює «вдалі». Кросинговер здійснює обмін частинами розв’язків, а мутація фактично – локальне перетворення розв’язку (збурення). 5. Визначити величину ( , ) {0,1}k k kh H    . Якщо 1,kh  то збільшити номер кроку k на одиницю та перейти на п. 2. Інакше ( 0)kh  зупинити обчислення. Розв’язок задачі має оцінку ke . В більшості генетичних алгоритмів ( , ) 0k kH    , якщо ,k G де G – максимальна кількість ітерацій (поколінь), або ідентифіковано збіжність генетичного алгоритму, наприклад, 1 N k k i i e y N     . Наведена схема – загальна та потребує уточнень залежно від обраного класу генетичного ал- горитму (нові класи генетичних алгоритмів будують шляхом уточнення генетичних операторів). Також, схема описує генетичні алгоритми з генераційним типом репродукції, опис алгоритмів зі стійким типом репродукції вимагає незначної модифікації. Підсумовуючи сказане та враховую- чи стохастичність операторів 1 SEL kG  , 1 CROS kG  , 1 MUT kG  , можна говорити про генетичні алгоритми як про стохастичні чисельні методи прямого пошуку. Н.М. ГУЛАЄВА, В.П. ШИЛО, М.М. ГЛИБОВЕЦЬ 12 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 3 Генетичні алгоритми в задачах умовної оптимізації. Досі ми обговорювали генетичні алго- ритми розв’язання задач безумовної оптимізації (7). В задачах умовної оптимізації допустима множина nX R . Загальні методи урахування обмежень у задачах математичного програмування детально описані, наприклад, в [5]: методи штрафних функцій, множників Лагранжа, параметриза- ції цільової функції та ін. Для врахування обмежень на допустимі розв’язки в генетичних алго- ритмах застосовують такі підходи: 1) вибір такого способу кодування, за якого всі значення з множини S декодуються в допусти- мі точки: s S  : 1( ) nx s X R    . Зазначимо, що на практиці розробити такий спосіб кодуван- ня не завжди вдається; 2) розробка спеціальних генетичних операторів (кросинговер, мутація), застосування яких гарантує породження допустимих розв’язків. Тобто, після застосування генетичного оператора породжений ним розв’язок буде допустимим (нова точка випробування задовольняє обмеженням на розв’язок); 3) застосування модифікації широко використовуваного в інших чисельних методах оптиміза- ції методу штрафних функцій. В цьому разі цільова функція задачі (8) замінюється функцією ( ) ( ) ( ),pF s F s P s s S    . Тут ( )pF s – нова цільова функція, 1 1 0, ( ) ( ) 0, ( ) x s X P s x s X             – функція штрафу,  – коефіцієнт штрафу. Така заміна цільової функції дозволяє погіршити оцінку якості розв’язку (оцінку точки випробування), в якому порушуються задані умовою обмеження. Відмінність методу штрафних функцій у генетичних алгоритмах полягає у тому, що значення коефіцієнтів штрафу  підби- раються експертним або експериментальним шляхом і способи підбору цих коефіцієнтів чітко не регламентуються. Нескладно бачити, що всі зазначені підходи не потребують додаткових змін пропонованої вище схеми подання генетичного алгоритму як чисельного методу прямого пошуку. Висновки. З огляду на велику кількість різноманітних методів оптимізації науковці все біль- ше уваги приділяють класифікації та систематизації цих методів. Питанню класифікації методів оптимізації присвячено роботи [3, 8–10]. Розглянута нами класифікація методів оптимізації на аналітичні та чисельні аналізує тип задіяних обчислень, тому проста й зрозуміла, але далеко не єдина. Інша популярна класифікація методів оптимізації є класифікація за типом отримуваного розв’язку, в цьому разі алгоритми поділяють на точні (за скінченний час гарантовано повертають оптимальний розв’язок або дають висновок, що розв’язку не існує), наближені (за скінченний час гарантовано повертають розв’язок, для якого може бути отримана асимптотична оцінка точності), евристичні (відсутня оцінка точності отриманого розв’язку та навіть гарантія отримання будь-якого розв’язку за скінченний час). За ступенем математичного обґрунтування алгоритми поділяють на раціональні та евристичні, за принципом прийняття рішень – на детермі- новані та стохастичні, за складністю структури – на прості, метаевристичні, гіперевристичні тощо. Часто дослідники як окремий клас розглядають алгоритми, породжені ідеєю імітації природних явищ (різноманітні роєві та еволюційні алгоритми). Хоча ідея виділення в окремий клас алгорит- мів, на створення яких авторів надихнуло спостереження за навколишнім середовищем, може здатись цілком природною, така класифікація не розкриває принципів роботи самих алгоритмів, їхньої суті. В роботі [3] пропонується проводити класифікацію методів комбінаторної оптимізації за вісьмома характеристиками: принцип прийняття розв’язку, складність структури, тип траєкторії, що формується алгоритмом, тип використовуваних просторів, вплив на ландшафт пошуку, викори- стання пам’яті, наявність адаптації/навчання, наявність спеціальної моделі задачі. Ця класифікація ГЕНЕТИЧНІ АЛГОРИТМИ ЯК ОБЧИСЛЮВАЛЬНІ МЕТОДИ СКІНЧЕННОВИМІРНОЇ ... ISSN 2707-4501. Cybernetics and Computer Technologies. 2021, No.3 13 є ґрунтовною, але породжує надвелику кількість різних класів та підкласів. Так, за цією класифі- кацією генетичні алгоритми є стохастичними метаевристичними траєкторно-розривними ітерацій- ними (популяційними) алгоритмами без зміни ландшафту пошуку, без пам’яті, в загальному випа- дку без адаптації, завдання-орієнтованими. Все сказане наштовхує на думку, що наразі стан теорії методів розв’язання оптимізаційних задач нагадує стан теорії штучних нейронних мереж кілька років тому: кількість розроблених методів оптимізації є надзвичайно великою та постійно зростає, причому досить поширеною є практика надання нових назв раніше відомим поняттям або незначним модифікаціям раніше розроблених методів без посилання на відповідні роботи. Такий стан справ пояснюється надзвичайною розгалуженістю різних напрямів досліджень і вузькою спеціалізацією дослідників. Особливо проблемним є напрям розробки метаевристичних алгоритмів, де в гонитві за науковою новизною автори створюють все нові алгоритми, не даючи їхнього математичного обґрунтування або більш-менш вичерпного експериментального аналізу і порівняння з вже існуючими алгорит- мами. Про необхідність виправлення ситуації вже звітують деякі науковці [10]. Підсумовуючи сказане, констатуємо необхідність перегляду та переосмислення історії виник- нення, розробки й модифікацій різних методів оптимізації для узагальнення і систематизації цих методів. В теорії штучних нейронних мереж такою роботою автори вважають роботу [11], в якій дано не просто огляд історії розвитку штучних нейронних мереж, але й аналіз історії основних ідей глибокого навчання, відстеження розвитку конкретних структур та алгоритмів. Автори споді- ваються, що наведене представлення генетичного алгоритму (метаевристичного, популяційного, породженого ідеєю імітації природних явищ тощо) як чисельного методу прямого пошуку може стати першим кроком на цьому шляху. Список літератури 1. Hulianytskyi L., Riasna I. Formalization and classification of combinatorial optimization problems. In honor of Ivan V. Sergienko's 80th birthday. Optimization Methods and Applications / Butenko S., Pardalos P., Shylo V. (eds). Cham : Springer, 2017. Vol. 130. P. 239–250. https://doi.org/10.1007/978-3-319-68640-0_11 2. Сергиенко И.В., Шило В.П. Проблемы дискретной оптимизации: сложные задачи, основные подходы к их ре- шению. Кибернетика и системный анализ. 2006. Т. 42, № 4. С. 3–25. https://doi.org/10.1007/s10559-006-0086-3 3. Сергиенко И.В., Гуляницкий Л.Ф., Сиренко С.И. Классификация прикладных методов комбинаторной оптими- зации. Кибернетика и системный анализ. 2009. Т. 45, № 5. С. 71–83. https://doi.org/10.1007/s10559-009-9134-0 4. Жалдак М.І., Триус Ю.В. Основи теорії і методів оптимізації : навчальний посібник. Черкаси : Брама-Україна, 2005. 608 с. 5. Городецкий С.Ю., Гришагин В.А. Нелинейное программирование и многоэкстремальная оптимизация: учеб- ное пособие. Нижний Новгород : Изд-во Нижегородского гос. ун-та, 2007. 489 с. 6. Глибовець М.М., Гулаєва Н.М. Еволюційні алгоритми : підручник. Київ : НаУКМА, 2013. 828 с. 7. Шило В.П., Глибовець М.М., Гулаєва Н.М., Нікіщіхіна К.В. Генетичні алгоритми турнірного витиснення з гауссовою мутацією. Кибернетика и системный анализ. 2020. Т. 56, № 2. С. 75–88. https://doi.org/10.1007/s10559-020-00239-4 8. Birattari M., Paquete L., Stützle T., Varrentrapp K. Classification of metaheuristics and design of experiments for the analysis of components: technical report. Darmstadt : Techn. Univ. Darmstadt, 2001. AIDA-01-05. 12 p. 9. Певнева А.Г. Построение классификации методов глобальной оптимизации. Международный научно- исследовательский журнал. 2012. № 3. С. 14–23. 10. Sörensen K. Metaheuristics – the metaphor exposed. International Transactions in Operational Research. 2015. Vol. 22, N 1. P. 3–18. https://doi.org/10.1111/itor.12001 11. Schmidhuber J. Deep learning in neural networks: an overview. Neural Networks. 2015. Vol. 61. P. 85–117. https://doi.org/10.1016/j.neunet.2014.09.003. 12. Эйлер Л. Об упругих кривых. Метод нахождения кривых линий, обладающих свойствами максимума, либо минимума или решение изопериметрической задачи, взятой в самом широком смысле / ред. Н.С. Кошляков. М. – Л.: ГТТИ, 1934. С. 447–572. (Серия «Классики естествознания»). Одержано 02.07.2021 https://doi.org/10.1007/978-3-319-68640-0_11 https://doi.org/10.1007/s10559-006-0086-3 https://doi.org/10.1007/s10559-009-9134-0 https://doi.org/10.1007/s10559-020-00239-4 https://doi.org/10.1111/itor.12001 https://doi.org/10.1016/j.neunet.2014.09.003 Н.М. ГУЛАЄВА, В.П. ШИЛО, М.М. ГЛИБОВЕЦЬ 14 ISSN 2707-4501. Кібернетика та комп'ютерні технології. 2021, № 3 Гулаєва Наталія Михайлівна, кандидат фізико-математичних наук, доцент кафедри інформатики факультету інформатики Національного університету «Києво-Могилянська Академія», Київ, https://orcid.org/0000-0003-4588-0702 ngulayeva@yahoo.com Шило Володимир Петрович, доктор фізико-математичних наук, професор, провідний науковий співробітник Інституту кібернетики імені В.М. Глушкова НАН України, Київ, v.shylo@gmail.com Глибовець Микола Миколайович, доктор фізико-математичних наук, професор кафедри інформатики факультету інформатики Національного університету «Києво-Могилянська Академія», Київ. https://orcid.org/0000-0002-3853-2171 glib@ukma.edu.ua MSC 65K05, 68W50 Nataliya Gulayeva 1 , Volodymyr Shylo 2, Mykola Glybovets 1 Genetic Algorithms as Computational Methods for Finite-Dimensional Optimization 1 National University of Kyiv-Mohyla Academy 2 V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv Correspondence: ngulayeva@yahoo.com Introduction. As early as 1744, the great Leonhard Euler noted that nothing at all took place in the universe in which some rule of maximum or minimum did not appear [12]. Great many today’s scientific and engineering problems faced by humankind are of optimization nature. There exist many different methods developed to solve optimization problems, the number of these methods is estimated to be in the hundreds and continues to grow. A number of approaches to classify optimization methods based on various criteria (e.g. the type of optimization strategy or the type of solution obtained) are proposed, narrower classifications of meth- ods solving specific types of optimization problems (e.g. combinatorial optimization problems or nonlinear programming problems) are also in use. Total number of known optimization method classes amounts to several hundreds. At the same time, methods falling into classes far from each other may often have many common properties and can be reduced to each other by rethinking certain characteristics. In view of the above, the pressing task of the modern science is to develop a general approach to classify optimization methods based on the disclosure of the involved search strategy basic principles, and to systematize existing optimization methods. The purpose is to show that genetic algorithms, usually classified as metaheuristic, population-based, simulation, etc., are inherently the stochastic numerical methods of direct search. Results. Alternative statements of optimization problem are given. An overview of existing classifications of optimization problems and basic methods to solve them is provided. The heart of optimization method clas- sification into symbolic (analytical) and numerical ones is described. It is shown that a genetic algorithm scheme can be represented as a scheme of numerical method of direct search. A method to reduce a given optimization problem to a problem solvable by a genetic algorithm is described, and the class of problems that can be solved by genetic algorithms is outlined. Conclusions. Taking into account the existence of a great number of methods solving optimization prob- lems and approaches to classify them it is necessary to work out a unified approach for optimization method classification and systematization. Reducing the class of genetic algorithms to numerical methods of direct search is the first step in this direction. Keywords: mathematical programming problem, unconstrained optimization problem, constrained opti- mization problem, multimodal optimization problem, numerical methods, genetic algorithms, metaheuristic algorithms. https://orcid.org/0000-0003-4588-0702 mailto:ngulayeva@yahoo.com mailto:v.shylo@gmail.com https://orcid.org/0000-0002-3853-2171 mailto:glib@ukma.edu.ua mailto:ngulayeva@yahoo.com

Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації

Institution

Ähnliche Einträge