Математическое моделирование процессов генетического поиска для повышения качества обучения нейронных сетей прямого распространения тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Воронкин, Роман Александрович

• Воронкин, Роман Александрович
• кандидат технических наук
• 2004

Оглавление диссертации кандидат технических наук Воронкин, Роман Александрович

ВВЕДЕНИЕ

1 ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПРОЦЕССА ОБУЧЕНИЯ НЕЙ

РОННЫХ СЕТЕЙ С ПОМОЩЬЮ ГЕНЕТИЧЕСКИХ АЛГО

РИТМОВ

1.1 Анализ методов обучения нейронных сетей прямого распространения

1.2 Генетические алгоритмы в качестве метода эволюционного моделирования при решении задач оптимизации.

1.3 Влияние отбора и проблема сходимости генетических алгоритмов к глобальным экстремумам целевых функций.

Выводы.

2 ПУТИ ПОВЫШЕНИЯ СКОРОСТИ И УСТОЙЧИВОСТИ РА

БОТЫ ГЕНЕТИЧЕСКИХ АЛГОРИТМОВ

2.1 Метод увеличения скорости генетического кодирования линейным кодом

2.2 Мажоритарный генетический алгоритм в качестве модели эволюции диплоидных популяций.

Выводы.

3 АНАЛИЗ СВОЙСТВ ГЕНЕТИЧЕСКИХ ОПЕРАТОРОВ МАЖОРИТАРНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА

3.1 Оператор кроссинговера в мажоритарном генетическом алгоритме

3.1.1 Математическая модель оператора кроссинговера мажоритарного генетического алгоритма.

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

3.2 Оператор мутации в мажоритарном генетическом алгоритме

3.2.1 Математическая модель оператора мутации мажоритарного генетического алгоритма

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

3.2.3 Выбор оптимального алгоритма процесса протекания мутации на основе анализа вероятностей апостериорных гипотез

3.2.4 Математическая модель-процесса несвободной мутации в мажоритарном генетическом алгоритме.

Выводы.

4 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ МАЖОРИТАРНОГО ГЕНЕТИЧЕСКОГО АЛГОРИТМА

4.1 Характеристики популяции, определяющие меру сходимости эволюционного процесса.

4.2 Решение задач глобальной оптимизации с помощью мажоритарного генетического алгоритма.

4.3 Обучение искусственных нейронных сетей прямого распространения с помощью мажоритарного генетического алгоритма

Выводы.

Введение диссертации (часть автореферата) на тему «Математическое моделирование процессов генетического поиска для повышения качества обучения нейронных сетей прямого распространения»

Задачи синтеза и анализа любой природы относятся к классу комбинаторных и, в большинстве случаев, имеют не одно, а множество решений различной значимости. Для решения таких задач разработано множество методов, способов и алгоритмов. Ядром всех комбинаторных алгоритмов являются операции полного, или сокращенного перебора подмножеств решений, но суть комбинаторного перебора в различных алгоритмах проявляется по-разному. Для поиска лучшего решения можно осуществлять направленный, случайный и направленно-случайный перебор всевозможных значений параметров задачи. Генетические алгоритмы (ТА) сейчас —это мощный механизм поиска оптимальных решений в задачах науки, техники, производства [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].

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

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

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

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

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

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

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

1. Выполнение анализа использования базовых структур генетического поиска при обучении нейронных сетей прямого распространения.

2. Разработка метода кодирования/декодирования генетической информации для минимизации временных затрат на обработку двоичных данных.

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

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

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

6. Обучение нейронных сетей прямого распространения с помощью разработанного генетического алгоритма.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Разработан генетический алгоритм с диплоидным способом кодирования генетической информации на основе построенной в работе модели доминирования генов, в котором упрощены правила экспрессии и снижен объем требуемого ресурса памяти для хранения всех особей популяции на 25 %.

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

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

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

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

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

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

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

На защиту выносятся следующие основные положения:

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

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

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

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

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

