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

Question

У меня есть проблема оптимизации, которую я пытаюсь решить, используя генетический алгоритм. По сути, существует список из 10 связанных переменных с действительными значениями (-1 <= x <= 1), и мне нужно максимизировать некоторую функцию из этого списка. Подвох в том, что в списке может быть только до 4 переменных! = 0 (условие подмножества). </p>

Математически говоря: Для некоторой функции f: [-1, 1] ^ 10 -> R мин ф (х) S.T. | {var в X с var! = 0} | <= 4 </p>

Некоторые сведения о f: эта функция НЕ похожа ни на какую целевую функцию ранца, такую ​​как сумма x * weight или что-то в этом роде.

Что я пробовал до сих пор:

Просто базовый генетический алгоритм над геномом [-1, 1] ^ 10 с пересечением в 1 точку и некоторой гауссовой мутацией по переменным. Я попытался закодировать условие подмножества в функции пригодности, используя только первые 4 ненулевых значения (ноль, как в , достаточно близких к 0 ). Этот подход работает не очень хорошо, и алгоритм привязан к 4 первым переменным и никогда не использует значения, превышающие это. Я видел некоторый GA для задачи 01-ранца, где этот подход работал хорошо, но, очевидно, это работает только с двоичными переменными.

Что бы вы посоветовали мне попробовать дальше?

Answer 1

Если ваша функция фитнеса быстрая и грязная для оценки, тогда дешево увеличить общую численность населения.

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

Я вижу два способа сделать это.

1. Вы создаете 210 различных "видов". Каждый вид определяется тем, какие 4 из 10 геномов им разрешено использовать. Затем вы можете запустить генетический алгоритм для каждого вида отдельно (или последовательно, или параллельно в кластере).

2. Каждый организм имеет только 4 значения генома (при создании случайного потомства выбирайте, какой геном наугад). Когда два организма спариваются, вы пересекаетесь только с соответствующими геномами. Если ваша пара организмов содержит 3 общих генома, вы можете случайным образом выбрать, какой из геномов вы предпочитаете в качестве 4-го. Вы также можете, как эвристик, избегать спаривания организмов, которые кажутся слишком генетически разными (то есть пара, которая имеет два или менее генома, может стать плохим потомком).

Надеюсь, это даст вам некоторые идеи, с которыми вы сможете работать.

Answer 2

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

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

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

Answer 3

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

Во-вторых, вы можете сделать свое ограничение мягким, а не жестким: штрафовать пригодность решения для каждой переменной с нулевым значением, кроме 4. (Вы могли бы начать с еще большего ослабления ограничения, допуская 9 0-значных переменных, затем 8 и т. Д., И убедитесь, что GA способен обработать эти варианты проблемы, прежде чем сделать проблему более сложной.)

В-третьих, возможно, стоит попробовать двухточечный или многоточечный кроссовер вместо 1-точечного.

Надеюсь, это поможет.

-Ted