BC/NW 2017 № 1 (30):10.3

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

Курников Д.М., Петров С.А.

Генетический алгоритм (genetic algorithm) – это алгоритм, используемый в нейронных сетях для решения задач оптимизации и моделирования путём стохастического подбора и комбинации искомых параметров с использованием механизмов, похожих на биологическую эволюцию. Он состоит из следующих этапов:

1.           создание начальной популяции;

2.           выполнение операций скрещивания (селекция);

3.           мутация и формирование новой, следующей популяции.

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

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

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

·   выбор способа представления решения;

·   разработка операторов случайных изменений;

·   определение способов «выживания» решений;

·   создание начальной популяции альтернативных решений.

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

1.           генерируем начальную популяцию из N хромосом;

2.           измеряем для каждой хромосомы ее пригодность;

3.           отбираем пару хромосом-родителей с помощью способов отбора;

4.           совершаем рекомбинацию двух родителей, производя двух потомков;

5.           проводим мутацию потомков;

6.           повторяем шаги 3-5, пока не будет сгенерировано новое поколение популяции, содержащее N хромосом;

7.           Повторяем шаги 2-6 до окончания процесса.

 

Схема выполнения этапов генетического алгоритма приведена на рисунке 1.

Рисунок 1. Схема выполнения генетического алгоритма

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

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

Эффективность алгоритма зависит от параметров (размер начальной популяции, тип отбора, уровень мутации и др.), подбираемых опытным путём.

У генетических алгоритмов имеются следующие особенности:

·          данные алгоритмы оперируют множеством параметров в закодированной форме;

·          данные алгоритмы ведут поиск множеств-популяций точек, а не отдельную точку;

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

·          в данных алгоритмах правила принятия решения носят вероятностный, а не детерминированный характер.

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

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

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

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

-       генетические алгоритмы просты в реализации при поиске в пространстве решений большой размерности и независимы от его структуры;

-       генетические алгоритмы инвариантны относительно вида целевой функции (функции приспособленности).

Из недостатков можно выделить следующие:

-       ввиду эвристичности генетических алгоритмов нет гарантии наличия критериев оптимальности полученного решения;

-       относительно высокая вычислительная трудоемкость. Она обуславливается оценкой как перспектив, так и ретроспектив для процесса моделирования эволюции;

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

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

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

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

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

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

Рисунок 2. Вид популяции из нейронных сетей

Как видно из рисунка 2, для фиксированной топологии нейронной сети генетическая информация полностью содержится в значениях синаптических (от сл. «синапс») весов (W) и смещений (B). Таким образом, вектор (W, B) рассматривается как хромосома. Блок-схема применения генетического алгоритма при обучении сети приведена на рисунке 3.

 

Рисунок 3. Схема применения генетического алгоритма к обучению нейронной сети

 

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

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

Стоит отметить, что генетический алгоритм является эвристическим, т.е. он не является гарантированно точным или оптимальным. Однако применение данного алгоритма считается достаточным для решения определённых задач. В основе генетического алгоритма лежит практический подход, поэтому он часто подвергается критике. Так известный исследователь алгоритмов Стивен С. Скиена, профессор кафедры вычислительной техники университета Стоуни—Брук и лауреат премии института IEEE, писал, что не находил такой задачи, для решения которой генетические алгоритмы были бы самым подходящим и оптимальным средством.

 

Список использованной литературы

1.                Хайкин С. Нейронные сети: полный курс, 2¬e издание.:Пер. с анrл. – М. Издательский дом "Вильямс", 2006.

2.                Курейчик В.М. Генетические алгоритмы. Обзор и состояние // Новости искусственного интеллекта. — 1998.

3.                Стивен С. Скиена Алгоритмы. Руководство по разработке – СПб: БХВ-Петербург, 2011