Интеллектуальные информационные системы

Свойства алгоритма обратного распространения ошибки (Back Propagation - ВР)

ВР - это итеративный градиентный алгоритм обучения многослойной НС без обратных связей. В такой сети на каждый нейрон первого слоя подаются все компоненты входного вектора. Все выходы скрытого слоя m подаются на слой m+1 и т.д., т.е. сеть является полносвязной.

Согласно методу наименьших квадратов, минимизируемой целевой функцией ошибки нейронной сети является величина:

(13)

где - реальное выходное состояние нейрона у выходного слоя нейронной сети при подаче на ее входы k-го образа; d_j,k - требуемое выходное состояние этого нейрона.

Суммирование ведется по всем нейронам выходного слоя и по всем обрабатываемым сетью образам. Минимизация методом градиентного спуска обеспечивает подстройку весовых коэффициентов следующим образом:

(14)

где w_ij - весовой коэффициент синаптической связи, соединяющей i-й нейрон слоя (q-1) с j-м нейроном слоя q; з - коэффициент скорости обучения, 0 < з <1.

В соответствии с правилом дифференцирования сложной функции:

, (15)

где s_j - взвешенная сумма входных сигналов нейрона j, т.е. аргумент активационной функции. Так как производная активационной функции должна быть определена на всей оси абсцисс, то функция единичного скачка и прочие активационные функции с неоднородностями не подходят для рассматриваемых нейронных сетей. В них применяются такие гладкие функции, как гиперболический тангенс или классический сигмоид с экспонентой. Например, в случае гиперболического тангенса:

(16)

Третий множитель ?s_j / ?w_ij равен выходу нейрона предыдущего слоя .

Что касается первого множителя в (23), он легко раскладывается следующим образом:

(17)

Здесь суммирование по r выполняется среди нейронов слоя (q+1). Введя новую переменную

(18)

Получим рекурсивную формулу для расчетов величин слоя q из величин более старшего слоя (q+1):

(19)



Для выходного слоя:

(20)

Теперь можно записать (14) в раскрытом виде:

(21)

Иногда для придания процессу коррекции весов некоторой инерционности, сглаживающей резкие скачки при перемещении по поверхности целевой функции, (21) дополняется значением изменения веса на предыдущей итерации:

(22)

где µ - коэффициент инерционности; t - номер текущей итерации.

Таким образом, полный алгоритм обучения нейронной сети с помощью процедуры обратного распространения строится следующим образом.

ШАГ 1. Подать на входы сети один из возможных образов и в режиме обычного функционирования нейронной сети, когда сигналы распространяются от входов к выходам, рассчитать значения последних. Напомним, что:

(23)



где L - число нейронов в слое (q-1) с учетом нейрона с постоянным выходным состоянием +1, задающего смещение; - i-й вход нейрона j слоя q.

(24)

где f(*)-сигмоид,

, (25)

где х_r - r-я компонента вектора входного образа.

ШАГ 2. Рассчитать д^(Q) для выходного слоя по формуле (20).

Рассчитать по формуле (21) или (22) изменения весов ?w^(Q) слоя Q.

ШАГ 3. Рассчитать по формулам (20) и (21) соответственно д^(Q) и ?w^(Q) для всех остальных слоев, q = (Q - 1)…1.

ШАГ 4. Скорректировать все веса в нейронной сети:

(26)

ШАГ 5. Если ошибка сети существенна, перейти на шаг 1. В противном случае - конец.

Сети на шаге 1 попеременно в случайном порядке предъявляются все тренировочные образы, чтобы сеть, образно говоря, не забывала одни по мере запоминания других.

Некоторые трудности, связанные с применением данного алгоритма в процедуре обучения НС.

Медленная сходимость процесса обучения. Сходимость ВР строго доказана для дифференциальных уравнений, т.е. для бесконечно малых шагов в пространстве весов. Но бесконечно малые шаги означают бесконечно большое время обучения. Следовательно, при конечных шагах сходимость алгоритма обучения не гарантируется.

Переобучение. Высокая точность, получаемая на обучающей выборке, может привести к неустойчивости результатов на тестовой выборке. Чем лучше сеть адаптирована к конкретным условиям (к обучающей выборке), тем меньше она способна к обобщению и экстраполяции. В этом случае сеть моделирует не функцию, а шум, присутствующий в обучающей выборке. Это явление называется переобучением. Кардинальное средство борьбы с этим недостатком - использование подтверждающей выборки примеров, которая используется для выявления переобучения сети. Ухудшение характеристик НС при работе с подтверждающей выборкой указывает на возможное переобучение. Напротив, если ошибка последовательно уменьшается при подаче примеров из подтверждающегося множества, сеть продолжает обучаться. Недостатком этого приема является уменьшение числа примеров, которое можно использовать в обучающем множестве (уменьшение размера обучающей выборки снижает качество работы сети). Кроме того, возникает проблема оптимального разбиения исходных данных на обучающую, тестовую и подтверждающую выборку. Даже при случайной выборке разные разбиения базы данных дают различные оценки.

«Ловушки», создаваемые локальными минимумами. Детерминированный алгоритм обучения типа ВР не всегда может обнаружить глобальный минимум или выйти из него. Одним из способов, позволяющих обходить «ловушки», является расширение размерности пространства весов за счет увеличения скрытых слоев и числа нейронов скрытого слоя. Другой способ - использование эвристических алгоритмов оптимизации, один из которых - генетический алгоритм.

Для создания и обучения нейронных сетей достаточно хорошо себя зарекомендовал пакет Matlab.

Описание функций пакета Matlab

Функция NEWFF - сеть прямой передачи FF

Синтаксис:

net = newff(PR,[S1 S2...SNI],{TF1 TF2...TFNI},btf,blf,pf)

Описание:

Функция newff предназначена для создания многослойных нейронных сетей прямой передачи сигнала с заданными функциями обучения и настройки, которые используют метод обратного распространения ошибки.

Функция net = newff(PR, [SI S2 ... SN1], (TF1 TF2 ... TFN1}, btf, blf, pf) формирует многослойную нейронную сеть.

Входные аргументы:

PR - массив размера Rx2 минимальных и максимальных значений для R векторов входа;

Si - количество нейронов в слое i;