Апробация работы. Основные результаты докладывались на 48 научно-методической конференции преподавателей и студентов «Университетская наука—региону» (Ставрополь, 2003), на V Международной научно-практической конференции «Информационная безопасность» (Таганрог, 2003), на Междисциплинарной (медицина, биология, радиоэлектроника, химия, математика, информатика, педагогика .) конференции с международным участием «Новые биокибернетические технологии 21 века для диагностики и лечения заболеваний человека» (Петрозаводск, 2003), на IV Международной научной конференции «Интеллектуальные и многопроцессорные системы — 2003» (п. Дивноморское, 2003), где доклад по теме диссертационных исследований был отмечен премией как один из лучших докладов, на III Санкт-Петербургской межрегиональной конференции «Информационная безопасность регионов России (ИБРР—2003)» (Санкт-Петербург, 2003).

Публикации. По теме диссертации опубликовано 17 печатных работ из них 7 научных статей. Практическая значимость работы подтверждена 3 актами реализации.

Автор глубоко благодарен научному руководителю кандидату технических наук, доценту Александру Федоровичу Чипиге за постановку задачи и постоянное внимание к работе. t

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Воронкин, Роман Александрович

Выводы

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

2. Разработана имитационная модель работы простого и можоритарно-го генетических алгоритмов, в качестве языка реализации выбран язык сценариев Maple. Определены показатели для сравнительного анализа эффективности простого и мажоритарного генетических алгоритмов.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

3. Разработан генетический алгоритм, являющийся моделью эволюции диплоидных популяций, для которого правила экспрессии генов построены по мажоритарному принципу, что позволяет упростить его аппаратную и программную реализацию. Из-за специфичных правил экспрессии генов, не имеющих аналогов в существующих методах генетического поиска, разработанный алгоритм получил название мажоритарного генетического алгоритма. Для разработанного ГА произведена оценка необходимого объема памяти для хранения генофонда популяции, которая показала, что требуемый ресурс памяти по сравнению с существующими аналогами сокращен на 25%.

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

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

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

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

Разработанные в результате диссертационных исследований математические модели и алгоритмы поиска глобальных экстремумов при решении задач адаптации на базе генетических алгоритмов могут быть использованы при решении экономических и технических задач, в которых требуется нахождение глобального экстремума целевой функции, к которым, например, относятся задачи обучения нейронных сетей. Результаты работы внедрены на ОАО «Электротехнический завод „Энергомера"», ЗАО «Энергомодуль» и в учебном процессе на кафедре защиты информации СевероКавказского государственного технического университета при изучении дисциплины «Проблемно ориентированные программные комплексы».

Список литературы диссертационного исследования кандидат технических наук Воронкин, Роман Александрович, 2004 год

1. Абилов Ю. А., Алиев Р. А., Насиров И.М. Генетический алгоритм с групповым выбором и направленной мутацией // Известия РАН. Теория и системы управления. № 5, 1997.

2. Айла Ф. Введение в популяционную и эволюционную генетику. М.: Мир, 1984.

3. Алиханян А. И. и др. Общая генетика. М.: Мир, 1985.

4. Батищев Д. И. Генетические алгоритмы решения экстремальных задач. 1995.

5. Беркинблит М. Б. Нейронные сети. М.: МИРОС, 1993.

6. Божич В. И., Лебедев О. Б., Шницер Ю. JI. Разработка генетического алгоритма обучения нейронных сетей//Перспективные информационные технологии и интеллектуальные системы. Таганрог: Изд-во ТРТУ. № 1(5), 2001.

7. Вагин В.Н. Дедукция и обобщение в системах принятия решений. М.: Наука, 1988.

8. Вороновский Г. К. и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности/Г. К. Вороновский, К. В. Махотило, С. Н. Петрашев, С. А. Сергеев. Харьков: ОСНОВА, 1997.

9. Воронкин Р. А. Моделирование процесса несвободной мутации в мажоритарном генетическом алгоритме//Интеллектуальные и многопроцессорные системы — 2003/Материалы Международной научной конференции. Т. 1. Таганрог: Изд-во ТРТУ, 2003. С. 315-318.

10. Галкина В. А. Дискретная математика: комбинаторная оптимизация на графах. М.: Гелиос АРВ, 2003.

11. Галушкин А. И. Теория нейронных сетей. Кн. 1: Учеб. пособие для вузов/Общая ред. А. И. Галушкина. М.: ИПРЖР, 2000.

12. Галушкин А. И. Многослойные системы распознавания образов. М,: МИЭМ, 1970.

13. Ф. Гилл, У. Мюррей, М. Райт. Практическая оптимизация: пер. с англ. М.: Мир, 1985.

