Зміст:

1. Природний відбір в природі
2. Що таке генетичний алгоритм
3. Детальний опис генетичного aлгорітма
4. Вплив параметрів генетичного алгоритму на ефективність
пошуку
5. Особливості генетичних алгоритмів
6. Список літератури та посилання

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

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


1 Природний відбір в природі

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

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

Щоб зробити зрозумілими принципи роботи генетичних алгоритмів, пояснимо також, як влаштовані механізми генетичного успадкування у природі. У кожній клітині будь-якої тварини міститься вся генетична інформація цієї особи. Ця інформація записана у вигляді набору дуже довгих молекул ДНК (Дезоксирибонуклеїнова кислота). Кожна молекула ДНК - це ланцюжок, що складається з молекул нуклеотидів чотирьох типів, що позначаються А, T, C і G. Власне, інформацію несе порядок проходження нуклеотидів в ДНК. Таким чином, генетичний код індивідуума - це просто дуже довга рядок символів, де використовуються усього 4 літери. В тваринній клітці кожна молекула ДНК оточена оболонкою - таке утворення називається хромосомою.

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

При розмноження тварин відбувається злиття двох батьківських статевих клітин та їх ДНК взаємодіють, утворюючи ДНК нащадка. Основний спосіб взаємодії - кросовер (cross-over, схрещування). При кросовері ДНК предків діляться на дві частини, а потім обмінюються своїми половинками.

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


2 Що таке генетичний алгоритм

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

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

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

Ось як моделюється генетичне спадкування:

Хромосома Вектор (послідовність) з нулів та одиниць.
Кожна позиція (біт) називається геном.
Індивідуум =
генетичний код Набір хромосом = варіант вирішення задачі.
Кроссовер Операція, при якій дві хромосоми обмінюються своїми частинами.
Мутація Cлучайное зміна однієї або декількох позицій у хромосомі.

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


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

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

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

Повертаючись до задачі оптимального розподілу інвестицій, пояснимо особливості реалізації генетичного алгоритму в цьому випадку.
* Індивідуум = варіант рішення задачі = набір з 10 хромосом ХJ
* Хромосома ХJ = обсяг вкладення в проект j = 16-розрядна запис цього числа
* Так як обсяги вкладень обмежені, не всі значення хромосом є допустимими. Це враховується при генерації популяцій.
* Так як сумарний обсяг інвестицій фіксованим, то реально варіюються тільки 9 хромосом, а значення 10-ій визначається за ним однозначно.

3 Детальний опис генетичного aлгорітма

1. Створення структури рішення шуканої завдання у вигляді масиву a [i], i = 1, ... n, де n - максимальне число компонент структури. Приклад: пошук функції y = f (x) найкращого у класі поліномів наближення експериментальних точок (xi, yi), j = 1 ,..., m.
Структура визначається двійкового масивом, де кожному елементу масиву сопоставлен найпростіший многочлен типу xi, i = 1, ... n, де n - максимальний ступінь полінома.

2. Створення показника ефективності структури, заповненої конкретними значеннями. Приклад: Показником ефективності для нашого прикладу буде нев'язки певна методом найменших квадратів Ja = I1 + I2 + .. + Im, де Ij = (yj-fa (xj)) 2,
де fa (x) є сума всіх елементів виду aixi, де ai = 0 або 1

3. Завдання деякого масиву різних структур Sk, k = 1 ,..., N, розмірністю N, більшою, ніж число компонент n в структурі
Даний масив можна згенерувати випадково, задавши нулі й одиниці в кожній структурі.

4. Розрахунок показників ефективності Jk для кожної структури Sk. За формулою заданої в пункті 2.

5. Природний відбір структур за певним правилом вибору найкращих структур серед заданого масиву структур. Приклад: можна за правилом виду J0 = M (Jk) - середнє значення Jk, якщо Jk

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

а.) мутація - заміна в структурі одного з значень випадково вибраної компоненти
Приклад: з (1, 1, 0, 1, 0, 0, 1, 0) вийде (1, 1, 0, 1, 1, 0, 1, 0).

б.) інверсія - перестановка в структурі деякої її частини навпаки
Приклад: з (1, 1, 0, 1, 0, 0, 1, 0) вийде (1, 1, 0, 0, 1, 0, 1, 0).

ст.) Кросинговер - створення структури, заснованої на двох структурах - заміною однієї частини першої структури на ту ж область у другій.
Приклад: з (A, B, C, D, E) і (a, b, c, d, e) вийде (A, B, c, d, E).

7. Перехід до етапу 4.


4 Вплив параметрів генетичного алгоритму на ефективність пошуку

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

