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

[Petrify]

Познавательно — давно хотел написать бота в Robocode, может теперь займусь.
По теме: может я не замечаю каких-то проблем, зачем устраивать скрещивание, если мы можем сколь угодно долго ждать появления «сверсущества»? Берем особь с нейросетью, даем ей решать задачу, а потом особь тупо делится (или не делится — в зависимости от того, как решила задачу) и мутирует. Немного более долгим будет поиск оптимального решения и многим просто не нравятся нейросети, но алгоритм проще имхо.

[FrimInc]

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

[Petrify]

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

[FrimInc]

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

[Petrify]

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

[FrimInc]

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

[man_without_face]

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

[Pozadi]

megaswf.com/serve/102223/ — просто в тему генетических алгоритмов, наглядное представление эволюции машинок. (если кто еще не видел)

[andrewsh]

сколько часов на это было убито мной и моими приятелями… :)

[IeN]

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

[mechmind]

Интересно… Никогда бы не подумал, что подобранные с помощью ГА программы смогут показать конкурентноспособность так быстро :) Качаю.

[twdragon]

Очень познавательно — сойдет в качестве туториала по генетическим алгоритмам для достаточно продвинутого начинающего =). Кстати, реализовать «скрещивание» вполне возможно, по-моему, еще и на основе VMT, но это относится скорее к моему любимому С++.

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

[mechmind]

Got an error with sample.Hulk: java.lang.ClassNotFoundException: sample.Environment
Could not load robot: sample.Hulk

:(

[mechmind]

После рекомпиляйии появился файлик Environment.class, который вы видимо забыли засунуть в дистрибутив. Положив его вместе с Hulk.class в robots/sample я решил проблему.

[kefiijrw]

виноват. архив исправил

[nrg3]

Еще один пример использования ГА
www.kongregate.com/games/BryceSummer/walkinator
Кратко: создаете бота с точек, костей и мышц, а программа с помощью ГА находит как двигать мышцами для максимального передвижения.

[Xlab]

ИТМО'шоного робота обыгрывает? Нет возможности проверить пока

[kefiijrw]

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

[Iskin]

А зачем работать с программой, как с деревом? Иерархичноый вид был добавлен, просто потому что он удобнее для человека. Например, есть не иерархический язык программирования, специально для использования генетическим алгоритмом: evolu.org/

[mikhanoid]

Вы бы ещё прикрепили коды роботов, которые в итоге рождаюься в ходе эволюции. Это было бы интересно

[gleb_kudr]

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

[thecoder]

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

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

[gleb_kudr]

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

[thecoder]

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

[Biga]

Вот интересно, если задать целевую функцию, которая будет оценивать такие параметры бота как обучаемость, способность предсказывать на основе собственного опыта (предлагая соответствующие задачки), получится ли вывести умный ИИ?

[VenomBlood]

Такая полноценная фитнес-функция уже сама будет ИИ.

[MaximKat]

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