Введение в эволюционные алгоритмы: генетический алгоритм, нейроэволюция

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

Что такое эволюционные алгоритмы?

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

• Генетический алгоритм [1]
• Генетическое программирование[2],
• Эволюционное программирование[3],
• Эволюционные стратегии [4, 5, 6],
• Изучение систем классификаторов[7],
• Алгоритмы нейроэволюции [8].

Генетический алгоритм

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

1. Отбор: особи с лучшей приспособленностью отбираются для воспроизводства.
2. Кроссовер: выбранные особи спариваются и производят потомство.
3. Мутация: потомство подвергается случайным мутациям.
4. Повторить: процесс повторяется до тех пор, пока не будет найдено решение.

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

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

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

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

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

Методы кодирования

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

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

Прямое кодирование

В методах прямого кодирования точная структура искусственной нейронной сети кодируется непосредственно в генотип [11]. Генотип представляет собой представление ANN. В контексте эволюционных искусственных нейронных сетей структура ИНС называется фенотипом. В методах прямого кодирования генотип совпадает с фенотипом. Закодированные данные содержат информацию о количестве нейронов, весовых коэффициентах и ​​типах соединений. Некоторые категории прямого кодирования включают Двоичное кодирование и Графическое кодирование.

Двоичное кодирование

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

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

Кодирование графика

Кодирование графаАлгоритмы кодирования графа представляют структуру искусственной нейронной сети с использованием узлов и соединений графа [11]. Эти алгоритмы включают Кодирование на основе пути и Кодирование на основе узла. Алгоритм кодирования на основе путей кодирует пути от каждого входного нейрона к каждому выходному нейрону. Подход кодирования на основе узлов, который также называют генетическим кодированием [15], использует гены для кодирования необходимой информации для каждого нейрона внутри них. Гены — это структуры данных, которые содержат информацию о нейронах и их связи. Кодирование на основе узлов используется в Нейроэволюции увеличивающих топологий для описания топологии нейронной сети и весов соединений. Это кодирование позволяет избежать проблемы конкуренции, сохраняя записи о вновь созданных узлах и ссылках, что обсуждается далее в разделе NEAT.

Косвенное кодирование

В отличие от прямого кодирования, задающего каждый нейрон и связь фенотипа непосредственно с генотипом, при непрямом кодировании структура фенотипа кодируется и конструируется опосредованно через некоторые правила и инструкции. «Эти правила часто определяют множество соединений одновременно и могут даже применяться рекурсивно» [11]. Примеры косвенного кодирования включают двумерное наращивание и кодирование на основе грамматики.

Генетическое программирование

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

Различия между генетическим программированием и генетическим алгоритмом

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

Есть несколько других ключевых различий между генетическим программированием и генетическими алгоритмами:

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

Эволюционное программирование и эволюционные стратегии

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

Различия между эволюционными стратегиями и эволюционным программированием

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

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

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

Эволюционные искусственные нейронные сети

Эволюционная искусственная нейронная сеть, также называемая Нейро-эволюция, представляет собой категорию методов машинного обучения, в которой используются эволюционные алгоритмы для обучения искусственных нейронных сетей [17]. Более эффективные решения могут быть получены, когда нейронная сеть и Методы эволюционного алгоритма объединены. Искусственная нейронная сеть обеспечивает архитектуру для обучения, тогда как эволюционный алгоритм хорош для задач поиска и оптимизации. Эффективное использование нейронной сети требует разработки оптимальной архитектуры или топологии сети. Обучение нейронной сети включает в себя получение параметров сети, которые минимизируют значение ошибки. Эти параметры включают веса, таксономию, пороги, передаточные функции, количество скрытых слоев и количество нейронов в каждом слое.

Процесс настройки этих параметров занимает много времени и часто сводится к академическим пробам и ошибкам. Целью такого процесса было бы найти сеть, достаточно простую для быстрого обучения и способную обобщать. Для настройки этих параметров можно использовать эволюционные алгоритмы, чтобы найти наилучшие решения. В схеме классификации нейронных сетей эволюционные искусственные нейронные сети обычно относятся к категории подходов к обучению на основе вознаграждения. Это мощные методы, особенно в ситуациях, когда состояние мира не полностью известно, а хорошей теории предметной области не существует. Хорошие примеры таких методов включают Нейро-эволюцию увеличивающих топологий (NEAT) [16] и ее расширенные версии, которые кратко представлены в следующем разделе и более подробно обсуждаются в следующей статье: ЧИСТЫЙ.

