Генетичний алгоритм

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

Особливістю генетичного алгоритму є акцент на використання оператора "схрещення", який виконує операцію рекомбінацію рішень-кандидатів, роль якої аналогічна ролі схрещення в живій природі. "Батьком-засновником" генетичних алгоритмів вважається Джон Голланд (англ. John Holland), книга якого "Адаптація в природних і штучних системах" (англ. Adaptation in Natural and Artificial Systems) є фундаментальною в цій сфері досліджень.

Опис алгоритму

Задача кодується таким чином, щоб її вирішення могло бути представлено в вигляді масиву подібного до інформації складу хромосоми. Цей масив часто називають саме так «хромосома». Випадковим чином в масиві створюється деяка кількість початкових елементів «осіб», або початкова популяція. Особи оцінюються з використанням функції пристосування, в результаті якої кожній особі присвоюється певне значення пристосованості, яке визначає можливість виживання особи. Після цього з використанням отриманих значень пристосованості вибираються особи допущені до схрещення (селекція). До осіб застосовується "генетичні оператори" (в більшості випадків це оператор схрещення (crossover) і оператор мутації (mutation), створюючи таким чином наступне покоління осіб. Особи наступного покоління також оцінюються застосуванням генетичних операторів і виконується селекція і мутація. Так моделюється еволюційний процес, що продовжується декілька життєвих циклів (поколінь), поки не буде виконано критерій зупинки алгоритму. Таким критерієм може бути:

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

Генетичні алгоритми можуть використатися для пошуку рішень в дуже великих і тяжких просторах пошуку.

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

Етапи генетичного алгоритму

Можна виділити такі етапи генетичного алгоритму:

1. Створення початкової популяції:
2. Обчислення функції пристосованості для осіб популяції (оцінювання)
3. Повторювання до виконання критерію зупинки алгоритму:

1. Вибір індивідів із поточної популяції (селекція)
2. Схрещення або/та мутація
3. Обчислення функції пристосовуваності для всіх осіб
4. Формування нового покоління

Створення початкової популяції

Перед першим кроком необхідно отримати з життя або випадковим чином створити деяку початкову популяцію. Навіть якщо популяція здасться зовсім не конкурентною, генетичний алгоритм все одно достатньо швидко переведе її в придатну для життя популяцію. Таким чином, на першому кроці можна не особливо старатися зробити надто вже пристосованих осіб, достатньо, щоб вони відповідали формату осіб популяції, і на них можна було вирахувати функції пристосованості (Fitness). Наслідком першого кроку є популяція H, що налічує N осіб.

Відбір

На етапі відбору необхідно із всієї популяції вибрати її певну долю, яка залишиться в «живих» на цьому етапі популяції. Є декілька способів провести відбір. Ймовірність виживання особи h повинна залежати від значення її пристосованості Fitness(h). Сама ж доля відібраних s зазвичай є параметром генетичного алгоритму, і її просто задають заздалегідь. Внаслідок відбору із N осіб популяції H повинні залишитись sN осіб, які ввійдуть в наступну популяцію H'. Решта осіб «загине».

Розмноження

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

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

Приклад операції розмноження: Вибрати (1-s)p/2 пар гіпотез із H і провести з ними розмноження, отримавши по два нащадка від кожної пари (якщо розмноження описано так, щоб давати одного нащадка, необхідно вибрати (1 - s)p пар), і добавити цих нащадків в H'. В результаті H' буде складатися з N осіб.

Особи для розмноження зазвичай вибираються із всієї популяції H, а не із тих, що вижили на першому кроці (хоча останній варіант теж має право на існування). Справа в тому, що головна проблема генетичних алгоритмів - недостача різноманітності (diversity) в особах. Достатньо швидко виділяється єдиний генотип, який представляє собою локальний максимум і згодом всі елементи популяції програють йому в відборі, і вся популяція "забивається" копіями цієї особи. Існують різні способи боротьби із таким небажаним ефектом; один з них - вибір для розмноження не з самих "пристосованих", а взагалі зі всіх осіб.

Мутації

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

Застосування генетичних алгоритмів

Генетичні алгоритми застосовується для вирішення наступних задач:

1. Оптимізація функцій
2. Оптимізація запитів в базах даних
3. Різноманітні задачі на графах (задача комівояжера, розфарбування)
4. Налаштування і навчання штучної нейронної мережі
5. Задачі компоновки
6. Створення розкладів
7. Ігрові стратегії
8. Апромоксація функцій
9. Штучне життя
10. біоінформатика (згортання білків)

Приклад простої реалізації на C++

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

# include <iostream.h>
# include <algorithm.h>
# include <numeric.h>
using namespace std;
int main()
{
    //початковий масив (популяція) з 1000 елементів (осіб). 
    const int N = 1000;
    int a[N];
    //заповнимо елементи нулями
    fill(a, a+N, 0);
    for (;;)
    {
        //Мутація кожного елемента. 
        //Випадково збільшуємо або зменшуємо значення елементу на один;
        for (int i = 0; i < N; ++i)
            if (rand()%2 == 1)
                a[i] += 1;
            else
                a[i] -= 1;
        //відсортуванням по зростанню вибираємо більші за значенням... 
        sort(a, a+N);
        //... і тоді більші за значенням виявляться в другій частині масиву.
        //скопіюємо більші в першу половину, коли вони залишили нащадків, а перші померли:
        copy(a+N/2, a+N,    a /*куди*/);
        //тепер поглянемо на середнє значення елементу популяції. Як бачимо, середнє значення все більше і більше.
        cout << accumulate(a, a+N, 0) / N << endl;
    }
}

Дивіться також

• Задача оптимізації
• Теорема схем
• Фітнес-функція

Посилання

• Poli, R., Langdon, W. B., McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4. 
• Субботін С.О., Олійник А.О., Олійник О.О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С.О. Субботіна. – Запоріжжя: ЗНТУ, 2009. – 375 с.
• Генетичний алгоритм, каталог посилань Open Directory Project