Структура генетичного алгоритму
ГА включає три основні стадії, перша з яких передбачає подання окремих потенційних рішень у спеціальному вигляді, зручному для виконання еволюційних операцій зміни й відбору. На рисунку 9.1 представлена максимально узагальнена структурна схема генетичного алгоритму.
Рисунок 9.1 – Узагальнена структурна схема генетичного алгоритму.
Так як ГА – це проста модель еволюції в природі, у ньому використовуються як аналог механізму генетичного спадкування, так і аналог природного відбору. При цьому зберігається біологічна термінологія в спрощеному вигляді (таб. 9.1).
Таблиця 9.1 – Перелік термінів які використовуються при описі ГА
Назва терміну | Визначення терміну |
Хромосома | Вектор шуканих параметрів системи представлений у закодованому вигляді (найчастіше у двійковій системі числення), даний вектор однозначно визначає стан системи й містить всі шукані параметри. Це варіант рішення завдання пошуку параметрів системи. |
Генотип | Рішення в закодованому вигляді (генотип визначається хромосомою). |
Фенотип | Рішення в розкодованому вигляді. Кожному генотипу відповідає свій фенотип. |
Особина (індивід) | У біології представник певного біологічного виду, що характеризується нерозривною єдністю генотипу й фенотипу. В еволюційному моделюванні особина також має генотип, який однозначно визначає пристосованість особини, і має сенс одного з можливих рішень розглянутого завдання. |
Ген | Фрагмент хромосоми, що кодує значення одного із шуканих параметрів системи. Хромосома складається з декількох генів. |
Локус | Окрема позиція (область) у хромосомі, яку може займати ген. |
Алель | У популяції завжди найдуться особини, у яких в ідентичних локусах представлені різні форми генів. Ці альтернативні форми й називаються алельними станами гена або просто алелями. Алель – це значення гена. Набір припустимих станів гена називають алельним алфавітом. |
Популяція | У біології це група особин одного виду, які мають однакову структуру генотипу й тому здатні взаємодіяти один з одним, наприклад, схрещуватися й давати потомство. В еволюційному моделюванні це набір особин (векторів–рішень, хромосом) конкуруючих між собою. Холланд використовував термін «вибірка». |
Схрещування (кросовер, кросинговер) | Генетична операція, при якій дві хромосоми обмінюються своїми частинами. У результаті виконання операції формується хромосома-нащадок, зібрана із фрагментів батьківських хромосом. |
Мутація | Це генетичний оператор, який вносить зміни в структуру копії батьківської хромосоми, модифікуючи значення окремих генів у рамках дозволеного алельного алфавіту й приводить до випадкової зміни однієї або декількох позицій у хромосомі або зміні порядку розташування генів. |
Епоха (поколін-ня) | Одна ітерація в обчислювальному процесі ГА (термін «покоління» може використовуватись в тому випадку якщо вживається в такому контексті: «пройшло 4-и покоління», «рішення було знайдено на 30-му поколінні»). |
Пристосо-ваність | Кількісна характеристика, що показує, наскільки успішно особина вирішує поставлене завдання, і що дозволяє зіставити її щодо цього з іншими особинами. Ступінь пристосованості визначається значенням функції пристосованості (функції відповідності, fitnes function). Кожній особині (хромосомі) ставиться у відповідність значення функції пристосованості. |
Відбір | Генетична операція яка передбачає відкидання (відсівання) частини особин (хромосом) з популяції, як правило відкидаються найменш пристосовані особини. |
З урахуванням спеціальних термінів (таб.9.1) узагальнену структурну схему ГА можна представити в наступному вигляді (рисунок 9.2).
Рисунок 9.2 – Узагальнена структурна схема генетичного алгоритму (з використанням спеціальних термінів).
Деталізуємо структурну схему ГА (рисунок 9.3).
Алгоритм представлений на рисунок 9.3 відбиває основні принципи генетичного пошуку. Його конкретні реалізації можуть відрізнятися залежно від завдання.
Опишемо коротко основні етапи й операції ГА
Рисунок 9.3 – Деталізована структурна схема генетичного алгоритму.
Попереднім етапом роботи ГА є кодування. Кодування визначає структуру хромосоми.
ГА працюють із сукупністю особин – популяцією, кожна з особин представляє можливе рішення поставленого завдання.
На першому етапі роботи самого ГА випадковим чином генерується вихідна популяція особин (хромосом). Для оцінки ефективності хромосом (особин) за допомогою спеціальної математичної моделі (функції) визначається ступінь пристосованості кожного рішення, дана операція вимагає попередньо декодування хромосом. Кожна особина оцінюється мірою її пристосованості відповідно тому, наскільки "добре" відповідне їй рішення завдання. У природі це еквівалентно оцінці того, наскільки ефективний організм при конкуренції за ресурси.
Після визначення ефективності всіх хромосом (особин) проводиться перевірка того, чи не досягнуто кінцевий результат (рішення завдачі). Якщо поставлене задача вирішена робота алгоритму припиняється, інакше на наступному кроці проводиться відбір найбільш пристосованих особин (відсівання найменш пристосованих).
Після відбору особини, що залишилися, піддаються генетичним перетворенням з використанням генетичних операцій схрещування й мутації. У результаті чого з'являються нові особини. Популяція поповнюється новим поколінням. Для нових особин оцінюється їхня ефективність, після чого вони беруть участь у подальшій конкуренції усередині популяції. Найбільш пристосовані особини одержують можливість "відтворювати" потомство з більшою ймовірністю (це стосується схрещування). У зв'язку із чим нові особини сполучають у собі деякі характеристики, наслідувані ними від батьків. Таким чином, з покоління в покоління, гарні характеристики поширюються по всій популяції. Схрещування найбільш пристосованих особин призводить до того, що досліджуються найбільш перспективні ділянки простору пошуку. В остаточному підсумку популяція буде сходитися до оптимального рішення задачі.
Робота ГА являє собою ітераційний процес, що триває доти, поки не пройде завдана кількість поколінь або буде виконаний який–небудь інший критерій зупинки (задовольняючий вимогам рішення поставленої задачі).