Курс эволюционных вычислений
Блок 4) Генетическое программирование
Охватите основные темы генетического программирования и примените их к задаче анализа временных рядов
Здравствуйте и добро пожаловать обратно на этот полный курс по эволюционным вычислениям! В этом посте мы начнем и закончим Раздел 4, Генетическое программирование. В предыдущем посте мы закончили Блок 3, Генетические алгоритмы, применив алгоритм для изменения весов нейронной сети для анализа временных рядов. Я настоятельно рекомендую сначала прочитать этот пост, поскольку мы попытаемся решить ту же проблему с помощью генетического программирования:
В этом посте мы рассмотрим краткий обзор генетического программирования и того, чем оно отличается от стандартных генетических алгоритмов с точки зрения представления хромосомы.
Содержание
- Разница в представлении
- Муравьиная тропа Санте-Фе
- Постановка проблемы
- Операторы кроссовера
- Операторы мутации
- Приложение - Анализ временных рядов
Разница в представлении
Генетическое программирование - это фактически подмножество генетических алгоритмов; однако основное различие между ними - представление хромосомы. Стандартные генетические алгоритмы решают задачи оптимизации, в которых фенотип является точкой или вектором, но теперь фенотип в генетическом программировании представляет собой древовидную грамматику.
Если вы не знали, все языки программирования построены на грамматике формы Бэкуса-Наура (BNF), что, если вы не посещали какие-либо классы теории автоматов, просто означает, что каждый язык имеет определенный набор правила для настройки инструкций, которые компилятор использует, чтобы определить, можно ли запускать код. Думайте об этом, как если бы в стандартном английском языке грамматика английского языка рассказывала вам, как собирать слова вместе и структурировать предложения. Например, «Tom is…», у нас есть «существительный глагол…», который из английской грамматики говорит нам, что у нас не может быть глагола после глагола «is», а может быть прилагательное, существительное или наречие. В программировании наша IDE сообщает нам, когда у нас возникает «синтаксическая ошибка», когда мы забываем ключевое слово, потому что она знает, что должно произойти до или после, на основе этой специфической для языка грамматики BNF. Поскольку существует определенная структура программ, сочетание генетических алгоритмов и грамматики породило генетическое программирование, которое впервые появилось на сцене для развития наборов инструкций, называемых программами.
В дополнение к различию фенотипа между генетическим программированием и стандартными генетическими алгоритмами, каждый человек имеет возможность увеличивать или уменьшать свой генотип, добавляя больше терминалов и инструкций. Как указывалось ранее, генетическое программирование основано на древовидной структуре, что означает, что ему нужна собственная грамматика, основанная на теории вычислений, например, терминальный набор, функция и правила перехода. В качестве простого примера ниже у нас есть таблица истинности XOR с входами и целевыми выходами.
Учитывая грамматику, операторы и терминалы, мы хотим разработать древовидный набор инструкций для решения этой проблемы. Ниже у нас есть возможное решение этой проблемы с использованием древовидной структуры, полученной в результате генетического программирования.
Обратите внимание на то, насколько древовидная структура похожа на Дерево решений. Одно из многих приложений генетического программирования состоит в том, чтобы на самом деле развить деревья решений и поведения для классификации или игры.
Муравьиная тропа Санте-Фе
Один из первых и наиболее известных примеров генетического программирования находится в области робототехники. Проблема была известна как «Муравьиная тропа Санте-Фе». Проблема заключалась в том, что, учитывая среду с едой, размещенной на тропе вокруг карты, как можно увидеть ниже, максимальное количество собранной еды с ограниченным количеством энергии, предпринятых шагов. Проблема была решена с помощью генетического программирования путем разработки набора инструкций для муравья.
Модель генетического программирования оказалась чрезвычайно успешной в развитии дерева грамматики, основанного на if и else, для принятия направленных шагов на основе определенных входных данных.
Постановка проблемы
Во всех эволюционных вычислениях есть два основных предварительных этапа, о которых необходимо позаботиться независимо от выбранного алгоритма:
- Создание начальной популяции
- Разработка фитнес-функции
В отличие от стандартных генетических алгоритмов, генетическое программирование не может создавать начальную популяцию равномерно случайным образом из домена. Вместо этого он должен следовать структуре грамматики, зависящей от проблемы. Для этого нам сначала нужно определить нашу грамматику BNF для проблемы. Затем нам нужно установить минимальную и максимальную глубину нашего дерева, где глубина обозначает количество слоев в дереве. Определение минимума и максимума влияет только на начальную популяцию, а это означает, что все особи начального поколения будут находиться между минимальным и максимальным глубинными слоями, в то время как более поздние особи могут уменьшаться или расти.
Чтобы создать дерево для каждого человека, мы случайным образом выбираем функциональный элемент из грамматики и разветвляемся, случайным образом выбирая оконечные или функциональные элементы. Как и в генетических алгоритмах для ограниченных задач, случайное создание индивидов с использованием этой процедуры может привести к появлению некоторых нежелательных первоначальных индивидов, а именно тех, у которых глубина ниже минимальной или больше максимальной. Для этого мы отбрасываем этих особей и продолжаем отбор проб, пока не получим особь в этом диапазоне.
В зависимости от решаемой проблемы функция пригодности может иметь ряд способов определения значений пригодности. Что касается робототехники, могут быть некоторые тестовые примеры, которые необходимо оценить для оценки того, насколько хорошо работает агент, или для поведенческих деревьев для игрового ИИ, вы можете использовать коэволюцию. Как и в случае со стандартными деревьями поведения и решений, мы хотим снизить сложность модели, чтобы она могла хорошо обобщаться на новые входные данные, поэтому нам нужен способ наказать слишком сложные модели. В генетическом программировании мы можем предотвратить развитие сложных моделей, оценивая раздувание модели, которое относится к тому, когда дерево добавляет больше конечных узлов и глубины, лишь слегка уменьшая значения приспособленности.
Операторы кроссовера
Операторы кроссовера в генетическом программировании довольно интуитивно понятны. Как видно из первого рисунка ниже, учитывая двух родителей, мы случайным образом выбираем точку в каждом из них и пересекаем это поддерево в этой точке, чтобы создать потомство. Это можно сделать либо для одного потомства, что более интуитивно понятно, для двух потомков, когда вы получаете первую половину одного родителя и вторую половину другого.
На ранних стадиях эволюционных вычислений кроссовер в генетическом программировании обычно никогда не выполнялся из-за проблемы перестановки. Проблема перестановки похожа на проблему выбора спаривания, описанную в Разделе 3, Часть 2, Расширенные концепции. У вас могут быть два родителя с одинаковыми показателями пригодности, но их архитектура настолько различается, что их пересечение приводит к очень плохим людям. Вот почему в первые годы эволюционного программирования кроссовер никогда не выполнялся, только мутация. Однако по мере того, как область расширялась, возникали решения этих проблем. Одно из наиболее распространенных решений - скрещивать только похожих людей; но теперь проблема состоит в том, чтобы определить, кто похож, поскольку вы не можете использовать евклидово расстояние. Один из способов - реализовать генетический маркер, позволяющий воспроизводить людей, у которых есть похожие генетические маркеры или поддеревья.
Операторы мутации
Как и кроссовер, мутация для генетического программирования чрезвычайно интуитивна. Как мы видим ниже, существует много разных способов осуществить мутацию. В левом верхнем углу у нас есть исходное дерево. Наша первая мутация - это переключение функционального узла, при котором мы переключаем случайный функциональный узел на другой жизнеспособный узел. Затем у нас есть переключение оконечного узла, при котором мы переключаем случайный оконечный узел на другой жизнеспособный узел. Затем у нас есть перестановка аргументов терминального термина. Под усечением понимается сжатие дерева путем случайного удаления одного функционального узла. Мы также можем добавить случайный гауссовский шум к существующим числовым значениям. Наконец, мы можем выращивать наши деревья, случайным образом вводя один новый функциональный узел.
Приложение - Анализ временных рядов
Поскольку фенотип алгоритмов генетического программирования основан на дереве, он идеально подходит для развития дерева поведения или принятия решений во многих классификационных или игровых задачах ИИ. Однако его также можно использовать для выполнения регрессии. В нашем приложении мы будем оценивать ту же проблему временных рядов, что и в предыдущем посте. Чтобы не повторяться о постановке задачи и динамике, прочтите мой предыдущий пост:
Наша настройка задачи будет такой же, как и раньше, перебрать все возможные размеры окон и выбрать лучшую модель из каждого размера окна из данных проверки в качестве окончательной модели, которая будет оцениваться на данных тестового набора. Итак, программирование модели генетического программирования с нуля требует множества предварительных внеклассных занятий, таких как теория автоматов. Я не буду выполнять алгоритм с нуля. Вместо этого я буду использовать gplearn, бесплатную библиотеку Python, разработанную специально для алгоритмов генетического программирования как для классификации, так и для регрессии.
Вот как мы импортируем и запускаем алгоритм. Есть много других гиперпараметров, которые мы также можем использовать, но для простоты я ограничил его следующим:
Я заметил, что успех алгоритма в значительной степени зависит от исходной популяции, поэтому я запускал алгоритм четыре раза для каждого размера окна и сохранял лучшую модель из прогонов. К сожалению, gplearn не имеет механизма ранней остановки, поэтому данные проверки использовались только для определения окончательной модели; однако, чтобы имитировать раннюю остановку, максимальное количество поколений для эволюции было ограничено до 100, чтобы предотвратить переобучение обучающих данных. Вот окончательные результаты после запуска скрипта:
Из результатов мы видим, что лучшая модель имела размер окна 8. Для сравнения мы будем использовать результаты из предыдущего поста, в котором использовались генетический алгоритм и обратное распространение для обучения нейронной сети для решения той же проблемы. Пожалуйста, просмотрите предыдущий пост, связанный вверху, для получения дополнительной информации. Оптимальный размер окна модели для генетического алгоритма и стандартного обратного распространения ошибки был 5 и 3, что сильно отличалось от 8 для генетического программирования. Что касается ошибки проверки лучшей модели на размер окна, среднее значение MSE больше, чем генетический алгоритм и обратное распространение; однако стандартное отклонение намного ниже, на 57% меньше, чем при обратном распространении, и на 42% меньше, чем при генетическом алгоритме. Что касается ошибки тестового набора, MSE была больше, чем генетический алгоритм и обратное распространение; однако это приемлемо с точки зрения адекватности, всего на 10% хуже, чем генетический алгоритм, но не предпочтительнее по сравнению с двумя предыдущими методами.
Для визуальных элементов вот общий прогноз для всего набора данных с использованием лучшей модели с размером окна 8:
Вот реальное дерево регрессии для лучшей модели:
Окончательный код
Код, используемый для этого сообщения, относительно короткий по сравнению с остальными сообщениями; однако вот моя страница GitHub с полным сценарием и изображением окончательного дерева регрессии:
Заключение
На этом завершается весь блок генетического программирования! Это определенно была самая короткая из серии, поскольку для разработки с нуля требовалось знание теории автоматов, поэтому мне пришлось использовать стороннюю библиотеку.
Основное различие между стандартными генетическими алгоритмами и генетическим программированием заключается в представлении хромосомы, как фенотипа, так и генотипа. Фенотип моделей генетического программирования - это древовидные графы, в которых геном может уменьшаться или увеличиваться за счет добавления новых конечных узлов и функций.
Что касается приложения, мы рассмотрели ту же проблему временных рядов, что и в предыдущем сообщении, за исключением использования библиотеки gplearn python для развития основного уравнения набора данных. Результаты показали, что алгоритм успешно предсказал набор данных временных рядов; однако после сравнения результатов с двумя методами в предыдущем посте он не является предпочтительным перед ними. Следите за обновлениями, и мы увидим следующий пост, где мы начнем Раздел 5) Эволюционное программирование!
