Similar presentations:
Генетические алгоритмы
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