Что сдерживает генетическое программирование?

Question

Я довольно успешно проделал большую работу с генетическими алгоритмами и до сих пор игнорировал генетическое программирование. Насколько я знаю, большинство программ остаются написанными программистами, и мне любопытно узнать, что сдерживает генетическое программирование?

Вот некоторые возможные объяснения, о которых я подумал:

1. Пространство поиска слишком велико, чтобы найти полезные программы среди шума
2. Большинство реальных приложений не могут предоставить достаточно данных для оценки пригодности такого пространства.
3. Трудно снизить эффективность многих реальных приложений до одной меры пригодности. Другими словами, написание подходящей фитнес-функции, вероятно, повлечет за собой тот же объем работы, что и написание реальной программы.

Есть идеи?

Answer 1

Это то, что я рассматривал в своем собственном исследовании, и я бы сказал, что есть много причин:

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

2. Существуют значительныечрезмерный акцент на использование LISP, потому что он может создавать красивые древовидные структуры, которыми легко манипулировать, и, к сожалению, императивными программами пренебрегали, потому что они включают в себя решение некоторых сложных задач.Чтобы программисты воспринимали GP серьезно, она должна создавать императивные программы.

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

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

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

Еще один верный ответ состоит в том, что трудно доверять коду, автоматически генерируемому.Это правда, но на практике я сомневаюсь, что это имеет большое влияние, потому что ГП не может производить правильные программы в первую очередь.

Answer 2

Самое сложное в генетическом программировании - написать хорошую функцию подсчета очков:

• Функция оценки должна правильно определять, обладает ли алгоритм требуемыми свойствами. Это сложнее, чем кажется - гораздо сложнее, чем написать набор тестов. Алгоритм может адаптироваться к любой особенности вашей функции скоринга и оптимизировать ее. Пытаетесь эволюционировать strcmp? Вместо этого ваш алгоритм может обнаружить математический шаблон для длины ваших успешных / неудачных тестовых случаев.

• Функция оценки должна быть способна определять, работает ли тестируемый алгоритм частично. Генетическое программирование опирается на "восхождение на холм". Крошечная полезная мутация должна вызвать незначительное постепенное улучшение оценки. Если ваша функция подсчета очков может выводить только true / false, то вы ищете случайно, а не генетически.

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

Изменить на цитировать:

Грэм-Роу, Дункан. «Радио выходит из электронного супа». New Scientist, vol.175, no.2358, p.19 (31 августа 2002 г.). Доступно онлайн на http://www.newscientist.com/news/news.jsp?id=ns99992732

Однако теперь ссылка не работает.

Новая ссылка http://www.newscientist.com/article/dn2732-radio-emerges-from-the-electronic-soup.html

Answer 3

Я знаю, что опаздываю на эту вечеринку, но я бы хотел сделать пару замечаний. Мне повезло работать с Джоном Коза над его книгой «Генетическое программирование 4».

Тип программирования, который большинство из нас делает изо дня в день - подключение событий графического интерфейса, добавление пикселей, создание баз данных и т. Д., Безусловно, не тип программ, которые GP планирует создавать.

Что Джон Коза делает со своим кластером из примерно ста машин (если я правильно помню!), Так это поиск решений интересных проблем (подумайте NP-hard). Это печально, но большинство проблем, с которыми мы, программисты, работаем каждый день, не очень интересные или сложные, в основном просто раздражающие и отнимающие много времени.

То, что Бен Джексон сказал о генно-инженерном электронном генераторе, является самой близкой вещью в этой теме к тому, что на самом деле делают доктор Коза и его команда. В серии книг GP было много примеров схем.

То, что Том Касл сказал здесь об императивных программах, не совсем верно. Оригинальным примером этого от Джона и компании является проектирование антенны. Это в значительной степени программа для трехмерного рисования с такими командами, как язык рисования LOGO, который создает антенну. У него есть команды типа moveto, lineto для перемещения и выталкивания матриц в стеке. Пакет GP, который я только что посмотрел на прошлой неделе, jgap, имеет прямую поддержку: нетерминал типа контейнера, который может содержать пустые операторы return, а затем в конце имеет оператор return. Я полагаю, что у него даже есть что-то вроде локальных переменных, хотя я не слишком внимательно присматривался.

Оригинальный дизайн LISP, вокруг которого работает ранний GP, время от времени является чем-то вроде боли, что, безусловно, верно. Это что-то вроде обряда, я думаю, что меня раздражает перевод вывода результатов GP в более удобный код.

TL; DR: GP на самом деле не система автоматического программирования. Это автоматизированная система изобретение .

Answer 4

Я бы сказал 1. и 3.

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

Относительно пункта 1Я бы сказал, что пространство поиска имеет бесконечное число измерений.

