Программа дисциплины «Базы данных и экспертные системы» учебно-методические материалы Редакция №1 от 01. 09. 2013 учебно-методический комплекс дисциплины «Базы данных и экспертные системы»

^ Лекция 8. Основные понятия теории искусственных нейронных сетей. В лекции представлен альтернативный подход к разработке ИИС, основанный на концепции обучения искусственных нейронных сетей. Рассмотрены основные типы и архитектура нейронных сетей, методы адаптации, обучения и настройки параметров. Модель искусственного нейрона. Искусственная нейронная сеть (ИНС) - это упрощенная модель биологичес-кого мозга, точнее нервной ткани. Нервная система человека, построенная из элементов, называемых нейронами, имеет поразительную сложность. Около 1011 нейронов участвуют в примерно 1015 передающих связях, имеющих длину метр и более. Каждый нейрон обладает многими качествами, общими с другими элемента-ми тела, но его уникальной способностью является прием, обработка и передача электрохимических сигналов по нервным путям, которые образуют коммуникацион-ную систему мозга. Структура пары типичных биологических нейронов показана на рис. 39. Нейрон состоит из тела (сомы), содержащего ядро, и отростков - дендритов, по которым в нейрон поступают входные сигналы. Один из отростков, ветвящийся на конце, служит для передачи выходных сигналов данного нейрона другим нервным клеткам. Он называется аксоном. Соединение аксона с дендритом другого нейрона называется синапсом. Нейрон возбуждается и передает сигнал через аксон, если число пришедших по дендритам возбуждающих сигналов больше, чем число тормозящих. Несмотря на то, что у этой функциональной схемы нейрона много усложнений и исключений, большинство искусственных нейронных сетей моделируют лишь эти простые свойства. Рис. 39. Биологический нейрон. Искусственный нейрон (рис. 40), далее просто нейрон, задается совокупностью своих входов, обозначенных , весами входов , функцией состояния NET и функцией активации F. Функция состояния определяет состояние нейрона в зависимости от значений его входов, весов входов и, возможно, предыдущих состояний. Наиболее часто используются функции состояния, вычисляемые как сумма произведений значений входов на веса соответствующих входов по всем входам . Суммирующий блок, соответствующий телу биологического нейрона, складывает взвешенные входы алгебраически, создавая выход, который будем называть NET. Сигнал NET преобразуется функцией активации F и дает выходной сигнал нейрона . Рис. 41. Искусственный нейрон с активационной функцией F. На рис. 41 блок, обозначенный F, принимает сигнал NET и выдает сигнал OUT. Если блок F сужает диапазон изменения величины NET так, что при любых значениях NET значения OUT принадлежат некоторому конечному интервалу, то F называется «сжимающей» функцией. В качестве «сжимающей» функции часто используется сигмоидальная (S-образная) функция, показанная на рис. 42. Рис. 42. Сигмоидальная функция. Эта функция имеет вид: . По аналогии с электронными системами активационную функцию можно считать нелинейной усилительной характеристикой искусственного нейрона. Коэффициент усиления вычисляется как отношение приращения величины OUT к вызвавшему его небольшому приращению величины NET. Центральная область сигмоидальной функции, имеющая большой коэффициент усиления, решает проблему обработки слабых сигналов, в то время как области с падающим усилением на положительном и отрицательном концах подходят для больших возбуждений. Таким образом, нейрон функционирует с большим усилением в широком диапазоне уровня входного сигнала. Другой широко используемой функцией активации является гиперболический тангенс OUT = th(x). Подобно сигмоидальной функции гиперболический тангенс является S-образной функцией, но он симметричен относительно начала координат, и в точке NET = 0 значение выходного сигнала OUT равно нулю (рис. 43). В отличие от сигмоидаль-ной функции гиперболический тангенс принимает значения различных знаков, что оказывается выгодным при поиске экстремума в пространстве параметров ИНС. Рис. 43. Функция гиперболического тангенса. Простейшими формами функции активации являются линейная и ступенчатая (пороговая) функции. Линейная функция активации дифференцируема и легко вычисляется, что в ряде случаев позволяет уменьшить ошибки выходных сигналов в ИНС. Однако она не универсальна и не обеспечивает решение многих плохо формализованных задач. Ступенчатая функция обычно задается в виде единичной функции с жесткими ограничениями: она равна нулю, если NET < 0, и единице, если NET 0. Такая функция не обеспечивает достаточной гибкости ИНС при обучении. Рассмотренная простая модель искусственного нейрона игнорирует многие свойства своего биологического двойника. Например, она не принимает во внимание задержки во времени, которые воздействуют на динамику системы. Несмотря на эти ограничения, сети, построенные из этих нейронов, обнаруживают свойства, сильно напоминающие биологическую систему. Модели нейронных сетей. Нейронная сеть представляет собой совокупность искусственных нейронов, организованных слоями. Реальная нейронная сеть может содержать один или большее количество слоев и соответственно характеризоваться как однослойная или как многослойная, с обратными связями и без них. Многослойные сети отличаются от однослойных тем, что между входными и выходными данными располагаются несколько так называемых скрытых слоев нейронов, добавляющих больше нелинейных связей в модель. Простейшая сеть состоит из группы нейронов, образующих один слой (рис. 44). На рисунке вершины - круги слева служат лишь для распределения входных сигналов. Они не выполняют каких - либо вычислений, и поэтому не будут считаться слоем. По этой причине они обозначены кругами, чтобы отличать их от вычисляющих нейронов, обозначенных квадратами. Каждый элемент из множества входов Х отдельным весом соединен с каждым искусственным нейроном, и каждый нейрон выдает взвешенную сумму входов в сеть. В искусственных и биологических сетях многие соединения могут отсутствовать, поэтому на рисунке все соединения показаны в целях общности. Многослойные сети обладают большими вычислительными возможностями, чем однослойные. Послойная организация нейронов копирует слоистые структуры определенных отделов мозга. Многослойные сети могут образовываться каскадами слоев: выход одного слоя является входом для последующего слоя. Двухслойная сеть со всеми соединениями показана на рис. 45. Если функция активации является линейной, то нейронная сеть также будет линейной. Двухслойная линейная сеть эквивалентна одному слою с весовой матрицей, равной произведению двух весовых матриц, то есть . Следовательно, любая многослойная линейная сеть может быть заменена эквивалентной однослойной сетью. Для расширения вычислительных возможностей ИНС применяется нелинейная функция активации. Рис. 44. Однослойная нейронная сеть Рис. 45. Двухслойная нейронная сеть. По архитектуре связей нейронные сети могут быть сгруппированы в два класса: сети прямого распространения, в которых обратные связи отсутствуют (нет соединений, идущих от выходов некоторого слоя к входам этого же слоя или предшествующих слоев) и сети рекуррентного типа, в которых возможны обратные связи. В сетях прямого распространения нет памяти, их выход полностью определяется текущими входами и значениями весов. Сети прямого распространения подразделяются на однослойные перцепротроны (сети) и многослойные перцептроны (сети). Название перцептрон для нейросетей введено Ф. Розенблаттом, разработчиком первой нейросети (1957 г.). Он же доказал схо-димость области решений для перцептрона при его обучении. Реккурентные сети могут обладать свойствами, сходными с кратковременной человеческой памятью. Класс рекуррентных нейронных сетей гораздо обширнее и сложнее по своему устройству. Поведение рекуррентных сетей описывается дифференциальными или разностными уравнениями, как правило, первого порядка. Это гораздо расширяет области применения нейросетей и способы их обучения. Сеть организована так, что каждый нейрон получает входную информацию от других нейронов, возможно, и от самого себя, и от окружающей среды. Этот тип сетей имеет важное значение для моделирования нелинейных динамических систем. Среди рекуррентных сетей можно выделить сети Хопфилда и сети Кохонена. При всем многообразии возможных конфигураций ИНС на практике получили распространение лишь некоторые из них. Классическим моделями нейронных сетей являются: Многослойные перцептроны содержат помимо входного и выходного слоев так называемые скрытые слои. Они представляют собой нейроны, которые не имеют непосредственных входов исходных данных, а связаны только с выходами входного слоя и с входом выходного слоя. Таким образом, скрытые слои дополнительно преобразуют информацию и добавляют нелинейности в модели. Многослойный перцептрон с сигмоидальными функциями активации способен аппроксимировать любую функциональную зависимость (доказано в виде теоремы), однако при этом не известно ни нужное число слоев, ни нужное количество скрытых нейронов, ни необходимое для обучения сети время. Эти проблемы до сих пор не решены; Сети Хопфилда строятся из N нейронов, связанных каждый с каждым кроме самого себя, причем все нейроны являются выходными. Нейронную сеть можно использовать в качестве ассоциативной памяти, а также для обработки неупорядоченные, упорядоченных во времени или пространстве образцов (рукописные буквы, временные ряды, графики); Сети Кохонена еще называют «самоорганизующимися картами признаков». Сеть рассчитана на самостоятельное обучение. В процессе обучения на вход сети подаются различные образцы. Сеть улавливает особенности их структуры и разделяет образцы на кластеры, а затем уже обученная сеть относит каждый вновь поступающий пример к одному из кластеров, руководствуясь некоторым критерием «близости». Сеть состоит из одного входного и одного выходного слоя. Количество элементов в выходном слое непосредственно определяет, сколько различных кластеров сеть сможет распознать. Каждый из выходных элементов получает на вход весь входной вектор. Как и во всякой нейронной сети, каждой связи приписан некоторый синаптический вес. В большинстве случаев каждый выходной элемент соединен также со своими соседями. Эти внутрислойные связи играют важную роль в процессе обучения, так как корректировка весов происходит только в окрестности того элемента, который наилучшим образом откликается на очередной вход. Выходные элементы соревнуются между собой за право вступить в действие «получить урок». Выигрывает тот из них, чей вектор весов окажется ближе всех к входному вектору. Структура ИНС, включая определение числа слоев и числа нейронов в каждом слое, формируется до начала обучения, поэтому успешное решение этой проблемы во многом зависит от опыта и искусства аналитика, проводящего исследование. Обучение нейронных сетей. Главное отличие и преимущество нейросетей перед классическими средствами прогнозирования и классификации заключается в их способности к обучению. На этапе обучения происходит вычисление синаптических коэф-фициентов в процессе решения нейронной сетью задач, в которых нужный ответ определяется не по правилам, а с помощью примеров, сгруппированных в обучающие множества. Нейросеть на этапе обучения сама выполняет роль эксперта в процессе подготовки данных для построения экспертной системы. Предпола-гается, что правила находятся в структуре обучающих данных. Такие данные представляют собой ряды примеров с указанием для каждого из них значения выходного параметра, которое было бы желательно получить. Действия, которые при этом происходят, можно назвать обучение с учителем. На вход сети подается вектор исходных данных, а на выходной узел сообщается желаемое значение результата вычислений. Контролируемое обучение нейросети можно рассматривать как решение оптимизационной задачи. Ее целью является минимизация функции ошибок на данном множестве примеров путем выбора значений весов W. Достижение минимума называется сходимостью процесса обучения. Поскольку ошибка зависит от весов нелинейно, получить решение в аналитической форме невозможно, и поиск глобального минимума осуществляется посредством итерационного процесса, так называемого обучающего алгоритма. В настоящее время используются более сотни разных обучающих алгоритмов, отличающихся друг от друга стратегией оптимизации и критерием ошибок. Обычно в качестве меры погрешности берется средняя квадратичная ошибка , где M – число примеров в обучаемом множестве. Среди обучающих алгоритмов наиболее распространенным является алгоритм обратного распространения ошибок. Согласно методу перед началом обучения сети всем межнейронным связям присваиваются небольшие случайные значения весов. Каждый шаг обучающей процедуры состоит из двух фаз. Во время первой фазы входные элементы сети устанавливаются в заданное состояние. Входные сигналы распространяются по сети, порождая некоторый выходной вектор. При этом используются сигмоидальные функции активации. Полученный выходной вектор сравнивается с требуемым (правильным) вектором. Если они совпадают, то весовые коэффициенты связей не изменяются. В противном случае вычисляется разница между фактическими и требуемыми выходными значениями, которая передается последовательно от выходного слоя к входному слою. На основе этой информации проводится модификация весов связей в соответствии с формулой: где - изменение веса связи на шаге итерации t обучающей пары вход-выход i -го нейрона, получающего входной сигнал, и j –го нейрона, посылающего выход-ной сигнал;  - коэффициент, задаваемый пользователем в интервале (0,1);  - величина шага сети или мера точности обучения сети. В современных нейросетевых пакетах пользователь может сам определять, как будет изменяться величина шага сети, очень часто по умолчанию берется линейная или экспонен-циальная зависимость величины шага от количества итераций сети. Чем меньше шаг сети, тем больше времени потребуется на обучение сети и тем возможнее станет ее попадание в окрестность локального минимума ошибки. Общая ошибка функционирования сети определяется по формуле: где и - соответственно желательное и действительное значение выходного сигнала j – го блока для p – й обучающей пары нейронов вход-выход. Когда величина ошибки достигает приемлемо малого уровня, обучение останавливают, и сеть готова к выполнению возложенных на нее задач. Важно отметить, что вся информация, которую сеть приобретает о задаче, содержится в наборе примеров. Поэтому качество обучения сети зависит от количества примеров в обучающей выборке, а также от того, насколько полно эти примеры описывают задачу. Считается, что для полноценной тренировки требуется хотя бы несколько десятков (а лучше сотен) примеров. Если не для всех примеров обучающей выборки известны правильные ответы, то обучение сети проводится без учителя. В этом случае применение самонастраивающихся сетей Кохонена дает возможность определить внутреннюю структуру поступающих в сеть данных и распределить образцы по категориям. Несмотря на многочисленные успешные применения алгоритма обратного распространения при обучении ИНС, у него есть недостатки. Больше всего неприятностей приносит неопределенно долгий процесс обучения. В сложных задачах для обучения сети могут потребоваться дни или даже недели, она может и вообще не обучиться. Длительное время обучения может быть результатом неоптимального выбора шага сети . Неудачи в обучении сети обычно возникают по двум причинам. Паралич сети. В процессе обучения сети значения весов могут в результате коррекции стать очень большими величинами. Это может привести к тому, что все или большинство нейронов будут функционировать при очень больших значениях OUT, в области, где производная сжимающей функции очень мала. Так как посылаемая обратно в процессе обучения ошибка пропорциональна этой производной, то процесс обучения может практически замереть. В теоретическом отношении эта проблема плохо изучена. Обычно этого избегают уменьшением размера шага, но это увеличивает время обучения. Для предохранения от паралича применяются различные эвристики, но пока что они могут рассматриваться лишь как экспериментальные. Попадание в локальный минимум. Обратное распространение использует разновидность градиентного спуска, то есть осуществляет спуск вниз по поверхности ошибки, непрерывно подстраивая веса в направлении минимума. Поверхность ошибки сложной сети сильно изрезана и состоит из холмов, долин, складок и оврагов в пространстве высокой размерности. Сеть может попасть в локальный минимум (неглубокую долину), когда рядом имеется гораздо более глубокий минимум. В точке локального минимума все направления ведут вверх, и сеть не может из него выбраться. Способы реализации ИНС. Нейронные сети могут быть реализованы программным или аппаратным спосо-бами. Вариантом аппаратной реализации являются нейрокомпьютеры. Большинство современных нейрокомпьютеров представляют собой персональный компьютер, снабженный дополнительной нейроплатой. Повышенный интерес вызывают спе-циализированные нейрокомпьютеры, в которых реализованы принципы архитек-туры нейронных сетей. В тех случаях, когда разработка или внедрение аппаратных реализаций нейронных сетей обходится слишком дорого, применяют более дешевые программные реализации. Программу моделирования нейронной сети обычно называют программой-имитатором или нейропакетом, понимая под этим программную оболочку, эмулирующую для пользователя среду нейрокомпьютера на обычном компьютере. В настоящее время на рынке программного обеспечения имеется множество самых разнообразных программ для моделирования нейронных сетей. В них воплощены практически все известные алгоритмы обучения и топологии нейросетей. Общее число фирм, разрабатывающих эти средства, превышает 150. Несмотря на сложность заложенных в нейропакетах методов, использовать их довольно просто. Они позволяют сконструировать, обучить, протестировать и использовать в работе нейронную сеть на основе понимания нескольких базовых теоретических положений, изложенных выше. Первые подобные программные продукты появились на Западе в середине 80 -х годов XX века. Одним из лидеров этого рынка стал нейросетевой пакет BrainMaker американской фирмы California Scientific Software. В настоящее время нейрокомпь-ютерный сегмент рынка программного обеспечения бурно развивается, и появление новых пакетов – естественный процесс. Современные продукты во многом лучше своих предшественников – улучшен интерфейс пользователя, появились дополни-тельные нейропарадигмы, в пакетах реализованы возможности взаимодействия с другими приложениями посредством механизмов OLE, ActiveX и др. Плата за эти возможности использовать более мощный, чем ранее компьютер, рост требований к объему оперативной и дисковой памяти. Кроме того, новый пакет не гарантирует более качественного решения прикладной задачи пользователя. В большей степени это качество зависит от правильно поставленной задачи, выбора данных. Эффективным реальным инструментом для расчета и проектирования нейронных сетей при решении многочисленных прикладных задач во многих областях техники, в том числе электротехники и электроники, электрооборудования является пакет прикладных программ Neural Network Toolbox (ППП NNT), функциони-рующий под управлением системы Matlab версии 5.3 и 6.0. Следует также обратить внимание на интерфейс ППП NNT с системой Simulink, что позволяет наглядно отобразить архитектуру сети и выполнить моделирование как статических, так и динамических нейронных сетей. Последнее обстоятельство особенно важно при построении систем управления различными электротехническими объектами, диагностики их состояния и поведения. Лекция 9. Генетические алгоритмы. В лекции рассмотрены методы поиска оптимальных решений многокрите-риальных прикладных задач управления системами в реальном времени с исполь-зованием эволюционных аналогий. Представлены основы теории генетических алгоритмов, построенных на принципах, сходных с принципами естественного отбора и генетики. Приведены примеры решения задач, в которых показаны эффективность генетических алгоритмов. Эволюционные вычисления и традиционные методы оптимизации. Задача управления любым техническим комплексом или системой, включая электротехнические комплексы, является много­критериальной, то есть такой, в которой приходится учитывать большое число факторов. Здесь аналитику приходится оценивать множество сил, влия­ний интересов и последствий, характеризующих то или иное решение. Зачастую решения требуется прини­мать в режиме, близком к реальному времени. При­нятие правильного решения заключается в выборе такого варианта из числа возмож­ных, в котором с учетом всех разнообразных факторов и противоречивых тре­бований будет оптимизирована некая общая ценность, то есть решение будет в максимальной степени способствовать достижению поставленной цели. В качестве критерия оценки качества принимаемого решения выступает некая целевая функция, аргументами которой являются количественные характеристики, описы­вающие состояние факторов, влияющих на достижение цели в решаемой зада­че. При этом решению, приводящему к наилучшему результату, как правило, соответствует экстремальное значение целевой функции, то есть точка ее мак­симума или минимума. В основе традиционных методов оптимизации лежат матема­тические вычисления, позволяющие находить экстремум целевой функции. Ценность каждого такого метода заключается в том, что с помощью него мож­но найти точку экстремума целевой функции, не перебирая всех возможных комбинаций ее аргументов. Среди многочисленных подходов можно выделить три основных типа методов поиска оптимальных решений. Методы, основанные на математических вычислениях подразделяются на направленные и ненаправленные. Суть ненап­равленного метода состоит в том, что локальный экстремум ищется путем ре­шения системы, как правило, нелинейных уравнений. Эта система составляет­ся путем прирав-нивания градиента целевой функции к нулю (например, метод градиентного спуска или покоординатного спуска). Направленные методы строятся на перемещении от точки к точке в допустимой области, причем направле­ние подобных перемещений связывается с направлением, на которое указыва­ет градиент (например, метод касательных). К недостаткам этих методов можно отнести очень жесткие условия, накла­дываемые на целевую функцию. Она должна быть дифференцируема на всем пространстве поиска. При формализации современных задач это условие, как правило, выполнить не удается. Кроме того, данные методы находят лишь ло­кальные экстремумы целевой функции, тогда как оптимальному решению со­ответствует только глобальный экстремум. Следовательно, методы поиска оп­тимальных решений, основанные на математических вычислениях, примени­мы лишь в случаях гладких, всюду дифференцируемых целевых функций, имею­щих один экстремум на пространстве поиска. Перечислительные методы основываются на том, что пространство поиска любой задачи можно представить в виде совокупности дискретных то­чек. Даже если пространство поиска непрерывно, то конечная точность пред­ставления чисел в компьютере позволяет сделать такое допуще­ние. В этом случае поиск решения будет сводиться к перебору всех точек про­странства поиска и вычислению в них целевой функции, в одной из которых она, несомненно, примет экстремальное значение. Недостаток этих методов очевиден. При увеличении числа аргументов целевой функции количество точек простран­ства значительно увеличивается, что приводит к значитель-ным временным зат­ратам и необходимости применения все более мощной и дорогостоящей вы­числительной техники. В то же время размерность решаемых сейчас задач по­стоянно растет, а время, доступное для принятия решений сокращается. Следовательно, перечислительные методы также применимы для решения все более сужающегося класса задач. Методы, использующие элементы случайного по­иска в пространстве задачи с сохранением наилучшего полученного результата. Очевидно, что такие методы не гарантируют нахождение оптимальных решений, но могут к ним существенно приблизиться. Для этого в методы вносится свойство детерминированности, на чем основываются эволюционные вычисления. Эволюционные вычисления используется для описания алгоритмов поиска, основанных на не­которых формализованных принципах естественного эволюционного процес­са. Основное преимущество эволюционных вычислений заключается в возможности решения задач с большой размерностью за счет сочетания элементов случайности и детерминированности точно так, как это происходит в природной среде. Детерминированность методов заключается в моделировании природ­ных процессов отбора, размножения и наследования, происходящих по строго определенным правилам. Основным правилом при этом является закон эволю­ции: «выживает сильнейший», который обеспечивает улучшение находимого решения. Другим важным фактором эффективности эволюционных вычисле­ний является моделирование размножения и наследования. Рассматриваемые варианты решений могут по определенному правилу порождать новые реше­ния, которые будут наследовать лучшие черты своих «предков». В качестве случайного элемента в методах эволюционных вычислений мо­жет использоваться, например, моделирование процесса мутации. В этом слу­чае характеристики того или иного решения могут быть случайно изменены, что приведет к новому направлению в процессе эволюции решений и может ускорить процесс выработки лучшего решения. История эволюционных вычислений началась с разработки ряда независимых моделей эволюционного процесса. Среди этих моделей можно выделить три основные парадигмы – это генетические алгоритмы, эволюционные стратегии, эволюционное программирование. Отличительной особенностью генетических алгоритмов является представле-ние любой альтернативы решения в виде битовой строки фиксированной длины, манипуляции с которой производятся в отсутствие всякой связи с ее смысловой интерпретацией, то есть применяется единое универсальное представление любой задачи. Эволюционные стратегии представляют каждую из альтернатив решения еди­ным массивом численных параметров. По существу за каждым массивом скрывается аргумент целевой функции. Воздействие на данные массивы осуществ­ляется с учетом их смыслового содер­жания и направлено на улучшение значений входящих в них параметров. Эволюционное программирование основано на пред­ставлении альтернатив решений в виде моделей-автоматов, описывающих средствами формальной логики возможные переходы исследуемой системы из некоторого начального состояния в заключительное состояние. Эволюционная программа при этом реализует моделирование процессов естественной эволюции моделей-автоматов, когда в каждый момент времени сохраняется тот «организм», который может наилучшим способом справится с данной задачей. Эволюционные вычисления не гарантируют обнаружения глобального экстремума целевой фун­кции, однако они демонстрируют эффективность решений ряда практических задач по проектированию, планированию, управлению, прогнозированию во многих областях техники. Отрицательной чертой эволю-ционных вычислений является то, что они представляют собой скорее подход к решению задач оптимизации, чем алгоритм. Вследствие этого они требуют адаптации к каждому конкретному классу задач путем выбора определенных характеристик и параметров. Генетические алгоритмы. Генетический алгоритм представляет собой поисковый алгоритм, основанный на природных механизмах селекции и генетики. Он работает с кодами безотно-сительно их смысловой интерпретации. Поэтому сам код и его структура описыва-ются понятием генотип, а его интерпретация, с точки зрения решаемой задачи, понятием фенотип. Каждый код представляет, по сути, точку про­странства поиска. С целью максимально приблизиться к биологическим тер­минам, экземпляр кода называют хромосомой или особью. В обозначении строки кода будем использовать термин «особь». На каждом шаге работы генетический алгоритм использует несколько то­чек поиска одновременно. Совокупность этих точек в пространстве поиска является набором особей или популяцией. Количество особей в популяции называют размером популяции. Размер популяции является фиксированным и представляет одну из характеристик генетического алгоритма. Формирование исход-ной популяции происходит с использованием какого-либо случайного закона, на основе которого выбирается нужное количество точек поискового пространства. На каждом шаге работы генетический алгоритм обновляет популя­цию путем создания новых особей и уничтожения старых. Чтобы отличать по­пуляции на каждом из шагов и сами эти шаги, их называют поколениями и обычно идентифицируют по номеру. Например, популяция, полученная из ис­ходной популяции после первого шага работы алгоритма, будет первым поко­лением, после следующего шага - вторым, и т.д. В процессе работы алгоритма генерация новых особей происходит на ос­нове моделирования процесса размножения. При этом, естественно, порожда­ющие особи называются родителями, а порожденные соответственно - потомками. Родительс­кая пара, как правило, порождает пару потомков. Непосредственная генерация новых кодовых строк из двух выбранных происходит за счет работы оператора скрещивания, который также называют кроссинговером. При порождении новой популяции оператор скрещивания может применяться не ко всем парам родителей. Часть этих пар может переходить в популяцию сле­дующего поколения непосредственно. Насколько часто будет возникать такая ситуация, зависит от значения вероятности применения оператора скрещива­ния, которая является одним из параметров генетического алгоритма. Вероятность применения оператора скрещивания обычно выбирается в пределах от 0,9 до 1, чтобы обеспечить появление новых особей, расширяющих пространство поиска. При значении вероятности меньше единицы часто используют особую стратегию - элитизм, которая предполагает переход в популяцию следующего поколения элиты, то есть лучших особей текущей популяции, без всяких изменений. Применение элитизма способствует сохранению общего качества популяции на высоком уровне. При этом элитные особи участвуют еще и в процессе отбора родителей для последующего скрещивания. Количество элитных особей определяется по формуле , где К – количество элитных особей, Р - вероятность применения оператора скрещивания, N – размер популяции. В случае использования элитизма все выбранные родительские пары подвергаются скрещиванию, несмотря на то, что вероятность применения оператора скрещивания меньше единицы, что позволяет сохранить прежний размер популяции. Моделирование процесса мутации новых особей осуществляется за счет работы оператора мутации. Основным параметром оператора мутации также является вероятность мутации. Поскольку размер популяции фиксирован, то порождение потомков долж­но сопровождаться уничтожением других особей. Выбор пар родителей из по­пуляции для порождения потомков производит оператор отбора, а выбор осо­бей для уничтожения - оператор редукции. Основным параметром их работы является, как правило, качество особи, которое определяется значением целе­вой функции в точке пространства поиска, описываемой этой особью. В основе оператора отбора лежит принцип «выживает сильнейший». Выбор особи для размножения производится случайно. Вероятность участия особи в процессе размножения определяется по формуле , где i – номер особи, - вероятность участия особи в процессе размножения, - значение целевой функции для i -ой особи. Очевидно, что одна особь может быть задействована в нескольких родительских парах. Таким образом, можно перечислить основные понятия и термины, исполь­зуемые в области генетических алгоритмов: генотип и фенотип; особь и качество особи; популяция и размер популяции; поколение; родители и потомки. К характеристикам генетического алгоритма относятся: размер популяции; оператор скрещивания и вероятность его использования; оператор мутации и вероятность мутации; оператор отбора; оператор редукции; критерий останова. Операторы отбора, скрещивания, мутации и редукции называют еще гене­тическими операторами. Критерием останова работы генетического алгоритма может быть одно из трех событий: формирование заданного пользователем числа поколений; достижение популяции заданного пользователем качества; достижение уровня сходимости, при котором дальнейшее улучшение особей в популяции происходит чрезвычайно медленно. Характеристики генетического алгоритма определяются путем подбора, обеспечивающего поиск лучшего решения задачи за малое время работы. Рассмотрим примеры применения генетических алгоритмов при решении оптимизационных задач. Пример поиска одномерной функции. Пусть имеется набор натуральных чисел от 0 до 31 и функция , определен­ная на этом наборе чисел. Требуется найти максимальное значение функции. При решении задачи используем в качестве кода двоичное представление аргументов функции. Это положение представляет собой фенотип решаемой задачи. Сам код будет представлять собой двоичную строку из пяти бит. Это генотип алгорит­ма. Функция является целевой функцией. При задании характеристик генетического алгоритма будем исходить из следующих правил: Размер начальной популяции N можно выполнять произвольным образом, например подбрасыванием монеты; Вероятность оператора скрещивания ; Вероятность оператора мутации Пусть процесс мутации зак­лючается в инверсии одного из битов строки, выбираемого случайно по равно­мерному закону; вероятность оператора мутации равна 0,001; размер популяции (табл. 5); в связи с простейшей задачей стратегия элитизма в алгоритме не применяется. Таблица 5 Исходная популяция из четырех особей. № Код Значение Вероятность 1 01011 11 11/43 2 10010 18 18/43 3 00010 2 2/43 4 01100 12 12/43 Предположим, что оператор отбора выбрал для производства потомков две пары строк (1,2) и (2,4). В каждой паре разбиение на подстроки оператором скрещивания происходит независимо (табл. 6). Таблица 6 Работа оператора скрещивания № Родители Потомки Значение для потомков 1 0 1011 00010 2 2 1 0010 11011 27 3 10010 10000 16 4 01100 01110 14 Пусть оператор мутации, несмотря на низкую вероятность 0,001, изменяет значение кода потомка в третьей строке (табл.6) с 10000 на 10001. Тогда за счет порожденных потомков популяция расширяется до восьми особей. Оператор редукции сокращает популяцию до исходного числа особей, исключая те особи, в которых значения целевой функции минимальны (табл. 7). Таблица 7. Популяция первого поколения особей. № Код Значение Вероятность 1 10010 18 18/76 2 11011 27 27/76 3 10001 17 17/76 4 01110 14 14/76 На этом шаг работы генетического алгоритма заканчивается. Очевидно, что даже за эту одну итерацию качество популяции значительно возросло. Лучшее решение увеличилось с 18 до 27 при оптимальном решении 31. Оптимизационная задача по обучению нейронной сети. Обучение нейронных сетей является одной из основных областей применения генетических алгоритмов. Для построения и обучения нейронной сети зададим набор при­меров, который представляет собой совокупность векторов вида, где - значения всех входов нейронной сети, a - значения всех выходов нейронной сети, которые должны получаться в процес­се ее работы. Структура эталонных векторов задает одновременно количество входных и выходных нейронов, то есть в данном случае n и m соответственно. Целью обучения нейронной сети является достижение такой ситуации, когда при подаче на вход сети любого вектора X из набора примеров на ее выходе получается выходной вектор , отличающийся от эталонного вектора Y не более чем на заданную заранее и вычисляемую определенным образом величину . Исходными данными для решения задачи являются количество входных и выходных нейронов; набор обучающих примеров. Требуется найти следующие характеристики нейронной сети: количество скрытых слоев; количество нейронов в каждом скрытом слое; значения весов всех входов для каждого скрытого и выходного нейрона; функции активации для каждого скрытого и выходного нейрона. Очевидно, что целевой функцией в данной задаче будет максимальное значение , полученное среди всех векторов набора примеров. Подбирая значения характеристик нейронной сети и вычис­ляя каждый раз значение , можно найти такое значение , которое требуется. Чем меньше значение , тем качественнее будет построена нейронная сеть. Таким образом, задача обучения нейронной сети сводится к задаче поиска оптимального решения. Следует заметить, что даже для простейших нейронных сетей эта задача является многомерной и крайне сложной. Цель найти нейронную сеть, удовлетворяющую условию , для реальных задач недости­жима и обычно не ставится. Поэтому поиск оптимального решения превраща­ется в поиск лучшего решения, где с успехом можно применить генетический алгоритм. Как правило, генетические алгоритмы используются на различных эта­пах построения и обучения сети в качестве основного или вспомогательного сред­ства. Генетический алгоритм может использоваться на первом этапе работы для поиска общих параметров нейронной сети: количества скрытых слоев и нейронов. Также генетический алгоритм может использоваться на заключитель­ном этапе работы для поиска всех значений весов нейронной сети и функций активации. Причем функции активации, как правило, выбираются из ограниченного набора, а еще чаще подбирается не сама формула функции ак­тивации, а один или несколько ее параметров. Для упрощения возьмем не­большую сеть прямого распространения (рис. 46) и построим для нее обучающий алгоритм. Сеть состоит из шести нейронов: трех входных, двух скрытых и одного выходного. Рис. 46 Нейронная сеть. Используем сигмоидальную функцию качестве функции активации , а для вычисления значения целевой функции выражение , где k – число примеров; - значение выхода нейронной сети для j –го примера; - эталонное значение выхода нейронной сети для j – го примера. Для останова работы генетического алгоритма можно указать число поколений, а можно задать условие на значение целевой функции. Например, остановить работу алгоритма, когда значение целевой функции . При обучении нейронной сети размер популяции должен быть не менее 100 особей. В качестве кода при решении задачи будем использовать массив из 11 действительных чисел (табл. 8), по четыре на каждый скрытый нейрон и три для выходного нейрона, которые представляют собой веса соответствующих входов нейронов и параметры их функций активности. Для элементов хромосомы (особи) – генов – введем ограничения, обусловленные природой нейронных сетей: Для оператора скрещивания можно установить вероятность применения 0,95 и использовать элитизм. В качестве оператора мутации будем использовать случайное изменение значений весов и параметра функции активации для каждого нейрона на случайную величину. Вероятность мутации 0,01. Причем одновременно будет изменяться параметр функции только для одного нейрона, и для каждого нейрона будет изменяться один из входных весов. Какие конкретно веса и параметры будут меняться, определяется по равномерному закону. Например, мутация может быть следующей: значение увеличивается на 0,1; значение уменьшается на 0,01 и т.д. Исходная информация будет формироваться на основе равномерного распределения для каждого гена хромосомы (особи). Таблица 8 Структура кода. Рассмотренный процесс показывает, насколько сложной является задача построения и обучения нейросети как с точки зрения ее размерности, так и с точки зрения ее вычислительной сложности. Тем не менее, генетические алго­ритмы представляют один из эффективных и изящных путей ее решения. Выводы по лекции. Эволюционные вычисления, в том числе и генетические алгоритмы, представляют собой подход к решению задачи по­иска лучшего решения, а не четко определенный алгоритм. Для решения конк­ретной задачи, помимо ее формализации, формулировки генотипа и фенотипа, требуется создавать и конкретный генетический алгоритм. Для этого задают значения размера популяции, вероятности мутации, описывают процесс рабо­ты операторов отбора, скрещивания, мутации и редукции, что и было показано в рассмотренных примерах. Однако может оказаться, что алгоритм, успешно решаю­щий одну задачу, совершенно не подходит для решения другой. Создание генетических алгоритмов, эффективно решающих как можно большее число задач, является предметом проводимых в настоящее время исследований.

Похожие рефераты: