Після схрещування і мутації необхідно створити нову популяцію. Види операторів формування нового покоління (репродукції, редукції) практично збігаються з видами операторів відбору батьків, що передбачають формування проміжного масиву особин, допущених до схрещування.
Слід визначити, які з нових особин увійдуть до наступного покоління, а які — ні. Для цього застосовують один із двох способів.
Перший спосіб полягає в тому, що нові особини (нащадки) займають місця своїх батьків, після чого настає наступний етап, в якому нащадки оцінюються, відбираються, дають потомство і поступаються місцем своїм нащадкам.
Недоліком даного способу є можливість втрати найбільш пристосованої особини попереднього покоління. Одним із способів розв’язання даної проблеми може бути використання принципу елітизму, який полягає в тому, що хромосоми з найбільшою пристосованістю гарантовано переходять у нову популяцію. Кількість елітних особин k е , які гарантовано перейдуть у наступну популяцію, може бути обчислена за формулою: k е = (1 – S O ) · N, де S O — ступінь оновлення популяції, що знаходиться в діапазоні [0,95; 1,0]; N — розмір популяції.
Використання принципу елітизму зазвичай дозволяє прискорити збіжність генетичного пошуку. Недолік використання даної стратегії полягає в тому, що підвищується імовірність потрапляння методу в локальний оптимум.
Другий спосіб передбачає створення проміжної популяції, яка включає як батьків, так і їхніх нащадків. Члени цієї популяції оцінюються, а потім з них вибираються N найкращих, які й увійдуть до наступного покоління. Другий варіант є більш оптимальним, але він потребує сортування масиву розміром 2 N.
Другий варіант формування нового покоління можна реалізувати за допомогою принципу витіснення, котрий носить двокритеріальний характер: включення особин у нове покоління залежить не тільки від величини їх fitness-function, але й від того, чи існує вже у формованій популяції наступного покоління особина з аналогічним хромосомним набором. З усіх особин з однаковими генотипами перевага спочатку віддається тим, чия пристосованість вища. Отже, досягаються дві мети: по-перше, не втрачаються кращі знайдені рішення, що мають різні хромосомні набори, а по-друге, у популяції постійно підтримується достатня генетична різноманітність. Витіснення в даному випадку формує нову популяцію скоріше з далеко розташованих особин, замість особин, що групуються біля поточного знайденого рішення. Цей метод особливо добре себе зарекомендував у розв’язанні багатоекстремальних задач, при цьому крім визначення глобальних екстремумів з’являється можливість виділити й ті локальні оптимуми, значення яких близькі до глобальних.
Наступний крок — виконання перетину двох хромосом. Батько А копіюється у дитини А, а батько В — у дитини В, і так аж до точки перетину. У цій точці (другий цикл for) батько А копіюється у дитини В, а батько В — у дитини А. Якщо точка перетину дорівнює розміру програми, то перший цикл for скопіює всю хромосому, а другому не буде чого копіювати (тобто ми досягнемо потрібного результату).
Нарешті, діти в новій популяції успадковують розміри своїх батьків. Розмір у даному випадку є постійною величиною, але ви легко можете змінити цю установку під час ініціалізації алгоритму.
Зверніть увагу, що змінна nextPop створюється на підставі curPop. Змінна nextPop задає популяцію, в якій будуть створені діти; змінна curPop показує, з якої популяції обирати батьків.
Остання функція, mutate, змінює ген у поточній хромосомі на нову інструкцію, яка залежить від імовірності мутації.
Оператор мутації полягає у зміні генів у випадково вибраних позиціях. На відміну від операторів відбору і схрещування, що використовуються для поліпшення структури хромосом, метою оператора мутації є диверсифікація, тобто підвищення різноманітності пошуку і введення нових хромосом у популяцію, для того щоб більш повно досліджувати простір пошуку. Оскільки число членів популяції P, як
Проста мутація використовується для бінарних, гомологічних, числових і векторних хромосом. Суть її полягає у внутрішньогенній мутації. При цьому в хромосомі випадковим чином вибирається ген, а потім проводиться його випадкова зміна.
Одним із важливих елементів генетичного пошуку є критерії зупинення. Очевидно, що еволюція — нескінченний процес, в ході якого пристосованість особин поступово підвищується. Примусово зупинивши цей процес через досить тривалий час після його початку і вибравши найбільш пристосовану особину в поточному поколінні, можна одержати не абсолютно точне, але близьке до оптимального рішення.
Як правило, як критерій зупинення застосовується обмеження на максимальну кількість ітерацій функціонування методу (тобто обмеження на кількість поколінь). Кількість популяцій може бути будь-якою, але зазвичай установлюється 50—110 популяцій. Якщо як критерій зупинення обирається максимальна кількість ітерацій, то задається кількість ітерацій t, унаслідок чого цикл генетичного пошуку виконується t разів.
Зупинення роботи генетичного методу може відбутися також у разі, якщо популяція вироджується, тобто якщо практично немає різноманітності в генах особин популяції. Виродження популяції називають передчасною збіжністю.
Якщо критерієм зупинення вибирається виродження популяції, то задаються кількість ітерацій t п та поріг коефіцієнта поліпшення значень fitness-function кращої хромосоми ? п . t best
Починаючи з циклу (t п + 1), обчислюються значення цільової функції для кожної хромосоми поточної t-ої популяції, і вибира
Починаючи з циклу (t п + 1), обчислюються значення цільової функції для кожної хромосоми поточної t-ої популяції, і вибирається з цих значень найкраще значення цільової функції f .
З попередніх (t – 1) поколінь вибирається найкраще значення цільової функції
1?t best f .
Потім обчислюється коефіцієнт поліпшення ? за формулою:
1 ? t best
правило, вибирається значно меншим порівняно із загальним числом (2 L ) можливих хромосом у просторі пошуку, то через це вдається досліджувати лише частину пошукового простору. Отже, мутація ініціює різноманітність у популяції, дозволяючи проглядати більше точок у просторі пошуку і долати таким чином локальні екстремуми в процесі пошуку. У процесі мутації з ненульовою імовірністю чергове рішення може перейти в будь-яке інше.
Якщо значення ? виявляється меншим, ніж ? п , то критерій зупинення вважається досягнутим, в іншому випадку виконується наступний цикл генетичного пошуку.
Прийнятне значення цільової функції f п також може використовуватись як критерій зупинення. Якщо в процесі функціонування генетичного методу значення цільової функції f деякої особини досягло значення f п з певною наперед заданою точністю ?, то метод зупиняється. При цьому розв’язком задачі є набуте значення цільової функції f п .
При запуску видається велика кількість інформації, включаючи тенденції зміни здоров’я (у файлі stats.txt, рис. 6.9).
На графіку, поданому на рис. 6.9, зображений цікавий момент
— поступове поліпшення функції здоров’я популяції в часі. Це доводить, що ГА корисний для розв’язання символічних проблем, подібних до поставленого завдання. Незважаючи на те що вибираються хромосоми, які до кінця не вирішують проблему, мутація і перехресне схрещування з іншими хромосомами популяції ведуть до підвищення здоров’я до тих пір, поки завдання не буде повністю вирішене.
Можна не тільки змінювати безліч параметрів ГА (наприклад метод відбору або рекомбінування), але й управляти коефіцієнтами застосування генетичних операторів. Виходить, що не існує оптимального набору методів і параметрів, який зумів би вирішити будь-яке завдання. Кожне завдання слід розглядати окремо, щоб вирішити його швидше або більш ефективним способом (а в деяких випадках — хоча б вирішити). У цьому розділі описуються способи настроювання параметрів ГА розв’язання певної задачі.
Файл stats.txt
Рис. 6.9. Графік зміни функції здоров’я популяції в часі
17.18. Канонічний ГА
Дана модель алгоритму є класичною. Вона була запропонована Джоном Холландом у його відомій праці «Адаптація в природних і штучних середовищах» (1975). Часто можна зустріти опис простого ГА, він відрізняється від канонічного тим, що використовує або турнірний відбір, або метод рулетки. Модель канонічного ГА має такі характеристики:
— фіксована чисельність популяції;
— фіксована розрядність генів;
— пропорційний відбір;
— особини для схрещування вибираються випадковим чином;
— одноточковий кросовер і одноточкова мутація.
Наступне покоління формується з нащадків поточного покоління без «елитизму». Нащадки займають місця своїх батьків.
17.19. Джиніторний ГА
У даній моделі використовується специфічна стратегія відбору. Спочатку, як і вважається, популяція ініціалізувалася і її особини оцінюються. Потім вибираються випадковим чином дві особини, схрещуються, причому виходить тільки один нащадок, який оцінюється і займає місце найменш пристосованої особини. Після цього знову випадковим чином вибираються 2 особини, і їхній нащадок займає місце особини з найнижчою пристосованістю. Таким чином на кожному кроці в популяції оновлюється тільки одна особина. Підбиваючи підсумки, можна виділити такі характерні особливості:
— фіксована чисельність популяції;
— фіксована розрядність генів;
— особини для схрещування вибираються випадковим чином;
— обмежень на тип кросовера і мутації немає.
У результаті схрещування особин виходить один нащадок, який займає місце найменше пристосованої особини.
17.20. Гібридний острівний ГА
Використання гібридного алгоритму дозволяє об’єднати переваги ГА з перевагами класичних методів. Річ у тому, що ГА є робастними алгоритмами, тобто вони дозволяють знаходити хороше рішення, але знаходження оптимального рішення часто виявляється набагато важчим завданням через стохастичності принципів роботи алгоритму. Тому виникла ідея використовувати ГА на початковому етапі для ефективного звуження простору пошуку навколо глобального екстремуму, а потім узявши кращу особину, застосувати один з «класичних» методів оптимізації. Характеристиками алгоритму є:
— фіксована чисельність популяції;
— фіксована розрядність генів;
— будь-які комбінації стратегій відбору та формування наступного покоління;
— обмежень на тип кросовера і мутації немає.
ГА застосовується на початковому етапі, а потім у роботу включається класичний метод оптимізації.
Острівний ГА
Уявимо собі таку ситуацію. У деякому океані є група близькорозташованих островів, на яких живуть популяції особин одного виду. Ці популяції розвиваються незалежно і лише зрідка відбувається обмін представниками між популяціями. Острівна модель ГА використовує описаний принцип для пошуку рішення. Варіант, безумовно, цікавий і є одним з різновидів паралельних ГА. Дана модель ГА володіє такими властивостями:
— наявність кількох популяцій, як правило, однакового фіксованого розміру;
— фіксована розрядність генів;
— будь-які комбінації стратегій відбору і формування наступного покоління в кожній популяції. Можна зробити так, що в різних популяціях використовуватимуться різні комбінації стратегій, хоча навіть один варіант дає різноманітні рішення на різних «островах»;
— обмежень на тип кросовера і мутації немає.
Випадковий обмін особинами між «островами». Якщо міграція буде дуже активною, то особливості острівної моделі будуть
Рис. 6.10. Топологія острівних моделей: а — ізольована, b — кільце, с — повний граф
17.21. CHC (Eshelman) алгоритм CHC розшифровується як Cross-population selection, Heterogenous recombination and Cataclysmic mutation. Даний алгоритм досить швидко сходиться, оскільки в ньому немає мутацій, використовуються популяції невеликого розміру, і відбір особин у наступне покоління ведеться і між батьківськими особинами, і між їхніми нащадками. Через це після знаходження деякого рішення алгоритм перезапускається, а краща особина копіюється в нову популяцію, а особини, що залишилися, є сильною мутацією (мутує приблизно третина бітів у хромосомі) тих, що існують, і пошук повторюється. Ще однією специфічною межею є стратегія схрещування: усі особини розбиваються на пари, причому схрещуються тільки ті пари, в яких хромосоми особин істотно різні (хеммінгова відстань більша за деяку порогову плюс можливі обмеження на мінімальну відстань між крайніми бітами, що відрізняються). При схрещуванні використовується так званий HUX-оператор (Half Uniform Crossover) — це різновид однорідного кросовера, але в ньому до кожного нащадка потрапляє рівно половина бітів хромосоми від кожного батька. Отже, модель володіє такими властивостями:
— фіксована чисельність популяції;
— фіксована розрядність генів;
— перезапуск алгоритму після знаходження рішення;
— невелика популяція;
згладжені і вона не буде значно відрізнятися від моделей ГА без паралелізму.
— особини для схрещування розбиваються на пари і схрещуються за умови істотних відмінностей;
— відбір у наступне покоління проводиться між батьківськими особинами і нащадками;
— використовується половинний однорідний кросовер (HUX);
— макромутація за перезапуску.
17.22. Переваги та недоліки генетичного алгоритму
Генетичні алгоритми володіють яскраво вираженою властивістю створення нового. Інтуїтивний аналіз ГА допомагає виявити аналогії між штучною генетичною системою і властивими людському інтелекту процесами, які зазвичай називаються творчими та інноваційними (спрямованими на створення новин).
Можна припустити, що відкриття (нова ідея, новина) не є результатом тільки суто випадковості. З другого боку, дійсне значення випадкового при поясненні механізму відкриттів, здійснюваних людиною, полягає в можливості виконати зіставлення різних ідей. Примітно у зв’язку з цим, що ГА, який моделює природні процеси, поєднує випадкове і закономірне в такому співвідношенні, яке дозволяє ефективно генерувати нові рішення з кращих частин колишніх рішень, заснованих на попередньому досвіді.
Оскільки ГМ в процесі пошуку використовують деяке кодування множини параметрів замість самих параметрів, то вони можуть ефективно застосовуватися для розв’язання задач дискретної оптимізації, визначених як на числових множинах, так і на скінченних множинах довільної природи.
Для роботи ГМ як інформація про функцію, що оптимізується, використовують її значення в даних точках простору пошуку і не потрібно обчислень похідних або інших характеристик. Тому дані методи можуть бути застосовані до широкого класу функцій, зокрема до тих, що не мають аналітичного опису. Отже, методи генетичного пошуку є досить гнучкими і можуть бути застосовані до широкого кола задач, у тому числі до задач, для розв’язування яких не існує загальновідомих методів.
ГМ є більш ефективним інструментом пошуку порівняно з класичними методами оптимізації за таких умов:
— досліджуваний простір пошуку є великим, негладким (існують точки розриву) і неунімодальним (є кілька оптимумів);
— цільова функція пошуку може мати шуми;
— задача не вимагає знаходження надточного глобального оптимуму. Тобто необхідно досить швидко знайти прийнятне рішення, що досить часто має місце в реальних задачах.
Отже, генетичний пошук можна успішно використовувати для розв’язання комбінаторних задач, а також для пошуку оптимальних значень полімодальних функцій.
Генетичні методи мають такі переваги:
• проблемна незалежність і здатність показати при цьому добрі результати навіть за великої кількості симулятивно-технічних розв’язків задач оптимізації;
• великий простір рішень;
• невідомі властивості простору рішень;
• дискретні простори рішень, які не дозволяють застосування математичної числової оптимізації проблеми;
• безліч м’яких обмежень, тобто обмежень, які не обов’язково мають виконуватися, але бракує обліку яких може привести до погіршення результатів;
• кількість можливих рішень залежить від типу оптимізації, а також від кількості елементів безлічі визначень, які містять елементи, що підлягають оптимізації;
• головними ж перевагами ГА є те, що вони можуть застосовуватися для вирішення складних неформалізованих завдань, для яких не розроблено спеціальних методів, тобто ГА забезпечують розв’язання проблем. Але навіть у тих випадках, коли добре працюють існуючі методики, можна досягти цікавих результатів, поєднуючи їх з ГА;
• наявність у ГА цілої «популяції» розв’язків, спільно з імовірнісним механізмом мутації, дозволяють припускати меншу ймовірність знаходження локального оптимуму й більшу ефективність роботи на багатоекстремальному ландшафті. Сьогодні ГА успішно застосовують для розв’язання задач оптимізації у просторах з великою кількістю вимірювань, низки економічних завдань оптимального характеру, наприклад, завдань розподілу інвестицій;
• відсутність потреби у специфічних знаннях про розв’язувану задачу. Проте у разі, якщо додаткова інформація про досліджувану систему, об’єкт або процес є відомою, вона може бути використана в процесі пошуку;
• концептуальна простота та прозорість реалізації;
• можливість розпаралелювання;
• простота кодування вхідної і вихідної інформації. Некритичність до виду параметрів досліджуваних систем (можливість використання експертної, емпіричної, довідкової та іншої інформації про об’єкт, поданої різними типами даних);
• можливість застосування до великого кола задач без внесення серйозних змін у внутрішню структуру методу;
• можливість адаптивності параметрів генетичного пошуку до особливостей розв’язуваної задачі;
• менша імовірність потрапляння і зациклення в локальному оптимумі, що досягається за рахунок використання популяційного підходу;
• можливість застосування в методі інших пошукових процедур.
ГА не позбавлений певних недоліків.
Основна проблема, пов’язана з використанням ГА, — це їх евристичний характер. Говорячи більш строго, яка ймовірність досягнення популяцією глобального оптимуму в заданій галузі? На сьогодні не існує відповіді і теоретично обґрунтованих оцінок. Є припущення, що ГА може стати ефективною процедурою пошуку оптимального рішення, якщо:
— простір пошуку досить великий;
— завдання не вимагає знаходження глобального оптимуму, необхідно досить швидко знайти прийнятне «хороше» рішення, що досить часто трапляється в реальних завданнях.
ГА є в певному сенсі універсальним методом, тобто він явно не враховує специфіку задачі або має бути для неї налаштований.
До недоліків генетичного пошуку відносять:
• високу ітеративність;
• істотну залежність ефективності генетичного пошуку від його параметрів (чисельність популяції, початкова точка пошуку, імовірнісні характеристики генетичних операторів та ін.);
• епістазис — внутрішню залежність між змінними (генами), закодованими в хромосомі. Якщо гени не пов’язані один з одним, то вважається, що епістазис малий або взагалі не існує. У разі, якщо гени є взаємозалежними, то епістазис може створювати проблеми для генетичного пошуку, спричинені тим, що при схрещуванні ланцюжки взаємозалежних генів будуть зруйновані, що призводить до появи низько пристосованих нащадків. Розв’язання проблеми епістазису полягає в тому, аби зберігати в хромосомі взаємозалежні гени, розташовуючи їх близько один до одного. У разі групування залежних генів істотно знижується імовірність того, що вони будуть зруйновані при застосуванні схрещування;
• передчасна збіжність, пов’язана з недостатньою різноманітністю хромосом у популяції. Найпоширенішою причиною передчасної збіжності є недостатній розмір популяції. Тож, розв’язанням такої проблеми може бути збільшення кількості хромосом у популяції.
Ураховуючи особливості, переваги й недоліки оптимізаційних методів, можна надати такі рекомендації щодо вибору пошукового методу для розв’язання практичних задач ПСШІ:
— якщо простір пошуку є дискретним і невеликим за обсягом, можна скористатися методом повного перебору, який знайде найкраще рішення. Генетичний метод, на відміну від методу повного перебору, може з більшою імовірністю зійтися до локального оптимуму, а не до глобального. Проте генетичний пошук швидше знайде субоптимальне рішення, що знаходиться недалеко від дійсного оптимуму;
— якщо цільова функція в пошуковому просторі є гладкою і унімодальною, то будь-який градієнтний метод (наприклад, метод найшвидшого спуску) буде ефективнішим, ніж генетичний пошук;
— якщо про простір пошуку відома деяка додаткова інформація (наприклад, для задачі комівояжера), то методи пошуку, що використовують апріорні відомості про пошуковий простір, часто перевершують будь-який універсальний метод, у тому числі й генетичний;
— за досить складного рельєфу цільової функції методи пошуку, що працюють з єдиним рішенням на кожній ітерації (наприклад, простий метод спуску), можуть зациклитися в локальному рішенні. Генетичні методи працюють з набором із кількох рішень, тому вони мають менше шансів зійтися до локального оптимуму і надійно функціонують на багатоекстремальних поверхнях.
Проблема передчасного сходження пов’язана з недостатньою різноманітністю хромосом у популяції. Якщо більшість хромосом у популяції схожа між собою, то для селекції доступно менше робочого матеріалу, і коефіцієнт збільшення здоров’я знижується. Ви можете виявити ефект завчасного сходження, порівнявши середнє здоров’я популяції з максимальним здоров’ям. Якщо вони дуже схожі, це означає, що відбулося передчасне сходження популяції.
Найпоширенішою причиною передчасного сходження є дуже маленька чисельність популяції. Зі збільшенням чисельності популяції проблема легко розв’язується. Іншою причиною може бути алгоритм відбору, який ви застосовуєте. За викори-
Якщо жоден ген не пов’язаний з іншими генами в хромосомі, вважається, що епістазіс дуже малий або взагалі не існує. Якщо гени залежать один від одного, епістазіс високий і може створити проблеми для алгоритмів рекомбіювання.
Звичайне рішення цієї проблеми полягає в тому, щоб зберігати гени (змінні), які близько пов’язані один з одним у хромосомі. У разі групування залежних генів істотно знижується вірогідність того, що вони будуть зруйновані генетичними операторами, наприклад перехресного схрещування.
Основний недолік ГА полягає в залежності результату від вибору первинної популяції хромосом. Тобто у принципі не виключено, що за невдалого вибору первинної популяції і за відсутності в ній вдалої комбінації генів вдалу комбінацію генів ніколи не буде знайдено. У цьому випадку єдиний спосіб натрапити на таку комбінацію — це вдала мутація. Проте мутація — це випадковий процес, і її частота не може бути дуже великою — інакше відбуватиметься значне руйнування популяції «хороших» хромосом.
Проте ГА не гарантує знаходження глобального рішення за прийнятний час. ГА не гарантують і того, що знайдене рішення буде оптимальним. Тим не менше, вони застосовні для пошуку «досить хорошого» розв’язку задачі за «досить короткий час». ГА є різновидом алгоритмів пошуку і мають переваги над іншими алгоритмами за дуже великих обсягів завдань і відсутності впорядкованості в початкових даних, коли альтернативою їм є метод повного перебору варіантів.
У випадках, коли завдання може бути вирішене спеціально розробленим для неї методом, практично завжди такі методи будуть ефективніші за ГА як у плані швидкодії, так і за точністю знайдених рішень.
Генетичний алгоритм використовується для вирішення багатьох завдань оптимізації. Оскільки ефективність ГА багато в чому залежить від подання рішення, ви можете оптимізувати як числові, так і символічні завдання. Наприклад, крім простої функціональної оптимізації можна працювати з такими символічними завданнями, як завдання Ханойських Башт.
стання методу еліти вибираються тільки хромосоми з найкращим здоров’ям, що спричиняє значного зменшення чисельності популяції порівняно з початковою. Якщо популяція дуже рано зійшлася і рішення не було знайдено, вам слід перезапустити алгоритм. При перезапуску в популяцію буде введений новий матеріал, в якому може не бути великої кількості домінуючих хромосом.
Основними сферами застосування ГА є:
— вирішення комбінаторних завдань і завдань оптимізації; інструмент реалізації процесів оптимізації у моделюванні виробничих процесів — оптимізація послідовності, упорядкування та вибору (Simulationstool);
— як алгоритм знаходження екстремуму багатоекстремальної функції.
Генетичні алгоритми застосовують для розв’язання таких проблем:
• створення дизайну за допомогою комп’ютера;
• складання порядку розв’язання задач;
• економічні завдання і завдання теорії ігор;
• інші завдання оптимізації.
Приклад завдання оптимізації для генерації певної послідовності — це вироблення оптимальної послідовності завантаження однієї з виробничих ділянок. Відповідна модель симуляції надасть загальний час проходження завантаження для кожного запропонованого рішення. У процесі еволюції з’являтимуться все кращі й кращі послідовності, при яких завдання виконуються в найбільш короткі терміни.
Резюме за змістом теми
Відомою світовою школою, що представляє новий напрям в еволюційному моделюванні, є школа Dr. Candida Ferreira у Великобританії (www.gene-expression-programming.com). Основний напрям досліджень зосереджений у програмуванні генетичних виразів. Нові алгоритми, що розробляються представниками школи, використовують специфічних операторів комбінаторного пошуку, які включають інверсію, вставку та видалення генів і їх послідовностей, обмеження та узагальнення перестановок, які збільшують їх ефективність. Самі автори визначають програмування генетичних виразів (GEP) як мультиагентне генотип/фенотип кодування дерев виразів, пов’язаних приватною взаємодією. Відомо, що в простому випадку при одиничній довжині хромосоми, GEP еквівалентне ГА.
Найбільш відомою школою, в якій досліджують ГА, еволюційні стратегії, генетичне та еволюційне програмування, є лабораторія еволюційних обчислень Департаменту комп’ютерних наук в університеті Джорджа Мейсона США (http://www. cs.gmu.edu). Управління школою здійснює учень Джона Холланда Dr. K. De Jong.
Порівняно із звичайними оптимізаційними методами еволюційні алгоритми мають такі особливості: паралельний пошук, випадкові
Еволюційне програмування орієнтоване на оптимізацію неперервних функцій без використання оператора схрещування. Інший напрям еволюційного програмування пов’язаний з пошуком залежності цільових параметрів від інших змінних у формі функцій якогось певного вигляду. Наприклад, в одному з найбільш вдалих методів цього типу, методі групового врахування аргументів, залежність шукають у формі поліномів.
Від генетичних методів еволюційне програмування відрізняється не лише відсутністю схрещування, але й поданням особин популяції. Оскільки тут немає потреби у використанні хромосом, то особина часто є реальним рішенням без додаткового кодування. Наприклад, в еволюційному програмуванні як особини дуже часто використовують скінченні автомати. Відповідно оператори відбору і мутації застосовуються безпосередньо до них. При оптимізації функцій як особини популяції використовуються безпосередньо вектори дійсних чисел.
Терміни та поняття до теми
Еволюційний алгоритм — це оптимізаційний метод, що базується на еволюції популяції «особин».
Логічні (скінченні) автомати — це моделі, що описують засобами формальної логіки, можливі переходи досліджуваної системи з деякого початкового стану в завершальний.
Еволюційні інтелектуальні системи — це науковий напрям, що тільки формується та активно розвивається.
Ген — реально існуюча, незалежна одиниця спадковості, що комбінується й розщеплюється при схрещуваннях.
Хромосоми — структурні елементи клітинного ядра біологічних організмів, є носіями генів у клітинному ядрі особини.
Локус — місце, що займає ген у хромосомі.
Алелі — значення генів.
Популяція — досить велике співтовариство організмів, що схрещуються між собою.
Еволюція — термін, який позначає сукупність усіх змін у популяції організмів протягом поколінь.
Методи еволюційного моделювання — це скоріше не методи обробки даних, а загальний підхід до побудови моделей, який може використовуватися в різних методах.
мутації і рекомбінації вже знайдених хороших рішень. Вони добре підходять як простий евристичний метод оптимізації багатовимірних, погано визначених функцій. Формуються навіть цілі галузі застосування еволюційних алгоритмів. Наприклад, кілька років тому з’явився термін «Еволюційна роботика», що відображає можливості формування нейронної мережі робота, що управляє природним еволюційним шляхом.
Спадковість — здатність передавати з покоління в покоління спадкові ознаки, збереження й відтворення у нащадків основних ознак зовнішньої та внутрішньої будови, фізико-хімічних особливостей і життєвих функцій батьків.
Мінливість — це можливість змін невеликої частини ознак (мутацій), що забезпечує гнучкість і можливість розвитку.
Відбір — це перевірка результатів, той механізм, який дозволяє розділити хороші та погані властивості.
Схрещування — це спосіб створення об’єкта нащадка, за якого половина властивостей береться від одного об’єкта — батька, а друга — від іншого.
Генетичний алгоритм — це еволюційний алгоритм пошуку, що використовується для вирішення задач оптимізації і моделювання шляхом послідовного підбору, комбінування та варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію.
Питання для самоконтролю
1. Перелічіть галузі застосування еволюційного моделювання.
2. На яких принципах еволюції базуються ЕМ та відрізняються одна від одної?
3. Які особливості еволюційних алгоритмів?
4. У чому різниція між генетичними методами та еволюційним програмуванням?
5. Охарактеризуйте послідовність виконання еволюційного програмування.
6. Які три стадії включає вирішення завдань за допомогою ГА?
7. Виділіть етапи генетичного алгоритму.
8. Охарактеризуйте генетичні оператори відбору, схрещування і мутації.
9. У чому полягає природний відбір?
10. Які різновиди мутацій Ви знаєте?
11. Для розв’язання яких проблем застосовують ГА?
12. Проаналізуйте переваги та недоліки ГА.
Завдання для індивідуальної роботи, обов’язкові та додаткові практичні завдання
1. Які головні кроки включає узагальнена послідовність виконання еволюційного програмування?
2. Поясніть головні моделі виникнення молекулярногенетичних кібернетичних систем.
3. Які етапи генетичного алгоритму можна виділити?
4. У чому полягає основна ідея генетичного алгоритму?
5. За рахунок чого забезпечується паралельність пошуку на кожній ітерації генетичного алгоритму?
6. За якими критеріями можуть бути класифіковані методи еволюційного пошуку?
7. Поясніть, які методи генетичного програмування використовують генетичні оператори?
8. Дайте пояснення, які можуть бути застосовані оператори схрещування до бінарних хромосом?
9. Поясніть особливості основних еволюційних алгоритмів.
Література для поглибленого вивчення матеріалу
1. Сотник С. Л. Конспект лекцій з курсу «Основи проектування систем штучного інтелекту»: (1997—1998), [Електронний ресурс]: http://neuroschool.narod.ru/books/sotnik.html
2. Букатова І. Л. Еволюційне моделювання і його додатки. — М. : Наука, 1979. — 231 с.
3. Дубровін В. І. Методи оптимізації та їх застосування в задачах навчання нейронних мереж : навч. посіб. / В. І. Дубровін, С. О. Субботін.
— Запоріжжя : ЗНТУ, 2003. — 136 с.
4. Курейчик В. М. Генетические алгоритмы : монография. — Таганрог : ТРТУ, 1998. — 242 с.
5. Хайкин С. Нейронные сети : полный курс. — СПб. : Вильямс, 2005. — 1104 с.
6. Эволюционные методы компьютерного моделирования : монография / [А. Ф. Верлань, В. Д. Дмитриенко, Н. И. Корсунов, В. А. Шорох]. — К. : Наукова думка, 1992. — 256 с.
