Главная » Налогообложение » Обучение методом обратного распространения ошибок. Процедура обратного распространения (описание алгоритма)

Обучение методом обратного распространения ошибок. Процедура обратного распространения (описание алгоритма)

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

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

кажущуюся простоту, требует громоздких рутинных вычислений И, наконец, третий, более приемлемый вариант - распространение сигналов ошибки от выходов нейронной сети к ее входам, в направлении, обратном прямому распространению сигналов в обычном режиме работы Этот алгоритм обучения получил название процедуры обратного распространения ошибки (error back propagation) Именно он рассматривается ниже

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

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

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

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

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

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

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

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

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

Здесь суммирование по выполняется среди нейронов слоя Введя новую переменную:

получим рекурсивную формулу для расчетов величин слоя из величин более старшего слоя

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

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

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

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

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

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

где - число нейронов в слое с учетом нейрона с постоянным выходным состоянием задающего смещение; вход нейрона у слоя

где - сигмоид,

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

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

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

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

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

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

где - число подстраиваемых весов, - число нейронов в выходном слое.

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

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

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

происходить неприемлемо медленно. С другой стороны, слишком большие коррекции весов могут привести к постоянной неустойчивости процесса обучения. Поэтому в качестве коэффициента скорости обучения 1] обычно выбирается число меньше 1 (например, 0,1), которое постепенно уменьшается в процессе обучения. Кроме того, для исключения случайных попаданий сети в локальные минимумы иногда, после стабилизации значений весовых коэффициентов, 7 кратковременно значительно увеличивают, чтобы начать градиентный спуск из новой точки. Если повторение этой процедуры несколько раз приведет сеть в одно и то же состояние, можно предположить, что найден глобальный минимум.

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

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

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

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

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

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

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

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

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

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

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

Как же выбрать правильную степень сложности сети? Почти всегда более сложная сеть дает меньшую ошибку, но это может свидетельствовать не о хорошем качестве модели, а о переобучении сети.

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

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

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

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

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

1) Функции ошибки:

Интегральные функции ошибки по всей совокупности обучающих примеров;

Функции ошибки целых и дробных степеней

2) Процедуры определения величины шага на каждой итерации

Дихотомия;

Инерционные соотношения (см выше);

3) Процедуры определения направления шага.

С использованием матрицы производных второго порядка (метод Ньютона);

С использованием направлений на нескольких шагах (партан метод).

Алгоритм обратного распространения ошибки является одним из методов обучения многослойных нейронных сетей прямого распространения, называемых также многослойными персептронами. Многослойные персептроны успешно применяются для решения многих сложных задач.

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

Рассмотрим работу алгоритма подробней. Допустим необходимо обучить следующую нейронную сеть, применив алгоритм обратного распространения ошибки:

На приведенном рисунке использованы следующие условные обозначения:

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

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

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

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

Инициализировать синаптические веса маленькими случайными значениями.
Выбрать очередную обучающую пару из обучающего множества; подать входной вектор на вход сети.
Вычислить выход сети.
Вычислить разность между выходом сети и требуемым выходом (целевым вектором обучающей пары).
Подкорректировать веса сети для минимизации ошибки (как см. ниже).
Повторять шаги с 2 по 5 для каждого вектора обучающего множества до тех пор, пока ошибка на всем множестве не достигнет приемлемого уровня.

Операции, выполняемые шагами 2 и 3, сходны с теми, которые выполняются при функционировании уже обученной сети, т.е. подается входной вектор и вычисляется получающийся выход. Вычисления выполняются послойно. На рис. 1 сначала вычисляются выходы нейронов слоя (слой входной, а значит никаких вычислений в нем не происходит), затем они используются в качестве входов слоя , вычисляются выходы нейронов слоя , которые и образуют выходной вектор сети . Шаги 2 и 3 образуют так называемый «проход вперед», так как сигнал распространяется по сети от входа к выходу.

Шаги 4 и 5 составляют «обратный проход», здесь вычисляемый сигнал ошибки распространяется обратно по сети и используется для подстройки весов.

Рассмотрим подробней 5 шаг – корректировка весов сети. Здесь следует выделить два нижеописанных случая.

Случай 1. Корректировка синаптических весов выходного слоя

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

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

