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

голоса
33

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

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

Задан 10/12/2008 в 09:58
источник пользователем
На других языках...                            


8 ответов

голоса
28

Существует некоторая дискуссия о том, является ли программа Джоконда Роджера является генетическое программирование на всех. Это , кажется, ближе к (1 + 1) Эволюция стратегии . Обе методики являются примерами более широкой области эволюционных вычислений, который также включает в себя генетические алгоритмы .

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

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

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

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

EDIT: Свободно доступная книга, Руководство поля для генетического программирования , содержит примеры того , где ГП произвел человек конкуренции результаты.

Ответил 10/12/2008 в 13:21
источник пользователем

голоса
9

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

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

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

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

Ответил 10/12/2008 в 13:55
источник пользователем

голоса
8

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

Ответил 10/12/2008 в 10:33
источник пользователем

голоса
6

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

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

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

Ответил 10/12/2008 в 10:11
источник пользователем

Ответил 10/12/2008 в 10:10
источник пользователем

голоса
5

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

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

Ответил 10/12/2008 в 10:30
источник пользователем

голоса
4

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

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

Ответил 10/12/2008 в 13:59
источник пользователем

голоса
2

Там в развивающейся области робототехники называют эволюционной робототехники ( ш: Эволюционные Robotics ), которая использует генетические алгоритмы (ГА) в большой степени.

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

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

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

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

Ответил 14/12/2008 в 23:38
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more