Генетическое программирование объяснено: как машины учатся писать свой код

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

GP имеет большой потенциал в области инженерии управления. В этой статье мы обсудим, что такое генетическое программирование, как оно может быть представлено, и посмотрим на пример программы.

Эта статья первая в серии. Чтобы перейти к следующим записям, выберите одну ниже:

• Генетические операторы в эволюционных алгоритмах
• Примеры генетических алгоритмов: эволюция программы сортировки и символьная регрессия
• Применения и ограничения генетического программирования

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

GP по сути является вариацией генетического алгоритма (GA), изначально замышленным Джоном Холландом. Как GA, GP — эволюционный алгоритм, полагающийся на генетические операторы, такие как пропорциональное воспроизведение пригодности (fitness proportionate reproduction), кроссовер (crossover) и мутация (mutation), для движения популяции закодированных программ, или «особей», через последовательные поколения к решению.

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

Ничеал Крамер и Джон Козаcredited за заложение фундаментов GP. Джон Коза (который также держит патент на GP) провел значительное количество исследований по GP, и его ландмартная книга «Genetic Programming» считается семинальной работой по теме. Текущие исследования продемонстрировали некоторые вдохновляющие успехи GP в широком спектре приложений, включая навигацию роботов, приобретение игровых стратегий, символьный регрессионный анализ и системы управления.

Представление генетического программирования

Упомянутое ранее основанное на дереве представление является центральным для темы GP, так как практически любая компьютерная программа может быть представлена таким образом. На практике функциональный язык, такой как LISP, хорошо подходит для этой формы и легко увидеть, как LISP S-выражение может быть изображено как дерево (Рисунок 1).

Ниже вы найдете три отдельных представления одной и той же информации:

Простой фрагмент программы:
BEGIN
IF a < b THEN a := a + 1 ELSE b := b * b
c := a * b * 2;
END


LISP эквивалент:
 (progn (if (a < b)
 (setq a (+ a 1))
 (setq b (* b b))
 )
 (setq c (* (* a b) 2))
)

Внутренние узлы дерева состоят из функций, тогда как листовые узлы состоят из терминалов. Функции должны иметь счетчик аргументов (обычно называемый арностью) как минимум один, позволяя им соединяться с другими функциями или терминалами, таким образом предоставляя «клей» для ветвей внутри дерева.

Терминалы обычно включают такие вещи как константы и переменные. Поскольку терминалы формируют листья дерева, у них всегда арность ноль. Вам нужно выбрать набор функций и терминалов для проблемы, которую вы пытаетесь решить. Например, логические функции AND, OR и NOT и терминалы X1 и X2, представляющие две булевы входные переменные, подходят, если вы пытаетесь открыть программу, способную синтезировать булеву функцию XOR. Функция пригодности также требуется, так как вы должны предоставить средства для измерения одной программы против другой в смысле, что одна лучше решает данную проблему.

Например, в случае XOR, мы можем проверить пригодность программы, выполняя программу один раз для каждого тестового случая пригодности, соответствующего четырем возможным булевым входам для X1 и X2 (0 0, 0 1, 1 0, 1 1) и суммируя количество правильных ответов (0, 1, 1, 0) соответственно для каждого тестового случая.

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

Идеальное решение проблемы XOR, найденное GP:
(defun program ()
  (AND (OR X1 X2)
  (NOT (AND X1 X2) )
  )
)

Далее: Генетические операторы

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

Рекомендуемая литература

• Kinnear, Jr., K. E. (ed.). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press, 1994.
• Knuth, D. E. The Art of Computer Programming, Volume 3, Sorting and Searching. Reading, Mass.: Addison-Wesley, 1973
• Koza, J. R. Genetic Programming. Cambridge, Mass.: The MIT Press, 1992.
• Koza, J. R. Genetic Programming II. Cambridge, Mass.: The MIT Press, 1994.
• Montana, D. J. "Strongly Typed Genetic Programming." BBN Technical Report #7866, May 1993.
• Mitchell, Melanie, An Introduction to Genetic Algorithms, The MIT Press, 1998.