Тогда, веса выходного слоя после коррекции будут равны:

Приведем пример вычислений для синаптического веса :

Случай 2. Корректировка синаптических весов скрытого слоя

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

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

Обновление правила цепочки

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

F(x)=A(B(C(x)))

A, B, и C — на различных слоях. Пользуясь правилом цепочки, мы легко вычисляем производную f(x) по x:

F′(x)=f′(A)⋅A′(B)⋅B′(C)⋅C′(x)

Что насчёт производной относительно B ? Чтобы найти производную по B , вы можете сделать вид, что B (C(x)) является константой, заменить ее переменной-заполнителем B , и продолжить поиск производной по B стандартно.

F′(B)=f′(A)⋅A′(B)

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

Применение правила цепочки

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

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

Cost=C(R(Z(XW)))

Используя правило цепочки, мы легко можем найти производную потери относительно веса W.

C′(W)=C′(R)⋅R′(Z)⋅Z′(W)=(y^−y)⋅R′(Z)⋅X

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

Какова производная от потери по Wo ?

C′(WO)=C′(y^)⋅y^′(ZO)⋅Z′O(WO)=(y^−y)⋅R′(ZO)⋅H

А что насчет Wh ? Чтобы узнать это, мы просто продолжаем возвращаться в нашу функцию, рекурсивно применяя правило цепочки, пока не доберемся до функции, которая имеет элемент Wh .

C′(Wh)=C′(y^)⋅O′(Zo)⋅Z′o(H)⋅H′(Zh)⋅Z′h(Wh)=(y^−y)⋅R′(Zo)⋅Wo⋅R′(Zh)⋅X

И просто забавы ради, что, если в нашей сети было бы 10 скрытых слоев. Что такое производная потери для первого веса w1?

C(w1)=(dC/dy^)⋅(dy^/dZ11)⋅(dZ11/dH10)⋅(dH10/dZ10)⋅(dZ10/dH9)⋅(dH9/dZ9)⋅(dZ9/dH8)⋅(dH8/dZ8)⋅(dZ8/dH7)⋅(dH7/dZ7)⋅(dZ7/dH6)⋅(dH6/dZ6)⋅(dZ6/dH5)⋅(dH5/dZ5)⋅(dZ5/dH4)⋅(dH4/dZ4)⋅(dZ4/dH3)⋅(dH3/dZ3)⋅(dZ3/dH2)⋅(dH2/dZ2)⋅(dZ2/dH1)⋅(dH1/dZ1)⋅(dZ1/dW1)

Заметили закономерность? Количество вычислений, необходимых для расчёта производных потерь, увеличивается по мере углубления нашей сети. Также обратите внимание на избыточность в наших расчетах производных . Производная потерь каждого слоя добавляет два новых элемента к элементам, которые уже были вычислены слоями над ним. Что, если бы был какой-то способ сохранить нашу работу и избежать этих повторяющихся вычислений?

Сохранение работы с мемоизацией

Мемоизация — это термин в информатике, имеющий простое значение: не пересчитывать одно и то же снова и снова . В мемоизации мы сохраняем ранее вычисленные результаты, чтобы избежать пересчета одной и той же функции. Это удобно для ускорения рекурсивных функций, одной из которых является обратное распространение. Обратите внимание на закономерность в уравнениях производных приведённых ниже.

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

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

Примечание: термин ошибка слоя относится к производной потерь по входу в слой. Он отвечает на вопрос: как изменяется выход функции потерь при изменении входа в этот слой?

Ошибка выходного слоя

Для расчета ошибки выходного слоя необходимо найти производную потерь по входу выходному слою, Zo . Это отвечает на вопрос: как веса последнего слоя влияют на общую ошибку в сети? Тогда производная такова:

C′(Zo)=(y^−y)⋅R′(Zo)

Чтобы упростить запись, практикующие МО обычно заменяют последовательность (y^−y)∗R"(Zo) термином Eo . Итак, наша формула для ошибки выходного слоя равна:

Eo=(y^−y)⋅R′(Zo)

Ошибка скрытого слоя

Для вычисления ошибки скрытого слоя нужно найти производную потерь по входу скрытого слоя, Zh .

