Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер



Скачать 29.91 Kb.
Дата17.01.2013
Размер29.91 Kb.
ТипДокументы

УДК 004.4(06) Технологии разработки программных систем


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

Московский инженерно-физический институт (государственный университет)
РАЗРАБОТКА АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ОРТОГОНАЛЬНОЙ УПАКОВКИ ПРЯМОУГОЛЬНЫХ ОБЪЕКТОВ В ДВУХМЕРНЫЙ КОНТЕЙНЕР
Для решения 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.




ISBN 978-5-7262-0883-1. НАУЧНАЯ СЕССИЯ МИФИ-2008. Том 11

Похожие:

Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconРазработка алгоритмов решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер
Предлагаются алгоритмы поиска глобально-оптимального решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер,...
Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconРазработка алгоритма и программного обеспечения для решения прикладной задачи теории графов
Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов
Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconПодготовка руки к письму для детей зпр
Способствовать развитию мыслительных операций: анализа, синтеза, сравнения, обобщения. Научить разным способам решения мыслительной...
Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconПрограмма по дисциплине программирование маслянкин В. И. Для очной формы обучения всего 260
Целью изучения дисциплины является изучение основ программирования, включая постановку задачи, выбор метода решения задачи, создание...
Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconМетоды оптимизации Введение в теорию сложности. Понятие о сложности решения задач
Основные определения: индивидуальная и массовая задачи, кодировка, алгоритм решения массовой задачи, временная сложность алгоритма....
Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconСтандартный контейнер, Стандартный сухой контейнер, Dry Container
Стандартный контейнер самый распространенный тип контейнеров. Применяется для перевозки большого ассортимента грузов, пригодных по...
Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconО применении модифицированного генетического алгоритма для решения задачи контроля границ беспроводной локальной сети

Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconПрименение параллельного алгоритма Bicgstab для решения трёхмерной упругопластической задачи 1
Применение параллельного алгоритма Bicgstab для решения трёхмерной упругопластической задачи1
Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconМетод генетического программирования для решения задачи оптимального управления
Приведен метод поиска решения на основе генетического алгоритма в виде функциональной зависимости управления от времени и начальных...
Разработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер iconПлотность упаковки различных конфигураций мембран
Однако трубчатые элементы являются довольно дорогими, так как характеризуются самой низкой плотностью упаковки, т е наименьшей площадью...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org