Сегодня я прочитал эту запись в блоге Роджера Алсинга о том, как нарисовать реплику Mona Lisa, используя только 50 полупрозрачных полигонов.
Я увлекаюсь результатами для этого конкретного случая, поэтому мне было интересно (и это мой вопрос): как работает генетическое программирование и какие другие <сильные > проблемы могут быть решены генетическим программированием?
Есть некоторые дебаты относительно того, является ли программа Роджера Моны Лизы Генетическое программирование вообще. Это похоже на стратегию эволюции (1 + 1) . Оба метода являются примерами более широкого поля эволюционных вычислений, который также включает Генетические алгоритмы.
Генетическое программирование (GP) - это процесс разработки компьютерных программ (обычно в виде деревьев - часто Lisp программ). Если вы спрашиваете конкретно о GP, Джон Коза широко считается ведущим экспертом. Его сайт содержит множество ссылок на дополнительную информацию. GP, как правило, очень интенсивно вычисляется (для нетривиальных проблем часто используется большая сетка машин).
Если вы спрашиваете в более общем плане, эволюционные алгоритмы (EAs) обычно используются для обеспечения хороших приближенных решений проблем, которые не могут быть легко решены с использованием других методов (таких как NP-жесткие проблемы). В эту категорию попадают многие проблемы оптимизации. Это может быть слишком вычислительно-интенсивным, чтобы найти точное решение, но иногда достаточно оптимальное решение. В этих ситуациях эволюционные методы могут быть эффективными. Из-за их случайного характера эволюционные алгоритмы никогда не гарантируют найти оптимальное решение для любой проблемы, но они часто найдут хорошее решение, если оно существует.
Эволюционные алгоритмы также могут использоваться для решения проблем, которые люди действительно не знают, как их решить. EA, без каких-либо предубеждений или предубеждений людей, может создавать удивительные решения, которые сопоставимы или лучше лучших человеческих усилий. Просто необходимо, чтобы мы смогли найти хорошее решение, если бы оно было представлено нам, даже если мы не знаем, как создать хорошее решение. Другими словами, мы должны иметь возможность сформулировать эффективную функцию fitness.
Некоторые примеры
EDIT: Свободно доступная книга Полевое руководство по генетическому программированию содержит примеры того, где GP что привело к результатам, выгодным для человека.
Интересно, что компания за динамичной анимацией персонажа, используемая в таких играх, как Grand Theft Auto IV и новейшая игра Star Wars (The Force Unleashed), использовала генетическое программирование для разработки алгоритмов движения. Веб-сайт компании находится здесь, и видео очень впечатляют:
http://www.naturalmotion.com/euphoria.htm
Я считаю, что они имитировали нервную систему персонажа, а затем рандомизировали соединения в некоторой степени. Затем они объединили "гены" моделей, которые шли дальше, чтобы создавать все более и более "детей" в последовательных поколениях. Действительно увлекательная работа по симуляции.
Я также видел генетические алгоритмы, используемые в автоматах поиска пути, причем муравьи, ищущие продукты питания, являются классическим примером.
Генетические алгоритмы могут использоваться для решения большинства задач оптимизации. Однако во многих случаях существуют более совершенные, более прямые методы их решения. Он находится в классе алгоритмов метапрограммирования, что означает, что он способен адаптироваться ко всему, что вы можете на него набросить, учитывая, что вы можете создать метод кодирования потенциального решения, комбинирования/мутирования решений и принятия решения о том, какие решения лучше других. GA имеет преимущество перед другими алгоритмами метапрограммирования в том, что он может обрабатывать локальные максимумы лучше, чем чистый алгоритм подъема холма, например, имитированный отжиг.
http://en.wikipedia.org/wiki/Genetic_algorithm#Problem_domains
В моем тезисе я использовал генетическое программирование для моделирования эволюции видов на основе ландшафта, но это, конечно же, применение генетических алгоритмов A-life.
Проблемы GA хороши в проблемах подъема холма. Проблема в том, что, как правило, легче решить большинство этих проблем вручную, если только факторы, определяющие проблему, неизвестны, другими словами, вы не можете каким-либо другим образом достичь этого знания, сказать вещи, связанные с обществами и сообществами, или в ситуациях, когда у вас есть хороший алгоритм, но вам нужно точно настроить параметры, здесь GA очень полезны.
Ситуация тонкой настройки, которую я делал, заключалась в тонкой настройке нескольких игроков Othello AI на основе тех же алгоритмов, дающих разные стили игры, что сделало каждого противника уникальным и с его собственными причудами, а затем я решил, из первых 16 AI, которые я использовал в своей игре. Преимущество заключалось в том, что все они были очень хорошими игроками более или менее равного мастерства, поэтому он был интересен для человеческого противника, потому что они не могли угадать ИИ так же легко.
Вы должны спросить себя: "Могу ли я (априори) определить функцию, чтобы определить, насколько хорошо конкретное решение относится к другим решениям?"
В примере mona lisa вы можете легко определить, будет ли новая картина больше похожа на исходное изображение, чем на предыдущую картину, поэтому Genetic Programming можно "легко" применить.
У меня есть несколько проектов с использованием генетических алгоритмов. GA идеально подходят для задач оптимизации, когда вы не можете разработать полностью последовательный, точный алгоритм, решить проблему. Например: какая лучшая комбинация автомобиля характеризует его быстрее и в то же время более экономичную?
В настоящий момент я разрабатываю простую GA для разработки плейлистов. Моя GA должна найти лучшие комбинации альбомов/песен, которые схожи (это сходство будет "вычислено" с помощью last.fm) и предлагает плейлисты для меня.
Появилось новое поле в робототехнике, называемое Эволюционная робототехника (w: Evolutionary Robotics), в которой широко используются генетические алгоритмы (GA).
Псевдокод простого генетического алгоритма генерации
- Выберите начальную совокупность
- Оценить пригодность каждого человека в популяции
- Повторяйте до окончания: (достигнуто ограничение по времени или достаточная пригодность)
- Выберите лучших людей для воспроизведения
- Порождение нового поколения через кроссовер и/или мутацию (генетический операции) и родить потомство
- Оцените индивидуальную пригодность потомства.
- Заменить наихудшую часть населения с потомством
Ключом является часть воспроизведения, которая может произойти сексуально или беспорядочно, используя генетические операторы Crossover и Mutation.