Генетическое программирование
В области искусственного интеллекта генетическое программирование ( 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, будет просто критерий эффективности.
См. также [ править ]
- Биологические вычисления
- Декартово генетическое программирование
- Стратегия эволюции адаптации ковариационной матрицы (CMA-ES)
- Приближение фитнеса
- Программирование экспрессии генов
- Генетическое улучшение
- Генетическое представление
- Грамматическая эволюция
- Индуктивное программирование
- Линейное генетическое программирование
- Мультивыраженное программирование
- Распространение схемы
Ссылки [ править ]
- ^ «Вычислительная техника и интеллект» . www.cs.bham.ac.uk. Проверено 19 мая 2018 г.
- ^ «BEAGLE: Дарвиновский подход к распознаванию образов» . www.cs.bham.ac.uk. Проверено 19 мая 2018 г.
- ^ Личное общение с Томом Уэстердейлом
- ^ «Представление адаптивной генерации простых последовательных программ» . www.cs.bham.ac.uk. Проверено 19 мая 2018 г.
- ^ «Нелинейные генетические алгоритмы решения задач» . www.cs.bham.ac.uk. Проверено 19 мая 2018 г.
- ^ «Иерархические генетические алгоритмы, работающие с популяциями компьютерных программ» . www.cs.bham.ac.uk. Проверено 19 мая 2018 г.
- ^ Гольдберг. DE (1983), Компьютерная эксплуатация газопровода с использованием генетических алгоритмов и обучения правилам. Диссертация представлена в Мичиганском университете в Анн-Арборе, штат Мичиган, в частичном выполнении требований для получения степени доктора философии.
- ^ «Генетическое программирование: о программировании компьютеров посредством естественного отбора» . www.cs.bham.ac.uk. Проверено 19 мая 2018 г.
- ^ «Генетическое программирование: Фильм» . gpbib.cs.ucl.ac.uk . Архивировано из оригинала 11 декабря 2021 г. Проверено 20 мая 2021 г.
- ^ «Влияние рекомбинации на фенотипическое исследование и устойчивость эволюции» . gpbib.cs.ucl.ac.uk . Проверено 20 мая 2021 г.
- ^ «Конкурентные для человека результаты, полученные с помощью генетического программирования» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ «Генетическое программирование 1996: материалы первой ежегодной конференции» . www.cs.bham.ac.uk. Проверено 19 мая 2018 г.
- ^ «Генетическое программирование» . www.cs.bham.ac.uk. Проверено 19 мая 2018 г.
- ^ «Генетическое программирование и структуры данных: генетическое программирование + структуры данных = автоматическое программирование!» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ Перейти обратно: а б «Генетическое программирование — введение; об автоматической эволюции компьютерных программ и их приложений» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ Банцхаф, Вольфганг (1 апреля 2000 г.). «Редакционное введение». Генетическое программирование и развивающиеся машины . 1 (1–2): 5–6. дои : 10.1023/А:1010026829303 . ISSN 1389-2576 .
- ^ «Теория и практика генетического программирования» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ Перейти обратно: а б с «Полевое руководство по генетическому программированию» . www.gp-field-guide.org.uk . Проверено 20 мая 2018 г.
- ^ «Интеллектуальный анализ данных и обнаружение знаний с помощью эволюционных алгоритмов» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ «ЭДДИ побеждает букмекеров» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ «Применение вычислительного интеллекта для создания ценности» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ «Изобретение конкурентоспособной человека машины посредством генетического программирования» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ «Открытие конкурирующих с человеком программ извлечения функций текстуры изображений с использованием генетического программирования» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ «Три способа выращивания дизайнов: сравнение эмбриогений для решения проблемы эволюционного дизайна» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ «Клеточное кодирование как грамматика графа — Публикация конференции IET» . ieeexplore.ieee.org : 17/1–1710. Апрель 1993 года . Проверено 20 мая 2018 г.
- ^ «Генетический алгоритм декодирования для интерпретации инфракрасных спектров в аналитической биотехнологии» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ «Генетическое программирование для анализа данных ДНК-чипов онкологических больных» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ «Генетическое программирование и моделирование тестов Джомини» . www.cs.bham.ac.uk. Проверено 20 мая 2018 г.
- ^ Майкл Л. Крамер «Представление адаптивной генерации простых последовательных программ». Архивировано 4 декабря 2005 г. в Wayback Machine .
- ^ Генетическое программирование: Введение, Вольфганг Банцхаф, Питер Нордин, Роберт Э. Келлер, Фрэнк Д. Франконе, Морган Кауфманн, 1999. ISBN 978-1558605107
- ^ Гарнетт Уилсон и Вольфганг Банцхаф. «Сравнение декартова генетического программирования и линейного генетического программирования»
- ^ ( Питер Нордин , 1997, Банцхаф и др., 1998, раздел 11.6.2-11.6.3)
- ^ Джованни Скиллеро. «μGP (МикроГП)» .
- ^ «Стековое генетическое программирование» . gpbib.cs.ucl.ac.uk . Проверено 20 мая 2021 г.
- ^ Перейти обратно: а б Спектор, Ли; Робинсон, Алан (01 марта 2002 г.). «Генетическое программирование и автоконструктивная эволюция с помощью языка программирования Push». Генетическое программирование и развивающиеся машины . 3 (1): 7–40. дои : 10.1023/А:1014538503543 . ISSN 1389-2576 . S2CID 5584377 .
- ^ Спектор, Ли; Кляйн, Джон; Кейзер, Мартен (25 июня 2005 г.). «Стек выполнения Push3 и эволюция контроля». Материалы 7-й ежегодной конференции по генетическим и эволюционным вычислениям . АКМ. стр. 1689–1696. CiteSeerX 10.1.1.153.384 . дои : 10.1145/1068009.1068292 . ISBN 978-1595930101 . S2CID 11954638 .
- ^ Райан, Конор; Коллинз, Джей-Джей; Нил, Майкл О (1998). Конспекты лекций по информатике . Берлин, Гейдельберг: Springer Berlin Heidelberg. стр. 83–96. CiteSeerX 10.1.1.38.7697 . дои : 10.1007/bfb0055930 . ISBN 9783540643609 .
- ^ О'Нил, М.; Райан, К. (2001). «Грамматическая эволюция». Транзакции IEEE в эволюционных вычислениях . 5 (4): 349–358. дои : 10.1109/4235.942529 . ISSN 1089-778X . S2CID 10391383 .
- ^ Джулиан Ф. Миллер. «Декартово генетическое программирование». Архивировано 24 сентября 2015 г. в Wayback Machine . п. 19.
- ^ Джанет Клегг; Джеймс Альфред Уокер; Джулиан Фрэнсис Миллер. Новая техника кроссовера для декартова генетического программирования» . 2007.
- ^ Спектор, Ли (2012). «Оценка модальности проблемы по дифференциальной эффективности выбора лексиказы в генетическом программировании». Материалы 14-й ежегодной конференции по генетическим и эволюционным вычислениям . Гекко '12. АКМ. стр. 401–408. дои : 10.1145/2330784.2330846 . ISBN 9781450311786 . S2CID 3258264 .
- ^ Коза, Джон Р. (2010). «Конкурентные для человека результаты, полученные с помощью генетического программирования» . Генетическое программирование и развивающиеся машины . 11 (3–4): 251–284. дои : 10.1007/s10710-010-9112-3 .
- ^ «Хьюмис = Награды за человеческую конкурентоспособность» .
- ^ «ДИССЕССАЦИЯ 1987 ГОДА НА ОБУЧЕНИЕ УЧИТЬСЯ, МЕТА-ОБУЧЕНИЕ, МЕТА-ГЕНЕТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ, ЭКОНОМИКА МАШИННОГО ОБУЧЕНИЯ, Сохраняющая кредиты» .
- ^ GECCO '16 Companion: материалы конференции по генетическим и эволюционным вычислениям 2016 г.: 20–24 июля 2016 г., Денвер, Колорадо, США . Нойманн, Франк (ученый-компьютерщик), Ассоциация вычислительной техники. СИГЕВО. Нью Йорк, Нью Йорк. 20 июля 2016 г. ISBN 9781450343237 . OCLC 987011786 .
{{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка ) CS1 maint: другие ( ссылка )
Внешние ссылки [ править ]
- Аймен С. Сакет и Марк С. Синклер
- Генетическое программирование и развивающиеся машины , журнал
- Evo2 для генетического программирования
- Библиография врача общей практики
- Путеводитель по эволюционным вычислениям для путешествующих автостопом
- Риккардо Поли, Уильям Б. Лэнгдон, Николас Ф. Макфи, Джон Р. Коза, « Полевое руководство по генетическому программированию » (2008)
- Генетическое программирование, ресурс, поддерживаемый сообществом.
| Базы данных органов управления : Национальные |
|---|