14. Гладков В. А., Зинченко JI. А., Курейчик В. В., Курейчик В. М., Лебедев Б. К., Нужнов Е. В., Сорокин С. Н. Методы генетического поиска: Научное издание/Под редакцией В.М. Курейчика. Таганрог: Изд-во ТРТУ, 2002.

15. Дьяконов В. Мар1е7: учебный курс. СПб.: Питер, 2002.

16. Зинченко JI.A. Алгоритмы численно-аналитического моделирования и средства программной поддержки САПР электронных устройств. Таганрог, Изд-во ТРТУ, 1999.

17. Дубинин Н. П. Новое в современной генетике. М.: Наука, 1986, 322 с.

18. Игнатов В. А. Теория информации и передачи сигналов.: Учебник для ВУЗов гражданской авиации. М.: Советское радио, 1979.

19. Инге-Вечтомо С. Г. Введение в молекулярную генетику. М.:Мир, 1982.

20. Жиглявский А. А., Жилинскас А. Г. Методы поиска глобального экс-тремума.М.: Наука, 1991.

21. Жиглявский А. А. Математическая теория глобального случайного поиска. Л.: Изд-во ЛГУ, 1991.

22. Калан Р. Основные концепции нейронных сетей.: Пер. с англ. М.: Издательский дом «Вильяме», 2001.

23. Колосов Г. Е. Об одной задаче управления численностью популяции//Известия РАН. Теории и системы управления № 2, 1995.

24. Корнеев В. В., Гареев А. Ф. и др. Базы данных. Интеллектуальная информация. М.: Нолидж, 2000.

25. Круглов В. В., Борисов В. В. Искусственные нейронные сети. Теория и практика. М.: Горячая линия — Телеком, 2001.

26. Курейчик В. В. Эволюционные, синергетические и гомеостатиче-ские методы принятия решений: Монография. Таганрог: Изд-во ТР-ТУ, 2001.

27. Курейчик В. М. Генетические алгоритмы. Монография. Таганрог: Изд-во ТРТУ, 1998.

28. Курейчик В.М. Генетические алгоритмы и их применение. Таганрог: Изд-во ТРТУ, издание второе, дополненное, 2002.

29. Курейчик В.М. Генетический алгоритм разбиения графа//Известия РАН. Теории и системы управления. № 4, 1999.

30. Курейчик В. М. Генетические алгоритмы. Состояние. Проблемы. Перспективы//Известия РАН. Теории и системы управления. № 1, 1999. С. 144-160.

31. Курейчик В. М. Генетические алгоримы. Обзор и состояние. Новости искусственного интеллекта, 1998. № 3. С. 14-64.

32. Курейчик В.М. Методы генетического поиска: Учебное пособие. Часть 1. Таганрог: Издательство ТРТУ, 1997.

33. Курейчик В.М., Зинченко Л. А. Эволюционное моделирование с динамическим изменением параметров. Труды VII национальной конференции по искусственному интеллекту. М.: Физматлит, 2000.

34. Лебедев Б. К. Формирование гомологичных структур хромосом при кодировании списков//Перспективные информационные технологии и интеллектуальные системы. Таганрог: Изд-во ТРТУ. № 1(5), 2001.

35. Лима-де-Фариа А. Эволюция без отбора: Автоэволюция формы и функции. М.: 1991.

36. Медведев B.C., Потомкин В. Г. Нейронные сети. MATLAB 6/Под общ. ред. к.т.н. В. Г. Потемкина. М.: ДИАЛОГ-МИФИ, 2002.

37. Моррис У. Наука об управлении. Байесовский подход. Перевод с англ. О. В Редькиной. Под редакцией И.Ф. Шахнова. М.: Мир, 1971.

38. Мишулина OA., Лабадинская А.А. Щербинина М.В. Лабораторный практикум по курсу «Введение в теорию нейронных сетей». М.: МИФИ, 2000.

39. Омату С., Халид М., Юсоф Р. Нейроуправление и его приложения: М.: ИПРЖРБ, 2000.

40. Осовский С. Нейронные сети для обработки информации/Пер. с польского И.Д. Рудинского. М.: Финансы и Статистика, 2002.

41. Осыка А. В. Экспериментальные исследования зависимости скорости сходимости генетического алгоритма от его параметров//Известия РАН. Теория и системы управления. № 5, 1997.

42. Петров Д. Ф. Генетика с основами селекции. М.: Высшая школа, 1971.

