Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 26
Интересно, на сколько на основе этой работы можно организовать эволюцию кода. Например, есть разные языки программирования (царство), есть программы различного применения (тип), есть программы, решающие примерно одни и те же задачи (класс). Берем все это, и по описанным выше алгоритмам сталкиваем в одной «среде обитания». Следим за размножением, эволюцией и получаем на выходе более совершенные модифицированные решения.
А можно
- Ссылку на проект
- Анимацию процесса где-нибудь посмотреть
Хм, чисто по технической стороне замечания:
1. Почему OpenGL? Рисование простенькое, можно было бы простой GUI библиотечкой обойтись и контролы прикрутить, чтобы всеми параметрами управлять.
2. По C++ разные недочеты — не используете списки инициализации, используется постфиксную форму инкремента на итераторе, кодинг стайл без дополнительных пробелов между математчиескими операциями ИМХО плохо читается, поля классов никак особенно не именуются, скачет регистр (то caml case, то Pascal), используете лямбды, но не используете auto, а напрашивается. А еще странно выглядит «bool ok=0;». C++ же, можно и true написать.
3. Ну и скриншотов не хватает, мне кажется.
1. Почему OpenGL? Рисование простенькое, можно было бы простой GUI библиотечкой обойтись и контролы прикрутить, чтобы всеми параметрами управлять.
2. По C++ разные недочеты — не используете списки инициализации, используется постфиксную форму инкремента на итераторе, кодинг стайл без дополнительных пробелов между математчиескими операциями ИМХО плохо читается, поля классов никак особенно не именуются, скачет регистр (то caml case, то Pascal), используете лямбды, но не используете auto, а напрашивается. А еще странно выглядит «bool ok=0;». C++ же, можно и true написать.
3. Ну и скриншотов не хватает, мне кажется.
А еще странно выглядит «bool ok=0;». C++ же, можно и true написать.
#define true 0?
Туда же до кучи можно добавить полнейший хаос в «архитектуре»: взять хотя бы метод Draw, который внезапно не только рисует, но еще и передвигает, размножает, спасает от хищников (не пойми откуда в нем вообще взявшихся).
OpenGL я изучаю давно и уже очень привык к нему. Что касается кода, я его писал несколько лет назад и многого еще не знал. А отсутствие скриншотов — это мой косяк.
Кажется вы читали
Восход Эндимиона
Делал много подобных поделий. Это было забавно, но называть это «доказательством эволюции живых организмов» я не стал.
При столкновении двух особей, они будут умирать, и в случайных координатах будут появляться их дети (от 1 до 3).
Какое-то странное правило. А если особи не столкнутся, они что — живут вечно?
inline Code_bio childcode(Code_bio c1, Code_bio c2) { //СКРЕЩИВАНИЕ Code_bio c; c.maxltime=(c1.maxltime+c2.maxltime)/2; c.minspeed=(c1.minspeed+c2.minspeed)/2; c.maxspeed=(c1.maxspeed+c2.maxspeed)/2; c.maxturn=(c1.maxturn+c2.maxturn)/2; //МУТАЦИЯ c.maxltime+=c.maxltime/100*((rand()%(maxltime_mut*2+1))-maxltime_mut); c.maxspeed+=c.maxspeed/100*((rand()%(maxspeed_mut*2+1))-maxspeed_mut); c.minspeed+=c.minspeed/100*((rand()%(minspeed_mut*2+1))-minspeed_mut); c.maxturn+=c.maxturn/100*(rand()%(maxturn_mut*2+1)-maxturn_mut); return c; }
Вы меня простите, конечно, но с генетикой тут нет ничего общего. Это не генетический алгоритм.
Суть генетических алгоритмов в том, что генетическая информация хранится в родителях в виде битовой строчки. При скрещивании и мутировании тоже используется эта битовая строчка, безо всякого знания о ее внутреннем устройстве. Только потом получившийся код «парсится на гены» (т.е. разбирается на составляющие его поля) и используется при создании нового организма.
Откуда такая информация про определение генетических алгоритмов?
Мне всегда казалось, что основной их особенностью является оператор скрещивания, остальное непринципиально.
(заметим, что в реальных организмах скрещивание происходит как раз на уровне генов, а не нуклеотидов)
Мне всегда казалось, что основной их особенностью является оператор скрещивания, остальное непринципиально.
(заметим, что в реальных организмах скрещивание происходит как раз на уровне генов, а не нуклеотидов)
Откуда такая информация про определение генетических алгоритмов?
ru.wikipedia.org/wiki/%D0%93%D0%B5%D0%BD%D0%B5%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC
Я когда-то довольно плотно игрался с генетическими алгоритмами. Они отлично работают в задачах, где куча параметров, неочевидно влияющих на результат (и где тупой перебор работал бы веками).
Мне всегда казалось, что основной их особенностью является оператор скрещивания, остальное непринципиально.
(заметим, что в реальных организмах скрещивание происходит как раз на уровне генов, а не нуклеотидов)
Скрещивание происходит вообще на уровне хромосом: ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%BE%D1%81%D1%81%D0%B8%D0%BD%D0%B3%D0%BE%D0%B2%D0%B5%D1%80
Впрочем, все это лирика.
У вас в программе нет ни скрещивания как такового, ни, строго говоря, мутаций. Вместо скрещивания у вас усреднение признаков, вместо мутаций — случайные изменения признаков в пределах каких-то лимитов. То есть это — не генетический алгоритм, а нечто совсем другое. Зато у вас есть вещи, не относящиеся к генетике напрямую: беготня особей по полю — это всего лишь очень хитрый способ построения оценочной функции.
Ок, определение из вики:
Где тут говорится про представление?
«Скрещивание на уровне генов» — в том смысле, что перемещаются как единое целое гены, а не нуклеотиды.
(и вы, видимо, перепутали меня с автором статьи)
Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания»
Где тут говорится про представление?
«Скрещивание на уровне генов» — в том смысле, что перемещаются как единое целое гены, а не нуклеотиды.
(и вы, видимо, перепутали меня с автором статьи)
(и вы, видимо, перепутали меня с автором статьи)
Да, перепутал, прошу прощения.
Где тут говорится про представление?
Нигде. Какие, по-вашему, из этого следует сделать выводы?
«Скрещивание на уровне генов» — в том смысле, что перемещаются как единое целое гены, а не нуклеотиды.
Для компьютерной симуляции это малосущественно и в большинстве случаев такими тонкостями можно пренебречь.
Где тут говорится про представление?
Нигде.
Из этого можно сделать вывод, что утверждение
Суть генетических алгоритмов в том, что генетическая информация хранится в родителях в виде битовой строчки. При скрещивании и мутировании тоже используется эта битовая строчка, безо всякого знания о ее внутреннем устройстве.
неверно.
Ценю вашу тягу к расстановке точек над Ё. Открываем священную книгу Тору на странице 1432 в очередной раз википедию, смотрим в текст:
В общем случае физическое представление генома (битовые строчки, байты, текст и т.п.) для работы генетического алгоритма не важно. Тем не менее, именно с битовых строчек генетические алгоритмы начались (см. работы Джона Холларда, которые я сам, впрочем, не читал).
Genetic algorithms use linear binary representations. The most standard one is an array of bits. Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size. This facilitates simple crossover operation. Variable length representations were also explored in Genetic algorithms, but crossover implementation is more complex in this case.
В общем случае физическое представление генома (битовые строчки, байты, текст и т.п.) для работы генетического алгоритма не важно. Тем не менее, именно с битовых строчек генетические алгоритмы начались (см. работы Джона Холларда, которые я сам, впрочем, не читал).
Т.е. crossover проще всего делать на битовых строках одинаковой длины, но можно и иначе.
Почему принципиально скрещивание без знания внутреннего устройства?
(в реальных организмах внутреннее устройство в виде деления на гены «известно»)
И почему случайные изменения параметров — не мутации?
Почему принципиально скрещивание без знания внутреннего устройства?
(в реальных организмах внутреннее устройство в виде деления на гены «известно»)
И почему случайные изменения параметров — не мутации?
Почему принципиально скрещивание без знания внутреннего устройства?
Потому что тогда у нас собственно генетический алгоритм полностью изолирован от конкретных данных. Для «доказательства эволюции» — самый правильный подход.
Впрочем, это не так уж и принципиально. Просто универсальнее.
(в реальных организмах внутреннее устройство в виде деления на гены «известно»)
С некоторой натяжкой да. ЕМНИП, в местах, где возможен кроссинговер, есть довольно широкие «буферные зоны», не содержащие генов.
В компьютерной симуляции важны основные принципы (скрещивание, мутации, отбор). Многие присущие реальным организмам вещи (такие, как кроссинговер с учетом границ генов) в компьютерной симуляции малосущественны, т. к. ведут к увеличению времени работы или объемов потребляемой памяти, но при этом мало сказываются на конечном результате. Скажем, кроссинговер «посреди живого гена» по сути своей мало отличается от мутации в этом гене (а если ген у родителей одинаков, то вообще никак не проявится). Но для учета границ генов их придется как-то обозначать (+расход памяти), или вычислять (+расход времени), или завязывать всю реализацию под конкретное представление генов (потеря универсальности).
И почему случайные изменения параметров — не мутации?
В нашем конкретном случае на то есть несколько причин:
1. Это не совсем случайная мутация, а постепенное «гуляние» параметров. В реальном генетическом алгоритме одной случайной мутацией можно кардинально изменить ген, а в некоторых реализациях — вообще чуть ли не весь генотип сразу. Например, пропуск бита при копировании приведет к тому, что все гены, расположенные после мутации, изменятся. Здесь же все изменения постепенные.
2. Вероятность мутирования достаточно низка (в генетических алгоритмах задается отдельным параметром). Вероятность получить нежизнеспособный организм (в симуляции — неконкурентный) в результате мутации — весьма высока. Но можно получить и организм кардинально более «приспособленный». Смысл введения мутаций как раз в том, чтобы дать популяции возможность выйти из локального минимума (т. е. не дать популяции выродиться раньше времени). Здесь же «мутации», по сути, изменяют организм достаточно плавно, но при этом по всем параметрам сразу, поэтому нет смысла от них ждать каких-то «эволюционных скачков».
Ну и общее замечание по реализации: в генетическом алгоритме у потомка будет набор родительских генов (минус мутации, которые редкость). Здесь же у потомка весь генотип, по всем генам, всегда отличается от генотипа обоих родителей. То есть по сути — ничего общего с генетическими алгоритмами предложенная нам программа не имеет. Получился своеобразный поиск экстремума сложной функции методом случайных шагов.
интересно, но почему хищники и нехищники — это 2 разных класса. пусть они наследуют 1 класс, а способности вроде поедать, догонять, убегать реализовывались бы интерфейсами, учитывая массу, дальность зрения и наличие зубов, к примеру, мне кажется, так ближе к реальности. и тогда было бы интересно посмотреть, кто выживет — сильный хищник или быстрый нехищник)
А было бы интеренсо написать эдакий манйрафт для роботов. Где сервер раз в тик опрашивал бы «животных» по http json для унификации, а добаление новых животных бы свелось к живому добавлению параметров клиента животного в конфиг в сервер «мира»
Было это все давно, и на момент написания кода я еще очень плохо разбирался в наследовании, хотя то, что вы предлагаете было бы лучше. Спасибо.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Природный генетический алгоритм или доказательство эволюции живых организмов на C++