Файл: Практикум по дисциплинам Методы искусственного интеллекта в управлении, Интеллектуальное управление сложными объектами.pdf

колесо рулетки вращается 6 раз, при этом случайным образом выбирается число из интервала [0, 100], фиксируется попадание этого числа в один из промежутков, соответствующих хромосоме начальной популяции.
Пусть разыграны следующие 8 чисел:
97, 26, 54, 13, 31, 88.
Тогда на основе данных таблицы 5.4 определяются секторы колеса рулетки, в которые попали эти числа, а затем устанавливается, какие хромосомы начальной популяции соответствуют этим числам
(табл. 5.5).
Таблица 5.5
Результаты розыгрыша и соответствующие хромосомы
Результаты розыгрыша
Хромосомы
97

11101 26

10101 54

11101 13

10011 31

10101 88

11101
Анализы результатов розыгрыша показали, что хромосома ch
6
была выбрана трижды, а хромосома ch
4
– дважды, что связано с тем, что именно эти хромосомы имеют наибольшие значения функции приспособленности.
Таким образом, образуется так называемый родительский пул – набор хромосом, на основе которых формируются родительские пары хромосом. Родительский пул – временная популяция, необходимая для формирования потомков.
3.5. Применение генетических операторов
3.5.1. Операция скрещивания (кроссовер)
Множество всех возможных родительских пар формируется путем прямого произведения хромосом из родительского пула.
В рассматриваемом примере образуется 36 пар хромосом:
,
,
,
,
,
,
,
,
,
,
,
;
,
;
,
;
,
; … . . ;
,

Предположим, что из полученных 36 пар хромосом случайным образом установлены три пары родителей:
ch
1
и ch
4
, ch
4
и ch
6
, ch
6
и ch
6
К каждой родительской паре хромосом применяется оператор скрещивания (кроссовер), в результате которого порождаются новые хромосомы, у которых первая половина аллелей заимствуется у первого родителя, а вторая – у второго.
В случае одноточечного скрещивания для каждой родительской пары случайным образом задается точка скрещивания (локус) l
k
Пусть, например, для первой пары l
k
= 3, для второй l
k
= 2, для третьей
– l
k
= 2. Далее в каждой родительской паре производится обмен частями хромосом и образуется 2 новых потомка. В результате выполнения оператора скрещивания формируется 3 пары потомков
(табл. 5.6).
Таблица 5.6
Скрещивание хромосом
№
Родительские пары
локус
скрещивание
Пары потомков
1
ch
1
= [1 0 0 1 1]
ch
4
= [1 0 1 0 1]
l
k
= 3

Сh
1
= [1 0 0 0 1]
Сh
2
= [1 0 1 1 1]
2
ch
4
= [1 0 1 0 1]
ch
6
= [1 1 1 0 1]
l
k
= 2

Ch
3
= [1 0 1 0 1]
Ch
4
= [1 1 1 0 1]
3
ch
6
= [1 1 1 0 1]
ch
6
= [1 1 1 0 1]
l
k
= 2

Ch
5
= [1 1 1 0 1]
Ch
6
= [1 1 1 0 1]
Таким образом, применение оператора скрещивания к родительскому пулу порождает новую популяцию.
3.5.2. Операция мутации
Оператор мутации случайным образом с заданной вероятностью
, где
0 0,1, изменяет значение гена в хромосоме на противоположный. В табл. 5.7 показано, как применяется оператор мутации в локусе l
k
= 5 хромосомы Сh
2
: тогда Сh
2
:= [1 0 1 1 1] преобразуется в Сh
2
= [1 0 1 1 0].
Таблица 5.7
Мутация хромосом
№
Хромосома
локус
мутация
Новая хромосома
1
Ch
2
= [1 0 1 1 1]
l
k
= 5

Сh
2
= [1 0 1 1 0]

