Генетический алгоритм для задачи одномерной упаковки объектов

Дворянкин Александр Михайлович, Ибрагим Исмаил Адаму

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

Ключевые слова:одномерная упаковка, сила, нагруженные отрезки, генетический алгоритм, хромосома, мутация, кроссинговер, центр тяжести.