Класичний генетичний алгоритм
Основний (класичний) ГА складається з наступних кроків (рис.2):
1. Ініціалізація, або вибір початкової популяції хромосом.
2. Оцінювання пристосованості хромосом в популяції
3. Перевірка умови закінчення алгоритму.
4. Селекція хромосом
5. Використання генетичних операторів
6. Формування нової популяції
7. Вибір найкращої хромосоми
Рис.2. Алгоритм класичного ГА
Розглянемо ГА більш детально:
1. Ініціалізація, або вибір початкової популяції хромосом. Полягає у випадковому виборі заданої кількості N хромосом (особин), які представляються двійковими послідовностями довжини L.
2. Оцінювання пристосованості хромосом в популяції полягає у розрахунку функції пристосованості для кожної хромосоми pS(Xi).
3. Перевірка умови закінчення алгоритму. Алгоритм може бути закінчений, якщо його виконання не приводить до покращення отриманого результату або через певний проміжок часу..
4. Селекція хромосом полягає у виборі на основі функції пристосованості тих хромосом, які будуть приймати участь у створення нащадків, тобто нового покоління. Такий вибір виконується згідно принципу природного відбору, за яким найбільші шанси на створення потомства мають хромосоми з найвищими значеннями функції пристосованості. Існують різні методи селекції. Найбільш популярним вважається метод рулетки. Кожній хромосомі ставиться у відповідність сектор колеса рулетки, величина якого пропорційна до функції пристосованості даної хромосоми. Ймовірність селекції хромосоми Xi, i=1..N: .
5. Використання генетичних операторів до відібраних у результаті селекції батьківських хромосом приводить до створення популяції нащадків. В класичному га використовують два основних генетичних оператора: оператор схрещування (crossover) і оператор мутації (mutation). Як і живих організмах, ймовірність мутації звичайно дуже мала (рм<0,1).
В ГА мутація може виконуватися на популяції батьків перед схрещуванням або на популяції нащадків, утворених у результаті схрещування.
Оператор схрещування. На першому етапі схрещування вибиваються пари хромосом з батьківської популяції. Операції схрещування полягають у обміні фрагментами ланцюжків між двома батьківськими хромосомами. Далі для кожної пари вибирається позиція гена (локус)в хромосомі, який визначає точку схрещування. Якщо хромосома містить L війкових чисел, то точка схрещування LK вибирається випадковим чином з інтервалу [1, L]. В результаті схрещування утворюються два нащадки:
1) нащадок, хромосома якого на позиціях від 1 до LK складається з генів першого предка, а позиції від LK+1 до L – з генів другого предка.
2) нащадок, хромосома якого на позиціях від 1 до LK складається з генів другого предка, а позиції від LK+1 до L – з генів першого предка.
Наприклад, якщо хромосоми (1, 2, 3, 4, 5) і (0, 0, 0, 0, 0) розрізати між третім і четвертим генами і обміняти їх частини, то вийдуть нащадки (1, 2, 3, 0, 0) і (0, 0, 0, 4, 5).
Оператор мутації з ймовірністю рм змінює значення гену в хромосомі на протилежне (0/1).
6. Формування нової популяції. Хромосоми, отримані у результаті генетичних операторів до популяції предків, утворюють нову популяцію. Така популяція стає поточної для даної ітерації k ГА. На кожній ітерації розраховується значення функції пристосованості для всіх хромосом. В результаті перевірки умови закінчення ітерацій відбувається або зупинка алгоритму, або перехід до нового кроку ГА – селекції. В результаті селекції вся попередня популяція замінюється популяцією нащадків з кількістю N.
7. Вибір найкращої хромосоми. Найкращою вважається хромосома з максимальним значенням функції пристосованості.
Дата добавления: 2016-04-19; просмотров: 1872;