Главная » 2014 » Август » 30 » Скачать Эволюционные алгоритмы на базе блочных технологий для решения задач упаковки контейнера. Сурначев, Максим Юрьевич бесплатно
7:12 AM
Скачать Эволюционные алгоритмы на базе блочных технологий для решения задач упаковки контейнера. Сурначев, Максим Юрьевич бесплатно
Эволюционные алгоритмы на базе блочных технологий для решения задач упаковки контейнера
Диссертация
Автор: Сурначев, Максим Юрьевич
Название: Эволюционные алгоритмы на базе блочных технологий для решения задач упаковки контейнера
Справка: Сурначев, Максим Юрьевич. Эволюционные алгоритмы на базе блочных технологий для решения задач упаковки контейнера : диссертация кандидата технических наук : 05.13.18 Уфа, 2005 97 c. : 61 06-5/799
Объем: 97 стр.
Информация: Уфа, 2005
Содержание:
1 Задачи раскроя-уиаковки: аиалитический обзор моделей и методов ихрешеиия
11 Задача одномерного раскроя-упаковки
111 Методы, использующие математическое программирование
112 Комбинаторные методы
113 Приближенные и эвристические методы
114 Методы локального поиска оптимума
115
Заключение по задаче одномерного раскроя-упаковки:
12 Задача прямоугольного раскроя-упаковки
121 Методы, использующие математическое программирование
122 Комбинаторные методы
113 Приближенные и эвристические методы
124 Методы локального поиска оптимума
13 Задача упаковки трехмерного контейнера и ее постановки
131 Технологические ограничения в задаче упаковки контейнера
132 Комбинаторные методы
133 Эвристики и методы локального поиска оптимума
134
Выводы по задаче контейнерного раскроя-упаковки:
14
Выводы
2 Математическая модель коитейнериой уиаковки и одиоироходиыеметоды ее решеиия
21 Математическая модель задачи контейнерной упаковки
22 Блочная структура трехмерной упаковки и ее свойства
221 Блок-структуры прямоугольной упаковки
222 Задачи прямоугольно-ориентированного линейного раскроя
223 Блок-структура RP, адаптированная для контейнернойупаковки
23 Блочный декодер
24 Учет технологических ограничений в блочном декодере
2,4
Выводы по второй главе
3 Методы локального поиска оитимума с использованием блочногодекодера
31 Метод случайных перестановок приоритетного списка
32 Генетические методы Классический генетический алгоритм
33 Генетический алгоритм с блочным декодером
34 Эволюционный алгоритм (1+1)
35 Нижние границы для задач раскроя упаковки
35
Выводы по третьей главе
4 Численные эксперименты
41 Реализация программного обеспечения
42 Выбор целевой функции для численных экспериментов
42 Выбор параметров алгоритмов
43 Численные эксперименты
431 Эксперимент на случайно сгенерированных примерах
432 Сравнительный эксперимент с другими методами решенияпоставленной задачи
44
Выводы по четвертой главе
Введение:
Диссертационная работа носвящена моделированию и разработке методоврасчета для задачи трехмерной упаковки контейнера, использующих блочныйдекодер; программной реализации разработанных методов и численномуисследованию их эффективности.Актуальность проблемы. В научной и производственной деятельностичасто встречаются ситуации раскроя и упаковки встречаются очень часто: этозадачи раскроя материала на заготовки различных форм и размеров, и задачиразмещения совокупности предметов на ограниченной площади или вограниченном пространстве. Многие другие проблемы также сводятся кситуациям раскроя и упаковки. Среди многообразия постановок задач раскрояи упаковки самостоятельный интерес представляют задачи упаковкипараллелепипедов (3DBPP). К таким задачам относятся, например,оптимизация перевозки и складирования грузов, планирование помещений,проектирование систем, конструктивно выполненных в виде набора блоков,компоновка деталей. К рассматриваемым проблемам сводится также и рядзадач планирования и распределения ресурсов. Несмотря на конкретноепрактическое применение, круг работ по решению задач параллелепипеднойупаковки невелик. Это объясняется сложностью задач и высокойтрудоемкостью их решения. Поэтому является актуальной разработка,эффективных алгоритмов решения задач раскроя-упаковки параллелепипедов.Задача раскроя-упаковки принадлежит к классу NP-трудных проблем, тоесть для ее точного решения не известно алгоритма полиномиальнойсложности. Более того, рассматриваемая задача является NP-трудной в сильномсмысле, так как содержит NP-трудную задачу в качестве подзадачи. До сих порне разработано эффективных и достаточно точных способов расчета нижнихграниц для данной задачи, позволяющих определить достижение оптимума.5Таким образом, точные алгоритмы сводятся к полиому перебору вариантов. Всвязи с этим, использование точных методов для решения задачи раскрояупаковки часто оказывается нецелесообразным и невозможным по причинебольших затрат времени. Поэтому большое значение уделяется разработке иисследованию эвристических методов оптимизации. Одним из перспективныхнаправлений является разработка метаэвристических алгоритмов, основанныхна известных метаэвристических стратегиях, с успехом используемых длярешения многих задач дискретной оптимизации. Для большинстваметаэвристик доказана их асимптотическая сходимость, что является важнымдоводом в пользу их активного использования.Целью работы является разработка и исследование моделей и методоврешения задач контейнерной упаковки на базе блочной технологии иреализация комплекса программ, ориентированных на достижениерационального решения в ограниченное время.Задачи, поставленные для достижения цели работы:1. Рассмотреть постановки основных задач трехмерной упаковки, описатьих математические модели;2. Разработать блочный способ моделирования трехмерных упаковок.Сформулировать его основные свойства и установить связь с другимиспособами кодирования;3. Разработать блочный декодер конструирования трехмерных упаковок набазе применения простых стратегий.4. Выбрать эволюционные алгоритмы для локального поиска оптимальныхупаковок и осуш;ествить их адаптацию к решению задачи с блочным декодеромконструирования упаковок;5. Разработать программное обеспечение, реализуюш;ее предложенныеметоды и алгоритмы;66. провести численный эксперимент с целью исследования эффективностипредложенных алгоритмов.На защиту выносятся:1. Блочный способ кодирования трехмерных упаковок.2. «Блочный декодер» - алгоритм конструирования блочной структурыупаковки по приоритетному списку (перестановке параллелепипедов).3. Эволюционные методы, работающие с блочным декодером для решенияпоставленной задачи.4. Компьютерная программа, реализующая разработанные методы иалгоритмы.5. Анализ эффективности предложенных методов на основе результатовчисленного эксперимента.Научная новнзна работы заключается в следующем:1. Блочный способ кодирования контейнерных упаковок. Он являетсяметодом кодирования и моделирования упаковок. Его преимуществамиявляются: а) взаимнооднозначное представление упаковка-кодировка; б) легкаямодифицируемость; в) учет пустых пространств; г) возможность адаптации длялюбых постановок задач и ограничений; д) возможность использования дляразнообразных методов локального поиска.2. Блочный декодер конструирования упаковки, использующий блочныйспособ кодирования на базе простых стратегий следующий подходящий {NF) ипервый подходящий {FF). Декодер универсален и может применяться в составеразличных методов локального поиска оптимума.
Ъ. Модификация гибридного группирующего генетического алгоритмадля рещения задачи прямоугольно-ориентированного линейного раскроя всоставе алгоритма построения 3D-ynaK0B0K и использование его в качествеоценки нижней границы.. 74. Адаптация эволюционных алгоритмов — метода случайныхперестановок, (1+1)-ЕА и генетического алгоритма для задач упаковкиконтейнера на базе блочного декодера.
Практическая ценность работы. Разработанное программное обеспечениерешает задачу, имеющую многочисленное практическое применение, в томчисле упаковка грузов при их транспортировке, планирование размещенияподземных сооружений, разрезание губчатой резины. Важным аспектомпрактического применения разработанных методов является учеттехнологических ограничений. В диссертации представлены методики учетатаких ограничений в рамках разработанных алгоритмов.
Работа выполнялась при частичной поддержке грантов Российского Фондафундаментальных исследований (РФФИ), проекты 99-01-000937 и 01-01-000510.
Анробация работы. Результаты работы докладывались и обсуждались наследующих конференциях и семинарах:1. Международная научная конференция "Моделирование, вычисления,проектирование в условиях неопределенности-2000" (Уфа, 2000).
2. Студенческая научно-теоретическая конференция 2001 (Уфа, 2001)3. Всероссийская научно-практическая конференция "Ресурсосберегающиетехнологии: математическое обеспечение оптимизационных задач в системахавтоматизированного проектирования" ОПТИМ-2001 (Санкт-Петербург, 2001);4. CSIT'2001: Computer Science and Informational Technologies (Уфа, 2001);5. Вторая Всероссийская научно-техническая конференция «Мехатроника,автоматизация, управление - 2005» (Уфа, 2005).
6. Семинары кафедры вычислительной математики и кибернетикиУфимского государственного авиационного технического университета.
По теме диссертации опубликовано 10 работ: 6 статей и 4 трудовконференций.8Содержание диссертации.
Ш Во введении к диссертации обоснована актуальность решаемой научнойнроблемы; сформулирована цель и задачи исследования; приведены^ результаты, выносимые на защиту; отмечена их научная новизна. Приведенысведения об апробации работы и публикациях.^ В иервой главе проведен аналитический обзор моделей и методов решениязадач раскроя-упаковки.
Во второй главе приводятся математические постановки задач упаковкиконтейнера. Предложена блочная модель кодирования трехмерной упаковки и^ разработанный на ее основе блочный декодер.
Третья глава посвящена методам локального поиска, использующими^ блочный декодер. Предложен метод случайных перестановок, вариантклассического генетического метода и эволюционный алгоритм.
В четвертой главе описывается реализация ПО и порядок проведениячисленного эксперимента.
Выражаю глубокую благодарность своему научному руководителюЭ.А. Мухачевой за ее вклад в определение направления диссертационнойработы, советы и помощь при написании текста диссертации и проведенииэксперимента, а также А.С. Филипповой за помощь при использовании общейтехнологии блочных структур.
Список литературы:
1. Батиш;ев Д.Ю. Генетические алгоритмы решения экстремальных задач //учебное пособие под ред. Я.Е.Львовича. Воронеж: Воронежский гос. техн. ун-т;Нижегородский ун-т. 1995. 96.
2. Булавский В.А., Яковлева М.А. О решении задач онтимального раскроя линейных материалов на ЭВМ // Математические методы в технико-экономических расчетах: Материалы научного совеш;ания. т. IV. М.: АН СССР.1961.С.83-87.
3. Валеева А.Ф., Гареев И.Р., Мухачева Э.А. Задача одномерной упаковки: рандомизорованный метод динамического перебора и метод перебора сусечением. //Информационные технологии. Нриложение. 2003. №2. 24.
4. Валеева А.Ф., Тоцков И.Е., Гареев И.Р. Методы решения трехмерной задачи в интеллектуальной системе раскроя-упаковки // МатериалыРеспубликанской научно-технической конференции "Интеллектуальноеуправление в сложных системах - 99". Уфа, 1999. 36-38.
5. Гери М., Джонсон Д. Вычислительные машины и трудноразрешимые задачи // М. Мир. 416.
6. Гимади Э.Х,, Залюбовский В.В. Задача упаковки в контейнеры: асимптотически точный подход // Известия вузов. Математика. 1997. №12.С.25-33.
7. Гимади Э.Х., Залюбовский В.В., Шарыгин Н.И. Задачи упаковки в полосу: асимптотически точный подход // Известия высших учебныхзаведений. Математика. №12(427). 1997. 34-44.
8. Ермаченко А.И., Сиразетдинов Т.М. Рекурсивный метод для решения задачи гильотинного раскроя // Нринятие решений в условияхнеопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2000. 35-39.90
9. Канторович Л.В., Залгаллер В.А. Рациональный раскрой промышленных материалов //Новосибирск: Наука СО, 1971. 299.
10. Картак В.М. Оптимальная упаковка N-мерных параллелепипедов в полубесконечность // 12-я Байкальская международная конференция, методыоптимизации и их приложения. Иркутск. 2001. 18-22.
11. Кацев СВ. Об одном классе дискретных минимаксных задач: Кибернетика, 1979, Яо5, 139-141.
12. Кокотов В.З. Алгоритм плотного размещения разногабаритных элементов на плате // Информационные технологии. 1998. № 11. 16-21.
13. Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискрет, анализ и исслед. операций. Сер. 2.2003, Т. 10, № 1 . С . 11-43.
14. Липовецкий А.И. К оптимизации свободного размещения прямоугольников // Автоматизация проектирования в машиностроении.Минск.1985. 80-87.
15. Мзосачева А.С., Валеева А.Ф., Картак В.М. Задачи двухмерной упаковки в контейнеры: новые подходы к разработке методов локального поискаоптимума. М.: МАИ, 2004, 193 с.
18. Мухачева А.С., Сурначев М.Ю. Задача параллелепипедной упаковки: декодер на базе блочных структур // Принятие решений в условияхнеопределенности: Межвуз. науч. сб. Уфа: УГАТУ, 2005. 51-55.
19. Мухачева А.С., Ширгазин P.P. Задачи упаковки прямоугольников: рандомизированная эвристика на базе двойственной схемы локального поискаоптимума //Информационные технологии. 2003. Нй5. 18-23.
20. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. -М . :Машиностроение. 1984. 176.
21. Мухачева Э.А., Верхотуров М.А., Мартынов В.В. Модели и методы расчета раскроя-упаковки геометрических объектов // Уфа. УГАТУ. 1998.С.216.
22. Мухачева Э.А., Картак В.М. Модифицированный метод ветвей и границ: алгоритм и численный эксперимент для задачи одномерного раскроя //Инфор.\1ационные технологии. 2000. №9. 15-22.
23. Мухачева Э.А., Мухачева А.С., Чиглинцев А.В. Генетический алгоритм блочной структуры в задачах двумерной упаковки // Информационныетехнологии. 1999. №11. 13-18.92
25. Норенков И.Н.. Эвристики и их комбинации в генетических методах дискретной оптимизации. //Информационные технологии. 1999. Ш1. 2-7.
26. Романовский И.В. Алгоритмы решения экстремальных задач // М.: Наука. 1977. 168.
27. Романовский И.В. Решение задачи гильотинного раскроя методом переработки списка состояний // Кибернетика. 1969. Jvfe 1. 102-104.
28. Романовский И.В., Христова Н.Н. Решение дискретных минимаксных задач методом дихотомии // ЖВМ и МФ. 1973. 13(5). 1200-1209.
29. Сборник трудов ВНИИСИ "Модели и методы оптимизации" - М., 1980, №З.С.352.
30. Стоян Ю.Г., Яковлев СВ. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наукова думка. 1986. 268 с,
31. Сурначев М.Ю. Задача параллелепипедной упаковки в контейнер: обзор методов решения. // Принятие решений в условиях неопределенности: Межвуз.науч. сб. Уфа: УГАТУ, 2003. 208-211.93
32. Сурначев М.Ю. Задача целочисленного линейного раскроя: обзор алгоритмов. // Принятие решений в условиях неопределенности: Межвуз. на}^.сб. Уфа: УГАТУ, 2002. 168-171.
33. Сурначев М.Ю. Применение блочных технологий к задаче упаковки контейнера // Мехатроника, автоматизация, управление - 2005: ВтораяВсероссийская научно-техническая конференция. Сб. тр. Т.2. Уфа: УГАТУ.С.10-12.
34. Сурначев М.Ю., Собко СП. Гибридный группируюпдий генетический алгоритм для задачи упаковки. // Моделирование, вычисления, проектированиев условиях неопределенности-2000: Сб.науч.тр. Уфа: УГАТУ, 2000. 458-459.
35. Сурначев М.Ю., Собко СП. Гибридный группируюш;ий генетический алгоритм. // Дискретный анализ и исследование операций: Матер, конф.Повосибирск: Изд-во Института математики, 2002. 237.
36. Сурначев М.Ю., Собко СП. Гибридный группирующий генетический алгоритм. // Математическое моделирование в решении научных итехнических задач. Выпуск 2. Уфа: Пзд-во "Технология", 2001. С70-75.
37. Тоцков П.Е. Методы решения задачи трехмерной упаковки на базе алгоритма динамического перебора. Рукопись депонирована в ВППИТИ,№2589-В99, 1999.
38. Шабрина Л.М. К разработке линейного алгоритма решения задачи трехмерной упаковки// Математическое моделирование в решении научных итехнических задач. - Уфа, 1994. 3-5.
39. Aurts Е., Lenstra J., edit. Local Search in Combinatorial Optimization/ // John Wiley&Sons. 1996.
40. Baum S., Trotter Jr.L. Integer rounding for polymatroid and branching optimization problems. // SIAM J. Alg. Disc. Meth. 1981. 2(4). P.416-425.94
41. Belov G., Scheithauer G. A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths // European Journal of OperationalResearch. 2002. 141. P.274-294.
42. Bischoff E.E., Marriott M.D. A comparative evaluation of heuristics for container loading // European Journal of Operation Research, 44(1990). Y.261-216.
43. Bortfeldt A., Gehring H., Applying tabu search to container loading problems // Operations Research Proceedings 1997, Springer, Berlin, 1998, P.533-538.
44. Bortfeldt A., Gehring H.. A hybrid genetic algorithm for the container loading problem. // European Journal of Operation Research, 131(2001). P.143-161.
45. Boschetti M.A. The Two-Dimensional Finite Bin Packing Problem // Quaterly Journal of the Belgian, French and Italian Operations Research Societies2002.
46. Chen P., Chen Y., Goel M., Mang F. Approximation of Two-Dimensional Rectangle Packing // CS270 Project Report, Spring 1999.
47. Dykhoff H. A typology of cutting and packing problems // Evropean Journal of Operational research. 1990. Vol. 44. P.145-159.
48. Faroe O., Pisinger D., Zachariasen M. Guided local search for the three- dimensional bin packing problem // Tech. Rep. 99/13, DIKU, University ofCopenhagen, Denmark. Dept. of Computer Science, University of Copenhagen.
49. Folkenauer E. The grouping genetic algorithms for Bin-Packing. JORBEL- Belgian Journal of operations Research, Statistics and Computer Science, 1995. V.
50. Gehring Н., Bortfeldt A.. Genetic algorithm for solving the container loading problem. // International Transactions in Operation Research 4(5-6). P.401-418.
51. Gilmore P.C. and Gomory R.E. A Linear Programming Approach to the Cutting-stock Problem, Operations Research 9(1961), P.849-859.
52. Gilmore P.C, Gomory R.E. Multistage cutting stock problems of two and more dimensions // Operation Research, 13(1965). P.94-120.
53. Hinxman A. The Trim-Loss and assortment problems: a survey // European Journal of Operational Research. 1980. N11. P.863-888.
54. I.R. Gareev, R.R. Shirgasin, S.N. Sobko, M.Yu. Sumachev. Heurisms for One-Dimensional Bin-Packing Problem // CSIT'2001: Computer Science andInformational Technologies. - Ufa: USATU Publishers. - P.263-267.
55. Imahori S., Yaguira M., Ibaraki T. Local Search Heuristics for the Rectangle ' Packing Problem With General Spatial Costs // MIC'2001 - 4th MetaheuristicsInternational conference. P.471-476.
56. Liu D., Teng H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles. // European Journal of Operation Research. 1999.
57. Lodi, S. Martello, D. Vigo. Heuristic algorithms for the three-dimensional bin packing problem // European Journal of Operational Research 141 (2002). P.410-420.
58. Marcotte O. The cutting stock problem and integer rounding // Math. Program. 1985. 33(1). P.82-92.
59. Martello S. and Toth P. Knapsack problems: Algorithms and Computer Implementations. In: Operations Research. 1990. v. 32. P.983-998.
60. Martello S., edit. Special issue: Knapsack, Packing and Cutting, Part II: Multidimensional Knapsack and Cutting Stock Problems // INFOR. 1994. 32(4).96
61. Martello S., Pisinger D., Vigo D., The three-dimensional bin packing problem, Operations Research 48 (2000). P.256-267.
62. Martello S., Toth P. Knapsack problems: Algorithms and Computer Implementations. // YOHN WILEY&SONS. Chichester. 1990.
63. Martello S., Vigo D. Exact solution of two-dimensional finite bin packing problem // Management Science. 1997. 35. P.64-68.
64. Morabito R., Arenales M., An AND/OR graph approach to the container loading problem // International Transactions in Operational Research 1 (1994).P.59-73.
65. Mukhacheva E., edit. Special issue: Decasion Making under Conditions of Uncertainty (Cutting-Packing Problems)/ The International Scientific Collection.1997. Ufa. Russia.
66. Mukhacheva E.A., Zalgaller V.A. Linear Programming Cutting Problems // International Journal of Software Engineering and Knowledge Engineering. 1993. V.
68. Pisinger D. Heuristic for the container loading problem // European Journal of Operation Research, 141(2002). P.3 82-392.
69. Rehtenberg L, Evolutionsstrategie: Optimerung Technischer systeme nach Prinzipen der Biologischen Evolution // Stuttgart: Formann-Holzboog Verlag, 1973.
70. Scheithauer G. and Temo J. A Branch-and-Bound Algorithm for Solving One- dimensional Cutting Stock Problems Exactly, Applicationes Mathematicae,23.2:151-167,1995.97
71. Scheithauer G. and Temo J. About the gap between the optimal values of the integer and continuous relaxation one-dimensional cutting stock problem. Oper. Res.Proc. 1991, Springer-Verlag, Berlin Heidelberg, P.439-444.
72. Schwerin P., Wascher G. A New Lower Bound for the Bin-Packing Problem and its integration to MTP // Pesquisa Operational. 1999. 19(2). P. 111-131.
73. Temo J., Lindeman R., Scheithauer G. Zuschnitprobleme und ihre praktische 1.osung. - Leipzig. 1987.
74. Valeyeva A.F. and Totskov LE. Developed of Three-Dimensional Methods Decision Making under Conditions of Uncertainty (Cutting-Packing Problems). Ufa,1998.-P.198-206.
75. Valeyeva A.F., Agliullin M.N. Ant Colony Algorithm for the 2-D Bin- Packing Problem: Numerical Study // Proceedings of the 5th International Workshopon Computer Science and Information Technologies, 2003. P.I 10-114.
76. Verhoturov M.A., Sergeyeva O.Y. The sequential value correction method for the two-dimensional irregular cutting stock problem // Pesquisa Operacional.2000. V. 20. N2. P.233-247.
77. Yanasse H., edit. Special issue: Cutting and Packing Problems// Pesquisa Operacional. 1999. 19(2).
