Evolutionary Programming

Evolutionary Programming

Prombles in programming 2013; 4: 3-13

Gespeichert in:
Bibliographische Detailangaben
Datum:2025
Hauptverfasser: Glybovets, M.M., Gulayeva, N.M.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: PROBLEMS IN PROGRAMMING 2025
Schlagworte:
Online Zugang:https://pp.isofts.kiev.ua/index.php/ojs1/article/view/737
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Problems in programming
Завантажити файл: Pdf

Institution

Problems in programming
id pp_isofts_kiev_ua-article-737
record_format ojs
resource_txt_mv ppisoftskievua/e2/f2406fdc79a70c0437e73c33b1a7fee2.pdf
spelling pp_isofts_kiev_ua-article-7372025-04-16T13:52:57Z Evolutionary Programming Еволюційне програмування Glybovets, M.M. Gulayeva, N.M. УДК 004.4 Prombles in programming 2013; 4: 3-13 Проведено комплексний аналіз стану царини практичного застосування сучасного еволюційного програмування, а також визначення світових тенденцій і перспектив розвитку еволюційних технологій.Prombles in programming 2013; 4: 3-13 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-04-16 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/737 PROBLEMS IN PROGRAMMING; No 4 (2013); 3-13 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2013); 3-13 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2013); 3-13 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/737/789 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution Problems in programming
baseUrl_str https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date 2025-04-16T13:52:57Z
collection OJS
language Ukrainian
topic

spellingShingle

Glybovets, M.M.
Gulayeva, N.M.
Evolutionary Programming
topic_facet


