Практическое применение упаковки бина с использованием генетического алгоритма

Question

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

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

Answer 1

Фон

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

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

В твоем случае

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

Одним из преимуществ ГА по сравнению с классическими методами упаковки бинов может быть ее способность эффективно решать проблемы со сложными ограничениями. Например, вот статья, в которой используются GA для решения задачи оптимизации упаковки прямоугольного призматического бункера произвольного размера в одном контейнере произвольного размера (не правда ли?). Хотя классические методы обычно очень эффективны для выпуклых задач, таких как традиционная упаковка бинов, после добавления невыпуклых ограничений их становится гораздо труднее решать. Для таких проблем другие методы, такие как GA (среди прочих), как правило, работают очень хорошо.