Блог

В нашей программе мы используем генетический алгоритм с годами для решения задач для n переменных, каждая из которых имеет фиксированный набор из m возможных значений. Обычно это хорошо работает для ~ 1000 переменных и 10 возможностей.

Теперь у меня есть новая задача, в которой для каждой переменной существует только две возможности (вкл / выкл), но мне, вероятно, потребуется решать системы с 10 000 или более переменными. Существующий GA работает, но решение улучшается очень медленно.

Все EA, которые я нахожу, предназначены скорее для непрерывных или целых / плавающих задач. Какой из них лучше всего подходит для двоичных задач?

Что ж, генетический алгоритм в его канонической форме является одной из наиболее подходящих метаэвристик для задач с двоичным решением. Конфигурация по умолчанию, которую я бы попробовал, — это такой генетический алгоритм, который использует 1-элитарность и который настроен с выбором колеса рулетки, одноточечным кроссовером (100% скорость кроссовера) и мутацией с переворотом битов (например, вероятность мутации 5%). Я бы посоветовал вам попробовать эту комбинацию при скромном размере популяции (100-200). Если это не работает хорошо, я бы предложил увеличить размер популяции, а также изменить схему выбора на схему выбора турнира (начните с выбора бинарного турнира и увеличьте размер турнирной группы, если вам нужно еще большее давление отбора). Причина в том, что при более высоком размере популяции схема пропорционального отбора может не оказывать необходимого давления на отбор, чтобы направить поиск в оптимальную область.

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

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

Как сказал Донандре, canonical GA был в значительной степени разработан для двоичных задач.

Однако…

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

Рулетка, выбор турнира и элитарность — хорошие идеи (возможно, сохранение более 1, это черное искусство, кто может сказать …). Вы также можете извлечь выгоду из адаптивной мутации. Старое эмпирическое правило заключается в том, что 1/5 потомства должно быть лучше, чем у родителей — следите за этим количеством и соответствующим образом варьируйте частоту мутаций. Если потомство выходит хуже, тогда мутируйте меньше; если потомство постоянно лучше, тогда мутируйте больше. Но для скорости мутации требуется компонент инерции, чтобы он не адаптировался слишком быстро, и, как и в случае с любым метапараметром, настройка этого является чем-то вроде черного искусства. Удачи!

Почему бы не попробовать линейную / целочисленную программу?