Для каких типов задач подходят алгоритмы genti c?

Question

(Некоторое время я размышлял, подходит ли это вопрос для сайта вопросов и ответов. Я думаю, что да - ответы могут быть частично субъективными, но я надеюсь, что в ответах я ищу объективные критерии. Возможно, SO - не лучший сайт в сети, но давайте попробуем здесь.)

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

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

Другой пример, с которым я столкнулся, - это использование ГА для нахождения максимума двумерной функции, координаты которой - геном. Вероятно, это было выбрано в качестве простого педагогического примера, чтобы сосредоточиться на том, как может быть реализован GA, но опять же, вопрос о том, является ли GA правильный выбор здесь в первую очередь, кажется менее чем ясным: разведение просто «произвольно» меняет местами координаты или - в эта реализация - берет среднее значение отдельных геномов, теряя всю историю оптимизации. Таким образом, для меня это пример проблемы, которая по своей сути не подходит для ГА, потому что смешивание геномов (координат), которое является основной идеей ГА, здесь не кажется полезным. И без него, то есть когда он сводится только к мутациям, ГА представляет собой просто случайное блуждание по фазовому пространству с перезапусками.

В общем, ГА более подходят для задач с дискретными пространствами решений с высокой комбинаторной сложностью, чем исследование непрерывных фазовых пространств. Какие еще аспекты следует учитывать?

Answer 1

Действительно сложно предсказать исход и SA, и GA (как и сама жизнь?).

Мутация GA чем-то похожа на соседнее предложение SA, поэтому ключевым отличием является селекционная часть GA.

Скажем, x, y - оба предложения решения вашей проблемы .

Если есть смысл взять 1 часть x и 1 часть y для лучшего решения, у GA есть потенциал.

Вы должны использовать комбинацию интуиции и экспериментов чтобы проверить, верно ли приведенное выше.

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

Для минимизации функции в 2D (скажем, 0 - минимум), это обычно не имеет особого смысла, если (a, b) близко к 0, а (c, d) близко до 0, (a, d) и (c, b) так же хороши, как и любые другие случайные предположения (во многих случаях).

Поиск по холмам будет иметь больше смысла в последнем. Размножение GA отличается от лазания по холмам.

Answer 2

На ум приходят две ситуации, в которых могут быть полезны генетические c алгоритмы (я не эксперт по эволюционным вычислениям, поэтому не стесняйтесь поправлять меня):

1. Оптимизация без объективов. Некоторые целевые функции приводят к очень нерегулярному ландшафту потерь, поэтому методы на основе градиента приводят только к локальным минимумам. В таком случае интересно исследовать пространство на основе «поведенческой новизны» или «творчества». См., Например, классическую страницу поиска новинок . Проще говоря, вы сопоставляете последовательности состояний (робота, агента или чего-либо еще) с поведениями в пространстве поведения и пытаетесь единообразно искать это пространство поведения. Последовательности состояний исследуются на основе того, насколько они новы (например, на основе их удаленности от более старых решений в пространстве поведения). Это также полезно, когда вы заинтересованы в разнообразных решениях, которые хорошо работают по сравнению со своими соседями ( например, развитие разнообразных виртуальных существ с поиском новинок и местным соревнованием ).

   Обратите внимание, что здесь имеет смысл использовать алгоритмы geneti c, поскольку у вас нет ни целей, ни информации о градиенте. Вы также не можете использовать имитацию отжига, поскольку она привязана к одной целевой функции и не заботится о новизне поведения.

2. Когда нас не интересует одно решение, но мы, скорее, хотим знать, какие части пространства с высокой вероятностью дают хорошие решения. Один из способов сделать это - определить распределение вероятностей с параметрами, скажем, theta, и выборку из него, затем вычислить математическое ожидание / среднее значение по выбранным решениям и использовать его градиент относительно theta для оптимизации распределения ( обратите внимание, что этот градиент не относится к начальному пространству поиска, где мы не хотим компьютерных градиентов).