» Эволюция в виртуальной машине

Давно-давно, когда у меня появился компьютер типа 80386, я попробовал програмировать на паскале. Через некоторое время я понял, что нужно заняться чем-то более или менее серьезным и у меня появилась идея придумать виртуальный мирок с организмами, которые могли бы в нем эволюционировать. Идея не покидала меня годами, пробовал кое-что и бросал много раз. Пару лет назад я стал программировать на С++, потом на Borland C++, коему верен остаюсь и по сей день.
Так вот, последние полтора года я пытаюсь что-то сварганить. У меня есть небольшое плоское (двумерное) поле, в котором живут несколько десятков объектов, обладающих свойствами, подчас такими банальными, как масса, координаты, время жизни, пол, и двоичной хромосомой, в которой заложены некоторые свойства. Есть истребитель, который время от времени появляется в моем мирке и портит жизнь "жертвам". У него тоже куча свойств и его цель - убивать слабых. Жервы могут разножаться, при этом выполняется кроссинговер и мутация хромосомы. Все напичкано стохастикой, все рандомное. Несмотря на все усилия и искуственные ограничения, процесс заходит в тупик или сваливается в аттрактор (иногда странный).
Так вот, я хочу обзавестись однодумцами, кому это было бы интересно, для обсуждения || новых идей || совместного программирования || просто критиков или все вместе. Никаких денег тут нет, только интерес.
Отвечайте, пишите на мыло, в аську.

Сам я такого никогда не писал, но посмотреть на чужое было бы очень интересно. Может выложишь куда-нибудь свою прогу?

Crazy_Shrike
Тоже хотел написать что-то подобное, но вот только руки никак не доходят.

ЗЫ Тоже хотел бы взглянуть на прогу.

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

Чтобы наччать с нуля мы должны подумать над тем, какая цель существования этих "организмов", и за какими параметрами будем наблюдать мы. Скорее всего цель "организмов" занять как можно большее "пространство", тогда мы должны как-то описать это пространство, его свойства. Начинать нужно с простого, например задать такие характеристики как: двумерная координата, время, несколько типов ресурсов.
В результате своей жизнедеятельности "организмы" должны что-то "выделять" в "пространство" и обмениваться инвормацией, и кроме того нужно задать задать какие-то силы, которые будут перемещать ресурсы и "выделения" "организмов".

Свершилось! Первые вопросы по существу!
Итак, в моей модели есть ограниченное двумерное поле. Об этом я писал. Каждый объект может менять координаты - двигаться. Есть ресурсы - энергия, которая тратится при движении и, скажем, еда, которая увеличивает массу, необходимую при размножении. Количество ресурсов изменяется циклически. Но это все не главное. Главное, должна быть хромосома с шенами, котоые будут отвечать за жизнеспособность. Например, у меня есть идея ввести в хромосому ген, который будет отвечать за продожительность жизни объекта.
Нужно придумать конкретно, чем будут обмениваться объекты и что выделять, согласно предложенному.
Цель.... тут все посложнее. Дело в том, что для эволюции необходимо изменять среду и организмы должны к ней приспосабливаться. Поскольку сама идея эволюции подразумевает бесконечное совершенствование, а не нахождение оптимального организма для данной среды, ее тоже нужно изменять бесконечно... типа того... Вот. Было предложение ввести в хромосому какие-то параметры, которые будут определять поведение. В самой простой абстракции можно представить, например, что организм будет двигаться в соотетствии с состоянием читаемого гена... ну и так далее... Для обеспечения изменчивости реализован кроссинговер - у потомка гены родителей случайно перемещиваются. Также неплохо сделать мутацию - случайное изменение случайного гена.
И самое важное. Вы будете участвовать в программировании?

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

Ну, имхо, не совсем так. Как раз целью эволюции является создание индивидуумов абсолютно независящих от окружающей среды т.н. гомеостаз. Инстинкты - дают независимость от окружающей среды на уровне обобщающем опыт предыдущих поколений. Мозг - уже гораздо более высокий инструмент достижения гомеостаза.

Моделировать эволюцию интересно

А какими параметрами обладает среда обитания?
"Живые организмы -- объекты, которые поддерживают низкий уровень внутренней энтропии за счет увеличения внешней" -- услышано в курилке...

2 beeos

На курилке услышана очень даже правильная фраза. Более того, красивая.
Свойства среды... Тут есть оговорка. У меня роль среды переложена на плечи одного маленького существа (существа, объекты и организмы здесь и далее в кавычках), которое появляется когда популяция превышает определенный предел численности. Он движется случайно и нападает на объекты, попавшие в радиус его видимости. Они могут убегать, тратя при этом энергию. Когда преследуемого догоняют, сравниваются некоторые параметры хищника и жертвы. Логично предположить, что тут выживают те, параметры которого в сумме (значение функции ценности) лучше, чем параметры хищника.

