cing=0 cellpadding=0>
Ціле
Двійковий код
Код Грея
0
0000
0000
1
0001
0001
2
0010
0011
3
0011
0010
4
0100
0110
5
0101
0111
6
0110
0101
7
0111
0100
8
1000
1100
9
1001
1101
10
1010
1111
11
1011
1110
12
1100
1010
13
1101
1011
14
1110
1001
15
1111
1000
Популяція - сукупність рішень на конкретній ітерації,кількість хромосом у популяції задається спочатку і в процесі зазвичайне змінюється. Для ГА поки не існує таких же чітких математичних основ, якдля НС, тому при реалізації ГА можливі різні варіації.
1. Початкова популяція - кінцевий набір допустимихрішень задачі.
2.
3.елементи.
4.
.
Таблиця
таким чином.
Рис. 3.Таким чином,
Рис. 4.
Рис. 5.
координатами.
ить хоча б наближене рішення, точністьякого буде зростати при збільшенні часу розрахунку.
Генетичний алгоритм являє собою саме такий комбінованийметод. Механізми схрещування і мутації в якомусь сенсі реалі
зують переборну частинаметоду, а відбір кращих рішень - градієнтний спуск.
Рис
На малюнку показано, що така комбінація дозволяє забезпечитистійко хорошу ефективність генетичного пошуку для будь-яких типів завдань.
Отже, якщо на деякій множинізадана складна функція від декількох змінних, то генетичний алгоритм - цепрограма, яка за розумний час знаходить точку, де значення функції доситьблизько до максимально можливого. Вибираючи прийнятний час розрахунку, ми отримаємо однез кращих рішень, які взагалі можливо отримати за цей час.
Однак, ГА, як і інші методи еволюційнихобчислень, не гарантує виявлення глобального рішення за поліноміальний час.ГА-ми не гарантують і того, що глобальне рішення буде знайдено, але вони гарнідля пошуку "досить хорошого" рішення задачі "досить швидко".Там, де завдання може бути вирішене спеціальними методами, майже завжди такі методибудуть ефективніше ГА і у швидкодії і в точність знайдених рішень. Головнимж перевагою ГА-мов є те, що вони можуть застосовуватися навіть на складних завданнях,там, де не існує ніяких спеціальних методів. Навіть там, де добре працююіснуючі методики, можна досягти поліпшення поєднанням їх з ГА.
3. Вплив параметрів генетичного алгоритму на ефективністьпошуку
3.1 Оператори кросовера і мутації
Найбільш традиційним підходом євідхід від традиційної схеми "розмноження", використовуваної в більшостіреалізованих ГА-мах і повторюють класичну схему. Класична схема припускаєобмеження чисельності нащадків шляхом використання так званої ймовірностікроссовера. Така модель надає величиною, відповідної чисельності нащадків,взагалі кажучи, недетермінірованний характер. Є метод пропонує відійти від імовірностікроссовера і використовувати фіксоване число шлюбних пар на кожному поколінні, прицьому кожна шлюбна пара "дає" двох нащадків. Такий підхід хороший тим,що робить процес пошуку більш керованим і передбачуваним в сенсі обчислювальнихвитрат.
В якості генетичних операторів отриманнянових генотипів нащадків, використовуючи генетичну інформацію хромосомних наборівбатьків ми застосовуємо два типи кросоверів - одно-і двоточковим. Обчислювальніексперименти показали, що навіть для простих функцій не можна говорити про перевагутого чи іншого оператора. Більш того, було показано, що використання механізмувипадкового вибору одно-або двох точкового кроссовера для кожної конкретної шлюбноїпари часом виявляється більш ефективним, ніж детермінований підхід до виборукросоверів, оскільки досить важко визначити який з двох операторів більшпідходить для кожного конкретного ландшафту пристосованості. Використання ж випадковоговибору переслідувало мету, передусім згладити відмінності цих двох підходів і поліпшитипоказники середнього очікуваного результату. Для всіх представлених тестових функційтак і сталося, - випадкового вибір виявився ефективнішим гіршого.
Підвищення ефективності пошуку при використаннівипадкового вибору операторів кроссовера вплинуло на те, щоб застосувати аналогічнийпідхід при реалізації процесу мутагенезу нових особин, проте в цьому випадку перевагаперед детермінованим підходом не так очевидно в силу традиційно малу ймовірністьмутації. В основному ймовірність мутації становить 0.001 - 0.01.
3.2 Вибір батьківської пари
Перший підхід найпростіший- Це випадковий вибір батьківської пари ("панмиксия"), коли обидві особини,які складуть батьківську пару, випадковим чином вибираються з
всієї популяції, причому будь-яка особина може стати членом декількохпар. Незважаючи на простоту, такий підхід універсальний для вирішення різних класівзадач. Однак він достатньо критичний до чисельності популяції, оскільки ефективністьалгоритму, що реалізує такий підхід, знижується зі зростанням чисельності популяції.Другий спосіб вибору особин в батьківську пару - так званий селективний. Йогосуть полягає в тому, що "батьками" можуть стати тільки ті особини, значенняпристосованості яких не менше середнього значення пристосованості по популяції,при рівній імовірності таких кандидатів скласти шлюбну пару. Такий підхід забезпечуєбільш швидку збіжність алгоритму. Однак через швидкої збіжності селективнийвибір батьківської пари не підходить тоді, коли ставиться завдання визначення декількохекстремумів, оскільки для таких завдань алгоритм, як правило, швидко сходиться доодному з рішень. Крім того, для деякого класу задач зі складним ландшафтомпристосованості швидка збіжність може перетворитися на передчасну збіжністьдо квазіоптимального рішенням. Цей недолік може бути частково компенсовано використаннямналежного механізму відбору, який би "гальмував" занадто швидку збіжністьалгоритму. Інші два способи формування батьківської пари, на які хотілосяб звернути увагу, це інбридинг і аутбридинг. Обидва ці методу побудовані на формуванніпари на основі близького і далекого "спорідненості" відповідно. Під "спорідненням"тут розуміється відстань між членами популяції як в сенсі геометричноговідстані особин у просторі параметрів. У зв'язку з цим будемо розрізняти генотипнихі фенотипних (або географічний) інбридинг і аутбридинг. Під інбрідінгом розумієтьсятакий метод, коли перший член пари вибирається випадково, а другим з більшою ймовірністюбуде максимально близька до нього особина. Аутбридинг ж, навпаки, формує шлюбніпари з максимально далеких особин. Використання генетичних інбридингу і аутбридингвиявилося більш ефективним у порівнянні з географічним для всіх тестових функційпри різних параметрах алгоритму. Найбільш корисне застосування обох представленихметодів для багатоекстремального завдань. Проте два цих способу по-різному в...
