Pull to refresh

Comments 28

Познавательно — давно хотел написать бота в Robocode, может теперь займусь.
По теме: может я не замечаю каких-то проблем, зачем устраивать скрещивание, если мы можем сколь угодно долго ждать появления «сверсущества»? Берем особь с нейросетью, даем ей решать задачу, а потом особь тупо делится (или не делится — в зависимости от того, как решила задачу) и мутирует. Немного более долгим будет поиск оптимального решения и многим просто не нравятся нейросети, но алгоритм проще имхо.
Суть в том, что в случае отсутствия селекции используятся одни и теже или схожые генетические последовательности (куски кода) с теми же индексами приспособленности. Случайные мутации, помимо положительного, чаще дают отрицательный прирост к этим индексам, поэтому необходимы, скорее, как рандомизаторы основного процесса эволюции.
А вот скрещивание наиболее приспособленных в популяции особей — более правильный подход, хотя конечно также не застрахованный от появление генетических уродцев.
Всё как в природе. Амебы не эволюционируют.
Амебы не эволюционируют? Именно от простейших (если вы, конечно, не являетесь приверженцем теократической теории появления жизни), размножающихся именно делением появилось то бесчисленное множество видов, существующих сейчас. Скрещивание же ведет к появлению только одного вида, приспособленного к выполнению задачи одним способом(Всякие птицы, которые умеют летать, и т.д.). Если вам интересно решение задачи в принципе — это правильный подход, но если необходимо решить задачу различными способами, то мутации с простым делением приведут к появлению различным методов решения задачи.
Возможно, как компромисс и интереса ради использовать эволюцию целиком, начиная от простейших, занимающихся делением для создания разнообразия видов до совершенствования полученных видов с помощью скрещивания. Это, правда уже гораздо более емкая задача.
Я неверно выразился каюсь. Амебы эволюционируют, несомненно, но крайне медленно. В идеальном варианте, несомненно, нужен комплексный подход, но не у каждого (я имею ввиду супер-компьютеры) хватит мощности для решения задач сложнее определенного класса. Одно дело — квадратное уравнение, и совсем другое — расчет ста мильонов параметров в какой-нибудь модели живой природы.
Медленно — это да, но является ли скорость эволюции для данной задачи такой уж важной величиной?
Среда жизнедеятельности бота сильно ограничена как его собственными способностями(ехать, стрелять, вертеть пушкой), так и внешними факторами. С тем периодом жизни, который есть у бота эволюция будет происходить крайне быстро. Т.о., по-моему мнению, временной фактор здесь можно не рассматривать, даже с учетом скорости появления полезных признаком при случайной мутации.
суть не только в базисе способностей. У бота есть стратегия, последовательность, очередность, вариантность действий. Наконец, каждый конкретный бот, в идеале, способен обучаться во время своей активности. Всё это регламентируется его генетическим алгоритмом. Вариантов, по сути, бесконечное множество, и большинство из них — нежизнеспособны, так что метод последовательного перебора действительно требователен к временнЫм ресурсам.
Поэтому резонно осуществлять этот перебор, основываясь на жизнеспособных вариантах, меняя неэффективные фрагменты кода и сохраняя эффективные. Суть эволюции и селекции, в основном, в этом.
а я был чемпионом университета по robocode. только генетическим алгоритмом там даже не пахло. хотя сейчас думаю заморочился бы.
megaswf.com/serve/102223/ — просто в тему генетических алгоритмов, наглядное представление эволюции машинок. (если кто еще не видел)
сколько часов на это было убито мной и моими приятелями… :)
Оу, я подобное делал на *курсовую*)
только там было подобие клеточного автомата + стек из примитивных функций в качестве генома)
вообщем область очень интересная

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

Я давно вынашиваю идею сборки «биомеха», который будет действовать в соответствии не с жесткими процедурами, а с т.н. «действиями», которые будут представлять из себя нечто вроде макросов, а активироваться определенными паттернами сенсорных сигналов, накапливающихся в буфере памяти, причем определение нужного паттерна будет нечетким, а сами паттерны должны меняться при достаточно долгом повторении одной и той же сенсорики. Так вот: для обсчета «задумчивой» ситуации, когда для определенного содержимого буфера нет определенного паттерна, я намерен применить генетический алгоритм. Не знаю, насколько он будет успешен для подобных задач, но попытка не пытка…
Got an error with sample.Hulk: java.lang.ClassNotFoundException: sample.Environment
Could not load robot: sample.Hulk

:(
После рекомпиляйии появился файлик Environment.class, который вы видимо забыли засунуть в дистрибутив. Положив его вместе с Hulk.class в robots/sample я решил проблему.
Еще один пример использования ГА
www.kongregate.com/games/BryceSummer/walkinator
Кратко: создаете бота с точек, костей и мышц, а программа с помощью ГА находит как двигать мышцами для максимального передвижения.
ИТМО'шоного робота обыгрывает? Нет возможности проверить пока
дописал в апдейт статьи: этот робот просто ссыкущийся щенок по отношению к реальным боевым роботам.
А зачем работать с программой, как с деревом? Иерархичноый вид был добавлен, просто потому что он удобнее для человека. Например, есть не иерархический язык программирования, специально для использования генетическим алгоритмом: evolu.org/
Вы бы ещё прикрепили коды роботов, которые в итоге рождаюься в ходе эволюции. Это было бы интересно
Вы описали как найти локальный минимум, эта задача самая простая. А вот как найти глобальный — вот где вся загвоздка. Необходимо оценивать множество популяций, каждую из которых иногда перетряхивать сильными изменениями — тогда эволюция с большей вероятностью придет к глобальному минимуму функции, а не останется навечно с 50% результатом.
ГА принципиально не может гарантировать глобальный экстремум. Лишь достаточно хороший локальный, среди других локальных.

Т.к. применяется для задач, где прямой перебор пространства решений за разумное время не дает приемлемых результатов.
Я не спорю, что глобальный не найти. Другое дело, что способ найти достаточно хороший локальный в данной статье все-таки не описан, описан просто способ достигнуть ближайшего экстремума при заданных начальных условиях.
Ну да. В частности не способствуют выходу за локальный экстремум запрет на размножение и преждевременное убийство слабых особей.
UFO landed and left these words here
Вот интересно, если задать целевую функцию, которая будет оценивать такие параметры бота как обучаемость, способность предсказывать на основе собственного опыта (предлагая соответствующие задачки), получится ли вывести умный ИИ?
Такая полноценная фитнес-функция уже сама будет ИИ.
Если у вас представление функции в виде дерева, то и скрещивать надо было деревья, например меняться узлами.
Only those users with full accounts are able to leave comments. Log in, please.