2021, випуск 3, c. 5-14
Одержано 02.07.2021; Виправлено 23.07.2021; Прийнято 28.09.2021
Надруковано 30.09.2021; Вперше Online 25.10.2021
https://doi.org/10.34229/2707-451X.21.3.1
Попередня | Повний текст | Наступна
Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації
Н.М.
Гулаєва 1 * 
,
В.П. Шило 2, М.М. Глибовець 1
1 Національний університет «Києво-Могилянська Академія»
2 Інститут кібернетики імені В.М. Глушкова НАН України, Київ
* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.
Вступ. Ще в 1744 р. великий Леонард Ейлер зазначав, що в світі не відбувається нічого, в чому не було б видно сенс якогось максимуму або мінімуму [12]. І сьогодні практично усі наукові та технічні задачі, що стоять перед людством, мають оптимізаційний характер. Для розв’язання оптимізаційних задач розроблено багато різних методів, кількість цих методів постійно зростає і вже налічує сотні. Проводять класифікації методів оптимізації за різними ознаками (наприклад, тип оптимізаційної стратегії, тип отримуваного розв’язку), також існують вужчі класифікації методів розв’язання окремих класів оптимізаційних задач (наприклад, задач комбінаторної оптимізації, задач нелінійного програмування). Загальна кількість пропонованих класів методів оптимізації налічує кілька сотень. Водночас методи, що потрапляють до далеких один від одного класів, часто мають багато спільних властивостей та навіть можуть бути зведені один до одного шляхом переосмислення певних характеристик. Ураховуючи сказане нагальною задачею сучасної науки є розроблення спільного підходу до класифікації методів розв’язання задач оптимізації, заснованого на розкритті базових принципів задіяних пошукових стратегій, та проведення систематизації існуючих методів.
Мета роботи. Показати, що генетичні алгоритми, зазвичай класифіковані як метаевристичні, популяційні, імітаційні тощо, по суті є стохастичними чисельними методами прямого пошуку.
Результати. Наведено варіанти постановки задачі оптимізації, дано огляд класифікацій оптимізаційних задач із зазначенням основних методів їх розв’язування. Описано суть класифікації методів оптимізації на аналітичні та чисельні та показано, що схема генетичного алгоритму може бути подана як схема чисельного методу прямого пошуку. Дано спосіб зведення заданої оптимізаційної задачі до задачі, розв’язуваної за допомогою генетичного алгоритму, та окреслено клас задач, які можуть бути розв’язані за допомогою генетичних алгоритмів.
Висновки. За існування величезної кількості методів розв’язання оптимізаційних задач та способів їх класифікації необхідно розробити єдиний підхід до класифікації та систематизації існуючих методів. Зведення класу генетичних алгоритмів до чисельних методів прямого пошуку є першим кроком у цьому напрямі.
Ключові слова: Задача математичного програмування, задача безумовної оптимізації, задача умовної оптимізації, задача багатоекстремальної оптимізації, чисельні методи, генетичні алгоритми, метаевристичні алгоритми.
Цитувати так: Гулаєва Н.М., Шило В.П., Глибовець М.М. Генетичні алгоритми як обчислювальні методи скінченновимірної оптимізації. Cybernetics and Computer Technologies. 2021. 3. С. 5–14. https://doi.org/10.34229/2707-451X.21.3.1
Список літератури
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. (Серия «Классики естествознания»)/
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Попередня | Повний текст | Наступна