Господа, повторюсь, я занимался только некоторыми опытами и некоторые приблизили меня к пониманию. Мне нужны предложения, потому что моя фантазия ограничена в некоторых рамках, за которые я как раз и хочу выйти, услышав новые мысли. Я хочу начать все с начала, желательно в соавторстве. И не обязательно соавторы должны быть программистами (хотя неплохо бы). Так что, почти от всего, что есть у меня теперь, я могу отказаться, если новые подходы будут логичными.

ЗЫ. Может кто-то что-то знает про устройство Tierra?

Crazy_Shrike
Под свойствами среды я подразумевал несколько иное: если абстракция мира -- матрица, то каждая ячейка не просто поле, в которое может характеризовать местоположение организма, а, грубо говоря, обладающий своими свойствами неодушевленный объект. Соответсвенно, организмы взаимодействуют не только друг с другом и с организмами другого вида (хищниками), но и со средой. Они могут изменять свойства ячейки, у организмов есть свои предпочтения в среде обитания, некоторые организмы не могут жить в определенных ячейках или могут переселяться туда только в вынужденных обстоятельствах.

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

... что то в этом есть. Развейте, пожалуйста, мысль про свойства ячеек... Пример, какой-нить...

ЗЫ. Абстракция мира - матрица. Гы.

Добавлено
Да, чуть не забыл ... Про количество параметров. Это на самом деле основной ограничивающий фактор - количество параметров, медленно все происходит. У меня есть на работе 4-х процессорный Xeon 2.2 GHz, на котором удобно гонять подобные программки, но есть проблема, которая меня выводит из себя и невозвращает обратно - загружается только один процессор! Я тут спрашивал, как, мол, всю мощность использовать - никто понятия не имеет. Обидно, что такая штука и простаивает.

Цитата:

У меня есть на работе 4-х процессорный Xeon 2.2 GHz, на котором удобно гонять подобные программки, но есть проблема, которая меня выводит из себя и невозвращает обратно - загружается только один процессор! Я тут спрашивал, как, мол, всю мощность использовать - никто понятия не имеет. Обидно, что такая штука и простаивает.

посмотри функцию SetProcessAffinityMask

Это че за функия??? Де смотреть-то? =) В Билдере нету....

Crazy_Shrike
Пример такой: есть существо, обладающее определенными параметрами (масса, энергия, etc.) и свойствами, расчитываемыми через параметры (например сила = масса*энергия). Есть свойство ячейки, характеризующее ее тип: 0 - простая ячейка, 1 - ячейка отдает энергию, 2 - ячейка поглощает энергию, 3 - для занятия ячейки необходима определенная сила (для простоты можно зарезервировать диапазон индексов, напр. 31-39 будет означать силу от 10 до 90 (масштаб естественно приблизительный)).

Если проводить аналогии -- третий параметр можно сравнить с горами, первый с лесом а второй -- с водой. Опять же грубо.

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

Цитата:

Это че за функия??? Де смотреть-то? =) В Билдере нету....

http://msdn.microsoft.com .....

2 beeos

Это немного похоже на задачу оптимизации... Подозреваю, что они позанимают самы "удобные" ячейки и будут там торчать до скончания веков. Нужны изменяющиеся факторы среды...

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

2 ssx

М-да... довольно конкретная ссылка. Лучше скажите, это много мороки для не очень опытного программиста?

Crazy_Shrike

Цитата:

Подозреваю, что они позанимают самы "удобные" ячейки и будут там торчать до скончания веков. Нужны изменяющиеся факторы среды...

Если кто и займет ячейки, которые окажутся объективно удобными, будет рано или поздно вытеснен оттуда более сильными особями. Или же наоборот, там и погибнет в одиночестве.
Изменяющиеся факторы среды сделать тоже можно -- каждое существо, "поселившись" в ячейке, оказывает влияние на нее, т.е. например уменьшает фактор барьера, или вычерпывает одну единицу ресурсов, содержащихся в ячейке. Таким образом, получаем среду, которая изменяется в зависимости от существ, которые ее населяют. Идея с хромосомами -- просто супер.
Есть предложение: составить краткое описание каждого объекта в системе с тем, чтобы написать рабочий и, главное, расширяемый вариант программы. А уже потом заняться экспериментированием с параметрами.

Ой, ой!!! Что это??? У Вас текст тоже перекорежило???

Добавлено
Вы программируете?

Это такие первоапрельские шуточки...
Crazy_Shrike
Да. Но это не главное. Грамотно спроектированную и документированную систему может закодировать студентка-третьекурсница...
Или интересуют именно решения конкретных программных задач?

Ага. Все нормально.

Как вы думаете, нужен ли хищник?

Добавлено
Вы второй человек, говорящий про 1-апрельские шуточки. Это что, серьезно???

Начнем с размеров поля...

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

Ага. Хорошо. Давайте делать класс?

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

Да, кстати, про сексуальную активность. Нужно ж какое-то либидо придумать, чтобы гнало друг к другу разнополых созданий... А то засядет в ячейке и пофиг ему будет продолжение рода... Предположим, для размножения нужно чтобы совпали коорднаты потенциальных родителей...

Итак, масса, энергия, пол, время жизни.
Поподробнее про коэффициент выживания и коэф. хищника... я немного не понял...
У Вас есть аська? Или давайте мылом общаться... если не трудно...

По порядку.
Простейший вариант либидо -- число, показывающее, на каком удалении особь будет "замечать" объект для продолжения рода. Можно ввести дополнительный ген, отвечающий за индивидуальные предпочтения в выборе партнера. Т.е. при встрече двух особей будут сравниваться такие показатели, и если их разность лежит в определенном диапазоне, то пара способна произвести потомство. Можно поиграться с этим показателем и заложить в него количество и приблизительное смещение генов будущих детей
Коэффициент выживаемости. Пример такой: есть существо, у которого этот коэффициент равен 0.2 и существо с коэффициентом 0.3. Текущая энергия первого существа - 30, второго - 20. Их жизнеспособность в данных условиях рассчитывается как произведение коэффициента выживаемости на энергию. Нетрудно заметить, что она одинакова. При достижении низкого уровня жизнеспособности, например 5, существо погибает.
Аськой и мылом общаться пока не получится. И потом это будет означать, что тему закроют и приток единомышленников прекратится... их и так не слишком много...


Совсем забыл: коэффициент хищника расчитывает возможность использования себе подобных в качестве источника энергии. это может быть либо просто бит -- если он сброшен, то существо никогда не будет нападать на других живых существ. Либо опять же число, через которое расчитывается вероятность нападения на существ своего вида, чужого вида или склонность исключительно к "природным" источникам энергии.

интересная тема...

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

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

Добавлено
Crazy_Shrike
а по поводу использования нескольких процессоров:
приложение должно многопоточным.
твое именно такое?

2 GreyGendalf

Про биологов - это правильно. Это не проблема. У меня есть друг - профессиональный генетик. Он-то и внес немалую лепту в мои размышления.

Насчет многопоточности.... Как его сделать многопоточным? У меня об этом ровно ноль представлений.

2 beeos

Значит, либидо - это, грубо говоря, радиус видимости потенциального партнера. Ясно.
Что такое смещение генов? Не понял. Если это про скрещивание, то, знаю по опыту, оно должно быть случайным: потомку передается хромосома одного родителя, а потом в нее вставляется кусок случайной длины второго родителя, начиная со случайной точки.
Сразу возникает вопрос: как быть с генами? Будут они неразрывными при кроссинговере, либо будет возможным заменять участок хромосомы без учета локализации генов... Нуна подумать.

Коэффициент выживаемости... Может пока обойдемся простым ограничением времени жизни? А там видно будет. Или убедите меня в обратном.

Цитата:

Коэффициент выживаемости... Может пока обойдемся простым ограничением времени жизни? А там видно будет. Или убедите меня в обратном.

Согласен. Не надо создавать себе трудности, даже для того, чтобы потом их успешно преодолевать... Так что обождем.
А насчет смещения генов -- просто мысли. Для меня наследование -- одно из белых пятен. И действительно хотелось бы узнать (хорошо бы у биологов), как оно должно происходить. Я предположил, что это смещение должно содержать информацию о преобладании генотипа того или иного родителя, т.е. отношение этих чисел у родителей определяет соотношение наследуемых признаков у детей.
Насчет участков хромосом: тоже у билогов узнать...

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

Добавлено
Вопрос по технической части...

В моей старой программе была одна кривая сторона (ну, не одна, конечно)... как мне кажется... У меня был массив объектов, так что популяция ограничивалась этим массивом. У каждого объекта-элемента был признак живой или нет. Это неправильно?

Неправильно. Так получается, что мертвые существа фактически продолжают существовать и не дают популяции развиваться выше некоторого предела. Можно реализовать механизм "разложения", т.е. жизни после смерти, когда существо продолжает занимать клетку и разлагаться, влияя на окружающую среду и живых существ. Но это опять же усложнит систему.
Итог: объекты не должны обладать признаком "живой/мертвый", а фактически уничтожаться и рождаться. Поскольку они "живут" в памяти, а существуют и действуют в заданной матрице, то выделенная для них память должна находиться в соответствии с размерами матрицы. Иными словами, количество существ все равно не может превышать количество доступных клеток. И достаточно выделить им соответствующий, меньший, чем количество клеток, объем. Технически можно это реализовать через соответствующий класс "популяция", основным свойством которого будет являться псевдодинамический массив особей...