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

Ответ 1

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

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

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

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

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

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

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

Ответ 2

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

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

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

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

Отредактируйте, чтобы цитировать:

Грэм-Роу, Дункан. "Радио выходит из электронного супа". 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

Ответ 3

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

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

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

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

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

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

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

Ответ 4

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

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

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

Ответ 5

Три вещи:

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

Ответ 6

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

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

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

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

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

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

Ответ 7

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

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

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

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

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

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

Ответ 8

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

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

Не все нуждается в фантастическом алгоритме. Из всего кода, написанного в мире, "стандартные" webapps, ОС, программирование устройств действительно нужны генетические алгоритмы?

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

Ответ 9

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

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

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

Ответ 10

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

Ответ 11

Мой личный взгляд после пары лет в исследовании ГП в университете и после полезна после этого: GP не масштабируется.

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

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

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

Cheers, Джей

Ответ 12

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

Ответ 13

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

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

Ответ 14

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

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

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

Но его область исследований, и ее до нас, чтобы заставить ее работать. В настоящее время это просто хобби!