stringtranslate.com

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

В области искусственного интеллекта генетическое программирование ( GP ) — это метод разработки программ, начиная с популяции непригодных (обычно случайных) программ, пригодных для конкретной задачи, путем применения к совокупности программ операций, аналогичных естественным генетическим процессам.

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

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

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

История

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

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

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

В 1996 году Коза начал ежегодную конференцию по генетическому программированию [12] , за которой в 1998 году последовала ежегодная конференция EuroGP [13] и первая книга [14] из серии GP под редакцией Козы. В 1998 году также вышел первый учебник общей практики. [15] GP продолжала процветать, что привело к появлению первого специализированного журнала по GP [16] , а три года спустя (2003 г.) Рик Риоло учредил ежегодный семинар по теории и практике генетического программирования (GPTP). [17] [18] Статьи по генетическому программированию продолжают публиковаться на различных конференциях и в связанных с ними журналах. Сегодня существует девятнадцать книг общей практики, в том числе несколько для студентов. [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 людьми) из текущего поколения, является методом, который иногда используется, чтобы избежать регресса.

Кроссовер

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

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

Репликация

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

Мутация

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

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

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

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

Приложения

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

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

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

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

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

Рекомендации

  1. ^ «Вычислительная техника и интеллект». www.cs.bham.ac.uk. _ Проверено 19 мая 2018 г.
  2. ^ «BEAGLE: Дарвиновский подход к распознаванию образов» . www.cs.bham.ac.uk. _ Проверено 19 мая 2018 г.
  3. ^ Личное общение с Томом Уэстердейлом
  4. ^ «Представление адаптивной генерации простых последовательных программ». www.cs.bham.ac.uk. _ Проверено 19 мая 2018 г.
  5. ^ «Нелинейные генетические алгоритмы решения проблем». www.cs.bham.ac.uk. _ Проверено 19 мая 2018 г.
  6. ^ «Иерархические генетические алгоритмы, работающие с популяциями компьютерных программ». www.cs.bham.ac.uk. _ Проверено 19 мая 2018 г.
  7. ^ Гольдберг. DE (1983), Компьютерная эксплуатация газопровода с использованием генетических алгоритмов и обучения правилам. Диссертация представлена ​​в Мичиганском университете в Анн-Арборе, штат Мичиган, в частичном выполнении требований для получения степени доктора философии.
  8. ^ «Генетическое программирование: о программировании компьютеров посредством естественного отбора». www.cs.bham.ac.uk. _ Проверено 19 мая 2018 г.
  9. ^ «Генетическое программирование: Фильм». gpbib.cs.ucl.ac.uk . Архивировано из оригинала 11 декабря 2021 г. Проверено 20 мая 2021 г.
  10. ^ «Влияние рекомбинации на фенотипическое исследование и устойчивость эволюции». gpbib.cs.ucl.ac.uk . Проверено 20 мая 2021 г.
  11. ^ «Конкурентоспособные для человека результаты, полученные с помощью генетического программирования» . www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  12. ^ «Генетическое программирование 1996: Материалы первой ежегодной конференции». www.cs.bham.ac.uk. _ Проверено 19 мая 2018 г.
  13. ^ «Генетическое программирование». www.cs.bham.ac.uk. _ Проверено 19 мая 2018 г.
  14. ^ «Генетическое программирование и структуры данных: генетическое программирование + структуры данных = автоматическое программирование!». www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  15. ^ ab «Генетическое программирование - Введение; Об автоматической эволюции компьютерных программ и их приложений». www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  16. ^ Банцхаф, Вольфганг (1 апреля 2000 г.). «Редакционное введение». Генетическое программирование и развивающиеся машины . 1 (1–2): 5–6. дои : 10.1023/А: 1010026829303. ISSN  1389-2576.
  17. ^ «Теория и практика генетического программирования». www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  18. ^ abc «Полевое руководство по генетическому программированию». www.gp-field-guide.org.uk . Проверено 20 мая 2018 г.
  19. ^ «Интеллектуальный анализ данных и обнаружение знаний с помощью эволюционных алгоритмов». www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  20. ^ «ЭДДИ побеждает букмекеров» . www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  21. ^ «Применение вычислительного интеллекта как создать ценность» . www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  22. ^ «Изобретение конкурентоспособной машины с помощью генетического программирования». www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  23. ^ «Открытие конкурирующих с человеком программ извлечения функций текстуры изображений с использованием генетического программирования» . www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  24. ^ «Три способа выращивания образцов: сравнение эмбриогенов для решения проблемы эволюционного дизайна» . www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  25. ^ «Клеточное кодирование как грамматика графа - Публикация конференции IET» . ieeexplore.ieee.org : 17/1–1710. Апрель 1993 года . Проверено 20 мая 2018 г.
  26. ^ «Декодирование генетического алгоритма для интерпретации инфракрасных спектров в аналитической биотехнологии». www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  27. ^ «Генетическое программирование для анализа данных ДНК-чипов онкологических больных» . www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  28. ^ «Генетическое программирование и моделирование тестов Джомини». www.cs.bham.ac.uk. _ Проверено 20 мая 2018 г.
  29. ^ Николас Л. Крамер «Представление адаптивной генерации простых последовательных программ». Архивировано 4 декабря 2005 г. в Wayback Machine .
  30. ^ Генетическое программирование: Введение, Вольфганг Банцхаф, Питер Нордин, Роберт Э. Келлер, Фрэнк Д. Франконе, Морган Кауфманн, 1999. ISBN 978-1558605107
  31. ^ Гарнетт Уилсон и Вольфганг Банцхаф. «Сравнение декартова генетического программирования и линейного генетического программирования»
  32. ^ ( Питер Нордин , 1997, Банцхаф и др., 1998, раздел 11.6.2-11.6.3)
  33. ^ Джованни Скиллеро. «µGP (МикроGP)».
  34. ^ «Стековое генетическое программирование». gpbib.cs.ucl.ac.uk . Проверено 20 мая 2021 г.
  35. ^ аб Спектор, Ли; Робинсон, Алан (01 марта 2002 г.). «Генетическое программирование и автоконструктивная эволюция с помощью языка программирования Push». Генетическое программирование и развивающиеся машины . 3 (1): 7–40. дои : 10.1023/А: 1014538503543. ISSN  1389-2576. S2CID  5584377.
  36. ^ Спектор, Ли; Кляйн, Джон; Кейзер, Мартен (25 июня 2005 г.). «Стек выполнения Push3 и эволюция контроля». Материалы 7-й ежегодной конференции по генетическим и эволюционным вычислениям . АКМ. стр. 1689–1696. CiteSeerX 10.1.1.153.384 . дои : 10.1145/1068009.1068292. ISBN  978-1595930101. S2CID  11954638.
  37. ^ Райан, Конор; Коллинз, Джей-Джей; Нил, Майкл О (1998). Конспекты лекций по информатике . Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 83–96. CiteSeerX 10.1.1.38.7697 . дои : 10.1007/bfb0055930. ISBN  9783540643609.
  38. ^ О'Нил, М.; Райан, К. (2001). «Грамматическая эволюция». Транзакции IEEE в эволюционных вычислениях . 5 (4): 349–358. дои : 10.1109/4235.942529. ISSN  1089-778X. S2CID  10391383.
  39. ^ Джулиан Ф. Миллер. «Декартово генетическое программирование». Архивировано 24 сентября 2015 г. в Wayback Machine . п. 19.
  40. ^ Джанет Клегг; Джеймс Альфред Уокер; Джулиан Фрэнсис Миллер. Новая техника кроссовера для декартова генетического программирования». 2007.
  41. ^ Спектор, Ли (2012). «Оценка модальности проблемы по дифференциальной эффективности выбора лексиказы в генетическом программировании». Материалы 14-й ежегодной конференции по генетическим и эволюционным вычислениям. Гекко '12. АКМ. стр. 401–408. дои : 10.1145/2330784.2330846. ISBN 9781450311786. S2CID  3258264.
  42. ^ Коза, Джон Р. (2010). «Конкурентоспособные для человека результаты, полученные с помощью генетического программирования». Генетическое программирование и развивающиеся машины . 11 (3–4): 251–284. дои : 10.1007/s10710-010-9112-3 .
  43. ^ "Хьюмис = Награды за соревнование между людьми" .
  44. ^ «ДИССЕРА 1987 ГОДА О том, как учиться, метаобучение, метагенетическое программирование, экономия машинного обучения, сохраняющая кредиты» .
  45. ^ GECCO '16 Companion: материалы Конференции по генетическим и эволюционным вычислениям 2016 г.: 20–24 июля 2016 г., Денвер, Колорадо, США . Нойманн, Франк (ученый-компьютерщик), Ассоциация вычислительной техники. СИГЕВО. Нью Йорк, Нью Йорк. 20 июля 2016 г. ISBN 9781450343237. ОСЛК  987011786.{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: others (link)

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