TFi - функция активации слоя i, по умолчанию tansig;

btf - обучающая функция, реализующая метод обратного распространения, по умолчанию trainlm;

blf- функция настройки, реализующая метод обратного распространения, по умолчанию learngdm;

pf- критерий качества обучения, по умолчанию mse.

Выходные аргументы:

net - объект класса network object многослойной нейронной сети.

Свойства сети:

Функциями активации могут быть любые дифференцируемые функции, например tansig, logsig или purelin.

Обучающими функциями могут быть любые функции, реализующие метод обратного распространения: trainlm, trainbfg, trainrp, traingd и др.

Функция trainlm является обучающей функцией по умолчанию, поскольку обеспечивает максимальное быстродействие, но требует значительных ресурсов памяти. Если ресурсы памяти недостаточны, воспользуйтесь следующими рекомендациями:

* установите значение свойства net.trainParam.mеm_reduc равным 2 или более, что снизит требования к памяти, но замедлит обучение;

* воспользуйтесь обучающей функцией trainbfg, которая работает медленнее, но требует меньшей памяти, чем М-функция trainlm;

* перейдите к обучающей функции trainrp, которая работает медленнее, но требует меньшей памяти, чем М-функция trainbifg.

Функциями настройки могут быть функции, реализующие метод обратного распространения: learngd, learngdm.

Критерием качества обучения может быть любая дифференцируемая функция: mse, msereg.

TRAIN - обучение нейронной сети

Синтаксис:

[net, TR] = train(net,P,T,Pi,Ai)

[net, TR] = train(net,P,T,Pi,Ai,VV,TV)

Описание:

Функция [net, TR] = train(net, P, T, Pi, Ai) является методом для объектов класса network object, который реализует режим обучения нейронной сети. Эта функция характеризуется следующими входными и выходными аргументами.

Входные аргументы:

net - имя нейронной сети;

Р - массив входов;

Т - вектор целей, по умолчанию нулевой вектор;

Pi - начальные условия на линиях задержки входов, по умолчанию нулевой вектор;

Ai - начальные условия на линиях задержки слоев, по умолчанию нулевой вектор.

Выходные аргументы:

net - структура объекта network object после обучения;

TR - характеристики процедуры обучения:

TR.timesteps - длина последней выборки;

TR.perf - значения функции качества на последнем цикле обучения.

Заметим, что входной аргумент Т используется только при наличии целевых выходов. Аргументы Pi и Pf используются только в случае динамических сетей, имеющих линии задержки на входах или в слоях.

Примеры функций активации:

logsig - сигмоидальная;

purelin - линейная;

tansig - гиперболический тангенс;

Пример 1:

Создать нейронную сеть, чтобы обеспечить следующее отображение последовательности входа Р в последовательность целей Т:

Р= [0 1 2 3 4 5 6 7 8 9 10];

Т= [0 1 2 3 4 3 2 1 2 3 4];

Архитектура нейронной сети: двухслойная сеть с прямой передачей сигнала; скрытый слой - 5 нейронов с функцией активации tansig; выходной слой - 1 нейрон с функцией активации purelin; диапазон изменения входа [0 10].

net = newff([0 10],[5 1],{`tansig' `purelin'});

Обучим сеть в течение 50 циклов:

net.trainParam.epochs = 50;

net = train(net,P,T);

Выполним моделирование сети и построим графики сигналов выхода и цели.

Y = sim(net,P);

plot(P, Т, P, Y)

Пример 2:

Построить нейронную сеть для распознавания индексов на почтовых конвертах.

Для этих целей будет использована двухслойная структура нейронной сети. На вход будут подаваться цвета пикселей, из которых состоит изображение цифры. Количество входных нейронов - это произведение ширины изображения цифры на высоту. Выходных нейронов будет столько, сколько предполагается распознавать образов: 10 цифр - 10 образов.

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

Рис. 17 Распознаваемые символы

В данном случае их размеры: 11 на 21 пикселей.

2) Загружаем эти символы в Matlab.

File=>Import data

После загрузки в поле WorkSpace появится структура, состоящая из двух массивов. В одном из них содержится цвет каждого пикселя. С его помощью и будем формировать обучающую выборку.

a0=A0.cdata; % запишем этот массив в переменную. И так для каждой цифры. Необходимо привести массив к нужному виду.

a0=double(a0); %привести к нужному типу

a0=a0'; %транспонировать

a0=reshape(a0,231,1); % перевести в вектор-столбец. 231 = 11*21 пикселей.

Таким образом создан вектор-столбец цифры ноль. Указанные набор действий повторяется для каждой цифры.



Рис. 18 Интерфейс загрузки изображений в Matlab

Далее создадим общий массив цифр: это основная часть обучающей выборки.

chisla=[a0 a1 a2 a3 a4 a5 a6 a7 a8 a9];

Далее создается массив ожидаемых результатов - «целей» target. В нем по главной диагонали будут 1, все остальные - нули. Размер: 10*10 (так как мы распознаем 10 цифр).

target=eye(10);

3) Затем создается программа просмотра полученных цифр. File=>New=>M-file.

Ниже приведено содержимое созданного файла-функции myplotchar.m:

function myplotchar(c)

x1 = [-0.5 -0.5 +0.5 +0.5 -0.5];

y1 = [-0.5 +0.5 +0.5 -0.5 -0.5];

x2 = [x1 +0.5 +0.5 -0.5];

y2 = [y1 +0.5 -0.5 +0.5];

newplot;

plot(x1*11.6+2.5,y1*21.6+10.5,'m');

axis([-1.5 11.5 -0.5 21.5]);

axis('equal')

axis off

hold on

for i=1:length(c)

x = rem(i-1,11)-2.5;

y = 6-floor((i-1)/11)+14.5;

plot(x2*(1-c(i))+x,y2*(1-c(i))+y);

end

hold off

%--------------------------------------------------

Результат вызова команды myplotchar(a1):

Рис.19 Результат вызова команды myplotchar(a1)

4) Создается программа, генерирующая описанную выше нейронную сеть и обучающая ее.

Содержимое m-файла letter.m:

[R,Q]=size(chisla); % берем размерности массива чисел R=231, Q=10