Eh=Eo⋅Wo⋅R′(Zh)

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

Производная потерь по любому весу

Вернемся к нашей формуле для производной потерь по весу выходного слоя Wo .

C′(WO)=(y^−y)⋅R′(ZO)⋅H

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

C′(Wo)=Eo⋅H

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

C′(w)=CurrentLayerError⋅CurrentLayerInput

Примечание: вход относится к активации с предыдущего слоя, а не к взвешенному входу, Z.

Подводя итог

Вот последние 3 уравнения, которые вместе образуют основу обратного распространения.

Вот процесс, визуализированный с использованием нашего примера нейронной сети выше:

Обратное распространение: пример кода

def relu_prime(z): if z > 0: return 1 return 0 def cost(yHat, y): return 0.5 * (yHat - y)**2 def cost_prime(yHat, y): return yHat - y def backprop(x, y, Wh, Wo, lr): yHat = feed_forward(x, Wh, Wo) # Layer Error Eo = (yHat - y) * relu_prime(Zo) Eh = Eo * Wo * relu_prime(Zh) # Cost derivative for weights dWo = Eo * H dWh = Eh * x # Update weights Wh -= lr * dWh Wo -= lr * dWo

Прудников Иван Алексеевич
МИРЭА(МТУ)

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

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

Теоретическая часть

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

Архитектура

На рисунке 1 показана многослойная нейронная сеть с одним слоем скрытых нейронов (элементы Z).

Нейроны, представляющие собой выходы сети (обозначены Y), и скрытые нейроны могут иметь смещение(как показано на изображении). Смещение, соответствующий выходу Y k обозначен w ok , скрытому элементу Z j - V oj . Эти смещения служат в качестве весов на связях, исходящих от нейронов, на выходе которых всегда появляется 1 (на рисунке 1 они показаны, но обычно явно не отображаются, подразумеваясь). Кроме того, на рисунке 1 стрелками показано перемещение информации в ходе фазы распространения данных от входов к выходам. В процессе обучения сигналы распространяются в обратном направлении.

Описание алгоритма

Алгоритм, представленный далее, применим к нейронной сети с одним скрытым слоем, что является допустимой и адекватной ситуацией для большинства приложений. Как уже было сказано ранее, обучение сети включает в себя три стадии: подача на входы сети обучающих данных, обратное распространение ошибки и корректировка весов. В ходе первого этапа каждый входной нейрон X i получает сигнал и широковещательно транслирует его каждому из скрытых нейронов Z 1 ,Z 2 ...,Z p . Каждый скрытый нейрон затем вычисляет результат его активационной функции (сетевой функции) и рассылает свой сигнал Z j всем выходным нейронам. Каждый выходной нейрон Y k , в свою очередь, вычисляет результат своей активационной функции Y k , который представляет собой ничто иное, как выходной сигнал данного нейрона для соответствующих входных данных. В процессе обучения, каждый нейрон на выходе сети сравнивает вычисленное значение Y k с предоставленным учителем t k (целевым значением), определяя соответствующее значение ошибки для данного входного шаблона. На основании этой ошибки вычисляется σ k (k = 1,2,...m). σ k используется при распространении ошибки от Y k до всех элементов сети предыдущего слоя (скрытых нейронов, связанных с Y k), а также позже при изменении весов связей между выходными нейронами и скрытыми. Аналогичным образом вычисляется σj (j = 1,2,...p) для каждого скрытого нейрона Z j . Несмотря на то, что распространять ошибку до входного слоя необходимости нет, σj используется для изменения весов связей между нейронами скрытого слоя и входными нейронами. После того как все σ были определены, происходит одновременная корректировка весов всех связей.

Обозначения:

В алгоритме обучения сети используются следующие обозначения:

X Входной вектор обучающих данных X = (X 1 , X 2 ,...,X i ,...,X n).
t Вектор целевых выходных значений, предоставляемых учителем t = (t 1 , t 2 ,...,t k ,...,t m)
σ k Составляющая корректировки весов связей w jk , соответствующая ошибке выходного нейрона Y k ; также, информация об ошибке нейрона Y k , которая распространяется тем нейронам скрытого слоя, которые связаны с Y k .
σ j Составляющая корректировки весов связей v ij , соответствующая распространяемой от выходного слоя к скрытому нейрону Z j информации об ошибке.
a Скорость обучения.
X i Нейрон на входе с индексом i. Для входных нейронов входной и выходной сигналы одинаковы - X i .
v oj Смещение скрытого нейрона j.
Z j Скрытый нейрон j; Суммарное значение подаваемое на вход скрытого элемента Z j обозначается Z_in j: Z_in j = v oj +∑x i *v ij
Сигнал на выходе Z j (результат применения к Z_in j активационной функции) обозначается Z j: Z j = f (Z_in j)
w ok Смещение нейрона на выходе.
Y k Нейрон на выходе под индексом k; Суммарное значение подаваемое на вход выходного элемента Y k обозначается Y_in k: Y_in k = w ok + ∑ Z j *w jk . Сигнал на выходе Y k (результат применения к Y_in k активационной функции) обозначается Y k:

Функция активации

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

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

Алгоритм обучения

Алгоритм обучения выглядит следующим образом:

Инициализация весов (веса всех связей инициализируются случайными небольшими значениями).

До тех пор пока условие прекращения работы алгоритма неверно, выполняются шаги 2 - 9.

Для каждой пары { данные, целевое значение } выполняются шаги 3 - 8.

Распространение данных от входов к выходам:

Шаг 3.
Каждый входной нейрон (X i , i = 1,2,...,n) отправляет полученный сигнал X i всем нейронам в следующем слое (скрытом).

Каждый скрытый нейрон (Z j , j = 1,2,...,p) суммирует взвешенные входящие сигналы: z_in j = v oj + ∑ x i *v ij и применяет активационную функцию: z j = f (z_in j) После чего посылает результат всем элементам следующего слоя (выходного).

Каждый выходной нейрон (Y k , k = 1,2,...m) суммирует взвешенные входящие сигналы: Y_in k = w ok + ∑ Z j *w jk и применяет активационную функцию, вычисляя выходной сигнал: Y k = f (Y_in k).

Обратное распространение ошибки:

Каждый выходной нейрон (Y k , k = 1,2,...m) получает целевое значение - то выходное значение, которое является правильным для данного входного сигнала, и вычисляет ошибку: σ k = (t k - y k)*f " (y_in k), так же вычисляет величину, на которую изменится вес связи w jk: Δw jk = a * σ k * z j . Помимо этого, вычисляет величину корректировки смещения: Δw ok = a*σ k и посылает σ k нейронам в предыдущем слое.

Каждый скрытый нейрон (z j , j = 1,2,...p) суммирует входящие ошибки (от нейронов в последующем слое) σ_in j = ∑ σ k * w jk и вычисляет величину ошибки, умножая полученное значение на производную активационной функции: σ j = σ_in j * f " (z_in j), так же вычисляет величину, на которую изменится вес связи vij: Δv ij = a * σ j * x i . Помимо этого, вычисляет величину корректировки смещения: v oj = a * σ j

Шаг 8. Изменение весов.

Каждый выходной нейрон (y k , k = 1,2,...,m) изменяет веса своих связей с элементом смещения и скрытыми нейронами: w jk (new) = w jk (old) + Δw jk
Каждый скрытый нейрон (z j , j = 1,2,...p) изменяет веса своих связей с элементом смещения и выходными нейронами: v ij (new) = v ij (old) + Δv ij

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

Многослойная искусственная нейронная сеть (рис. 6) может содержать произвольное количество слоев (K ), каждый слой состоит из нескольких нейронов, число которых также может быть произвольно (Н k – количество нейронов в слое), количество входов n , количество выходов H=H k – числу нейронов в выходном (последнем) слое.

Рис. 6. Многослойная нейронная сеть прямого распространения

Слои между первым и последним называются промежуточными или скрытыми. Веса в такой сети имеют три индекса i -номер нейрона следующего слоя, для которого связь входная, j -номер входа или нейрона текущего слоя, для которого связь выходная, k -номер текущего слоя в нейронной сети (для входов, вектора X, k=0 ).

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

Алгоритм обучения методом обратного распространения ошибки:

1 шаг: инициализация матриц весов случайным образом (в циклах).