УДК 004.4
format Article
author Glybovets, M.M.
Gulayeva, N.M.
author_facet Glybovets, M.M.
Gulayeva, N.M.
author_sort Glybovets, M.M.
title Evolutionary Programming
title_short Evolutionary Programming
title_full Evolutionary Programming
title_fullStr Evolutionary Programming
title_full_unstemmed Evolutionary Programming
title_sort evolutionary programming
title_alt Еволюційне програмування
description Prombles in programming 2013; 4: 3-13
publisher PROBLEMS IN PROGRAMMING
publishDate 2025
url https://pp.isofts.kiev.ua/index.php/ojs1/article/view/737
work_keys_str_mv AT glybovetsmm evolutionaryprogramming
AT gulayevanm evolutionaryprogramming
AT glybovetsmm evolûcíjneprogramuvannâ
AT gulayevanm evolûcíjneprogramuvannâ
first_indexed 2025-07-17T10:03:25Z
last_indexed 2025-07-17T10:03:25Z
_version_ 1850410824363933696
fulltext Теоретичні та методологічні основи програмування © М.М. Глибовець, Н.М. Гулаєва, 2013 ISSN 1727-4907. Проблеми програмування. 2013. № 4 3 УДК 004.4 М.М. Глибовець, Н.М. Гулаєва ЕВОЛЮЦІЙНЕ ПРОГРАМУВАННЯ Проведено комплексний аналіз стану царини практичного застосування сучасного еволюційного про- грамування, а також визначення світових тенденцій і перспектив розвитку еволюційних технологій. Вступ Природа завжди вражала своєю складністю і водночас невипадковою взає- мопов’язаністю. Зовсім не дивує той факт, що дослідники математичних та комп’ю- терних задач у пошуках натхнення зверну- лися до теорії еволюції. Можливість функ- ціонування обчислювальної системи з про- стими механізмами мінливості та відбору по аналогії з законами еволюції у природ- них системах була досить привабливою. На відміну від природного процесу, обчи- слювальна система на основі еволюційно- го алгоритму, як правило, створена для отримання можливого і прийнятного розв’язку деякої конкретної задачі (або не- одноразового отримання таких розв’язків) за скінченний проміжок часу. Еволюційну метафору можна засто- совувати для оптимізаційних задач чи за- дач пошуку у будь-якій галузі, за умови, що можливі розв’язки задачі можна де- яким чином закодувати у рядок символів, коректно визначити оператори вибірки, мутації та схрещування для таких рядків і описати деяку функцію, що оцінюватиме життєздатність такого розв’язку за вико- нання умов задачі. Оператор схрещування вносить у закодований рядок суттєві змі- ни, забезпечуючи пошук на всій множині можливих розв’язків, а оператор мутації потроху «налаштовує» оптимальніший розв’язок. Дослідження даної теми є безпереч- но актуальним, адже розробка, аналіз та за- стосування ефективних і універсальних методів розв’язку задач (алгоритмів) – це ключова задача комп’ютерних наук, а тема еволюційних алгоритмів ще не достатньо досліджена. Еволюційні алгоритми нада- ють можливість швидкої генерації прий- нятних розв’язків задач, які неможливо розв’язати іншими аналітичними метода- ми, уникаючи повного перебору і значно скорочуючи часові витрати. Метою цього дослідження є комп- лексний розгляд стану царини практич- ного застосування сучасного еволюційного програмування, а також визначення світо- вих тенденцій і перспектив розвитку ево- люційних технологій. Ми вважаємо, що особливу увагу слід приділити новим, не- ординарним сферам застосування еволю- ційних алгоритмів, оскільки вони вказують на перспективність цього напрямку. 1. Еволюційне програмування Історія еволюційних обчислень по- чинається з розробки різних незалежних моделей. Еволюційне програмування (ЕП) ви- найдене Лоуренсом Фогелем у 1960 – 1965 роках під час роботи над звітом перед Конгресом Сполучених Штатів «Стан га- лузі штучного інтелекту і можливості інве- стування в неї». Основними підходами у цій галузі на той час були моделювання роботи мозку (нейронні мережі) та моде- лювання розв’язання задач експертами. Фогель помітив можливість ще одного, альтернативного підходу до проблем шту- чного інтелекту – не моделювання кінце- вого результату еволюції, а моделювання самого процесу еволюції як засобу випра- цювання розумної поведінки і можливос- тей передбачення явищ у середовищі. Л. Фогель виконав низку експери- ментів, у яких скінченні автомати предста- вляли собою особин у популяції вирішува- чів задачі. Ці скінченні автомати передба- чали символи у цифрових послідовностях, які, еволюціонуючи, ставали все придат- нішими до розв’язання поставленої задачі. Теоретичні та методологічні основи програмування 4 Саме тоді за досліджуваною цариною за- кріпилася назва «еволюційне програму- вання». Популяція скінченних автоматів, потрапивши до експериментального сере- довища, отримує певну послідовність сим- волів. Для кожного автомата-батька вико- нується процедура зіставлення кожного наступного символу з відповідним про- гнозованим символом із виходу автомата та оцінюється значення функції втрат для цього виходу. Закінчивши прогнозу- вання, визначається «життєздатність» та- кого автомату (програми). Автомати- нащадки утворюються випадковою мута- цією автоматів-батьків і теж оцінюються. Найкращі автомати відбираються до на- ступного покоління, і процес повторюєть- ся. За потреби прогнозування нових сим- волів використовують найкращий на цей час автомат, а нове спостереження дода- ється до старих [1]. Тому можна сказати, що ЕП, на ві- дміну від генетичних алгоритмів, моделює еволюцію більш як процес пристосу- вальної поведінки особин популяції або виду, аніж процес адаптації генів. Еволюційні стратегії у багатьох аспектах подібні і до генетичних алго- ритмів, і до еволюційного програмування, бо теж імітують процеси природної еволю- ції. Однак, вони мають суттєву відмінність на прикладному рівні. Водночас генетичні алгоритми просто створені для оптимізації дискретних або цілочисельних розв’язків задач, еволюційні стратегії застосовують для неперервних значень, які типовіші для експериментальних задач у лабораторіях. Спочатку ЕП було запропоновано як процедура породження машинного ін- телекту. Інтелект при цьому розглядався у контексті адаптивної поведінки, а саме як здатність системи адаптувати в широкому діапазоні середовищ свою поведінку для досягнення поставленої мети; можливі розв’язки заданої проблеми представля- лись скінченними автоматами [2]. В кінці 1980-х рр. ЕП було розши- рене для використання в задачах числової оптимізації; зокрема, були запропоновані альтернативні представлення розв’язків, включаючи дійсні вектори для оптимізації неперервних функцій та упорядковані спи- ски (перестановки) для задачі комівояжера [3]. Фактично, початкова організація алго- ритму еволюційного програмування, який оперував скінченними автоматами, була розширена до використання довільного способу кодування, різних операторів му- тації та селекції, а також до техніки самоа- даптації. Наразі прийнято говорити про дві гілки ЕП – традиційне еволюційне програ- мування та сучасне еволюційне програму- вання. Принциповим аспектом, який від- різняє ЕП від генетичного алгоритму, є те, що ЕП представляє фенотипічний, а не ге- нотипічний підхід до моделювання ево- люції: пошук розв’язків йде на рівні фено- типу, а біологічна еволюція розглядається як процес пристосування до навколиш- нього середовища в першу чергу на рівні поведінки. Центральним об’єктом еволю- ції в ЕП є популяція. Такий рівень абстра- кції у природі не передбачає рекомбінації, тому в ЕП немає оператора кросинговеру, а єдиним оператором пошуку альтернати- вних розв’язків є мутація. В цілому сьогодні ЕП розглядається як відкрита структура з точки зору пред- ставлення розв’язків та операторів мутації. Фундаментальним положенням тут є те, що представлення не повинно фіксуватись заздалегідь, а визначається з поставленої проблеми. Аналогічно, оператори мутації розробляються у відповідності з обраним способом кодування розв’язків; ключовим моментом у конструюванні операторів му- тації є те, що вони мають забезпечувати тісний зв’язок між батьком та його нащад- ком. Наразі ЕП найчастіше використову- ється для оптимізації неперервних функ- цій. Тому спочатку розглянемо сучасне еволюційне програмування (СЕП), а озна- йомитися з його історично першою фор- мою можна в роботі [4]. 2. Сучасне еволюційне програмування Сучасне еволюційне програмування (Contemporary Evolutionary Programming), як вже згадувалось, розроблене для задач Теоретичні та методологічні основи програмування 5 числової оптимізації, зокрема, для оптимі- зації дійсних функцій (оптимізації дійсних параметрів – continuous parameter optimiza- tion): необхідно знайти значення аргумен- тів, на яких досягається мінімум функції RRxxxFXF n n  :),...,,()( 21  (аргументи та значення функції є дійсни- ми). В загальному випадку припускається існування обмеженого підпростору: n nn n RvuvuvuX  ],[...],[],[ 2211 , такого що nivxu iii ,...1,  . Насправді ці обмеження мають місце тільки на етапі іні- ціалізації, при встановленні початкової по- пуляції; оператори не перевіряють вико- нання вказаної умови. Таким чином, прос- тір пошуку в принципі є необмеженим: n x RA  . Обмежень на вид цільової функ- ції немає. 2.1. Стандартна форма алгоритму сучасного еволюційного програмування. Стандартна форма алгоритму (Standard EP) ґрунтується на припущенні, що 0)),...,,(min( 21 nxxxF . Схема алгоритму. 0. Кодування розв’язків. 1. Ініціалізація. 2. Оцінювання. 3. Моделювання еволюційного проце- су (репродукція): 3.1. застосування генетичних опера- торів; 3.2. селекція (оцінювання та відбір або перехід на п. 4); 3.3. перехід на п. 3.1. 4. Завершення роботи. Розглянемо кожен крок детальніше. Кодування розв’язків. Одній осо- бині A відповідає вектор дійсних змінних: n n RxxxXA  ),...,,()( 21  . Ініціалізація. Випадковим чином генерується початкова популяція, що складається з N особин iA , Ni ,...,2,1 ; рекомендоване значення розміру популяції 200N ([5]). Значення елемента ijx , nj ,...,2,1 , кожної особини ,...,( 21 iii xxA  )..., inx , Ni ,...,2,1 , встановлюється випа- дково за допомогою рівномірного розподі- лу на інтервалі Rvu jj ],[ , jj vu  . Гра- ниці цього інтервалу мають значення лише на етапі ініціалізації; у подальшій еволюції простір пошуку в принципі є необмеже- ним. Якщо границі інтервалів не обумов- лені задачею, то рекомендовані значення параметрів є такими: 50ju , 50jv , nj ,...,2,1 ([5]). Оцінювання. Функція пристосова- ності )(A зазвичай збігається з цільовою функцією: )()( XFA   . В загальному випадку значення фу- нкції пристосованості змінюється за допо- могою випадкової величини ζi – елемента збурення (random noise term), після чого масштабується до додатного значення. Тобто, в загальному випадку функція здо- ров’я набуває вигляду: )),(()( XFA   , де  RR: – функція масштабуван- ня (scaling function), Θ – додаткова множина параметрів, включених у процес. Застосування генетичних опера- торів. Єдиним оператором в еволюційно- му програмуванні є оператор мутації, який застосовується наступним чином:  кожну особину iA , i=1,…,N, копію- ють для застосування оператора мутації;  мутація копії кожної особини iA здійснюється шляхом додавання нормаль- но розподіленої випадкової величини з ну- льовим математичним сподіванням та се- редньоквадратичним відхиленням, що змі- нюється динамічно (вираховується для кожної компоненти вектора iX  як квадрат- ний корінь лінійного перетворення функції здоров’я). Тобто, значення змінних ijx , nj ,...,2,1 , нащадка 'iA особини iA обра- ховуються за формулою )1,0()( jjijijij NAxx   , (1) де )( iA – значення функції пристосова- ності батька, j – константа масштабуван- Теоретичні та методологічні основи програмування 6 ня або константа пропорційності (propor- tionality constant), j – дисперсія або зна- чення зсуву (offset value), )1,0(jN – стан- дартна нормально розподілена випадкова величина. Як видно з наведених формул, «ши- рина мутації» залежить від значення функ- ції пристосованості батька. Ідея полягає у підвищенні ефективності процесу оптимі- зації шляхом скорочення «ширини мута- ції» при наближенні до оптимуму (нагадає- мо, що в стандартній формі алгоритму гло- бальний оптимум вважається відомим та таким, що дорівнює 0). Константи j , j ( nj ,...,2,1 ) є параметрами алгоритму та встановлю- ються користувачем (всього 2n парамет- рів). Підбір значень параметрів створює додаткові труднощі при використанні ал- горитму. На практиці рекомендують поклада- ти 1j , 0j ( nj ,...,2,1 ). Тоді фор- мула (1) набуває вигляду )1,0()( jiijij NAxx  . Однак необхідно зазначити, що вка- зані значення параметрів були досліджені для випадку задач малої розмірності. Вод- ночас існує суттєва чутливість процесу пошуку до розміру кроку мутації у випад- ку задач великої розмірності. Тому при 2n в [5] рекомендується використовува- ти значення 2 1 n j  ;  кожен нащадок 'iA оцінюється (за допомогою функції пристосованості )'( iA ) та додається в популяцію, причо- му i-ий нащадок додається під номером N+i. Легко бачити, що після генерації всіх нащадків розмір популяції збільшу- ється вдвічі: популяція складається з N ба- тьків та N нащадків. Відбір. Перед початком відбору по- пуляція містить 2N особин. Для відбору серед них N особин в наступне покоління влаштовуються змагання. Для визначення кількості особин, з якими має змагатись кожна особина з об’єднаної популяції ба- тьків та дітей, вводиться додатковий пара- метр 1h ( Nh ). Змагання особин проводяться на- ступним чином. Кожна особина iA ( Ni 2,...,1 ) попарно порівнюється з h ін- шими особинами, обраними випадково за законом рівномірного розподілу з об’єднаної популяції батьків та дітей. Особина iA перемагає особину jA ( },...,,{ 21 hmmmj , }2,...,2,1{ Nmk  , hk ,...,1 ), якщо її функція пристосова- ності є не гіршою, ніж у супротивника: )()( ji AA  . Далі, для кожної особини iA вираховується оцінка iW – кількість її перемог:    h j ji resW 1 , де      інакше,0 )()(якщо,1 ji j AA res ; очевидно, },...,1,0{ hWi  . Після цього всі особини сортуються, за зменшенням кіль- кості їхніх перемог (за спаданням значення оцінки iW ), і найкращі особини утворюють нову популяцію розміром N. У випадку однакової кількості перемог, перевага на- дається особині з кращим значенням функ- ції пристосованості. Значення параметра h встановлю- ється користувачем. Як правило, параметр h набуває значення від Nh  05.0 до Nh  01.0 , тобто від %1 до %5 від зага- льної кількості особин в популяції. При 200N в [5] рекомендується брати 10h . Зауважимо, що з ростом h відбір набуває дискримінаційного елітарного ха- рактеру. Неважко також побачити, що про- ведена в описаний спосіб селекція може інтерпретуватись як ймовірнісна (N+N)-се- лекція еволюційної стратегії. Тут доречно було б навести головні аргументи дослідників ЕП, які наполяга- ють на ймовірнісній селекції [5]. Перш за все вони звертають увагу на те, що селек- ція в природі є ймовірнісною. Крім того, існують емпіричні факти, згідно з якими «м’який» механізм селекції, що присвоює ненульову ймовірність відбору навіть най- Теоретичні та методологічні основи програмування 7 гіршим індивідуумам, дозволяє еволюцій- ним алгоритмам вийти з локального опти- муму [6]. Завершення роботи. Умовою зу- пинки алгоритму ЕП може бути виконання однієї з умов: досягнення заданого числа поколінь maxt ; досягнення заданого рівня якості; досягнення заданого рівня збіж- ності (особини в популяції стають настіль- ки схожими між собою, що подальше по- кращення відбувається надто повільно). ЕП, як було сказано вище, не пе- редбачає оператора рекомбінації, повністю покладаючись на силу мутації. Аргумента- ція такого підходу є наступною. Трактування еволюції у першу чер- гу як механізму генетичних змін, а не фе- нотипічних наслідків, є неправильним, от- же, роль кросинговеру в генетичному ал- горитмі перебільшується [7]. На кросинго- вер слід дивитись скоріше як на можли- вість ізолювання дефектів у зародку, а не як на можливість покращення еволюційної оптимізації шляхом рекомбінації гарних розв’язків, на чому наголошують дослід- ники в галузі генетичних алгоритмів [8]. Полігенність та плейотропія в більшості випадків перешкоджають останній можли- вості, адже класичне припущення «один ген – одна властивість» в органічній ево- люції не є вірним. Д. Фогель та В. Атмар в [9] предста- вили емпіричні дані (отримані шляхом по- рівняння результатів роботи алгоритмів ЕП з та без рекомбінації на послідовностях лінійних функцій з параметризованими взаємодіями між генами), згідно з якими оператор мутації Гаусса є більш ефектив- ним, ніж одноточковий кросинговер, та навіть більш ефективним, ніж комбінація кросинговеру та мутації. Після цього вийшла низка робіт, присвячених дослідженню ЕП та генетич- них алгоритмів, автори яких намагались встановити, за яких обставин використан- ня оператора рекомбінації покращує про- дуктивність алгоритму [10]. Так, в [11] отримано емпіричний результат, згідно з яким кросинговер є перешкодою для вели- ких популяцій при вирішенні проблеми виходу популяції з локального оптимуму. Водночас автори роботи [12] дослідили нішу кросинговеру (двоточкового та одно- рідного) в генетичному алгоритмі та роз- робили задачу, для якої кросинговер має суттєві переваги над мутацією. В роботі [13] робиться висновок, що можливості кросинговеру чи гауссівської мутації з по- родження нащадка кращої у порівнянні з батьками якості великою мірою залежать від стану простору пошуку; мутація вияв- ляється кращою на початку, а кросинговер – у процесі еволюції. 2.2. Теоретичні основи сучасного еволюційного програмування. Розгля- даючи ЕП як оптимізаційну процедуру, природно дослідити її математичні власти- вості. Маючи на меті дослідження збіж- ності алгоритму ЕП, Д. Фогель провів ана- ліз стандартної форми алгоритму ЕП для випадку 1j , 0j , 0)()(  ii XFA  ( Ni ,...,2,1 , nj ,...,2,1 ). Зокрема, вико- ристовуючи ланцюги Маркова, Д. Фогель показав [7, 14], що ймовірність збіжності алгоритму дорівнює 1, тобто довів асимп- тотичну збіжність стандартної форми алго- ритму до глобального оптимуму. В доведенні Д. Фогеля кожна мож- лива популяція, яка може виникнути в процесі еволюції, інтерпретується як стан скінченного ланцюга Маркова, а єдиний поглинаючий стан ланцюга Маркова – як об’єднання всіх станів популяції, які міс- тять точку глобального оптимуму. Простір станів визначається шляхом дискретизації простору R, яка фактично використовуєть- ся при будь-якому представленні комп’ю- тером дійсних значень. В роботі [5] звертається увага на те, що результат Д. Фогеля ґрунтується на: властивості елітарності відбору, яка гаран- тує монотонну поведінку еволюції, зокре- ма, існування поглинаючого стану; дис- кретизації простору пошуку; можливості переходу в будь-яку точку простору пошу- ку за один або декілька кроків. Можна зауважити, що реальний глобальний оптимум може як завгодно си- льно відрізнятись від знайденого алгорит- мом. Більше того, в зв’язку з дискретизаці- єю простору пошуку, нічого не можна ска- зати про властивість збіжності еволюцій- Теоретичні та методологічні основи програмування 8 ного програмування для цільової функції RRf n : . Аналіз матриці ймовірностей пере- ходів [15], яку визначає еволюційний мар- ківський ланцюг, також вказує на те, що ймовірність покращення розв’язку зростає як геометрична прогресія, збігаючись до 1.0, та є лінійною комбінацією власних значень цієї матриці переходів. Виходячи зі схожості підходів ЕП та еволюційної стратегії, в [15] пропону- ється перенести на еволюційне програму- вання аналіз швидкості збіжності, проведе- ний для еволюційної стратегії в роботі [16]. Ці результати вказують на геометрич- ну швидкість збіжності для строго опуклих функцій, і більше того, на те, що швид- кість збіжності може бути покращена як логарифм кількості нащадків λ в (1, λ)-від- борі. У роботі [5] Д. Фогель також про- аналізував випадок розмірності популяції 1N та елітарної селекції; 1jk , 0jz , nj ,...,2,1 . Результуючий алгоритм ви- явився ідентичним алгоритму (1+1)-ЕС для )(xf . Загалом можна сказати, що на сьо- годні еволюційне програмування є від- носно мало дослідженою парадигмою мо- делювання еволюції. 2.3. Варіанти алгоритмів сучасно- го еволюційного програмування. Вико- ристання стандартної форми алгоритму ЕП супроводжується такими труднощами:  необхідність підбору 2n значень па- раметрів еволюції j та j ( nj ,...,2,1 );  узгодження та підбір функції мас- штабування Ω у випадку, коли немає ін- формації про глобальний оптимум;  у випадках, коли значення функції пристосованості є надто великими, пошук стає квазівипадковим;  негативно впливає на стійкість ал- горитму випадок, коли глобальний міні- мум функції пристосованості відрізняється від 0; точне досягнення глобального міні- муму в цьому випадку є неможливим. Для подолання вказаних недоліків стандартної форми ЕП було запропонова- но низку модифікацій наведеного вище алгоритму. Один з варіантів модифікації допус- кає змінний розмір популяції, а також на- явність різної кількості нащадків у різних батьків. Інший підхід полягає у зміні про- цедур генерації нащадків та відбору. На- приклад, обирають випадково батька, з нього отримують шляхом мутації нащадка, оцінюють нащадка та додають в популя- цію; одразу після цього з популяції вилу- чають найслабшу особину. Найбільш перспективним підходом видається застосування ідеї самоадаптації в ЕП. Дійсно, в алгоритмі ЕП існує низка параметрів, які керують поведінкою алго- ритму: розмір популяції, розподіл мутацій, тиск відбору. Тоді, наприклад, оператори мутації (варіації, зміни) можуть бути включені до складу особин як додаткова інформація щодо способу породження на- щадків; ця додаткова інформація може під- лягати мутації та селекції в той же спосіб, що і можливий розв’язок задачі. Були за- пропоновані методи розширення еволю- ційного пошуку до двокрокового процесу, який включає еволюцію мутаційних змін. Зауважимо, що такі методи були розробле- ні для ЕП та еволюційної стратегії повніс- тю незалежно. Самоадаптовні алгоритми застосовувались як до проблем непере- рвної, так і до проблем дискретної оптимі- зації [15]. Враховуючи сказане, на сьогодні можна виділити, згідно робіт [5, 14, 15], 5 варіантів сучасного (неперервного) еволю- ційного програмування:  стандартне ЕП (Standard EP) – ха- рактеризується відсутністю будь-якого ме- ханізму самоадаптації;  неперервне стандартне ЕП (Conti- nuous Standard EP) – на противагу механіз- му, базованому на зміні популяцій, ново- створений індивід одразу оцінюється та додається в популяцію;  мета-ЕП (Meta-EP) – включає до- даткові змінні (параметри мутацій) в гено- тип з метою проведення самоадаптації;  неперервне мета-ЕП (Continuous Meta-EP) – мета-ЕП, за якого новостворе- Теоретичні та методологічні основи програмування 9 ний індивід одразу оцінюється та додаєть- ся в популяцію;  R-мета-ЕП (Rmeta-EP) – крім стан- дартних відхилень, включає в генотип ко- варіації (представлені за допомогою коефі- цієнтів кореляції) для самоадаптації. Цей метод, який, очевидно, легко узагальнити до неперервного R-мета-ЕП, був реалізова- ний та протестований Д. Фогелем тільки для двовимірного випадку. Зупинимось детальніше на питанні самоадаптації в ЕП – розглянемо мета-ЕП та R-мета-ЕП. Ще раз наголосимо, що в цьому випадку кожна особина містить не лише потенційний розв’язок задачі, але й інформацію щодо того, як розподіляються нащадки. Мета-еволюційне програмування. Мета-ЕП (Meta-EP), як вже зазначалось, включає додаткові змінні (параметри мута- цій) в генотип з метою проведення само- адаптації. Доповнимо схему стандартної форми ЕП для випадку мета-ЕП. Кодування розв’язків. Особина кодується у вигляді sx AAXA  ),(  , де n n RxxxX  ),...,,( 21  – вектор парамет- рів об’єкта (object variable vector), які оці- нюються за допомогою цільової функції, n n R ),...,,( 21   – вектор па- раметрів мутації, вектор стандартних від- хилень (mutation step sizes vector, standard deviations vector), які використовуються при генерації нащадків. Таким чином, у випадку мета-ЕП n x RA  , n s RA  . Можна узагальнити на- ведений спосіб кодування для стандартної форми ЕП: у випадку стандартної форми n x RA  , sA Ø. Ініціалізація. Випадковим чином генерується початкова популяція, що скла- дається з N особин iA , i=1,…,N; рекомен- доване значення розміру популяції 200N ([10]). При цьому значення еле- мента ij , nj ,...,2,1 , кожної особини )...,,,,,...,,( 2121 iniiiniii xxxA  , Ni ,...,1 , встановлюється випадково за законом рів- номірного розподілу на інтервалі ],0[ c , де c – параметр еволюції, 0c . В момент іні- ціалізації рекомендується брати 25c [7]. Під час оптимізації значення ij можуть варіюватись на всьому діапазоні додатних дійсних чисел R+. Застосування генетичних опера- торів. Існує кілька варіантів оператора му- тації; в усіх цих варіантах вектор  ви- користовується при генерації нащадка ),('   XA індивідуума ),(   XA та від- бувається самоадаптація параметрів мута- ції  . Розглянемо п’ять основних варіан- тів оператора мутації. Найпоширенішими операторами мутації у мета-еволюційному програму- ванні є наступні. 1. При застосуванні оператора му- тації у роботах [3, 7, 15, 16] до індивідуума ),(   XA нащадок ),('   XA утворю- ється наступним чином: )1,0(Nxx iii  , )1,0(Niii   . Тут N(0, 1) – стандартна нормально розподілена випадкова величина; ζ – зов- нішній параметр, завдяки якому величини i  мають тенденцію залишатись до- датними; рекомендоване значення 6 . Для гарантування додатних значень змін- них i  (параметрів мутації), використову- ється обмежувальне правило (boundary rule):  якщо 0i , то покласти 00   i , де 0 – невелике додатне, на- приклад, 001.00  . Слід пам’ятати, що при надто малих значеннях змінних – параметрів мутації – може суттєво уповільнитись процес збіж- ності. Легко бачити, що однією з відмін- ностей мета-еволюційного програмування від еволюційної стратегії є те, що в мета- еволюційному програмуванні спочатку ві- дбувається мутація параметрів об’єкта, а потім – параметрів мутації. Робилися спроби змінити порядок мутації векторів X  та   . Зокрема, в роботі [17] дається яв- не порівняння варіантів мутації «спочатку Теоретичні та методологічні основи програмування 10 сигма» та «в кінці сигма» і робиться ви- сновок, що перший варіант має суттєві пе- реваги. 2. Змінні нащадка ),('   XA осо- бини ),(   XA обраховуються в роботах [10, 18] наступним чином: )1,0(iiii N  , )1,0(iiii Nxx   . Тут )1,0(iN – стандартна нормально розподілена випадкова величина; α – зов- нішній параметр, який задається корис- тувачем. Рекомендоване значення 6 1  ( 2.0 ). Звернемо увагу на такий факт. Як- що коефіцієнт α обрати надто великим, то величина i  може стати від’ємною. В цьо- му випадку її слід замінити на деяке мале 00  , хоча це й протирічить певною мі- рою ідеї самоадаптації. Якщо ж обрати ко- ефіцієнт α надто малим, то проявляється тенденція уповільнення еволюції [18]. Для попередження надто близьких до 0 відхи- лень також застосовується обмежувальне правило (boundary rule):  якщо 0 i , то покласти 00   i , де 0 – невелике додатне. Існують варіанти оператора мутації з використанням не адитивної, а логнор- мальної схеми модифікації розміру кроку мутації. 3. В роботах [10, 19] розглядається алгоритм, названий класичним (classical EP – CEP), з мутацією виду: )1,0(iiii Nxx   , ))1,0()1,0(exp( iii NN   . Тут N(0,1) – стандартна нормально розподілена випадкова величина, що гене- рується для кожного нащадка; Ni(0,1) – стандартна нормально розподілена випад- кова величина, що генерується для кожної змінної; 1 2       n та   1 2n    – навчальні норми (learning rates). 4. В роботах [10, 19] також розг- лядається алгоритм, названий швидким (fast-EP – FEP), з мутацією виду: iiii xx   , ))1,0()1,0(exp( iii NN   . Тут i – випадкова величина з роз- поділом Коші (параметр масштабування 1t ). 5. В роботах [10, 19] пропонується також модифікація попереднього алгорит- му, названа покращеним швидким алгорит- мом (improved fast evolutionary program- ming algorithm – IFEP). В цьому випадку в кожного з батьків породжуються по два нащадки, один з використанням розподілу Гаусса, інший – розподілу Коші. Останній розподіл має товстіший «хвіст», завдяки якому з’являється більше шансів згенеру- вати широкі мутації; в цілому це дає алго- ритму більше шансів вийти з локального мінімуму. Водночас розподіл Гаусса при використанні малих кроків мутації дає бі- льше можливостей для регулювання існу- ючих батьків. Серед інших варіантів оператора мутації у мета-еволюційному програму- ванні можна виділити алгоритми оптимі- зації керованих мутацій в полярній сис- темі координат [20] та алгоритми з вико- ристанням комбінації різних розподілів мутації [21]. R-мета-еволюційне програмуван- ня. У випадку R-мета-еволюційного про- грамування (Rmeta-EP) для самоадаптації параметрів використовується коваріаційна матриця. Наведемо лише основні відмін- ності R-мета-еволюційного програмування від мета-еволюційного програмування. Кодування розв’язків. Особина кодується у вигляді AAAXA sx  ),,(  , де 2/)1(* 21 ]1,1[),...,,(  nn m  – век- тор коефіцієнтів кореляції (correlation coefficients vector), ]1,1[ ji ij ij c   , }1,...,1{  ni , },...,1{ nij  , представляє Теоретичні та методологічні основи програмування 11 матрицю коваріацій 1C . Таким чином, у випадку R-мета-еволюційного програ- мування n x RA  , n s RA  , A 2/)1(*]1,1[  nn . Ініціалізація коефіцієнтів кореляції ]1,1[j здійснюється аналогічно ініці- алізації інших змінних. Застосування генетичних опера- торів. При застосуванні оператора мутації до індивідуума ),,(   XA нащадок ),,('   XA утворюється наступним чи- ном [5]: )),(,0(   CNXX , )1,0(iiii N  ,       інакше),~sign( 1~якщо,~ j jj j    , де )1,0(~ jjjj N  , ω – масштабу- ючий множник коефіцієнтів кореляції; ре- комендоване значення 6 . Для повноти викладення матеріалу наведемо (згідно з [5]) зведену таблицю рекомендованих значень зовнішніх пара- метрів стандартного еволюційного програ- мування та мета-еволюційного програму- вання, яка може бути корисною при прак- тичній реалізації відповідних алгоритмів. Звернемо увагу, що вказані значення були рекомендовані для задач малої роз- мірності. Таблиця. Рекомендовані значення зовнішніх параметрів Параметр Має місце в Значення за замовченням стандартне ЕП мета-ЕП Границі iu , iv інтервалів значень змінних ix + + 50iu 50iv Верхня границя c параметрів мутації i + 25c Константи пропорційності i + 1i Константи зсуву i + 0i Параметр підтримки самоадаптації ζ + 6 Параметр турнірного відбору h + + 10h Розмір популяції N + + 200N 2.4. Порівняння сучасного ево- люційного програмування та еволюцій- ної стратегії. Спочатку зазначимо спільні властивості сучасного еволюційного про- грамування та еволюційної стратегії. Обидва підходи представляють фе- нотипічний підхід до моделювання еволю- ції: увага фокусується на поведінці потен- ційних розв’язків у популяції, а не на ге- нетичному зв’язку між батьками та на- щадками. При розв’язку задач оптиміза- ції дійсних функцій оперують безпосеред- ньо з дійсними числами. Мутації парамет- рів задачі мають нормальний розподіл. Відбір в ЕП можна розглядати як ймовір- нісну (N+N)-селекцію в еволюційній стра- тегії. В мета-ЕП, як і в еволюційній страте- гії, до складу генотипу включені додаткові змінні – параметри мутацій, тобто кожна особина містить потенційний розв’язок та інформацію про те, як розподілятимуться нащадки. Серед відмінностей між СЕП та еволюційною стратегією виділимо такі. В мета-еволюційному програмуванні, на відміну від еволюційної стратегії, кіль- кість змінних – параметрів мутації дорів- нює n ( ),...,,( 21 n  ), тобто немає можливості обрати довільне число таких змінних з інтервалу [1, n]. В еволюційній Теоретичні та методологічні основи програмування 12 стратегії спочатку проводиться мутація параметрів стратегії, а потім – параметрів об’єкта; в мета-ЕП порядок мутацій є зворотним, що призводить до ефекту за- тримки в зміні параметрів еволюції. Хоча необхідно відзначити, що останнім часом з’явились приклади використання в мета- ЕП порядку мутації   – X  , що фактично згладжує відмінності між еволюційним програмуванням та еволюційною стратегі- єю. Зокрема, в роботах Д. Фогеля [22, 23] використовується логарифмічно нормаль- на адаптація параметрів   , за якою вико- нується мутація змінних – параметрів за- дачі X  . Логарифмічно нормальний розпо- діл, що використовується в еволюційній стратегії, автоматично гарантує додатні значення параметрів стратегії, а також від- сутність відхилень у випадку нульового тиску відбору. Водночас флуктуації в мета-ЕП не є нейтральними і не гаранту- ють додатних значень параметрів мутації. В ЕП використовується стохастичний відбір, а в еволюційній стратегії – детер- мінований (найгірші розв’язки викидають- ся з популяції). Таким чином, в еволю- ційній стратегії кожна особина бере участь в середньому в породженні   на- щадків, але, можливо, і жодного. В еволю- ційній стратегії реалізовано багато форм кросинговеру, а ЕП кросинговер не вико- ристовує. Останній пункт вимагає більш ґрун- товного пояснення. Справа в тому, що еволюційна стра- тегія є абстракцією еволюції на рівні ін- дивідуальної поведінки. Включена в хро- мосому інформація для самоадаптації параметрів фактично є генетичною, а не фенотипічною інформацію, тому деякі форми кросинговеру є доречними. ЕП є абстракцією еволюції на рівні репродук- тивних популяцій, видів. Точка в просто- рі пошуку в ЕП розглядається не як осо- бина – представник певного виду, а ско- ріше як абстракція самого виду. Як на- слідок, рекомбінація в ЕП не має сенсу, оскільки її неможливо застосувати до різ- них видів: кросинговер не відбувається між видами [10]. Висновок Роботи Л. Фогеля та його учнів по- ширили процеси ЕП від задач прогнозу- вання на моделювання систем, розпізна- вання образів, теорію ігор тощо. Сучасні вчені у царині ЕП займа- ються дослідженням еволюції програм, впливу різних параметрів середовища та різних видів мутації на результативність ЕП, розпізнаванням образів тощо. Принци- пи ЕП застосовуються у плануванні та ма- ршрутизації трафіку, військово-страте- гічному плануванні, діагностиці раку, ке- руючих системах, обробці сигналів, на- вчанні у іграх і багатьох інших застосу- ваннях. При застосуванні традиційних мето- дів оптимізації і пошуку, у разі навіть не- значної зміни параметрів середовища всі обчислення доводиться проводити заново. Еволюційний підхід дозволяє проводити аналіз і адаптацію вже створеної популяції до нових умов середовища, чим скорочує час роботи алгоритму і реалізує принцип машинної адаптації і навчання. 1. Fogel L.J., Lawrence J.A. А Retrospective View and Outlook on Evolutionary Algorithms // Proceedings of the International Conference on Computational Intelligence Theory and Applications: Lecture Notes In Computer Science. – 1997. – Vol. 1226. – P. 337–342. 2. Фогель Л., Оуэнс А., Уолш М. Искусствен- ный интеллект и эволюционное моделиро- вание. – М.: Мир, 1969. – 230 с. 3. Fogel L.J., Fogel D.B. Artificial Intelligence through Evolutionary Programming // Final Report for U. S. Army Research Institute, Contract. – 1986. 4. Гулаєва Н.М. Еволюційні алгоритми // Віс- ник Київського національного універ- ситету імені Тараса Шевченка. Серія: фі- зико-математичні науки. – 2013. – Вип. 2. – С. 141–150. 5. Bäck T. Evolutionary Algorithms in Theory and Practice: Evolution Stratagies, Evolu- tionary Programming, Geneticd Algorithms. – Oxford University Press, 1996. – 318 p. 6. Galar R. Evolutionary search with soft selec- tion // Biological Cybernetics. – 1989. – Vol. 60. – P. 357–364. 7. Fogel D.B. Evolving Artificial Intelligence // PhD thesis. – University of California, San Diego, CA. – 1992. Теоретичні та методологічні основи програмування 13 8. Atmar W. The philosophical errors that plague both evolutionary theory and simulated evolu- tionary programming // In: D.B. Fogel and W. Atmar (eds.) Proceedings of the 1 st Annual Conference on Evolutionary Programming. – Evolutionary Programming Society, San Die- go, CA. – 1992. – P. 27–34. 9. Fogel D.B., Atmar W. Comparing genetic op- erators with Gaussian mutations in simulated evolutionary processes using linear systems // Biological Cybernetics. – 1990. – Vol. 63, N 2. – P. 111–114. 10. Eiben A.E., Smith J.E. Introduction to Evolutionary Computing. – Springer, Natural Computing Series, 2007. – 300 p. 11. Galar R. Simulation of local evolutionary dy- namics of small populations // Biological Cy- bernetics. – 1991. – Vol. 65. – P. 37–45. 12. Eshelman L.J., Schaffer J.D. Crossover’s niche // In: S. Forrest (editor) Proceedings of the 5 th International Conference on Genetic Algorithms. – Morgan Kaufmann Publishers, San Mateo, CA. – 1993. – P. 9–14. 13. Jain A.D., Fogel D.B. Case studies in apply- ing fitness distributions in evolutionary algo- rithms. II. Comparing the improvements from crossover and gaussian mutation on simple neural networks // In: X. Yao, D.B. Fogel (eds.) Proceedings of the 2000 IEEE Sympo- sium on Combinations of Evolutionary Com- putation and Neural Networks. – IEEE Press, Piscataway, NJ. – 2000. – P. 91–97. 14. Fogel D.B. Asymptotic Convergence Proper- ties of Genetic Algorithms and Evolutionary Programming: Analysis and Experiments // Cybernetics and Systems. – 1994. – Vol. 25, N 3. – Р. 389–407. 15. Fogel D.B. An overview of evolutionary pro- gramming // In: L.A. Davis et al. (eds.) Evolu- tionary algorithms. – Springer. – 1999. – P. 89–110. 16. Bäck T., Rudolph G., Schwefel H.-P. Evolu- tionary Programming and Evolution Strate- gies: Similarities and Differences // In: D.B. Fogel and W. Atmar (eds.) Proceedings of the 2 nd Annual Conference on Evolutionary Pro- gramming. – Evolutionary Programming So- ciety, La Jolla, CA. – 1993. – Р. 11–22. 17. Gehlhaar D.K., Fogel D.B. Tuning evolution- ary programming for conformationally flexi- ble molecular docking // In: L.J. Fogel, P.J. Angeline, T. Bäck (eds.) Proceedings of the 5 th Annual Conference on Evolutionary Pro- gramming. – MIT Press, Cambridge, MA. – 1996. – Р. 419–429. 18. Курейчик В.М., Родзин С.И. Эволюцион- ные вычисления: генетическое и эволюци- онное программирование // Новости ис- кусственного интеллекта. – 2003. – № 5. – С. 13–19. Режим доступу: www.raai.org/library/ainews/2003/5/kureichik _rodzin.doc 19. Yao X., Liu Y., Lin G. Evolutionary program- ming made faster // IEEE Transactions on Evolutionary Computing. – 1999. – Vol. 3, N 2. – Р. 82–102. 20. Ghozeil A., Fogel D.B. A Preliminary Investi- gation into Directed Mutation in Evolutionary Algorithms // In: H.-M. Voigt, W. Ebeling, I. Rechenberg, and H.-P. Schwefel (eds.) Paral- lel Problem Solving from Nature PPSN IV. – Springer, Berlin. – 1993. – Р. 329–335. 21. Saravanan N., Fogel D.B. Multi-Operator Evolutionary Programming // In: P.J. Ange- line, R.C. Eberhart, R.G. Reynolds, and J.R. McDonnell (eds.) Evolutionary Programming VI: Proceedings of the 6 th Annual Conference on Evolutionary Programming. – Springer, Berlin. – 1997. – Р. 215–221. 22. Chellapilla K., Fogel. D.B. Evolving an ex- pert checkers playing program without human expertise // IEEE Transactions on Evolution- ary Computation. – 2001. – Vol. 5, N 4. – Р. 422–428. 23. Fogel D.B. Blondie24: Playing at the Edge of AI. – Morgan Kauffmann, San Francisco, 2002. – 406 p. Одержано 28.02.2013 Про авторів: Глибовець Микола Миколайович, доктор фізико-математичних наук, професор, декан факультету інформатики НаУКМА, Гулаєва Наталія Михайлівна, кандидат фізико-математичних наук, доцент кафедри інформатики НаУКМА. Місце роботи авторів: Національний університет «Києво-Могилянська Академія», 04655, м. Київ, вул. Сковороди, 2. Тел.: (044) 463 6985. Факс: (044) 416 4515. E-mail: glib@ukma.kiev.ua http://www.springer.com/east/home/computer/artificial?SGWID=5-147-69-173623010-0 http://www.springer.com/east/home/computer/artificial?SGWID=5-147-69-173623010-0 http://www.raai.org/library/ainews/2003/5/kureichik_rodzin.doc http://www.raai.org/library/ainews/2003/5/kureichik_rodzin.doc

Ähnliche Einträge