Улучшенный генетический алгоритм для задачи с несколькими рюкзаками

Должно быть любое количество достойных методов ГА, с которыми вы можете сравнить. Тем не менее, вы должны сначала попытаться четко установить, какой именно «традиционный» метод ГА вы уже протестировали.

Один хороший метод, который я могу порекомендовать, — это алгоритм NSGA-II, который был разработан для многоцелевой оптимизации.

Взгляните на следующее для других идей:

• Генетический алгоритм — Википедия
• Карлос А. Коэльо Коэльо (1999). "Всеобъемлющий обзор методов многокритериальной оптимизации, основанных на эволюции", Знания и информационные системы, Vol. 1, стр. 269-308.
• Карлос А. Коэльо Коэльо и др. (2005). "Текущие и будущие направления исследований в области эволюционной многокритериальной оптимизации", информация Обработка с помощью эволюционных алгоритмов, Springer.

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

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

Вы пытаетесь улучшить современные решатели с несколькими ранцами с помощью генетических алгоритмов? Или вы пытаетесь усовершенствовать технику генетического алгоритма, используя мультирюкзак в качестве тестовой платформы? (Можете уточнить?)

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

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

Я бы сначала изучил литературу по мультирюкзакам, чтобы увидеть, какие различные виды пространств поиска и методов решения люди использовали для мультирюкзаков. Какие операторы поиска они используют в своих оптимальных или субоптимальных методах (независимо от генетических алгоритмов)? Что они кодируют как переменные и что они кодируют как значения? Какие эвристические функции оценки используются? Какие ограничения они проверяют? Затем вы адаптируете их кодировки к вашим операторам мутации и скрещивания и посмотрите, насколько хорошо они работают в ваших генетических алгоритмах.

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