Комментарии 28
Если посмотреть на биологические аналоги, при скрещивании происходит обмен генами: блоками порядка 10^3-10^4 «инструкций». То есть, программу нужно делить на большие слабо связанные модули и при скрещивании обмениваться ими.
К сожалению, биологические геномы содержат от 3*10^6 до 10^11 инструкций (нуклеотидных пар).
Поскольку меньше не встречается, видимо есть нижний предел сложности, под которым размножающийся в сложных условиях организм «не заведётся».
Так что апгредим железо для эмулятора, да ищем индусов, которые напишут эти гигантские гигабайты кода.
К сожалению, биологические геномы содержат от 3*10^6 до 10^11 инструкций (нуклеотидных пар).
Поскольку меньше не встречается, видимо есть нижний предел сложности, под которым размножающийся в сложных условиях организм «не заведётся».
Так что апгредим железо для эмулятора, да ищем индусов, которые напишут эти гигантские гигабайты кода.
Искусственная жизнь исследовалась в академических кругах в прошлом веке, сейчас мода прошла.
В начале 90-х меня поразила статья в каком-то науч-поп журнале («Техника-молодёжи», возможно), где описывался симулятор TIERRA Томаса Рея. Якобы он достиг конкуренции между организмами и т.п.
А визуализация «бульона» (по тем годам) была просто шикарной:
tierra.jpg
Попробуйте отыскать старые статьи, хотя возможно в интернет они не перенесены никем.
В начале 90-х меня поразила статья в каком-то науч-поп журнале («Техника-молодёжи», возможно), где описывался симулятор TIERRA Томаса Рея. Якобы он достиг конкуренции между организмами и т.п.
А визуализация «бульона» (по тем годам) была просто шикарной:
tierra.jpg
Попробуйте отыскать старые статьи, хотя возможно в интернет они не перенесены никем.
Хм. Бесспорно интересно. Статья в википедии.
Причем у него даже были паразиты, симбионты… Молодец.
Другой вопрос, что он ученый, которым этим занимался, а я делал программу «just for fun».
Ни на какую академичность не претендую. Просто нравится наблюдать за живностью.
Причем у него даже были паразиты, симбионты… Молодец.
Другой вопрос, что он ученый, которым этим занимался, а я делал программу «just for fun».
Ни на какую академичность не претендую. Просто нравится наблюдать за живностью.
Я бы вынес в геном для начала параметры «конфигурации», а не поведения — дальность и четкость зрения, чуткость обоняния, слуха. Потом бы уже занялся параметрами поведения — реакция на объекты,.
И, кстати, я бы животных сделал не императивными, а событийными. И вместо своего сомнительного байткода запилил туда, скажем, Lua. Или Erlang?.. Вот тут надо подумать, у меня не продумана модель взаимодействия «актормир».
И, кстати, я бы животных сделал не императивными, а событийными. И вместо своего сомнительного байткода запилил туда, скажем, Lua. Или Erlang?.. Вот тут надо подумать, у меня не продумана модель взаимодействия «актормир».
Понятно, что лучше событийная модель лучше. Только она и сложнее насколько? Если какой-нибудь язык запиливать, то автоматическая генерация уже не получится — надо будет, чтобы человек писал.
Я как раз об этом — первоначальные блоки поведения писать самому, а в геноме оставить лишь их активаторы. Скажем, «хищник-травоядное». Позже можно допилить до decision network, частично передаваемой потомству.
«Скрещивать» программы поведения мне кажется не самой интересной идеей. Слишком упрощенной.
Насчет сложности событийной модели — ну, тут как посмотреть. Код поведения станет явно лаконичнее, хотя, конечно, симуляция несколько усложнится. Самая ресурсоемкая задача — выбор получателей события. Это нужно прямо сильно оптимизировать — событий много, получатели определяются исходя из расстояния до источника события…
«Скрещивать» программы поведения мне кажется не самой интересной идеей. Слишком упрощенной.
Насчет сложности событийной модели — ну, тут как посмотреть. Код поведения станет явно лаконичнее, хотя, конечно, симуляция несколько усложнится. Самая ресурсоемкая задача — выбор получателей события. Это нужно прямо сильно оптимизировать — событий много, получатели определяются исходя из расстояния до источника события…
Так для обеспечения разнообразия требуется написание очень большого количества «первоначальных блоков поведения». Я думаю не меньше нескольких десятков.
И здесь выбор все равно весьма ограничен.
В моем же варианте, лучше доработать набор команд для упрощения образования циклов и ветвлений, что позволит живностям проще создавать более сложные алгоритмы.
Суть была в том, чтобы с использованием минимума кода получить максимум фана и веселья.
Хоть идея ваша беспорно правильна, но в моем случае она неприменима.
И здесь выбор все равно весьма ограничен.
В моем же варианте, лучше доработать набор команд для упрощения образования циклов и ветвлений, что позволит живностям проще создавать более сложные алгоритмы.
Суть была в том, чтобы с использованием минимума кода получить максимум фана и веселья.
Хоть идея ваша беспорно правильна, но в моем случае она неприменима.
Было бы интересно добавить к живности характеристики вроде силы и тд. Получится РПГ в вакууме.
Поясните. Не очень понял.
То есть не просто одно животное съело другое? Надо несколько раз укусить?
То есть не просто одно животное съело другое? Надо несколько раз укусить?
Ну да.У одного животного благодаря сильной ДНК больше жизни, у другого- больше силы и т.д.
Конечно, это сильно замедлит расчеты.Но их как раз можно было бы рассчитывать на GPU.
Конечно, это сильно замедлит расчеты.Но их как раз можно было бы рассчитывать на GPU.
А как определить какая ДНК сильнее?
Если строить ДНК не по принципу кода, а набором характеристик, таких как:
1) скорость движения
2) сила атаки
3) количество жизни
4) наличие брони
ну и т.д., то все организмы будут банально стремиться к увеличению всех этих параметров
Если строить ДНК не по принципу кода, а набором характеристик, таких как:
1) скорость движения
2) сила атаки
3) количество жизни
4) наличие брони
ну и т.д., то все организмы будут банально стремиться к увеличению всех этих параметров
Тогда уж заодно по карте разбросать магические предметы.
Например, «Адамантовый меч погибели одноклеточных» => +5 к повреждению организмов с короткой программой.
Например, «Адамантовый меч погибели одноклеточных» => +5 к повреждению организмов с короткой программой.
Мне кажется, результат fitness-функции не должен зависеть напрямую от времени жизни особи. Если вы сделаете размножение через скрещивание, то первыми в приоритете будут те, кто тупо дольше жил, даже если на поле уже существуют более приспособленные особи, так как последние могли просто не успеть съесть достаточно травы. Если разница во времени их рождения будет в несколько сотен тысяч раундов, то средний по показателям организм уже, возможно, никто и не обойдет, и он так и будет размножаться, а новые более приспособленные организмы будут умирать.
В общем, если оставить расчет fitness таким, какой он есть, то предложенный вами второй вариант не подходит, по моему мнению. Только полное убийство всей популяции, через X раундов.
Еще хотелось бы, чтобы вы сделали ограничения по краям (просто камнями застроить, например), а то сейчас они все ходят лишь в одну сторону. С ограничием такие организмы бы упирались в стену и умирали, а чтобы выжить им пришлось находить более сложные алгоритмы перемещения.
В общем, если оставить расчет fitness таким, какой он есть, то предложенный вами второй вариант не подходит, по моему мнению. Только полное убийство всей популяции, через X раундов.
Еще хотелось бы, чтобы вы сделали ограничения по краям (просто камнями застроить, например), а то сейчас они все ходят лишь в одну сторону. С ограничием такие организмы бы упирались в стену и умирали, а чтобы выжить им пришлось находить более сложные алгоритмы перемещения.
Есть смысл примерить на эту задачу язык PUSH (видел реализацию на sf.net), он придуман как раз для таких вещей. И обязательно вставить кроссовер, обычный или двухточечный, организмы смогут обмениваться информацией, сходимость к фитнессу резко повышается. В некоторых вариантах мутации становятся вообще ненужными, т.к. имитируются кроссовером со случайным геномом.
Вообще это задачки для классического ГП. Ваш подход ближе к AIMGP или решению en.wikipedia.org/wiki/Santa_Fe_Trail_problem
А вот кстати один древний проект alife с 3д визуализацией
www.framsticks.com/
куча видео, проект очень старый.
Когда-то вел список таких, интересовался темой, сейчас посмотрел — почти все дохлое.
Вообще тема древняя но по прежнему интересная.
Мне когда-то было интересно прикрутить генетику к вот этому: sodaplay.com/
Там организмы более живенькие.
А если сделать фенотип организма L-системой, то будет и живенько и красиво.
Вообще это задачки для классического ГП. Ваш подход ближе к AIMGP или решению en.wikipedia.org/wiki/Santa_Fe_Trail_problem
А вот кстати один древний проект alife с 3д визуализацией
www.framsticks.com/
куча видео, проект очень старый.
Когда-то вел список таких, интересовался темой, сейчас посмотрел — почти все дохлое.
Вообще тема древняя но по прежнему интересная.
Мне когда-то было интересно прикрутить генетику к вот этому: sodaplay.com/
Там организмы более живенькие.
А если сделать фенотип организма L-системой, то будет и живенько и красиво.
Крайне интересно.
А вот язык PUSH — это круто! Можно по аналогии что-то сделать. (Хочется своё же!)
sourceforge.net/projects/push-evolve/
faculty.hampshire.edu/lspector/push.html
faculty.hampshire.edu/lspector/push3-description.html
А вот язык PUSH — это круто! Можно по аналогии что-то сделать. (Хочется своё же!)
sourceforge.net/projects/push-evolve/
faculty.hampshire.edu/lspector/push.html
faculty.hampshire.edu/lspector/push3-description.html
PUSH достаточно серьезно проработан под эти задачи.
Например такая деталь — в обычном языке случайно сгенерированный цикл приведет к долгому выполнению программы или зависанию.
А в PUSH циклы реализуются по обходу стека.
Вообще достаточно интересный язык, я только первую версию ковырял, сейчас уже третья.
Например такая деталь — в обычном языке случайно сгенерированный цикл приведет к долгому выполнению программы или зависанию.
А в PUSH циклы реализуются по обходу стека.
Вообще достаточно интересный язык, я только первую версию ковырял, сейчас уже третья.
Выбор родителей для скрещивания делается так.
Берется N случайных особей и из них выбирается с лучшим фитнессом.
N по традиции обычно равно 7.
:-)
Скрещивание обычно делается одно- или двух-точечным кроссовером, в данной задаче мне кажется надо использовать оба.
Для одноточечного в ДНК каждого родителя выбирается случайная точка, которая делит ДНК на две части — голову и хвост. У двух потомков голова и хвост комбинируются так, чтобы они были от разных родителей, при этом голова остается головой и хвост остается хвостом.
Для двухточечного выбираются две точки в ДНК, обмен проходит аналогично — середина одного родительского ДНК вставляется в середину другого родителя.
Собственно это типовой вариант для генетического программирования.
Ну и повторюсь, может удастся убрать точечные мутации, заменив их на скрещивание со случайной ДНК.
Но это уже экспериментировать надо.
Если надо сылок накидать — пишите, но основные моменты были исследованы в схемах с tree-based genomes а у вас геном линейный, там есть отличия в параметрах.
Например для генома-дерева кроссовер совсем по другому выглядит и сходится быстрее.
Берется N случайных особей и из них выбирается с лучшим фитнессом.
N по традиции обычно равно 7.
:-)
Скрещивание обычно делается одно- или двух-точечным кроссовером, в данной задаче мне кажется надо использовать оба.
Для одноточечного в ДНК каждого родителя выбирается случайная точка, которая делит ДНК на две части — голову и хвост. У двух потомков голова и хвост комбинируются так, чтобы они были от разных родителей, при этом голова остается головой и хвост остается хвостом.
Для двухточечного выбираются две точки в ДНК, обмен проходит аналогично — середина одного родительского ДНК вставляется в середину другого родителя.
Собственно это типовой вариант для генетического программирования.
Ну и повторюсь, может удастся убрать точечные мутации, заменив их на скрещивание со случайной ДНК.
Но это уже экспериментировать надо.
Если надо сылок накидать — пишите, но основные моменты были исследованы в схемах с tree-based genomes а у вас геном линейный, там есть отличия в параметрах.
Например для генома-дерева кроссовер совсем по другому выглядит и сходится быстрее.
Класс! Ссылки в студию!
Скажите, а вы этим просто интересовались или работаете/работали в данной области? Хватка чувствуется.
Скажите, а вы этим просто интересовались или работаете/работали в данной области? Хватка чувствуется.
Работаю, деньги за это получаю.
Собственно стало скучно просто применять очередной паттерн проектирования в очередной типовой задаче, вот в какой-то момент и мигрировал в эту область.
Ну и ленив я, зачем писать программы, когда программы могут написать все за меня.
:-)
По ссылкам — дальше много буков.
Во первых надо различать GP (генетическое программирование) и GA (генетические алгоритмы).
Ваш случай — GP и это самый интересный вариант.
Сам я его изучал по вот этой книжке.
Стоила на момент выхода очень дорого (по тем временам), а за ней вышли еще три тома по той же цене, поэтому бумажные версии мне дорога как память — экономил на обедах.
:-)
Быстрый поиск нашел ее на здесь
Надеюсь не умрет от хабраэффекта.
Первые 70 страниц можно пропустить.
Но можно и не пропускать.
Книгу весьма рекомендую, автор использует лисп-деревья, но это никак не влияет на читаемость, тем более что кода написанного человеком в книге вообще практически нет, только выращенный и только для примеров.
Но вся механика и все варианты реализации и экспериментов описаны отлично и очень детально.
Включая очень экзотические эксперименты.
Например эксперименты по самозарождению сексуальной эволюции из обрывков программ.
Или сколько процентов реальных патентов полученных роботами превосходят аналоги полученные человеком.
При этом книга совершенно не научпоп.
И относительно мало теории, но много практических рекомендаций, например магическое число 7 ввел именно он, метод половинной инициализации тоже его.
Т.е. для инженера практика, которого не интересует очередное доказательство теоремы, а интересно чтобы работало — самое то.
Я по ней сразу свою реализацию на С накатал с шахматами и балеринами.
Обычно по теоретическим монографиям такое редко получается — вылезают разные грабли, тут же описаны все нюансы и мелочи.
Но там описан только геном в виде дерева.
Т.е. есть набор функций (константы как частный случай) с фиксированным количеством аргументов, результат каждой функциии может быть аргументом другой функции — и так далее.
И кстати с линейным геномом, который более удобен и сегодня более популярен у меня никогда не получалось таких результатов как с деревом, оно более эффективно, тем более что я там тоже кое что допилил от себя.
В каком-то смысле книга уже устарела, но как база — я просто лучше не знаю.
И для многих практических задач ее хватает с головой.
Потом есть такой метод как AIMGP, на его основе делались первые автономные роботы-трейдеры, вот тут автор сделал такую конторку www.tradingsystemlab.com/introgeneticprograms.aspx
Когда она открылась, лицензия на одного клиента стоила емнип 60 килобаксов
Там суть похожа, но геном — это линейная последовательность ассемблерных команд, с рядом ограничений против зацикливания.
Т.е. примерно как у вас реализовано.
Ссылку не дам, искать надо по «Nordin AIMGP formal description», но в открытом доступе чего-то не нашел.
Есть еще такая штука как Grammatical Evolution.
Достаточно привлекательная, ей задается грамматика языка и она по ней строит правильные программы и проверяет их.
Но чего-то она у меня не показала столь хороших результатов как первый вариант, я ее тоже наваял и несколько пожалел о потраченном времени.
Есть в википедии даже.
Ну и есть over9000 модификаций, каждый придумывает свою версию, Cartesian GP (CGP), Stronlty typed GP (STGP), в общем там свои тараканы.
Это что касается собственно эволюции самих особей.
Но есть еще социальное взаимодействие особей — помимо сексуального, используемого GP.
Не все ж программам личной жизнью заниматься, общественная тоже должна быть.
И тут уже начинается вивариум от «меметических алгоритмов» до каких-то совершенно странных метаэвристических изысков.
И туда лучше без критического мышления и без подготовки не лезть, ибо туфты там много.
Хотя вот есть например такое издание как jasss.soc.surrey.ac.uk/JASSS.html специализирующееся на Agent Based Modeling (ABM)
Со своими фреймворками и симуляторами.
Например вас наверное заинтересует вот такая публикация jasss.soc.surrey.ac.uk/14/2/5.html
Названия статей там говорят сами за себя
Nonlinear Dynamics of Crime and Violence in Urban Settings
jasss.soc.surrey.ac.uk/15/1/2.html
Это с псевдокодами симуляции и картинками примерно как у вас.
A Virtual Laboratory for the Study of History and Cultural Dynamics
jasss.soc.surrey.ac.uk/14/4/19.html
Sympathy and Punishment: Evolution of Cooperation in Public Goods Game
jasss.soc.surrey.ac.uk/14/4/20.html
Это почему общество основанное на кооперации не выживает если состоит из классов производителей и воров
Но выживает если появляются менты, наказывающие воров и получающие за это мзду от кооператоров.
:-)
A Computational Model of Worker Protest
jasss.soc.surrey.ac.uk/14/3/1.html
В общем интересный такой журнальчик, после его статей можно свой оккупай начинать.
:-)
Тоже рекомендую.
Это я к тому привел, чтобы вы не думали, что то, что вы написали — просто игрушка.
На похожих игрушках просчитываются многие реальные серьезные вещи.
Собственно стало скучно просто применять очередной паттерн проектирования в очередной типовой задаче, вот в какой-то момент и мигрировал в эту область.
Ну и ленив я, зачем писать программы, когда программы могут написать все за меня.
:-)
По ссылкам — дальше много буков.
Во первых надо различать GP (генетическое программирование) и GA (генетические алгоритмы).
Ваш случай — GP и это самый интересный вариант.
Сам я его изучал по вот этой книжке.
Стоила на момент выхода очень дорого (по тем временам), а за ней вышли еще три тома по той же цене, поэтому бумажные версии мне дорога как память — экономил на обедах.
:-)
Быстрый поиск нашел ее на здесь
Надеюсь не умрет от хабраэффекта.
Первые 70 страниц можно пропустить.
Но можно и не пропускать.
Книгу весьма рекомендую, автор использует лисп-деревья, но это никак не влияет на читаемость, тем более что кода написанного человеком в книге вообще практически нет, только выращенный и только для примеров.
Но вся механика и все варианты реализации и экспериментов описаны отлично и очень детально.
Включая очень экзотические эксперименты.
Например эксперименты по самозарождению сексуальной эволюции из обрывков программ.
Или сколько процентов реальных патентов полученных роботами превосходят аналоги полученные человеком.
При этом книга совершенно не научпоп.
И относительно мало теории, но много практических рекомендаций, например магическое число 7 ввел именно он, метод половинной инициализации тоже его.
Т.е. для инженера практика, которого не интересует очередное доказательство теоремы, а интересно чтобы работало — самое то.
Я по ней сразу свою реализацию на С накатал с шахматами и балеринами.
Обычно по теоретическим монографиям такое редко получается — вылезают разные грабли, тут же описаны все нюансы и мелочи.
Но там описан только геном в виде дерева.
Т.е. есть набор функций (константы как частный случай) с фиксированным количеством аргументов, результат каждой функциии может быть аргументом другой функции — и так далее.
И кстати с линейным геномом, который более удобен и сегодня более популярен у меня никогда не получалось таких результатов как с деревом, оно более эффективно, тем более что я там тоже кое что допилил от себя.
В каком-то смысле книга уже устарела, но как база — я просто лучше не знаю.
И для многих практических задач ее хватает с головой.
Потом есть такой метод как AIMGP, на его основе делались первые автономные роботы-трейдеры, вот тут автор сделал такую конторку www.tradingsystemlab.com/introgeneticprograms.aspx
Когда она открылась, лицензия на одного клиента стоила емнип 60 килобаксов
Там суть похожа, но геном — это линейная последовательность ассемблерных команд, с рядом ограничений против зацикливания.
Т.е. примерно как у вас реализовано.
Ссылку не дам, искать надо по «Nordin AIMGP formal description», но в открытом доступе чего-то не нашел.
Есть еще такая штука как Grammatical Evolution.
Достаточно привлекательная, ей задается грамматика языка и она по ней строит правильные программы и проверяет их.
Но чего-то она у меня не показала столь хороших результатов как первый вариант, я ее тоже наваял и несколько пожалел о потраченном времени.
Есть в википедии даже.
Ну и есть over9000 модификаций, каждый придумывает свою версию, Cartesian GP (CGP), Stronlty typed GP (STGP), в общем там свои тараканы.
Это что касается собственно эволюции самих особей.
Но есть еще социальное взаимодействие особей — помимо сексуального, используемого GP.
Не все ж программам личной жизнью заниматься, общественная тоже должна быть.
И тут уже начинается вивариум от «меметических алгоритмов» до каких-то совершенно странных метаэвристических изысков.
И туда лучше без критического мышления и без подготовки не лезть, ибо туфты там много.
Хотя вот есть например такое издание как jasss.soc.surrey.ac.uk/JASSS.html специализирующееся на Agent Based Modeling (ABM)
Со своими фреймворками и симуляторами.
Например вас наверное заинтересует вот такая публикация jasss.soc.surrey.ac.uk/14/2/5.html
Названия статей там говорят сами за себя
Nonlinear Dynamics of Crime and Violence in Urban Settings
jasss.soc.surrey.ac.uk/15/1/2.html
Это с псевдокодами симуляции и картинками примерно как у вас.
A Virtual Laboratory for the Study of History and Cultural Dynamics
jasss.soc.surrey.ac.uk/14/4/19.html
Sympathy and Punishment: Evolution of Cooperation in Public Goods Game
jasss.soc.surrey.ac.uk/14/4/20.html
Это почему общество основанное на кооперации не выживает если состоит из классов производителей и воров
Но выживает если появляются менты, наказывающие воров и получающие за это мзду от кооператоров.
:-)
A Computational Model of Worker Protest
jasss.soc.surrey.ac.uk/14/3/1.html
В общем интересный такой журнальчик, после его статей можно свой оккупай начинать.
:-)
Тоже рекомендую.
Это я к тому привел, чтобы вы не думали, что то, что вы написали — просто игрушка.
На похожих игрушках просчитываются многие реальные серьезные вещи.
Может быть стоит статейку по этому поводу накатать?
Тем более, что объем комментария уже на пост тянет…
За инфу огромное спасибо. Буду удовлетворять своё любопытство.
Тем более, что объем комментария уже на пост тянет…
За инфу огромное спасибо. Буду удовлетворять своё любопытство.
Статейку писать сложно, у меня тут уже лежит недописанная статейка по искусственным иммунным системам, добавлять еще сверху в очередь задач бессмысленно.
Хроническая нехватка времени, увы.
Я думаю что по всему что я перечисли есть более простые и компактные источники информации, но советовать тут сложно, я учился по тому что привел а другого и не знаю.
Может кто посоветует что попроще.
Вроде в книжках по AI были описания разных типов ГП, но обычно они очень поверхностные и недостаточны для полной реализации.
Хроническая нехватка времени, увы.
Я думаю что по всему что я перечисли есть более простые и компактные источники информации, но советовать тут сложно, я учился по тому что привел а другого и не знаю.
Может кто посоветует что попроще.
Вроде в книжках по AI были описания разных типов ГП, но обычно они очень поверхностные и недостаточны для полной реализации.
Я требую продолжения!
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Evo, часть 2 — о скрещивании