Каковы типичные варианты использования Генетического Программирования?
8 ответов
Существуют некоторые дебаты относительно того, является ли программа Моны Лизы Roger Генетическое Программирование вообще. Это, кажется, ближе к (1 + 1) Стратегия Эволюции. Оба метода являются примерами более широкого поля Эволюционного Вычисления, которое также включает Генетические алгоритмы .
Генетическое программирование (GP) является процессом развития компьютерных программ (обычно в форме деревьев - часто программы Lisp). Если Вы спрашиваете конкретно о GP, John Koza широко рассматривается как ведущий эксперт. Его веб-сайт включает много ссылок на большую информацию. GP обычно очень в вычислительном отношении интенсивен (для нетривиальных проблем, он часто включает большую сетку машин).
, Если Вы спрашиваете в более общем плане, эволюционные алгоритмы (EA) обычно используются для предоставления хороших приближенных решений проблем, которые не могут быть решены легко с помощью других методов (таких как NP-трудные проблемы). Много проблем оптимизации попадают в эту категорию. Это может быть слишком в вычислительном отношении интенсивно для нахождения точного решения, но иногда почти оптимальное решение достаточно. В этих ситуациях эволюционные методы могут быть эффективными. Из-за их случайного характера, эволюционные алгоритмы, как никогда гарантируют, не найдут оптимальное решение ни для какой проблемы, но они будут часто находить хорошее решение, если Вы будете существовать.
Эволюционные алгоритмы могут также использоваться для занятия проблемами, которые действительно не знают люди, как решить. EA, свободный от любых человеческих предвзятых мнений или предвзятости, может генерировать удивительные решения, которые сопоставимы с, или лучше, чем, лучшие сгенерированные человеком усилия. Просто необходимо, чтобы мы могли распознать хорошее решение, если это было представлено нам, даже если мы не знаем, как создать хорошее решение. Другими словами, нам необходимо сформулировать эффективное функция фитнеса .
Некоторые Примеры
РЕДАКТИРОВАНИЕ: книга в свободном доступе, Полевое Руководство А по Генетическому Программированию , содержит примеры того, где GP произвел человечески-конкурентоспособный результаты.
Интересно достаточно компания позади динамической символьной анимации, используемой в играх как IV Grand Theft Auto и последней игре Звездных войн (Развязанная Сила), использовала генетическое программирование для разработки алгоритмов перемещения. Веб-сайт компании здесь, и видео являются очень впечатляющими:
http://www.naturalmotion.com/euphoria.htm
я полагаю, что они моделировали нервную систему символа, затем рандомизировали соединения в некоторой степени. Они тогда объединили 'гены' моделей, которые шли дальше всего для создания все более способных 'детей' в последовательных поколениях. Действительно захватывающее моделирование.
я также видел генетические алгоритмы, используемые в автоматах нахождения пути с ищущими еду муравьями, являющимися классическим примером.
Генетические алгоритмы могут использоваться для решения большей части любой проблемы оптимизации. Однако в большом количестве случаев, существуют лучшие, более прямые методы решить их. Это находится в классе алгоритмов метапрограммирования, что означает, что это в состоянии адаптироваться к в значительной степени чему-либо, что можно бросить в него, учитывая, что можно генерировать метод кодирования потенциального решения, объединения/видоизменения решений и решения, какие решения лучше, чем другие. GA имеет преимущество перед другими алгоритмами метапрограммирования, в которых он может обработать локальные максимумы лучше, чем чистый алгоритм преодоления подъема, как моделируемый отжиг.
Я использовал генетическое программирование в своем тезисе для моделирования эволюции разновидностей на основе ландшафта, но это - конечно, A-жизненное приложение генетических алгоритмов.
проблемы, к которым способны GA, проблемы преодоления подъема . Проблема состоит в том, что обычно легче решить большинство этих проблем вручную, если факторы, которые определяют проблему, не неизвестны, другими словами, Вы так или иначе еще не можете достигнуть того знания, сказать вещи, связанные с обществами и сообществами, или в ситуациях, где у Вас есть хороший алгоритм, но необходимо точно настроить параметры, здесь GA очень полезны.
ситуация с А точной настройки, которую я сделал, должна была точно настроить несколько плееров AI Отелло на основе тех же алгоритмов, дав каждой различной игре стили, таким образом делая каждого противника уникальным и с ее собственными причудами, тогда я сделал, чтобы они конкурировали для отбора лучших 16 AI, которые я использовал в своей игре. Преимущество было, они были всеми очень хорошими игроками более или менее равного навыка, таким образом, это было интересно для противника - человека, потому что они не могли предположить AI как легко.
Необходимо спросить себя: "Я могу (априорно) определить функцию, чтобы определить, насколько хороший конкретное решение относительно других решений?"
В примере Моны Лизы, можно легко определить, походит ли новое рисование больше на исходное изображение, чем предыдущее рисование, таким образом, Генетическое Программирование может быть "легко" применено.
У меня есть некоторые проекты с помощью Генетических алгоритмов. GA идеальны для проблем оптимизации, когда Вы не можете разработать полностью последовательный, точный алгоритм, действительно решают проблему. Например: какова лучшая комбинация автомобиля characteristcs для создания его быстрее и в то же время более экономическим?
В данный момент я разрабатываю простой GA для разработки плей-листов. Мой GA должен найти лучшие комбинации альбомов/песен, которые подобны (это подобие будет "вычислено" с помощью Last.fm), и предлагает плей-листы для меня.
Существует появляющееся поле в робототехнике, названной Эволюционная Робототехника ( w:Evolutionary Робототехника ), который использует генетические алгоритмы (GA) в большой степени.
См. w:Genetic Алгоритм :
Простой псевдокод генетического алгоритма поколений
- Выбирает, начальное население
- Оценивают физическую форму каждого человека в населении
- Повторение до завершения: (ограничение по времени или достаточная достигнутая пригодность)
- Избранные лучше всего занимающие место люди, чтобы воспроизвести
- новое поколение Породы посредством перекрестного соединения и/или мутации (генетические операции) и родить потомков
- Оценивает отдельный fitnesses потомков
- Замена худшая оцениваемая часть населения с потомками
, ключ является частью воспроизведения, которая могла произойти сексуально или асексуально, с помощью генетических операторов Перекрестное соединение и Мутация .