Приведем  словесное описание алгоритма.

     Шаг 1. Весам сети присваиваются небольшие  начальные значения.

     Шаг 2. Выбирается очередная обучающая пара (X, Y) из обучающего множества; вектор X подается на вход сети.

     Шаг 3. Вычисляется выход сети.

     

     где W - вектор весов выходного нейрона, o^k - вектор выходов нейронов скрытого слоя с элементами

     

     w_i обозначает вектор весов, связанных с i-м скрытым нейроном, i = 1, 2, ..., L.

     Шаг 4. Вычисляется разность между требуемым (целевым, Y) и реальным (вычисленным) выходом сети.

     Шаг 5. Веса сети корректируются так, чтобы  минимизировать ошибку.

     

     

     Шаг 6. Шаги со 2-го по 5-й повторяются для  каждой пары обучающего множества до тех пор, пока ошибка на всем множестве  не достигнет приемлемой величины.

     Шаги 2 и 3 подобны тем, которые выполняются в уже обученной сети.

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

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

     

     Рисунок 6 –Двухслойная сеть

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

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

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

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

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

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

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

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

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

 

      
 
 

     3 ГЕНЕТИЧЕСКИЙ АЛГОРИТМ

 

     Генетический алгоритм (англ. genetic algorithm) — это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем последовательного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений (англ. evolutionary computation). Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. «Отцом-основателем» генетических алгоритмов считается Джон Холланд (англ. John Holland), книга которого «Адаптация в естественных и искусственных системах» (англ. Adaptation in Natural and Artificial Systems) является основополагающим трудом в этой области исследований.

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

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

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

     2) Для поиска генетический алгоритм использует несколько точек поискового пространства одновременно, а не переходит от точки к точке, как это делается в традиционных методах. Это позволяет преодолеть один из их недостатков - опасность попадания в локальный экстремум целевой функции, если она не является унимодальной, то есть имеет несколько таких экстремумов. Использование нескольких точек одновременно значительно снижает такую возможность.

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

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

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

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

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

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

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

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

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

     - генотип и фенотип;

     - особь и качество особи;

     - популяция и размер популяции;

     - поколение;

     - родители и потомки.

     К характеристикам генетического  алгоритма относятся:

     - размер популяции;

     - оператор скрещивания и вероятность его использования;

     - оператор мутации и вероятность мутации;

     - оператор отбора;

     - оператор редукции;

     - критерий останова.

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