Войти
В области искусственного интеллекта генетическое программирование (GP) - это метод развития программ, начиная с популяции непригодных (обычно случайных) программ, подходящих для конкретной задачи, путем применения операций, аналогичных естественным генетическим процессам, к популяции программ. По сути, это эвристический метод поиска, часто описываемый как «восхождение на холм», то есть поиск оптимальной или, по крайней мере, подходящей программы в пространстве всех программ.
Операции: выбор наиболее приспособленных программ для воспроизводства (кроссовера) и мутации в соответствии с заранее заданной мерой пригодности, обычно с умением справиться с желаемой задачей. Операция кроссовера включает в себя замену случайных частей выбранных пар (родителей) для получения новых и разных потомков, которые становятся частью программ нового поколения. Мутация включает замену некоторой случайной части программы на другую случайную часть программы. Некоторые программы, не выбранные для воспроизведения, копируются из текущего поколения в новое поколение. Затем выбор и другие операции рекурсивно применяются к новому поколению программ.
Как правило, члены каждого нового поколения в среднем более приспособлены, чем представители предыдущего поколения, и лучшая из поколения программа часто лучше, чем лучшие из лучших программ предыдущих поколений. Прекращение рекурсии - это когда какая-то отдельная программа достигает заранее определенного уровня подготовки или пригодности.
Может случиться и часто случается, что конкретный прогон алгоритма приводит к преждевременной сходимости к некоторому локальному максимуму, который не является глобально оптимальным или даже хорошим решением. Для получения очень хорошего результата обычно требуется несколько запусков (от десятков до сотен). Также может быть необходимо увеличить размер исходной популяции и изменчивость особей, чтобы избежать патологий.
Первая запись о предложении разработать программы, вероятно, принадлежит Алану Тьюрингу в 1950 году. До публикации книги Джона Холланда «Адаптация в естественных и искусственных системах», в которой изложены теоретические и эмпирические основы науки, прошло 25 лет. В 1981 году Ричард Форсайт продемонстрировал успешную эволюцию небольших программ, представленных в виде деревьев, для классификации улик на месте преступления для Министерства внутренних дел Великобритании.
Хотя идея разработки программ изначально была на компьютерном языке Lisp был распространен среди студентов Джона Холланда, и только после того, как они организовали первую конференцию по генетическим алгоритмам в Питтсбурге, Найкл Крамер опубликовал развитые программы на двух специально разработанных языках, которые включали первое утверждение современного «древовидного» подхода. Генетическое программирование (то есть процедурные языки, организованные в древовидные структуры и управляемые соответствующим образом определенными операторами GA). В 1988 году Джон Коза (также аспирант Джона Холланда) запатентовал свое изобретение ГА для эволюции программ. За этим последовала публикация на Международной объединенной конференции по искусственному интеллекту IJCAI-89.
После этого Коза выпустил 205 публикаций по «Генетическому программированию» (ГП), название придумано Дэвидом Голдбергом, также докторантом Джона Голландия. Тем не менее, именно серия из 4 книг Козы, начиная с 1992 года, с сопровождающими видео, действительно установила GP. Впоследствии количество публикаций с библиографией по генетическому программированию резко увеличилось, превысив 10 000 статей. В 2010 году Коза перечислил 77 результатов, в которых генетическое программирование было конкурентоспособным среди людей.
В 1996 году Коза начал ежегодную конференцию по генетическому программированию, за которой в 1998 году последовала ежегодная конференция EuroGP и первая книга из серии GP под редакцией Коза. В 1998 г. был выпущен первый учебник для ВОП. GP продолжал процветать, что привело к появлению первого специализированного журнала GP, а три года спустя (2003 г.) Рик Риоло основал ежегодный семинар по теории и практике генетического программирования (GPTP). Статьи по генетическому программированию продолжают публиковаться на различных конференциях и в связанных журналах. Сегодня существует девятнадцать книг по GP, в том числе несколько для студентов.
Ранние работы, заложившие основу для текущих тем и приложений генетического программирования, разнообразны и включают программное обеспечение синтез и ремонт, прогнозное моделирование, интеллектуальный анализ данных, финансовое моделирование, программные датчики, проектирование и обработка изображений. Приложения в некоторых областях, таких как дизайн, часто используют промежуточные представления, такие как сотовое кодирование Фреда Грюау. Промышленное внедрение было значительным в нескольких областях, включая финансы, химическую промышленность, биоинформатику и сталелитейную промышленность.
Функция, представленная в виде древовидной структуры GP развивает компьютерные программы, традиционно представленные в памяти как древовидные структуры. Деревья можно легко оценить рекурсивным способом. Каждый узел дерева имеет операторную функцию, а каждый конечный узел имеет операнд, что упрощает разработку и оценку математических выражений. Таким образом, GP традиционно поддерживает использование языков программирования, которые естественным образом воплощают древовидные структуры (например, Lisp ; другие языки функционального программирования также подходят).
Не-древовидные представления были предложены и успешно реализованы, например, линейное генетическое программирование, которое подходит для более традиционных императивных языков [см., Например, Banzhaf et al.. (1998)]. Коммерческое программное обеспечение GP Discipulus использует автоматическую индукцию двоичного машинного кода («AIM») для достижения лучшей производительности. µGP использует направленные мультиграфы для создания программ, которые полностью используют синтаксис данного языка ассемблера. Другие программные представления, в отношении которых проводились значительные исследования и разработки, включают программы для виртуальных машин на основе стека и последовательности целых чисел, которые отображаются на произвольные языки программирования с помощью грамматик. Декартово генетическое программирование - еще одна форма GP, который использует представление графа вместо обычного представления на основе дерева для кодирования компьютерных программ.
Большинство представлений имеют структурно неэффективный код (интроны ). Такие некодирующие гены могут показаться бесполезными, потому что они не влияют на производительность отдельного человека. Однако они изменяют вероятности порождения другого потомства с помощью операторов вариации и, таким образом, изменяют индивидуальные вариационные свойства. Эксперименты, кажется, показывают более быструю конвергенцию при использовании программных представлений, которые допускают такие некодирующие гены, по сравнению с программными представлениями, которые не имеют никаких некодирующих генов.
Выбор - это процесс, посредством которого некоторые люди выбираются из нынешнего поколения, которые станут родителями для следующего поколения. Люди отбираются вероятностно, так что у более эффективных людей больше шансов быть отобранным. Наиболее часто используемый метод выбора в GP - это турнирный выбор, хотя другие методы, такие как пропорциональный выбор по пригодности, выбор лексики и другие, продемонстрировали лучшую эффективность для многих задач GP.
Элитарность, которая включает посев следующего поколения лучших индивидов (или лучших n индивидов) из текущего поколения, - это метод, который иногда используется для предотвращения регресса.
Различные генетические операторы (например, кроссовер и мутация) применяются к особям, выбранным на этапе отбора, описанном выше, для разведения новых особей. Скорость, с которой применяются эти операторы, определяет разнообразие в популяции.
Переверните один или несколько битов из предыдущего потомка для создания нового потомка или поколения.
GP успешно используется в качестве инструмента автоматического программирования, инструмента машинного обучения и механизма автоматического решения проблем. GP особенно полезен в тех областях, где точная форма решения неизвестна заранее или приближенное решение является приемлемым (возможно, потому, что найти точное решение очень сложно). Некоторые из приложений GP: аппроксимация кривой, моделирование данных, символическая регрессия, выбор признаков, классификация и т. Д. Джон Р. Коза упоминает 76 случаев, когда генетическое программирование смогло произвести результаты, которые конкурируют с результатами, созданными человеком (так называемые результаты конкуренции с человеком). С 2004 года ежегодная Конференция по генетическим и эволюционным вычислениям (GECCO) проводит конкурс Human Competitive Awards (называемый Humies), где денежные премии вручаются за результаты, полученные с помощью любой формы генетических и эволюционных вычислений. На протяжении многих лет GP завоевала множество наград в этом конкурсе.
Мета-генетическое программирование - это предлагаемый мета-обучение метод развития системы генетического программирования с использованием самого генетического программирования. Это предполагает, что хромосомы, кроссовер и мутации сами по себе эволюционировали, поэтому, как и их реальным аналогам, следует позволить изменяться самостоятельно, а не определяться человеком-программистом. Meta-GP был официально предложен Юргеном Шмидхубером в 1987 году. Eurisko Дуга Лената - это более ранняя попытка, которая может быть той же техникой. Это рекурсивный, но завершающий алгоритм, позволяющий избежать бесконечной рекурсии. В подходе к метагенетическому программированию «автоконструктивной эволюции» методы производства и изменения потомства закодированы в самих развивающихся программах, а программы выполняются для создания новых программ, которые будут добавлены к популяции.
Критики этой идеи часто говорят, что этот подход слишком широк. Однако можно было бы ограничить критерий пригодности общим классом результатов и, таким образом, получить усовершенствованный GP, который более эффективно давал бы результаты для подклассов. Это могло бы принять форму мета-развитого GP для создания алгоритмов ходьбы человека, которые затем используются для развития человеческого бега, прыжков и т. Д. Критерий пригодности, применяемый к мета-GP, будет просто критерием эффективности.
