ЛИСТ ЗАМЕЧАНИЙ

СОДЕРЖАНИЕ 

ВВЕДЕНИЕ 5

1 МОДЕЛИРОВАНИЕ РАБОТЫ НЕЙРОННОЙ СЕТИ 6

2 АЛГОРИТМ ОБРАТНОГО РАСПРОСТРОНЕНИЯ ОШИБКИ 10

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

4 ЭФФЕКТИВНОСТЬ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ 22

4.1 Показатели эффективности генетических алгоритмов 22

4.2 Скорость работы генетических алгоритмов 22

4.3 Устойчивость работы генетических алгоритмов 24

4.4 Направления развития генетических алгоритмов 27

ЗАКЛЮЧЕНИЕ 30

СПИСОК ЛИТЕРАТУРЫ 31

ПРИЛОЖЕНИЕ 32

     ВВЕДЕНИЕ

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

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

     1 МОДЕЛИРОВАНИЕ РАБОТЫ НЕЙРОННОЙ СЕТИ

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

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

     Моделирование сети начинается с выбора архитектуры. На данном этапе необходимо учесть:

     - какие нейроны мы хотим использовать (число входов, передаточные функции);

     - каким образом следует соединить их между собой;

     - что взять в качестве входов и выходов сети.

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

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

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

     - выходные нейроны - это нейроны, выходные значения которых представляют выход сети;

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

     Обучить нейросеть - значит, сообщить ей, чего мы от нее добиваемся. Этот процесс очень похож на обучение ребенка алфавиту. Показав ребенку изображение буквы «А», мы спрашиваем его: «Какая это буква?» Если ответ неверен, мы сообщаем ребенку тот ответ, который мы хотели бы от него получить: «Это буква А». Ребенок запоминает этот пример вместе с верным ответом, т.е. в его памяти происходят некоторые изменения в нужном направлении. Мы будем повторять процесс предъявления букв снова и снова до тех пор, когда все буквы будут твердо запомнены. Такой процесс называют «обучение с учителем».

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

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

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

     Математически процесс обучения можно описать  следующим образом. В процессе функционирования нейронная сеть формирует выходной сигнал Y в соответствии с входным сигналом X, реализуя некоторую функцию Y = G(X). Если архитектура сети задана, то вид функции G определяется значениями синоптических весов и смещений сети. Пусть решением некоторой задачи является функция Y = = F(X), заданная парами входных - выходных данных (X ₁, Y ₁ ), (X ₂, Y ₂ ), ..., (X_w, Y_w), для которых Y _k = F(X _k ) (к = 1, 2, …,N). 

     Рисунок 5- Схема обучения сети

     2 АЛГОРИТМ ОБРАТНОГО РАСПРОСТРОНЕНИЯ ОШИБКИ

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

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

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

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

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

     Шаг 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). При порождении новой популяции оператор скрещивания может применяться не ко всем парам родителей. Часть этих пар может переходить в популяцию следующего поколения непосредственно. Насколько часто будет возникать такая ситуация, зависит от значения вероятности применения оператора скрещивания, которая является одним из параметров генетического алгоритма.

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

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

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

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

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

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

     - поколение;

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

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

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

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

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

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

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

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

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