Каковы типичные случаи использования генетического программирования?

Question

Сегодня я прочитал эту запись в блоге Роджера Алсинга о том, как нарисовать копию Моны Лизы , используя только 50 полупрозрачных многоугольников.

Я очарован результатами для этого конкретного случая, поэтому мне было интересно (и это мой вопрос): как работает генетическое программирование и что еще проблемы могут быть решены с помощью генетического программирования ?

Answer 1

Есть некоторые споры относительно того, является ли программа Роджера Мона Лизы Генетическим Программированием вообще. Похоже, что это ближе к (1 + 1) Стратегия эволюции . Оба метода являются примерами более широкой области эволюционных вычислений, которая также включает Генетические алгоритмы .

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

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

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

Некоторые примеры

• Командующий продавец
• Судоку

РЕДАКТИРОВАТЬ: Свободно доступная книга, Полевое руководство по генетическому программированию , содержит примеры того, как ВП дала человечески конкурентоспособных результатов.

Answer 2

Интересно, что компания, которая стояла за динамической анимацией персонажей, используемой в играх, таких как Grand Theft Auto IV и последняя игра «Звездные войны» (The Force Unleashed), использовала генетическое программирование для разработки алгоритмов движения. Сайт компании находится здесь, и видео очень впечатляет:

http://www.naturalmotion.com/euphoria.htm

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

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

Answer 3

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

Answer 4

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

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

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

Answer 5

Вы должны спросить себя: «Могу ли я (априори) определить функцию, чтобы определить, насколько хорошо конкретное решение относительно других решений?»

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

Answer 6

http://en.wikipedia.org/wiki/Genetic_algorithm#Problem_domains

Answer 7

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

В данный момент я разрабатываю простой GA для разработки плейлистов. Мой GA должен найти лучшие комбинации альбомов / песен, которые похожи (это сходство будет «вычислено» с помощью last.fm) и предлагает плейлисты для меня.

Answer 8

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

См. w: Генетический алгоритм :

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

1. Выберите начальную популяцию
2. Оценка пригодности каждого человека в популяции
3. Повторять до прекращения: (достигнут лимит времени или достаточная приспособленность)
4. Выберите лучших людей для воспроизведения
5. Порода нового поколения путем кроссовера и / или мутации (генетическая операции) и родить потомство
6. Оценить индивидуальные качества потомства
7. Заменить наихудшую часть населения потомством

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