Генетические алгоритмы

1.

ГЕНЕТИЧЕСКИЕ
АЛГОРИТМЫ
1
Донсков С. 69
группа

2.

Что такое генетический алгоритм?
Генетический алгоритм (англ. generic algorithm) – это
эвристический алгоритм поиска, применяемый для
решения задач оптимизации и моделирования путем
последовательного подбора, комбинирования и
вариации искомых параметров с использованием
механизмов, напоминающих биологическую эволюцию.
2

3.

Историческая справка
По данным википедии «Отец-
основатель генетических
алгоритмов Джон Холланд,
который придумал использовать
генетику в своих целях в 1975
году». Для справки в этом же
году появился Альтаир 8800 –
первый персональный
компьютер. К тому времени
Джону уже было 46 лет.
3

4.

Принцип работы
Формирование «начальной популяции»
Введение «функции приспособленности»
Применение «генетических операторов», чаще всего это
«селекция» и «мутация»
Создание «нового поколения»
4

5.

Модель эволюционного процесса
5

6.

Пример работы
a + 2 ⋅ b + 3 ⋅ c + 4 ⋅ d = 30
Хромосома
(a, b, c, d)
1
(1, 28, 15,3)
2
(14, 9, 2, 4)
3
(13, 5, 7, 3)
4
(23, 8, 16, 19)
5
(9, 13, 5, 2)
6

7.

Коэффициенты выживаемости первого
поколения
Хромосома
Коэффициент выживаемости
1
114 − 30 = 84
2
54 − 30 = 24
3
56 − 30 = 26
4
163 − 30 = 133
5
58 − 30 = 28
7

8.

Вероятность оказаться родителем
Хромосома
Подходящесть
1
1
÷ 0.135266 = 8.80%
84
1
÷ 0.135266 = 30.8%
24
1
÷ 0.135266 = 28.4%
26
1
÷ 0.135266 = 5.56%
133
1
÷ 0.135266 = 26.4
28
2
3
4
5
8

9.

Выбор родителей
Хромосома отца
Хромосома матери
3
1
5
2
3
5
2
5
5
3
9

10.

Кросс-оверы
Хромосома-отец
Хромосома-мать
Хромосома - потомок
a1 | b1, c1, d1
a2 | b2, c2, d2
a1 | b1, c1, d1 or a2 | b2, c2, d2
a1 b1| c1, d1
a2 b2| c2, d2
a1 b1 c1| d1
a2 b2 c2| d2
10