[S2,Q]=size(target); %S2- количество вариантов: 10 распознаваемых чисел

S1=231; % в первом слое должно быть столько нейронов, сколько пикселей в подаваемом изображении

net=newff(minmax(chisla),[S1 S2],{'logsig' 'purelin'},'traingdx'); % %minmax(chisla) определит минимальное и максимальное число в %каждой строке. Поскольку у нас только черный и белый цвет в %изображениях цифр, минимальное число подаваемое на вход сети - 0, %максимальное - 1.

net.LW{2,1}=net.LW{2,1}*0.01;

net.b{2}=net.b{2}*0.01;

gensim(net) %генерируем сеть

P=chisla; % входные сигналы обучающей выборки

T=target; % ожидаемые выходные сигналы

net.performFcn='sse';

net.trainParam.goal=0.01; % требуемая ошибка обучения

net.trainParam.show=20;

net.trainParam.epochx=5000; % количество тактов обучения

net.trainParam.mc=0.95;

[net,tr]=train(net, P, T); % запуск процесса обучения

Далее следует набрать в командной строке matlab команду letter.

>>letter

Рис. 20 Модель полученной сети

Рис. 21 График процесса обучения нейронной сети



5) Следует проверить насколько уверенно построенная нейронная сеть распознает примеры из обучающей выборки (команда sim (<имя сети>,<имя примера>)):

Рис. 22 Результаты работы сети по распознаванию примеров из обучающей выборки

Сеть уверенно распознает символы.

6) Следует проверить способность распознавания сетью зашумленных символов.

>> simvol=chisla(:,1)+randn(231,1)*0.2; % создаем символ, %зашумленный на 20%

>> myplotchar(simvol) % нарисуем его



Рис. 23 Вид зашумленного символа «0»

>> rez=sim(net,noisyJ)

rez =

0.9161

-0.0745

0.0615

0.0218

0.0713

0.0061

-0.0039

0.0102

0.0453

0.0233

Сеть распознала символ «0».

4.3 Порядок выполнения лабораторной работы

Используя описанный выше метод, в пакете Matlab построить нейронную сеть для распознавания символов на изображениях. Изображения следует выбрать самостоятельно. Количество распознаваемых изображений - не менее 10. Размер изображений - не менее 30*30 пикселей. Первоначально построить двухслойную сеть - количество нейронов во входном слое есть произведение ширины изображения на высоту, в выходном слое - количество распознаваемых изображений. Обучить сеть. Проверить работу сети на зашумленных и незашумленных символах. Сделать выводы.

4.4 Контрольные вопросы

1. Что называется обучением НС?

2. Методы обучения сетей.

3. Обосновать достоинства и недостатки методов обучения НС.

4. Способность НС к обобщению. Как с течением процесса обучения изменяются ошибка обучения и ошибка обобщения.

4.5 Оформление отчета по лабораторной работе

Текстовый файл в формате .doc

1. В отчете следует привести код созданных m-файлов, реализующих обучение нейронной сети согласно варианту и процесс вывода изображения на экран, а также скриншоты структуры нейронной сети, графика процесса обучения, результатов работы нейронной сети на зашумленных и незашумленных символах.

2. Выводы по итогам работы.

Лабораторная работа №5

Оптимизация функции с помощью генетических алгоритмов

5.1 Цель работы

Изучить на практике принцип применения генетических алгоритмов для решения задач оптимизации.

5.2 Теоретическое введение

Генетический алгоритм представляет собой метод, отражающий естественную эволюцию методов решения проблем, и в первую очередь задач оптимизации. Генетические алгоритмы - это процедуры поиска, основанные на механизмах естественного отбора и наследования. В них используется эволюционный принцип выживания наиболее приспособленных особей. Они отличаются от традиционных методов оптимизации несколькими базовыми элементами. В частности, генетические алгоритмы:

1) обрабатывают не значения параметров самой задачи, а их закодированную форму;

2) осуществляют поиск решения исходя не из единственной точки, а из их некоторой популяции;

3) используют только целевую функцию, а не ее производные либо иную дополнительную информацию;

4) применяют вероятностные, а не детерминированные правила выбора.

Перечисленные четыре свойства, которые можно сформулировать также как кодирование параметров, операции на популяциях, использование минимума информации о задаче и рандомизация операций, приводят в результате к устойчивости генетических алгоритмов и к их превосходству над другими широко применяемыми технологиями.

Основные понятия генетических алгоритмов

При описании генетических алгоритмов используются определения, заимствованные из генетики. Например, речь идет о популяции особей, а в качестве базовых понятий применяются ген, хромосома, генотип, фенотип, аллель. Также используются соответствующие этим терминам определения из технического лексикона, в частности, цепь, двоичная последовательность, структура.

Популяция - это конечное множество особей.

Особи, входящие в популяцию, в генетических алгоритмах представляются хромосомами с закодированными в них множествами параметров задачи, т.е. решений, которые иначе называются точками в пространстве поиска (search points). В некоторых работах особи называются организмами.

Хромосомы (другие названия - цепочки или кодовые последовательности) - это упорядоченные последовательности генов.

Ген (также называемый свойством, знаком или детектором) - это атомарный элемент генотипа, в частности, хромосомы.

Генотип или структура - это набор хромосом данной особи. Следовательно, особями популяции могут быть генотипы либо единичные хромосомы (в довольно распространенном случае, когда генотип состоит из одной хромосомы).

Фенотип - это набор значений, соответствующих данному генотипу, т.е. декодированная структура или множество параметров задачи (решение, точка пространства поиска).

Аллель - это значение конкретного гена, также определяемое как значение свойства или вариант свойства.

Локус или позиция указывает место размещения данного гена в хромосоме (цепочке). Множество позиций генов - это локи.

