Лабораторна робота № 6
Генетичні алгоритми
Мета: отримати навички розв’язання практичних задач за допомогою генетичних алгоритмів.
5.1. Теоретичні відомості
Генетичні алгоритми (ГА) (Holland, 1969-1990) спрощено моделюють процеси природної еволюції і засновані на стохастических принципах.
Генетичні алгоритми зводяться до виконання наступних етапів:
1. Ініціалізувати популяцію.
2. Обчислити значення критерію якості для кожної особини популяції.
3. Виконати процес відтворення для кожної особини популяції.
4. Виконати схрещування і мутацію для кожної особини популяції.
5. Повернутися до п. 2, якщо не виконано умову завершення.
Реалізація ГА зводиться до операцій з рядками: копіювання рядків, заміни фрагментів рядків і інверсії бітів. Розглянемо приклад.
Приклад.
Знайти
, де .
Функція залежить від однієї цілочисельної змінної. Особин популяції доцільно представити у вигляді бінарного рядка довжиною 1 байт.
0
00000000

1
00000001

...


255
11111111




Число особин популяції в реальних задачах зазвичай складає 10–100. У даній задачі виберемо 8.
1. Ініціалізація — за допомогою датчика випадкових чисел у кожній з 8 позицій кожного рядка встановимо або 0 або 1.
Результати ініціалізації наведено в табл. 13.1.
Таблиця 5.1. Значення при ініціалізації
Особи
x
fx
fnorm

10111101
189
0.733
0.144

11011000
216
0.471
0.093

01100011
99
0.937
0.184

11101100
236
0.243
0.048

10101110
174
0.845
0.166

01001010
74
0.788
0.155

00100011
35
0.416
0.082

00110101
53
0.650
0.128






Значення критерію якості — нормоване значення функції
.
3. Формування нової популяції з тим же числом особин. При формуванні нової популяції використовується принцип рулетки (рис. 5.1).
Результати застосування принципу рулетки показано в табл. 5.2.
Таблиця 5.2. Показники при формуванні покоління за принципом рулетки
N
Рядок
Крит. якості
% співвідн.

1
01101
169
14.4

2
11000
576
49.2

3
10010
64
5.5

4
10011
361
30.9

Разом:

1170
100








Рис. 5.1. Співвідношення за критерієм якості
Ймовірність влучення в кожний із сегментів пропорційна його величині.
Генеруються 8 випадкових значень з діапазону [0,1]:
.
Якщо

тоді
.
Наприклад, якщо [0, 0.144], то в нову популяцію включається . Якщо [0.144, (0.144+0.093)=0.237], то включається в нову популяцію.
Таким чином максимальна імовірність включення в нову популяцію особин з максимальним значенням критерію якості.
Візьмемо набір з 8 випадкових чисел:
0.293, 0.971, 0.160, 0.469, 0.664, 0.568, 0.371, 0.109.
Індекси особин першої популяції, що ввійдуть у наступне покоління: 3, 8, 2, 5, 6, 5, 3, 1.
Після відтворення популяція матиме вигляд:
01100011

00110101

11011000

10101110

01001010

10101110

01100011

10111101



4. Схрещування — основна риса генетичного алгоритму полягає в обміні частин двох батьківських особин.
(a) Вибирається імовірність (приблизно 0.65–0.80) того, що між двома батьками відбудеться схрещування (виберемо = 0.75).
(б) Популяція випадковим образом розбивається на пари. Для будь-якої пари генерується випадкове число:
.
Якщо
,
то пари піддаються схрещуванню.
(в) Для кожної з пар, що підлягають схрещуванню, випадковим чином задаються два числа (або одне число для одноточкового схрещування), що визначають границі рядка для обміну (табл. 5.3).
Таблиця 13.3. Значення при схрещуванні
Батьківська популяція
Нове покоління
x
f(x)

0111000211
01110111
119
0.999

0011101201
00100001
33
0.394






1110112000
10101000
168
0.882

1101012110
11011110
222
0.405






0120010110
10001010
138
0.998

1021011110
01101110
110
0.976






01100011
01100011
99
0.937

10111101
10111101
189
0.733

Оптимальне значення

10000000
128

(г) Мутація — інвертування випадково обраних бітів (зазвичай з постійною імовірністю для кожного біта популяції, приблизно рівною 0.001–0.01).
Таким чином будь-який біт інвертується з імовірністю 0.1%–1%. Оскільки в наведеному прикладі число бітів у популяції складає 64, то при імовірності мутації =0.001 або 0.01 швидше за все жоден біт не змінить значення.
Тепер двом особинам нового покоління відповідає значення критерію якості >0.99.
5. Перехід до нової ітерації.
5.2. Порядок виконання роботи
1. Реалізувати генетичний алгоритм, використовуючи такі мови програмування як C++, Java, Fortran.
2. За допомогою генетичного алгоритму розв’язати задачу згідно з номером варіанту (розділ 5.3).
3. Результати роботи оформити звітом, який має містити: постановку задачі, опис послідовності дій при виконанні генетичного алгоритму із зазначенням всіх параметрів і проміжних результатів, результати роботи генетичного алгоритму та перевірка їх коректності, вихідний код програми.
5.3. Варіанти завдань
Реалізуйте генетичний алгоритм для розв’язання задачі максимізації функції:
1. f(x)=-(x-1)2/256, x ( [0, 255].
2. f(x)=-(x2-3x+2)/256, x ( [0, 255].
3. f(x)=-(x2-4x+15)2/256, x ( [0, 255].
4. f(x)=-(x2-4x+3)/256, x ( [0, 255].
5. f(x)=-(x2-6x+19)/256, x ( [0, 255].
6. f(x)=-(2x2-5x+13)2/256, x ( [0, 255].
7. f(x)=-(6x2-5x-1)2/256, x ( [0, 255].
8. f(x)=-(4x2-4x+2)2/256, x ( [0, 255].
9. f(x)=-(3x2-15)2/256, x ( [0, 255].
10. f(x)=-(17x2-14x+15)2/256, x ( [0, 255].