Задачи раскроя-упаковки представляют собой важный прикладной раздел дискретной оптимизации. Среди них выделяются задачи ортогональной упаковки

Вид материала

Документы

Подобный материал:

• Задачи нелинейной и дискретной оптимизации. Методы решения. Постановка и экономико-математическая, 24.28kb.
• Бизнес план предприятия по производству упаковки, 37.58kb.
• Задачи оптимизации с ограничениями в виде неравенств. Постановка задачи. Геометрические, 42.48kb.
• Рабочая программа дисциплины основы теории принятия экономических решений цели и задачи, 92.73kb.
• Задачи нелинейной и дискретной оптимизации. Методы решения. Постановка и экономико-математическая, 25.18kb.
• Решение задач глобальной оптимизации большой размерности на многопроцессорных комплексах, 143.77kb.
• Б. Ф. Мельников (Тольяттинский государственный университет, B. Melnikov@tltsu ru, bormel@mail, 477.61kb.
• Создание асимметричных мембран в виде полых волокон из полиэфирсульфона методом двойной, 199.98kb.
• Методические указания к выполнению курсового проекта по дисциплине «Технология упаковочного, 401.66kb.
• Методы оптимизации дисциплина цикла обще-профессиональных дисциплин направления, 18.29kb.

М.В. СЕРГИЕВСКИЙ, С.Н. СЫРОЕЖКИН

Московский инженерно-физический институт (государственный университет)


РАЗРАБОТКА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ОРТОГОНАЛЬНОЙ УПАКОВКИ ПРЯМОУГОЛЬНЫХ ОБЪЕКТОВ В ДВУХМЕРНЫЙ КОНТЕЙНЕР


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


Задачи раскроя-упаковки представляют собой важный прикладной раздел дискретной оптимизации. Среди них выделяются задачи ортогональной упаковки. Актуальность проблемы создания эффективных алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер объясняется как широким практическим применением решения в различных областях, так и трудностью разработки адекватных математических моделей. Сложность решения задач раскроя-упаковки обусловлена их принадлежностью к классу NP-трудных задач комбинаторной оптимизации, то есть для них не существует методов, находящих точное решение за полиномиальное время [1].

Представленный метод основан на применении генетических алгоритмов - новой быстроразвивающейся области исследований. Генетические алгоритмы используют методы моделирования искусственных систем, которые основаны на процессах, происходящих в естественных системах [2, 3]. Основное отличие генетических алгоритмов от других оптимизационных процедур состоит в том, что поиск осуществляется не с помощью улучшения одного решения, а путём анализа целого множества альтернативных решений – популяции. В популяцию отбор решений происходит по принципу "выживания сильнейшего", то есть большая часть попадающих в популяцию решений обладают наилучшими значениями целевой функции. Работа генетического алгоритма начинается с некоторого начального множества допустимых решений. Таким образом, данный метод решения задач раскроя-упаковки, является представителем класса методов поиска локально-оптимального решения. К его преимуществам следует отнести быстроту получения эффективного решения.

Исходными данными для разработанного алгоритма являются размеры контейнера и прямоугольников. Под решением понимается последовательность номеров прямоугольных объектов, в соответствии с которой при помощи специально созданного декодера определяются их координаты в контейнере. Декодер использует стратегию замещения «первый подходящий» (SubFF) [4].

В разработанном генетическом алгоритме использованы три генетических оператора: кроссинговера (скрещивания), мутации и селекции. Оператор кроссинговера скрещивает пару решений из популяции; в данном алгоритме используется одноточечный оператор кроссинговера [3]. Оператор мутации включает две процедуры. Первая – перестановка, использует классический двухточечный оператор мутации для перестановки двух произвольно выбранных объектов. Вторая осуществляет поворот прямоугольника на 90^о относительно своего центра. Оператор селекции формирует новую популяцию решений, 80% которой составляют решения с наилучшими значениями целевой функции и 20% с наихудшими. Поскольку решения представляются в виде числовых последовательностей, работа операторов сводится лишь к простым перестановкам. Это позволяет существенно сократить время поиска решения.

Разработанный алгоритм способен решать задачи, имеющие большую размерность, за сравнительно короткое время. В случае существования решения со значением целевой функции 100% алгоритм в зависимости от размерности задачи находит решения со значениями целевой функции в диапазоне 97-100%. Например, для задачи с размерами контейнера 13,5 х 2,5 метра при 42-х прямоугольных объектах за 14 секунд было получено решение с целевой функцией 98,6%. Алгоритм реализован с помощью системы разработки приложений Delphi 2006.


Список литературы

1. Ковалев М.Я. Исследование операций. Курс лекций. Минск 2005.
   
2. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. М.: Физматлит. 2006.
   
3. Емельянов В.В., Курейчик В.М., Курейчик В.В. Теория и практика эволюционного моделирования. М.: Физматлит. 2003.
   
4. Филипова А.С. Методы решения задач ортогональной упаковки на базе технологии блочных структур. Авто-реф. дис. на д-ра техн. наук. Уфимский государственный авиа-тех. университет. Уфа, 2007.