Методические указания выполнению лабораторных работ по дисциплине Основы разработки систем искусственного интеллекта для студентов направления

• Название: Методические указания выполнению лабораторных работ по дисциплине Основы разработки систем искусственного интеллекта для студентов направления
• Дата: 13.01.2022
• Размер: 1.29 Mb.
• Имя файла: 16_Metod_ORSII_09.03.02_2017.pdf
• Тип: Методические указания; #329847
• страница: 4 из 5

48
Рисунок 8.1 − Блок-схема работы генетического алгоритма
Аналогично может быть решен вопрос уничтожения особей. Только вероятность уничтожения соответственно должна быть обратно пропорциональна качеству особей. Однако обычно происходит просто уничтожение особей с наихудшим качеством.
Оператор скрещивания призван моделировать природный процесс наследования, то есть обеспечивать передачу свойств родителей потомкам.
Простейший оператор скрещивания выполняется в два этапа. Пусть особь представляет собой строку из
n
элементов. На первом этапе равновероятно выбирается натуральное число
k
от
1
до
1

n
. Это число называется точкой разбиения. В соответствии с ним обе исходные строки разбиваются на две подстроки. На втором этапе строки обмениваются своими подстроками,

49
лежащими после точки разбиения, то есть элементами с
1

k
-го по
n
-й. Так получаются две новые строки, которые наследовали частично свойства обоих родителей. Этот процесс можно представить как
Вероятность применения оператора скрещивания обычно выбирается достаточно большой, в пределах от 0,9 до 1, чтобы обеспечить постоянное появление новых особей, расширяющих пространство поиска. При значении вероятности меньше 1 часто используют элитизм. Это особая стратегия, которая предполагает переход в популяцию следующего поколения элиты, то есть лучших особей текущей популяции без всяких изменений.
Применение элитизма способствует сохранению общего качества популяции на высоком уровне. При этом элитные особи также участвуют в процессе отбора особей для скрещивания. Количество элитных особей определяется обычно по формуле
N
P
K



)
1
(
, где
K
− количество элитных особей,
P
−
вероятность применения оператора скрещивания,
N
− размер популяции.
Оператор мутации служит для моделирования природного процесса мутации. Его применение в генетических алгоритмах обусловлено следующими соображениями. Исходная популяция, какой бы большой она ни была, охватывает ограниченную область пространства поиска. Оператор скрещивания, безусловно, расширяет эту область, но все же до определенной степени, поскольку использует ограниченный набор значений, заданный исходной популяцией. Внесение случайных изменений в особи позволяет преодолеть это ограничение и иногда значительно сократить время поиска или улучшить качество результата. Как правило, вероятность мутации, в отличие от вероятности скрещивания, выбирается достаточно малой. Сам процесс мутации заключается в замене одного из элементов строки на другое значение. Это может быть перестановка двух элементов в строке, замена элемента строки значением элемента из другой строки и т. д.

50
В процессе работы алгоритма все указанные выше операторы применяются многократно и ведут к постепенному изменению исходной популяции. Поскольку операторы отбора, скрещивания, мутации и редукции по своей сути направлены на улучшение каждой отдельной особи, то результатом их работы является постепенное улучшение популяции.
После завершения работы генетического алгоритма из конечной популяции выбирается та особь, которая дает максимальное (или минимальное) значение целевой функции и является, таким образом, результатом работы генетического алгоритма. За счет того, что конечная популяция лучше исходной, полученный результат представляет собой улучшенное решение.
Аппаратура и материалы
См. приложение А настоящих методических указаний.
Указания по технике безопасности
См. приложение Б настоящих методических указаний.
Методика и порядок выполнения работы
Рассмотрим предметную область «спортивные соревнования». В таблице 6 представлены исходные данные задачи в виде турнирной сетки соревнований с указанием набранных спортивными клубами очков (данную таблицу можно реализовать в виде типа данных − структура выбранного языка программирования).
Определим при заданных условиях два «хороших» спортивных клуба.
При этом не ставится задача поиска двух наилучших клубов (в нашем случае ими является пара ({«Спартак», «Металлург»}), но требуется определить два не самых плохих клуба. Таким образом, мы соглашаемся на компромисс, при котором результат работы алгоритма будет непредсказуемым при каждом запуске: всякий раз могут быть отобраны два произвольных клуба с

51
«немалым» количеством очков. Задача представляется тривиальной, не требующей применения столь изощренных методов поиска, но мы решаем ее лишь для иллюстрации функционирования генетического алгоритма.
Таблица 8.2 − Турнирная сетка спортивных соревнований
Название клуба
Очки
«Спартак»
8
«Динамо»
2
«Торпедо»
4
«Сатурн»
3
«Крылья
Советов»
3
«Металлург»
9
«ЦСКА»
7
«Локомотив»
6
«Зенит»
1
«Сокол»
1
«Ростсельмаш»
7
«СКА»
5
Решим представленную задачу с использованием генетического алгоритма.
1. Определим особь в виде двойки названий клубов:
{Название1, Название2}. Особи формируются случайным образом, но с учетом постановки задачи: Название1< >Название2.
2. Определим размер популяции −
4

n
особи. Таким образом, единовременно алгоритмом будут обрабатываться максимум 8 клубов.
3. Оставшиеся клубы могут быть включены в работу алгоритма посредством срабатывания оператора мутации, т. е. в исходную популяцию будут добавляться особи вида {Название_1’, Название_2’}, где Название_1’ и Название_2’ взяты из числа клубов, отсутствующих в существующей на данный момент популяции. Определим вероятность срабатывания оператора мутации 5 %.
4. Элитизм не используется.

52
5. В качестве целевой функции будем использовать сумму очков двух клубов особи:
2 1
i
i
i
o
o
f


, где
i
f
− значение целевой функции
i
-й особи,
1
i
o
(
2
i
o
) − число очков первого (второго) клуба
i
-й особи.
6. В качестве оператора скрещивания будем использовать его простую интерпретацию в виде обмена подстроками (названиями вторых клубов) двух родительских особей, при этом следует учитывать, что для новых особей должно выполняться условие Название_1<>Название_2.
7. Оператор редукции будет уничтожать наихудшие особи.
8. Критерием останова алгоритма будет формирование двух поколений.
Пусть случайным образом на первом шаге формируется популяция, представленная в таблице 8.3.
Качество исходной популяции определим как




n
i
i
f
F
1 0
42
. Пусть на основе вероятностей участия в размножении особей популяции в качестве родительских случайным образом выбраны особи {«Ростсельмаш»,
«ЦСКА»} и {«Сатурн», «Локомотив»}. После выполнения оператора скрещивания получим две новые особи {«Ростсельмаш», «Локомотив»} со значением целевой функции
13 5

f
и {«Сатурн», «ЦСКА»} со значением целевой функции
10 6

f
. Пусть оператор мутации не сработал. Среди шести особей полученной популяции первого поколения оператор редукции уничтожит две наиболее слабые: {«Динамо», «СКА»} c
7 3

f
и {«Сатурн»,
«Локомотив»} c
9 4

f
. В итоге получим популяцию первого поколения
(табл.8.4).
Таблица 8.3 − Исходная популяция
Особь
i
f
Вероятность участия в размножении
Выбор родителей
«Спартак», «Торпедо»
12 12/42
«Ростсельмаш», «ЦСКА»
14 14/42
*
«Динамо», «СКА»
7 7/42
«Сатурн», «Локомотив»
9 9/42
*

53
Качество полученной популяции
49 1

F
выше качества исходной популяции с
42 0

F
. На втором шаге в результате работы оператора скрещивания появятся две новые особи {«Спартак», «ЦСКА»} c
15 7

f
и
{«Ростсельмаш», «Торпедо»} c
11 8

f
. Пусть, несмотря на низкую вероятность, сработал оператор мутации и в текущую популяцию случайным образом добавилась особь {«Металлург», «СКА»} с
14 9

f
. Среди семи особей полученной популяции второго поколения оператор редукции уничтожит три наиболее слабые: {«Сатурн», «ЦСКА»} c
10 6

f
,
{«Ростсельмаш», «Торпедо»} c
11 8

f
и {«Спартак», «Торпедо»} c
12 1

f
После второго шага достигнут критерий останова работы генетического алгоритма. В итоге получим популяцию второго поколения (табл. 8.5).
Таблица 8.4 − Популяция первого поколения
Особь
i
f
Вероятность участия в размножении
Выбор родителей
«Спартак», «Торпедо»
12 12/49
*
«Ростсельмаш», «ЦСКА»
14 14/49
*
«Ростсельмаш», «Локомотив»
13 13/49
«Сатурн», «ЦСКА»
10 10/49
Таблица 8.5 − Популяция второго поколения
Особь
i
f
«Ростсельмаш», «ЦСКА»
14
«Ростсельмаш», «Локомотив»
13
«Спартак», «ЦСКА»
15
«Металлург», «СКА»
14
Качество полученной популяции
56 2

F
, что превосходит качество всех предыдущих популяций. Из числа последних особей выбирается особь с наилучшими характеристиками, в данном случае «хорошими» спортивными клубами являются «Спартак» и «ЦСКА».

54
Варианты заданий
Вариант 1. Предметная область «учебный процесс»: специальность вуза имеет учебный план с перечнем дисциплин по каждой, из которого известна трудоемкость в часах. Определить три «сложные» дисциплины учебного плана.
Вариант 2. Предметная область «поликлиника»: существует реестр больных, обратившихся в поликлинику с указанием числа обращений.
Определить трех «очень больных» посетителей поликлиники.
Вариант 3. Предметная область «библиотека»: существует реестр книг, хранящихся в библиотеке, с указанием числа выдач клиентам.
Определить три «популярные» книги библиотеки.
Вариант 4. Предметная область «автосервис»: существует реестр марок автомобилей, прошедших ремонт в автосервисе, с указанием числа поломок. Определить три «надежные» марки автомобилей.
Вариант 5. Предметная область «билетная касса»: существует реестр маршрутов с указанием числа купленных билетов. Определить три
«популярных» маршрута.
Вариант 6. Предметная область «спортивные соревнования»: существует реестр спортивных клубов с указанием суммарного числа спортсменов. Определить три «популярных» спортивных клуба.
Вариант 7. Предметная область «телефонная станция»: существует реестр номеров телефонной станции с указанием суммарного числа дозвонов на них. Определить три «загруженных» телефонных номера.
Вариант 8. Предметная область «магазин»: существует реестр товаров магазина с указанием числа покупок. Определить три «покупаемых» товара.
Содержание отчета, его форма и правила оформления
Структура отчета по лабораторной работе:
1.
Название лабораторной работы.

55
2.
Цели лабораторной работы.
3.
Ответы на контрольные вопросы.
4.
Формулировка индивидуального задания.
5.
Листинг программы с комментариями.
6.
Анализ тестовых прогонов программы.
Вопросы для защиты работы
1. Для чего используется концепция элитизма? Привести пример для предметной области «спортивные соревнования».
2. В чем заключается отличие эволюционных вычислений от традиционных методов поиска?
3. Пояснить назначение основных блоков блок-схемы генетического алгоритма.
4. Каково назначение оператора отбора? Предложить собственный оператор отбора.
5. Какова область применения генетических алгоритмов?
Список рекомендуемой литературы
[1 − 4, 6 − 8].
ЛАБОРАТОРНАЯ РАБОТА 9
ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ В MATLAB 7.0.
Цель
и
содержание: приобретение практических навыков применения генетических алгоритмов (ГА) при решении плохо формализованных задач с использованием пакета MATLAB 7.0.
Теоретическое обоснование
Одним из новшеств MATLAB 7.0.1 является тулбокс Genetic Algorithm
and
Direct
Search
Toolbox, предназначеннный для расширения функциональных возможностей пакета генетическими алгоритмами. Такие

56
алгоритмы чаще всего используются в случае, когда искомая целевая функция является разрывной, существенно нелинейной, стохастической и не имеет производных или эти производные являются недостаточно определенными. Работать с генетическими алгоритмами можно в двух тулбоксах.
Собственно генетические алгоритмы относятся к разделу Genetic
Algorithm и вызываются из командной сроки с помощью gatool или ga.
Генетические алгоритмы и их комбинации с другими оптимизационными методами можно найти в разделе Direct Search Toolbox.
Для этого в командной строке необходимо набрать psearchtool (от poll search tool − средство поиска упорядоченным опросом).
Рассмотрим первый вариант работы с ГА. Существуют 4 основные функции для работы с алгоритмом:
ga − функция для нахождения минимума целевой функции;
gaoptimget − возвращает параметры используемого генетического алгоритма;
gaoptimset − устанавливает параметры генетического алгоритма;
gatool − открывает окно Genetic Algorithm Tool.
Для того, чтобы применить ГА к поставленной функции цели, необходимо в первую очередь записать её в M-file и сохранить в текущей папке.
Рассмотрим подробнее первую функцию.
Функция ga вызывается в командной строке согласно нижеприведенному синтаксису:
[x fval] = ga(@fitnessfun, nvars, options)
здесь
fitnessfun − имя M-file, содержащего поставленную целевую функцию;
nvars − число независимых переменных в целевой функции;
options − структура, содержащая параметры используемого ГА. Если

57
параметры не изменять, то их значения возьмутся по умолчанию.
Результаты вычислений сохранятся в переменных:
fval − окончательное значение целевой функции;
x − точка, в которой достигнуто оптимальное значение.
Существуют и другие варианты вызова функции ga:
x = ga(fitnessfun, nvars)
x = ga(fitnessfun, nvars, options)
x = ga(problem)
[x, fval] = ga(...)
[x, fval, reason] = ga(...)
[x, fval, reason, output] = ga(...)
[x, fval, reason, output, population] = ga(...)
[x, fval, reason, output, population, scores] = ga(...)
Однако наиболее наглядный способ работы с ГА в MATLAB 7.0. заключается в вызове окна тулбокса с помощью функции gatool (рис. 9.1,
9.2).
Как видно из рисунков, окно сопровождено справкой по всем компонентам, и работа пользователя заключается в виде установки параметров и нажатии кнопки «start». Результат будет тем же, что и в случае последовательного применения функций gaoptimset и ga. В разделе plots можно выбрать переменные, изменение которых будет отображаться графически. Также анализ рисунков показывает, что русификация окна является весьма неудачной.
Аппаратура и материалы
См. приложение А настоящих методических указаний.
Указания по технике безопасности
См. приложение Б настоящих методических указаний.

58
Методика и порядок выполнения работы
Минимизировать функцию одной переменной
3 4
12 16 8
)
(




x
x
x
f
Решение
Напишем M-file для данной функции и сохраним его в текущей папке под именем ex3.m (рис. 9.3).
function y = ex3(x)
y = - 12*(x+4)^ (2/3)+8*x-16;
Вызовем окно тулбокса с помощью gatool. В поле fitness function введем имя целевой функции @ex3.
Рисунок 9.1 − Окно тулбокса по генетическим алгоритмам
Установим значения параметров ГА: количество особей в популяции −
10, количество поколений
− 100 (в окне критерия остановки алгоритма), начальный отрезок − [−4; 1]. В разделе plots установим флажки для best

59
fitness, best individual, distance. Щелкнем по кнопке start (рис. 9.1).
В результате завершения процесса в окне final point появится значение переменной x, соответствующее минимуму функции, а в окне status and
result можно увидеть найденное минимальное значение целевой функции.
Для данной задачи результаты получились следующие: минимум функции достигается в точке x= −2.99448 и f (−2.99448) = −51.9945.
Рисунок 9.2 − Окно тулбокса по генетическим алгоритмам (с русификацией)
Процесс нахождения минимального решения генетическим алгоритмом визуально иллюстрируется в окне Genetic Algorithm (рис. 9.4).
Первый фрагмент рисунка отображает изменение значение целевой функции. Видно, что, начиная с 80 популяции, алгоритм сошелся к решению.
На втором фрагменте (справа) изображена наилучшая особь. Третий фрагмент рисунка соответствует изменению расстояния между особями в

60
поколениях. Особи становятся одинаковыми (хеммингово расстояние = 0) в последних 18 поколениях. ГА нужно запустить несколько раз, а потом выбрать оптимальное решение.
Рисунок 9.3 − Окно редактора кода
Рисунок 9.4 − Графический анализ решения
Это связано с тем, что начальная популяция формируется с использованием генератора случайных чисел.

61
Убедиться в правильности решения можно, построив график функции.
То же самое можно было бы получить, используя функции gaoptimset и
ga.
Чтобы посмотреть M-File выберете в меню «File» окна
«Genetic Algoritm Tool» команду «Generate M-file», сохраните файл под другим именем и просмотрите код. Для данной задачи получили:
function [X,FVAL,REASON,OUTPUT,POPULATION,SCORES] = ex3q
%% This is an auto generated M file to do optimization with the Genetic
Algorithm and
% Direct Search Toolbox. Use GAOPTIMSET for default GA options
structure.
%%Fitness function
fitnessFunction = @ex3;
%%Number of Variables
nvars = 1 ;
%Start with default options
options = gaoptimset;
%%Modify some parameters
options = gaoptimset(options,'PopInitRange' ,[-4 ; 1 ]);
options = gaoptimset(options,'PopulationSize' ,10);
options = gaoptimset(options,'MutationFcn' ,{ @mutationgaussian 1 1 });
options = gaoptimset(options,'Display' ,'off');
options = gaoptimset(options,'PlotFcns' ,{ @gaplotbestf @gaplotbestindiv
@gaplotdistance });
%%Run GA
[X,FVAL,REASON,OUTPUT,POPULATION,SCORES] =
ga(fitnessFunction,nvars,options);