Анализ структуры эволюционной стратегии и генетического алгоритма для обучения нейросети

Введение

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

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

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

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

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

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

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

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

Анализ структуры эволюционного алгоритма

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

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

2.    Генерируется нулевая популяция особей.

3.    Популяция подвергается влиянию сгенерированной среды.

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

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

6.    Генерируется новое поколение путем мутации предков.

7.    В случае если не пройдено нужное количество итераций, повторяются действия с шага 2.

8.    Конец алгоритма.

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

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

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

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

Принцип построения особи при использовании генетического алгоритма

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

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

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

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

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

Адаптация эволюционного алгоритма для использования в нейросети

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

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

2. Учитываются механизмы и критерии успешности, которые должны использоваться в фитнес-функции. Сама фитнес-функция в результате своей работы должна возвращать некоторое значение, которое будет однозначно трактоваться нейросетью. Например, 0 – это полный провал приспособленности у особи, 1 – абсолютный успех. Все остальные значения, лежащие между 0 и 1, – это спектр приспособленности.

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

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

5. Созданное поколение запускается в сгенерированную среду. Сама работа особей может выполняться как в цикле, так и с использованием отдельного потока под каждый объект. Это не принципиально важно и зависит лишь от реализации среды.

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

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

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

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

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

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

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

Например, нужно выработать «идеальную» форму летательного аппарата. Как критерий приспособленности будет использоваться дистанция, на которую созданный летательный аппарат смог пролететь.

Для кодировки летательного аппарата мы можем использовать следующие гены: 2 пары по 2 гена для кодировки тела объекта – вместимость, форма, 2 гена для кодировки структуры крыльев, 2 гена для структуры двигателей. Объективно компонентов особи может быть больше, следовательно, и генов.

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

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

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

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

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

Реализация фитнес-функции

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

Оптимизация затрачиваемой мощности особи

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

Заключение

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