Структура генетичного алгоритму

 

ГА включає три основні стадії, перша з яких передбачає подання окремих потенційних рішень у спеціальному вигляді, зручному для виконання еволюційних операцій зміни й відбору. На рисунку 9.1 представлена максимально узагальнена структурна схема генетич­ного алгоритму.

 

 

Рисунок 9.1 – Узагальнена структурна схема генетичного алгоритму.

 

Так як ГА – це проста модель еволюції в природі, у ньому використовуються як аналог механізму генетичного спадку­вання, так і аналог природного відбору. При цьому зберігається біологічна термінологія в спрощеному вигляді (таб. 9.1).

 

Таблиця 9.1 – Перелік термінів які використовуються при описі ГА

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

З урахуванням спеціальних термінів (таб.9.1) узагальнену структурну схему ГА можна представити в наступному вигляді (рисунок 9.2).

 

 

 

Рисунок 9.2 – Узагальнена структурна схема генетичного алгоритму (з використанням спеціальних термінів).

 

Деталізуємо структурну схему ГА (рисунок 9.3).

Алгоритм представлений на рисунок 9.3 відбиває основні прин­ципи генетичного пошуку. Його конкретні реалізації можуть відрі­знятися залежно від завдання.

Опишемо коротко основні етапи й операції ГА

 

Рисунок 9.3 – Деталізована структурна схема генетичного алгоритму.

 

Попереднім етапом роботи ГА є кодування. Кодування визначає структуру хромосоми.

ГА працюють із сукупністю особин – популяцією, кожна з особин представляє можливе рішення поставленого завдання.

На першому етапі роботи самого ГА випадковим чином генеру­ється вихідна популяція особин (хромосом). Для оцінки ефек­тивності хромосом (особин) за допомогою спеціальної мате­матичної моделі (функції) визначається ступінь пристосовано­сті кожного рішення, дана операція вимагає попередньо деко­дування хромосом. Кожна особина оцінюється мірою її присто­сованості відповідно тому, наскільки "добре" відповідне їй рі­шення завдання. У природі це еквівалентно оцінці того, наскі­льки ефективний організм при конкуренції за ресурси.

Після визначення ефективності всіх хромосом (особин) проводиться перевірка того, чи не досягнуто кінцевий резуль­тат (рішення завдачі). Якщо поставлене задача вирішена ро­бота алгоритму припиняється, інакше на наступному кроці проводиться відбір найбільш пристосованих особин (відсі­вання найменш пристосованих).

Після відбору особини, що залишилися, піддаються гене­тичним перетворенням з використанням генетичних операцій схрещування й мутації. У результаті чого з'являються нові особини. Популяція поповнюється новим поколінням. Для но­вих особин оцінюється їхня ефективність, після чого вони бе­руть участь у подальшій конкуренції усередині популяції. Найбільш пристосовані особини одержують можливість "відтво­рювати" потомство з більшою ймовірністю (це стосується схре­щування). У зв'язку із чим нові особини сполучають у собі деякі характеристики, наслідувані ними від батьків. Таким чином, з покоління в покоління, гарні характерис­тики поширюються по всій популяції. Схрещування найбільш пристосованих особин призводить до того, що досліджуються найбільш перспективні ділянки простору пошуку. В остаточ­ному підсумку популяція буде сходитися до оптимального рі­шення задачі.

Робота ГА являє собою ітераційний процес, що триває доти, поки не пройде завдана кількість поколінь або буде виконаний який–небудь інший критерій зупинки (задовольняючий вимогам рішення поставленої задачі).