бородат

Классический Иван

И птица рядом

#27
бородат
xeb


Проголосовать за комикс А-Топ100: Лучшие комиксы Рунета

Поддержать автора



Немного css
бородат
xeb


html + css

Сонное царство
бородат
xeb

Живу в сонном царстве. Причём являюсь главным нарушителем покоя. Когда прохожу мимо, сонные тушки смотрят на меня с укоризной. "Эй!", — говорят они, "что за нездоровая активность, мы тут спим ващета". Иногда меня будят, ударом головой в лицо, хорошо, что  голова пушистая. Из трёх домашних питомцев, роль живого будильника играет всегда один и тот же. Может он вытянул короткую спичку, а может ему это нравится.

Сперва думал, что ему от меня нужно только одно: "наполни миски, жалкий человечишка и делай, что хочешь!". Но регулярно это случается когда корм уже есть (не доели с вечера). В таком случае это похоже на ритуал: шерстяной шар тыкается мне в лицо, мы идём в ванную, не дожидаясь окончания водно-туалетных процедур, меня начинают подгонять: "Сколько можно возиться? Зачем ты мочишь лицо водой? Просто наслюнявь лапу и сотри всё что там у тебя за ночь навыделялось! Я всегда так делаю и посмотри какой красавчик!". Иногда выходим вместе, но чаще просто открываю дверь и выпускаю. Он сразу к миске, есть не начинает, сидит и смотрит. Чтобы начал нужно погладить голову.

Read more...Collapse )

Генетическое программирование 2.0 "В поисках контролируемой мутации"
бородат
xeb
Глядя на то, что вышло из прошлых экспериментов, задал начальные параметры генома, таким образом, чтобы потомки менялись поменьше, а геномы были более разнообразными.


Смотрю сейчас на это и понимаю, как я был наивен...

Следующая же популяции, на 198-м поколении, выдала особь с 98% успеха. Рассмотрев её геном, заключил, что она тоже совсем не мутировала а прирастала случайными операциями, которые очень удачно легли.

Счастливая популяция, топ-6:


Что же это такое? Почему программы с геномом, допускающим мутации, не выживают?

Массовые расследования показали, что программа с набором генов, меняющих хоть что-то, сильно искажает холст от поколения к поколению. Параметры, в таких особях, принимали астрономические значения. Было принято решение, задать для каждого гена диапазон предельных значений — минимум и максимум. Чтобы совсем не запутать нарисую табличку настроек генома:



За одно упростил нашего художника, забрал инструкцию смены цвета.



Такая инструкция влияла на все последующие макания кисти до следующей смены цвета. Поэтому её мутация могла сильно изменить результат.

Отправил это всё в свой эволюционный комбайн, получил 94,5% на выходе. И снова выжил геном без мутаций. Его мутирующие конкуренты опять оказались слишком нестабильными.

В итоге я провёл целый комплекс мероприятий:

Случайный диапазон изменений


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

Например, ген мутации параметров постановил, что конкретная инструкция "перемещение кисти на 1 влево и 3 вверх" должна измениться на 60%, раньше, к 1 и 3, прибавилось/отнялось 0.6 и 1.8 соответственно, теперь, величины изменения будут лежать в пределах [0; 0.6] и [0; 1.8], какие конкретно они примут значения решит судьба генератор случайных чисел.

Счастливчики и неудачники


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

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

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

Чтобы отличать, чудом выживших, на снимках поколения, добавил звёздочку (*) перед количеством инструкций программы. Так же там появилась информация о геноме: <кол-во генов мутирующих инструкции>:<кол-во генов мутирующих геном>.



Турнирный метод отбора


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

Идея вообще отличная, и популяцию улучшаем и даём шанс на потомство даже не очень, по общим меркам, успешным особям. Незамедлительно реализовал.