Answer 5

ГП не может быстро решить новые проблемы, которые не могут быть известны человеку, создающему фитнес-функцию. Таким образом, в настоящее время он может использоваться только для решения проблем, которые мы уже знаем, как решить, но не идеальны для полного решения из-за пространства поиска. Например, коммивояжер. Который может быть решен быстрее с помощью GA.

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

Генетическое программирование, как и настоящая генетика, подчиняется той же схеме роста, что и все системы роста платформы. Это означает, что GP будет прогрессировать до точки, где основные включенные утилиты попадают на платформу, он выравнивается, а затем требуется ДЛИННОЕ время, прежде чем он наткнется на новую парадигму, чтобы перейти на новую платформу.

Это видео про эволюцию иллюстрирует эти модели роста платформы. http://www.youtube.com/watch?v=mcAq9bmCeR0 На разработку новой руки уходит много времени, и как только это происходит, дополнительная рука становится новой вещью и быстро продвигается к оптимальному примеру большего количества рук. (Я должен отметить, что это видео, скорее всего, использует GA, а не GP, но генетика - это генетика)

Это все о той же логике, которая входит в теорию сингулярности, кстати.

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

Answer 6

Три вещи:

1. Как Андре говорит , очень сложно написать достаточную фитнес-функцию. Это окончательная версия Test Driven Development. Вам придется написать модульные тесты, которые обеспечат 100% покрытие еще не написанной программы. Даже тогда 100% покрытия само по себе вряд ли будет достаточным. Когда мы решили проблему формального определения точного поведения всех аспектов сложной системы, а затем подтвердили, что данная программа удовлетворяет этой спецификации, у нас может появиться шанс.
2. Генетическое программирование недетерминировано и лучше подходит для генерации приближенных решений, чем точных решений.
3. Генетическое программирование применительно к любой проблеме разумной сложности является феноменально дорогим в вычислительном отношении. Еще в 1999 году Genetic Programming Inc использовала кластер из 1000 узлов для своей работы в полевых условиях.

Answer 7

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

Предположим, у вас есть бесконечная вычислительная мощность, отбрасывающая размер пространства поиска и проблемы с медлительностью, а также другие «скоростные» вещи.Теперь перед вами только две проблемы: - Будет ли сгенерированная программа остановлена?- Как быть уверенным, что сгенерированная программа ведет себя так, как я хочу?

Первая проблема - это центральный вопрос теории вычислимости, и она называется проблема остановки .В 1936 году Тьюринг доказал, что эта проблема неразрешима для всех пар ввода программы.Это означает, что это возможно в некоторых случаях, но не для всех.Не существует автоматизированного процесса, который может определить, останавливается программа или нет.Так что для этого вы ничего не можете сделать;)

Вторая проблема связана с корректностью программы.В генетическом программировании валидация обычно производится через примеры значений, которые вообще не являются доказательством правильности.Это сравнимо с модульным тестированием, хорошо подходит для ряда примеров, но не дает общего доказательства.Например, если я напишу проверку простых чисел, протестирую ее только с 3 5 7 и 11, тогда программа, которая возвращает истину для каждого нечетного числа, пройдет проверку.

Если сделать еще один шаг, то использовать автоматизированныйдоказательства.Автоматическое доказательство правильности алгоритмов на самом деле тесно связано с математическим автоматическим доказательством теорем.Вы описываете свою программу, используя аксиоматизированную систему, и пытаетесь автоматически подтвердить правильность вашего утверждения.Здесь снова вы сталкиваетесь с сильными теоретическими барьерами, которыми являются теоремы Гёделя о неполноте .Эти теоремы утверждают, среди прочего, что даже для очень простых аксиоматизированных систем, способных выполнять арифметику над натуральными числами, не существует алгоритма (называемого эффективной процедурой), способного доказать все теоремы относительно этих натуральных чисел.Конкретно, это означает, что даже для простых программ вы не сможете доказать ее правильность.

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

Answer 8

Я думаю, что большая часть причины - управление рисками. Терпите меня: когда программист садится писать программу, у него есть хотя бы некоторое представление о том, сколько времени это займет и что они могут сделать.

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

Существует также неопределенность в других местах: насколько легко будет настроить программу позже или исправить ошибки? Сгенерированный код почти невозможно отладить.

Answer 9

Может быть, большинство программистов - программисты, а не ученые-компьютерщики?

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

Не всем нужен причудливый алгоритм. Из всего кода, написанного в мире, действительно ли нужны «стандартные» веб-приложения, операционные системы, устройства программирования, генетические алгоритмы?

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

Answer 10

Есть несколько проектов, решающих вышеупомянутые проблемы в GP.Примером может служить opencog MOSES