Генетическое программирование 1.0

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

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

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

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

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

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

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. Оставлю возможность рисовать только чёрным.
• Художника нужно усложнять, первое, что напрашивается это добавление операции "функция", которая будет вызывать уже имеющуюся цепочку инструкций. Начнётся веселье с рекурсией. Так же нужны переменные и математические операции над координатами перемещения кисти. Тогда это будет больше похоже не программу.

Всем кто дочитал, бонус — анимашка прогресса: