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

Матеріал із MachineLearning.

популяції

Генетичний алгоритм(англ. genetic algorithm) - це евристичний алгоритм пошуку, що використовується для вирішення задач оптимізації та моделювання шляхом послідовного підбору, комбінування та варіації шуканих параметрів з використанням механізмів, що нагадують біологічну еволюцію. Є різновидом еволюційних обчислень (англ. evolutionary computation). Відмінною особливістю генетичного алгоритму є акцент на використання оператора «схрещування», який здійснює операцію рекомбінації рішень-кандидатів, роль якої аналогічна ролі схрещування у живій природі.

Зміст

Постановка задачі

Дляфункції пристосованостіу просторі пошуку потрібно знайти (або ).

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

  1. Випадковим чином генерується кінцевий набір пробних рішень: (перше покоління - розмір популяції).
  2. Оцінка пристосованості поточного покоління:
  3. Вихід, якщо виконується критерій зупинки, інакше
  4. Генерація нового покоління за допомогою операторів селекції, схрещування та мутацій: та перехід до пункту 2.

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

Інші позначення

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

Зустрічаються такі позначення:

  • Функція пристосованості (Fitness) – цільова функція;
  • Особина- пробне рішення;
  • Населення - все покоління, які роблять внесок у наступне. Найчастіше покоління та населення - синоніми;
  • Ген-компонент вектора простору пошуку;
  • Схрещування - кросинговер (crossingover).

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

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

Детальний опис алгоритму

Кодування простору пошуку

У ГА часто використовують такі типи кодування компонентів простору пошуку:

  • Бінарний, якщо ознака сама по собі є бінарною;
  • Чисельний у двійковій системі. Розширений варіант бінарного, де використовується фіксована кількість біт. Найпростіший у реалізації, але має суттєвий недолік (див. нижче);
  • Кодування кодом Грея. Позбавляє проблем попереднього варіанту, але додає накладні витрати на кодування/декодування;
  • З небінарними операторами схрещування та мутацій:
  • Числа з плаваючою комою. Використовуються у разі, коли масштаб зміни ознаки заздалегідь не відомий;
  • Номінальні типи та більш абстрактні сутності;
  • Типи з автопідстроюванням.

    • Початкова популяція

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

    Оцінка пристосованості

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

    Оператор відбору (селекції)

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

    Оператор схрещування

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

    • В одноточковому варіанті, результатом схрещування батьків у -ій популяції стануть два

    елемента популяції такі , де точка вибирається випадково. У двоточковому варіанті відповідно точок перетину буде дві, і вони також вибираються випадково. Легко розширити цю конструкцію до n точок. Слід зазначити, що у разі непарного n, відбувається n+1-точковий кросинговер з n+1-ой точкою між останньою і першою компонентами.

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

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

    • У безперервному просторі можна ввести таку аналогію для схрещування:

    , Де - щільність генофонду к-ої популяції, - відстань між двома особинами з генами x і y, M_c - матриця сили схрещування.

    Оператор мутацій

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

    • Інвертує біт у разі бінарної ознаки.
    • Змінює на деяку величину числову ознаку. Причому швидше на найближчий.
    • Замінить на іншу номінальну ознаку.
    • У безперервному просторі можна запровадити таку аналогію:

    , Де - щільність генофонду до-ої популяції, M_c - матриця сили мутацій.

    Критерії зупинки

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

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

    Плоїдність

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

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

    • Ускладнення алгоритму;
    • Потребує більшого числаітерацій до сходження в екстремум

    Найпростіший приклад ГА

    Підбір ключа 2048 біт

    Ефективність генетичних алгоритмів

    Холланд недвозначно пише[1], що за інших рівних умов ГА працюватиме гірше, ніж спеціальний алгоритм, розрахований на конкретне завдання (тип ознак, цільову функцію). Наприклад, повний перебір кінцевого невеликого простору або будь-який ефективний алгоритм спуску буде завжди ефективнішим за ГА. Тим не менш, у ситуації, коли про завдання нічого a priori не відомо, можна покладатися на результат роботи найпростішого генетичного алгоритму як наближення.

    Існують певний клас функцій (Hyperplane-defined functions, Holland), з яким за прийнятний час [2] справляються лише генетичні алгоритми.

    Тестові функції

    У процесі розробки ефективної реалізації генетичного алгоритму виникає необхідність простої тестової функції, яка

    1. враховує всі сильні сторони ГА (багатомірна, багатоекстремальна тощо);
    2. має аналітичне точне рішення.
    3. проста в реалізації
    4. її проблематично "зламати"

    Найбанальніша, сферична функція моментально вирішується будь-яким алгоритмом спуску. Багатоекстремальна. Подібних функцій можна вигадати(і було придумано) велику кількість, але невелика кількість з них задовольняє потрібним вимогам. Холландером було запропоновано функції HDR[3], які спочатку будуються з метою забезпечення всіх висунутих умов.

    Конвергенція з генетикою та синтетичної теорії еволюції

    Прообраз генетичного алгоритму прийшов з біології і, безперечно, продовжує «підглядати» звідти відповіді на багато питань, що виникають при проектуванні ефективних генетичних реалізаційалгоритмів. Більше того, ідеї щодо оптимізації ГА знаходять підтвердження і в біологів. Наприклад, такі явища як га- і квадру-плоїдні набори хромосом, інцест, подвоєння гена, управління швидкістю мутацій, тригери і т.п. Тим не менш, математика та кібернетика дозволяє вийти за межі хімічної реальності клітини та уявити n-плоїдний набір хромосом, об'єктні сутності замість генів тощо.

    Нейронні мережі та еволюційне моделювання

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

    Аналогія з іншими алгоритмами

    У разі відключеного кросинговера ГА починає поводитись за образом випадкового пошуку. Також ГА має аналогію з випадковим пошуком з адаптацією. Багато стохастичних алгоритмах можна знайти аналогію з ГА.