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

Генетическое программирование — автоматическое создание или изменение программ с помощью генетических алгоритмов, развитие парадигмы эволюционного программирования. С помощью этой методологии «выращиваются» программы, всё лучше и лучше (в соответствии с определённой функцией приспособленности для «хромосом») решающие поставленную вычислительную задачу.

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

Способы кодирования можно разделить на два класса:

прямое кодирование — генетический алгоритм работает с программой в явном виде;
косвенное кодирование — генетический алгоритм работает не с самим кодом программы, а с правилами его построения. То есть генетический алгоритм работает с программой, которая генерирует нужную нам программу.

Метагенетическое программирование — вариант генетического программирования, в котором изменяется и, тем самым, «выращивается», не только заданная компьютерная программа, но и сами применяемые операторы скрещивания➤ и мутации➤.

Нейронные сети

Древовидное

В древовидном кодировании каждый узел дерева содержит функцию, а каждый лист — операнд. Выражение, представленное в виде дерева, может быть легко рекурсивно посчитано. Традиционное ГП легче использовать для выращивания программ, написанных на языках, естественным образом воплощающих древовидную структуру: Lisp, Haskell, F# и других функциональных языках программирования.

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

Оператор скрещивания

В древовидном представлении оператор скрещивания реализуется обменом между двумя деревьями какими-либо узлами вместе с их потомками (поддеревьями).

Пример:

individual.Children[randomChildIndex] = otherIndividual.Children[randomChildIndex];

Оператор мутации

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

Пример:

individual.Information = randomInformation();

или

individual = generateNewIndividual();

Литература

Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D. (1997), Genetic Programming: An Introduction: On the Automatic Evolution of Computer Programs and Its Applications, Morgan Kaufmann
Cramer, Nichael Lynn (1985), «A representation for the Adaptive Generation of Simple Sequential Programs» in Proceedings of an International Conference on Genetic Algorithms and the Applications, Grefenstette, John J. (ed.), CMU
Koza, J. R. (1990), Genetic Programming: A Paradigm for Genetically Breeding Populations of Computer Programs to Solve Problems, Stanford University Computer Science Department technical report STAN-CS-90-1314. A thorough report, possibly used as a draft to his 1992 book.
Koza, J. R. (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press
Koza, J. R. (1994), Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press
Koza, J. R., Bennett, F.H., Andre, D., and Keane, M.A. (1999), Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann
Koza, J. R., Keane, M. A., Streeter, M. J., Mydlowec, W., Yu, J., Lanza, G. (2003), Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers
Langdon, W. B., Poli, R. (2002), Foundations of Genetic Programming, Springer-Verlag
Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, Lulu.com, freely available from the internet ISBN 978-1-4092-0073-4
Smith, S. F. (1980), A Learning System Based on Genetic Adaptive Algorithms, PhD dissertation (University of Pittsburgh)
Сопов Е. А. (2004), Эволюционные алгоритмы моделирования и оптимизации сложных систем, диссертация на соискание учёной степени кандидата технических наук, Красноярск