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

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

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

10.12.2008 08:58:20
В общем, все методы ИИ хороши, когда вы не знаете, как решить проблему.
zaratustra 14.12.2008 22:54:52
8 ОТВЕТОВ
РЕШЕНИЕ

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

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

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

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

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

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

28
20.12.2008 22:50:34
Дебаты вроде глупые. Определение ясно, и в коде Моны Лизы отсутствует рекомбинация. Помимо неправильного определения, использование рекомбинации может значительно сократить количество итераций (хотя и за счет более дорогих итераций), что потенциально улучшит общее время выполнения.
Konrad Rudolph 20.12.2008 22:55:48
Подробный генератор судоку anthony-tresontani.github.com/Python/2012/12/31/…
trez 4.01.2013 06:50:53

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

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

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

6
11.03.2009 17:43:08
«Я использовал генетическое программирование в своей диссертации, чтобы симулировать эволюцию видов на основе рельефа» - что-то в Интернете, что можно посмотреть? : P
fableal 11.09.2012 21:31:17

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

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

5
10.12.2008 09:30:21

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

8
10.12.2008 09:33:09

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

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

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

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

9
10.12.2008 12:55:01
Пример муравья, о котором вы упомянули, - это не Генетический алгоритм, это то, что называется алгоритмом муравьиных колоний, они имеют схожие цели, но алгоритмы совершенно разные
Robert Gould 11.12.2008 06:40:33
@Роберт. Пример муравья, о котором он говорил, на самом деле является классическим игрушечным примером для GP, он полностью отличается от алгоритма Ant Colony.
Dennis 9.03.2011 07:43:21

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

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

4
10.12.2008 12:59:35
Ух ты, программное обеспечение плейлиста звучит как забавный проект. Я надеюсь, что вы поделитесь тем, что вы узнали из этого, с публикой :)
Dave R. 10.12.2008 15:31:50

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

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

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

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

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

2
14.12.2008 22:52:13