В области искусственного интеллекта генетическое программирование ( ГП ) представляет собой метод разработки программ на основе популяции непригодных (обычно случайных) программ, пригодных для выполнения конкретной задачи, путем применения к популяции программ операций, аналогичных естественным генетическим процессам.
Операции: выбор наиболее приспособленных программ для воспроизводства (кроссинговер), репликация и/или мутация в соответствии с предопределенной мерой приспособленности, обычно мастерством в желаемой задаче. Операция кроссинговер включает обмен указанными частями выбранных пар (родителей) для получения нового и отличного потомства, которое становится частью нового поколения программ. Некоторые программы, не выбранные для воспроизводства, копируются из текущего поколения в новое поколение. Мутация включает замену некоторой случайной части программы некоторой другой случайной частью программы. Затем выбор и другие операции рекурсивно применяются к новому поколению программ.
Обычно члены каждого нового поколения в среднем более приспособлены, чем члены предыдущего поколения, и лучшая программа поколения часто лучше, чем лучшие программы поколения предыдущих поколений. Окончание эволюции обычно происходит, когда некоторая индивидуальная программа достигает предопределенного уровня мастерства или приспособленности.
Может и часто случается, что конкретный запуск алгоритма приводит к преждевременной сходимости к некоторому локальному максимуму, который не является глобально оптимальным или даже хорошим решением. Обычно для получения очень хорошего результата требуется несколько запусков (десятки или сотни). Также может быть необходимо иметь большой начальный размер популяции и изменчивость особей, чтобы избежать патологий.
Первая запись предложения об эволюции программ, вероятно, принадлежит Алану Тьюрингу в 1950 году. [1] Прошло 25 лет, прежде чем вышла работа Джона Холланда «Адаптация в естественных и искусственных системах», в которой были изложены теоретические и эмпирические основы этой науки. В 1981 году Ричард Форсайт продемонстрировал успешную эволюцию небольших программ, представленных в виде деревьев, для классификации улик с места преступления для Министерства внутренних дел Великобритании. [2]
Хотя идея эволюционирующих программ, изначально на языке программирования Lisp , была распространена среди студентов Джона Холланда [3] , только после того, как они организовали первую конференцию по генетическим алгоритмам (ГА) в Питтсбурге, Нихаэль Крамер [4] опубликовал эволюционирующие программы на двух специально разработанных языках, которые включали первое утверждение современного «древовидного» генетического программирования (то есть процедурных языков, организованных в древовидные структуры и управляемых соответствующим образом определенными ГА-операторами). В 1988 году Джон Коза (также аспирант Джона Холланда) запатентовал свое изобретение ГА для эволюции программ. [5] За этим последовала публикация на Международной совместной конференции по искусственному интеллекту IJCAI-89. [6]
Коза последовал за этим с 205 публикациями по «Генетическому программированию» (ГП), название придумал Дэвид Голдберг, также аспирант Джона Холланда. [7] Однако именно серия из 4 книг Коза, начавшаяся в 1992 году [8] с сопровождающими видео, [9] действительно утвердила ГП. Впоследствии произошло огромное расширение числа публикаций в Библиографии генетического программирования, превысившее 10 000 записей. [10] В 2010 году Коза [11] перечислил 77 результатов, в которых генетическое программирование было конкурентоспособным для человека.
В 1996 году Коза начал проводить ежегодную конференцию по генетическому программированию [12] , за которой в 1998 году последовала ежегодная конференция EuroGP [13] и первая книга [14] в серии GP под редакцией Коза. В 1998 году также вышел первый учебник по GP. [15] GP продолжала процветать, что привело к появлению первого специализированного журнала по GP [16] , а три года спустя (2003) Рик Риоло основал ежегодный семинар по теории и практике генетического программирования (GPTP). [17] [18] Статьи по генетическому программированию продолжают публиковаться на различных конференциях и в связанных журналах. Сегодня существует девятнадцать книг по GP, включая несколько для студентов. [15]
Ранние работы, которые заложили основу для современных тем и приложений генетического программирования, разнообразны и включают в себя синтез и исправление программного обеспечения, предиктивное моделирование, интеллектуальный анализ данных, [19] финансовое моделирование, [20] мягкие датчики, [21] проектирование, [22] и обработку изображений. [23] Приложения в некоторых областях, таких как проектирование, часто используют промежуточные представления, [24] такие как клеточное кодирование Фреда Груау. [25] Промышленное внедрение было значительным в нескольких областях, включая финансы, химическую промышленность, биоинформатику [26] [27] и сталелитейную промышленность. [28]
GP развивает компьютерные программы, традиционно представленные в памяти в виде древовидных структур . [29] Деревья можно легко оценить рекурсивным способом. Каждый внутренний узел имеет операторную функцию, а каждый конечный узел имеет операнд, что делает математические выражения простыми для развития и оценки. Таким образом, традиционно GP предпочитает использовать языки программирования , которые естественным образом воплощают древовидные структуры (например, Lisp ; другие функциональные языки программирования также подходят).
Были предложены и успешно реализованы недревовидные представления, такие как линейное генетическое программирование , которое, возможно, подходит для более традиционных императивных языков . [30] [31] Коммерческое программное обеспечение GP Discipulus использует автоматическую индукцию двоичного машинного кода («AIM») [32] для достижения лучшей производительности. μGP [33] использует направленные мультиграфы для генерации программ, которые полностью используют синтаксис данного языка ассемблера . Программирование с множественными выражениями использует трехадресный код для кодирования решений. Другие представления программ, по которым были проведены значительные исследования и разработки, включают программы для виртуальных машин на основе стека, [34] [35] [36] и последовательности целых чисел, которые отображаются в произвольные языки программирования с помощью грамматик. [37] [38] Декартово генетическое программирование является другой формой GP, которая использует графовое представление вместо обычного древовидного представления для кодирования компьютерных программ.
Большинство представлений имеют структурно неэффективный код ( интроны ). Такие некодирующие гены могут показаться бесполезными, поскольку они не оказывают никакого влияния на производительность какой-либо одной особи. Однако они изменяют вероятности генерации различного потомства под действием операторов вариации и, таким образом, изменяют вариационные свойства особи . Эксперименты, по-видимому, показывают более быструю сходимость при использовании программных представлений, которые допускают такие некодирующие гены, по сравнению с программными представлениями, которые не имеют никаких некодирующих генов. [39] [40] Инстанцирования могут иметь как деревья с интронами, так и без них; последние называются каноническими деревьями. Вводятся специальные канонические операторы кроссинговера, которые поддерживают каноническую структуру родителей в их потомках.
Отбор — это процесс, в ходе которого из текущего поколения выбираются определенные особи, которые будут служить родителями для следующего поколения. Особи выбираются вероятностно, так что у особей с лучшими показателями больше шансов быть выбранными. [18] Наиболее часто используемый метод отбора в GP — это турнирный отбор , хотя другие методы, такие как пропорциональный отбор по приспособленности , отбор по лексике [41] и другие, как было показано, работают лучше для многих задач GP.
Элитизм, который подразумевает заселение следующего поколения лучшими особями (или лучшими n особями) текущего поколения, — это метод, который иногда применяется для избежания регресса.
В генетическом программировании из популяции выбираются два подходящих индивида, которые становятся родителями для одного или двух детей. В генетическом программировании деревьев эти родители представлены в виде перевернутых деревьев типа lisp, с их корневыми узлами наверху. При кроссинговере поддеревьев в каждом родителе поддерево выбирается случайным образом. (Выделено желтым в анимации.) В корневом отдающем родителе (в анимации слева) выбранное поддерево удаляется и заменяется копией случайно выбранного поддерева из другого родителя, чтобы получить новое дочернее дерево.
Иногда используется кроссовер двух дочерних деревьев, в этом случае удаленное поддерево (в анимации слева) не просто удаляется, а копируется в копию второго родителя (здесь справа), заменяя (в копии) его случайно выбранное поддерево. Таким образом, этот тип кроссовера поддеревьев берет два подходящих дерева и генерирует два дочерних дерева.
Некоторые особи, отобранные по критериям приспособленности, не участвуют в кроссинговере, но копируются в следующее поколение, что похоже на бесполое размножение в естественном мире. Они могут быть в дальнейшем подвержены мутации.
В генетическом программировании существует множество типов мутаций. Они начинаются с подходящего синтаксически правильного родителя и стремятся случайным образом создать синтаксически правильного потомка. В анимации поддерево выбирается случайным образом (выделено желтым). Оно удаляется и заменяется случайно сгенерированным поддеревом.
Другие операторы мутации выбирают лист (внешний узел) дерева и заменяют его случайно выбранным листом. Другая мутация заключается в случайном выборе функции (внутреннего узла) и замене ее другой функцией с той же арностью (количеством входов). Мутация подъема случайным образом выбирает поддерево и заменяет его поддеревом внутри себя. Таким образом, мутация подъема гарантированно сделает потомка меньше. Замена листьев и функции с той же арностью гарантирует, что потомок будет того же размера, что и родитель. В то время как мутация поддерева (в анимации) может, в зависимости от функции и конечных наборов, иметь смещение либо к увеличению, либо к уменьшению размера дерева. Другие мутации на основе поддеревьев пытаются тщательно контролировать размер заменяющего поддерева и, следовательно, размер дочернего дерева.
Аналогично существует множество типов мутаций линейного генетического программирования, каждый из которых стремится гарантировать, что мутировавший потомок по-прежнему будет синтаксически правильным.
GP успешно использовался в качестве автоматического инструмента программирования , инструмента машинного обучения и автоматического механизма решения проблем. [18] GP особенно полезен в областях, где точная форма решения заранее неизвестна или приемлемо приблизительное решение (возможно, потому что найти точное решение очень сложно). Некоторые из приложений GP — это подгонка кривых, моделирование данных, символическая регрессия , выбор признаков , классификация и т. д. Джон Р. Коза упоминает 76 случаев, когда генетическое программирование смогло дать результаты, которые конкурентоспособны с результатами, полученными человеком (называемые результатами, конкурентоспособными с человеком). [42] С 2004 года ежегодная Конференция по генетическим и эволюционным вычислениям ( GECCO ) проводит конкурс Human Competitive Awards (называемый Humies), [43] где денежные премии вручаются за результаты, конкурентоспособные с человеком, полученные с помощью любой формы генетических и эволюционных вычислений. GP выиграл множество наград в этом конкурсе за эти годы.
Метагенетическое программирование — это предлагаемая методика метаобучения для эволюции генетической программной системы с использованием самого генетического программирования. Она предполагает, что хромосомы, кроссинговер и мутация сами эволюционировали, поэтому, как и их реальные аналоги, им должно быть разрешено изменяться самостоятельно, а не определяться программистом-человеком. Мета-ГП был официально предложен Юргеном Шмидхубером в 1987 году. [44] Eurisko Дуга Лената — это более ранняя попытка, которая может быть той же методикой. Это рекурсивный, но завершающийся алгоритм, позволяющий избежать бесконечной рекурсии. В подходе «автоконструктивной эволюции» к метагенетическому программированию методы производства и изменения потомства кодируются в самих эволюционирующих программах, и программы выполняются для создания новых программ, которые будут добавлены в популяцию. [35] [45]
Критики этой идеи часто говорят, что этот подход слишком широк по охвату. Однако, возможно, можно ограничить критерий пригодности общим классом результатов и таким образом получить развитый ГП, который будет более эффективно выдавать результаты для подклассов. Это может принять форму метаразвитого ГП для создания алгоритмов ходьбы человека, который затем используется для эволюции бега, прыжков и т. д. Критерий пригодности, применяемый к мета ГП, будет просто критерием эффективности.
{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: others (link)