Нейроэволюция дополняющих топологий

NeuroEvolution of Augmenting Topologies ( NEAT ) — генетический алгоритм (GA) для генерации развивающихся искусственных нейронных сетей ( метод нейроэволюции ), разработанный Кеннетом Стэнли и Ристо Мииккулайненом в 2002 году в Техасском университете в Остине . Он изменяет как весовые параметры, так и структуру сетей, пытаясь найти баланс между пригодностью разработанных решений и их разнообразием. Он основан на применении трех ключевых методов: отслеживании генов с помощью исторических маркеров, позволяющих осуществлять скрещивание топологий, применении видообразования (эволюции видов) для сохранения инноваций и постепенной разработке топологий из простых исходных структур («усложнение»).

Производительность

В простых задачах управления алгоритм NEAT часто создает эффективные сети быстрее, чем другие современные нейроэволюционные методы и методы обучения с подкреплением . ^[1]^[2]

Алгоритм

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

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

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

Конкурирующие конвенции

Проблема конкурирующих соглашений возникает, когда существует более одного способа представления информации в фенотипе. Например, если геном содержит нейроны A , B и C и представлен [ABC], если этот геном скрещен с идентичным геномом (с точки зрения функциональности), но упорядоченное скрещивание [CBA] приведет к появлению потомков, в которых отсутствует информация ( [ABA] или [CBC]), фактически в этом примере потеряна 1/3 информации. NEAT решает эту проблему, отслеживая историю генов с помощью глобального числа инноваций, которое увеличивается по мере добавления новых генов. При добавлении нового гена глобальный номер инновации увеличивается и присваивается этому гену. Таким образом, чем выше число, тем позже был добавлен ген. Для конкретного поколения, если идентичная мутация возникает более чем в одном геноме, им обоим присваивается один и тот же номер, однако в дальнейшем число мутаций останется неизменным на неопределенный срок.

Эти инновационные цифры позволяют NEAT сопоставлять гены, которые можно скрещивать друг с другом. ^[1]

Выполнение

Оригинальная реализация Кена Стэнли опубликована под лицензией GPL . Он интегрируется с Guile GNU , интерпретатором схем . Эта реализация NEAT считается общепринятой базовой отправной точкой для реализации алгоритма NEAT.

Расширения

rtNEAT

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

Первым применением rtNEAT стала видеоигра под названием Neuro-Evolving Robotic Operatives или NERO. На первом этапе игры отдельные игроки размещают роботов в «песочнице» и обучают их определенной тактической доктрине. После обучения группы роботов второй этап игры позволяет игрокам сразить своих роботов с роботами, обученными каким-либо другим игроком, чтобы увидеть, насколько хорошо их режимы обучения подготовили их роботов к битве.

Поэтапная обрезка

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

ГиперНИАТ

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

cgNEAT

NEAT, генерирующий контент (cgNEAT), разрабатывает индивидуальный контент видеоигр на основе предпочтений пользователя. Первой видеоигрой, в которой реализован cgNEAT, является Galactic Arms Race , космический шутер, в котором уникальное оружие системы частиц разрабатывается на основе статистики использования игроками. ^[3] Каждое оружие системы частиц в игре контролируется развитым CPPN , аналогично технике эволюции в программе интерактивного искусства NEAT Particles .

одNEAT

odNEAT — это онлайн-децентрализованная версия NEAT, предназначенная для систем с несколькими роботами. ^[4] odNEAT выполняется на самих роботах во время выполнения задач для непрерывной оптимизации параметров и топологии контроллеров на базе искусственных нейронных сетей. Таким образом, роботы, выполняющие odNEAT, имеют потенциал адаптироваться к меняющимся условиям и научиться новому поведению при выполнении своих задач. Онлайн-эволюционный процесс реализуется в соответствии с моделью физически распределенного острова. Каждый робот оптимизирует внутреннюю совокупность решений-кандидатов (внутриостровная вариация), а два или более роботов обмениваются решениями-кандидатами при встрече (миграция между островами). Таким образом, каждый робот потенциально самодостаточен, и эволюционный процесс извлекает выгоду из обмена контроллерами между несколькими роботами для более быстрого синтеза эффективных контроллеров.

См. также

Эволюционное приобретение нейронных топологий

Ссылки

^ Перейти обратно: ^а ^б Кеннет О. Стэнли и Ристо Мииккулайнен (2002). «Развитие нейронных сетей посредством расширения топологий». Эволюционные вычисления 10 (2): 99–127.
^ Мэтью Э. Тейлор, Шимон Уайтсон и Питер Стоун (2006). «Сравнение методов эволюционного и временного различия в области обучения с подкреплением». GECCO 2006: Материалы конференции по генетическим и эволюционным вычислениям.
^ Эрин Дж. Гастингс, Ратан К. Гуха и Кеннет О. Стэнли (2009). «Автоматическое создание контента в видеоигре «Галактическая гонка вооружений». Транзакции IEEE по вычислительному интеллекту и искусственному интеллекту в играх, том 4, номер 1, страницы 245–263, Нью-Йорк: IEEE Press, 2009.
^ Сильва, Фернандо; Урбано, Пауло; Коррейя, Луис; Кристенсен, Андерс Люне (15 сентября 2015 г.). «odNEAT: алгоритм децентрализованной онлайн-эволюции роботизированных контроллеров». Эволюционные вычисления . 23 (3): 421–449. дои : 10.1162/evco_a_00141 . hdl : 10071/10504 . ПМИД 25478664 . S2CID 20815070 .

