[17.02.12] Лекция №2 (Конспекты - Интеллектуальные системы)

Лекция №2 [17.02.12]

http://it-claim.ru/Education/Course/AI/Lections/Lections_ga.htm

Должна быть презентация. Но там пока ничего нет. Но будет. Ну, он обещал.

Задача. Есть множество от 0 до 31. Надо найти максимум. С помощью генетических алгоритмов.

Как решать:

1) надо сформировать некоторую популяцию хромосом, которые будут в этом участвовать

Будет 4 особи. И у каждой случайное значение .

Особь
1		11
2		18
3		2
4		12

2) теперь хромосомы надо закодировать в двоичный вид

Особь	Код
1	01011	11
2	10010	18
3	00010	2
4	01100	12

3) теперь надо выбрать лучшую. Как некоторую вероятность участия в кроссовере

Особь	Код
h1	01011	11	11/43
h2	10010	18	18/43
h3	00010	2	2/43
h4	01100	12	12/43

4) теперь кроссовер (скрещивание). Выбираем две пары

Первая пара, 2 и 4, они самые лучшие для скрещивания, линию раздела произвольно:

h1	01011	00010	код 2
h2	10010	11011	код 27

теперь другую линию раздела и у другой пары:

h2	10010	10000	код 16
h4	01100	01110	код 14

5) применяем мутацию

Например, к h2:

h2

10010

10000

код 16

10001

код 17

6) следующее поколение (откуда-то взялось)

Особь	Код
h1	10010	18	18/76
h2	11011	27	27/76
h3	00010	2	2/76
h4	01100	12	12/76

и сравним с первым:

	минимальное	среднее	максимальное
1 поколение	2	10.75	18
2 поколение	14	19	27

Типа что-то получилось.

Задача. Найти кратчайший путь.

Возьмём две хромосомы (для одинаковой длины – в конце дубли):

h1	1	3	5	5	5
h2	1	2	4	3	5

в двоичном коде:

h1

001

011

101

Задача. Купить колбасы, молока и хлеба. Есть три магазина. Как это формализовать?

Pr = {A,B,C}

Shop = {x,y,z}

Price = f(Pr,Shop)

по этой схеме: 300р = f(колбаса,Пятёрочка)

	x	y	z	ещё критерий	ещё критерий
A
B
C

Типа вот так.