Вибір батьківської пари
Перший підхід найпростіший - це випадковий вибір батьківської пари ( "панміксія"), коли обидві особи, які складуть батьківську пару, випадковим чином вибираються з
всієї популяції, причому будь-яка особина може стати членом кількох пар. Незважаючи на простоту, такий підхід універсальний для вирішення різних класів задач. Однак він досить критичний до чисельності популяції, оскільки ефективність алгоритму, що реалізує такий підхід, знижується зі зростанням чисельності популяції.
Другий спосіб вибору особин в батьківську пару - так званий селективний. Його суть полягає в тому, що "батьками" можуть стати тільки ті особи, значення пристосованості яких не менше середнього значення пристосованості по популяції, при рівній ймовірності таких кандидатів скласти шлюбну пару. Такий підхід забезпечує більш швидку збіжність алгоритму. Однак через швидку збіжності селективний вибір батьківської пари не підходить тоді, коли ставиться завдання визначення декількох екстремумів, оскільки для таких завдань алгоритм, як правило, швидко сходиться до одного з рішень. Крім того, для деякого класу задач зі складним ландшафтом пристосованості швидка збіжність може перетворитися на передчасну збіжність до квазіоптімальному рішенням. Цей недолік може бути частково компенсовано використанням відповідного механізму відбору (про що буде сказано нижче), який би "гальмував" занадто швидку збіжність алгоритму.
Інші два способи формування батьківської пари, на які хотілося б звернути увагу, це Інбридинг і Аутбридінг. Обидва ці методу побудовані на формуванні пари на основі близького і далекого "спорідненості" відповідно. Під "спорідненістю" тут розуміється відстань між членами популяції як в сенсі геометричного відстані особин у просторі параметрів. У зв'язку з цим будемо розрізняти генотіпний і фенотіпний (або географічний) Інбридинг і Аутбридінг. Під інбрідінгом розуміють такий метод, коли перший член пари вибирається випадково, а другого з більшою ймовірністю буде максимально близька до нього особина. Аутбридінг ж, навпаки, формує шлюбні пари з максимально далеких особин. Використання генетичних інбридингу і Аутбридінг виявилося більш ефективним в порівнянні з географічним для всіх тестових функцій при різних параметрах алгоритму. Найбільш корисно застосування обох представлених методів для многоекстремальних завдань. Проте два ці способи по-різному впливають на поведінку генетичного алгоритму. Так Інбридинг можна охарактеризувати властивість концентрації пошуку в локальних вузлах, що фактично призводить до розбиття популяції на окремі локальні групи навколо підозрілих на екстремум ділянок ландшафту, навпаки Аутбридінг якраз спрямований на попередження збіжності алгоритму до вже знайдених рішень, змушуючи алгоритм переглядати нові, недосліджені області.

Механізм відбору
Обговорення питання про вплив методу створення батьківських пар на поведінку генетичного алгоритму неможливо вести в відриві від реалізованого механізму відбору при формуванні нового покоління. Найбільш ефективніше два механізми відбору елітний та відбір з витісненням.
Ідея елітного відбору, загалом, не нова, цей метод заснований на побудові нової популяції тільки з кращих особин репродукційної групи, що об'єднує в собі батьків, їхніх нащадків і мутантів. В основному це пояснюють потенційною небезпекою передчасної збіжності, віддаючи перевагу пропорційним відбору. Швидка збіжність, що забезпечується елітним відбором, може бути, коли це необхідно, з успіхом компенсовано відповідним методом вибору батьківських пар, наприклад Аутбридінг. Саме така комбінація "Аутбридінг - елітний відбір" є однією з найбільш ефективних.
Другий метод, на якому хотілося б зупинитися, це відбір витісненням. Чи буде особина з репродукційної групи заноситися в популяцію нового покоління, визначається не тільки величиною її пристосованості, а й тим, чи є вже в формованої популяції Настйого покоління особина з аналогічним хромосомним набором. З усіх особин з однаковими генотипами перевагу спочатку, звичайно ж, віддається тим, чия пристосованість вище. Таким чином, досягаються дві мети: по-перше, не втрачаються найкращі знайдені рішення, що володіють різними хромосомними наборами, а по-друге, в популяції постійно підтримується достатня генетичну різноманітність. Витіснення в даному випадку формує нову популяцію скоріше з далеко розташованих особин, замість особин, що групуються близько поточного знайденого рішення. Цей метод особливо добре себе показав при вирішенні многоекстремальних завдань, при цьому крім визначення глобальних екстремумів з'являється можливість виділити і ті локальні максимуми, значення яких близькі до глобальних.

5 Особливості генетичних алгоритмів

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

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

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


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

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

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

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

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

Література і Links:

Генетичні алгоритми по-русски http://www.chat.ru/ ~ saisa

НейроПроект. Аналітичні технології XXI століття http://www.neuroproject.ru

Наукове видавництво ТВП http://www.tvp.ru/mathem3.htm

Факультет обчислювальної математики і кібернетики МГУ (ВМиК)
http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html

Neural Bench Development http://www.neuralbench.ru/rus/theory/genetic.htm

Журнал "Автоматизація Проектування" http://www.opensystems.ru/ap/1999/01/08.htm

(EHIPS) Генетичні алгоритми http://www.iki.rssi.ru/ehips/genetic.htm

SENN Генетичні Алгоритми http://fdmhi.mega.ru/ru/senn_ga.htm

Генетичні алгоритми і машинне навчання
 http://www.math.tsu.ru/russian/center/ai_group/ai_collection/docs/faqs/ai/part5/faq3.html

Компьютерра | 11/1999 | Генетичні алгоритми: чому вони працюють?
http://www.vspu.ru/public_html/cterra/20.html

Лекції по нейронних мереж і генетичних алгоритмів
http://infoart.baku.az/inews/30000007.htm

@ lgorithms: Catalogue of sources. http://algo.ekaboka.com/algo-rus/index.htm



7