Генетичні алгоритми

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

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

3. Докладний опис генетичного aлгоритма.

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

пошуку.

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

6. Список літератури та посилання.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хромосома Вектор (послідовність) з нулів і единиц.

Кожна позиція (біт) називається геном.

Індивідуум =.

генетичного коду Набір хромосом = варіант вирішення даної завдання.

Кросовер Операція, коли він дві хромосоми обмінюються своїми частинами.

Мутація Cлучайное зміна одній або кількох позицій в хромосомі.

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

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

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

Відбір в генетичному алгоритмі тісно пов’язані з принципами природного добору у природі так:

Приспособленность.

індивідуума Значення цільової функції у цьому індивідуумі.

Виживання наиболее.

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

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

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

* Індивідуум = варіант вирішення даної завдання = набір з десяти хромосом Хj.

* Хромосома Хj= обсяг вкладення проект j = 16-разрядная запис цього числа.

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

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

3 Докладний опис генетичного aлгоритма.

1. Створення структури рішення шуканої завдання у вигляді масиву a[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, З, D, E) і (a, b, з, d, e) вийде (A, B, з, d, E).

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

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

Оператори кроссовера і мутации.

Найбільш традиційним підходом є відхід традиційної схеми «розмноження », яка у більшості реалізованих ГА-мах і які повторюють класичну схему. Класична схема передбачає обмеження чисельності нащадків шляхом застосування так званої ймовірності кроссовера. У такій моделі надає величині, відповідної чисельності нащадків, власне кажучи, недетерминированный характер. Є метод пропонуючи від ймовірності кроссовера і використовувати фіксований число шлюбних пар кожному поколінні, у своїй кожна шлюбна пара «дає «двох нащадків. Такий їхній підхід хороший тим, що робить процес пошуку більш керованим і передбачуваним себто обчислювальних затрат.

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

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

Вибір батьківської пары.

Перший підхід найпростіший — це випадковий вибір батьківської пари («панмиксия »), коли обидві особини, що складуть батьківську пару, випадково вибираються з.

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

Другий спосіб вибору особин в батьківську пару — так званий селективний. Суть його у тому, що «батьками «можуть бути ті особини, значення пристосованості яких немає менше середнього значення пристосованості за популяцією, при рівної ймовірності таких кандидатів скласти шлюбну пару. Такий їхній підхід забезпечує швидший відповідність алгоритму. Але через швидкої збіжності селективний вибір батьківської пари не підходить тоді, коли переносити завдання визначення кількох экстремумов, бо завдань алгоритм, зазвичай, швидко сходиться до жодного з рішень. З іншого боку, для деякого класу завдань зі складною ландшафтом пристосованості швидка відповідність може перетворитися на передчасну відповідність до квазиоптимальному рішенню. Цей недолік то, можливо почасти компенсований використанням підходящого механізму відбору (буде про що сказано нижче), який би «гальмував «занадто швидку відповідність алгоритма.

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

Механізм отбора.

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

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

Другий метод, у якому хотілося б, це відбір витісненням. Буде особина з репродукционной групи заноситися в популяцію нової генерації, визначається як величиною її пристосованості, а й тим, чи є вже у формованої популяції для наступного покоління особина під аналогічною хромосомным набором. З усіх особин з генотипами перевагу спочатку, ясна річ, віддається тим, чия пристосованість вище. Отже, досягаються мету: по-перше, не губляться кращі знайдені рішення, які мають різними хромосомними наборами, а по-друге, в популяції постійно підтримується достатнє генетичне розмаїтість. Витіснення у разі формує нову популяцію швидше зі далеко розташованих особин, замість особин, группирующихся близько поточного знайденого рішення. Цей метод добре себе показав під час вирішення многоэкстремальных завдань, у своїй крім визначення глобальних экстремумов з’являється можливість виділити й ті локальні максимуми, значення яких близькі до глобальным.

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

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

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

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

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

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

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

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

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

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

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

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

Література і Ссылки:

Генетичні алгоритми російською internet.

НейроПроект. Аналітичні технології ХХІ сторіччя internet.

Наукове видавництво ТВП internet.

Факультет обчислювальної математики кібернетики МДУ (ВМиК).

internet.

Neural Bench Development internet.

Журнал «Автоматизація Проектування «internet.

(EHIPS) Генетичні алгоритми internet.

SENN Генетичні Алгоритми internet.

Генетичні алгоритми і машинне обучение.

internet.

Компютерра | 11/1999 | Генетичні алгоритми: чому вони працюють?

internet.

Лекції по нейронным мереж і генетичним алгоритмам.

internet.

@lgorithms: Catalogue of sources. internet.