Сборники трудов ИСП РАН

Упаковка прямоугольников в полосу модифицированным методом Нелдера-Мида с использованием генетического алгоритма.

С.А. Мартишин, М.В. Храпченко.

Аннотация

Исследуется задача упаковки прямоугольников в полубесконечную полосу. Известно, что эта задача является NP-трудной. Предложен новый эвристический алгоритм упаковки с использованием модифицированного метода Нелдера-Мида, генетического алгоритма и линейного программирования. Проведенное экспериментальное исследование предложенного алгоритма на известных тестовых примерах демонстрирует его преимущества. Предложены перспективные направления его использования для упаковки произвольных выпуклых многоугольников. Показана принципиальная возможность распараллеливания данного алгоритма.

Ключевые слова

упаковка прямоугольников в полубесконечную полосу, генетический алгоритм, метод Нелдера-Мида, линейное программирование.

Издание

Труды Института системного программирования РАН, том 19, 2010, стр. 135-156.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

Полный текст статьи в формате pdf Вернуться к содержанию тома