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

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

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

Історія

Перші спроби симуляції еволюції були проведені у 1954 році Нільсом Баричеллі на комп'ютері, встановленому в Інституті перспективних досліджень Прінстонського університету. Його робота, що була опублікована у тому ж році, привернула увагу громадськості. З 1957 року, австралійський генетик Алекс Фразер опублікував серію робіт з симуляції штучного відбору серед організмів з множинним контролем вимірюваних характеристик. Це дозволило комп'ютерній симуляції еволюційних процесів та методам, які були описані у книгах Фразера та Барнела(1970) та Кросбі(1975), з 1960-х років стати більш розповсюдженим видом діяльності серед біологів. Симуляції Фразера містили усі найважливіші елементи сучасних генетичних алгоритмів. До того ж, Ганс-Іоахім Бремерман в 1960-х опублікував серію робіт, які також приймали підхід використання популяції рішень, що піддаються відбору, мутації та рекомбінації, в проблемах оптимізації. Дослідження Бремермана також містили елементи сучасних генетичних алгоритмів. Також варто відмітити Річарда Фрідберга, Джоржа Фрідмана та Майкла Конрада^{[джерело?]}.

Хоча Баричеллі у своїй роботі 1963 р. займався симуляцією можливості машини грати у просту гру, штучна еволюція стала загальновизнаним методом оптимізації після роботи Інго Рехенберга та Ханса-Пауля Швереля у 60-х та на початку 70-х років двадцятого століття — група Рехенсберга змогла вирішити складні інженерні проблеми згідно зі стратегіями еволюції. Іншим підходом була техніка еволюційного програмування Лоренса Дж. Фогеля, яка була запропонована для створення штучного інтелекту. Еволюційне програмування, яке спочатку використовувало кінцеві автомати для передбачення обставин, та використовували різноманіття та відбір для оптимізації логіки передбачення. Генетичні алгоритми стали особливо відомі завдяки роботі Дж. Холанда на початку 70-х років та його книзі «Адаптація у природніх та штучних системах» (1975).Його дослідження були основані на експериментах з клітинними автоматами та на його роботах, що були написані в університеті Мічігану. Він ввів формалізований підхід для передбачення якості наступного покоління, відомий як Теорема схем. Дослідження в області генетичних алгоритмів залишалось більше теоретичним до середини 80-х років, коли була, нарешті, проведена Перша міжнародна конференція з генетичних алгоритмів (Піттсбург, Пенсильванія (США)).

З ростом дослідницького інтересу суттєво виросла обчислювальна потужність комп'ютерів, що дозволило використовувати нову обчислювальну техніку на практиці. Наприкінці 80-х років, компанія General Electric почала продаж першого в світі продукту, який працював з використанням генетичного алгоритму. Це був набір промислових обчислювальних засобів. В 1989 інша компанія Axcelis, Inc. випустила Evolver — перший у світі комерційний продукт на генетичному алгоритмі для персональних комп'ютерів. Журналіст The New York Times в технологічній сфері Джон Маркофф писав про Evolver у 1990 році.

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

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

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

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

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

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

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

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

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

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

Перед першим кроком необхідно випадковим чином створити деяку початкову популяцію. Навіть якщо популяція виявиться абсолютно неконкурентоздатною, генетичний алгоритм все одно достатньо швидко переведе її в придатну для життя популяцію. Таким чином, на першому кроці можна не старатися зробити надто пристосованих осіб, достатньо, щоб вони відповідали формату осіб популяції, і на них можна було порахувати функцію пристосованості (фітнес функцію). Наслідком першого кроку є популяція 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