Первый раз разбил на три группы: альфачи, бетты и гаммы. Если, из-за нечётности группы, кто-то не находил себе противника ему записывался автовин. Метод рабочий, средний показатель популяции растёт, смотреть снимки стало гораздо интересней, можно было даже на поздних поколениях увидеть разнообразных представителей. Вот, например, 5 особей от разных групп, 155-го поколения, отобранных по турнирному методу:


Был забавный эпизод: один геном убил в себе всякую способность к изменениям, даже к появлению новых инструкций и заполнил собой всю последнюю группу. Из поколения в поколение он просто копировал себя 1 в 1. Паразитировал на популяции, не давая никаких шансов получить из этой группы хоть что-нибудь. Когда я пошёл смотреть его в базе, строка, описывающая его геном, имела длину 666 байт.



Есть конечно и минусы: скорость роста среднего показателя значительно ниже.

На графике одна популяция с методом отбора "лучшие из лучших" (best) и три с турнирным методом по 5, 3 и 1-й группе, смотрим их средние значения:


Оптимизация кода


Устав ждать очередное поколение, решил по оптимизировать код. Расставил таймеры, нашёл узкие места. Самыми ресурсоёмкими, "внезапно", оказались два процесса: получение нового поколения и выполнение инструкций программ. С удивлением обнаружил, что конструкция foreach(range(...)) работает гораздо медленнее for(...). Но самый большой прирост производительности случился когда я перенастроил всё c PHP 5.5 на PHP7. Всё ускорилось в разы, ребята вообще молодцы.

Что там с мутациями?


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

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

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

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

Запустил генерацию поколений. И о чудо! Оно заработало! Мутирующие геномы стали занимать лидирующие позиции, среднее по популяции росло. Я был рад. Наблюдал за изменениями, ждал особо высокого процента совпадений, как вдруг одно из поколений резко снизило показатели. По началу они начали немного выравниваться, потом снова провал и дальше только деградация.

Понятно, что случайные мутации могут изменить рисунок, но почему так резко? Да тут попахивает расследованием!

Для детального разбора я взял самую лучшую особь того поколения после которого случился спад. Это родитель и его потомок:


Мы помним, что согласно параметрам, должно мутировать только две инструкции за раз. Операции сильно связаны друг с другом, изменится какое-нибудь ранее перемещение кисти вся картинка может сместится, что тут и случилось. Но действительно ли на картинке всего два изменения инструкций? Сравнение программ показало, что их гораздо больше. Как такое может быть? Детально рассмотрел процесс создания потомка по шагам и нашёл чудесный баг:



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

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

На сегодня всё.

В планах:
* посмотреть что теперь будет при увеличении мута-силы
* сделать инструкции менее связными
* таки добавить художнику возможность создавать фукнции

Как и обещал выкладываю в общий доступ https://github.com/zapominai/GeneticProgram
Tags:

Генетическое программирование 1.0
бородат
xeb
Жена выбрала в качестве дипломной работы перевод книги про генетическое программирование (ГП). Началось всё с того, что я попросил её, из любопытства, перевести небольшую статью про ГП, сам особо не разбираясь в теме. С тех пор у них и закрутилось.

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

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

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



Результатом работы наших программ будет рисунок. Другими словами каждый "организм" в популяции это набор инструкций для художника. Что же умеет первая версия художника?



По какому признаку мы будем делать отбор? Будем выбирать тех, кто лучше нарисует закрашенный кружочек, ну или не кружочек, в общем "я так вижу":



100% означает, что у изображения все точки совпали с эталоном, что логично, потому что это он и есть.

А теперь возьмём и сгенерируем популяцию из 100 особей, по 300 инструкций в каждой. Сами инструкции и их параметры будем выбирать абсолютно случайным образом — никакого программирования!

Вот они, исчадия хаоса, жаждущие эволюционировать:


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

Как же будет осуществляться отбор? Очень просто: берём 30% самых успешных, остальные не выжили, ничего личного просто эволюция. 30% счастливчиков тоже помрут, но оставят после себя потомство (и запись в ЗАГСе базе данных).

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

