Исследование возможностей и ограничений генетических алгоритмов

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

Здесь мы высокого уровня рассмотрим, чего может достичь эта технология по мере развития.

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

Для понимания этой заключительной главы серии вспомним пример XOR, обсуждаемый в первой части:

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

Вспомним также пример символьной регрессии из предыдущей статьи:

Полиномиальное приближение sin(x) в интервале (0 <= x <= pi/2)

(defun program ()
  (+ (* (* (* X X) X)
  (* 0.2283 -0.6535))
  X)
)

Упрощение вышеуказанной программы дает эквивалентное уравнение:

polysin(x) = -.1492 x3 + x

Результаты:

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

Эта характеристика не является ограничением, так как функция или терминал могут иметь побочный эффект при выполнении. Это часто случается в программе сортировки, содержащей функцию с потенциальным побочным эффектом обмена пары элементов в векторе. На практике побочные эффекты встречаются часто. Другие примеры полезных побочных эффектов: присваивание одной переменной другой или изменение направления, в котором смотрит робот.

Наш набор функций может включать условные функции, предоставляющие эволюционирующим программам способность принимать решения. Условные функции селективно вычисляют свои аргументы. Например, функция с арностью три, такая как (if arg1 arg2 arg3). Она вычисляется путем оценки первого аргумента: если результат истинный, вычисляется второй аргумент; иначе — третий. Итеративные конструкции также возможны, так как функция может вычислять один из своих аргументов несколько раз. Дополнительная сложность вводится необходимостью ограничить количество итераций и уровень вложенности, чтобы избежать ситуаций, когда оценка особи занимает чрезмерно много времени. Некоторая работа велась по рекурсивным формулировкам, хотя успехи в этой области были ограниченными.

Хотя результаты GP-систем обычно представляют собой LISP-подобные программы, GP-система не обязательно должна быть реализована на LISP. Многие системы реализованы на C или C++. Можно использовать линеаризованное представление дерева программы, избегая накладных расходов динамической памяти и дорогой сборки мусора. Эффективность функции пригодности заслуживает особого внимания, так как она часто становится узким местом из-за большого количества вызовов в каждом поколении. Отличная статья, обсуждающая различные техники реализации, можно найти в Advances in Genetic Programming (указана в рекомендуемой литературе ниже).

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

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

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

Генетическое программирование успешно применялось к задачам в таких областях как:

• Проектирование схем
• Комбинаторная оптимизация
• Системы управления
• Аппроксимация кривых / регрессионный анализ
• Сжатие данных
• Экономическое прогнозирование / финансовое моделирование
• Приобретение игровых стратегий
• Математическая индукция последовательностей
• Проектирование нейронных сетей
• Распознавание образов и классификация
• Генерация случайных чисел
• Навигация роботов
• Символьное интегрирование и дифференцирование
• Трехмерное проектирование

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

В зависимости от сложности задачи, может потребоваться несколько запусков GP для нахождения приемлемого решения, если оно вообще может быть найдено. Идеально, мы хотели бы, чтобы GP «масштабировался» по мере увеличения сложности задачи. Поиск хороших способов достижения этой цели — активная область исследований. Как и в обычном программировании, концепция построения представлений высшего уровня через подпрограммы — один из подходов к этой проблеме. В Genetic Programming II Коза обсуждает методы, которые могут обнаруживать повторно используемые подпрограммы, и представляет результаты, подтверждающие способность иерархических модульных программ решать более сложные задачи.

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

По-прежнему находясь в зачаточном состоянии, будущие прорывы могут приблизить нас на шаг к тому Священному Граалю — системам, способным писать свои собственные программы.

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

• 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.