РЕАЛІЗАЦІЯ ГЕНЕТИЧНИХ АЛГОРИТМІВ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 6
з дисципліни
„Експертні системи та автоматизовані системи навчання ”
для студентів базового напряму „Філологія”
спеціальності „Прикладна лінгвістика”
Затверджено
на засіданні кафедри інформаційних системи та мереж
Протокол №9 від 10.02.15
Реалізація генетичних алгоритмів: Методичні вказівки до лабораторної роботи № 6 / Укл.: Я.П.Кісь, В.А.Висоцька – Львів: Видавництво Національного університету ”Львівська політехніка”, 2015. – 44 с.
Укладачі
Кісь Я.П, к.т.н., доцент
Висоцька В.А., к.т.н., асистент
Відповідальний за випуск
Литвин В.В., завідувач кафедри ІСМ, д.т.н., професор
Рецензенти
Камінський Р.М., д.т.н., професор
Кравець П.О., к.т.н., доцент
(Для ознайомлення з повним текстом статті необхідно залогінитись)
1 Мета роботи
Вивчити призначення, особливості та способи реалізації генетичних алгоритмів.
Вступ
Природа вражає своєю складністю і багатством всіх своїх проявів. Серед прикладів можна назвати складні соціальні системи, імунні і нейронні системи, складні взаємозв'язки між видами. Вони - всього лише деякі з чудес, що стали більш очевидні, коли ми стали глибше досліджувати себе самих і світ навколо нас. Наука - це одна із систем віри, що змінює інші, якими ми намагаємось пояснити те, що спостерігаємо, цим самим, змінюючи себе, щоб пристосуватися до нової інформації, одержуваної з зовнішнього середовища. Багато чого з того, що ми бачимо і спостерігаємо, можна пояснити єдиною теорією: теорією еволюції через спадковість, змінність і відбір.
Теорія еволюції вплинула на зміну світогляду людей із самої своєї появи. Теорія, що Чарльз Дарвін представив у роботі, відомій як "Походження Видів", у 1859 році, стала початком цієї зміни. Багато областей наукового знання в даний час насолоджуються волею думки в атмосфері, що багатьом зобов'язана революції, викликаною теорією еволюції і розвитку. Але Дарвін, подібно багатьом своїм сучасникам, хто припускав, що в основі розвитку лежить природний відбір, не міг не помилятися. Наприклад, він не зміг показати механізм спадкування, при якому підтримується змінність. Його гіпотеза про пангенезис виявилася неправильною. Це було за п'ятдесят років до того, як теорія спадковості почала поширюватися по світу, і за тридцять років до того, як "еволюційний синтез" зміцнив зв'язок між теорією еволюції і відносно молодою наукою генетикою. Однак Дарвін виявив головний механізм розвитку: відбір у сполученні зі змінністю або, як він його називав, "спуск із модифікацією". У багатьох випадках, специфічні особливості розвитку через змінність і відбір все ще не безперечні, однак, основні механізми пояснюють неймовірно широкий спектр явищ, що спостерігаються в Природі.
Тому не дивно, що вчені, які займаються комп'ютерними дослідженнями, звернулися до теорії еволюції в пошуках натхнення. Можливість того, що обчислювальна система, наділена простими механізмами змінності і відбору, могла б функціонувати за аналогією з законами еволюції в природних системах, була дуже приваблива. Ця надія стала причиною появи ряду обчислювальних систем, побудованих на принципах природного відбору.
Історія еволюційних обчислень почалася з розробки ряду різних незалежних моделей. Основними з них були генетичні алгоритми і класифікаційні системи Голанда (Holland), опубліковані на початку 60-х років і які отримали загальне визнання після виходу у світ книги, що стала класикою в цій області, - "Адаптація в природних і штучних системах" ("Adaptation in Natural and Artifical Systems", 1975).
Головні труднощі з можливістю побудови обчислювальних систем, заснованих на принципах природного відбору і застосуванням цих систем у прикладних задачах, полягає в тому, що природні системи досить хаотичні, а всі наші дії, фактично, носять чітку спрямованість. Ми використовуємо комп'ютер як інструмент для рішення визначених задач, що ми самі і формулюємо та акцентуємо увагу на максимально швидкому виконанні при мінімальних витратах. Природні системи не мають ніяких таких цілей чи обмежень, у всякому разі, нам вони не відомі. Виживання в природі не спрямовано до деякої фіксованої мети, замість цього еволюція робить крок вперед у будь-якому доступному напрямку. Можливо це велике узагальнення, але я думаю, що зусилля, спрямовані на моделювання еволюції за аналогією з природними системами, до дійсного часу можна розбити на дві великі категорії:
Системи, що змодельовані на біологічних принципах. Вони успішно використовуються для задач функціональної оптимізації і можуть легко бути описані небіологічною мовою;
Системи, що є біологічно більш реалістичними, але які не виявилися особливо корисними в прикладному змісті. Вони більше схожі на біологічні системи і менш спрямовані (чи не спрямовані зовсім). Вони мають складну і цікаву поведінку, і, скоріше, незабаром набудуть практичного застосування.
Звичайно, на практиці ми не можемо розділяти ці речі так строго. Ці категорії - просто два полюси, між якими лежать різні обчислювальні системи. Ближче до першого полюса - еволюційні алгоритми, такі як Еволюційне Програмування (Evolutionary Programming), Генетичні Алгоритми (Genetic Algorithms) і Еволюційні Стратегії (Evolution Strategies). Ближче до другого полюса - системи, що можуть бути класифіковані як Штучне Життя (Artificial Life). Звичайно, еволюція біологічних систем не єдине "джерело натхнення" творців нових методів, що моделюють природні процеси.
Як відомо, еволюційна теорія затверджує, що життя на нашій планеті виникло спочатку лише в найпростіших формах - у вигляді одноклітинних організмів. Ці форми поступово ускладнювалися, пристосовуючись до навколишнього середовища, породжуючи нові види, і тільки через багато мільйонів років з'явилися перші тварини і люди. Можна сказати, що кожен біологічний вид з часом вдосконалює свої якості так, щоб найбільш ефективно справлятися з найважливішими задачами виживання, самозахисту, розмноження і т.д. Таким шляхом виникло захисне забарвлення в багатьох риб і комах, панцир у черепахи, отрута в скорпіона і багато інших корисних застосувань.
За допомогою еволюції природа постійно оптимізує все живе, знаходячи часом неординарніші рішення. Неясно, за рахунок чого відбувається цей прогрес, однак йому можна дати наукове пояснення, ґрунтуючись всього на двох біологічних механізмах - природного відбору і генетичного спадкування.
2 Еволюційні алгоритми
Генетичні алгоритми (анг. Genetic algorithms) становлять поряд з еволюційними стратегіями та еволюційним програмуванням один з трьох головних напрямків так званої стимульованої еволюції. Незважаючи на те, що кожний з трьох методів виник незалежно, всі вони мають спільні основні якості. В кожному з них представлений вид індивідумів котрий потім підлягає процесу селекції і різним так званим операторам генетичним (найчастіше мутації і/або схрещенню), шо веде до отримання шоразу кращих вирішень.
Еволюційні стратегії - це алгоритми, які розвивають в Німеччині, як методи розвязання проблем оптимізації, основаній на принципах натуральної еволюції . Еволюційне програмування - це підхід, що використовується в США, спочатку в застосуванні до закінчених автоматів, а пізніше різних оптимізаційних проблемах. Обидва методи винкли в 60-х роках.
Зосередимося на визначені основних схожостей і розбіжностей між еволюційними стратегіями і генетичними алгоритмами. Головною схожістю є звичайно те, що обидва методи оперують на популяціях потенційних розвязків та використовують основи селекції і перетворення найкраще пристосованих індивідумів. Але є багато різниць між цими двома підходами. Перша різниця стосується способу представлення індивідумів. Еволюційні стратегії діють на векторах чисел з плаваючою комою, а генетичні алгоритми оперують на векторах бінарних. Друга різниця між еволюційними стратегіями та генетичним алгоритмами прихована в процесі селекції. В еволюційних стратегіях створюється посередня популяція, що складаються з усіх батьків та певної кількосиі потомків створених в наслідок застосування генетичних операторів. Потім процес селекції формує розмір цієї посередньої популяції до величини популяції батьків шляхом усунення індвідумів, що найгірше пристосовані. Отримана таким чином популяція створює наступну генерацію . В генетичному алгоритмі порцедура селекції вибирає з популяції батьків таке саме число індивідумів, як кількість популяції батьків, при чому декотрі індивідуми (найкраще пристосовані) можуть бути вибрані багаторазово. Одночасно також найслабші індивідуми мають можливість потрапити до цієї популяції . Однак шанси вибору є пропорційними до пристосованості індивідумів. Незалежно від застосованого в генетичному алгоритмі методу селекції (метод кола рулетки або метод ранкінговий) найкраще пристосовані індивідуми можуть бути вибрані декілька разів . Натомість в еволюційних стратегіях індивідуми вибираються без повторень . В еволюційних стратегіях процедура селекції є детерміністичною, а в генетичних алгоритмах - випадковою.
Третя різниця між еволюційними стратегіями і генетичними алгоритмами стосується черговості силекції і рекомбінації (тобто зміни генів внаслідок впливу генетичних операторів). В еволюційних стратегіях спочатку відбувається процес рекомбінації, а потім селекції. В генетичних алгоритмах все навпаки . В еволюційних стратегіях потомок є результатом схрещення двох батьківських індивідумів та мутації . Стоворено таким способом посередня популяція, сладена з популяції батьків та отриманих потомків підлягає процедурі селекції, яка формує розмір цієї популяції до розміру популяції батьків . В генетичних алгоритмах спочатку відбувається селекція, що веде до створення перехідної популяції, а потім застосовують генетичні оператори (схрещення і мутація) до індивідумів (вбраних згідно з правдоподібністю схрещування) і генів (вибраних згідно з правдоподімності мутації). Наступна різниця між еволюційними стратегіями і генетичними алгоритмами полягає в тому, що параметри генетичних алгоритмів, такі як правдоподібність схрещування і правлоподібність мутації, залишаються постійними під час процесу еволюції, а в еволюційних стратегіях ці параметри підлягають постійній змінній (самоадаптація параметрів). Інша різниця між еволюційними стратегіями генетичними алгортмами стосується трактування обмежень прийнятих в розвязанні проблем оптимізації . В еволюційних стратегіях, якшо під час певної ітерації потомок не виконує всіх обмежень, його відкидають і не розташовують в новій популяції . Якщо такихпотомків є багато, то в евволюційній стратегії спонукають згадані вище параметри збільшувати наприклад правдоподібність схрещування . В генетичних алгоритмах ці параметри не змінюються. Замість цьго застосовується функція покарання індивідумів, що не виконують обмежень, шо має з рештою багато недоліків.
Визначаючи розбіжності між еволюційними стратегіями генетичними алгориитмами потрібно визнати, досліджуючи розвиток цих методів на протязі останніх років, що різноця поступово зникає . Нариклад, в багатьох застосуваннях генетичних алгоритмів до проблем оптимізації вживають змінно-променеві та різні здефінійовані оператори генетичні, щоб покращити функціонування систем, що діють на підставі цих цих алгоритмів. Так методи, шо значно відрізняються від класичного генетичного алгоритму надалі називають генетичними алгоритмами, хоча більш відповідним було би назвати їх алгоритмами еволюційними .
Еволюційне програмування, подібно до еволюційних стратегій, ставить за основу адаптування і різнорідність поведінок від батька до потомка в наступних генераціях. Подивимось, як діє стандартний алгоритм еволюційного програмування.
Випадково вибираємо посаткову популяцію розвязків. В проблемах оптимізації дійсних чисел (прикладом яких є наука нейронових мереж) інвивідум предсавлений як ланцюг дійсних чисел (хромосом). Ця популяція оцінюється відносно даної функції (функція пристосування). Потомки створюються з тих батьків шляхомвипадкової мутації . Селекція основана на пробабілістичних розіграшах (метод турніру), де кожний розвязок бере участь в перегонах з хромосомами випадково вибраними з популяціями . Розвязки, які перемогли (виявилися найкращими) стають батьками в наступній генерації . Процедура повторюється так довго поки отримується відповідний розвязок або вичерпується доступний час компютера .
Еволюційне програмування застосовують в оптимізації діяльності нейронових мереж . Воно не вимагає, подібно до інших методів основаних на еволюції, градованої інформації тому є придатним в проблемах, де така інформація є недосяжною або розрахунково важка чи дорога для отримання . Одним з найсучасніших використань еволюцйного програмування були проблеми штучного інтелекту .
Великими є подібності між еволюційними стратегіями і еволюційним програмуванням в застосуванні до проблем оптимізації безперервної функції . Деякі вчені твердять, що процедури в дійсності однакові, хоча були розвязані незалежно . Обидва методи кінцево подібні до гентичних алгоритмів . Основна різниця між еволюційним програмуванням генетичних алгоритмів полягає в тому, що еволюційне програмування не є звязане з особливістю репрезентації індивідума, ле оператор мутації не вмагає особливого способу кодування .
Перший контакт між групами осіб розвязується стратегією еволюції також еволюційним програмуванням мало місце на початку 1992 року, перед першою міжнародною конференцією на тему еволюцйного програмування . ці методи вирішувалися незалежно протягом 30-ти років . Між представлених різниць містится багато основних подібностей .
Всі три представлені методи, тобто генетичні алгоритми, еволюційнї стратегії та еволюційне програмування називаються еволюційними алгоритмами . Вживають також термін еволюційні методи .
Поняття еволюційні алгоритми включають в себе також інші методи основані на еволюції, наприклад генетичне програмування, будучи розширенням генетичного алгоритму в застосуванні до компютерних програм . В цьому методі популяція складається з закодованих відповідним способом компютерних програм, котрі підлягають генетичним операторам (схрещення, мутація) з метою пошуку оптимального розвязку, тобто програми найкрашої для розвязаного завдання . Програма оцінюється на підставі відповідно визначеної функції пристосування . цікавою відмінністю в еволюційних алгоритмах є метод оптимізації з мягкою селекцією запропонована Галарм .
Також введено термін еволюційнох програм, як возначення найрізноманітніших алгоритмів основаних на еволюції . Цей термін обєднує також генетичні алгоритми, еволюційні стратегії, еволюційне програмування, як і генетичне програмування, а також інші подібні методи.
Отже еволюційні програми є узагальненням генетичних алгоритмів . Класичні генетичні алгоритми оперують на визначенних бінарних довжинах та використовує оператор схрещення та мутації . Еволюційні програми включають більш складні структури (не тільки елементи 0 і 1 ) та різні інші оператори "генетичні" . Наприклад стратегії еволюційні можуть бути трактовані як еволюційні програми, в котрих вживають змінне представлення хромосомів ( не бінарне ) з мутацією як єдиним генетиним оператором .
Структура еволюційної програми відповідає блок-схемі з рис. 4.3. Вона така сама як для генетичного алгоритму, тому що поняття еволюційної програми є повністю основане на ідеї генетичного алгоритму . Різниці прихрвані глибше і стусуються представленні хромосомів та генетичних операторів . Еволюційні програми допускають повніший збір структур даних, тобто представлення хромосомів інше ніж лише елементи 0 і 1 та розширений збір генетичних операторів .
Згідно з Михайлевичем еволюційна програма є пробабілістичним алгоритм, що діє на популяції індивідумів
k k
P(k) = {x1,...,xn}
для ітерації k . Кожен індивідум представляє потенційний розвязок проблеми і в довільній еволюційній програмі є представленим у вигляді певної k ( можливо складної ) структури даних D. Кожен розвязок x i оцінюється вартістю його "пристосування" . Потім створюється нова популяція (ітерація k+1) шляхом вибору індивідумів найкраще пристосованих (селекція). Деякі індивідуми наводять популяцію підлягають перетворенню з допомогою "генетичних операторів", даючи нове розвязання . Існують трансформації mі (типу мутації), котрі створюють нові індивідуми зміною здійсненою на поодинокому індивідумі (mі : D ®D) та трансформації вищого ряду gj (типу схрещення), що створюють нові індивідуми щляхом комбінації фрагментів декількох (двох чи більше) індивідумів gj : Dx ... x D ®D) . Після певної кількості генерації еволюційної програми очікується, що найкращий індивідум представить розвязок наближений до оптимального . Структура еволюційної програми також можна представити у вигляді псевдокоду, як на рис.1.
процедура еволюційна програма
begin
k = 0
встановлення популяції P(k)
оцінка пристосування індивідумів в P(k)
while (not умова зупинки) do
begin
k = k+1
селекція індивідумів з P(k-1) доP(k)
використання генетичних операторів
оцінка пристосованості в P(k)
end
end
Рис. 1. Еволюційна програма представлена у вигляді псевдокоду.
Зараз представимо загальний приклад еволюційної програми. Уявімо, що шукаємо графу, котра виконує певні обмеження (нпр. Шукаємо оптимальну типологію комунікаційної мережі згідно з перними критеріями: вартості пересилок і т.п.) . Кожний індивідум в еволюційній програмі представляє потенційний розвязок проблеми, тобто в даному випадку графу . Початкова популяція граф P(0), генеровано випадково або створено певним хеуристичним процесом, є стартовим пунктом (k = 0) для еволюційної програми . Функція пристосування, котра звичайно дана, повязана з обмеженням проблеми. Ця функція описує "пристосування" кожної графи, розрзняючи індивідуми "кращі" і "гірші" . Можна запроектувати декілька операторів мутації, що виконують трансформацію поодинокої графи, та декілька операторів зхрещування, котрі виконують рекомбінацію двох чи більше граф, створюючи одну . Дуже часто такі оператори є залежними від виду проблеми . Наприклад, якщо шукаємо графу у вигляді дерева, то можна використати такий оператор мутації, який усуває гілку з одної графи і додає гілку, що сполучає дві розділені підграфи . Інші можливості полягають в проектуванні мутації незалежно від проблеми і залучення обмежень до функції пристосування, як "покарання" для граф, котрі не є деревами. Основну різницю між класичним генетичним алгоритмом і еволюційною програмою ілюструють рис.2 і рис.3.
Класичний генетичний алгоритм, який оперує на бінарному продовжені, вимагає модифікації оригінальної проблеми до проблеми у відповідному виді для генетичного алгоритму. Та не завжди є легке завдання . Еволюційне програмування може поставити незмінну проблему, модифікація представляє хромосоми відповідного потенційного розвязку і стосується відповідного здефінійованого "генетичного" оператора.
Інакшими словами, щоб розвязати нетрівіальну проблему, можна перетворити його в відповідну постать для алгоритму генетичного або змодифікувати генетичний алгоритм так, щоб підходив до проблеми. Перший підхід використовують застосовуючи класичний генетичний алгоритм, а другий - використовуючи еволюційну програму . Модифіковані генетичні алгоритми можна назвати еволюційними прграмами . Однак найчастіше їх визначають як еволюційні алгоритми . Еволюційні програми такж можна розглядати як еволюційні алгоритми, що підготовані програмістом до реалізації на компютері . Головним завданням програміста є вибір відповідних структур даних, а також операторів "генетичних" .
Всі поняття, вказані в нижчому розділі і стосуються назв методів основаних на еволюційному підході, можна порівнювати з загальним напрямком досліджень, а саме з галузью, що займається симуляцією еволюції з допомогою компютера . Це галузь інформатики, визначена назвою Evolutionary Computation, що в перекладі означає еволюційні обрахунки .
Еволюційні алгоритми також називають технікою еволюційних обрахунків . Потрібно додати, що назву генетичні алгоритми алгоритм генетичний вживається як в широкому так і в вузькому сенсі .
(Для продовження ознайомлення з повним текстом методички необхідно залогінитись та завантажити вкладення)