У цьому розділі описується концепція простого генетичного алгоритму (ГА), орієнтованого рішення різних оптимізаційних завдань. Вводяться та змістовно описуються поняття, що використовуються в теорії та додатках ГА. Наводиться фундаментальна теорема ГА та викладається теорія схем, що становлять теоретичну базу ГА. Обговорюються концептуальні питання щодо переваг та недоліків ГА.
1.1. Простий генетичний алгоритм
Основи теорії генетичних алгоритмів сформульовані Дж. Г. Холландом в основній роботі і надалі були розвинені низкою інших дослідників. Найбільш відомою і часто цитованою в даний час є монографія Д. Голдберга, де систематично викладено основні результати та сфери практичного застосування ГА.
ГА використовують принципи та термінологію, запозичені у біологічної науки – генетики. У ГА кожна особина представляє потенційне вирішення певної проблеми. У класичному ГА особина кодується рядком двійкових символів - хромосомою, кожен біт якої називається геном. Безліч особин – потенційних рішень становить населення. Пошук оптимального чи субоптимального вирішення проблеми виконується у процесі еволюції популяції, тобто. послідовного перетворення однієї кінцевої множини рішень в інше за допомогою генетичних операторів репродукції, кросинговера та мутації. ЕВ використовують механізми природної еволюції, засновані на таких принципах:
- Перший принцип заснований на концепції виживання найсильніших і природніших відборів за Дарвіном, який був сформульований ним у 1859 році в книзі "Походження видів шляхом природного відбору". Згідно з Дарвіном особини, які краще здатні вирішувати завдання у своєму середовищі, частіше виживають і частіше розмножуються (репродукують). У генетичних алгоритмах кожна особина є рішенням певної проблеми. За аналогією з цим принципом особини з найкращими значеннями цільової (фітнес) функції мають великі шанси вижити та репродукувати. Формалізацію цього принципу, як побачимо далі, реалізує оператор репродукції.
- Другий принцип обумовлений тим, що хромосома нащадка складається з частин, отриманих з хромосом батьків. Цей принцип було відкрито 1865 року Г.Менделем. Його формалізація дає основу для оператора схрещування (кросинговера).
- Третій принцип заснований на концепції мутації, відкритої в 1900 де Вре. Спочатку цей термін використовувався для опису істотних (різких) змін властивостей нащадків та набуття ними властивостей, які відсутні у батьків. За аналогією з цим принципом генетичні алгоритми використовують подібний механізм для різкої зміни властивостей нащадків і тим самим підвищують різноманітність (мінливість) особин у популяції (множині рішень).
Ці три принципи становлять ядро ЕВ. Використовуючи їх, населення (безліч рішень цієї проблеми) еволюціонує від покоління до покоління.
Еволюцію штучної популяції – пошук безлічі рішень деякої проблеми, формально можна описати як алгоритму, який представлений на рис.1.1.
ГА отримує безліч параметрів оптимізаційної проблеми та кодує їх послідовностями кінцевої довжини в деякому кінцевому алфавіті (у найпростішому випадку в двійковому алфавіті "0" та "1").
Попередньо простий ГА випадково генерує початкову популяцію хромосом (стрингів). Потім алгоритм генерує наступне покоління (популяцію) за допомогою трьох наступних основних генетичних операторів:
- оператора репродукції (ВР);
- оператора схрещування (кросинговера, ОК);
- оператора мутації (ОМ).
Генетичні алгоритми – це просто випадковий пошук , вони ефективно використовують інформацію, накопичену у процесі еволюції.
У процесі пошуку рішення необхідно дотримуватися балансу між "експлуатацією" отриманих на даний момент кращих рішень та розширенням простору пошуку. Різні методи пошуку вирішують цю проблему по-різному.
Наприклад, градієнтні методи практично засновані лише на використанні кращих поточних рішень, що підвищує швидкість збіжності з одного боку, але породжує проблему локальних екстремумів з іншого. У полярному підході випадкові методи пошуку використовують усі
1. Природний відбір у природіЕволюційна теорія стверджує, кожен біологічний вид цілеспрямовано розвивається і змінюється у тому, щоб найкраще пристосуватися до довкілля. У процесі еволюції багато видів комах і риб набули захисного забарвлення, їжак став невразливим завдяки голкам, людина стала володарем найскладнішої нервової системи. Можна сміливо сказати, що еволюція - це процес оптимізації всіх живих організмів. Розглянемо, якими засобами природа вирішує це завдання оптимізації.
Основний механізм еволюції – це природний відбір.
Його суть полягає в тому, що більш пристосовані особини мають більше можливостей для виживання та розмноження і, отже, приносять більше нащадків, ніж погано пристосовані особини. При цьому завдяки передачі генетичної інформації ( генетичного спадкування) Нащадки успадковують від батьків основні їх якості. Таким чином, нащадки сильних індивідуумів також будуть відносно добре пристосованими, а їхня частка в загальній масі особин зростатиме. Після зміни кількох десятків чи сотень поколінь середня пристосованість особин цього виду помітно зростає.
Щоб зробити зрозумілими принципи роботи генетичних алгоритмів, пояснимо також, як улаштовані механізми генетичного спадкування в природі. У кожній клітині будь-якої тварини міститься вся генетична інформація цієї особини. Ця інформація записана у вигляді набору дуже довгих молекул ДНК (Дезоксирибонуклеїнова кислота). Кожна молекула ДНК - це ланцюжок, що складається з молекул нуклеотидівчотирьох типів, що позначаються А, T, C і G. Власне, інформацію несе порядок проходження нуклеотидів у ДНК. Таким чином, генетичний код індивіда - це просто дуже довгий рядок символів, де використовуються всього 4 літери. У тваринній клітині кожна молекула ДНК оточена оболонкою - така освіта називається хромосомою.
Кожна вроджена якість особини (колір очей, спадкові хвороби, тип волосся тощо) кодується певною частиною хромосоми, яка називається геномцієї властивості. Наприклад, ген кольору очей містить інформацію, що кодує певний колір очей. Різні значення гена називаються його алелями.
При розмноженні тварин відбувається злиття двох батьківських статевих клітин та його ДНК взаємодіють, утворюючи ДНК нащадка. Основний спосіб взаємодії - кросовер (cross-over, схрещування).При кросовері ДНК предків діляться дві частини, та був обмінюються своїми половинками.
При наслідуванні можливі мутації через радіоактивність або інші впливи, в результаті яких можуть змінитися деякі гени в статевих клітинах одного з батьків. Змінені гени передаються нащадку та надають йому нових властивостей. Якщо ці нові властивості корисні, вони, швидше за все, збережуться в даному виді – при цьому відбудеться стрибкоподібне підвищення пристосованості виду.
2. Що таке генетичний алгоритмНехай дана деяка складна функція ( цільова функція), що залежить від кількох змінних, і потрібно знайти такі значення змінних, у яких значення функції максимально. Завдання такого роду називаються завданнями оптимізаціїі зустрічаються практично дуже часто.
Один із найбільш наочних прикладів – завдання розподілу інвестицій, описане раніше. У цьому завдання змінними є обсяги інвестицій у кожен проект (10 змінних), а функцією, яку потрібно максимізувати – сумарний прибуток інвестора. Також дано значення мінімального та максимального обсягу вкладення в кожен із проектів, які задають область зміни кожної зі змінних.
Спробуємо вирішити це завдання, застосовуючи відомі нам природні методи оптимізації. Розглянемо кожен варіант інвестування (набір значень змінних) як індивідуума, а дохідність цього варіанта - як пристосованість цього індивідуума. Тоді у процесі еволюції (якщо ми зуміємо його організувати) пристосованість індивідуумів зростатиме, отже, з'являтимуться дедалі більше прибуткові варіанти інвестування. Зупинивши еволюцію в якийсь момент і вибравши найкращого індивідуума, ми отримаємо досить гарне рішення задачі.
Генетичний алгоритм - це проста модель еволюції у природі, реалізована як комп'ютерної програми. У ньому використовуються як аналог механізму генетичного наслідування, і аналог природного відбору. При цьому зберігається біологічна термінологія у спрощеному вигляді.
Ось як моделюється генетичне успадкування
Щоб змоделювати еволюційний процес, спочатку згенеруємо випадкову популяцію - кілька індивідуумів з випадковим набором хромосом (числових векторів). Генетичний алгоритм імітує еволюцію цієї популяції як циклічний процес схрещування індивідуумів та зміни поколінь.
Життєвий цикл популяції - це кілька випадкових схрещувань (за допомогою кросовера) та мутацій, в результаті яких до популяції додається якась кількість нових індивідуумів. Відбір у генетичному алгоритмі - це формування нової популяції зі старої, після чого стара популяція гине. Після відбору нової популяції знову застосовуються операції кросовера і мутації, потім знову відбувається відбір, тощо.
Відбір у генетичному алгоритмі тісно пов'язані з принципами природного відбору у природі так:
Таким чином, модель відбору визначає, як слід будувати популяцію наступного покоління. Як правило, ймовірність участі індивідуума у схрещуванні береться пропорційною його пристосованості. Часто використовується так звана стратегія елітизму, за якої кілька кращих індивідуумів переходять у наступне покоління без змін, не беручи участі у кросовері та відборі. У будь-якому випадку кожне наступне покоління буде в середньому краще за попереднє. Коли пристосованість індивідуумів перестає помітно збільшуватися, процес зупиняють і як розв'язання задачі оптимізації беруть найкращого зі знайдених індивідуумів.
Повертаючись до завдання оптимального розподілу інвестицій, пояснимо особливості реалізації генетичного алгоритму у разі.
- Індивідуум = варіант розв'язання задачі = набір із 10 хромосом Х j
- Хромосома Х j = обсяг вкладення у проект j = 16-розрядний запис цього числа
- Оскільки обсяги вкладень обмежені, в повному обсязі значення хромосом є допустимими. Це враховується під час генерації популяцій.
- Так як сумарний обсяг інвестицій фіксований, то реально варіюються лише 9 хромосом, а значення десятої визначається за ними однозначно.
Нижче наведено результати роботи генетичного алгоритму до трьох різних значень сумарного обсягу інвестицій K.
Кольоровими квадратами на графіках прибутків зазначено, який обсяг вкладення у проект рекомендований генетичним алгоритмом. Видно, що при малому значенні K інвестуються тільки ті проекти, які є прибутковими при мінімальних вкладеннях.
Якщо збільшити сумарний обсяг інвестицій, стає прибутковим вкладати гроші в більш дорогі проекти.
При подальшому збільшенні K досягається поріг максимального вкладення в прибуткові проекти, і інвестування в малоприбуткові проекти знову набуває сенсу.
3. Особливості генетичних алгоритмівГенетичний алгоритм - новий, але з єдино можливий спосіб розв'язання завдань оптимізації. З давніх-давен відомі два основні шляхи вирішення таких завдань - перебірний і локально-градієнтний. Ці методи мають свої переваги і недоліки, і в кожному конкретному випадку слід подумати, який з них вибрати.
Розглянемо переваги та недоліки стандартних та генетичних методів на прикладі класичної задачі комівояжера (TSP - travelling salesman problem). Суть завдання полягає у тому, щоб знайти найкоротший замкнутий шлях обходу кількох міст, заданих своїми координатами. Виявляється, що вже для 30 міст пошук оптимального шляху є складним завданням, що спонукало розвиток різних нових методів (у тому числі нейромереж та генетичних алгоритмів).
Кожен варіант рішення (для 30 міст) - це числовий рядок, де на j-му місці стоїть номер j-ого по порядку обходу міста. Таким чином, у цій задачі 30 параметрів, причому не всі комбінації значень допустимі. Звичайно, першою ідеєю є повний перебір всіх варіантів обходу. 
Перебірний метод найпростіший за своєю суттю і тривіальний у програмуванні. Для пошуку оптимального рішення (точки максимуму цільової функції) потрібно послідовно обчислити значення цільової функції у всіх можливих точках, запам'ятовуючи максимальне їх. Недоліком цього є велика обчислювальна вартість. Зокрема, завдання комівояжера потрібно прорахувати довжини понад 10 30 варіантів шляхів, що цілком неможливо. Однак, якщо перебір всіх варіантів за розумний час можливий, то можна бути абсолютно впевненим, що знайдене рішення дійсно оптимальне.
Другий популярний спосіб ґрунтується на методі градієнтного спуску. При цьому спочатку вибираються деякі випадкові значення параметрів, а потім ці значення поступово змінюють, досягаючи найбільшої швидкості зростання цільової функції. Досягши локального максимуму, такий алгоритм зупиняється, тому для пошуку глобального оптимуму будуть потрібні додаткові зусилля. Градієнтні методи працюють дуже швидко, але не гарантують оптимальність знайденого рішення.
Вони ідеальні для застосування в так званих унімодальнихзавдання, де цільова функція має єдиний локальний максимум (він же - глобальний). Легко бачити, що завдання комівояжера унімодальної не є. 
Типове практичне завдання, як правило, мультимодальна і багатовимірна, тобто містить багато параметрів. Для таких завдань немає жодного універсального методу, який дозволяв би досить швидко знайти абсолютно точне рішення.
Однак, комбінуючи перебірний та градієнтний методи, можна сподіватися отримати хоча б наближене рішення, точність якого зростатиме при збільшенні часу розрахунку.
Генетичний алгоритм є саме такий комбінований метод. Механізми схрещування та мутації у якомусь сенсі реалізують перебірну частину методу, а відбір кращих рішень – градієнтний спуск. На малюнку показано, що така комбінація дозволяє забезпечити стабільно хорошу ефективність генетичного пошуку для будь-яких типів завдань.
Отже, якщо на деякому безлічі задана складна функція від кількох змінних, то генетичний алгоритм - це програма, яка за розумний час знаходить точку, де значення функції досить близько до максимально можливого. Вибираючи прийнятний час розрахунку, ми отримаємо одне з найкращих рішень, які взагалі можна отримати за цей час.
Компанією Ward Systems Group підготовлено наочний приклад розв'язання задачі комівояжера за допомогою генетичного алгоритму. Для цього було використано бібліотеку функцій продукту GeneHunter.
Основний (класичний) генетичний алгоритм (також званий елементарним чи простим генетичним алгоритмом) складається з наступних кроків:
1) ініціалізація, або вибір вихідної популяції хромосом;
2) оцінка пристосованості хромосом у популяції;
3) перевірка умови зупинення алгоритму;
4) селекція хромосом;
5) застосування генетичних операторів;
6) формування нової популяції;
7) вибір «найкращої» хромосоми.
Блок-схему основного генетичного алгоритму зображено на рис. 4.3. Розглянемо конкретні етапи цього алгоритму докладніше з допомогою додаткових подробиць, представлених на рис. 4.4.
Мал. 4.3. Блок-схема генетичного алгоритму.
Мал. 4.4. Схема виконання генетичного алгоритму.
Ініціалізація, тобто. формування вихідної популяції, полягає у випадковому виборі заданої кількості хромосом (особей), що представляються двійковими послідовностями фіксованої довжини.
Оцінювання пристосованості хромосом у популяції полягає у розрахунку функції пристосованості кожної хромосоми цієї популяції. Чим більше значення цієї функції, тим вища «якість» хромосоми. Форма функції пристосованості залежить від характеру задачі, що розв'язується. Передбачається, що функція пристосованості завжди набуває невід'ємних значень і, крім того, що для вирішення оптимізаційної задачі потрібно максимізувати цю функцію. Якщо вихідна форма функції пристосованості не задовольняє цим умовам, виконується відповідне перетворення (наприклад, задачу мінімізації функції можна легко звести до завдання максимізації).
Перевірка умови зупинення алгоритму. Визначення умови зупинення генетичного алгоритму залежить з його конкретного застосування. В оптимізаційних задачах, якщо відомо максимальне (або мінімальне) значення функції пристосованості, зупинка алгоритму може статися після досягнення очікуваного оптимального значення, можливо - із заданою точністю. Зупинка алгоритму може статися у разі, коли його виконання не призводить до поліпшення вже досягнутого значення. Алгоритм може бути зупинений після певного часу виконання або після виконання заданої кількості ітерацій. Якщо умова зупинки виконано, відбувається перехід до завершального етапу вибору «найкращої» хромосоми. Інакше наступному кроці виконується селекція.
Селекція хромосом полягає у виборі (за розрахованими на другому етапі значенням функції пристосованості) тих хромосом, які братимуть участь у створенні нащадків для наступної популяції, тобто. для наступного покоління. Такий вибір проводиться згідно з принципом природного відбору, за яким найбільші шанси на створення нових особин мають хромосоми з найбільшими значеннями функції пристосованості. Існують різноманітні методи селекції. Найбільш популярним вважається так званий метод рулетки (roulette wheel selection), який свою назву отримав за аналогією із відомою азартною грою. Кожній хромосомі може бути зіставлений сектор колеса рулетки, величина якого встановлюється пропорційною значенню функції пристосованості даної хромосоми. Тому що більше значення функції пристосованості, то більше вписувалося сектор на колесі рулетки. Все колесо рулетки відповідає сумі значень функції пристосованості всіх хромосом популяції, що розглядається. Кожній хромосомі, що позначається для (де позначає чисельність популяції) відповідає сектор колеса, виражений у відсотках згідно з формулою
, (4.2)
, (4.3)
причому - значення функції пристосованості хромосоми, a - ймовірність селекції хромосоми. Селекція хромосоми може бути представлена як результат повороту колеса рулетки, оскільки «виграла» (тобто обрана) хромосома відноситься до сектора цього колеса, що випав. Очевидно, що чим більше сектор, тим більша ймовірність "перемоги" відповідної хромосоми. Тому можливість вибору даної хромосоми виявляється пропорційною значенню її функції пристосованості. Якщо все коло колеса рулетки у вигляді цифрового інтервалу , то вибір хромосоми можна ототожнити з вибором числа з інтервалу , де і позначають відповідно початок і закінчення фрагмента кола, що відповідає цьому сектору колеса; Очевидно, що . У цьому випадку вибір за допомогою колеса рулетки зводиться до вибору числа інтервалу , яке відповідає конкретній точці на колі колеса. Інші методи селекції розглядатимуться у п. 4.8.1.
В результаті процесу селекції створюється батьківська популяція, також звана батьківським пулом (mating pool) з чисельністю, що дорівнює чисельності поточної популяції.
Застосування генетичних операторів до хромосом, відібраних за допомогою селекції, призводить до формування нової популяції нащадків від створеної на попередньому етапі батьківської популяції.
У класичному генетичному алгоритмі застосовуються два основні генетичні оператори: оператор схрещування (crossover) та оператор мутації (mutation). Проте слід зазначити, що оператор мутації відіграє явно другорядну роль порівняно з оператором схрещування. Це означає, що схрещування в класичному генетичному алгоритмі проводиться практично завжди, тоді як мутація досить рідко. Імовірність схрещування, як правило, досить велика (зазвичай), тоді як ймовірність мутації встановлюється дуже малою (найчастіше). Це випливає з аналогії зі світом живих організмів, де мутації відбуваються дуже рідко.
У генетичному алгоритмі мутація хромосом може виконуватися популяції батьків перед схрещуванням чи популяції нащадків, утворених у результаті схрещування.
Оператор схрещування. На першому етапі схрещування вибираються пари хромосом із батьківської популяції (батьківського пулу). Це тимчасова популяція, що складається з хромосом, відібраних у результаті селекції та призначених для подальших перетворень операторами схрещування та мутації з метою формування нової популяції нащадків. На цьому етапі хромосоми з батьківської популяції поєднуються в пари. Це проводиться випадковим способом відповідно до ймовірності схрещування. Далі кожної пари відібраних в такий спосіб батьків розігрується позиція гена (локус) в хромосомі, що визначає так звану точку схрещування. Якщо хромосома кожного з батьків складається з генів, то очевидно, що точка схрещування є натуральним числом, менше . Тому фіксація точки схрещування зводиться до випадкового вибору числа з інтервалу. В результаті схрещування пари батьківських хромосом виходить наступна пара нащадків:
1) нащадок, хромосома якого на позиціях від 1 до складається з генів першого з батьків, а на позиціях від до - з генів другого з батьків;
2) нащадок, хромосома якого на позиціях від 1 до складається з генів другого з батьків, а на позиціях від до - з генів першого з батьків.
Дія оператора схрещування буде проілюстрована прикладами 4.4 та 4.5 (п.п. 4.5 та 4.6).
Оператор мутації з ймовірністю змінює значення гена в хромосомі протилежне (тобто з 0 на 1 або назад). Наприклад, якщо в хромосомі мутації піддається ген на позиції 7, його значення, рівне 1, змінюється на 0, що призводить до утворення хромосоми . Як уже згадувалося вище, ймовірність мутації зазвичай дуже мала, і саме від неї залежить, буде цей ген мутувати чи ні. Імовірність мутації може емулюватися, наприклад, випадковим вибором числа з інтервалу для кожного гена та відбором для виконання цієї операції тих генів, для яких розігране число виявляється меншим або рівним значенню.
Формування нової популяції. Хромосоми, отримані внаслідок застосування генетичних операторів до хромосом тимчасової батьківської популяції, включаються до складу нової популяції. Вона стає так званою поточною популяцією для цієї ітерації генетичного алгоритму. На кожній черговій ітерації розраховуються значення функції пристосованості всім хромосом цієї популяції, після чого перевіряється умова зупинки алгоритму і фіксується результат як хромосоми з найбільшим значенням функції пристосованості, або здійснюється перехід до наступного кроку генетичного алгоритму, тобто. до селекції. У класичному генетичному алгоритмі вся попередня популяція хромосом заміщається новою популяцією нащадків, має таку чисельність.
Вибір "найкращої" хромосоми. Якщо умова зупинки алгоритму виконано, слід вивести результат роботи, тобто. представити розв'язане завдання. Найкращим рішенням вважається хромосома з найбільшим значенням функції пристосованості.
На завершення слід визнати, що генетичні алгоритми успадкували властивості природного еволюційного процесу, які перебувають у генетичних змінах популяцій організмів із часом.
Головний чинник еволюції - це природний відбір (тобто. природна селекція), який призводить до того, що серед генетично різняться особин однієї й тієї ж популяції виживають і залишають потомство лише найбільш пристосовані до навколишнього середовища. У генетичних алгоритмах також виділяється етап селекції, у якому з поточної популяції вибираються і входять у батьківську популяцію особини, мають найбільші значення функції пристосованості. На наступному етапі, який іноді називається еволюцією, застосовуються генетичні оператори схрещування та мутації, які виконують рекомбінацію генів у хромосомах.
Операція схрещування полягає в обміні фрагментами ланцюжків між двома батьківськими хромосомами. Пари батьків для схрещування вибираються з батьківського пулу випадковим чином так, щоб ймовірність вибору конкретної хромосоми для схрещування дорівнювала ймовірності . Наприклад, якщо в якості батьків випадково вибираються дві хромосоми з батьківської популяції чисельністю способом, представленим при описі відповідного оператора. Це призводить до інвертування значень відібраних генів із 0 на 1 і назад. Значення, як правило, дуже мало, тому мутації піддається лише невелика кількість генів. Схрещування - це ключовий оператор генетичних алгоритмів, що визначає їх можливості та ефективність. Мутація грає більш обмежену роль. Вона вводить у популяцію деяке розмаїтість і попереджає втрати, які б статися внаслідок виключення якогось значущого гена внаслідок схрещування.
Основний (класичний) генетичний алгоритм відомий у літературі як інструмент, у якому виділяються три види операцій: репродукції, схрещування та мутації. Терміни селекція та репродукція в даному контексті використовуються як синоніми. У цьому репродукція у разі пов'язується швидше зі створенням копій хромосом батьківського пулу, тоді як найпоширеніший зміст цього поняття позначає процес формування нових особин, що походять від конкретних батьків (див. разд. 4.1). Якщо приймаємо таке тлумачення, то оператори схрещування і мутації можна вважати операторами репродукції, а селекція - відбором особин (хромосом) для репродукції.
Років чотири тому, в універі почув про такий метод оптимізації, як генетичний алгоритм. Про нього скрізь повідомлялося два факти: він кльовий і він не працює. Точніше, працює, але повільно, ненадійно, і ніде його не варто використовувати. Зате він може продемонструвати механізми еволюції. У цій статті я покажу гарний спосіб наживо подивитися на процеси еволюції на прикладі роботи цього простого методу. Потрібно лише трохи математики, програмування і все це приправити уявою.
Коротко про алгоритм
Отже, що таке генетичний алгоритм? Це, передусім, метод багатовимірної оптимізації, тобто. метод пошуку мінімуму багатовимірної функції. Потенційно цей метод можна використовувати для глобальної оптимізації, але з цим виникають складнощі, опишу їх пізніше.Сама суть методу полягає в тому, що ми модулюємо еволюційний процес: у нас є якась популяція (набір векторів), яка розмножується, на яку впливають мутації та здійснюється природний відбір на підставі мінімізації цільової функції. Розглянемо докладніше ці процеси.
Отже, перш за все наша популяція має розмножуватися. Основний принцип розмноження – нащадок схожий на своїх батьків. Тобто. ми маємо задати якийсь механізм успадкування. І краще буде, якщо він включатиме елемент випадковості. Але швидкість розвитку таких систем дуже низька - генетична різноманітність падає, популяція вироджується. Тобто. значення функції перестає мінімізуватись.
Для вирішення цієї проблеми було введено механізм мутації, який полягає у випадковій зміні якихось особин. Цей механізм дозволяє привнести щось нове до генетичної різноманітності.
Наступний важливий механізм - селекція. Як було сказано, селекція - відбір особин (можна тільки з народжених, а можна з усіх - практика показує, що це не відіграє вирішальної ролі), які краще мінімізують функцію. Зазвичай відбирають стільки особин, скільки було до розмноження, щоб з епохи в епоху ми мали постійну кількість особин у популяції. Також прийнято відбирати «щасливчиків» - якусь кількість особин, які, можливо, погано мінімізують функцію, зате внесуть різноманітності в наступні покоління.
Цих трьох механізмів найчастіше замало, щоб мінімізувати функцію. Так населення вироджується - рано чи пізно локальний мінімум забиває своїм значенням всю популяцію. Коли таке відбувається, проводять процес, званий струси(В природі аналогії - глобальні катаклізми), коли знищується майже вся популяція, і додаються нові (випадкові) особини.
Ось опис класичного генетичного алгоритму, він простий у реалізації і є місцем для фантазії та досліджень.
Постановка задачі
Отже, коли я вже вирішив, що хочу спробувати реалізувати цей легендарний (нехай і невдалий) алгоритм, мова зайшла про те, що ж я мінімізуватиму? Зазвичай беруть якусь страшну багатовимірну функцію із синусами, косинусами тощо. Але це не дуже цікаво та взагалі не наочно. Прийшла одна невигадлива ідея – для відображення багатовимірного вектора відмінно підходить зображення, де значення відповідає за яскравість. Таким чином, ми можемо ввести просту функцію - відстань до нашого цільового зображення, що вимірюється різницею яскравості пікселів. Для простоти та швидкості я взяв зображення з яскравістю 0 або 255.З погляду математики така оптимізація - справжня дрібниця. Графік такої функції є величезну багатовимірну «яму» (як тривимірний парабалоід на малюнку), в яку неминуче скотишся, якщо йти градієнтом. Єдиний локальний мінімум є глобальним. .
Проблема лише в тому, що вже близько до мінімуму кількість шляхів, якими можна спуститися вниз сильно скорочується, а всього у нас стільки напрямків, скільки вимірювань (тобто кількість пікселів). Очевидно, що вирішувати це завдання за допомогою генетичного алгоритму не варто, але ми можемо подивитися на цікаві процеси, що протікають у нашій популяції.
Реалізація
Було реалізовано всі механізми, описані у першому параграфі. Розмноження проводилося простим схрещуванням випадкових пікселів від "мами" та від "тата". Мутації проводилися шляхом зміни значення випадкового пікселя у випадкової особи на протилежне. А струс робився, якщо мінімум не змінюється протягом п'яти кроків. Тоді проводиться «екстремальна мутація» - заміна відбувається інтенсивніше, ніж зазвичай.Як вихідні картинки я брав нонограми («японські сканворди»), але, правду кажучи, можна брати просто чорні квадрати - немає жодної різниці. Нижче наведено результати для кількох зображень. Тут всім, крім «будиночка», кількість мутацій було 100 загалом на кожну особину, особин у популяції було 100, при розмноженні населення збільшувалася вчетверо. Щасливчиків було 30% у кожній епосі. Для будиночка значення були обрані менші (30 особин у популяції, мутацій по 50 на особину).
Експериментально я встановив, що використання «щасливчиків» у селекції знижує швидкість прагнення популяції до мінімуму, проте допомагає вибиратися зі стагнації – без «щасливчиків» стагнація буде постійна. Що можна побачити з графіків: лівий графік – розвиток популяції «фараона» зі щасливчиками, правий – без щасливчиків.
Таким чином, ми бачимо, що цей алгоритм дозволяє вирішити поставлене завдання, хай і за довгий час. Занадто велика кількість струсів, у разі великих зображень, може вирішити більшу кількість особин у популяції. Оптимальний вибір параметрів для різних розмірностей я залишаю за рамками даного посту.
Глобальна оптимізація
Як було сказано, локальна оптимізація – завдання досить тривіальне, навіть для багатовимірних випадків. Набагато цікавіше побачити, як алгоритм справлятиметься з глобальною оптимізацією. Але для цього потрібно спочатку побудувати функцію з безліччю локальних мінімумів. А це у нашому випадку не так складно. Достатньо брати мінімум з відстаней до кількох зображень (будиночок, динозаврик, рибка, кораблик). Тоді початковий алгоритм «скочуватиметься» в якусь випадкову ямку. І можна просто запускати його кілька разів.Але є більш цікаве вирішення цієї проблеми: можна зрозуміти, що ми скотилися в локальний мінімум, зробити сильний струс (або взагалі ініціювати особини заново), і надалі додавати штрафи при наближенні до відомого мінімуму. Як видно, картинки чергуються. Зауважу, що ми не маємо права чіпати вихідну функцію. Але ми можемо запам'ятовувати локальні мінімуми та самостійно додавати штрафи.
На цій картинці зображений результат, коли при досягненні локального мінімуму (сильна стагнація), населення легко вимирає.
Тут населення вимирає, і додається невеликий штраф (у розмірі звичайної відстані до відомого мінімуму). Це дуже знижує ймовірність повторів.
Цікавіше, коли населення не вимирає, а просто починає підлаштовуватися під нові умови (слід. малюнок). Це досягається за допомогою штрафу у вигляді 0.000001*sum^4. У такому випадку, нові образи стають трохи зашумлені:
Цей шум усувається шляхом обмеження штрафу max(0.000001 * sum ^ 4, 20). Але ми бачимо, що четвертого локального мінімуму (динозавра) досягти не вдається - швидше за все тому, що він занадто близько розташований до якогось іншого.
Біологічна інтерпретація
Які ж висновки ми можемо зробити, не побоюсь цього слова, моделювання? Насамперед, бачимо, статеве розмноження - найважливіший двигун розвитку та пристосовуваності. Але тільки його мало. Роль випадкових, маленьких змін є надзвичайно важливою. Саме вони забезпечують виникнення нових видів тварин у процесі еволюції, а в нас забезпечує різноманітність популяції.
Найважливішу роль еволюції Землі грали природні катаклізми і масові вимирання (вимирання динозаврів, комах тощо. - найбільших було близько десяти - див. діаграму нижче). Це було підтверджено нашим моделюванням. А відбір «щасливчиків» показав, що найслабкіші організми на сьогодні здатні в майбутньому стати основою для наступних поколінь.
Як то кажуть, все як у житті. Цей метод «зроби еволюцію сам» наочно показує цікаві механізми та його роль розвитку. Звичайно, існує багато більш еволюційних моделей, що стоять, (заснованих, звичайно, на дифурах), що враховують більше факторів, більш наближені до життя. Звісно, існують ефективніші методи оптимізації.
P.S.
Писав програму на Matlab (вірніше, навіть на Octave), тому що тут все – голі матриці, і є інструменти для роботи з картинками. Вихідний код додається.Вихідний код
function res = genetic(file) %generating Global A B; im2line(file); dim = length(A(1,:)); count = 100; reprod = 4; mut = 100; select = 0.7; stagn=0.8; pop = round (rand (count, dim)); res =; B =; localmin =; localcount =; for k = 1:300% reproduction for j = 1: count * reprod pop = ; end %mutation idx = 10 * (length(res) > 5 & std(res(1:5)) == 0) + 1; for j = 1: count * mut a = floor (rand () * count) + 1; b = floor(rand() * dim) + 1; pop(a,b) = ~pop(a,b); end %selection val = func(pop); val(1:count) = val(1:count) * 10; npop = zeros (count, dim); = sort(val); res =; opt = pop(i(1),:); fn = sprintf("result/%05d-%d.png",k,s(1)); line2im(opt*255,fn); if (s(1) == 0 || localcount > 10) localmin = ; localcount =; B =; % pop = round (rand (count, dim)); continue; % Break; end for j = 1:floor(count * select) npop(j,:) = pop(i(j),:); end %adding luckers for j = (floor(count*select)+1) : count npop(j,:) = pop(floor(rand() * count) + 1,:); end %fixing stagnation if (length(res) > 5 && std(res(1:5)) == 0) if (localmin == res(1)) localcount = localcount+1; else localcount = 1; end localmin = res (1); for j = 1: count * stagn a = floor (rand () * count) + 1; npop(a,:) = crossingover(npop(a,:),rand(1,dim)); end end pop = npop; end res = res(length(res):-1:1); end function res = crossingover(a, b) x = round(rand(size(a))); res = a .* x + b .* (~x); end function res = func(v) Global A B; res = inf; for i = 1: size (A, 1) res = min (res, sum (v ~ = A (i,:), 2)); end for i = 1: size (B, 1) res = res + max (0.000001 * sum (v = = B (i,:), 2). ^ 4,20); end end function = im2line(files) Global A sz; A =; files = cellstr (files); for i = 1: size (files, 1) imorig = imread (char (files (i,:))); sz = size (imorig); A = )]; end A = A/255; end function = line2im(im,file) global sz; imwrite(reshape(im*255,sz),file); end
Теги: Додати теги
Останнім часом все більше «ходять» розмови про новомодні алгоритми, такі як нейронні мережі та генетичний алгоритм. Сьогодні я розповім про генетичні алгоритми, але цього разу постараємося обійтися без хитромудрих визначень і складних термінах.
Як сказав один із великих учених: «Якщо ви не можете пояснити свою теорію своїй дружині, ваша теорія нічого не варта!» Тож давайте спробуємо у всьому розібратися по порядку.
Дрібка історії
Як каже Вікіпедія: «Батько-засновник генетичних алгоритмів Джон Холланд, який вигадав використовувати генетику у своїх цілях аж 1975 року». Для довідки цього року з'явився Альтаїр 8800, і ні, це не терорист, а перший персональний комп'ютер. На той час Джону було вже 46 років.Де це використовують
Оскільки алгоритм самонавчається, спектр застосування вкрай широкий:- Завдання на графи
- Завдання компонування
- Складання розкладів
- Створення «Штучного інтелекту»
Принцип дії
Генетичний алгоритм - це насамперед еволюційний алгоритм, тобто основна фішка алгоритму - схрещування (комбінування). Як нескладно здогадатися ідея алгоритму зухвало взята у природи, благо вона не подасть на це до суду. Так ось, шляхом перебору та найголовніше відбору виходить правильна «комбінація».Алгоритм ділиться на три етапи:
- Схрещування
- Селекція (відбір)
- Формування нового покоління
- Кількість поколінь (циклів) досягне заздалегідь обраного максимуму
- Вичерпано час на мутацію
Докладніше про кроки
Створення нової популяції. На цьому кроці створюється початкова популяція, яка, можливо, виявиться не кошерною, проте велика ймовірність, що алгоритм цю проблему виправить. Головне, щоб вони відповідали «формату» та були «пристосовані до розмноження».Розмноження. Ну тут все як у людей, для отримання нащадка потрібно два батьки. Головне, щоб нащадок (дитина) могла успадкувати у батьків їх риси. При цьому розмножуються всі, а не тільки ті, що вижили (ця фраза особливо абсурдна, але так як у нас все в сферичному вакуумі, то можна все), інакше виділиться один альфа самець, гени якого перекриють всіх інших, а нам це принципово не прийнятно .
Мутації. Мутації схожі з розмноженням, з мутантів вибирають кілька особин і змінюють їх відповідно до заздалегідь визначених операцій.
Відбір. Тут починається найсолодше, ми починаємо вибирати з населення частку тих, хто «піде далі». При цьому частку тих, хто «вижив» після нашого відбору, ми визначаємо заздалегідь руками, вказуючи у вигляді параметра. Як не сумно, інші особи мають загинути.
Практика
Ви успішно прослухали «казку» про диво-алгоритм і цілком можливо зачекалися, коли ми його почнемо експлуатувати нарешті, хочу вас порадувати, настав час.Давайте розглянемо на прикладі моїх улюблених Діофантових рівнянь (Рівняння з цілими корінням).
Наше рівняння: a+2b+3c+4d=30
Ви напевно вже підозрюєте, що коріння цього рівняння лежить на відрізку, тому ми беремо 5
випадкових значень a, b, c, d. (Обмеження в 30 взято спеціально для спрощення завдання)
Отже, у нас є перше покоління:
- (1,28,15,3)
- (14,9,2,4)
- (13,5,7,3)
- (23,8,16,19)
- (9,13,5,2)
- |114-30|=84
- |54-30|=24
- |56-30|=26
- |163-30|=133
- |58-30|=28
- (1/84)/0.135266 = 8.80%
- (1/24)/0.135266 = 30.8%
- (1/26)/0.135266 = 28.4%
- (1/133)/0.135266 = 5.56%
- (1/28)/0.135266 = 26.4%
3-1, 5-2, 3-5, 2-5, 5-3
Як було сказано раніше, нащадок містить інформацію про гени батька та матері. Це можна забезпечити у різний спосіб, але в даному випадку буде використовуватися «кросовер». (| = розділова лінія)
- Х.-батько: a1 | b1, c1, d1 Х.-мати: a2 | b2, c2, d2 Х.-нащадок: a1, b2, c2, d2 або a2, b1, c1, d1
- Х.-батько: a1, b1 | c1, d1 Х.-мати: a2, b2 | c2, d2 Х.-нащадок: a1, b1, c2, d2 або a2, b2, c1, d1
- Х.-батько: a1, b1, c1 | d1 Х.-мати: a2, b2, c2 | d2 Х.-нащадок: a1, b1, c1, d2 або a2, b2, c2, d1
А тепер зробимо те саме з нащадками:
- Х.-батько: (13 | 5,7,3) Х.-мати:(1 | 28,15,3) Х.-нащадок: (13,28,15,3)
- Х.-батько: (9,13 | 5,2) Х.-мати: (14,9 | 2,4) Х.-нащадок: (9,13,2,4)
- Х.-батько: (13,5,7 | 3) Х.-мати: (9,13,5 | 2) Х.-нащадок: (13,5,7,2)
- Х.-батько: (14 | 9,2,4) Х.-мати: (9 | 13,5,2) Х.-нащадок: (14,13,5,2)
- Х.-батько: (13,5 | 7, 3) Х.-мати: (9,13 | 5, 2) Х.-нащадок: (13,5,5,2)
- (13,28,15,3) - |126-30|=96(9,13,2,4) - |57-30|=27
(13,5,7,2) - |57-30|=22
(14,13,5,2) - |63-30|=33
(13,5,5,2) - |46-30|=16Сумно тому, що середня пристосованість (fitness) нащадків виявилася 38.8, а у батьків цей коефіцієнт дорівнював 59.4. Саме в цей момент доцільніше використовувати мутацію, для цього замінимо один або більше значень випадкове число від 1 до 30.
Алгоритм буде працювати до тих пір, поки коефіцієнт виживання не дорівнюватиме нулю. Тобто. буде рішенням рівняння.
Системи з більшою популяцією (наприклад, 50 замість 5 сходяться до бажаного рівня (0) більш швидко і стабільно.Код
На цьому простота закінчується і починається чудовий C++.
Клас на C++ вимагає 5 значень при ініціалізації: 4 коефіцієнти та результат. Для наведеного вище прикладу це буде виглядати так: CDiophantine dp(1,2,3,4,30);Потім, щоб вирішити рівняння, викличте функцію Solve(), яка поверне алель, що містить рішення. Викличте GetGene(), щоб отримати ген із правильними значеннями a, b, c, d. Стандартна процедура main.cpp, яка використовує цей клас, може бути такою:
#include "
" #include "diophantine.h" void main() ( CDiophantine dp(1,2,3,4,30); int ans; ans = dp.Solve(); if (ans == -1) ( cout<< "No solution found." << endl; } else { gene gn = dp.GetGene(ans); cout << "The solution set to a+2b+3c+4d=30 is:\n"; cout << "a = " << gn.alleles << "." << endl; cout << "b = " << gn.alleles << "." << endl; cout << "c = " << gn.alleles << "." << endl; cout << "d = " << gn.alleles << "." << endl; } } Сам клас CDiophantine:
#include
#include #define MAXPOP 25 struct gene ( int alleles; int fitness; float likelihood; // Test for equality. operator==(gene gn) ( for (int i=0;i<4;i++) { if (gn.alleles[i] != alleles[i]) return false; } return true; } }; class CDiophantine { public: CDiophantine(int, int, int, int, int);// Constructor with coefficients for a,b,c,d. int Solve();// Solve the equation. // Returns a given gene. gene GetGene(int i) { return population[i];} protected: int ca,cb,cc,cd;// The coefficients. int result; gene population;// Population. int Fitness(gene &);// Fitness function. void GenerateLikelihoods(); // Generate likelihoods. float MultInv();// Creates the multiplicative inverse. int CreateFitnesses(); void CreateNewPopulation(); int GetIndex(float val); gene Breed(int p1, int p2); }; CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {} int CDiophantine::Solve() { int fitness = -1; // Generate initial population. srand((unsigned)time(NULL)); for(int i=0;i Стаття заснована на матеріалах Вікіпедії та сайту