Недавно на хабре проскочил пост, который напомнил мне о такой забавной и довольно интересной вещи, как BoxCar2D (Оригинал, Версия из поста), которую в первый раз я увидел пару лет назад, и которая меня порядком впечатлила. И уже тогда я подметил в ней один фатальный недостаток (вкратце — ее сделал не я), но в тот раз руки так и не дошли до его исправления. И вот теперь я решил это исправить.
Итак, я расчехлил Visual Studio и принялся за дело.
Первым делом я просто повторил функционал BoxCar2D, а именно: фиксированный размер популяции, которая проживает свою жизнь и порождает следующее поколение. Можно было поиграться с тем, как усложняется трасса со временем, что содержит в себе геном и как машинки скрещиваются и мутируют.
Я остановился на таком варианте: каждая машинка обладает своим геномом, который содержит информацию о каждой из 8 вершин и каждом из 4 потенциальных колес. Также отдельный ген отвечает за то, какие потенциальные колеса вырастают у машинки на самом деле.
При скрещивании каждый ген берется случайным образом от одного из родителей, а также с определенной вероятностью может мутировать, получив случайное значение в заданном диапазоне. Особенный в этом плане только ген, определяющий, какие колеса вырастают, а какие нет. В нем мутация заключается в том, что может случайным образом поменяться состояние одного из колес (выросло — не выросло), либо информация о колесах может сдвинуться на бит вправо или влево.
Понаблюдав за тем, что получилось, я пришел к выводу, что это немного скучновато. Естественный отбор тут довольно-таки, простите за каламбур, искуственный.
И тут память услужливо вытащила из широких штанин своих глубин книгу Ричарда Докинза «Слепой часовщик», а точнее – видео, иллюстрирующее опыт по воссозданию естественного отбора для популяции часов (тех самых, которые показывают время).
Вкратце, способ, которым моделируется естественный отбор можно описать так: существует популяция организмов, и через каждый определенный промежуток времени случайным образом выбираются три из них. Из этих троих двое наиболее приспособленных убивают третьего и производят потомка, после чего новая тройка возвращается в популяцию.
Конечно же я моментально ощутил физическую необходимость реализовать именно такой алгоритм.
Что из этого вышло
Итак, произвольным образом создаем популяцию машинок без колес, запускаем в наш мир и запасаемся попкорном.
Пусть первичные прото-машинки будут совсем без колес.
Они начинают свой жизненный путь и в какой-то момент замирают, будучи не способными продвинуться дальше по трассе. Для первых машинок и их недалеких потомков это будет происходить очень быстро. Для всех замерших машинок мы точно знаем их «приспособленность» и периодически производим «естественный отбор» описаным выше способом.
Сильное влияние имеет то, как часто мы проводим отбор. Чем больше машинок доступно для случайно выборки, тем получается честнее, но тем медленнее движется эволюция в целом. Методом научного тыка я выбрал границу в 1/6 популяции. Если количество закончивших свой жизненный путь машинок еще меньше этого значения, отбор не происходит.
Итак, немного результатов. На скриншотах верхний график показывает абсолютный рекорд дистанции и среднее значение по популяции. А нижний — количество машин с разным количеством колес.
На графике количества колес как правило можно наблюдать стремительные переходы между «эрами». Бесколесные машинки в какой-то момент сменяются одноколесными. Тех, в свою очередь, вытесняют двухколесные. Но, поскольку три и более колеса не обязательно эффективнее двух, дальнейшее развитие не так предсказуемо.
Так, например, на этом скриншоте видно, как в какой-то момент количество трехколесных машинок стало стремительно расти и, казалось бы, вот-вот они вытеснят двухколесных. На самом деле третье колесо помогло преодолеть одну очень коварную горку, но довольно скоро появилась и двухколесная машинка, способная на это. Так что в дальнейшем можно наблюдать что-то, похожее на конкуренцию двух видов, приспособленных по-разному, но примерно одинаково хорошо.
Что еще можно исправить/добавить (в порядке возрастания сложности)
- Сделать больше параметров изменяемыми через интерфейс программы. Многие интересные вещи сейчас захардкодены.
- Ограничить количество потомков одной особи. Сейчас машинка, уехавшая дальше всех плодит и плодит потомков, пока ее рекорд не будет побит. Надо усложнить ей жизнь.
- Добавить еще генетической информации. Больше генов! Еще больше!
- Сделать более умный механизм скрещивания генов. Например, как в вышеупомянутом JavaScript-овом симуляторе первые k генов от папы, а следующие n-k – от мамы.
- Интересно будет так же попробовать определить критическую дистанцию между геномами так, чтобы особи, геномы которых сильно отличаются, теряли способность к скрещиванию между собой. Это позволит параллельно эволюционировать нескольким отдельным видам.
- Ввести «поведение» машинок, диктуемое так же генами. Например, снизить скорость на крутом уступе и так далее.
Где все это брать?
Для заинтересовавшихся выкладываю скомпилированную версию и исходный код (вместе с solution для Visual Studio 2012)
Скачай и запусти 1032 KB
Исходники 1868 KB
Надеюсь, дропбокс выдержит.
Релизная сборка у меня тянет популяции из 300 и более особей. Вначале тормозит, пока они все не упадут на землю, а затем все гладко.
Камера двигается правой кнопкой мыши, колесико отвечает за зум.
Кнопками 'a' и 'd' можно соответственно увеличивать и уменьшать скорость симуляции. Полезно вначале до появления первых интересных особей.
Использованные технологии:
C++, Box2D, OpenGL, SDL
Линукс-версия теоретически возможна. Если будет спрос, можно что-то придумать.
Автор: wStranger