Очень важным понятием в генетических алгоритмах считается функция приспособленности (fitness function), иначе называемая функцией оценки. Она представляет меру приспособленности данной особи в популяции. Эта функция играет важнейшую роль, поскольку позволяет оценить степень приспособленности конкретных особей в популяции и выбрать из них наиболее приспособленные (т.е. имеющие наибольшие значения функции приспособленности) в соответствии с эволюционным принципом выживания «сильнейших» (лучше всего приспособившихся). Функция приспособленности также получила свое название непосредственно из генетики. Она оказывает сильное влияние на функционирование генетических алгоритмов и должна иметь точное и корректное определение. В задачах оптимизации функция приспособленности, как правило, оптимизируется (точнее говоря, максимизируется) и называется целевой функцией. В задачах минимизации целевая функция преобразуется, и проблема сводится к максимизации. В теории управления функция приспособленности может принимать вид функции погрешности, а в теории игр - стоимостной функции. На каждой итерации генетического алгоритма приспособленность каждой особи данной популяции оценивается при помощи функции приспособленности, и на этой основе создается следующая популяция особей, составляющих множество потенциальных решений проблемы, например, задачи оптимизации.

Очередная популяция в генетическом алгоритме называется поколением, а к вновь создаваемой популяции особей применяется термин «новое поколение» или «поколение потомков».

Основной (классический) генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

1) инициализация, или выбор исходной популяции хромосом;

2) оценка приспособленности хромосом в популяции;

3) проверка условия остановки алгоритма;

4) селекция хромосом;

5) применение генетических операторов;

6) формирование новой популяции;

7) выбор «наилучшей» хромосомы.

Блок-схема основного генетического алгоритма изображена на рис.24. Рассмотрим конкретные этапы этого алгоритма более подробно.

Инициализация, т.е. формирование исходной популяции, заключается в случайном выборе заданного количества хромосом (особей), представляемых двоичными последовательностями фиксированной длины.

Рис. 24 Блок-схема генетического алгоритма

Оценивание приспособленности хромосом в популяции состоит в расчете функции приспособленности для каждой хромосомы этой популяции. Чем больше значение этой функции, тем выше «качество» хромосомы. Форма функции приспособленности зависит от характера решаемой задачи. Предполагается, что функция приспособленности всегда принимает неотрицательные значения и, кроме того, что для решения оптимизационной задачи требуется максимизировать эту функцию. Если исходная форма функции приспособленности не удовлетворяет этим условиям, то выполняется соответствующее преобразование (например, задачу минимизации функции можно легко свести к задаче максимизации).

Проверка условия остановки алгоритма. Определение условия остановки генетического алгоритма зависит от его конкретного применения. В оптимизационных задачах, если известно максимальное (или минимальное) значение функции приспособленности, то остановка алгоритма может произойти после достижения ожидаемого оптимального значения, возможно - с заданной точностью. Остановка алгоритма также может произойти в случае, когда его выполнение не приводит к улучшению уже достигнутого значения. Алгоритм может быть остановлен по истечении определенного времени выполнения либо после выполнения заданного количества итераций. Если условие остановки выполнено, то производится переход к завершающему этапу выбора «наилучшей» хромосомы. В противном случае на следующем шаге выполняется селекция.

Селекция хромосом заключается в выборе (по рассчитанным на втором этапе значениям функции приспособленности) тех хромосом, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наибольшими значениями функции приспособленности. Существуют различные методы селекции. Наиболее популярным считается так называемый метод рулетки (roulette wheel selection), который свое название получил по аналогии с известной азартной игрой. Каждой хромосоме может быть сопоставлен сектор колеса рулетки, величина которого устанавливается пропорциональной значению функции приспособленности данной хромосомы. Поэтому чем больше значение функции приспособленности, тем больше сектор на колесе рулетки. Все колесо рулетки соответствует сумме значений функции приспособленности всех хромосом рассматриваемой популяции. Каждой хромосоме, обозначаемой ch_i для i = 1, 2, .... N (где N обозначает численность популяции) соответствует сектор колеса v(ch_i), выраженный в процентах согласно формуле



(27)

(28)

причем F(ch_i) - значение функции приспособленности хромосомы ch_i, a p_s(ch_i) - вероятность селекции хромосомы ch_i. Селекция хромосомы может быть представлена как результат поворота колеса рулетки, поскольку «выигравшая» (т.е. выбранная) хромосома относится к выпавшему сектору этого колеса. Очевидно, что чем больше сектор, тем больше вероятность «победы» соответствующей хромосомы. Поэтому вероятность выбора данной хромосомы оказывается пропорциональной значению ее функции приспособленности. Если всю окружность колеса рулетки представить в виде цифрового интервала [0, 100], то выбор хромосомы можно отождествить с выбором числа из интервала [а, b], где а и b обозначают соответственно начало и окончание фрагмента окружности, соответствующего этому сектору колеса; очевидно, что 0 ? а < b ? 100. В этом случае выбор с помощью колеса рулетки сводится к выбору числа из интервала [0, 100], которое соответствует конкретной точке на окружности колеса. Другие методы селекции будут рассмотрены ниже.

В результате процесса селекции создается родительская популяция, также называемая родительским пулом (mating pool) с численностью N, равной численности текущей популяции.

Применение генетических операторов к хромосомам, отобранным с помощью селекции, приводит к формированию новой популяции потомков от созданной на предыдущем шаге родительской популяции.

В классическом генетическом алгоритме применяются два основных генетических оператора: оператор скрещивания (crossover) и оператор мутации (mutation). Однако следует отметить, что оператор мутации играет явно второстепенную роль по сравнению с оператором скрещивания. Это означает, что скрещивание в классическом генетическом алгоритме производится практически всегда, тогда как мутация - достаточно редко. Вероятность скрещивания, как правило, достаточно велика (обычно 0,5 ? р_с ? 1), тогда как вероятность мутации устанавливается весьма малой (чаще всего 0 ? р_т ? 0,1). Это следует из аналогии с миром живых организмов, где мутации происходят чрезвычайно редко.

В генетическом алгоритме мутация хромосом может выполняться на популяции родителей перед скрещиванием либо на популяции потомков, образованных в результате скрещивания.

Оператор скрещивания. На первом этапе скрещивания выбираются пары хромосом из родительской популяции (родительского пула). Это временная популяция, состоящая из хромосом, отобранных в результате селекции и предназначенных для дальнейших преобразований операторами скрещивания и мутации с целью формирования новой популяции потомков. На данном этапе хромосомы из родительской популяции объединяются в пары. Это производится случайным способом в соответствии с вероятностью скрещивания р_с. Далее для каждой пары отобранных таким образом родителей разыгрывается позиция гена (локус) в хромосоме, определяющая так называемую точку скрещивания. Если хромосома каждого из родителей состоит из L генов, то очевидно, что точка скрещивания l_k представляет собой натуральное число, меньшее L. Поэтому фиксация точки скрещивания сводится к случайному выбору числа из интервала [1, L-1]. В результате скрещивания пары родительских хромосом получается следующая пара потомков:

