Принудительные ограничения в генетическом алгоритме с DEAP

Question

Я пытаюсь использовать генетический алгоритм с DEAP для решения проблемы оптимизации не все, что отличается от проблемы с рюкзаком. Хромосома представлена ​​вектором целых чисел, и ограничение состоит в том, что сумма вектора должна быть равна некоторому числу X. Кажется неэффективным справляться с этим в оценке пригодности, поскольку существует относительно небольшое количество кроссоверов/мутаций, что приведет к имеющий вектор с суммой, точно равной X.

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

Answer 1

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

Существует множество способов эффективного управления численными ограничениями при использовании эволюционных алгоритмов. Я рекомендую вам следующую статью от Coello Coello, которая представляет собой обширное исследование различных методов, которые могут быть использованы. Документация DEAP содержит около code examples.

Carlos Коэльо Коэльо, Теоретические и численные методы ограничения обработки, используемые с эволюционными алгоритмами: обзор состояния техники, компьютерные методы в прикладной механики и машиностроения, том 191, Issues 11-12, 4 января 2002, Pages 1245-1287, ISSN 0045-7825, http://dx.doi.org/10.1016/S0045-7825(01)00323-1. http://www.sciencedirect.com/science/article/pii/S0045782501003231

Обратите внимание, что последствия переназначения следует учитывать, поскольку кроссовер и мутация должны передавать генетический материал от родителей к потомству. Если ваше сопоставление перетасовывает слишком много значений, результат может быть более или менее случайным. Может быть, вы должны попытаться определить проблемных операторов, которые производят менее недействительных лиц.

Также обратите внимание, что я разработчик DEAP, и ответ также можно найти на mailing list.