какие бывают операторы генетического алгоритма

Введение.Основы генетических алгоритмов

1.2. Генетические операторы

1.2.1. Репродукция

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

Очевидно, оператор репродукции (ОР) является искусственной версией естественной селекции – выживания сильнейших по Ч. Дарвину. Этот оператор представляется в алгоритмической форме различными способами (подробнее различные варианты ОР будут рассмотрены далее). Самый простой (и популярный) метод реализации ОР – построение колеса рулетки, в которой каждая хромосома имеет сектор, пропорциональный по площади значению ее целевой функции. Для нашего примера «колесо рулетки» имеет вид, представленный на рис.1.4.

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

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

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

1.2.2 Оператор кроссинговера (скрещивания)

Одноточечный или простой оператор кросинговера (ОК) с заданной вероятностью выполняется в три этапа:

1-й этап. Две хромосомы (родители) выбираются случайно (или одним из методов, рассмотренных далее) из промежуточной популяции, сформированной при помощи оператора репродукции (ОР).

Две новых хромосомы A’, B’ (потомки) формируются из A и B путем обмена подстрок после точки скрещивания:

Например, рассмотрим выполнение кроссинговера для хромосом 1 и 2 из промежуточной популяции:

Следует отметить, что ОК выполняется с заданной вероятностью (отобранные два родителя не обязательно производят потомков). Обычно величина вероятности полагается равной .

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

1.2.3 Мутация

Оператор мутации (ОМ) выполняется в два этапа:

1-й этап. В хромосоме случайным образом выбирается -ая позиция (бит) .

2-й этап. Производится инверсия значения гена в -й позиции:

Например, для хромосомы 11011 выбирается и после инверсии значения третьего бита получается новая хромосома – 11111. Продолжение нашего примера представлено в третьей таблице (мутация) рис.1.3 образом, в результате применения генетических операторов найдено оптимальное решение .

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

Источник

Генетические алгоритмы или как учебник по биологии может помочь в функциональной оптимизации

Одной из задач интеллектуальных систем является поиск оптимального решения: когда на систему влияет множество внешних и внутренних факторов, интеллектуальное устройство должно учесть их все и выбрать оптимальное поведение с точки зрения своей выгоды. Допустим, если Вы — хозяин склада, Вам необходимо учитывать много факторов (стоимость единиц товаров, спрос, издержки на хранение различных товаров на складе и т.д.) для минимизации издержек и получение наибольшей прибыли.

Другой пример: вы едете по скользкой дороге, и вдруг ваш автомобиль начинает заносить, справа в нескольких метрах от вас столб, а по встречной полосе едет грузовик. Внимание вопрос: как выйти из ситуации с наименьшими потерями, а лучше вообще без них. Факторов, которые нужно учитывать много: ваша скорость и скорость встречного автомобиля, расстояние до столба, «крутость» заноса и т.д. Что нужно делать? Давать газу, пытаясь выйти из заноса, или тормозить, или, может, попытаться аккуратно съехать в кювет, так чтобы не попасть в столб. Вариантов много, и для того чтобы определить оптимальный — нужно попробовать их все. Будь это компьютерной игрой – вы могли бы сохраниться и переигрывать до тех пор, пака результат вас не удовлетворит. Это и есть поиск оптимального решения.

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

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

Скажем проще: по сути, генетический алгоритм — это метод перебора решений для тех задач, в которых невозможно найти решение с помощью математических формул. Однако простой перебор решений в сложной многомерной задаче – это бесконечно долго. Поэтому генетический алгоритм перебирает не все решения, а только лучшие. Алгоритм берёт группу решений и ищет среди них наиболее подходящие. Затем немного изменяет их – получает новые решения, среди которых снова отбирает лучшие, а худшие отбрасывает. Таким образом, на каждом шаге работы алгоритм отбирает наиболее подходящие решения (проводит селекцию), считая, что они на следующем шаге дадут ещё более лучшие решения (эволюционируют).

Причём тут биология?

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

Особь – одно решение задачи.

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

И сразу самый простой классический пример. Допустим, роботу необходимо объехать шесть контрольных точек за наименьшее время. Расстояние от каждой точки до каждой задано в виде матрицы расстояний.

Это вариация задачи о коммивояжёре (путешественнике) – относится к классу NP-полных, проще говоря, не может быть решена с помощью математических формул.

Решение задачи – это последовательность прохождения контрольных точек. Возьмём несколько возможных решений (особей)– это и есть начальная популяция.

Определения качества решений

Функция пригодности – функция определяющая качество особей популяции. В нашем примере это будет сумма расстояний от точки до точки в выбранном маршруте.

где Р(1) … Р(6) – расстояние между точками в соответствующем переходе из матрицы расстояний

Нам необходимо найти минимальное расстояние, поэтому, чем меньше значение ФП для особи, тем лучше.

