Еволюційне програмування

Проведено комплексний аналіз стану царини практичного застосування сучасного еволюційного програмування, а також визначення світових тенденцій і перспектив розвитку еволюційних технологій....

Full description

Saved in:

Bibliographic Details
Date:	2013
Main Authors:	Глибовець, М.М., Гулаєва, Н.М.
Language:	Ukrainian
Published:	Інститут програмних систем НАН України 2013
Series:	Проблеми програмування
Subjects:	Теоретичні та методологічні основи програмування
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/86688
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Еволюційне програмування / М.М. Глибовець, Н.М. Гулаєва // Проблеми програмування. — 2013. — № 4. — С. 3-13. — Бібліогр.: 23 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-86688
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-866882025-02-09T14:16:17Z Еволюційне програмування Evolutionary Programming Глибовець, М.М. Гулаєва, Н.М. Теоретичні та методологічні основи програмування Проведено комплексний аналіз стану царини практичного застосування сучасного еволюційного програмування, а також визначення світових тенденцій і перспектив розвитку еволюційних технологій. 2013 Еволюційне програмування / М.М. Глибовець, Н.М. Гулаєва // Проблеми програмування. — 2013. — № 4. — С. 3-13. — Бібліогр.: 23 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/86688 004.4 uk Проблеми програмування application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування
spellingShingle	Теоретичні та методологічні основи програмування Теоретичні та методологічні основи програмування Глибовець, М.М. Гулаєва, Н.М. Еволюційне програмування Проблеми програмування
description	Проведено комплексний аналіз стану царини практичного застосування сучасного еволюційного програмування, а також визначення світових тенденцій і перспектив розвитку еволюційних технологій.
author	Глибовець, М.М. Гулаєва, Н.М.
author_facet	Глибовець, М.М. Гулаєва, Н.М.
author_sort	Глибовець, М.М.
title	Еволюційне програмування
title_short	Еволюційне програмування
title_full	Еволюційне програмування
title_fullStr	Еволюційне програмування
title_full_unstemmed	Еволюційне програмування
title_sort	еволюційне програмування
publisher	Інститут програмних систем НАН України
publishDate	2013
topic_facet	Теоретичні та методологічні основи програмування
url	https://nasplib.isofts.kiev.ua/handle/123456789/86688
citation_txt	Еволюційне програмування / М.М. Глибовець, Н.М. Гулаєва // Проблеми програмування. — 2013. — № 4. — С. 3-13. — Бібліогр.: 23 назв. — укр.
series	Проблеми програмування
work_keys_str_mv	AT glibovecʹmm evolûcíjneprogramuvannâ AT gulaêvanm evolûcíjneprogramuvannâ AT glibovecʹmm evolutionaryprogramming AT gulaêvanm evolutionaryprogramming
first_indexed	2025-11-26T18:40:24Z
last_indexed	2025-11-26T18:40:24Z
_version_	1849879357957341184
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

Еволюційне програмування

Institution

Similar Items