Генетическое программирование. Возможности и проблемы технологии
Что такое генетическое программирование?
Генетическое программирование может послужить «механизмом» приобретения желаемых качеств у генно-модифицированного организма. Подобные эксперименты над растениями проводятся уже давно.
Возможности генетического программирования
Если вы помните еще из школьных курсов, то в ДНК и РНК человека содержится запись всей жизнедеятельности человеческого организма, его физические данные и свойства. На самые неблагоприятные признаки как раз и можно было бы воздействовать. Но нужно понимать, что в результате такого воздействия человеческий дух и его душ а не меняются, также не меняется его образ жизни, мышление, сознание и подсознание, память и понимание всего происходящего вокруг.
Однако все это пока на уровне предположений, потому что по факту генетическое программирование находится на стадии своего зачатия и впереди еще очень много всего нужно изучать. Элементарно сама молекула ДНК человека не изучена до конца, о каком тогда генетическом программировании может идти речь? Ведь управлять неизведанной системой будет очень сложно.
Попытка генетического программирования живого организма
Массачусетский Технологический Институт в составе небольшой группы уче н ых первым провел попытку генетического программирования живого организма. Для этого даже была разработана специальная технология программного кода «Cello». Данная технология дает возможность прописать в клетк е настоящей бактерии любой набор признаков и создать в ней собственную биологическую схему с необходимыми параметрами.
Технология «Cello» и новый генетический язык программирования существуют не только в теории. Уже проведен практический эксперимент, где удалось доказать возможность программирования ДНК. Да, пока это была бактерия, но это уже дает огромные перспективы для дальнейшего изучения и развития. К примеру, уче н ым удалось воссоздать 60 биологических схем, которые успешно были внедрены в подопытный организм. В финале работоспособность показал о 95% внедренных биологических схем.
Принцип работы генетического языка программирования
Возможности генетического языка программирования
Теперь только представьте грандиозность и потенциал этого проекта. Насколько широкие проблемы сможет решать программирование ДНК.
Мы будем очень благодарны
если под понравившемся материалом Вы нажмёте одну из кнопок социальных сетей и поделитесь с друзьями.
Генетическое программирование («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, разумеется, являются настраиваемыми. Я прогонял тесты, как со случайными выжившими, так и без них, и доказал справедливость их добавления в алгоритм: в отдельных случаях (при поиске решений повышенной сложности), удавалось достичь более хороших результатов с их использованием (притом суммарная затрачиваемая на поиск решений мощность оставалась постоянной, например, X1 = 250, Y1 = 750 против X2 = 1000, Y2=0).
Условия победы
Тут кроется загвоздка: как понять, что пора заканчивать? Допустим, решение удовлетворяет нас по точности результатов, но как быть с трудоемкостью? Вдруг алгоритм сейчас поработает и выдаст решение по раскраске графов за O(n)? Утрирую конечно, но критерий остановки работы необходимо формализовать. В моей реализации выполнение алгоритма заканчивается, когда Top 1 решение не меняется определённое количество поколений (сокращенно R — rounds). Отсутствие ротации значит, что, во-первых, не нашлось альтернативного решения, которое бы смогло превзойти лучшее текущее решение; во-вторых, лучшее текущее решение не смогло породить улучшенную мутацию себя в течение заданного времени. Количество поколений, через которое наступает победа лучшего решения, обычно большое число — чтобы действительно убедиться в том, что эволюция не способна продвинуться дальше, требуется смена нескольких сотен (число варьируется в зависимости от сложности самой задачи) поколений.
К сожалению, несмотря на многочисленные предосторожности, случаи когда эволюция заходит в тупик всё же бывают. Это известная проблема генетических алгоритмов, когда основная популяция решений сосредотачивается на локальном оптимуме, игнорируя, в итоге, искомый глобальный оптимум. На это можно ответить игрой с параметрами: уменьшением квоты для победителей, увеличением квоты для случайных, и увеличением времени доминирования для победы, параллелизацией независимых друг от друга поколений. Но всё это требует мощностей\времени.
Конкретная реализация
Как принято, всё выложено на гитхабе (правда, пока без доков).
Теперь о том, что мы увидим в конкретно моей велосипеде реализации:
Собираем набор дел (Case group) на основании совокупности входных данных (Input group).
Имеется естественный отбор (Natural Selection), который включает в себя испытание, и фильтрует поступающую к нему группу штаммов по заданным правилам.
У нас есть набор значений переменных (Input Group, ага), например:
Решения (Solutions), которые мы будем сравнивать с эталонами, представляют из себя такие же формулы, но создаваемые случайно — последовательно мутирующие из базовой формулы (обычно это просто x ). Оценкой (Score) качества решения является среднее отклонение результата от результата эталона, плюс ресурсоемкость решения (суммарный вес операций и аргументов формулы).
Мутация формул
Как было упомянуто ранее, токенами формул являются константы, переменные, и бинарные операции.
Как происходит мутация формул? Она затрагивает один из токенов, содержащихся в формуле, и может пойти тремя путями:
Вот таблица происходящего с разными типами формул при разных видах мутации:
| Формула → Мутация ↓ | Константа | Переменная | Бинарная операция |
|---|---|---|---|
| grow | становится переменной, или включается в новую случайную бинарную операцию (со случайным вторым операндом) | в новую случайную бинарную операцию (со случайным вторым операндом) | включается в новую случайную бинарную операцию (со случайным вторым операндом) |
| shrink | невозможно уменьшить, так что применяем к ней операцию shift | становится константой | вместо операции остается лишь один из операндов |
| shift | изменяет свое значение на случайную величину, может поменять тип (Float Int) | становится другой случайной переменной (если это допустимо в данном контексте) | либо операнды меняются местами, либо меняется вид операции, либо происходит попытка сокращения операции |
Примечание 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. Понадобились тысячи поколений, чтобы вывести в итоге громоздкие формулы. Я вижу три варианта, почему это случается:
Дальнейшие эксперименты
Здесь должен был идти рассказ про более амбициозный эксперимент, целью которого является автоматическая генерация алгоритма сортировки массива.
Был создан минимально допустимый набор выражений, состоящий из примитивов и управляющих структур (следований, циклов, ветвлений) позволяющий реализовать наивные сортировки (как минимум, «пузырьковую» и «выбором»), а также простейшая виртуальная машина, предназначенная исключительно для сортировки массивов.
Но рассказа здесь нет — эксперимент еще не проведен. Реализация мутирования еще далека от завершения. Плюс, итоги первого эксперимента заставили меня сильно усомниться в шансах на успех с сортировками: если в первом случае хоть как-то присутствует возможность линейного наращивания решения с планомерными приближением к эталонному результату, то в случае с сортировками, алгоритмы с единственным неверным шагом коверкают результат до неузнаваемости.
Как в таких условиях адекватно оценить, насколько хорошо претендент прошел испытание? У меня нет ответа. Как выбрать из двух претендентов, если они одинаково не отсортировали массив, но за разное количество выполненных команд? Выбрав простой, мы можем скатиться к доминированию претендентов типа
Выбор более сложного контринтуитивен — зачем эволюции намеренное усложнение при одинаковой эффективности? Так что с селекцией тоже проблемы.
Возможно, к тому моменту, как будет дописана основная часть кода, я поменяю цели на более простые — например, на алгоритм нахождения индекса максимального элемента массива. Надеюсь, так у генетического алгоритма будет хоть какое-то ощутимое преимущество перед брутфорсным построением решения с перебором всех доступных комбинаций.
Если будет о каком успехе докладывать, будет и вторая часть статьи.
Закончим на этой задумчиво неопределенной ноте. Большое спасибо за уделенное время!
Генетическое программирование
Ниже вводятся различные способы кодирования (представления) программ: древовидное, линейное, графоподобное. Для них представлены соответствующие генетические операторы кроссинговера и мутации и виды фитнесс-функции. Описан метод символьной регрессии.
6.1. Функциональное и терминальное множество
6.1.1. Терминальное множество
Терминальное множество включает в себя: 1) внешние входы в программу; 2) используемые в программе константы; 3) функции, которые не имеют аргументов. Слово «терминал» используется, так как перечисленные выше объекты соответствуют терминальным (конечным, висячим) вершинам в древовидных структурах и соответствуют терминалам в формальных грамматиках. Терминал дает некоторое (численное) значение, не подвергаясь никаким входным значениям. У него нет входных аргументов, и он имеет нулевую «арность».
Следует отметить тесную связь внешних входов с обучающими выборками, которые часто используются в ГП. При этом каждая переменная (признак, фактор и т.п.) обучающей выборки соответствует своему терминалу. В этом смысле ГП отличается от других методов машинного обучения. Здесь переменная выборки не привязана прямо к входным данным – связь производится через терминалы. При необходимости терминал можно связать с другой внешней переменной.
6.1.2. Функциональное множество
Функциональное множество состоит из операторов (взятых у языков программирования) и различных функций. Оно может быть достаточно широким и включать типовые конструкции различных языков программирования, такие как:
Это также относится к константам. Во многих реализациях используется 256 узлов для представления функций и терминалов. Например, 56 используются для кодирования функций и 200 для констант. Важным свойством функционального множества является его замкнутость относительно принимаемых значений. То есть каждая функция должна принимать значения, которые могут принимать ее аргументы. Самым известным контрпримером является обычное деление, в котором второй аргумент (делитель) не может принимать нулевое значение. В этом случае может быть аварийный останов. Поэтому иногда используют «защищенное» деление, которое обрабатывает указанную ситуацию, возвращая в этом случае, например, некоторое большое число или нуль. Желательно, чтобы все функции (корень квадратный, логарифм и т.п.) имели подобную «защиту».
Генетическое программирование
Что такое генетическое программирование?
Уж не знаю почему ГА и ГП разделяют на разные области, но я к ним отношусь как к одному и тому же.
Единственное отличие ГП от ГА состоит в том, что каждая особь в популяции теперь кодирует не числовые характеристики, которые обеспечивают задаче оптимальность, а некоторую «программу», которая решает поставленную проблему.
Алгоритм работает по всем законам ГА, лишь при оценке новой особи происходит «исполнение» программы, а затем оценка её деятельности. Например, в задаче автоматического определения функции хромосома кодирует некоторую сложную, часто многопараметрическую функцию. При оценке происходит расчет закодированной функции на тестовой выборке входных значений, после чего, результаты расчетов сравниваются с тестовыми (экспериментальными) значениями искомой функции на представленной выборке, происходит расчет отклонения текущей функции от искомой, которое используется как оценка особи. Уменьшая отклонение, алгоритм находит неизвестную функцию, представленную тестовой выборкой.
В принципе, возможно создание и реальной программы на некотором простом языке (вроде ассемблера). Но тогда возникает проблема исполнения такой программы (чтоб не подвисла) и оценки результата.
Пока что я видел такие направления в представлении программ:
Деревья поколений.
В генетическом программировании особи из популяции представляют собой программы. Удобно представлять эти программы в виде деревьев, где функции представлены внутренними узлами, к которым в качестве входных параметров присоединены поддеревья. Листьями такого дерева будут константы, входные параметры задачи или директивные команды программы.
Пример простой программы-дерева:
Такое представление программ наглядно и легко реализуемо. Однако, работа с деревьями не всегда удобна при выполнении таких операторов, как кроссинговер и мутация. По сути, необходимо реализовать совершенно новые операторы.
Кроссинговер будет заключаться в подмене одного из поддеревьев первого родителя на какое-либо поддерево второго родителя.
Мутация будет выполнять случайное изменение одного из узлов дерева (например смена функции или константы).
Таким образом, использование деревьев влечет за собой несколько проблем: необходимость создания новых операторов мутации и кроссинговера; динамическая длина хромосомы, кодирующей дерево.
Терминальный алфавит, функциональный базис и их свойства.
Первый главный шаг в подготовке использования генетического программирования должен идентифицировать множество терминалов. Набор терминалов, наряду с набором функций, представляет собой компоненты, из которых будет создаваться компьютерная программа для полного или частичного решения проблемы.
Второй шаг заключается в определении функционального множества, элементы которого должны использоваться для генерации математических выражений. Каждая компьютерная программа (то есть, анализируемое дерево, математическое выражение) является композицией функций от множества функций F и терминалов из терминального множества T (в случае программ-функций это константы и переменные).
Множество возможных внутренних узлов (не листовых), используемых в деревьях синтаксического анализа, используемых в генетическом программировании, называется функциональным множеством:
Множество листовых узлов в деревьях синтаксического анализа, представляющих программы в генетическом программировании, называются терминальным множеством:
Функциональное и терминальное множества могут быть объединены в однородную группу С, при условии, что терминалы рассматриваются как функции с нулевой арностью: Пространством поиска генетического программирования является множество всех возможных рекурсивных композиций функций множества C.
В функциональном множестве могут быть применены арифметические, математические, булевы и другие функции. В терминальное множество могут войти переменные, константы или директивные команды.
Множества F и T должны обладать свойствами замыкания и достаточности.
ДОСТАТОЧНОСТЬ требует, чтобы функции из множества C были способны выразить решение поставленной задачи, то есть, чтобы решение принадлежало множеству всех возможных рекурсивных композиций функций из C. Однако доказать, что выбранное множество C достаточно, возможно лишь в редких случаях. Поэтому, при выборе этого множества, как и при выборе основных операций генетического алгоритма, приходится полагаться лишь на интуицию и экспериментальный опыт.