Page 44 - 4521

3 МОДЕРНІЗАЦІЯ ГЕНЕТИЧНОГО АЛГОРИТМА
Однією з серйозних проблем, що виникають при вико-
ристанні генетичних алгоритмів, є передчасна збіжність. Не
рекомендується використовувати класичні ГА на маленьких
популяціях, оскільки в популяціях з малим розміром гени роз-
повсюджуються дуже швидко: всі особини стають схожими
(популяція вироджується) ще до того, як знайдено рішення
задачі. Тобто новий генотип з кращою оцінкою швидко витіс-
няє менш хороші комбінації генів, виключаючи тим самим
можливість отримання кращого рішення на їх базі. Можна за-
пропонувати три основні шляхи усунення передчасної збіжно-
сті: збільшення розміру популяції, застосування генетичних
операторів, що самоадаптуються, і створення «банку» заміню-
ваних особин.
У першому випадку, збільшуючи розмір популяції, мо-
жна сподіватися на досягнення різноманіття генотипу в попу-
ляції. Але, з іншого боку збільшення числа особин веде до збі-
льшення займаної пам'яті і часу роботи алгоритму. Даний під-
хід може бути ефективний або при паралельних обчисленнях,
або за наявності достатньо простої цільової функції.
Другий, і найпоширеніший спосіб, — використання ал-
горитмів, що самоадаптуються , — є ефективнішим. Самоада-
птація полягає в застосуванні динамічних мутацій. Динамічні
мутації залежно від особин, що схрещуються, міняють зна-
чення вірогідності мутації, тим самим стає можливим само-
управління алгоритму. У таких випадках вибирається малий
розмір популяції.
У третьому підході створюється масив для збереження
особин, генотип яких був загублений при формуванні нових
поколінь, і часом ці особини добавляться в популяцію.
Нижче детальніше розглянемо основні варіанти дина-
мічних мутацій.

43