Какой эволюционный алгоритм для оптимизации бинарных задач?

Question

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

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

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

Answer 1

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

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

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

Answer 2

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

Answer 3

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

Однако ...

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

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