Поняття генетичного алгоритму. Генетичні оператори: селекція, кросовер, мутація, інверсія

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

Припустимо, у нас є складна цільова функція (ЦФ) залежна від декількох змінних. Вимагається вирішити завдання на оптимізацію (ЦФ прагне до max або min). Кожен набір значень змінних (х1, х2,…,xn) - це особина, яка бере участь в еволюції, іншими словами, її набір генів в хромосомі. Значення ЦФ - пристосованість цієї особини. В процесі еволюції пристосованість (значення ЦФ) зростає. Зупинивши еволюцію і вибравши кращий варіант можна отримати досить не погане рішення задачі.

Популяція - це кінцева безліч особин.

Особини, що входять в популяцію, в генетичних алгоритмах представляються хромосомами із закодованим в них безліччю параметрів завдання, тобто рішень, які інакше називаються точками в просторі пошуку, - генетичний код(набір хромосом) або варіант рішення задачі.

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

Ген (що також називається властивістю, знаком або детектором) - це атомарний елемент генотипу, зокрема, хромосоми.

Генотип або структура - це набір хромосом цієї особини. Отже, особинами популяції можуть бути генотипи або одиничні хромосоми(у досить поширеному випадку, коли генотип складається з однієї хромосоми).

Фенотип - це набір значень, що відповідають цьому генотипу, тобто декодована структура або безліч параметрів завдання(рішення, точка простору пошуку).

Існує безліч генетичних операторів отримання потомства, що має властивості своїх батьків. Основними є селекція, кросовер і мутація.

Оператор селекція відбирає в популяції найкращі хромосоми для відтворення. Основний принцип селекції - чим вище пристосованість особини, тим більше потомства вона дасть.

Власне відтворення ведеться за допомогою оператора кросовера – схрещування (crossover). При схрещуванні два рішення-кандидати діляться на декілька частин і обмінюються цими частинами, результатом стають два нові кандидати.

При операції схрещування шаблонів бітових рядків довжини 8 цих рядків діляться на дві рівні частини, після чого формуються два нащадки, що містять по одному сегменту кожного з батьків. Помітимо, що розбиття батьківських особин на дві рівні частини- це досить довільний вибір. Рішення-кандидати можуть розбиватися у будь-якій точці, яку можна вибирати і змінювати випадковим чином в ході рішення задачі.

Припустимо, що цільовий клас - це набір усіх рядків, які починаються і закінчуються одиницею. Проте перший їх нащадок набагато точніше відповідає критерію якості, чим будь-який з батьків : за допомогою цього шаблону не буде пропущений жоден з цільових прикладів, а нерозпізнаними залишаться значно менше рядків, чим в реальному класі рішення.

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

Мутація(mutation) - це ще один важливий генетичний оператор. Вона полягає у випадковому виборі кандидата і випадковій зміні деяких його властивостей. Наприклад, мутація може полягати у випадковому виборі біта в шаблоні і зміні його значення з 1 на 0 або #. Значення мутації полягає в можливому заповненні важливих компонентів рішення, відсутніх в початковій популяції.

Якщо в розглянутому вище прикладі жоден з членів початкової популяції не містить 1 в першій позиції, то в процесі схрещування не можна отримати нащадка, що має цю властивість. Значення першого біта може змінитися лише внаслідок мутації. Цієї мети можна також досягти за допомогою іншого генетичного оператора – інверсії (inversion), який полягає в тому, що хромосома ділиться на дві частини, і потім вони міняються місцями.

Робота генетичного алгоритму триває до того часу, поки не буде досягнута умова його завершення, наприклад, для одного або декількох кандидатів значення критерію якості не перевищить деякого порогу.

Операції селекції, кросовера, мутації і інверсії відносяться до операторів класичного генетичного алгоритму, проте є ще один, дуже важливий оператор введений пізніше - оператор элитизма, що дозволяє особинам що має найбільшу пристосованість, без зміни переходити в наступне покоління.

Приведемо типову схему ГА :

1 Генерація початкової популяції - заповнення популяції особинами, в яких елементи масиву X(біти) заповнені випадковим чином.

2 Вибір батьківської пари - тобто беремо K особин з максимальними значеннями функції F і складаємо з них усі можливі пари. Застосування кросовера до усіх особин.

3 Кросовер(у літературі по генетичних алгоритмах також вживається назва кросовер або схрещування) - це операція, при якій з двох хромосом породжується одна або декілька нових хромосом. Чим більш пристосавана особина, тим більш вірогідності що вона братиме участь в кросовері.

Рішення завдань методом ГА закінчується тоді, коли пристосованість помітно збільшується. Таке рішення вважається кращим варіантом.