Библиография

Кеннет О. Стэнли и Ристо Мииккулайнен (2002). «Развитие нейронных сетей посредством расширения топологий» (PDF) . Эволюционные вычисления . 10 (2): 99–127. CiteSeerX 10.1.1.638.3910 . дои : 10.1162/106365602320169811 . ПМИД 12180173 . S2CID 498161 .

Кеннет О. Стэнли и Ристо Мииккулайнен (2002). «Эффективное обучение с подкреплением посредством развития топологий нейронных сетей» (PDF) . Материалы конференции по генетическим и эволюционным вычислениям (GECCO-2002) .

Кеннет О. Стэнли; Бобби Д. Брайант и Ристо Мииккулайнен (2003). «Развитие адаптивных нейронных сетей с адаптивными синапсами и без них» (PDF) . Материалы Конгресса IEEE 2003 г. по эволюционным вычислениям (CEC-2003) .

Колин Грин (2004). «Поэтапный поиск с помощью NEAT: чередование комплексификации и упрощения» . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
Кеннет О. Стэнли; Райан Корнелиус; Ристо Мииккулайнен; Томас Д'Сильва и Ализа Голд (2005). «Обучение в реальном времени в видеоигре NERO» (PDF) . Материалы конференции по искусственному интеллекту и интерактивным цифровым развлечениям (AIIDE 2005) . Демонстрационные статьи.

Мэтью Э. Тейлор; Шимон Уайтсон и Питер Стоун (2006). «Сравнение методов эволюционного и временного различия в области обучения с подкреплением» (PDF) . GECCO 2006: Материалы конференции по генетическим и эволюционным вычислениям .

Шимон Уайтсон и Дэниел Уайтсон (2007). «Стохастическая оптимизация выбора столкновений в физике высоких энергий» (PDF) . IAAI 2007: Материалы девятнадцатой ежегодной конференции по инновационным применениям искусственного интеллекта . arXiv : hep-ex/0607012 . Бибкод : 2006hep.ex....7012W . Архивировано из оригинала (PDF) 28 октября 2015 г.

Реализации

Стэнли Оригинальные версии mtNEAT . и rtNEAT для C++
ECJ , JNEAT , NEAT 4J , ANJI для Java
SharpNEAT для C#
MultiNEAT ( MultiNEAT на Wayback Machine (архивировано 15 мая 2021 г.)) и mtNEAT для C++ и Python.
аккуратный Python для Python
NeuralFit (не точная реализация) и аккуратный Python для Python
Encog для Java и C#
горох для Питона
RubyNEAT для Руби
Neatjs для Javascript
Neataptic для Javascript (не точная реализация)
Neat-Ex для эликсира
EvolutionNet для C++
goNEAT для Go (язык программирования)

Внешние ссылки

Домашняя страница NEAT ( Домашняя страница NEAT на Wayback Machine (архивировано 5 декабря 2023 г.))
«Группа исследования эволюционной сложности в UCF» - нынешняя исследовательская группа Кена Стэнли.
NERO: Нейроразвивающиеся роботы-оперативники – пример применения rtNEAT
GAR: Галактическая гонка вооружений – пример применения cgNEAT
«PicBreeder.org» — совместное онлайн-искусство, создаваемое CPPN, развивалось вместе с NEAT.
«EndlessForms.com» — 3D-версия Picbreeder, в которой вы в интерактивном режиме разрабатываете 3D-объекты, закодированные с помощью CPPN и развивающиеся с помощью NEAT.
Блог BEACON: Что такое нейроэволюция?
MarI/O — Machine Learning for Video Games , видео на YouTube , демонстрирующее реализацию обучения NEAT для игры в Super Mario World.
«GekkoQuant.com» — серия визуальных руководств по NEAT, включая решение классической задачи балансировки полюсов с использованием NEAT в R.
«Искусственный интеллект изучает уровень Марио всего за 34 попытки. NEAT объяснил с помощью программы MarI/O.

[stanley2002-1] Перейти обратно: ^а ^б Кеннет О. Стэнли и Ристо Мииккулайнен (2002). «Развитие нейронных сетей посредством расширения топологий». Эволюционные вычисления 10 (2): 99–127.

[taylor2006-2] Мэтью Э. Тейлор, Шимон Уайтсон и Питер Стоун (2006). «Сравнение методов эволюционного и временного различия в области обучения с подкреплением». GECCO 2006: Материалы конференции по генетическим и эволюционным вычислениям.

[hastings2009-3] Эрин Дж. Гастингс, Ратан К. Гуха и Кеннет О. Стэнли (2009). «Автоматическое создание контента в видеоигре «Галактическая гонка вооружений». Транзакции IEEE по вычислительному интеллекту и искусственному интеллекту в играх, том 4, номер 1, страницы 245–263, Нью-Йорк: IEEE Press, 2009.

[4] Сильва, Фернандо; Урбано, Пауло; Коррейя, Луис; Кристенсен, Андерс Люне (15 сентября 2015 г.). «odNEAT: алгоритм децентрализованной онлайн-эволюции роботизированных контроллеров». Эволюционные вычисления . 23 (3): 421–449. дои : 10.1162/evco_a_00141 . hdl : 10071/10504 . ПМИД 25478664 . S2CID 20815070 .

[1]

[2]

[3]

[4]