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

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

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

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

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

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

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

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

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

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

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

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

Изменить, чтобы процитировать:

Грэм-Роу, Дункан. «Радио возникает из электронного супа». New Scientist, том 175, № 2358, стр. 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

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

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

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

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

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

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

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

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

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

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

Три вещи:

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

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

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

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

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

Это примерно та же логика, что и в теории сингулярности, кстати.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первобытный суп подозрительный и неаппетитный. Для своего производственного кода я предпочитаю Intelligent Design.

Мое личное мнение после пары лет исследований общей практики в университете и последующих исследований в этой области: GP не масштабируется.

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

Хотя мне нравится идея, что фитнес-функция GP является TDD в совершенстве :-) Может быть, какой-нибудь светлый ум когда-нибудь придумает лучший способ управления симулированной эволюцией, но этого еще не произошло.

У меня есть некоторые надежды на GP в области неявных функций пригодности, где я сейчас провожу некоторые «частные исследования». Посмотрим, как далеко это зайдет!

Привет, Джей

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

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

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

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

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

Просто сравните спонсоров их конференций со спонсорами других конференций по AI/ML/оптимизации. Будет понятно их «текущее» значение в промышленности.

Но это область исследований, и от нас зависит, как заставить ее работать. Пока это просто хобби!