2 шаг: предъявление нейронной сети образа (на вход подаются значения из обучающей выборки – вектор Х ) и берется соответствующий выход (вектор D ).

3 шаг (прямой проход): вычисление в циклах выходов всех слоев и получение выходных значений нейронной сети (вектор Y ).

где – выход i -нейрона k -слоя, f – функция активации, – синаптическая связь между j -нейроном слоя k-1 и i-нейроном слоя k , – входное значение.

4 шаг (обратный проход): изменение весов в циклах по формулам:

– для последнего (выходного) слоя,

– для промежуточных слоев,

где t – номер текущей итерации цикла обучения (номер эпохи), – коэффициент обучения задается от 0 до 1, – выход i -го нейрона k -го слоя,

– синаптическая связь между j- нейроном слоя k- 1 и i -нейроном слоя k , d i – желаемое выходное значение на i -нейроне, y i – реальное значение на i -нейроне выходного слоя.

5 шаг: проверка условия продолжения обучения (вычисление значения ошибки и/или проверка заданного количества итераций). Если обучение не завершено, то 2 шаг, иначе заканчиваем обучение. Среднеквадратичная ошибка вычисляется следующим образом:

где Q – общее число примеров, H - количество нейронов в выходном слое, d i – желаемое выходное значение на i-нейроне, y i - реальное значение на i -нейроне выходного слоя.

Пример решения задачи

Задача . Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется сигмоидальная функция активации (k=0,9), а во втором – 1, линейная (l=0,7) функция. В качестве обучающей выборки использовать таблицу истинности для операции «штрих Шеффера»

Описание процесса решения. Для обучения нейронной сети методом обратного распространения ошибки необходимо:

1) Графически отобразить структуру нейронной сети. Определить размерность и количество матриц синаптических весов (для каждого слоя своя матрица).

2) Определить обучающую выборку, представив ее в табличном виде.

3) Выбрать входные данные, на которых будет рассматриваться итерация цикла обучения.

4) Следуя алгоритмы обучения методом обратного обучения ошибки просчитать одну итерацию цикла и представить новые синаптические веса в матричном виде.

Решение.

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

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


	0.3	0.8

2 шаг: вектор X={0,1}, D ={1}.

3 шаг (прямой проход): вычисление в циклах выходов всех слоев и получение выходных значений нейронной сети (вектор Y).

4 шаг (обратный проход): изменение весов:


	0.7
	0.5	0.2


	0.3	0.8

5 шаг:

Так как мы рассматриваем одну итерацию цикла обучения, в любом случае выходим из цикла.

Задачи

1. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона, а во втором – 1. Функция активации нейронов сети – пороговая (T=0,6) функция. В качестве обучающей выборки использовать таблицу истинности для операции «исключающее или» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

2. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона, а во втором – 1. Функция активации нейронов сети – сигмоидальная (k=1) функция. В качестве обучающей выборки использовать таблицу истинности для операции импликации (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

3. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона, а во втором – 1. Функция активации нейронов сети – линейная (k=0,6) функция. В качестве обучающей выборки использовать таблицу истинности для операции «штрих Шеффера» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

4. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона, а во втором – 1. Функция активации нейронов сети – гиперболический тангенс (k=1). В качестве обучающей выборки использовать таблицу истинности для операции «стрелка Пирса» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

5. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется сигмоидальная функция активации (k=0,9), а во втором – 1, пороговая (T=0,7). В качестве обучающей выборки использовать таблицу истинности для операции «исключающее или» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

6. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется линейная функция активации (k=0,5), а во втором – 1, сигмоидальная (k=0,7) функция. В качестве обучающей выборки использовать таблицу истинности для операции импликации (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

7. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется пороговая функция активации (T=0,4), а во втором – 1, линейная (k=0,6) функция. В качестве обучающей выборки использовать таблицу истинности для операции «штрих Шеффера» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

8. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется пороговая функция активации (T=0,6), а во втором –1, гиперболический тангенс (k =2). В качестве обучающей выборки использовать таблицу истинности для операции «стрелка Пирса» (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

9. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 3 нейрона, а во втором – 2. Функция активации нейронов сети – линейная (k=0,6) функция.

10. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 3 нейрона, а во втором – 2. Функция активации нейронов сети – сигмоидальная (k=1) функция.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

11. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 3 нейрона, а во втором – 2. Функция активации нейронов сети – пороговая (T=0,65) функция.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

12. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 3 нейрона, а во втором – 2. Функция активации нейронов сети – гиперболический тангенс (k=3) функция.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

13. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется сигмоидальная функция активации (k=0,9), во втором – 2, пороговая (T=0,7).

Синаптические веса и обучающую выборку задать случайным образом (не нули).

14. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется линейная функция активации (k=0,5), во втором – 2, сигмоидальная (k=0,7) функция.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

15. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется пороговая функция активации (T=0,4), во втором – 2, линейная (k=0,6) функция.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

16. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 2 слоёв, причем в первом слое находится 2 нейрона и используется пороговая функция активации (T=0,6), во втором – 1, гиперболический тангенс (k=2).

Синаптические веса и обучающую выборку задать случайным образом (не нули).

17. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 3 слоёв, использующей пороговую функцию активации (T=0,5), в первом слое 2 нейрона, во втором – 2, в третьем - 1.

Синаптические веса и обучающую выборку задать случайным образом (не нули).

18. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, использующей пороговую функцию активации (T=0,5), в первом слое 3 нейрона, во втором – 1. В качестве обучающей выборки использовать таблицу истинности для (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

19. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной бинарной однородной нейронной сети, состоящей из 2 слоёв, использующей сигмоидальную функцию активации (k=0,5), в первом слое 3 нейрона, во втором –1. В качестве обучающей выборки использовать таблицу истинности для (не использовать первую строчку таблицы).

Синаптические веса задать случайным образом.

20. Просчитать одну итерацию цикла обучения методом обратного распространения ошибки многослойной аналоговой неоднородной нейронной сети, состоящей из 3 слоёв, причем в первом слое находится 2 нейрона и используется пороговая функция активации (T=0,6), во втором –2, гиперболический тангенс (k=2), в третьем 1, линейная (k=0,7).

Синаптические веса и обучающую выборку задать случайным образом (не нули).

Лабораторная работа № 6
Генетический алгоритм

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

Для моделирования эволюционных процессов в генетическом алгоритме используются операторы (таблица 10) и стратегии отбора (таблица 11).

Таблица 10.

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

Оператор	Описание	Пример
Операторы скрещивания
Одноточечный кроссовер	выбирается одна точка разрыва и родительские хромосомы обмениваются одной из получившихся частей	Родитель 1:1001011\|01001 Родитель 2:0100011\|00111 Потомок 1:1001011\|00111 Потомок 2:0100011 \|01001
Двухточечный кроссовер	выбираются две точки разрыва и родительские хромосомы обмениваются сегментом, который находится между двумя этими точками	Родитель 1:100\|101101\|001 Родитель 2:010\|001100\|111 Потомок 1:100 \|001100\|001 Потомок 2:010\|101101\|111
Равномерный кроссовер	каждый бит первого потомка случайным образом наследуется от одного из родителей, второму потомку достается бит другого родителя	Родитель 1:100101101001 Родитель 2:010001100111 Вероятность: 90 % Случайные числа (100): 2, 24, 8, 93, 55, 13, 67, 43, 99, 61, 5, 89 Потомок 1:100\|0011000\|01 Потомок 2:0101 01101 111
Операторы мутации
Одноточечная мутация	произвольный бит хромосомы с определенной вероятностью изменяется на противоположный	до:1001011 00111 после:1001010 00111
Транслокация	перенос какого-либо участка хромосомы в другой сегмент этой же хромосомы	до:10011110 0111 после:11100011 0111
Инверсия	перестановка генов в обратном порядке внутри произвольно выбранного участка хромосомы	до:100111100 111 после:100100111 111

Таблица 11.

Виды отбора особей в генетических алгоритмах.

Вид отбора	Описание
Пропорциональный	каждой особи назначает вероятность , равную отношению ее приспособленности к суммарной приспособленности популяции, осуществляется отбор (с замещением) всех n (устанавливается заранее) особей для дальнейшей генетической обработки, согласно величине
Рулетка	вид пропорционального отбора, когда особи отбираются с помощью n «запусков» рулетки (колесо рулетки содержит по одному сектору для каждого члена популяции, размер i -ого сектора пропорционален соответствующей величине )
Турнирный	из популяции, содержащей m особей, выбирается случайным образом t особей и выбирается наиболее приспособленная (между выбранными особями проводится турнир), эта операция повторяется m раз
Отбор усечением	из отсортированной в порядке убывания степени приспособленности популяции с учетом порога приспособленности (ниже порога особи в отборе не участвуют) случайным образом m/2 раз выбираются родительские пары
Ранговый	для каждой особи ее вероятность попасть в промежуточную популяцию пропорциональна ее порядковому номеру в отсортированной по возрастанию приспособленности популяции
Элитный	добавляет к любому другому виду отбора принцип элитизма – сохранения в новой популяции одной или нескольких наиболее приспособленных особей

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

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

1 шаг . Формирование начальной популяции.

2 шаг . Оценка особей популяции (используется фитнесс-функция).

3 шаг . Отбор (используется один из методов отбора).

4 шаг . Скрещивание (используется оператор кроссовера).

5 шаг . Мутация (используется один или несколько операторов мутации).

6 шаг . Формирование новой популяции.

7 шаг . Если популяция не сошлась, то 2, иначе – останов (прекращение функционирования генетического алгоритма).

Пример решения задачи

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

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

Описание процесса решения .

Для использования генетического алгоритма необходимо:

1) Определить набор признаков, характеризующие решения задачи оптимизации или моделирования. Определить фенотип, закодировать признаки (можно использовать код Грея).

2) Использовать последовательность шагов генетического алгоритма с соответствующими операторами.

Решение.

1) Фенотип (задаем десятичные значения случайным образом):

Признак	Двоичное значение признака	Десятичное значение признака	Код Грея
Признак 1
Признак 2
Признак 3
Признак 4
Признак 5

2) 1 шаг. Формирование начальной популяции.