1) потомок, хромосома которого на позициях от 1 до l_k состоит из генов первого родителя, а на позициях от l_k + 1 до L - из генов второго родителя;

2) потомок, хромосома которого на позициях от 1 до l_k состоит из генов второго родителя, а на позициях от l_k + 1 до L - из генов первого родителя.

Оператор мутации с вероятностью р_т изменяет значение гена в хромосоме на противоположное (т.е. с 0 на 1 или обратно). Например, если в хромосоме [100110101010] мутации подвергается ген на позиции 7, то его значение, равное 1, изменяется на 0, что приводит к образованию хромосомы [100110001010]. Как уже упоминалось выше, вероятность мутации обычно очень мала, и именно от нее зависит, будет данный ген мутировать или нет. Вероятность р_т мутации может эмулироваться, например, случайным выбором числа из интервала [0, 1] для каждого гена и отбором для выполнения этой операции тех генов, для которых разыгранное число оказывается меньшим или равным значению р_т.

Формирование новой популяции. Хромосомы, полученные в результате применения генетических операторов к хромосомам временной родительской популяции, включаются в состав новой популяции. Она становится так называемой текущей популяцией для данной итерации генетического алгоритма. На каждой очередной итерации рассчитываются значения функции приспособленности для всех хромосом этой популяции, после чего проверяется условие остановки алгоритма и либо фиксируется результат в виде хромосомы с наибольшим значением функции приспособленности, либо осуществляется переход к следующему шагу генетического алгоритма, т.е. к селекции. В классическом генетическом алгоритме вся предшествующая популяция хромосом замещается новой популяцией потомков, имеющей ту же численность.

Выбор «наилучшей» хромосомы. Если условие остановки алгоритма выполнено, то следует вывести результат работы, т.е. представить искомое решение задачи. Лучшим решением считается хромосома с наибольшим значением функции приспособленности.

Пример.

Рассмотрим сильно упрощенный и довольно искусственный пример, состоящий в нахождении хромосомы с максимальным количеством единиц. Допустим, что хромосомы состоят из 12 генов, а популяция насчитывает 8 хромосом. Понятно, что наилучшей будет хромосома, состоящая из 12 единиц. Посмотрим, как протекает процесс решения этой весьма тривиальной задачи с помощью генетического алгоритма.

Инициализация, или выбор исходной популяции хромосом. Необходимо случайным образом сгенерировать 8 двоичных последовательностей длиной 12 битов. Это можно достигнуть, например, подбрасыванием монеты (96 раз, при выпадении «орла» приписывается значение 1, а в случае «решки» - 0). Таким образом, можно сформировать исходную популяцию

сh₁ = [111001100101] ch₅ = [010001100100]

ch₂ = [001100111010] ch₆ = [010011000101]

ch₃ = [011101110011] ch₇ = [101011011011]

ch₄ = [001000101000] ch₈ = [000010111100]

Оценка приспособленности хромосом в популяции. В рассматриваемом упрощенном примере решается задача нахождения такой хромосомы, которая содержит наибольшее количество единиц. Поэтому функция приспособленности определяет количество единиц в хромосоме. Обозначим функцию приспособленности символом F. Тогда ее значения для каждой хромосомы из исходной популяции будут такие:

F(ch₁) = 7 F(ch₅) = 4

F(ch₂) = 6 F(ch₆) = 5

F(ch₃) = 8 F(ch₇) = 8

F(ch₄) = 3 F(ch₈) = 5

Хромосомы ch₃ и ch₇ характеризуются наибольшими значениями функции принадлежности. В этой популяции они считаются наилучшими кандидатами на решение задачи. Если в соответствии с блок-схемой генетического алгоритма (рис.24) условие остановки алгоритма не выполняется, то на следующем шаге производится селекция хромосом из текущей популяции.

Селекция хромосом. Селекция производится методом рулетки. На основании формул (27) и (28) для каждой из 8 хромосом текущей популяции (в нашем случае - исходной популяции, для N = 8) получаем секторы колеса рулетки, выраженные в процентах (рис.25):

v(ch₁) = 15,22 v(ch₅) = 8,70

v(ch₂) = 13,04 v(ch₆) = 10,87

v(cn₃) = 17,39 v(ch₇) = 17,39

v(ch₄) = 6,52 v(ch₈) = 10,87

Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствующий сектор на колесе, т.е. на конкретную хромосому. Допустим, что разыграны следующие 8 чисел: 79 44 9 74 44 86 48 23

Рис. 25 Колесо рулетки

Это означает выбор хромосом ch₇ ch₃ ch₁ ch₇ ch₃ ch₇ ch₄ ch₂

Как видно, хромосома ch₇ была выбрана трижды, а хромосома ch₃ - дважды. Заметим, что именно эти хромосомы имеют наибольшее значение функции приспособленности. Однако выбрана и хромосома ch₄ с наименьшим значением функции приспособленности. Все выбранные таким образом хромосомы включаются в так называемый родительский пул.

Применение генетических операторов. Допустим, что ни одна из отобранных в процессе селекции хромосом не подвергается мутации, и все они составляют популяцию хромосом, предназначенных для скрещивания. Это означает, что вероятность скрещивания р_с = 1, а вероятность мутации р_m = 0. Допустим, что из этих хромосом случайным образом сформированы пары родителей ch₂ и ch₇ ch₁ и ch₇ ch₃ и ch₄ ch₃ и ch₇

Для первой пары случайным образом выбрана точка скрещивания l_k = 4, для второй - l_k = 3, для третьей - l_k = 11, для четвертой - l_k = 5. При этом процесс скрещивания протекает так как показано на рис.26. В результате выполнения оператора скрещивания получаются 4 пары потомков.