Давайте посчитаем функции пригодности. Для первой особи:

Для остальных особей таким же образом получаем:

Тут всё очевидно: особь №3 – лучшая, а №4 – самая плохая.

Генетические операторы

Дальше согласно алгоритму необходимо слегка изменить исходных особей, так чтобы они были похожи на своих родителей, но немного отличались. Так реализуется биологическое понятие «изменчивость».

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

Для потомков тоже посчитаны функции пригодности.

Оператор селекции

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

Алгоритмы селекции тоже могут быть различны, не будем пока заострять на этом внимание. Просто возьмем и отбросим из первой популяции (родители + потомки) четыре худших особи. Останутся родитель 1 и 3, и потомки 1 и 2. Эти особи сформируют новую популяцию. Далее алгоритм будет повторяться. Для наглядности посмотрим на блок-схему классического генетического алгоритма:

Критерий останова генетического алгоритма

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

Критерий останова – условие, по которому генетический алгоритм останавливает свою работу.

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

В нашем случае мы можем указать, например, один из следующих критериев останова:

Ещё немного о функции пригодности

Применение генетических алгоритмов

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

Такие алгоритмы могут стать хорошим помощником в бизнесе, сократить убытки и увеличить прибыль за счёт выбора оптимальных стратегий.

Источник

Основные этапы работы генетического алгоритма

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

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

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

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

Задача OneMax

В этой задаче у нас имеется список определенной длины, состоящий из нулей и единиц:

Наша цель – найти решение, которое бы давало максимальную сумму цифр этого списка:

Здесь N – длина списка. Очевидно, это список, состоящий из всех единиц:

Конечно, мы легко можем решить эту задачу без применения ГА, но на ее примере хорошо показать принцип его работы.

Популяция

Итак, все начинается с формирования популяции – множества особей одного вида. Что из себя представляют особи в задаче OneMax? Это обычные списки из нулей и единиц:

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

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

Функция приспособленности (целевая функция)

Например, в задаче OneMax, она суммирует все числа в генах и имеет следующий вид:

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

Конечно, для разных задач используется своя функция приспособленности, и ее конкретный математический вид определяется разработчиком ГА, исходя из поставленной задачи оптимизации.

Имитация эволюционного процесса

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

В итоге, схему ГА можно представить в следующем виде:

Отбор

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

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

Вначале во всей популяции случайным образом отбирается n индивидуумов (допустим три), а затем, среди них выбирается наиболее приспособленный:

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

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

Скрещивание

Этап скрещивания в научной литературе называют кроссинговером или кроссовером (от англ. crossing – скрещивание). На этом этапе происходит обмен данными между частями хромосом родителей. Обычно в популяции перебирают пары родителей, и фрагменты их хромосом перемешивают, получая новый набор генов в хромосомах их потомков:

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

Эта операция выполняется с некоторой (высокой) вероятностью. При этом родители, давшие потомство, как правило, не переходят в следующее поколение, а не давшие – сохраняются. В результате, размер популяции после операции скрещивания не меняется.

Существуют и другие виды скрещивания, о них мы также подробнее будем говорить на следующих занятиях.

Мутация

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

В самом простом варианте двоичного кодирования генов, мутация выполняет инвертирование бита:

Этот механизм позволяет расширять область поиска решения задачи и сохранять разнообразие популяции. Возможно, благодаря полезной мутации, особь приобретет новое свойство и станет более конкурентно-способной в своей популяции. В дальнейшем у нее есть все шансы дать потомство и закрепить полезный признак. Так, через мутацию, происходит улучшение решения. Конечно, может произойти и обратный эффект – ухудшение приспособленности индивидуума. Но тогда, он не сможет конкурировать с более приспособленными особями и вскоре будет отсеян в процессе отбора.

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

Видео по теме

Генетический алгоритм история и возможности

Источник

Генетическое программирование («Yet Another Велосипед» Edition)

Давайте на время отвлечемся от очередного «языка-убийцы C++», ошеломляющих синтетических тестов производительности какой-нибудь NoSQL-ой СУБД, хайпа вокруг нового JS-фреймворка, и окунемся в мир «программирования ради программирования».

Предисловие

Да, я осознаю в полной мере, что на дворе 2016 год, а я пишу такой длиннопост. Ещё и рисунки выполнены в стиле «курица лапой» пером на планшете, с шрифтами Comics Sans для гиков xkcd.

Введение

Ликбез

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

Как с помощью генетических алгоритмов решать задачи? Вы удивитесь, как всё просто работает в нулевом приближении:

Теперь WE NEED TO GO DEEPER. Первое приближение:

