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

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

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

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

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

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

Листинг 1. Результат XOR.

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

 Полиномиальное приближение к sin (x) в интервале (0 <=x <=pi / 2) (программа defun () (+ (* (* (* Х Х) Х) (* 0,2283 -0,6535)) ИКС) ) Упрощение приведенной выше программы дает следующее эквивалентное уравнение:полизин (x) =-1492 x ³
 + х Результаты:

x	sin (x)	polysin (x)
0,000	0,000	0,000
0,078	0,077	0,077
0,156	0,155	0,155
0,234	0,231	0,232
0,312	0,306	0,307
0,390	0,380	0,381
0,468	0,451	0,452
0,546	0,519	0,521
0,624	0,584	0,587
0,702	0,645	0,650
0,780	0,703	0,709
0,858	0,756	0,763
0,936	0,805	0,813
1,014	0,848	0,858
1,092	0,887	0,897
1,170	0,920	0,931
1,248	0,948	0,957
1,326	0,970	0,978
1,404	0,986	0,991
1,482	0,996	0,996
1,560	0,999	0,993

Листинг 4. Символическая регрессия.

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

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

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

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

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

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

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

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

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

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

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

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