43. Попов Э. В. и др. Статические и динамические экспертные системы. М.: Финансы и статистика, 1996.

44. Поспелов Г. С. Искусственный интеллект — основа новой информационной технологии. М.: Наука, 1988.

45. Поспелов Д. А. Моделирование рассуждений. М.: Ридио и связь, 1989.

46. Поспелов Д. А. Семиотические модели: успехи и перспективы//Кибернетика. № 6, 1976.

47. Приходченко Н.Н., Шкурат Т.П. Основы генетики человека. Ростов-на-Дону: Феникс, 1997.

48. Рик Л. Риоло. Естественный отбор в мире битов. Режим доступа http: //algolist .manual. ru/ai/ga/riolo. zip. 10.02.2004.

49. A. H. Скурихин. Генетические алгоритмы / Новости искусственного интеллекта. №4, 1995.

50. Теория передачи сигналов.: (Учеб. для электротехн. ин-тов связи спец. 0702, 0703, 0708 / А.Г. Зюко, М.В. Назаров, Л.М. Фина)-2-е изд., перераб. и доп. М.: Радио и Связь, 1986.

51. Уоссермен Ф., Нейрокомпьютерная техника. М.: Мир, 1992.

52. Червяков Н.И. Отказоустойчивые непозиционные процессоры.// Управляющие системы и машины. Киев: Наукова думака № 3, 1998.

53. Червяков Н. И., Бережной В. В., Гончарова Е. Н., Калмыков И. А. Локализация и исправление арифметических ошибок в модулярных нейрокомпьютерах//Нейрокомпьютеры: разработка, применение № 7, 2003.

54. Червяков Н. И., Бережной В. В., Оленев А. А., Калмыков И. А. Минимизация избыточного кода системы остаточных классов с одним контрольным основанием. — Киев «Наукова думка»— Электронное моделирование, 1999, № 1.

55. Червяков Н. И., Галкина В. А., Стрекалов Ю.А., Лавриненко С. В. Архитектура адаптивной параллельно-конвейерной нейронной сети для коррекции ошибок в модулярных нейрокомпьютерных системах// Нейрокомпьютеры: разработка, применение № 6, 2003.

56. Червяков Н. И., Сахнюк П. А., Шапошников А. В., Макоха А. Н. Архитектура нейрокомпьютеров, функционирующих в системе остаточных классов//Нейрокомпьютеры: разработка, применение № 5, 2003.

57. Червяков Н. И., Сахнюк П. А., Шапошников А. В., Лавриненко С. В. Применение нейронных сетей Хопфилда для коррекции ошибок в модулярных нейрокомпьютерах//Нейрокомпьютеры: разработка, применение № 11, 2002.

58. Червяков Н. И., Сахнюк П. А., Шапошников А. В., Галкина В. А. Нейронный цифровой фильтр с модулярной обработкой данных//Нейрокомпьютеры: разработка, применение № 11, 2002.

59. Червяков Н. И;, Сахнюк П. А., Шапошников А. В., Макоха А. Н. Задачи, решаемые нейроускорителями в конечных кольцах и полях//Нейрокомпьютеры: разработка, применение № 6, 2003.

60. Червяков Н. И., Сивоплясов Д. В., Горденко Д. В. Нейронная сеть для преобразования полиадического кода в код системы остаточных классов//Нейрокомпьютеры: разработка, применение № 10-11, 2003.

61. Червяков Н. И., Сивоплясов Д. В., Ткачук Р. В. Нейронная сеть для вычисления позиционной характеристики ранга числа, представленного в системе остаточных классов//Нейрокомпьютеры: разработка, применение № 10-11, 2003.

62. Червяков Н. И., Шапошников А. В., Сахнюк П. А. Нейронный алгоритм расширения оснований модулярного кода//Нейрокомпьютеры: разработка, применение № 11, 2002.

63. Червяков Н. И., Шапошников А. В., Сахнюк П. А. Модель и структура нейронной сети для реализации арифметики в системы остаточных классов//Нейрокомпьютеры: разработка, приненение, 2001, № 10.

64. Черноруцкий И. Г. Методы оптимизации и принятия решений: Учебное пособие. СПб.: Изд-во Лань, 2001.

65. Чипига А. Ф., Воронкин Р. А. Особенности генетического алгоритма, базирующегося на явлении расщепления признаков//Тезисы XVI конференции ФРВИ РФ, 28-29 февраля 2002 г.