Если бы при случайном подборе пар хромосом для скрещивания были объединены, например, ch₃ с ch₃ и ch₄ с ch₇ вместо ch₃ с ch₄ и ch₃ с ch₇, а другие пары остались без изменения, то скрещивание ch₃ с ch₃ дало бы две такие же хромосомы независимо от разыгранной точки скрещивания. Это означало бы получение двух потомков, идентичных своим родителям. Заметим, что такая ситуация наиболее вероятна для хромосом с наибольшим значением функции приспособленности, т.е. именно такие хромосомы получают наибольшие шансы на переход в новую популяцию.

Формирование новой популяции. После выполнения операции скрещивания мы получаем (согласно рис.26) следующую популяцию потомков:

Ch₁ = [001111011011] Ch₅ = [011101110010]

Ch₂ = [101000111010] Ch₆ = [001000101001]

Ch₃ = [111011011011] Ch₇ = [011101011011]

Ch₄ = [101001100101] Ch₈ = [101011110011]



Для отличия от хромосом предыдущей популяции обозначения вновь сформированных хромосом начинаются с заглавной буквы С.

Согласно блок-схеме генетического алгоритма производится возврат ко второму этапу, т.е. к оценке приспособленности хромосом из вновь сформированной популяции, которая становится текущей.

Значения функций приспособленности хромосом этой популяции составляют

F(Ch₁) = 8 F(Ch₅) = 7

F(Ch₂) = 6 F(Ch₆) = 4

F(Ch₃) = 9 F(Ch₇) = 8

F(Ch₄) = 6 F(Ch₈) = 8

Заметно, что популяция потомков характеризуется гораздо более высоким средним значением функции приспособленности, чем популяция родителей. Обратим внимание, что в результате скрещивания получена хромосома Сh₃ с наибольшим значением функции приспособленности, которым не обладала ни одна хромосома из родительской популяции. Однако могло произойти и обратное, поскольку после скрещивания на первой итерации хромосома, которая в родительской популяции характеризовалась наибольшим значением функции приспособленности, могла просто «потеряться». Помимо этого «средняя» приспособленность новой популяции все равно оказалась бы выше предыдущей, а хромосомы с большими значениями функции приспособленности имели бы шансы появиться в следующих поколениях.



Рис. 26 Процесс скрещивания хромосом

Методы селекции

Основанный на принципе колеса рулетки метод селекции, считается для генетических алгоритмов основным методом отбора особей для родительской популяции с целью последующего их преобразования генетическими операторами, такими как скрещивание и мутация. Несмотря на случайный характер процедуры селекции, родительские особи выбираются пропорционально значениям их функций приспособленности, т.е. согласно вероятности селекции. Каждая особь получает в родительском пуле такое количество своих копий, какое устанавливается выражением:

e(ch_i) = p_s(ch_i) * N , (29)

где N - количество хромосом ch_i, i = 1,2, ..., N в популяции, a p_s(ch_i) ? вероятность селекции хромосомы ch_i, рассчитываемая по формуле (28). Строго говоря, количество копий данной особи в родительском пуле равно целой части от e(ch_i). При использовании формулы (29) необходимо обращать внимание на то, что e(ch_i) = F(ch_i)/F, где - среднее значение функции приспособленности в популяции. Очевидно, что метод рулетки можно применять тогда, когда значения функции приспособленности положительны. Этот метод может использоваться только в задачах максимизации функции (но не минимизации).

Очевидно, что проблему минимизации можно легко свести к задаче максимизации функции и обратно. В некоторых реализациях генетического алгоритма метод рулетки применяется для поиска минимума функции (а не максимума). Это результат соответствующего преобразования, выполняемого программным путем для удобства пользователей, поскольку в большинстве прикладных задач решается проблема минимизации (например, затрат, расстояния, погрешности и т.п.). Однако возможность применения метода рулетки всего лишь для одного класса задач, т.е. только для максимизации (или только для минимизации) можно считать его несомненным недостатком. Другая слабая сторона этого метода заключается в том, что особи с очень малым значением функции приспособленности слишком быстро исключаются из популяции, что может привести к преждевременной сходимости генетического алгоритма.

С учетом отмеченных недостатков метода рулетки созданы и используются альтернативные алгоритмы селекции. Один из них называется турнирным методом (tournament selection). Наряду с методом рулетки и ранговым методом он применяется как один из основных алгоритмов селекции. Представим эти методы подробнее.

При турнирной селекции все особи популяции разбиваются на подгруппы с последующим выбором в каждой из них особи с наилучшей приспособленностью. Различаются два способа такого выбора: детерминированный выбор (deterministic tournament selection) и случайный выбор (stochastic tournament selection). Детерминированный выбор осуществляется с вероятностью, равной 1, а случайный выбор - с вероятностью, меньшей 1. Подгруппы могут иметь произвольный размер, но чаще всего популяция разделяется на подгруппы по 2 - 3 особи в каждой.

Турнирный метод пригоден для решения задач как максимизации, так и минимизации функции. Помимо того, он может быть легко распространен на задачи, связанные с многокритериальной оптимизацией, т.е. на случай одновременной оптимизации нескольких функций. В турнирном методе допускается изменение размера подгрупп, на которые подразделяется популяция (tournament size). Исследования подтверждают, что турнирный метод действует эффективнее, чем метод рулетки. На рис.27 представлена схема, которая иллюстрирует метод турнирной селекции для подгрупп, состоящих из двух особей. Такую схему легко обобщить на подгруппы большего размера. Это одно из возможных приложений рассматриваемого алгоритма селекции.

При ранговой селекции (ranking selection) особи популяции ранжируются по значениям их функции приспособленности. Это можно представить себе как отсортированный список особей, упорядоченных по направлению от наиболее приспособленных к наименее приспособленным (или наоборот), в котором каждой особи приписывается число, определяющее ее место в списке и называемое рангом (rank). Количество копий M(k) каждой особи, введенных в родительскую популяцию, рассчитывается по априорно заданной функции в зависимости от ранга особи. Пример такой функции показан на рис. 28.

Достоинство рангового метода заключается в возможности его применения как для максимизации, так и для минимизации функции.

Он также не требует масштабирования из-за проблемы преждевременной сходимости, актуальной для метода рулетки.

Существуют различные варианты алгоритмов селекции. Представленные ранее методы (рулетки, турнирный и ранговый) применяются чаще всего.



Рис. 27 Схема турнирной селекции для подгрупп, состоящих из двух особей

Рис. 28 Пример функции, определяющей зависимость количества копий особи в родительском пуле от его ранга при ранговой селекции

5.3 Порядок выполнения лабораторной работы

5.3.1 Выбрать функцию и диапазон согласно варианту.

5.3.2 Построить график функции.

5.3.3 Написать программу нахождения максимума и минимума функции на заданном диапазоне с помощью генетических алгоритмов.

5.3.4 Проанализировать полученные результаты и сделать выводы.

5.3.5 Описать выполнение лабораторной работы в

Таблица 5 Варианты заданий

№	Функция
5.	Y(x)=x*sin(5*x), x=[-2…5]
6.	Y(x)=1/x*sin(5*x), x=[-5…5]
7.	Y(x)=2^x*sin(10x), x=[-3…3]
8.	Y(x)=x^(1/2)*sin(10*x), x=[0…5]
9.	Y(x)=15*sin(10*x)*cos(3*x), x=[-3…3]
10.	Y(x)=5*sin(10*x)*sin(3*x), x=[0…4]
11.	Y(x)=sin(10*x)*sin(3*x)/(x^2), x=[0…4]
12.	Y(x)=5*sin(10*x)*sin(3*x)/(x^(1/2)), x=[1…7]
13.	Y(x)=5*cos(10*x)*sin(3*x)/(x^(1/2)), x=[0…5]
14.	Y(x)=-5*cos(10*x)*sin(3*x)/(x^(1/2))x=[0…10]
15.	Y(x)=-5*cos(10*x)*sin(3*x)/(x^x), x=[0…5]
16.	Y(x)=5*sin(10*x)*sin(3*x)/(x^x),x=[0…8]
17.	Y(x)=x^sin(10*x),x=[1…10]
18.	Y(x)=-x^cos(5*x), x=[0…10]
19.	Y(x)=x^cos(x^2),x=[0…10]
20.	Y(x)=cos(x^2)/x, x=[0…5]
21.	Y(x)= 10*cos(x^2)/x^2, x=[0…4]
22.	Y(x)=(1/x)*cos(x^2+1/x), x=[1…10]
23.	Y(x)=sin(x)*(1/x)*cos(x^2+1/x), x=[-2…2]
24.	Y(x)=5*sin(x)*cos(x^2+1/x)^2,x=[1…10]
25.	Y(x)=5*sin(1/x)*cos(x^2+1/x)^2, x=[1…4]
26.	Y(x)=5*sin(1/x)*cos(x^2)^3,x=[-4…4]
27.	Y(x)=(x^3)*cos(x^2),x=[-2…2]
28.	Y(x)= (x^3)+cos(15*x),x=[-2…2]
29.	Y(x)= (3^x)+cos(15*x), x=[-1…2]

5.4 Контрольные вопросы

1. Определите следующие термины: ген, хромосома, мутация, эволюция, селекция, репродукция., популяция, генотип.

2. Что представляют собой генетические алгоритмы? В чем заключается их основное отличие от традиционных методов оптимизации?

3. Что такое функция приспособленности (оценки)? В чем состоит ее назначение?

4. Опишите классический генетический алгоритм. Каковы его основные шаги? В чем заключается цель каждого из них?

5.5 Оформление отчета по лабораторной работе

Текстовый файл в формате .doc

1. В отчете следует привести код программы, реализующей генетический алгоритм оптимизации выбранной функции на заданном интервале согласно варианту, а также скриншоты результатов работы программы и график оптимизируемой функции.

2. Выводы по итогам работы.

Лабораторная работа №6

Использование муравьиных алгоритмов для решения задачи поиска оптимального маршрута в графе

6.1 Цель работы

Изучить метод муравьиных колоний. Научиться решать задачи комбинаторной оптимизации с помощью метода муравьиных колоний.

6.2 Теоретическое введение

Алгоритмы муравья, или оптимизация по принципу муравьиной колонии (создатель алгоритма - Марко Дориго), основаны на применении нескольких агентов и обладают специфическими свойствами, присущими муравьям, и используют их для ориентации в физическом пространстве. Алгоритмы муравья особенно интересны потому, что их можно использовать для решения не только статических, но и динамических проблем, например, в изменяющихся сетях.

Идея алгоритма

Два муравья из муравейника должны добраться до пищи, которая находится за препятствием. Во время перемещения каждый муравей выделяет немного феромона, используя его в качестве маркера.

Рис. 29 Начальная позиция



При прочих равных каждый муравей выберет свой путь. Первый муравей выбирает верхний путь, а второй - нижний. Так как нижний путь в два раза короче верхнего, второй муравей достигнет цели за время t₁. Первый муравей в этот момент пройдет только половину пути (рис. 30).

Когда один муравей достигает пищи, он берет один из объектов и возвращается к муравейнику по тому же пути. За время t₂ второй муравей вернулся в муравейник с пищей, а первый муравей достиг пищи (рис. 31).

При перемещении каждого муравья на пути остается немного феромона. Для первого муравья за время t₂ путь был покрыт феромонами только один раз. В то же самое время второй муравей покрыл путь феромонами дважды. За время t₄ первый муравей вернулся в муравейник, а второй муравей уже успел еще раз сходить к еде и вернуться. При этом концентрация феромона на нижнем пути будет в два раза выше, чем на верхнем. Поэтому первый муравей в следующий раз выберет нижний путь, поскольку там концентрация феромона выше.

Рис. 30 Промежуточная позиция №1 Рис. 31 Промежуточная позиция №2

В этом и состоит базовая идея алгоритма муравья - оптимизация путем непрямой связи между автономными агентами.

Пошаговое описание общей схемы

Предположим, что окружающая среда для муравьев представляет собой полный неориентированный граф. Каждое ребро имеет вес, который обозначается как расстояние между двумя вершинами, соединенными им. Граф двунаправленный, поэтому муравей может путешествовать по грани в любом направлении (рис. 32).

Рис. 32 Пример двунаправленного графа

