Page 8 - 4521

1 ГЕНЕТИЧНІ АЛГОРИТМИ

1.1 Простий приклад генетичного алгоритму

Розглянемо принципи роботи генетичних алгоритмів на
максимально простому прикладі.
нехай потрібно знайти глобальний мінімум функції
2 11 3 1 4
y (x )  5  24 x  17 x   x  x 
3 4 (1.1)
на відрізку [0; 7] (рис.1.1). На цьому відрізку функція приймає
мінімальне значення в точці х=1. Очевидно, що в точці х = 6
функція потрапляє в локальний мінімум. Якщо для знахо-
дження глобального мінімуму використовувати градієнтні ме-
тоди, то залежно від початкового наближення можна потрапи-
ти в даний локальний мінімум.
Розглянемо на прикладі даного завдання принцип робо-
ти генетичних алгоритмів. Для простоти покладемо, що х при-
ймає лише цілі значення, тобто xЄ  ,1,0 7 , 6 , 5 , 4 , 3 , 2 . Це припу-
щення істотно спростить виклад, зберігши всі основні особли-
вості роботи генетичного алгоритму.
Виберемо випадковим чином декілька чисел на відрізку
[0; 7]: {2,3,5,4}. Розглядатимемо ці числа як пробні рішення
нашого завдання.
Основною ідеєю генетичних алгоритмів є організація
«боротьби за існування» і «природного відбору» серед цих
пробних рішень. Запишемо пробні рішення в двійковій формі:
{010,011,101,100}. Оскільки генетичні алгоритми використо-
вують біологічні аналогії, то і термінологія, що застосовується,
нагадує біологічну. Так, одне пробне рішення, записане в двій-
ковій формі, ми називатимемо особиною або хромосомою, а
набір всіх пробних рішень – популяцією. Як відомо, принцип
природного відбору полягає в тому, що в конкурентній боро-
тьбі виживає найбільш пристосований.

7