застосовуються «генетичні оператори» (у більшості випадків «схрещування»- crossover і «мутація» - mutation), результатом чого є отримання нових рішень. Для них також обчислюється значення пристосованості, і потім проводиться відбір («селекція») кращих рішень в наступне покоління.
Цей набір дій повторюється ітеративне, так моделюється «еволюційний процес», що триває декілька життєвих циклів (поколінь), поки не буде виконаний критерій зупинки алгоритму. Таким критерієм може бути:
. знаходження глобального, або субоптимального рішення;
. вичерпання числа поколінь, відпущених на еволюцію;
. вичерпання часу, відпущеного на еволюцію.
Генетичні алгоритми служать, головним чином, для пошуку рішень в дуже великих, складних просторах пошуку.
Створення початковій популяції
Перед першим кроком потрібно випадковим чином створити початкову популяцію; навіть якщо вона виявиться абсолютно неконкурентоспроможною, генетичний алгоритм все одно достатньо швидко переведе її в життєздатну популяцію. Таким чином, на першому кроці можна особливо чи не намагатися зробити надто вже пристосованих особин, достатньо, щоб вони відповідали формату особин популяції, і на них можна було підрахувати функцію пристосованості (Fitness). Підсумком першого кроку є популяція H, що складається з N особин.
Розмноження
Розмноження в генетичних алгоритмах зазвичай статеве - щоб призвести нащадка, потрібні кілька батьків; зазвичай, звичайно, потрібні два. Розмноження в різних алгоритмах визначається по-різному - воно залежить від представлення даних. Головна вимога до розмноження - щоб нащадок або нащадки мали можливість успадкувати риси обох батьків, «змішавши» їх яким-небудь досить розумним способом. Взагалі кажучи, для того щоб провести операцію розмноження, потрібно вибрати (1-s) p/2 пар гіпотез з H і провести з ними розмноження, отримавши по два нащадка від кожної пари (якщо розмноження визначено так, щоб давати одного нащадка, потрібно вибрати (1-s) p пар), і додати цих нащадків в H laquo ;. У результаті H складатиметься з N особин. Чому особини для розмноження зазвичай вибираються з усієї популяції H, а не з виживших на першому кроці елементів H0 (хоча останній варіант теж має право на існування)? Справа в тому, що головний бич багатьох генетичних алгоритмів - недолік різноманітності (diversity) в особинах. Досить швидко виділяється один-єдиний генотип, який представляє собою локальний максимум, а потім всі елементи популяції програють йому відбір, і вся популяція «забивається» копіями цієї особини. Є різні способи боротьби з таким небажаним ефектом; один з них - вибір для розмноження не самих пристосованих, але взагалі всіх особин.
Мутація
До мутацій відноситься все те ж саме, що і до розмноження: є деяка частка мутантів m, що є параметром генетичного алгоритму, і на кроці мутацій потрібно вибрати mN особин, а потім змінити їх відповідно до заздалегідь визначеними операціями мутації.
Кожен біт кожної особини в популяції мутує (точніше, намагається мутувати) з деякою низькою ймовірністю pm. Зазвичай мутація застосовується з імовірністю менше ніж 1%.
Мутації бувають різних видів: інверсійна, двоточкова. Інверсійна мутація інтерпретується як дзеркальне відображення біта (інверсія його значення, тобто зміна його з 1 на 0 або з 0 на 1).
Крім описаної інверсійної мутації можна застосувати оператор двухточечной мутації. У цьому випадку якщо мутація відбувається, то випадковим чином вибираються два гени, які обмінюються своїми значеннями.
Однак в результаті мутації хромосома може не змінитися якщо ймовірність мутації низька. І хромосома залишиться колишньою. Це призводить до уповільнення пошуку мети.
Висока ймовірність мутації також погано позначається на пошуку, так як хромосома може проскочити потрібну ціль.
Тому ймовірність встановлюється в деякий певне значення.
Відбір (селекція)
На етапі відбору потрібно з усієї популяції вибрати певну її частку, яка залишиться «в живих» на цьому етапі еволюції. Є різні способи проводити відбір. Імовірність виживання особини h повинна залежати від значення функції пристосованості Fitness (h). Сама частка вижили s зазвичай є параметром генетичного алгоритму, і її просто задають заздалегідь. За підсумками відбору з N особин популяції H повинні залишитися sN особин, які увійдуть в підсумкову популяцію H '. Решта особини гину...