Вероятность включения ребра в маршрут отдельного муравья пропорциональна количеству феромонов на этом ребре, а количество откладываемого феромона пропорционально длине маршрута. Чем короче маршрут тем больше феромона будет отложено на его ребрах, следовательно, большее количество муравьев будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости - большинство муравьев двигается по локально-оптимальному маршруту. Избежать этого можно моделируя отрицательно обратную связь в виде испарения феромона. Причем, если феромон испаряется быстро, то это приводит к потере памяти колонии и забыванию хороших решений, с другой стороны, большое время испарений может привести к получению устойчивого локального оптимального решения.

Муравей

Муравей - это программный агент, который является членом большой колонии и используется для решения какой-либо проблемы. Муравей снабжается набором простых правил, которые позволяют ему выбирать путь в графе. Он поддерживает список узлов, которые он уже посетил. Таким образом, муравей должен проходить через каждый узел только один раз. Путь между двумя узлами графа, по которому муравей посетил каждый узел только один раз, называется путем Гамильтона.

Узлы в списке "текущего путешествия" располагаются в том порядке, в котором муравей посещал их. Позже список используется для определения протяженности пути между узлами. Настоящий муравей во время перемещения по пути будет оставлять за собой феромоны. В алгоритме муравья агент оставляет феромоны на ребрах графа после завершения путешествия.

Стартовая точка, куда помещается муравей, зависит от ограничений, накладываемых условиями задачи, так как для каждой задачи способ размещения муравьев является определяющим. Либо все они помещаются в одну точку, либо в разные с повторениями, либо без повторений.

На этом же этапе задается начальный уровень феромона. Он инициализируется небольшим положительным числом для того, чтобы на начальном шаге вероятности перехода в следующую вершину не были нулевыми.

Движение муравья

Движение муравья основывается на вероятностном уравнении. Если муравей еще не закончил путь, то есть не посетил все узлы сети, для определения следующего ребра пути используется формула:

(30)

Здесь ф(r,u) - интенсивность фермента на ребре между узлами r и u, з(r,u) - функция, которая представляет измерение обратного расстояния для грани, б - вес фермента, a и в - коэффициент эвристики. Параметры б и в определяют относительную значимость двух параметров, а также их влияние на уравнение. Так как муравей путешествует только по узлам, которые еще не были посещены (как указано списком табу), вероятность рассчитывается только для ребер, которые ведут к еще не посещенным узлам. Переменная k представляет эти ребра.

Путешествие муравья

Пройденный муравьем путь отображается, когда муравей посетит все узлы графа. Циклы запрещены, поскольку в алгоритм включен список табу. После завершения длина пути может быть подсчитана - она равна сумме длин всех ребер, по которым путешествовал муравей. Формула (31) показывает количество феромона, который был оставлен на каждом ребре пути для муравья k. Переменная Q является константой.

(31)

Результат уравнения является средством измерения пути, - короткий путь характеризуется высокой концентрацией феромонов, а более длинный путь - более низкой. Затем полученный результат используется в формуле (32), чтобы увеличить количество феромона вдоль каждого ребра пройденного муравьем пути.

(32)

Важно, что данная формула применяется ко всему пути, при этом каждое ребро помечается феромоном пропорционально длине пути. Поэтому следует дождаться, пока муравей закончит путешествие и только потом обновить уровни феромона, в противном случае истинная длина пути останется неизвестной. Константа p - значение между 0 и 1.

Испарение феромонов

В начале пути у каждого ребра есть шанс быть выбранным. Чтобы постепенно удалить ребра, которые входят в худшие пути графа, ко всем ребрам применяется процедура испарения феромона:



(33)

Для испарения феромона используется обратный коэффициент обновления пути.

Повторный запуск

После того как путь муравья завершен, ребра обновлены в соответствии с длиной пути и произошло испарение феромона на всех ребрах, алгоритм запускается повторно. Список табу очищается, и длина пути обнуляется. Муравьям разрешается перемещаться по графу, основывая выбор ребра на формуле (30). Этот процесс может выполняться для постоянного количества путей или до момента, когда на протяжении нескольких запусков не было отмечено повторных изменений. Затем определяется лучший путь, который и является решением.

Последовательность выполнения метода

Метод муравьиных колоний представляет собой следующую последовательность шагов.

Шаг 1. Задать параметры метода: б - коэффициент, который определяет относительную значимость пути (количество феромона на пути); в - параметр, который означает приоритет расстояния над количеством феромона; с - коэффициент количества феромона, который агент оставляет на пути, где (1-с) показывает коэффициент испарения феромона на пути после его завершения; Q - константа, которая относится к количеству феромона, который был оставлено на пути.

Шаг 2. Инициализация метода. Создание популяции агентов. После создания популяция агентов поровну распределяется по узлам сети. Необходимо равномерное распределение агентов между узлами, чтобы все узлы имели одинаковые шансы стать отправной точкой. Если все агенты начнут движение из одной точки, это будет означать, что данная точка полагается оптимальной для старта, а на самом деле она такой может и не быть.

Шаг 3. Движение агентов. Если агент еще не закончил путь, то есть не посетил все узлы сети, для определения следующей грани пути используется формула (30). Агент путешествует только по узлам, которые еще не были навещены им, то есть по узлам, которых не имеет в списке табу tlist. Поэтому вероятность рассчитывается только для граней, которые ведут к еще не посещенным узлам. По завершению итерации нас будут интересовать только те агенты, которые пройдут все узлы.

Шаг 4. Пройденный агентом путь отображается, когда агент посетит все узлы сети. Циклы запрещены, поскольку в метод включенный список табу tlist. После завершения может быть рассчитана длина пути. Она равняется сумме всех граней, по которым путешествовал агент. Количество феромона, которое было оставлено на каждой грани пути i- го агента, определяется по формуле (31).

Результат является средством измерения пути: короткий путь характеризуется высокой концентрацией феромона, а более длинный путь - более низкой. Потом полученный результат используется для увеличения количества феромона вдоль каждой грани пройденного i-ым агентом пути рассчитывается по формуле (32).

Формула (33) испарения феромона применяется ко всему пути, при этом каждая дуга обозначается феромоном пропорционально длине пути. Поэтому следует дождаться, пока агент закончит путешествие и только потом обновить уровень феромона, в противном случае действительная длина пути останется неизвестной. Константа с принимает значение между 0 и 1.