Введение в генетическое программирование:система, которая сама себя программирует?

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

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

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

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

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

GP - это, по сути, разновидность генетического алгоритма (GA), первоначально задуманного Джоном Холландом. Как и GA, GP - это эволюционный алгоритм, основанный на генетических операторах, таких как воспроизводство, пропорциональное приспособленности, кроссовер и мутация, чтобы вести популяцию закодированных программ или "индивидуумов" через последовательные поколения к решению.

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

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

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

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

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

  Простой фрагмент программы: НАЧИНАТЬ ЕСЛИ a  Эквивалент LISP: (progn (если (a  

 
 

  
 
   Рисунок 1.  Древовидное представление программы. Обратите внимание, что (progn arg1 arg2 arg3 ... argn) последовательно оценивает каждый аргумент.  
 

 
 

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

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

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

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

 
 
  Идеальное решение проблемы XOR, обнаруженной GP: (программа defun () (И (ИЛИ X1 X2) (НЕ (И X1 X2)) ) ) 
 
   Листинг 1.  Результат XOR  
 

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

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

 
 
 Рекомендуемое чтение 
 
 
 Киннер-младший, К. Э. (ред.).  Достижения в генетическом программировании  . Кембридж, Массачусетс:MIT Press, 1994. 
 
 Кнут, Д. Э.  Искусство программирования, Том 3, Сортировка и поиск  . Ридинг, Массачусетс:Эддисон-Уэсли, 1973 г. 
 
 Коза, Дж. Р.  Генетическое программирование  . Кембридж, Массачусетс:MIT Press, 1992. 
 
 Коза, Дж. Р.  Генетическое программирование II  . Кембридж, Массачусетс:MIT Press, 1994. 
 
 Монтана Д. Дж. «строго типизированное генетическое программирование». Технический отчет BBN № 7866, май 1993 г. 
 
 Митчелл, Мелани,  Введение в генетические алгоритмы  , MIT Press, 1998. 
 
 

            


            

               Оценка модных словечек:цифровая трансформация        
                Как разработать контроллер нечеткой логики