Генетическое программирование - Genetic programming

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

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

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

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

История

Первое упоминание о предложении развивать программы, вероятно, принадлежит Алану Тьюрингу в 1950 году. До публикации книги Джона Холланда «Адаптация в естественных и искусственных системах», в которой изложены теоретические и эмпирические основы науки, произошел разрыв в 25 лет. В 1981 году Ричард Форсайт продемонстрировал успешную эволюцию небольших программ, представленных в виде деревьев, для классификации улик на месте преступления для Министерства внутренних дел Великобритании.

Хотя идея развития программ, первоначально на компьютерном языке Lisp , была актуальна среди студентов Джона Холланда, только когда они организовали первую конференцию по генетическим алгоритмам (GA) в Питтсбурге, Найкл Крамер опубликовал развитые программы на двух специально разработанных языках, которые включала первое утверждение современного «древовидного» генетического программирования (то есть процедурных языков, организованных в древовидные структуры и управляемых соответствующим образом определенными GA-операторами). В 1988 году Джон Коза (также аспирант Джона Холланда) запатентовал свое изобретение ГА для эволюции программ. Затем последовала публикация на Международной совместной конференции по искусственному интеллекту IJCAI-89.

После этого Коза выпустил 205 публикаций по теме «Генетическое программирование» (ГП), название которой придумал Дэвид Голдберг, также аспирант Джона Холланда. Тем не менее, именно серия из 4 книг Козы, начиная с 1992 года, с сопровождающими видео, действительно установила GP. Впоследствии количество публикаций с библиографией по генетическому программированию резко увеличилось, превысив 10 000 статей. В 2010 году Коза перечислил 77 результатов, в которых генетическое программирование было конкурентоспособным среди людей.

В 1996 году Коза начал ежегодную конференцию по генетическому программированию, за которой в 1998 году последовала ежегодная конференция EuroGP и первая книга из серии GP под редакцией Коза. В 1998 г. был выпущен первый учебник для ВОП. GP продолжал процветать, что привело к появлению первого специализированного журнала GP, а три года спустя (2003 г.) Рик Риоло основал ежегодный семинар по теории и практике генетического программирования (GPTP). Статьи по генетическому программированию продолжают публиковаться на различных конференциях и в связанных журналах. Сегодня существует девятнадцать книг по GP, в том числе несколько для студентов.

Фундаментальная работа в GP

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

Методы

Представление программы

Функция, представленная в виде древовидной структуры

GP развивает компьютерные программы, традиционно представленные в памяти как древовидные структуры . Деревья можно легко оценить рекурсивным способом. Каждый узел дерева имеет операторную функцию, а каждый конечный узел имеет операнд, что упрощает разработку и оценку математических выражений. Таким образом, GP традиционно выступает за использование языков программирования, которые естественным образом воплощают древовидные структуры (например, Lisp ; другие языки функционального программирования также подходят).

Были предложены и успешно реализованы не-древовидные представления, такие как линейное генетическое программирование, которое подходит для более традиционных императивных языков [см., Например, Banzhaf et al. (1998)]. В коммерческом программном обеспечении GP Discipulus используется автоматическая индукция двоичного машинного кода («AIM») для достижения лучшей производительности. µGP использует направленные мультиграфы для создания программ, которые полностью используют синтаксис данного языка ассемблера . Другие программные представления, в отношении которых проводились значительные исследования и разработки, включают программы для виртуальных машин на основе стека и последовательности целых чисел, которые отображаются на произвольные языки программирования с помощью грамматик. Декартово генетическое программирование - это еще одна форма GP, которая использует представление графа вместо обычного представления на основе дерева для кодирования компьютерных программ.

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

Выбор

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

Элитарность, которая включает посев следующего поколения лучших индивидов (или лучших n индивидов) из текущего поколения, - это метод, который иногда используется для предотвращения регресса.

Кроссовер

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

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

Мутация

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

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

Анимация создания генетического дочернего элемента программирования путем мутации родителя, удаляя поддерево и заменяя его случайным кодом.

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

Приложения

GP успешно используется в качестве инструмента автоматического программирования , машинного обучения и механизма автоматического решения проблем. GP особенно полезен в тех областях, где точная форма решения неизвестна заранее или приближенное решение приемлемо (возможно, потому, что найти точное решение очень сложно). Некоторыми из приложений GP являются построение кривой, моделирование данных, символическая регрессия , выбор признаков , классификация и т. Д. Джон Р. Коза упоминает 76 случаев, когда генетическое программирование могло давать результаты, которые конкурируют с результатами, созданными человеком (так называемые человеческие -конкурентные результаты). С 2004 года ежегодная Конференция по генетическим и эволюционным вычислениям ( GECCO ) проводит конкурс Human Competitive Awards (называемый Humies), где денежные премии вручаются за результаты, полученные с помощью любой формы генетических и эволюционных вычислений. На протяжении многих лет GP завоевала множество наград в этом конкурсе.

Мета-генетическое программирование

Мета-генетическое программирование является предлагаемой метой обучения методики эволюционирует генетическую систему программирования с использованием самого генетического программирования. Это предполагает, что хромосомы, кроссовер и мутации сами по себе эволюционировали, поэтому, как и их реальным аналогам, следует разрешить изменяться сами по себе, а не определять человеческий программист. Мета-GP был официально предложен Юргеном Шмидхубером в 1987 году Дуги Ленат «s EURISKO является ранее усилием , которое может быть тем же техником. Это рекурсивный, но завершающий алгоритм, позволяющий избежать бесконечной рекурсии. В подходе к метагенетическому программированию «автоконструктивной эволюции» методы производства и изменения потомства закодированы в самих развивающихся программах, а программы выполняются для создания новых программ, которые будут добавлены к популяции.

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

Смотрите также

использованная литература

внешние ссылки