Тривіальний приклад
Вирішимо завдання генетичним алгоритмом на прикладі пошуку особини з максимальним числом одиниць. Нехай особина складається з 10 генів. Задамо первинну популяцію в кількості восьми особин. Очевидно, найкращою особиною повинна бути 1111111111. Складемо для вирішення ГА.
- Ініціалізація. Виберемо 8 випадкових особин:
п1 | 1110010101 | п5 | 0101000110 |
п2 | 1100111010 | п6 | 0100110101 |
п3 | 1110011110 | п7 | 0110111011 |
п4 | 1011000000 | п8 | 0100001001 |
- Оцінка пристосованості. Очевидно, в нашому генетичному алгоритмі функція придатності F буде підраховувати кількість одиниць у кожної особини. Таким чином, маємо:
пі | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
F(пі) | 6 | 7 | 8 | 3 | 4 | 5 | 7 | 3 |
З таблиці видно, що особини 3 і 7 мають найбільше число одиниць, а отже є найбільш придатними членами популяції для вирішення завдання. Так як на даний момент рішення необхідного якості немає, алгоритм продовжує роботу. Необхідно провести селекцію особин. Для простоти пояснення нехай селекція відбувається випадковим чином, і ми отримуємо вибірку особин {п7, п3, п1, п7, п3, п7, п4, п2} – це батьки для нової популяції.
- Використання генетичних операторів. Знову для простоти припустимо, що ймовірність мутацій дорівнює 0. Іншими словами всі 8 особин передають свої гени такими, які є. Для проведення схрещування, складемо пари особин випадковим чином: (п2, п7), (п1, п7), (п3, п4) і (п3, п7). Так само випадковим чином вибираються точки схрещування для кожної пари:
Пара | (п2, п7) | (п1, п7) | (п3, п4) | (п3, п7) |
Батьки |
[1100111010] [0110111011] |
[1110010101] [0110111011] |
[1110011110] [1011000000] |
[1110011110] [0110111011] |
Тскі |
3 |
5 | 2 | 8 |
Нащадки |
[1100111011] [0110111010] |
[1110011011] [0110110101] |
[1111000000] [1010011110] |
[1110011111] [0110111010] |
- Складання нової популяції, що складається з нащадків:
п1 | 1100111011 | п5 | 1111000000 |
п2 | 0110111010 | п6 | 1010011110 |
п3 | 1110011011 | п7 | 1110011111 |
п4 | 0110110101 | п8 | 0110111010 |
- Оцінюємо пристосованість кожної особини нової популяції:
пі | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
F(пі) | 7 | 6 | 7 | 6 | 4 | 6 | 8 | 6 |
Подальші дії очевидні. Найцікавіше в ГА відкривається у випадку, якщо оцінити середня кількість одиниць в кожній популяції. У першій популяції в середньому на кожну особину доводилося 5,375 одиниць, в популяції нащадків – 6,25 одиниць на особину. І така особливість буде спостерігатися навіть у випадку, якщо в ході мутацій і схрещування особина з найбільшим числом одиниць в першій популяції загубиться.