Содержание к диссертации
Введение
CLASS 1 Теоретические основы процесса обучения ней онных сетей с помощью генетических алгоитмов CLASS
1.1 Анализ методов обучения нейронных сетей прямого распространения 22
1.2 Генетические алгоритмы в качестве метода эволюционного моделирования при решении задач оптимизации 31
1.3 Влияние отбора и проблема сходимости генетических алгоритмов к глобальным кстремумам целевых функций 40
Выводы 48
2 Пути повышения скорости и устойчивости ра оты генетических алгоритмов 50
Метод увеличения скорости генетического кодирования линейным кодом 51
Мажоритарный генетический алгоритм в качестве модели волюции диплоидных популяций 62
Выводы 69
3 Анализ свойств генетических операторов мажо итарного генетического алгоритма 71
Оператор кроссинговера в мажоритарном генетическом алгоитме 73
Математическая модель оператора кроссинговера маоритарного генетического алгоритма 76
Оценка деструктивных свойств оператора кроссинговера мажоритарного генетического алгоритма 83
Оператор мутации в мажоритарном генетическом алгоритме 96
Математическая модель оператора мутации мажоритарного генетического алгоритма 98
Оценка деструктивных свойств оператора мутации мажоритарного генетического алгоритма 102
Выбор оптимального алгоритма процесса протекания мутации на основе анализа вероятностей апостериорных гипотез 113
Математическая модель-процесса несвободной мутации в мажоритарном генетическом алгоритме 125
Выводы 136
4 Экспериментальные исследования мажоритарного генетического алгоритма 139
4.1Характеристики популяции, определяющие меру сходимости эволюционного процесса 140
4.2Решение задач глобальной оптимизации с помощью мажоритарного генетического алгоритма 143
Обучение искусственных нейронных сетей прямого распространения с помощью мажоритарного генетического алгоритма 157
Выводы 164
Заключение 166
Список используемых источников 170
Приложения
- Генетические алгоритмы в качестве метода эволюционного моделирования при решении задач оптимизации
- Мажоритарный генетический алгоритм в качестве модели волюции диплоидных популяций
- Выбор оптимального алгоритма процесса протекания мутации на основе анализа вероятностей апостериорных гипотез
- Обучение искусственных нейронных сетей прямого распространения с помощью мажоритарного генетического алгоритма
Введение к работе
Задачи синтеза и анализа любой природы относятся к классу комбинаторных и, в большинстве случаев, имеют не одно, а множество решений различной значимости. Для решения таких задач разработано множество методов, способов и алгоритмов. Ядром всех комбинаторных алгоритмов являются операции полного, или сокращенного перебора подмножеств ре-шений, но суть комбинаторного перебора в различных алгоритмах проявляется по-разному. Для поиска лучшего решения можно осуществлять направленный, случайный и направленно-случайный перебор всевозможных значений параметров задачи, Генетические алгоритмы (ГА) сейчас —это мощный механизм поиска оптимальных решений в задачах науки, техники, производства [31].
Одним из направлений дальнейшего развития интеллектуальных систем, используемых в условиях неполноты и противоречивости информации, стало введение адаптации в процесс поиска решений, переход от формализованных систем классических логик к адаптивным моделям [1,4,7, 17,26,30-33,36,46,48-51]. Перспективным подходом является использование аналогий с процессами развития, изменения и приспособления живых организмов. Анализ адаптивного развития естественных процессов был основополагающим при разработке двух разделов вычислений; нейронных сетей и алгоритмов эволюционного моделирования.
Искусственные нейронные сети прямого распространения (многослойные перцептроны) в настоящее время используются для решения целого круга задач распознавания образов, сжатия изображений» идентификации, прогнозирования, управления [25,28,45] и т.д. В нетривиальных условиях данные сети для корректной работы должны пройти процедуру обучения с целью минимизации функционала ошибки между выходными и эталонными значениями. Среди множества методов обучения нейронных сетей такого типа особое место занимают методы, построенные на использовании генетических алгоритмов, к основным достоинствам которых можно
отнести робастность, оперирование с множеством решений и теоретическую сходимость к глобальным экстремумам.
Эволюционные вычисления, к которым относятся генетические алгоритмы, являются одной из фундаментальных областей научных исследований на-стыке информатики, биологии и искусственного интеллекта [17,31, 33,102,115]. Они нашли применение при решении различных задач проектирования [19,30], оптимизации структуры и обучения нейронных сетей [25,27,28,45], исследования графов [30], построения правил вывода в самонастраивающейся экспертной системе продукционного типа [100].
При поиске решений задачи глобальной оптимизации могут быть использованы аналогии с биологическими процессами эволюции [8, 17]. Введение эволюционного процесса в системы искусственного интеллекта позволяет перейти от систем с жестко заданными связями к моделям с динамически меняющейся структурой на каждом шаге в зависимости от эффективности решаемой задачи. Эволюционная^ адаптация может проявляться на уровне знаний, правил перехода от одной формальной системы к другой, изменения функций агентов, динамического распределения ресурсов реконфигурируемых устройств. В системах искусственного интеллекта эволюция может быть использована также при исследовании способности системы адаптироваться к изменению окружающей среды.
Эффективность использования генетических алгоритмов зависит от множества факторов. Их оптимальный выбор приводит к повышению скорости и устойчивости поиска. Скорость генетического поиска определяется временем, необходимым для выполнения заданного пользователем критерия останова (достижением заданного числа итераций, качества, популяции или сходимости). Устойчивость поиска определяется способностью постоянно повышать среднюю целевую функцию и преодолевать локальные оптимумы, В существующих алгоритмах выбор параметров генетических алгоритмов является произвольным, во многих задачах он определяется только интуицией пользователя [17].
При решении задач эволюционного моделирования обычно используются популяции фиксированного размера, время жизни и оператор редукции» что приводит к возникновению явления преждевременной сходимости. Оператор редукции особей и оператор селекции разнесены во времени, что приводит к несогласованности этих процедур [8,17].
Одним из перспективных направлений является разработка алгоритмов эволюционных вычислений с использованием различных моделей эволюции и исследование динамики эволюционного процесса при решении задач поиска глобального экстремума.
Таким образом, актуальность темы диссертационных исследований обусловлена тем, в настоящее время методы генетического поиска не гарантируют сходимости к глобальному экстремуму целевой функции и имеют достаточно высокую вероятность получения неудовлетворительных результатов при обучении нейронных сетей прямого распространения вследствие вырождения популяции генетического алгоритма в локальных экстремумах функционала ошибки.
Объектом диссертационных исследований являются генетические алгоритмы, применяемые для обучения нейронных сетей прямого распространения.
Предметом диссертационных исследований являются математические модели процессов генетического поиска, применяемые для повышения Эф" фективности и качества обучения нейронных сетей прямого распространения.
Целью диссертационных исследований является повышение качества обучения искусственных нейронных сетей прямого распространения за счет увеличения вероятности сходимости генетического алгоритма к глобальным экстремумам целевых функций.
Научная задача исследований состоит в разработке эффективного генетического алгоритма для повышения качества обучения нейронных
сетей прямого распространения путем использования методов математического моделирования.
Для решения поставленной общей научной задачи была проведена ее декомпозиция на ряд следующих частных задач:
Выполнение анализа использования базовых структур генетического поиска при обучении нейронных сетей прямого распространения.
Разработка метода кодирования/декодирования генетической информации для минимизации временнйх затрат на обработку двоичных данных.
Разработка генетического алгоритма на основе построенной математической модели доминирования генов с упрощенными правилами
экспрессии и меньшей ресурсоемкостью,
Построение математических моделей и исследование деструктивных свойств генетических операторов разработанного генетического алгоритма, влияющих на скорость и устойчивость сходимости процесса адаптации.
Проведение имитационного моделирования и получение сравнительных оценок эффективности решения задач глобальной оптимизации простого и разработанного генетических алгоритмов.
6. Обучение нейронных сетей прямого распространения с помощью раз
работанного генетического алгоритма-
Методы исследования. Для решения поставленных в диссертаци
онной работе научных задач использованы методы теории вероятностей,
основы теории случайных процессов, теории выживания особей генетиче
ских алгоритмов, теории нейронных сетей.
Работа состоит из введения, четырех глав, заключения и приложений.
Во введении обоснована актуальность исследования моделей процессов генетического поиска для повышения качества обучения.нейронных сетей прямого распространения, сформулирована цель работы, изложены основные результаты проведенных исследований, показаны их научная новизна и практическая значимость, указаны основные положения, выносимые на защиту..
В первой'главе, показаны преимущества обучения искусственных нейронных сетей прямого распространения с помощью генетических алгоритмов, которые эффективны в поиске глобальных минимумов адаптивных рельефов функционала ошибки, поскольку ими исследуются большие области допустимых параметров нейронных сетей- ГА, обладая свойством робастности, позволяют обучать нейронные сети с недифференцируемыми функциями активации нейронов. Выявлены также недостатки использования ГА, основным из которых является негарантированная сходимость к глобальным экстремумам функционала ошибки за конечное время обучения нейронных сетей- Осуществлена постановка задачи на исследование.
Показано, что при обучении нейронных сетей прямого распространения традиционные методы обучения не гарантируют сходимости к глобальному экстремуму функционала ошибки, что может снизить качество и увеличить общее время обучения нейронных сетей прямого распространения, вследствие чего возникает необходимость использования методов глобальной оптимизации. Из множества разработанных в этой области подходов в настоящее время нашли широкое применение генетические алгоритмы в силу достоинств, присущих данным методам.
Выявлены основные отличия генетических алгоритмов от других.методов эволюционного моделирования, главным из которых является ориентированность генетических алгоритмов на исследование генетического материала, тогда как в эволюционных алгоритмах решение задачи адаптации сводится к изучению поведения фенотипа. Определена базовая структура генетических алгоритмов, которой является простой генетический алго-
ритм, определяющий основные этапы эволюции искусственной популяции, используемой при решении задачи адаптации. Приведено определение шаблона простого генетического алгоритма как представления подмножества генетических строк.
Поскольку работа генетического алгоритма зиждется на гипотезе о селекции, то произведен сравнительный анализ влияния существующих методов отбора на эффективность генетического поиска. Показано, что среди алгоритмов отбора наибольшее распространение нашла пропорциональная селекция, однако с ней связан ряд математических проблем, главной из которых является негарантированная сходимость генетического алгоритма, использующего данный оператор отбора, к глобальному экстремуму. Скорость и устойчивость процесса адаптации искусственной популяции генетического алгоритма могут быть оценены с помощью положений теории выживания особей, основополагающим утверждением которой является теорема Холланда, полученная в [107].
Анализ использования генетических алгоритмов при обучении нейронных сетей прямого распространения позволил выявить ряд проблем, связанных с ухудшением скорости и устойчивости генетического поиска вследствие неверного выбора параметров алгоритма, что служит причиной снижения качества обучения нейронных сетей прямого распространения, чем и объясняется потребность в разработке моделей эволюции искусственных популяций с целью повышения скорости и устойчивости сходимости построенных на их основе ГА,
Во второй главе рассмотрены пути повышения эффективности использования генетических алгоритмов при решении задач поиска глобальных экстремумов целевых функций- Разработан способ, позволяющий осуществить кодирование/декодирование генетической информации с помощью кодека на основе радиальной базисной нейронной сети с минимальным временем обработки кодовых слов. Разработана модель эволюции диплоидных популяций, получившая название мажоритарного генетическо-
го алгоритма, определены правила экспрессии генов для разработанного
генетического алгоритма, произведена оценка ресурсоемкое алгоритма с позиции определения объема памяти, требуемого для хранения всех особей популяции.
Показано, что методы генетического поиска, базирующиеся на использовании простого генетического алгоритма, сложно применить к системам, для которых нельзя произвести декомпозицию на'подсистемы. Недостатком также является сильная зависимость эффективности данных методов от порядка расположения генов в хромосоме, что может свести к нулю преимущества обмена генетическим материалом и затруднить поиск глобального экстремума в задаче адаптации.
Показано, что эффективность ГА может быть улучшена путем представления генетической информации хромосом в виде двоичных строк, особенно при использовании кодов Грея, однако в этом случае приобретает актуальность задача.уменьшения.временных затрат на осуществление кодирования/декодирования двоичных данных.
Предложен один из вариантов решения данной проблемы применительно к линейным кодам, к которым относитсякод Грея, с помощью кодека, построенного на основе использования радиальной базисной нейронной сети.
Одним из способов увеличения эффективности использования генетического алгоритма при решении задач поиска глобального экстремума, является построение модели доминирования генов в диплоидном способе кодирования решений, на основании чего был разработан мажоритарный генетический алгоритм. Особенностью, отличающей его от существующих аналогов, является то, что решение задачи кодируется, тремя строками: двумя:равнозначными гомологичными хромосомами Л* и Уч гены которых могут быть модифицированы генетическими операторами в процессе эволюции, и одной опорной хромосомой Х\ содержащей подавляющее значение в фенотипе особей, элементы которой не изменяются до момента
элиминации особи. Каждая из указанных хромосом несет генетическую информацию в двоичном коде.
Помимо упрощения правил экспрессии генов, исключающих наличие конфликтов, одним из достоинств разработанного мажоритарного генетического алгоритма является экономия памяти, необходимой для хранения особей популяции- По сравнению с существующими аналогичными моделями, построенными на основе использования четырехбуквенного алфавита, требуемый объем памяти сокращен на 25%.
В третьей главе определено множество генетических операторов разработанного мажоритарного генетического алгоритма, выявлены особенности выполнения выбранных генетических операторов, произведена оценка их деструктивных свойств с позиции теории выживания особей, осуществлен анализ с аналогичными оценками генетических операторов простого генетического алгоритма.
Показано, что в условиях популяции ограниченного размера мутация и кроссинговер являются операторами, позволяющими исследовать области пространства поиска, не охваченные популяцией, и наиболее близкие к глобальным экстремумам целевых функций.
Разработана модель выполнения оператора кроссннговера мажоритарного генетического алгоритма, семантически сходная с реальными биологическими процессами, использование которой позволяет увеличить генетическое разнообразие популяции и тем самым снизить вероятность сходимости оптимизационного процесса к локальным экстремумам целевых функций. На.основе предложенной модели был разработан алгоритм, реализующий две фазы оператора кроссннговера мажоритарного генетического алгоритма. Определено влияние на фактор роста в теореме Холланда оператора кроссннговера мажоритарного генетического алгоритма, анализ которого позволил сделать вывод о том, что по своим деструктивным свойствам разработанный оператор кроссннговера не хуже, чем оператор равномерного кроссннговера простого генетического алгоритма,
Обоснован отказ от использования оператора инверсии в мажоритарном генетическом алгоритме на основе результатов, полученных из анализа деструктивных свойств оператора кроссинговера.
Разработана модель протекания мутации в мажоритарном генетическом алгоритме. В случае, независимой свободной мутации вероятность разрушения шаблона в теореме Холланда, обусловленная влянием данного генетического оператора, не превышает величину соответствующей'вероятности для простого генетического алгоритма при равных условиях. Более низкая оценка полученной вероятности приводит к более высокому значению фактора роста в теореме Холланда- Это служит доказательством того, что использование мажоритарного генетического алгоритма по отношению к мутации более эффективно по сравнению с использованием простого генетического алгоритма, при одинаковых значениях вероятности точечной мутации. Проведенный анализ апостериорных гипотез позволил выявить один из наиболее предпочтительных алгоритмов, по которому должен протекать мутагенез.
Построена модель процесса несвободной мутации. Доказано, что использование алгоритмов несвободной мутации в мажоритарном генетическом алгоритме позволяет максимально снизить и исключить влияние мутаций на фенотип особей популяции, чем удается обеспечить максимальную величину фактора роста без отказа, от оператора мутации.
В четвертой главе проведены экспериментальные исследования, направленные на подтверждение теоретических результатов, полученных в предыдущих главах. Показано эффективное обучение нейронных сетей прямого распространения с помощью мажоритарного генетического алгоритма.
Определены критерии сходимости1 генетических алгоритмов с фиксированной длиной хромосомы. Для построения имитационных моделей поиска глобальных экстремумов с помощью простого и мажоритарного генетических алгоритмов был выбран язык сценариев Maple- Описаны основ-
ные процедуры программных модулей, реализующие модели генетического поиска.
Для оценки эффективности мажоритарного генетического алгоритма производилось решение задач поиска глобального экстремума трех функций двух переменных за определенное число генерируемых поколений популяции фиксированного размера с последующим вычислением среднего значения эффективности за указанное число прогонов алгоритма. Анализ результатов проведенного имитационного моделирования показал; эффективность разработанного алгоритма не зависит от способа наследования потомком признака доминантности одного из родителей, иными словами, оператор кроссинговера мажоритарного генетического алгоритма симметричен по отношению к особям-родителям, что приближает его к оператору равномерного кроссинговера простого генетического алгоритма. Выявлено,. что эффективность мажоритарного генетического алгоритма при больших вероятностях точечной мутации больше, чем простого генетического алгоритма. Наибольшую величину эффективности, как следует из результатов имитационного моделирования, дает использование методов несвободной мутации с запретом на изменение фенотипа особи.
Показано применение мажоритарного генетического алгоритма на примере решения задачи поиска глобального экстремума функции в случае фенотипически вырожденной популяции.
Проведенные и проанализированные экспериментальные исследования решения задач поиска глобального экстремума с помощью разработанного генетического алгоритма показали достоверность и значимость теоретических результатов, полученных в предыдущих главах.
При решении тестовых задач обучения нейронных сетей прямого распространения с помощью мажоритарного генетического алгоритма сначала производилась процедура обучения для одного нейрона с сигмоидальной функцией активации, затем однослойной нейронной сети и многослойной нейронной сети с пороговыми функциями активации, служащей упрощен-
ным аналогом рециркуляционных нейронных сетей, используемой для сжатия изображений и распознавания образов. Во всех трех случаях было подтверждено эффективное применение разработанного мажоритарного генетического алгоритма для обучения нейронных сетей прямого распространения:
Проведенные и проанализированные экспериментальные исследования решения задач поиска глобального экстремума с помощью разработанного генетического алгоритма показали достоверность и значимость теоретических результатов, полученных в предыдущих главах,
В заключении обобщены итоги и результаты проведенных исследований,
В приложениях показаны примеры использования разработанного кодека на основе радиальной базисной нейронной сети, приведены исходные тексты сценариев Maple для проведения анализа распределения сочетаний аллелей потомков мажоритарного генетического алгоритма в результате выполнения оператора кроссинговера, представлены журнал тестирования и исходные тексты сценариев Maple.
Достоверность и обоснованность полученных в диссертационной работе результатов и формулируемых на их основе выводов обеспечиваются строгостью и корректностью производимых математических выкладок, базирующихся на аппарате теории вероятностей, нейронных сетей и теории выживания особей в генетических алгоритмах- Справедливость выводов относительно эффективности предложенных методов подтверждена математическим и имитационным моделированием.
Научная, новизна работы заключается в получении следующих результатов:
1. Разработан метод кодирования/декодирования генетической информации, отличающийся тем, что в его основе лежит использование радиальной базисной нейронной сети, в результате чего становится
возможным минимизировать временные затраты на обработку двоичных данных.
2, Разработан генетический алгоритм с диплоидным способом кодирова
ния генетической информации на основе построенной в работе моде
ли доминирования генов, в котором упрощены правила экспрессии и
снижен объем требуемого ресурса памяти для хранения всех особей
популяции на 25%.
Для разработанного генетического алгоритма определены генетические операторы, отличающиеся от аналогичных для простого генетического алгоритма тем, что их выполнение идет в соответствии с построенной моделью доминирования генов.
Для генетических операторов разработанного генетического алгоритма произведена оценка деструктивных свойств, развивающая ранее известные положения теории выживания особей генетических алгоритмов.
5, Доказаны преимущества использования разработанного генетическо
го алгоритма при решении задач адаптации по сравнению с простым
генетическим алгоритмом.
Практическая значимость результатов данной работы состоит в следующем:
1, Разработанный метод кодирования/декодирования линейного кода мо
жет быть использован не только в генетических алгоритмах, но и при
решении других задач кодирования/декодирования информации, тре
бующих высокоскоростной обработки двоичных данных,
2. Разработанный генетический алгоритм на основе построенной модели
доминирования генов может быть использован при решении техниче
ских и экономических задач, которые формулируются в виде задач
глобальной оптимизации. Целесообразность практического использования полученных в работе алгоритмов подтверждена при помощи тестов, доказавших их эффективность, а в ряде случаев — превосходство над существующими аналогами.
3. Разработанный генетический алгоритм позволяет производить обучение нейронных сетей прямого распространения с недифференцируе-мыми функциями активации нейронов. Сети такого типа могут быть использованы при решении задач распознавания и сжатия изображений.
На защиту выносятся следующие основные положения:
Минимизация временных затрат на кодирование/декодирование генетической информации возможна за счет распараллеливания обработки двоичных данных с помощью использования радиальной базисной нейронной СЄТИ-
Сокращение объема ресурса памяти на 25%, необходимого для популяции, и упрощение правил экспрессии генов генетического алгоритма с диплоидным способом кодирования решений достигаются за счет использования модели доминирования генов, построенной на принципах работы мажоритарного клапана.
Увеличение устойчивости сходимости разработанного генетического алгоритма к глобальным экстремумам целевых функций возможно за счет использования предложенного в работе алгоритма выполнения оператора кроссинговера, сходного по своему деструктивному влиянию с оператором равномерного кроссинговера простого генетического алгоритма,
Увеличение скорости сходимости разработанного генетического алгоритма к глобальным экстремумам целевых функций за счет сведения
к нулю вероятности разрушения шаблона вследствие влияния мутации в теореме Холланда, в результате чего удается достичь максимального значения фактора роста без отказа от использования оператора мутации.
Личный вклад автора. Лично автору принадлежат методы определения центроидов нейронов скрытого слоя и настройки весов и смещений нейронов выходного слоя радиальной базисной нейронной сети, используемой для кодирования/декодирования генетической информации, разработка математической модели доминирования генов и построение на ее основе генетического алгоритма, для которого автором произведена разработка математических моделей выполнения генетических операторов и оценка их деструктивных свойств.
Апробация работы. Основные результаты докладывались на 48 научно-методической конференции преподавателей и студентов «Университетская наука — региону» (Ставрополь, 2003), на V Международной научно-практической конференции «Информационная безопасность» (Таганрог, 2003), на Междисциплинарной (медицина, биология, радиоэлектроника, химия, математика, информатика, педагогика ,,.) конференции с международным участием «Новые биокибернетические технологии 21 века для диагностики и лечения заболеваний человека* (Петрозаводск, 2003), на IV Международной научной конференции «Интеллектуальные и многопроцессорные системы— 2003» (п. Дивноморское, 2003), где доклад по теме диссертационных исследований был отмечен премией как один из лучших докладов, на III Санкт-Петербургской межрегиональной конференции «Информационная безопасность регионов России {ИБРР—2003)*> (Санкт-Петербург, 2003).
Публикации. По теме диссертации опубликовано 17 печатных работ из них 7 научных статей. Практическая значимость работы подтверждена 3 актами реализации.
Автор глубоко благодарен научному руководителю кандидату технических наук, доценту Александру Федоровичу Чипиге за постановку задачи и постоянное внимание к работе.
Генетические алгоритмы в качестве метода эволюционного моделирования при решении задач оптимизации
Согласно эволюционной теории каждый биологический вид целенаправленна развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде. Эволюция в этом смысле представляет процесс оптимизации всех живых организмов. Внутренняя логика и строгая направленность законов живой природы.позволили выдвинуть гипотезу о возможности обобщения генетических процессов, характерных для живой природы, на ряд других наук, и, в первую очередь, на прикладную математику, что послужило поводом для построения эволюционных методов и, в частности, генетических алгоритмов [13,17]. Одними из первых работ по использованию механизмов эволюции для решения задач искусственного интеллекта были исследования по ма шинному обучению [17,98]. Поиск решений в большинстве вариантов за ключается в определении множества альтернативных решений, затем их оценке и выборе лучшего варианта. Под термином «принятие лучшего ре шениям следует понимать, как это показано в [17], нахождение приемле мого решения, которое может не быть оптимальным. Подобная постановка процесса принятия решений позволяет формализовать поиск решения на основе теории «мягких вычислений [125], в частности, алгоритмов эво люционного моделирования. Они отличаются возможностью нахождения решения при неточности, неопределенности, неполноте знаний и устой чивости его поиска в таких условиях, простотой использования, а также адекватной связью с реальностью.
Алгоритмы эволюционного моделирования являются адаптивными алгоритмами, что позволяет применять их в нелинейных задачах высокой размерности при отсутствии требований к дифференцируемости оптимизируемой функции или полноты знаний о решаемой проблеме. Они отличаются устойчивостью при поиске решения, хотя в задачах большой размерности может быть низка скорость его определения [17,29]. Алгоритмы эволюционного моделирования, как это показано на рисунке 1.4, подразделяются на эволюционные стратегии [118,122], эволюционное программирование [90,92-94] и генетические алгоритмы [107-109], которые включают в себя как подмножество генетическое программирование [113,114]. Эволюционные стратегии [17,118,122] оперируют с объектами, тесно связанными с самой задачей. Каждый из элементов популяции является При эволюционных вычислениях выделяют три фазы поиска решения [17]. На первом этапе определяются целевая функция и правила кодирования генетической информации. Синтез решения выполняется с использованием операторов репродукции (кроссинговера, мутации и т.д.), имеющих вероятностную основу. На третьем этапе проводится селекция. Подход эволюционных вычислений изначально не подразумевает фазы анализа при построении моделей. Как отражение процессов, происходящих в живой природе,.в эволюционных вычислениях существуют различные философские подходы к эволюционному процессу. Принципиальные отличия в генетических и эволюционных алгоритмах [17,31,33,34t 87,91,102t 105,115,121] состоят в выборе объекта, возможности которого исследуются с точки зрения эволюционной адаптации. Генетические алгоритмы ориентированы на исследования возможностей генетического материала, а в эволюционных алгоритмах задача сводится к изучению поведения фенотипа [17,92]. С теоретической точки зрения генетические алгоритмы используют эволюционную адаптацию как. механизм развития и комбинации полезных схем из ограниченного генетического материала. Генетическое программирование не является отдельным эволюционным алгоритмом. Это специальная форма генетического алгоритма, использующая модифицированные генетические операторы. Генетическое программирование было разработано и исследовано в [17,113,114] с целью решения задачи автоматического программирования.
Различия в генетических и эволюционных алгоритмах проявляются также и в выборе целевой функции [17,31]. Селекция в генетических алгоритмах выполняется на основе целевой функции, которая на всех этапах эволюции остается неизменной, В результате развитие эволюционного процесса может свестись к нахождению локального экстремума. В эволюционных алгоритмах целевая функция определяется в процессе конкуренции между индивидами,.что обеспечивает изменение целевой функции и предотвращает преждевременную сходимость [94]. Эволюционные алгоритмы являются мощным инструментом по преодолению локальных экстремумов в оптимизационных задачах. Это объясняется использованием механизма конкуренции между индивидами. Исследование пространства поиска при помощи популяций решений, а не одного текущего, позволяет алгоритмам эволюционного моделирования «улавливать - общие закономерности ландшафта целевой функции, что дает возможность распределять поиск путем комбинирования решений и отбора ъ наиболее перспективных направлениях [17,28],.
Основные этапы процесса эволюции, на основе которого создаются необходимые схемы генетического поиска, пределены, следующим образом [8,31,54]: 1 Инициализация начальной популяции. Ввести точку отсчета эпох і 0. Инициализировать случайным образом А генотипов особей и сформировать в своей совокупности получили название репродуктивного плана Холланда [106,107] и о из них начальную популяцию V0 = {А: . -., А }. Вычислить приспособленность особей популяции fl — (fx(Ai), -.., /і( 4д)) и среднюю приспособленность по популяции. В технических задачах оптимизации часто вместо понятия «приспособлен-ность» используется целевая функция [31]. Простой репродуктивный план включает две повторяющиеся процедуры, В течение первой из них дополнительные копии некоторых особей, обладающих приспособленностью выше среднего по популяции уровня, добавляются к текущей популяции Vі, в то время как некоторые особи с низкой приспособляемостью элиминируются. Каждая особь получает возможность стать родителем с вероятностью, пропорциональной ее приспособляемости. В течение второй процедуры генетические операторы воздействуют на генотипы потомков, модифицируя наборы аллелей так, чтобы исключить идентичность потомков и родителей. В результате получается новая популяция 7 +1. Процесс итеративно повторяется, генерируя последовательность поколений генотипов [8], Знание состава текущей популяции позволяет определить структуру следующего поколения, не обращаясь к предыдущему. Обобщенным оператором, выполняющим преобразование Vі в 7 , является репродуктивный план т. Модифицируя генотипы генетическими операторами UJI П в рамках возможностей, ограниченных гиперкубом, на котором осуществляется решение задачи комбинаторной оптимизации а, как это сделано в [8], репродуктивный план генерирует новые особи, более приспособленные к окружающей среде Е Обозначив через Iі = №Е{А ) реакцию среды, противостоящей адаптивной системе, в [107] приводится следующее символическое определение репродуктивному плану.
Мажоритарный генетический алгоритм в качестве модели волюции диплоидных популяций
Современная генетика оперирует со следующими понятиями: ген — реально существующая, независимая, комбинирующаяся и расщепляющаяся при скрещивании единица наследственности, самостоятельно наследующийся наследственный фактор. Совокупность генов составляет генотип, тогда как фенотип представляет собой совокупность всех внешних и внутренних признаков. Если рассматривать популяции с одинарным набором хромосом (гаплоидным хромосомным набором), с которыми оперирует простой генетический алгоритм, то можно сделать вывод об эквивалентности понятий «генотип» и «вектор переменных задачи оптимизации» [8,37]. В биологии к гаплоидным организмам относятся бактерии, водоросли и другие простейшие организмы, занимающие низшие ступени эволюционного развития. У организмов, стоящих на более высокой ступени эволюции, в ядрах соматических клеток содержится двойной набор хромосом. В обоих комплектах, унаследованных от каждого из родителей, существуют гомологичные хромосомы, кодирующие одни и те же фенотипические признаки и обладающие одинаковой структурой. Проявление какого-либо признака в фенотипе зависит от отношения доминирования между генами родителей. Не существует единого мнения на данный момент касательно того, как регулируются отношения доминантности/рецессивности между гомологичными генами родительских хромосом. Разработаны различные феноменологические модели, одни из которых предполагают механизм полного доминирования, исключающий активность гена, находящегося в рецессивном состоянии. Другие модели модели допускают, что оба гена могут проявлять активность одновременно, но в разной степени (кодоминирование) [8]. Среди множества преимуществ, полученных в результате использования популяций с диплоидными особями, главным является то, что в отличие от гаплоидных популяций, для которых фенотипическое вырождение почти неизбежно означает и генотипическое вырождение, в диплоидных популяциях фенотипическое вырождение может означать наличие генотипического разнообразия (хотя с малой вероятностью, крайне редко встречающейся в практике моделирования, можно предположить, что одному оптимальному фенотипу могут соответствовать разные генотипы). Для популяции с двойным набором хромосом данное утверждение является необязательным, то есть фенотипическое вырождение популяции, естественно наблюдающееся в состоянии адаптации, не свидетельствует об утрате ею генотипического разнообразия [8,111,112]. Если рассматривать фенотип как результат взаимодействия генотипа с условиями внешней среды [2,71], то в рамках поставленной задачи оптимизации с помощью генетического алгоритма может быть приведено следующее определение фенотипа. Пусть Ш.п — тг-мерное вещественное евклидово пространство; X — множество оптимизации, являющееся компактным подмножеством Еп нулевой меры и достаточно простой структуры; д — целевая функция (вещественная функция, заданная на X). Предполагается, что суть задачи оптимизации при использовании ГА сводится к отысканию вектора х є X, удовлетворяющего равенству. Пусть при решении поставленной задачи оптимизации на некотором шаге эволюции t получена популяция Vі = {Л\, ..., A\}t для корректной работы оператора отбора необходимо наличие отображения представляющего результат экспрессии (чтения) генов гомологичных хромосом и последующего декодирования в возможное решение задачи, заданное в виде вектора х\ Є X. Отвлекаясь от второстепенных факторов, правила экспрессии генов и способ декодирования могут трактоваться как «условия внешней среды». Таким образом, вектор решения задачи оптимизации х\, найденный из (2Л2), может быть определен как фенотип, полученный из взаимодействия генотипа Л\ с заданными условиями «окружающей среды» [8,71].
В соответствии с описанной трактовкой фенотипа в ГА предложена модель эволюции диплоидных популяций, названная мажоритарным генетическим алгоритмом (МГЛ), в котором реализовано полное доминирование [9,10,71,76]. Каждое решение задачи кодируется тремя строками: двумя равноценными гомологичными хромосомами X и У, содержащими полную генетическую информацию о данной особи, гены которых могут быть модифицированы всеми генетическими операторами в процессе эволюции популяции, и одной опорной (фантомной) хромосомой V, содержа Первый аллелъныйщей подавляющее значение в фенотипе особей, элементы которой, носящие название признаков доминантности, не изменятся с момента появления до момента элиминации особи. Две гомологичные и одна опорная хромосома несут генетическую информацию, представленную в двоичном коде.
Для реализации модели доминирования генов правила экспрессии могут быть определены следующим образом: результат экспрессии генов 4 — 4. если выполнено хотя бы одно из равенств 4 = 4 или уу = 4 в противном случае результат экспрессии 4 = 4» если выполнено равенство жу = уу = d\y Для хромосом в двоичном коде правила экспрессии генов могут быть представлены в виде таблицы истинности (таблица 2.1, которая эквивалентна таблице истинности мажоритарного элемента с тремя входами и одним выходом, исходя из чего можно найти аналитическую зависимость между входными параметрами 4- Ху, уу- и значением результата а\і\ 4 = (4 Л 4) V (4 Л уу) V (4 Л уу) . (2.14) ДЛЯ определенных правил экспрессии количество особей, в фенотипе которых проявлен 0 или 1, находится в отношении 1 : 1, что свойственно так же и для простого генетического алгоритма, однако количество особей, у которых в фенотипе проявлен доминантный признак, относится к числу особей, у которых в фенотипе проявлен рецессивный признак, как 3 : 1, что полностью соответствует известным законам расщепления в генетике [2,3,20,22,31,47,52].
Выбор оптимального алгоритма процесса протекания мутации на основе анализа вероятностей апостериорных гипотез
Оператору кроссинговера принадлежит первостепенная роль в формировании нового поколения особей популяции. Используя механизм диал-лельного расщепления, заложенный в основе мажоритарного генетического алгоритма, стало возможным построить принципиально новую схему, состоящую из двух фаз, формирования хромосомного набора потомка из двух хромосомных наборов родительских особей. Основным отличием предлагаемой модели оператора кроссинговера от уже существующих, показанных в [8,110,116], является наличие понятия «пола у особей, участвующих в кроссинговере, количество которых, как н в ПГА, равно двум. После выполнения описанных действий будут полностью определены аллельные гены и признак доминантности некоторого локуса под номером j потомка {d%j l, xlj 1, y\t1)- Они должны быть применены ко всем локусам, что после окончания второй фазы ОК в итоге даст полностью восстановленный хромосомный набор потомка.
Операции, выполняемые на каждой фазе кроссинговера мажоритарного генетического алгоритма, могут быть обобщены и представлены в виде алгоритма, структурная схема которого показана на рисунке 3.5. Рассматриваемый алгоритм начинает работу после выбора двух особей, участвующих в ОК, и состоит из следующих шагов, оформленных в виде блоков. В блоке 1 производится условное разделение особей-участников по «половому» признаку на «мужскую» и «женскую» для дальнейшего правильного восстановления хромосомного набора потомка. После этого в блоке 2 и блоке 3 организуется независимо друг от друга цикл по всем локусам «мужской» и «женской» особей с целью получения родительских гамет. Для каждого локуса родителей в соответствующей гамете сохраняются один из аллельных генов {блок 4 для «женской» и блок 5 для «мужской» особей) и признак доминантности {блок 6 для «женской» и блок 7 для «мужской» особей) этого локуса. Шаги с 2 по 7 определяют первую фазу оператора кроссинговера, ставящей своей задачей получение гамет. В блоке 8 организуется цикл по всем локусам потомка, необходимый для определения переданных от родителей значений аллелей {блок 9) и признака доминантности {блок 10) каждого локуса. Шаги с 8 по 10 определяют вторую фазу оператора кроссинговера, в результате которой формируется полный хромосомный набор потомка. Согласно теореме 1.2 гарантируется рост числа шаблонов в последовательности поколений при соблюдении трех условий: 1) оптимальность шаблона выше средней по популяции; 2) длина шаблона относительно мала; 3) шаблон низкого порядка. Таким образом, значение фактора роста (большее или меньшее 1) определяет, является ли данный шаблон строительным блоком. Когда 7 1» последующие поколения будут содержать увеличивающееся количество строк, принадлежащих шаблону. Новые строки будут создаваться посредством рекомбинации данного строительного блока и других строительных блоков.
Как показано в [54], существуют ситуации, нарушающие сходимость алгоритма к оптимальным точкам. Можно показать ситуации, в которых наблюдается проявление проблемы так называемого ложного оптимума (deception). Способ кодирования и упорядочивания битов внутри строки может направить алгоритм по ложному пути, вызывая сходимость к ложным оптимумам. Для преодоления указанной проблемы в простом генетическом алгоритме были предложены следующие варианты решения: 1) использование предварительной информации для правильного упорядочивания битовых комбинаций внутри строки; 2) использование инверсии; 3) использование оператора равномерного кроссинговера.
Первый вариант предполагает наличие предварительной информации о свойствах оптимизруемой функции, В таком случае кроссинговер с меньшей бы вероятностью разрушал необходимую комбинацию битов, вследствие чего возросло бы значение фактора роста и мог бы быть сформирован необходимый строительный блок, хотя в общем случае требование такой информации является нежелательным и ограничивает спектр приложений алгоритма. Если упорядочивание битов внутри строки при решении определенной задачи является случайным, то выражение для плотности вероятности случайного кодирования группы битов порядка к с определяющей длиной 5 — d в строке длины I, будет иметь следующий вид [54,95].
Инверсия направлена на создание строительного блока, основываясь на предположении, что необходимое сцепление битов может быть найдено одновременно с поиском оптимальных стрингов. Однако вопрос о степени эффективности данного оператора является спорным. Как показали исследования, проведенные в [100] и подтвержденные в [54], инверсия имеет невысокую эффективность: для того, чтобы инверсия обеспечивала сходимость к глобальному экстремуму, вероятность применения этого оператора должна быть очень низкой, но тогда встает вопрос о практической ценности инверсии при одновременном поиске стрингов, представляющих оптимальное решение, и необходимого сцепления битов, так как время эволюции при ее применении значительно возрастает.
Обучение искусственных нейронных сетей прямого распространения с помощью мажоритарного генетического алгоритма
Для сокращения вычислительных затрат перспективным направлением исследований также является использование численно-аналитических моделей [17,19]. Этот подход позволяет сократить вычислительные затраты в структурированных поисковых пространствах. В качестве технологической базы при построении моделей генетических алгоритмов могут быть использованы системы компьютерной алгебры. Системы компьютерной алгебры традиционно делятся на системы общего назначения и специализированные системы. К последним относятся те программные продукты, которые направлены на решение конкретных задач. Системы общего назначения объединяют в себе алгоритмы и методы для решения широкого круга задач различной природы. Примерами наиболее распространенных универсальных систем являются Reduce, MatLab, Maple, Mathematica и Derive. Они имеют в своем составе также библиотеки прикладных программ, состоящие из специализированных пакетов [17].
Каждая из этих систем предоставляет пользователю следующий набор основных возможностей: 1. Язык программирования высокого уровня. 2. Интерактивный и пакетный режим работы. 3. Возможность определения новых функций и создания новых математических объектов. 4. Точные арифметические операции над целыми и рациональными числами, а также с числами с плавающей точкой произвольной точности. 5. Алгебра полиномов и рациональных функций многих переменных. 6. Дифференцирование и интегрирование для элементарных и некоторого класса специальных функций, 7. Символьные матричные операции и методы линейной алгебры. 8. Степенные ряды и ряды Фурье. 9- Решение систем уравнений. Почти при равных возможностях при выборе системы компьютерной алгебры решающим становится удобство написания программ на входном языке конкретной системы. На фоне существующего множества систем, с точки зрения простоты реализации алгоритмов численно-аналитического моделирования, выделяется система компьютерной алгебры Maple фирмы Waterloo Maple Inc. Данная система отличается простотой написания программ на входном языке. Пакет Maple допускает преобразование численно-аналитических выражений, использование численных алгоритмов в решении систем уравнений и т.д. Синтаксис входного языка этой системы в значительной степени аналогичен синтаксису языков Паскаля или Си. Имеются операторы присваивания, понятие вызывающей функции, богатый выбор управляющих структур (if, do, for, while), возможности определения процедур. Допустимы операции с числами в двоичной форме, преобразование различных форм представления числа, возможны операции зменения частей переменных. Совокупность этих возможностей позволяет сделать вывод, что при реализации гибридных систем эффективным является разработка программ, ориентированных на применение этой системы компьютерной алгебры [17].
Для проведения экспериментальных исследований была разработана программа, реализующая простой и мажоритарный генетические алгоритмы. В качестве языка программирования, используемого для построения имитационной модели работы генетических алгоритмов выбран язык сценариев Мар1ег. ввиду хорошо развитых средств, реализующих основные концепции структурного программирования с возможностью интеграции со средствами символьной математики. Существующее в Maple понятие «модуля позволяет реализовать принципы псевдо объектно-ориентированного программирования с помощью механизма производящих процедур [18]. Эта парадигма нашла применение для основного принципа объектно-ориен-тированого программирования — инкапсуляции в двух имитационных моделях,, исходные тексты модулей которых приведены.в приложении Г.
Функцию фабрики объектов-модулей выполняет процедура CreatePopulation, аргументами которой являются размерность решаемой задачи, число особей популяции, вектор минимальных значений параметров задачи оптимизации, вектор максимальных значений.параметров задачи оптимизации, вектор отсчетов, задающий количество разрядов каждого из параметров задачи оптимизации, и процедура оценки степени приспособленности отдельной особи, служащая в качестве функции выживания. Процедура CreatePopulation создает и инициализирует популяцию.
Структурная схема; алгоритма, реализующего эволюционный цикл в процедуре Evolve, показана.на рисунке 4Л, прототип которого был взят из [53]. На.первом шаге алгоритма производится оценка степени приспособленности всех особей популяции, выполняемая в процедуре Evaluate, которая представляет собой цикл по всем особям популяции, присваивающий каждой из них значение /л {Л } как меру ее пригодности или жизне 146
Целью экспериментальных исследований было подтверждение теоретических результатов, полученных в предыдущей главе, к которым следует отнести независимость эффективности алгоритма от способа наследования потомком признака доминантности одного из родителей и бблыиая эффективность мажоритарного генетического алгоритма по сравнению с простым генетическим алгоритмом для мутаций с достаточно большой вероятностью возникновения. Пусть начальный момент рассматриваемого периода эволюции совпал с внезапным изменением рельефа целевой функции- Предполагается также, что предыдущий период был стабильным и настолько длительным, что обе популяции (как гаплоидная ПГА, так и диплоидная МГА) выродились фенотипически вокруг начала координат в пространстве Ш2. Для гаплоидной популяции данное условие означает, что все гены хромосомы в случае использования двоично-десятичного кода равны нулю. Для диплоидной по-пуляции МГА это предположение выполняется, если во всех гомологичных парах генов результаты экспрессии равны нулю.
