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

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

Ідея генетичних алгоритмів (ГА) з 'явилася досить давно (1950-1975 рр.), але по-справжньому об' єктом вивчення вони стали тільки в останні десятиліття. Першовідкривачем в цій області визнано вважати Д.Холланда, який запозичив багато з генетики і адаптував під обчислювальні машини. ГА широко використовуються в системах штучного інтелекту, нейронних мережах і завданнях оптимізації.

Еволюційний пошук

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

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

Навіщо потрібні генетичні алгоритми

ГА переслідують такі цілі:

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

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

Особливості ГА

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

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

Критерії роботи

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

  1. Виконує визначену кількість ітерацій.
  2. Якість знайденого рішення відповідає вимогам.

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

Базова термінологія

З огляду на те, що ГА засновані на генетиці, то і велика частина термінології відповідає їй. Будь-який генетичний алгоритм працює виходячи з початкової інформації. Безліч початкових значень є популяція Пt = {п1, п2,..., пn}, де пi = {г1,..., v}. Розберемо детальніше:

  • t - це номер ітерації. t1,..., tk - означає ітерації алгоритму з номера 1 по k, і на кожній ітерації створюється нова популяція рішень.
  • n - розмір популяції Пt.
  • п1,..., пi - хромосома, особина, або організм. Хромосома або ланцюжок - це закодована послідовність генів, кожен з яких має порядковий номер. При цьому слід мати на увазі, що хромосома може бути приватним випадком особини (організму).
  • v - це гени, які є частиною закодованого рішення.
  • Локус - це порядковий номер гена в хромосомі. Алель - значення гена, яке може бути як числовим, так і функціональним.

Що означає "" закодований "" в контексті ГА? Зазвичай будь-яке значення кодується на основі будь-якого алфавіту. Найпростішим прикладом є переведення чисел з десятеричної системи обчислення в двійкове уявлення. Таким чином алфавіт представляється як безліч {0, 1}, а число 15710 кодуватиметься хромосомою 100111012, що складається з восьми генів.

Батьки і нащадки

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

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

Функція пристосованості

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

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

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

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

Базовий генетичний алгоритм

Розкладемо по кроках найбільш простий (класичний) ГА.

  1. Ініціалізація початкових значень, тобто визначення первинної популяції, того безлічі особин, з якими відбуватиметься еволюція.
  2. Встановлення первинної пристосованості кожної особи в популяції.
  3. Перевірка умов припинення ітерацій алгоритму.
  4. Використання функції селекції.
  5. Застосування генетичних операторів.
  6. Створення нової популяції.
  7. Кроки 2-6 повторюються в циклі до виконання необхідної умови, після чого відбувається вибір найбільш пристосованої особи.

Пройдемося коротко по мало очевидних частинах алгоритму. Умов припинення роботи може бути дві:

  1. Кількість ітерацій.
  2. Якість рішення.

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

  1. Для кожної пари батьків, що містять L генів, випадковим чином вибирається точка схрещування Тскi.
  2. Перший нащадок складається шляхом приєднання до [1; Тськи] генам першого батька [Тскi + 1; L] генів другого батька.
  3. Другий нащадок складається зворотним шляхом. Тепер до генів другого батька [1; Тскi] додається гени першого батька на позиціях [Тскi + 1; L].

Тривіальний приклад

Вирішимо завдання генетичним алгоритмом на прикладі пошуку особини з максимальним числом одиниць. Нехай особина складається з 10 генів. Задамо первинну популяцію в кількості восьми особин. Очевидно, найкращою особиною повинна бути 1111111111. Складемо для рішення ГА.

  • Ініціалізація. Виберемо 8 випадкових особин:

п1

1110010101

п5

0101000110

п2

1100111010

п6

0100110101

п3

1110011110

п7

0110111011

п4

1011000000

п8

0100001001

  • Оцінка пристосованості. Очевидно, в нашому генетичному алгоритмі функція придатності F буде підраховувати кількість одиниць у кожній особині. Таким чином, маємо:

пі

1

2

3

4

5

6

7

8

F (пi)

6

7

8

3

4

5

7

3

З таблиці видно, що особини 3 і 7 мають найбільше число одиниць, а значить є найбільш підходящими членами популяції для вирішення завдання. Оскільки на даний момент рішення необхідної якості немає, алгоритм продовжує роботу. Необхідно провести селекцію особин. Для простоти пояснення нехай селекція відбувається випадковим чином, і ми отримуємо вибірку особин {п7, п3, п1, п7, п3, п7, п4, п2} - це батьки для нової популяції.

  • Використання генетичних операторів. Знову для простоти покладемо, що ймовірність мутацій дорівнює 0. Іншими словами всі 8 особин передають свої гени такими, які є. Для проведення схрещування, складемо пари особин випадковим чином: (п2, п7), (п1, п7), (п3, п4) і (п3, п7). Так само випадковим способом вибираються точки схрещування для кожної пари:

Пара

(п2, п7)

(п1, п7)

(п3, п4)

(п3, п7)

Батьки

[1100111010]

[0110111011]

[1110010101]

[0110111011]

[1110011110]

[1011000000]

[1110011110]

[0110111011]

Тськи

3

5

2

8

Нащадки

[1100111011]

[0110111010]

[1110011011]

[0110110101]

[1111000000]

[1010011110]

[1110011111]

[0110111010]

  • Складання нової популяції, що складається з нащадків:

п1

1100111011

п5

1111000000

п2

0110111010

п6

1010011110

п3

1110011011

п7

1110011111

п4

0110110101

п8

0110111010

  • Оцінюємо пристосованість кожної особи нової популяції:

пі

1

2

3

4

5

6

7

8

F (пi)

7

6

7

6

4

6

8

6

Подальші дії очевидні. Найцікавіше в ГА відкривається в разі, якщо оцінити середню кількість одиниць в кожній популяції. У першій популяції в середньому на кожну особину припадало 5,375 одиниць, в популяції нащадків - 6,25 одиниць на особину. І така особливість буде спостерігатися навіть у випадку, якщо в ході мутацій і схрещування особина з найбільшим числом одиниць у першій популяції загубиться.

План реалізації

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

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

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

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

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

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

Ефективність

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

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

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