Генетичні алгоритми: суть, опис, приклади застосування

Базовий генетичний алгоритм

Розкладемо по кроках найбільш простий (класичний) ГА.

Ініціалізація початкових значень, тобто визначення первинної популяції, того безлічі особин, з якими буде відбуватися еволюція.

Встановлення первинної пристосованості кожної особини в популяції.

Перевірка умов припинення ітерацій алгоритму.

Використання функції селекції.

Застосування генетичних операторів.

Створення нової популяції.

Кроки 2-6 повторюються в циклі до виконання необхідної умови, після чого відбувається вибір найбільш пристосованою особини.

Коротко пройдемося по мало очевидним частин алгоритму. Умов припинення роботи може бути два:

Кількість ітерацій.

Якість рішення.

Генетичними операторами є оператор мутацій і оператор схрещування. Мутація змінює випадкові гени з певною ймовірністю. Як правило, ймовірність мутації має низьке числове значення. Поговоримо детальніше про процедуру генетичного алгоритму “схрещування”. Він відбувається за наступним принципом:

Для кожної пари батьків, що містять L генів, випадковим чином вибирається точка схрещування Тскі.

Перший нащадок складається шляхом приєднання до [1; Тскі] генам першого батька [Тскі+1; L] генів другого з батьків.

Другий нащадок складається зворотним шляхом. Тепер до генам другого з батьків [1; Тскі] додається гени першого батька на позиціях [Тскі+1; L].