✖


Jump to content

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

Не путать с генетическими алгоритмами , обобщенным программированием , генной инженерией или вычислениями ДНК .
Часть серии о
Эволюционный алгоритм
Генетический алгоритм
Генетическое программирование

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

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

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

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

История

[ редактировать ]

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

Хотя идея создания программ, первоначально на компьютерном языке Lisp , была популярна среди студентов Джона Холланда, [3] только когда они организовали первую конференцию по генетическим алгоритмам (ГА) в Питтсбурге, Майкл Крамер [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] терапевтическая практика продолжала процветать, что привело к появлению первого специализированного журнала терапевтической практики. [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] для достижения лучшей производительности. мкгп [33] использует направленные мультиграфы для создания программ, полностью использующих синтаксис данного языка ассемблера . В программировании с несколькими выражениями используется трехадресный код для решения кодирования . Другие представления программ, над которыми были проведены значительные исследования и разработки, включают программы для виртуальных машин на основе стека, [34] [35] [36] и последовательности целых чисел, которые отображаются в произвольные языки программирования с помощью грамматик. [37] [38] Декартово генетическое программирование — это еще одна форма GP, которая использует графическое представление вместо обычного древовидного представления для кодирования компьютерных программ.

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

Выбор

[ редактировать ]

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

Элитаризм, который включает в себя засев следующего поколения лучшими людьми (или лучшими 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. ^ Jump up to: а б «Генетическое программирование — введение; об автоматической эволюции компьютерных программ и их приложений» . www.cs.bham.ac.uk. ​Проверено 20 мая 2018 г.
  16. ^ Банцхаф, Вольфганг (1 апреля 2000 г.). «Редакционное введение». Генетическое программирование и развивающиеся машины . 1 (1–2): 5–6. дои : 10.1023/A:1010026829303 . ISSN   1389-2576 .
  17. ^ «Теория и практика генетического программирования» . www.cs.bham.ac.uk. ​Проверено 20 мая 2018 г.
  18. ^ Jump up to: а б с «Полевое руководство по генетическому программированию» . 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» . IEEE : 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 (МикроГП)» .
  34. ^ «Стековое генетическое программирование» . gpbib.cs.ucl.ac.uk . Проверено 20 мая 2021 г.
  35. ^ Jump up to: а б Спектор, Ли; Робинсон, Алан (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 . OCLC   987011786 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) CS1 maint: другие ( ссылка )
[ редактировать ]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Genetic_programming&oldid=1237709198"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 8fb8d93720d859d5a70cdd8c9675212e__1722386400
URL1:https://arc.ask3.ru/arc/aa/8f/2e/8fb8d93720d859d5a70cdd8c9675212e.html
Заголовок, (Title) документа по адресу, URL1:
Genetic programming - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)