66. Чипига А.Ф., Воронкин Р. А. Введение в генетический алгоритм с расщеплением признаков. Ученые записки физико-математического факультета Ставропольского государственного университета. — Ставрополь: Изд-во СГУ, 2002. С. 105-109.

67. Чипига А. Ф., Воронкин Р. А. Математические модели алгоритмов несвободной мутации в мажоритарном генетическом алгоритме//Известия высших учебных заведений Северо-Кавказский регион.

68. Математическое моделирование и компьютерные технологии. Технические науки. Специальный выпуск. Новочеркасск, 2003. С. 29-33.

69. Чипига А. Ф., Воронкин Р. А. Увеличение скорости кодирования линейным кодом путем применил кодеров, использующих радиальные базисные нейронные сети//Вестник Ставропольского государственного университета. Выпуск 34, 2003. С. 17-23.

70. Backer J.E. "Adaptive selection methods for genetic algorithms," Proc. of the 1st International Coference on Genetic Algorithm and Their Applications, Hilisdale, NJ, P. 101-111, 1985.

71. Battiti R. First and second order methods for learning: Between sleepest descent and Newton's method.//Neural Computation. 1992 Vol. 4. № 2. P. 141-166.

72. Bremermann H.J., Rogson M., Salaff, S., Search by Evolution in Biophysics and Cybernetic Systems. M. Maxfield, A. Callahan, and L. J. Fo-gel, Eds. Washington DC: Spartan Books, P. 157-167, 1965.

73. Bremermann H.J., Rogson M., Salaff S., Global Properties of Evolution Processes in Natural Automata and Useful Simulations. H. Pattee, E. A. Edisack, L. Feiri, and A. B. Callahan, Eds, Washington DC: Spartan Book, P. 3-41, 1966.

74. Elben A. E., Aarts, В. H., and Van Нее, K.M., "Global convergence of genetic algorithms: An Infinite Markov chain analysis," Parallel Problem

75. Solving from Nature, H.-P. Schwefel and R. Manner, Eds. Heldberg, Berlin: Springer-Varlang, P. 4-12, 1991.

76. Fogel D. B. An Introduction to Simulated Evolutionary Optimization. IEEE Transactions on Neural Networks, vol. 5, no. 1, Jan. 1994, p.3-14.

77. Fletcher R., Reeves C.M. Function minimization by conjugate gradients//Computer Journal, 1964. Vol. 7. P. 149-154.

78. Fogel, D. В., "Asymptotic convergence properties of genetic algorithms and evolutionary programming: Analisys and experiments," Cybernetics and Systems, 1994.

79. Fogel L.J. Autonomous Automata, Industrial Research, 4, 14-19, 1962.

80. Fogel. D. B. Evolutionary Computation. New York. NY: IEEE Press, 1995.

81. Fogel D. B. On the Philosophical Difference between Evolutionary Algorithms and Genetic Algorithms. Proceeding of the Second Annual Conference on Evolutionary Programming, ed. by D. B. Fogel and W.A. At-mar. Palo Alto, 1993, CA: Morgan Kauffman.

82. Fogel L.J., Owens A.J., Walsh M.J. Artifical Intelligence throught Sumulated Evolution, New York, NY: John Wiley, 1966.

83. Fogel D.B. The Evolution of Intelligent Desigion Making in Gaming. Cybernetica and Systems, 1991, vol. 22, p. 223-226.

84. Frantz D. R., Non-linearities in genetic adaptive search, PhD thesis, University of Michigan, 1972.

85. Fraser A. S., "Simulation of genetic systems," Jurnal of Theoretical Biology, vol. 2, P. 329-346, 1962.

86. Fraser A. S., "The evolution of purposive behavior in Purposive Systems," H. von Foerster, J.D. White, L.J. Peterson, and J.K. Russel, Eds. Washington, DC: Spartan Books, P. 15-23, 1968.

87. Fridberg R. M. A Learning Machine, IBM Journal of Research and Development, 3, 282-287, 1958.

88. Grefenstette J.J. "Optimization of control parameters for genetic algorithm", IEEE Trans. Sys., Man and Cybern., Vol 16, N. I, P. 122-128, 1986.

89. Goldberg D. E., Lingle R., "Allele, loci, an traveling salesman problem", Proc. of an International Conferention on Genetic Algorithms and Their Applications, P.154-159,1985.

