r>
3
5
2
5
5
3
Таблиця 4: Симуляція вибору батьків
Кожен нащадок містить інформацію про гени і батька і від матері. Взагалі кажучи, це можна забезпечити різними способами, однак у нашому випадку можна використовувати т.зв. "Кросовер" (cross-over). Нехай мати містить наступний набір розв'язків: a1, b1, c1, d1, а батько - a2, b2, c2, d2, тоді можливо 6 різних крос-оверов (| = розділова лінія):
Хромосома-батько
Хромосома-мати
Хромосома-нащадок
a1 | b1, c1, d1
a2 | b2, c2, d2
a1, b2, c2, d2 or a2, b1, c1, d1
a1, b1 | c1, d1
a2, b2 | c2, d2
a1, b1, c2, d2 or a2, b2, c1, d1
a1, b1, c1 | d1
a2, b2, c2 | d2
a1, b1, c1, d2 or a2, b2, c2, d1
Таблиця 5: Крос-овер між батьками
Є достатньо багато шляхів передачі інформації нащадкові, і крос-овер - тільки один з них. Розміщення роздільник може бути абсолютно довільним, як і те, батько або мати будуть ліворуч від межі. p> А тепер спробуємо зробити це з нашими нащадками
Хромосома-батько
Хромосома-мати
Хромосома-нащадок
(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)
Таблиця 6: Симуляція крос-оверов хромосом батьків
Тепер ми можемо обчислити коефіцієнти виживаності (fitness) нащадків. span align=center>
Хромосома-нащадок
Коефіцієнт виживаності
(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
Таблиця 7: Коефіцієнти виживаності нащадків (fitness)
Середня пристосованість (fitness) нащадків виявилася 38.8, в той час як у батьків цей коефіцієнт дорівнював 59.4. Наступне покоління може мутувати. Наприклад, ми можемо замінити одне із значень небудь хромосоми на випадкове ціле від 1 до 30. Продовжуючи, таким чином, одна хромосома, зрештою, досягне коефіцієнта виживаності 0, тобто стане рішенням. Системи з більшою популяцією (наприклад, 50 замість 5-й) сходяться до бажаного рівня (0) більше швидко і стабільно.
2.4. Шляхи вирішення завдань оптимізації
Генетичний алгоритм - новітній, але не єдино можливий спосіб вирішення завдань оптимізації. З давніх пір відомі два основних шляхи вирішення таких завдань - переборний та локально-градієнтний. У цих методів свої переваги і недоліки, і в кожному конкретному випадку слід подумати, який з них вибрати.
Розглянемо достоїнства і недоліки стандартних і генетичних методів на прикладі класичної задачі комівояжера (TSP - travelling salesman problem). [20] Суть завдання полягає в тому, щоб знайти найкоротший замкнутий шлях обходу декількох міст, заданих своїми координатами. Виявляється, що вже для 30 міст пошук оптимального шляху являє собою складну задачу, що спонукала розвиток різних нових методів (у тому числі нейромереж і генетичних алгоритмів). <В
рис. 1 Найкоротший шлях
Кожен варіант рішення (Для 30 міст) - це числова рядок, де на j-му місці стоїть номер j-ого по порядком обходу міста. Таким чином, у цій задачі 30 параметрів, причому не всі комбінації значень допустимі. Природно, першою ідеєю є повний перебір всіх варіантів обходу. tabletable border=0 cellspacing=0 cellpadding=0>
В
рис.2 Переборний метод
переборного метод найбільш простий за своєю суттю і тривіальний в програмуванні. Для пошуку оптимального рішення (точки максимуму цільової функції) потрібно послідовно обчислити значення цільової функції у всіх можливих...