Нейроэволюция увеличивающих топологий (алгоритм NEAT)

Нейро-эволюция расширяющихся топологий (NEAT) — это новый алгоритм нейроэволюции, разработанный Стэнли и Мииккулайненом [16], который автоматически «развивает топологию нейронной сети, добавляя ссылки и скрытые узлы через мутация, чтобы соответствовать сложности проблемы». Стэнли и др. также разработал алгоритм нейроэволюции увеличивающих топологий (rtNEAT) в режиме реального времени как расширение метода NEAT, позволяющее модифицировать эволюционирующие агенты в режиме реального времени. Они представили NEAT в реальном времени в стрелялке с машинным обучением под названием NERO.

NERO расшифровывается как Neuro-Evolving Robotic Operatives. Это боевая игра с машинным обучением, разработанная в Digital Media Collaboratory Техасского университета (Остин) [18]. В игре команды агентов тренируются, чтобы улучшить свои боевые навыки, включая стрельбу по мишеням, избегание врагов и преодоление препятствий. После обучения силы соревнуются друг с другом в соревновании без участия ИИ, пока одна команда не наберет наибольшее количество агентов. Обучение агентов осуществляется с помощью набора упражнений, которые пользователи определяют и выполняют перед соревнованием.

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

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

Каждый агент в NERO управляется нейронной сетью, которую можно обучать с помощью различных методов. NEAT используется для обучения агентов на основе нейронных сетей в NERO. Стэнли и др. [18, 19] продемонстрировали, что с помощью NEAT в реальном времени поведение агентов, управляемых нейронной сетью, в NERO может эффективно и надежно развиваться в режиме реального времени.

Д'Сильва и др. [21] представил метод под названием Milestoneing для дальнейшего улучшения метода NEAT в реальном времени. Было указано, что этот метод эффективно сохранял и сохранял полученные знания, которыми в данном случае были ранее сгенерированные и полезные модели поведения агента, в то время как новые модели поведения создавались и развивались. Йонг и др. [22] также усовершенствовал метод NEAT в реальном времени, включив советы пользователей для эффективного управления эволюционным процессом. Этот метод улучшил алгоритм обучения и производительность агентов.

Уайтсон и др. [23] представил новую технику нейроэволюции под названием Feature Selective Neuro-Evolution of Augmenting Topologies (FS-NEAT), которая является расширением метода NEAT. FS-NEAT развивает топологию и веса ИНС и автоматизирует процесс выбора признаков, определяя соответствующий набор входных данных для нейронной сети. Авторы представили эксперименты для сравнения FS-NEAT с обычным методом NEAT в Robot Auto Racing Simulator (RARS).

Симулятор автогонок роботов (RARS) был разработан М. Э. Тиминым в 1995 году и стал тестовой площадкой и соревновательной платформой на основе Java для программистов и специалистов по искусственному интеллекту. Результаты показали, что FS-NEAT работал лучше, чем NEAT, когда некоторые из доступных входных данных были нерелевантными или избыточными. Количество входных данных и размер нейронной сети также были меньше при использовании FS-NEAT по сравнению с обычным NEAT.

Специальная версия NEAT под названием Content-generating Neuro-Evolution of Augmenting Topologies (cgNEAT) используется для автоматической генерации игрового контента в игре Галактическая гонка вооружений, которая задуман как исследовательский эксперимент [24]. Galactic Arms Race — многопользовательский онлайн-шутер, в котором игроки пилотируют космические корабли и сражаются с врагами. Игровой контент постоянно развивается в зависимости от предпочтений игроков, создавая уникальный контент, включая новые варианты оружия. Это исследование эволюционного алгоритма NEAT и его расширенных версий доказало, что можно автоматически изменять игровой контент и поведение агента во время выполнения. Это снизило стоимость создания контента и сделало игру более интересной для игроков.

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

Заключение

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

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

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

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

Для ссылок и других статей посетите страницу статьи по адресу: https://brainyloop.com/introduction-to-evolutionary-algorithms-genetic-algorithm-neuro-evolution/