90. Goldberg D. E., "Sizing populations for serial and parallel genetic algo-rithros," Proc. of the 3rd International conference on Genetic Algorithms and Their Applications, San Mateo, CA, P. 70-79, June 1989.

91. Goldberg D. EM Genetic algorithms in search, optimization and machine learning. Addison Wesley, 1989.

92. De Jong K. A. An analysis of the behavior of a class of genetic adaptive systems, PhD thesis, University of Michigan, 1975.

93. Hagan M. Т., Menhaj M. Training feedforward networks with the Mar-quardt algorithm //IEEE Transactions on Neural Networks, 1994. Vol. 5. № 6. P. 989-993.

94. Handbook of Genetic Algorithms, Edited by Lawrence Davis. USA: Van Nostrand Reinhold, New York, 1991.

95. Holland J. H., "Adaptive plans optimal for payoff-only environments," Proc. of the 2nd Hawaii Int. Conf. on System Sciences, P. 917-920, 1969.

96. Holland J.H. Adaptation in natural and artificial systems: an introduc-tionary analisis with application to biology, control, and artifical intelligence 1st MIT Press ed„ 1992.

97. Holland J. H. Outline of the Logical Theory of Adaptive Systems, J. ACM, 9, 297-314, 1962.

98. Holland J. H. Nonlinear Environments Permitting Efficient adaptation, Computer and Information Sci., New York, NY, Academic Press, 1967.

99. Hollstein R. B. Artifical genetic adaptation in computer control systems (Doctoral dissertation, 1971, University of Michigan) Dissertation Abstracts International.32.(3), 1510B.

100. Klepikov V.B., Sergeev S.A., Mahotilo K.V. Modification of Holland's reproductive plan for diploid populations//In: Artifical Neural Nets and Genetic Algorithms (Eds. D. Pearson et al). — Springer Verlag, 1995. P. 337-339.

101. Klepikov V. B. et al. Diploidy-based Genetic Algorithm in Nonstation-ary Environment.//В кн.: Проблемы автоматизированного электронного привода. Теория и практика. (Под ред. В. Б. Клепикова и др.). — Харьков: Основа, 1995-сс. 108-110.

102. Koza J.R. Genetic Programming: on the Programming of Computers my Means of Natural Selection, Cambridge, MA: MIT Press, 1992.

103. Koza J.R. Genetic Programming III, CA, 1999.

104. Michalewicz Z., Genetic Algorithms + Data Structures = Evolutionary Programs. Springer-Verlag, Al Series, New York, 1992.

105. NG K. P., Wong К. C. A New Diploid Scheme and Dominance Change Mechanism for Non — Stationary Function Optimization//Procs of6th Int. Conf. on Genetic Algorithms. — Morgan Kaufmann, 1995. — P. 159-166.

106. William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery Numerical Recipes in C. Cambridge, MA: MIT Press, 2002.

107. Recehberg I. Cybernetic Solution path of an Experimental problem, Royal Aircraft Establishment, Library Translation No. 1122, 1965.

108. Reed J., Toombs R., and Barricelli, N. A., "Simulation of biological evolution and machine learning," Journal of Theoretical Biology, vol. 17, P. 319-342, 1967.

109. Rudolph G., "Convergence properties of canonical genetic algorithms," IEEE Trans, on Neural Networks, Vol. 5, N. I, 1994.

110. Practical Handbook of Genetic Algorithms. Editor L. Chambers, Washington, USA, CRC Press, 1999.

111. H-P. Schwefel. Kybernetische Evolution als Strategie der Experi-mentellen Forschung in der Stromungstechnik, Diploma Thesis, Technical Univercity of Berlin, Germany, 1965.

112. Spears W. The Role of Mutation and Recombination in Evolutionary Algorithms. George Mason University, Virginia, 1998.

113. Xiaofeng Q., Palmieti. F., "Theoretical analysis of evolutionary algorithms an infinite population size in continuous space. Parts 1,11", IEEE Trans, on Neural Networks, Vol.5, No.l, 102-130, 1994.

114. Zadeh L. A. Fussy Logic and Soft Computing: Issues, Contentions and Perspective. Proc. Of IIZUKA 94, Third Int. Conf. Of Fuzzy Logic, Neural Nets and Soft Computing, 1-2, Iizuka, Japan, 1994.