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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2014-01-04