На головну

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

Основоположником сучасної теорії генетичних алгоритмів (ГА) вважається Холланд (J. Holland), чия робота «Adaptation in Natural and Artificial Systems» (1975) стала класикою в цій області. У ній Холланд вперше ввів термін «генетичний алгоритм». Зараз описаний там алгоритм називають «класичний», іноді «канонічний» ГА, а поняття «генетичні алгоритми» стало дуже широким, і часто до них відносяться алгоритми, сильно відрізняються від класичного ГА. Учні Холланда Кеннет Де Йонг (Kenneth De Jong) і Девід Голдберг (David E. Goldberg) внесли величезний вклад в розвиток ГА. На книгу Голдберга «Genetic algorithms in search optimization and machine learning» (1989), посилаються автори практично кожної роботи по цій темі.

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

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

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

Розглянемо принципи роботи генетичного алгоритму на простому прикладі. Нехай потрібно знайти глобальний мінімум функції

y (x) = 5 - 24x + 17x2- 11x3/ 3 + x4/ 4 на відрізку [0; 7] (рис. 1).

На цьому відрізку функція приймає мінімальне значення в точці x = 1. У точці x = 6 функція потрапляє в локальний мінімум. Якщо для знаходження глобального мінімуму використовувати градієнтні методи, то в залежності від початкового наближення можна потрапити в даний локальний мінімум.

Для простоти припустимо, щоxприймає лише цілі значення, т. е. x ? {0, 1, 2, 3, 4, 5, 6, 7}. Це припущення істотно спростить виклад, зберігши всі основні особливості роботи генетичного алгоритму. Виберемо випадковим чином кілька чисел на відрізку [0; 7]: Числа {2, 3, 5, 4} будемо розглядати в якості пробних рішень нашої задачі. (В еволюції це називається вибір популяції)

Основною ідеєю генетичних алгоритмів є організація «боротьби за існування» і «природного відбору» серед пробних рішень. Запишемо вибрані пробні рішення в двійковій формі: {010, 011, 101, 100} (кодування).

Будемо застосовувати біологічну термінологію. Так, одне пробне рішення, записане в двійковій формі, ми будемо називати особиною або хромосомою, А набір всіх пробних рішень - популяцією. Як відомо, принцип природного відбору полягає в тому, що в конкурентній боротьбі виживає найбільш пристосований. У нашому випадку пристосованість особини визначається цільовою функцією: Чим менше значення цільової функції, тим більш пристосованою є особина (т. Е. Пробне рішення, яке використовували як аргумент цільової функції (див. Табл. 1)).

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

Для цього сформуємо з вихідної популяції шлюбні пари для схрещування, Поставивши у відповідність кожної особини вихідної популяції випадкове ціле число з діапазону від 1 до 4, яке будемо розглядати як номери членів популяції (табл.2). процес розмноження(Рекомбінація) полягає в обміні ділянками хромосом між батьками. Наприклад, нехай схрещуються дві хромосоми 111111 і 000000. Визначаємо випадковим чином крапку розриву хромосоми, нехай, це буде 3: 111 | 111, 000 | 000. Тепер хромосоми обмінюються частинами, що стоять після точки розриву, і утворюють двох нових нащадків: 111000 і 000111. Визначення місця розриву хромосом називається кросинговером.

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

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

випадковість будемо моделювати колесом рулетки. Нехай ймовірність мутації дорівнює 0,3. Для кожного нащадка візьмемо випадкове число на відрізку [0; 1], і якщо це число менше 0,3, то інвертуємо випадково обраний ген (замінимо 0 на 1 або навпаки) (табл. 3). Як видно, мутації здатні поліпшити (перший нащадок) або погіршити (четвертий нащадок) пристосованість особини-нащадка. Якщо в результаті схрещування хромосоми обмінюються «хвостами», т. Е. Молодшими розрядами в двійковому поданні числа, то в результаті мутацій зміни може зазнати будь-який розряд, в тому числі, старший. Таким чином, якщо схрещування призводить до відносно невеликих змін пробних рішень, то мутації можуть призвести до суттєвих змін значень пробних рішень (табл. 3).

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

деякі «елітні»Особини (рішення) можуть переходити в нову популяцію без відбору. Таким чином, через кілька поколінь ми отримаємо популяцію зі схожих і найбільш пристосованих особин.

Значення пристосованості найбільш «хорошою» особини (або середня пристосованість популяції) і буде рішенням нашої задачі. Слідуючи цьому, в даному випадку, взявши найбільш пристосовану особину 001 у другому поколінні, можна сказати, що мінімумом цільової функції є значення -5,42, відповідне аргументу x = 1. Тим самимпопадання в локальний мінімум вдалося уникнути!

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

Отже, основні принципи роботи ГА укладені в наступною схемою:

1. Проводиться ініціалізація початкового покоління. Генеруємо початкову популяцію з n хромосом.

2. Обчислюємо для кожної хромосоми її придатність.

3. Вибираємо пару хромосом-батьків за допомогою одного із способів

відбору.

4. Проводимо кроссинговер двох батьків з ймовірністю pс, виробляючи двох нащадків.

5. Проводимо мутацію нащадків з ймовірністю pm.

6. Повторюємо кроки 3-5, поки не буде згенеровано нове покоління популяції, що містить n хромосом

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

8. Повторюємо кроки 2-6, поки не буде досягнуто критерію закінчення процесу.

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

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

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

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

2-x бітний код Грея: 00, 01, 11,10 3-x бітний код Грея: 000, 001, 011, 010, 110, 111, 101, 100.

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

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

Критерій зупинки алгоритму.

· Знаходження глобального, або субоптимального рішення;

· Вичерпання числа поколінь, відпущених на еволюцію;

· Вичерпання часу, відпущеного на еволюцію.

кроссинговер. Операція рекомбінації хромосом на основі кросинговеру (хромосоми схрещуються, обмінюючись частинами рядків), що здійснюється з імовірністю РКР, Відноситься до схеми одноточечного кросинговеру. Зазвичай на практиці застосовується РКР = 0,6.

Природним розвитком одноточечного кросинговеру є схеми з декількома точками (двоточковий, триточковий і т. Д. Кроссинговер).

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

при двоточковому кросовері для батьківської пари випадковим чином вибираються 2 точки розділу, і батьки обмінюються проміжками між ними. В результаті виходять дві дитини. Зручно в цьому випадку представити рядки у вигляді кілець:

Острівна модель ГА

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

 



 Види імітаційного моделювання |  паралельні ГА

 методики IDEF |  Функціонально-вартісний аналіз (ФВА). |  Методи класичного твердотільного моделювання |  Ідея методу скінченних елементів |  Алгоритм складання еквівалентних схем |  Алгоритм складання еквівалентних схем |  Алгоритм складання еквівалентних схем |  Фактори, що створюють складність для ГА |  Рішення практичних завдань |  Виявлення фальсифікацій. |

© um.co.ua - учбові матеріали та реферати