Пример: было 100 голов, выжило 30 (30%). У каждого будет по 3 (100/30 = 3.33) дитя, плюс первые 10 (100 - 30*3) получат по +1.

Как будут передаваться признаки? Каждая программа имеет набор генов. Гены бывают 6 типов:


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

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

Гены, которые могут изменить размер генома, срабатывают в самом конце, чтобы не раздуть его до бесконечности или не убить сразу в ноль.

Вот и вся бесхитростная механика. Заэволюционируем первые 10 поколений:


На графике показатели успешности поколения: минимум, максимум, среднее. Оно работает! Программы становятся всё лучше и лучше по нашему критерию. Прогресс на лицо:



Посмотрим на лучшую особь из этого поколения, мистера 73.5%.

Количество инструкций: 539 (начинали мы с 300)
Геном: 1 ген, сила мутации количества инструкций, значение 4%

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

А что с геномом у остальных 99-ти особей этого поколения? Он такой же. Расследование показало, что очень быстро в популяции осталось 2 типа генома, которые боролись за жизнь.
И 4 поколения назад, погибли, не оставив потомства, последние представители конкурирующего генома. Они держались дольше всех, посмотрим их.

Четыре гена разных типов:
  • Сила мутации инструкций 17%
  • Сила мутации количества инструкций 4%
  • Кол-во затрагиваемых мутацией генов 22%
  • Сила мутации генов 0%

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

Что ж, возможно, задавать значение -2 для гена, меняющего количество генов, не лучшая идея. Появившись с таким значением он может быстро выкосить весь геном, без шанса на изменения.

С этим разобрались. Остался один интересный вопрос, каков предел улучшения у текущих особей? Пока что идут очень хорошо. Посмотрим...



Своего максимума, 85% успеха, популяция достигла на 49-м поколении. Это был монстр из 1961-й инснтрукции. Вон он, мой племенной буцефал:

Дальше пошла деградация, тлен и тщет.

Резюме:
  • С параметрами, отвечающими за изменение генома, нужно нежнее.
  • Обрабатывать программы с большим количеством инструкций долго. Оптимизировать не хочется, поэтому пойду по пути сжатия программ. Уберу мусор, типа макнуть кисть три раза в одно и тоже место или перемещения на 0. Оставлю возможность рисовать только чёрным.
  • Художника нужно усложнять, первое, что напрашивается это добавление операции "функция", которая будет вызывать уже имеющуюся цепочку инструкций. Начнётся веселье с рекурсией. Так же нужны переменные и математические операции над координатами перемещения кисти. Тогда это будет больше похоже не программу.
Всем кто дочитал, бонус — анимашка прогресса:

.|.
бородат
xeb
по глупости мной чего-то хочу, громко кричу: срочно найти пикачу. зарплату врачу, и быть там где хочу. тем, кем хочу,чем хочу.что бы было по моему. неприменно угодить чужому мнению, нари- совать огромный хуй, сти хо тво ре нием.

(no subject)
бородат
xeb
1485415355179263652[1].jpg

(no subject)
бородат
xeb
Если долго сидеть на берегу реки
И не о чём не думать
То рано или поздно
Мимо проплывёт твой труп.

end
бородат
xeb
А запишу ка я все истории своих смертей. За свои скромные года я несколько раз умирал, пару раз погибал и один раз самоубивался. Всё это происходило во снах, поэтому кто не любит такое читать, под кат строго воспрещается.

Не для впечатлительных...Collapse )

СХЕМА
бородат
xeb
Заказал себе к зиме вязаную шапу шапулю шапку. Аня показала мне разные варианты, ткнул пальцем на понравившуюся.

Заглядываю как-то в её ноутбук, а там это:



Она поглядывает, вяжет.

— Что это? - спрашиваю
— Это схема.

СХЕМА! :D Да это кто-то крючков набросал, расставил как попало цифры и обвёл что-то зелёным, с понтом это тут всё не просто так.

Смех-смехом а ведь связала. Очень красивая и тёплая получилась.

?

Log in

No account? Create an account