Генетическое программирование
В искусственном интеллекте генетическое программирование ( ГП ) — это метод эволюции программ, начиная с популяции непригодных (обычно случайных) программ, подходящих для конкретной задачи, путем применения операций, аналогичных естественным генетическим процессам, к популяции программ.
Операции таковы: выбор наиболее подходящих программ для размножения (кроссовера) и мутации в соответствии с предопределенной мерой приспособленности, обычно умением выполнять желаемую задачу. Операция кроссинговера включает в себя замену случайных частей выбранных пар (родителей) для получения новых и отличающихся потомков, которые становятся частью программ нового поколения. Мутация предполагает замену некоторой случайной части программы какой-либо другой случайной частью программы. Некоторые программы, не выбранные для воспроизведения, копируются из текущего поколения в новое поколение. Затем выбор и другие операции рекурсивно применяются к программам нового поколения.
Как правило, представители каждого нового поколения в среднем лучше подготовлены, чем члены предыдущего поколения, и программа лучших представителей поколения часто оказывается лучше, чем программы лучших представителей предыдущих поколений. Прекращение рекурсии происходит, когда какая-то отдельная программа достигает предопределенного уровня мастерства или пригодности.
Может и часто случается, что конкретный запуск алгоритма приводит к преждевременной сходимости к некоторому локальному максимуму, который не является глобально оптимальным или даже хорошим решением. Многократные прогоны (от десятков до сотен), как правило, необходимы для получения очень хорошего результата. Также может быть необходимо увеличить исходный размер популяции и изменчивость особей, чтобы избежать патологий.
Первое упоминание о предложении развивать программы, вероятно, принадлежит Алану Тьюрингу в 1950 году. [1] Прошло 25 лет, прежде чем была опубликована книга Джона Холланда «Адаптация в естественных и искусственных системах», в которой были изложены теоретические и эмпирические основы наука. В 1981 году Ричард Форсайт продемонстрировал успешную эволюцию небольших программ, представленных в виде деревьев, для выполнения классификации улик на месте преступления для Министерства внутренних дел Великобритании. [2]
Хотя идея развития программ, изначально на языке программирования Лисп , была распространена среди студентов Джона Холланда [3] , только когда они организовали первую конференцию по генетическим алгоритмам (ГА) в Питтсбурге, Николь Крамер [4] опубликовал эволюционные программы на два специально разработанных языка, которые включали в себя первое утверждение современного «древовидного» генетического программирования (то есть процедурных языков, организованных в древовидные структуры и управляемых соответствующим образом определенными ГА-операторами). В 1988 году Джон Коза (также аспирант Джона Холланда) запатентовал свое изобретение ГА для эволюции программ. [5]Затем последовала публикация в Международной объединенной конференции по искусственному интеллекту IJCAI-89. [6]