Значит, у нас есть задача\проблема, мы хотим найти её решение. У нас есть какое-нибудь базовое, плохенькое, наивное решение, результаты которого нас, скорей всего, не удовлетворяют. Мы возьмём алгоритм этого решения и немного изменим его. Натурально случайным образом, без аналитики, без вникания в суть проблемы. Новое решение стало выдавать результат хоть на капельку лучше? Если нет — отбрасываем, повторяем заново. Если да — ура! Удовлетворяет ли результат нового решения нас полностью? Если да — мы молодцы, решили задачу с заданной точностью. Если нет — берем полученное решение, и проводим над ним те же операции.
Вот такое краткое и бесхитростное описание идеи в первом приближении. Впрочем, думаю, пытливые умы оно не удовлетворит.

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

Теперь давайте рассмотрим основной цикл подробнее:

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

Недостатки

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

Практика

Выбор языка

Был выбран Ruby. Этот язык заполнил в моих делах нишу, каковую традиционно занимал Питон, и он настолько меня очаровал, что я непременно решил познакомиться с ним поближе. А тут такая возможность! Люблю убивать N (где ) зайцев за раз. Не исключаю, что мой код может местами вызывать улыбки, если не фейспалмы у олдовых рубистов (нет, извините, но именно рУбистов, остальные варианты — троллинг).

Генотип

Первой мыслью было то, что раз в языке есть eval, то генотип решения может без каких-либо ухищрений строиться из произвольных символов (выступающих в роли генов), и на выходе мы будем иметь скрипт, интерпретируемый самим Ruby. Второй мыслью было то, что на эволюцию решений с такими высокими степенями свободы может уйти реально много лет. Так что я даже не шевельнул пальцем в этом направлении, и думаю, не прогадал. Можно попробовать данный подход лет этак через 30, если сохранится закон Мура.
Эволюция в итоге была заключена в достаточно жесткие рамки. Генами решения являются высокоорганизованные токены с возможностью вложенности (построения древовидной структуры).
В первом эксперименте, где мы будем говорить о решениях как математических выражениях, токены это константы, переменные, и бинарные операции (не знаю, насколько легитимен термин, в контексте проекта «бинарная операция» значит действие над на двумя операндами, например сложение).
Кстати, я решил частично оставить совместимость с eval, поэтому если запросить строковое представление токена (через стандартный to_s), то можно получить вполне удобоваримую строку для интерпретации. Например:

Да и нагляднее так.

Генетические операции

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

Фитнесс-функция

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

В ранних прототипах я пробовал замерять затраченное на прохождение испытаний процессорное время, но даже при длительных (десятки миллисекунд) прогонах наблюдался разброс в ±10% времени на одно и то же решение, вносимый операционной системой, с периодическими выбросами +в 100-200%.
Так что в первом эксперименте ресурсоемкость вычисляется суммарной сложностью генотипа, а во втором подсчётом реально выполненных инструкций кода

Селекция

Каждое поколение содержит не более чем N решений. После применения генетических операторов, у нас максимум 2N решений, притом в следующее поколение пройдет, опять же, не больше N из них.
По какому принципу формируется следующее поколение решений? Мы на этапе, когда каждое из решений уже получило оценку фитнесс-функции. Оценки, разумеется, можно сравнивать друг с другом. Таким образом, мы можем отсортировать текущее поколение решений. Дальше видится логичным просто взять X лучших решений, и сформировать из них следующее поколение. Однако, я решил не останавливаться на этом, и включать в новое поколение также Y случайных решений из оставшихся.
Например, если X = Y, то чтобы решению пройти в следующее поколение, ему нужно оказаться среди 25% лучших, либо выкинуть 3 на трёхгранном кубике (если бы такой существовал). Достаточно гуманные условия, не так ли?
Так вот, включение случайно выживших в следующее поколение нужно для сохранения видового многообразия. Дело в том что подолгу держащиеся среди лучших похожие друг на друга решения выдавливают остальные, и чем дальше, тем быстрее процесс, а ведь зачастую бывает что доминирующая ветвь оказывается тупиковой.
Параметры X и Y, разумеется, являются настраиваемыми. Я прогонял тесты, как со случайными выжившими, так и без них, и доказал справедливость их добавления в алгоритм: в отдельных случаях (при поиске решений повышенной сложности), удавалось достичь более хороших результатов с их использованием (притом суммарная затрачиваемая на поиск решений мощность оставалась постоянной, например, X₁ = 250, Y₁ = 750 против X₂ = 1000, Y₂=0).

Условия победы

