Комментарии 44
Кажется, не раскрыта тема полового размножения, которая выдала бы много интересных вариантов. Надо только подумать, как скрещивать формулы. И сколько полов сделать. Может быть эти параметры также сделать эволюционными.
Помню, залипал в boxcar2d. Жаль, что оригинал на флеше. Беглый гуглинг дал что-то похожее https://rednuht.org/genetic_cars_2/
Особенно впечатляло - плато на длительный период, а потом резкий скачок и новый фаворит.
минималистичная модель эволюции
Интересная идея, вполне заслуживает своего развития.
С одной стороны, мы показываем, что мутации и естественный отбор могут из полного хаоса создать что-то упорядоченное. С другой стороны — мы при этом выступаем в роли Демиурга, которому приходится контролировать процесс и настраивать параметры.
Из этого можно извлечь философский подтекст. Во-первых, естественно, наличие «Высшего Заказчика» («Демиурга», по-вашему). Кто он или что из себя представляет – неважно. Главное, что есть Интерес, Желание, Цель и Возможности реализации некой Идеи.
Таковой Идеей может выступить концепция Развития, Разнообразия, Гармонии и Красоты. Или, что вы там еще подразумевали?
В качестве инструментов вы выбрали «мутации» и «естественный отбор», но при этом оставили право за «Исполнителем Заказа» «Высшего Заказчика» (которые могут быть в одном Лице) «контролировать процесс и настраивать параметры».
В общем, модель вполне практичная и способная реализовываться в разных вариациях (в компьютерном виде). Наверное, всё к тому и идет. Высшая цель существующего Разума – создать модель самого себя, а, может быть, даже превзойти себя, Когда возникнут возможности, то создать новые Миры и Вселенные, развивающиеся по выбранным, этим Разумом, законам развития.
Отсюда следует что? То, что первопричина нашего Мира – субъективна. Иначе, надо придумывать идеи «Большого Взрыва», «возникновения Всего из Ничего», вечные циклы, вроде, «Хаос – Самоорганизация – Саморазрушение», или, там, всё «Само – Само – Само» и т.п. Убедительно? Как, по мне, то так себе… :)
Очень интересная статья, прям как будто прочитал фантастику))
Прочитал с огромным интересом!
Много лет назад в детстве я тоже делал модели эволюции, на QuickBasic 4.5. Организмы имели несколько параметров - размер, скорость, что-то еще. Мир представлял собой зацикленное по двум краям поле, по которому снова и снова медленно проходила от края до края широкая полоса - типа световой день. На свету организмы заряжались "энергией", в темноте тратили. Двигаясь тоже тратили. Для рождения потомства нужна была энергия, мутации случайно немного меняли параметры потомства. В итоге популяция через много циклов почти всегда делилась на "растения", которые теряли способность двигаться и легко переживали темноту, и "животных" - быстрых и легких которые успешно бегали за солнцем. Растения создавали колонии заселяя потомками место вокруг себя. Животные - не очень устойчивые популяции, которые могли в процессе миграций вымереть полностью.
Правда до взаимодействия организмов (поедания, скрещивания) я не добрался - начался институт а потом взрослая жизнь ))
Почему бы в качестве loss функции не взять просто количество неправильных ответов, от 0 до 12?
По поводу Python:
Не потому, что Python сам по себе не особо быстр, а потому что он прозрачно поддерживает длинную арифметику, а в мире случайных формул вполне может появится, например, такая:
x**967**9813.
import numpy as np
a = np.float32(10)
a**967
"<stdin>:1: RuntimeWarning: overflow encountered in scalar power
np.float32(inf)"Правда пришлось бы предварительно парсить формулу чтобы обернуть числовые константы во float32, но это не так уж сложно.
Спасибо, о переводе во float как-то не подумал. Это вообще не сложно, просто мысль такая не возникла. Действительно, решило бы проблему.
Почему бы в качестве loss функции не взять просто количество неправильных ответов, от 0 до 12?
Это замедлит эволюцию, потому что все формулы, выдающие 12 неверных ответов, будут иметь одинаковую оценку. Например, y = 42 и y = 9000 одинаково плохи — 12 неправильных ответов. В какую сторону двигаться, чтобы улучшить — неизвестно.
Получится блуждание в темноте, которое рано или поздно (но медленнее, чем через LSE) дойдёт до y = 31, то есть 5 неправильных ответов, и любая мутация будет ухудшать результат. Эволюция остановится.
Да, уже тоже об этом подумал, слишком ступенчатая получится. Но можно слегка приправить градиентом, например прибавить MSE с небольшим весом, скажем в 0.001. Просто штрафовать за дробные значения или отсутствие x в формуле мне показалось совсем уж костыльным решением.
P.S. Забыл упомянуть, статья отличная! Даже захотелось написать что-то подобное на питоне, с какой-нибудь другой оптимизируемой функцией.
Подбор алгоритма наград и штрафов в подобных алгоритмах и их развитии - RL-обучении или обучение без учителя - это сильно сложнее, чем может показаться. Прямо очень сильно сложнее, можно сказать, целая наука, где нужно не просто понимать базу, но и думать как модель.
Я так RL-нейросетку пытался научить торговли на бирже (хотя бы просто достичь оверфиттинга, чтобы она что-то умела делать), и поставил очевидную награду - больше прибыль - больше награда и наоборот. Сетка попыхтела, и решила, что самый лучший вариант - просто ничего не делать. И, в сущности, была права. Тогда я ввел штраф за бездействие, и система раз в N шагов делала покупку и тут же продажу. И так еще кучу итераций я пытался заставить сетку делать хоть что-то - она искала самый простой путь сделать минимум и отдыхать остаток времени. В итоге, я подумал, что у меня получился второй я, которому хочется отдыхать, а от него что-то требуют, проникся сочувствием, и удалил все наработки :)
Спасибо, было интересно почитать (͡°͜ʖ͡°)
Что-то про эволюцию помню писал)
https://habr.com/ru/articles/498914/
Интересный гайд, спасибо)
Увлекательная статья и результат очень красивый получился. Главное, не показывайте статью креационистам -- сразу начнут рассказывать, что, мол, видите, как всё сложно, а тут - якобы случайно цельный человек с глазом сразу работающим, молекулярным мотором и чего там они ещё приплетают.
Пока читал статью, в голове был вопрос "Зачем же вы секс запретили в этом мире?", но в конце вы раскрыли и эту тему :) Когда-то пытался делать мутационным алгоритмом поиск пути, так прямо нутром ощутил, как плохо оказываться в локальных минимумах. В нейросетях это обходится сейчас успешно. Интересно было бы попробовать сделать на нейросетях такое. Всё-таки, мутационные алгоритмы намного менее эффективные. Только, конечно, нужно думать как что кодировать и функцию потерь как задавать. Или перепоручить языковым моделям, они получше уже справляются.
Я выполнил и ваше предложение поискать формулу самому, только сразу разрешил деление по модулю (%) и правильно сделал. С ним конечно, начало лёгкое - из 31 вычесть x%2 и потом решать для февраля и летнего сбоя. Подводить под это теоретическую базу было лень и я методом тыка вышел как-то на поправочный коэффициент для лета:
k2=((x % 7 + 1) + 1) % 2
который даёт 010101001010 и это можно вычитать из 31. Оставался февраль. Методом тыка как-то быстро вышел на
k1 = x*(x % 3)%2
который давал 1-цы для февраля и августа. Понял, что август можно выкинуть, просто умножив на x и взяв остаток от деления на 7. Для 0-го и 7-го это будет 0, а остальные и так нули. Ну и умножить всё на 2.
Получилось n = 31 - 2*x*(x*(x % 3)%2)%7 - ((x % 7 + 1) + 1) % 2
Но это ещё не всё. Так как я люблю тестировать нейросети на разных задачах, скормил это им. Проверял ChatGPT o3 и Gemini 2.5 Pro. Последняя плохо справилась. Обе пытались считать деление целочисленным, но o3 быстро исправилась, когда пояснил ей условия, а Gemini продолжала выдавать не то.
В итоге o3 выдала сначала такое решение для разрешённого деления по модулю (24 символа). Вместо x у неё был m. Я его забыл в алфавите указать, сама догадалась:
29-m%7%2+2%((m+11)%12+2)
потом сократила его до 22-х:
29-m%7%2+2%(m*m-2*m+3)
Но даже без деления по модулю она выдала решение. Правда, она там искала в интернете, хотя я и не включал явно. Слишком самостоятельные стали модели. Вот решение через многочлен с какими-то там множителями Лагранжа и интерполяционной теоремой:
30
+(m-1)*(m-2)*(m-3)*(m-4)*(m-5)*(m-6)*(m-7)*(m-8)*(m-9)*(m-10)*(m-11)/(-39916800)
-2*(m)*(m-2)*(m-3)*(m-4)*(m-5)*(m-6)*(m-7)*(m-8)*(m-9)*(m-10)*(m-11)/3628800
+(m)*(m-1)*(m-3)*(m-4)*(m-5)*(m-6)*(m-7)*(m-8)*(m-9)*(m-10)*(m-11)/(-725760)
+(m)*(m-1)*(m-2)*(m-3)*(m-5)*(m-6)*(m-7)*(m-8)*(m-9)*(m-10)*(m-11)/(-120960)
+(m)*(m-1)*(m-2)*(m-3)*(m-4)*(m-5)*(m-7)*(m-8)*(m-9)*(m-10)*(m-11)/(-86400)
+(m)*(m-1)*(m-2)*(m-3)*(m-4)*(m-5)*(m-6)*(m-8)*(m-9)*(m-10)*(m-11)/120960
+(m)*(m-1)*(m-2)*(m-3)*(m-4)*(m-5)*(m-6)*(m-7)*(m-8)*(m-10)*(m-11)/725760
+(m)*(m-1)*(m-2)*(m-3)*(m-4)*(m-5)*(m-6)*(m-7)*(m-8)*(m-9)*(m-10)/39916800
Такое, конечно, эволюционный алгоритм будет долго искать, да и нейросеть не уверен, что нашла бы. Тут думать надо.
В дополнение к сотворению календаря -- сотворение часов:
Реально очень интересно. Хотелось бы увидеть еще больше подобных симуляций. Не менее интересных и не менее занятных)
Плюсик! Интересно было понаблюдать не только за эволюцией формул, но и за "эволюцией" условий игры. Оказывается, от них тоже много что зависит. Конвей, придумывая правила для игры "Жизнь", тоже перепробовал много вариантов, прежде чем пришел к таким правилам, которые делают изменения на доске интересными. А в реальном мире изменение любой физической константы приводит к вырожденному миру, где не то что эволюция, а даже никакие атомы не появились бы. Наверное, Боженька, как и вы, тоже долго игрался с исходными условиями, прежде чем запустилось и заэволюционировало что-то интересное :)
Хотелось бы посмотреть на код и позапускать самому
Как раз сейчас читаю книгу Маркова "охота на электроовец". Там большой раздел посвящён шахматным программам, и один из основных выводов - хорошая оценочная функция (та, которая оценивает, хороша ли позиция игрока, или нет) очень важна.
Например, специализированный компьютер ДипБлю (который победил Каспарова) имел флопсов на порядки больше, чем современные машины, на которых запускают до-нейронные шахматные программы. Но те имеют рейтинг в полтора раза больший, чем у ДипБлю - и, если я правильно понял Маркова, прирост в основном связан с уточнением оценочной функции.
Вероятно, если у вас оценочную функцию уточнить, результаты будут появляться на порядок быстрее.
Согласен, оценочная функция очень важна. Если говорить о настольных играх, то там есть чит: можно вообще не задавать оценочную функцию, а подбирать её налету с помощью MCTS. Я об этом когда-то писал.
Можно применять не только для настольных игр, а вообще для поиска в дереве, где есть понятия "успех" и "провал".
Правда, если применить MCTS в этой задаче, то и генетический алгоритм уже станет не нужен.
Спасибо, отличный эксперимент и великолепный текст!
Прям эволюционный триллер посмотрел! Шикарная статья!
Замечательная статья, и написана живым, понятным, красочным языком. Прочитал на одном дыхании, не отрываясь, как хороший детектив :)
Пара замечаний, не в плане критики, а вообще :)
Мне кажется, использование обратной польской нотации сделало бы формулы, во-первых, разнообразннее, во-вторых, жизнеспособных формул было бы в разы больше, такую запись очень сложно поломать (там нет скобок), только если в стеке не хватает операндов для операции. И скрещивание можно было бы сделать разными способами :)
Общефилософское: статья как раз наглядно демонстрирует факт "нет давления среды - нет отбора, нет эволюции". На первых вариантах (где основые это
30,31и30+x/11) это особенно четко видно :) Заодно наглядный пример эволюционным скептикам, которые спрашивают, почему сейчас мы не наблюдаем эвлюцию. Потому и не наблюдаем, что давления среды практически нет, мы находимся на эволюционном плато. Разумный диизайн тут непричем :)Интересно было бы имитировать резкое изменение условий среды, то есть, допустим, есть у нас популяция, состоящая из формулы
30+x/11и ее родни, а мы, не меняя популяцию, меняем функцию оценки, и смотрим, кто выживет в новых условиях, и какое потомство даст :)Скрещивание, я так понимаю, было случайным? А если ввести критерий "привлекательности" партнера, когда, допустим, формула "предпочитает" для скрещивания более короткую в качестве партнера?
По поводу обратной польской (венгерской) записи согласен, но это больше подходит для языков, где нет встроенного eval. На самом деле я когда-то проводил такой же эксперимент на Java, и там как раз использовал ОПЗ. Причём, у меня в реализации была "багофича". Дело в том, что операторы — это один символ, а число — это несколько цифр. Для простоты я решил сделать, что цифра — это тоже операция, которая берёт с вершины стека число, умножает его на 10 и прибавляет соответствующую цифру. Например, "123" — это поместить в стек 1, затем дописать к нему 2, затем дописать к нему 3. Фича была в том, что, например "x1" получалась корректной записью и означала x*10+1. Разумеется, эволюция начала во всю эксплуатировать это фичу.
В первых вариантах всё-таки причина "застоя" именно в том, что был ограниченный инструментарий. Это было лучшее, что можно было получить с теми операциями. Ну или, возможно, что-то лучше и возможно, но крайне маловероятно. Это примерно как с нейронками, когда количество слоёв/параметров недостаточно для решения задачи — обучение остановится на достаточно высоком loss, просто потому, что сделать лучше принципиально невозможно, если модель недостаточно большая.
4. Согласен )
Помню, была модель эволюции, кажется, называлась Pool, где можно было задавать критерии "красоты" для организмов: более быстрые, или более сложные, или наоборот более медленные и т.д. И можно было прямо в процессе менять и видеть, как постепенно средний состав организмов меняется.
И так постепенно шаг за шагом был получен ИДЕАЛ.
2/x^30|x^7>x
Можно подробно расписать операции. Или я плохо понимаю JS или одно из двух.
Но я не смог осилить как и что считается, а сидеть с рядами 0 и 1 не хочется.
Слишком ГОЛОВОКРУЖИТЕЛЬНО.
Сама постановка задачи и ее решение заставляют напрячь мозги.
По порядку:
2/x
Уже подобное рассматривалось в статье, только там было 3/x.
При x=0 получаем деление на ноль, но из-за битовых операций превращается в ноль.
При x=1 получаем 2.
При x=2 получаем 1.
При x>2 получаем дробное число меньше единицы, которое из-за битовых операций становится нулём.
Таким образом для всех месяцев получаем:
0 2 1 0 0 0 0 0 0 0 0 0
2/x^30
Предыдущее ксорим с 30. Получаем:
30 28 31 30 30 30 30 30 30 30 30 30
Прелесть XOR в том, что в феврале он работает как минус, а в марте — как плюс.
Тут уже несколько совпадений с ожидаемыми ответами, но самое важное — попали в февраль. Это главный смысл этой части — сделать 28 дней в феврале.
7>x
Можно записать и как x<7.
До июля каждый чётный месяц (если нумеровать с нуля) имеет 31 день. В августе эта закономерность инвертируется — теперь уже нечётные месяцы имеют 31 день.
Соответственно, это выражение даёт или true (с января по июль), или false (с августа по декабрь). Из-за последующих битовых операций это превратиться или в 1, или в 0.
1 1 1 1 1 1 1 0 0 0 0 0
x
На первый взгляд кажется, что мы здесь полностью берём значение x, но на самом деле важен только младший бит. Так как число 30 в двоичном виде выглядит как 11110, то позже старшие биты "растворятся" в этих единичках.
По сути, тут мы просто смотрим на чётность номера месяца, который, как уже говорилось, нужен для чередования месяцев с 31 днём.
0 1 0 1 0 1 0 1 0 1 0 1
x^7>x
Как уже говорилось, условие преобразуется в 0 или 1, а у икса важен только младший бит. Таким образом, здесь просто инвертируется младший бит, если месяц до июля включительно. В итоге получаем 1 строго для тех месяцев, в которых 31 день.
1 0 1 0 1 0 1 1 0 1 0 1
2/x^30|x^7>x
Совмещаем результаты:
30 28 31 30 30 30 30 30 30 30 30 30
1 0 1 0 1 0 1 1 0 1 0 1
То есть просто добавляем один день тем месяцам, в которых 31 день, и не меняем остальные. Так как используется не плюс, а побитовый OR, то на март (в котором и так уже правильный ответ) это никак не влияет.
Как-то так ;)
Очень впечатлило, спасибо огромное за вашу работу! Даже не задумывался, насколько оказывается просто придумать идеал и механизмы для стремления к нему через мутации и отсеивания, это ведь просто абстрактные математические формулы. До идеи реализации надо было дойти, и она получилась по настоящему минималистичной. Респект)
И что интересно — в формулах напрочь отсутствовали скобки и тернарные операторы.
Эти операции становятся потенциально валидны только при одновременном парном появлении, причём в правильном порядке "( )" или "? :" . Их надо внедрять в мутации, как единую лексему, а не по одному символу, когда они не имеют шансов.
Или же использовать польскую нотацию. Тогда, правда, критерии краткости поменяются, что приведёт, возможно, к иного вида популяциям. Но это уже не JS, а получается другая задача.
Можете пояснить, какое у вас стояло условие на вывод строки? Ну когда стоит сделать вывод на экран текущего состояния?
Когда получен новый рекорд. То есть хранится некий глобальный лучший результат (минимальный loss). Как только появляется формула лучше (у который loss ниже), она выводится.
Просто обычно формула-лидер достаточно долго держится в топе, и первоначально, когда я просто выводил лучшую формулу в каждом поколении, получал сотни одинаковых строк. Поэтому просто удалил "дубли", теперь выводится только когда действительно есть какие-то подвижки.
Сотворение мира за 20 минут на JavaScript, или минималистичная модель эволюции