к, так що термін рядок часто замінює поняття "хромосома". В принципі, генетичні алгоритми не обмежені бінарним поданням. Відомі інші реалізації, побудовані виключно на векторах дійсних чисел. Незважаючи на те, що для багатьох реальних задач, мабуть, більше підходять рядки змінної довжини, в даний час структури фіксованої довжини найбільш поширені і вивчені. Поки і ми обмежимося тільки структурам, які є поодинокими рядками по l біт. p> Кожна хромосома (рядок) являє собою конкатенацію ряду підкомпонентів званих генами. Гени розташовуються в різних позиціях або локусах хромосоми, і приймають значення, звані алелями. В уявленнях з бінарними рядками, ген - біт, локус - його позиція у рядку, і аллель - його значення (0 або 1). Біологічний термін "генотип" відноситься до повної генетичної моделі особини і відповідає структурі в генетичному алгоритмі. Термін "фенотип" відноситься до зовнішніх спостережуваним ознаками і відповідає вектору в просторі параметрів. Надзвичайно простий, але ілюстративний приклад - завдання максимізації наступної функції двох змінних: (1)
f (x1, x2) = exp (x1x2), де 0
Зазвичай, методика кодування реальних змінних x1 і x2 полягає в їх перетворенні в двійкові цілочисельні рядка достатньої довжини - достатньою для того, щоб забезпечити бажану точність. Припустимо, що 10-розрядне кодування достатньо і для x1, і x2. Встановити відповідність між генотипом і фенотипом закодованих особин можна, розділивши відповідне двійкове ціле число - на 210-1. Наприклад, 0000000000 відповідає 0/1023 або 0, тоді як 1111111111 відповідає 1023/1023 або 1. Оптимізується структура даних - 20-бітна рядок, що представляє конкатенацію кодувань x1 і x2. Мінлива x1 розміщується в крайніх лівих 10-розрядах, тоді як x2 розміщується у правій частині генотипу особини (20-бітової рядку). Генотип - точка в 20-мірному хеммінінговом просторі, досліджуваному генетичним алгоритмом. Фенотип - точка в двовимірному просторі параметрів. p> Щоб оптимізувати структуру, використовуючи генетичний алгоритм, потрібно задати деяку міру якості для кожної структури в просторі пошуку. Для цієї мети використовується функція пристосованості. У функціональній максимізації, цільова функція часто сама виступає в якості функції пристосованості (наприклад наш двовимірний приклад); для задач мінімізації, цільову функцію слід інвертувати і змістити потім в область позитивних значень. h2> Робота простого генетичного алгоритму
Простий генетичний алгоритм випадковим чином генерує початкову популяцію структур. Робота генетичного алгоритму являє собою ітераційний процес, який продовжується до тих пір, поки не виконав задане число поколінь або який-небудь інший критерій зупинки. На кожному поколінні генетичного алгоритму реалізується відбір пропорційно пристосованості, одноточковий кросовер і мутація. Спочатку, пропорційний відбір призначає кожній структурі ймовірність Ps (i) рівну відношенню її пристосованості до сумарної пристосованості популяції.
Потім відбувається відбір (із заміщенням) усіх n особин для подальшої генетичної обробки, згідно величиною Ps (i). Найпростіший пропорційний відбір - рулетка - відбирає особин за допомогою n "запусків" рулетки. Колесо рулетки містить по одному сектору для кожного члена популяції. Розмір i-ого сектора пропорційний відповідає величині Ps (i). При такому відборі члени популяції з більш високою пристосованістю з більшою ймовірність будуть частіше вибиратися, ніж особини з низькою пристосованістю. p> Після відбору, n обраних особин піддаються кросоверу (іноді званого рекомбінацією) із заданою вірогідністю Pc. n рядків випадковим чином розбиваються на n/2 пари. Для кожної пари з вірогідність Pc може застосовуватися кросовер. Відповідно з імовірністю 1-Pc кросовер НЕ відбувається і незмінені особини переходять на стадію мутації. Якщо кросовер відбувається, отримані нащадки заміняють собою батьків і переходять до мутації. p> Одноточковий кросовер працює таким чином. Спочатку, випадковим чином вибирається одна з l-1 точок розриву. (Точка розриву - ділянка між сусідніми бітами в рядку.) Обидві батьківські структури розриваються на два сегменти по цій точці. Потім, відповідні сегменти різних батьків склеюються і виходять два генотипу нащадків. p> Наприклад, припустимо, один батько складається з 10 нулів, а інший - з 10 одиниць. Нехай з 9 можливих точок розриву обрана точка 3. Батьки і їхні нащадки показані нижче в табл.1:
Кросовер
Батько 0000000000 000 ~ 0000000 - 111 ~ 0000000 1110000000 Нащадок
1 січня
> p> Батько 1111111111 111 ~ 1111111 - 000 ~ 1111111 0001111111 Нащадок
2 - 2
- p>> p> Схема 2
Після того, як закінчиться стадія кросовера, виконуються оператори мутації. У кожному рядку, яка піддається мутації, кожен біт з імовірністю Pm змінюється на протилежний. Населення, отримана після мутації записує поверх старої і цим цикл одного ...