Тут кроется загвоздка: как понять, что пора заканчивать? Допустим, решение удовлетворяет нас по точности результатов, но как быть с трудоемкостью? Вдруг алгоритм сейчас поработает и выдаст решение по раскраске графов за O(n)? Утрирую конечно, но критерий остановки работы необходимо формализовать. В моей реализации выполнение алгоритма заканчивается, когда Top 1 решение не меняется определённое количество поколений (сокращенно R — rounds). Отсутствие ротации значит, что, во-первых, не нашлось альтернативного решения, которое бы смогло превзойти лучшее текущее решение; во-вторых, лучшее текущее решение не смогло породить улучшенную мутацию себя в течение заданного времени. Количество поколений, через которое наступает победа лучшего решения, обычно большое число — чтобы действительно убедиться в том, что эволюция не способна продвинуться дальше, требуется смена нескольких сотен (число варьируется в зависимости от сложности самой задачи) поколений.
К сожалению, несмотря на многочисленные предосторожности, случаи когда эволюция заходит в тупик всё же бывают. Это известная проблема генетических алгоритмов, когда основная популяция решений сосредотачивается на локальном оптимуме, игнорируя, в итоге, искомый глобальный оптимум. На это можно ответить игрой с параметрами: уменьшением квоты для победителей, увеличением квоты для случайных, и увеличением времени доминирования для победы, параллелизацией независимых друг от друга поколений. Но всё это требует мощностей\времени.

Конкретная реализация

Как принято, всё выложено на гитхабе (правда, пока без доков).
Теперь о том, что мы увидим в конкретно моей велосипеде реализации:

Собираем набор дел (Case group) на основании совокупности входных данных (Input group).

Имеется естественный отбор (Natural Selection), который включает в себя испытание, и фильтрует поступающую к нему группу штаммов по заданным правилам.

У нас есть набор значений переменных (Input Group, ага), например:

Решения (Solutions), которые мы будем сравнивать с эталонами, представляют из себя такие же формулы, но создаваемые случайно — последовательно мутирующие из базовой формулы (обычно это просто x ). Оценкой (Score) качества решения является среднее отклонение результата от результата эталона, плюс ресурсоемкость решения (суммарный вес операций и аргументов формулы).

Мутация формул

Как было упомянуто ранее, токенами формул являются константы, переменные, и бинарные операции.
Как происходит мутация формул? Она затрагивает один из токенов, содержащихся в формуле, и может пойти тремя путями:

Вот таблица происходящего с разными типами формул при разных видах мутации:

Примечание 1 Сокращение формул это попытка заранее произвести операции над константами, где это возможно. Например из » (3+2) » получить » 5 «, а из » 8/(x/2) » получить » (16/x) «. Задача неожиданно оказалась настолько нетривиальна, что вынудила меня писать прототип решения с исчерпывающим юнит-тестом, и то, я не добился настоящего рекурсивного решения, достающего константы для сокращения с любой глубины. Разбираться в этом было увлекательно, но в какой-то момент мне пришлось остановить себя и ограничиться достигнутым решением, так как я слишком отклонился от основных задач. В большинстве ситуаций, сокращение и так полноценно работает.
Примечание 2 У мутации бинарных операций есть особенность, в силу того, что операции имеют вложенные в себя другие формулы-операнды. Мутировать и операцию, и операнды — слишком большое изменение для одного шага. Так что случайным образом определяется, какое событие произойдёт: с вероятностью 20% мутирует сама бинарная операция, с вероятностью 40% мутирует первый операнд, и с оставшейся 40% вероятностью, мутирует второй операнд. Не могу сказать, что соотношение 20-40-40 идеально, возможно следовало бы ввести корреляцию вероятности мутации операции в зависимости от их весов (фактически, глубины вложенности), но пока что работает так.

Результаты

Теперь ради чего, собственно, всё затевалось:

Первый эталон — простой полином:

X принимает значения от 0 до 255, с шагом 1
R = 64, X = 128, Y = 128

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

Результаты поразили меня в самое сердце 🙂 За 230 (включая те R раз, когда Top 1 не менялся) поколений было выведено такое решение:

Как вы помните, между один поколением допускается и более одной мутации.

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

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

Второй эталон — натуральный логарифм:

x принимает значения от 0 до 25.5, с шагом 0.1
Наши решения лишены возможности использовать логарифмы напрямую, но данный эталон раскладывается в ряд Тейлора:

Вот и посмотрим, сможет ли решение воспроизвести такой ряд с заданной точностью.
Поначалу, пробовал прогоны с точностью до 0.001, но после нескольких суток упорной работы алгоритма решения достигли точности только около 0.0016, а размер выражений стремился к тысяче символов, и я решил снизить планку точности до 0.01. Результаты таковы:

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

Третий эталон — синус, задаваемый в радианах:

x принимает значения от 0 до 6.28, с шагом 0.02
Опять же, эталон раскладывается в ряд Тейлора:

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

Четвертый эталон — выражение с четырьмя (совпадение? не думаю) переменными:

Каждая из переменных принимает значения от 0 до 3 c шагом 1, всего 256 комбинаций.

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

Итоги

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

Дальнейшие эксперименты

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

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

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

Закончим на этой задумчиво неопределенной ноте. Большое спасибо за уделенное время!

Источник