Определено пять признаков, пусть особь содержит любые 2 из них (два первых – значения первого критерия, три последних второго), случайным образом сгенерируем 10 особей, каждая особь длиной 8 бит:

Особь 1: 00111110 Особь 6: 00111110

Особь 2: 11001110 Особь 7: 11000111

Особь 3: 00111001 Особь 8: 00110111

Особь 4: 11001001 Особь 9: 10101010

Особь 5: 00110111 Особь 10: 01010101

2 шаг. Оценка особей популяции (используется фитнесс-функция равная сумме бит в особи).

Среднее значение суммы бит в популяции = 3,6.

3 шаг. Отбор (используется метод отбора – рулетка с принципом элитизма).

Строим рулетку (сектора пропорциональны приспособленности, рис.

7) и запускаем ее 8 раз (выбираем 4 пары, рис. 9):

Рис. 7. Рулетка для задачи генетического алгоритма

Запуски рулетки (случайным образом):

Рис. 8. Запуски рулетка для задачи генетического алгоритма

Таким образом, образовались следующие пары: 1 и 5, 7 и 5, 10 и 2, 8 и 6.

4 шаг. Скрещивание (используется оператор – двухточечный кроссовер).

Выбираем две точки разрыва (случайным образом, но числа должны различаться хотя бы на 2 и не быть равными 1 или длине особи): 2 и 5 и применяем оператор к выбранным парам особей:

Особь 1: 00|111|110 Особь 2.1: 00|110|110

Особь 5: 00|110|111 Особь 2.2: 00|111|111

Особь 7: 11|000|111 Особь 2.3: 11|110|111

Особь 5: 00|110|111 Особь 2.4: 00|000|111

Особь 10: 01|010|101 Особь 2.5: 01|001|101

Особь 2: 11|001|110 Особь 2.6: 11|010|110

Особь 6: 00|111|110 Особь 2.7: 00|110|110

Особь 8: 00|110|111 Особь 2.8: 00|111|111

5 шаг. Мутация (используется оператор – одноточечная мутация).

Определим вероятность мутации 30 % и бит – третий, подвергающийся мутации.

1-8 – наследники, 9-11 – матировавшие особи, 12 - сохраняем одну особь с максимальной приспособленностью – принцип элитизма.

7 шаг. Популяция достаточно разнообразна – нет признаков сходимости. Так как рассматривается лишь одна эпоха генетического алгоритма – выход из алгоритма.

Задачи

1. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, деленная на максимум суммы всех бит среди особей популяции; метод отбора – рулетка; оператор скрещивания – одноточечный кроссовер; оператор мутации – одиночная мутация.

2. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, деленная на минимум суммы всех бит среди особей популяции; метод отбора – турнирный отбор; оператор скрещивания – двухточечный кроссовер; оператор мутации – транслокация.

3. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – единица, деленная на минимум суммы всех бит среди особей популяции; метод отбора – ранговый отбор; оператор скрещивания – равномерный кроссовер; оператор мутации – инверсия.

4. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, умноженная на минимум суммы всех бит среди особей популяции; метод отбора – отбор усечением; оператор скрещивания – равномерный кроссовер; оператор мутации – одноточечная мутация.

5. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – единица, деленная на максимум суммы всех бит в особи в популяции; метод отбора – пропорциональный отбор; оператор скрещивания – одноточечный кроссовер; оператор мутации – инверсия.

6. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, деленная на количество бит в особи; метод отбора – рулетка с использованием принципа элитизма; оператор скрещивания – равномерный кроссовер; оператор мутации – инверсия.

7. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество бит в особи; метод отбора – пропорциональный с использованием принципа элитизма; оператор скрещивания – одноточечный кроссовер; оператор мутации – одноточечная мутация.

8. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – ранговый с использованием принципа элитизма; оператор скрещивания – одноточечный кроссовер; оператор мутации – одноточечная мутация.

9. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – турнирный с использованием принципа элитизма; оператор скрещивания – равномерный кроссовер; оператор мутации – транслокация.

10. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – отбор усечением с использованием принципа элитизма; оператор скрещивания – двухточечный кроссовер; оператор мутации – транслокация.

11. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, деленная на максимум суммы всех бит особи в популяции; метод отбора – рулетка; оператор скрещивания – двухточечный кроссовер; оператор мутации – одиночная мутация.

12. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на максимум суммы всех бит особи в популяции; метод отбора – турнирный отбор; оператор скрещивания – равномерный кроссовер; оператор мутации – инверсия.

13. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – единица, деленная на минимум суммы всех бит особи в популяции; метод отбора – ранговый отбор; оператор скрещивания – одноточечный кроссовер; оператор мутации – инверсия.

14. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит, умноженная на минимум суммы всех бит особи в популяции; метод отбора – отбор усечением; оператор скрещивания – равномерный кроссовер; оператор мутации – транслокация.

15. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – единица, деленная на максимум суммы всех бит среди особей популяции; метод отбора – пропорциональный отбор; оператор скрещивания – одноточечный кроссовер; оператор мутации – транслокация.

16. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество бит в особи; метод отбора – рулетка с использованием принципа элитизма; оператор скрещивания – одноточечный кроссовер; оператор мутации – транслокация.

17. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество бит в особи; метод отбора – пропорциональный с использованием принципа элитизма; оператор скрещивания – двухточечный кроссовер; оператор мутации – инверсия.

18. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – ранговый с использованием принципа элитизма; оператор скрещивания – равномерный кроссовер; оператор мутации – транслокация.

19. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – турнирный с использованием принципа элитизма; оператор скрещивания – равномерный кроссовер; оператор мутации – одноточечная мутация.

20. Описать функционирование одной эпохи генетического алгоритма на примере произвольной задачи (не менее пяти признаков закодировать случайным образом, начальная популяция содержит не менее 10 особей). Использовать следующие параметры генетического алгоритма: фитнесс-функция – сумма всех бит особи, деленная на количество особей в популяции; метод отбора – отбор усечением с использованием принципа элитизма; оператор скрещивания – двухточечный кроссовер; оператор мутации – одноточечная мутация.

Лабораторная работа №7.
Разработка специальных моделей представления знаний
для БЗ и БД и правил для машины вывода

Порядок работ и их виды

Введение с указанием предметной области.

В разделе “I. Идентификация ” постановка (формулировка) проблемы, цели и задачи.

В разделе “II.. Концептуализация ” нужно представить следующие результаты разработки Содержательной и Концептуальной моделей.