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

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



Смотрите также:
Курсовая работа по курсу «Дискретная математика» Тема: Разработка алгоритма и программного...
О налоге на природные ресурсы...
Лабораторная работа посвящена экспериментальной проверке теоретически полученной оценке функции...
Учебная программа по дисциплине программирование маслянкин В. И...
Краснер Н. Я., Пастухов А. И., Щепина И. Н...
Лекция №2
Лекция Задачи, модели, алгоритмы, программы...
Показательно-степенные уравнения являются немаловажным разделом алгебры...
Владимир Петров История развития алгоритма решения изобретательских задач – ариз информационные...
Владимир Петров История развития алгоритма решения изобретательских задач – ариз информационные...
Задачи и их решение Стандартные и нестандартные задачи Задачи «на работу» Задачи «на проценты»...
Задачи такого класса отличаются друг от друга значениями входящих в них параметров. Так...



скачать

УДК 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




Скачать 31,04 Kb.
оставить комментарий
Дата02.10.2011
Размер31,04 Kb.
ТипДокументы, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Документы

наверх