Таким образом, операция мутации, видоизменяя хромосомы, вносит разнообразие в популяцию.
3.6. Формирование новой популяции
Операторы скрещивания и мутации формируют новую популяцию. Оценки функции приспособленности хромосом новой популяции и ее фенотипы представлены в таблице 5.8. Для отличия от хромосом исходной популяции обозначения вновь сформированных хромосом начинаются с заглавной С.
Таблица 5.8
Хромосомы новой популяции и их фенотипы
Хромосома
Фенотип
Функция приспособленности
Сh
1
= [1 0 0 0 1]
∗
17
∗
579
Сh
2
= [1 0 1 1 0]
∗
22
∗
969
Ch
3
=[1 0 1 0 1]
∗
21
∗
883
Ch
4
=[1 1 1 0 1]
∗
29
∗
1683
Ch
5
=[1 1 1 0 1]
∗
29
∗
1683
Ch
6
=[1 1 1 0 1]
∗
29
∗
1683
Анализ результатов расчета новых функций приспособленности показывает, что новая популяция (потомки) характеризуется большей средней приспособленностью по сравнению с исходной
(родительской) популяцией (см. табл. 5.3).
Дальнейшие итерации генетического алгоритма формируют новые хромосомы популяции, значения функции приспособленности которых будут выше, чем у предыдущей популяции.
3.7. Выбор «наилучшей» хромосомы
Наибольшим значением функции принадлежности характеризуются хромосомы Ch
4
, Ch
5
и Ch
6
. Если на следующих итерациях генетического алгортма будут разыграны для скрещивания пары хромосом, например, Ch
4 и Ch
2
, Ch
5
и Ch
2
, Ch
6
и Ch
2
с точками скрещивания l
k
=2 или l
k
=3, то среди прочих может быть образована хромосома Ch=[11111] с фенотипом
∗
31, при котором функция приспособленности достигнет своего максимума, равного
∗
1923.

Порядок выполнения работы
1. Согласно варианту задания найти экстремум функции на заданном интервале с помощью генетического алгоритма. Принять размер начальной популяции, равным 6.
Закодировать значения параметров функции в двоичной системе. Выбрать исходную популяцию хромосом. Оценить функцию приспособленности. Провести селекцию хромосом. Применить генетические операторы скрещивания и мутации. Определить экстремум функции.
2. Проанализировать найденное решение путем построения графика целевой функции.
3. Оценить среднее количество шагов генетического алгоритма, необходимое для нахождения оптимального решения, выполняя запуск с разными начальными условиями.
Требования к содержанию и оформлению отчета
Отчет по практической работе должен содержать:
1. Название и цель работы, исходные данные варианта задания.
2. Этапы генетического алгоритма.
3. Найденное решение функции и сравнение с оптимальным решением для заданной функции (по графику).
4. Выводы.
Варианты заданий
№
Функция
Вид экстремума
Интервал
1 2
3
4
1 5
2 15 max
0 15 2
6 3
12 min
0 15 3
15 4
5
max
0 15 4
2 5
10 min
0 15 5
12 6
11 max
0 15 6
10 7
14 min
0 15 7
12 8
2 max
0 15 8
15 9
10
min
0 15 9
2 3
15 max
0 15 10 10 4
5 min
0 15

Окончание табл.
1 2
3
4
11 12 5
2 max
0 15 12 5
6 3 min
0 15 13 2
7 4 max
0 15 14 15 8
5 min
0 15 15 5
9 8 max
0 15 16 10 3
2 min
0 15 17 12 6
max
0 15 18 5
2 min
0 15 19 2
12 5 max
0 15 20 15 10 5 min
0 15
Контрольные вопросы и задания
1. Опишите работу генетического алгоритма.
2. Как происходит кодирование фенотипов в хромосомы?
3. Что такое функция приспособленности?
4. Что определяет сходимость генетического алгоритма?
5. В чем заключается метод рулетки? Опишите процесс селекции.
6. Каким образом происходит формирование начальной популяции?
7. Какие задачи решают с помощью генетических алгоритмов?
Список литературы
1. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы. М.: Горячая линия
- Телеком, 2004. 452 с.
2. Модели и методы искусственного интеллекта. Применение в экономике / Матвеев М. Г., Свиридов А. С., Алейникова Н. А.
М.: Финансы и статистика, 2008. 448 с.
3. Ярушкина Н. Г. Основы теории нечетких и гибридных систем: учеб. пособие. М.: Финансы и статистика, 2004. 320с.
4. Осипов Г.С. Лекции по искусственному интеллекту.
М.: Книжный дом «ЛИБРОКОМ», 2016. 272 с.
5. Панченко Т.В. Генетические алгоритмы: учеб. пособие / под ред. Ю.Ю.Тарасевича. Астрахань: Издательский дом «Астраханский университет», 2007. 87 с.