Разработка и применение бионических моделей и методов в задачах автоматизации проектирования маршрутов обхода геометрических объектов тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Ганелина, Наталья Давидовна

• Ганелина, Наталья Давидовна
• кандидат технических наук
• 2007

Оглавление диссертации кандидат технических наук Ганелина, Наталья Давидовна

Введение

1. Постановка и анализ методов решения задачи построения маршрута обхода отрезков на плоскости

1.1. Описание проблемы оптимизации маршрута обхода отрезков на плоскости. Основные определения

1.2. Основные методы решения задачи построения цепей и циклов на множестве отрезков

1.2.1. Принцип жадности

1.2.2. Построение простых цепей и циклов на графе видимости концов отрезка. Выпуклая оболочка множества отрезков

1.2.3. Независимые и цело-координатные отрезки

1.2.4. Алгоритмы Хоффманна на графах видимости концов отрезков

1.3. Анализ эвристических методов решения

1.4. Формирование графа на основе заданного множества отрезков

1.5. Выводы

2. Метод колонии муравьев

2.1. Основные элементы, параметры и процедуры метаэвристики муравьиной оптимизации

2.2. Механизм обратной связи в процессе управления поведением муравья

2.3. Алгоритм поведения муравья в процессе принятия решения

2.4. Оценка вычислительной сложности алгоритма

2.5. Выводы

3. Исследование эффективности алгоритма. Влияние параметров алгоритма на качество решения

3.1. Сравнительный анализ разработанного алгоритма с другими методами

3.2. Влияние параметров алгоритма на качество решения

3.3. Исследование различных конфигураций отрезков

3.4. Исследование сходимости алгоритма

3.5. Средства повышения эффективности применения алгоритма

3.6. Выводы 96 4. Описание программного комплекса Ant colony routing.

Руководство пользователя

4.1. Описание интерфейса

4.2. Краткое руководство пользователя

4.3. Выводы 112 Заключение 113 Список использованной литературы 115 Приложение

Введение диссертации (часть автореферата) на тему «Разработка и применение бионических моделей и методов в задачах автоматизации проектирования маршрутов обхода геометрических объектов»

Настоящая диссертация посвящена проблемам построения маршрутов обхода отрезков на плоскости.

Актуальность проблемы. Прикладной аспект поставленной задачи связан с автоматизацией процесса генерации управляющих программ для станков ЧПУ тепловой резки металла, которые являются результатом сквозного цикла обработки информации от чертежа детали до программ ее изготовления в тУС-кодах конкретного оборудования [21-25]. Одним из элементов траектории режущего инструмента является переход инструмента в выключенном состоянии от одной точки врезки к другой. Для толстолистового проката затраты на сквозную пробивку металла оказываются столь значительны, что экономически целесообразным становится обработка деталей без выключения режущего инструмента.

Задача состоит в оптимизации переходов режущего инструмента от одной точки врезки к другой. Исходными данными для задачи построения рационального маршрута являются технологические карты раскроя. Конфигурацию исходного множества формируют отрезки, соединяющие точки врезки.

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

Аналогичные по формальной постановке прикладные задачи могут быть сформулированы при построении рациональных коммуникационных сетей, при решении прикладных задач размещения и обслуживания оборудования и т.п.

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

При решении поставленной задачи в основном применяются эвристические методы и комбинированные алгоритмы, так как для ее решения на количестве элементов реальных практических задач не существует точных методов, дающих результат за приемлемое время.

Для нахождения приближенного решения задачи в работе было решено использовать модифицированный алгоритм муравьиной оптимизации, обладающий устойчивостью к попаданию в точки локальных экстремумов и способностью постоянно улучшать качество решения. Муравьиная оптимизация успешно используется в различных областях [14, 30, 31, 34, 35, 61-63], в том числе и для оптимизации раскроя [1 - 3].

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

Цели и задачи работы:

- разработка математических моделей, методов и алгоритмов решения оптимизационной задачи маршрутизации;

- разработка и исследование оптимизационных алгоритмов построения гамильтонова цикла на множестве отрезков и геометрических объектов, состоящих из отрезков;

- развитие современных отечественных систем проектирования.

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

Положения, выносимые на защиту:

1) математическая модель задачи маршрутизации для обхода геометрических объектов, составленных из отрезков;

2) модификация алгоритма муравьиной оптимизации для решения задачи маршрутизации;

3) программное приложение системы AutoCAD, реализующее алгоритм муравьиной оптимизации;

4) численные эксперименты на основе созданного программного обеспечения.

Научная новизна работы. Данная работа направлена на исследование и развитие бионических принципов, моделей и методов класса муравьиной оптимизации. Основное отличие предлагаемой методики от известных вариантов алгоритмов заключается в использовании дополнительного параметра (коэффициента смежности), позволяющего управлять движением по кусочно-ломаным траекториям и замкнутым объектам. Постановка задачи поиска гамильтоновых циклов на отрезках по сравнению с аналогичными проблемами, исследуемыми зарубежными учеными [50, 59, 60, 64-69], имеет принципиальное отличие, состоящее в требовании включения в гамильтонов цикл отрезка, а не только его концов. Маршрут строится на множестве произвольно ориентированных отрезков.

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

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

- повысить коэффициент использования оборудования;

- снизить энергетические затраты на резку металла, увеличить ресурс использования режущего инструмента за счет автоматического выбора оптимального маршрута обхода заготовок;

- сократить сроки проектирования;

- повысить качество проектных решений.

Программная реализация модифицированного алгоритма муравьиной оптимизации показала значительные преимущества перед часто используемыми на практике эвристическими методами для широкого класса задач маршрутизации.

Достоверность результатов. Разработка математической модели задачи маршрутизации и создание на этой основе алгоритма стало возможным благодаря комплексному использованию теоретических и экспериментальных методов исследования. Решение ряда новых задач теории оптимизации и вычислительной геометрии, поставленных в работе в рамках диссертационного исследования, стало возможным благодаря известным достижениям указанных научных дисциплин и не противоречит их положениям, базируется на строго доказанных выводах фундаментальных и прикладных наук, таких как математический анализ, планиметрия, математическая статистика, теория оптимизации и планирование эксперимента. Созданная методика построения эффективных траекторий с использованием разработанного алгоритма согласуются с опытом их проектирования.

Разработанные новые теоретические и практические решения опробованы экспериментально. Экспериментальные исследования проводились с использованием технической базы Новосибирского государственного технического университета. Результаты экспериментов анализировались и сопоставлялись с известными экспериментальными данными других исследователей. Результаты работы, отраженные в программе автоматического проектирования маршрутов раскроя, прошли техническую экспертизу на предприятии и использованы в экспериментальном проектировании в промышленной системе «Техтран-Раскрой» как составной элемент.

Апробация работы. Основные принципы и подходы для решения рассматриваемой задачи прошли апробацию на нескольких международных, региональных конференциях, обладают научной новизной и актуальностью, могут претендовать на мировой приоритет. Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:

1) Всероссийская научная конференция молодых ученых «Наука. Технологии. Инновации», 2004 г, Новосибирск, НГТУ.

2) Международная конференция по компьютерной графике и ее приложениям Графикон, 2005,2006 гг., Новосибирск.

3) Российско - корейский международный симпозиум по науке и технологиям, KORUS 2005, Новосибирск, НГТУ.

4) Международная конференция по компьютерной графике и искусственному интеллекту, 31А'2006, 2006 г, Лимож, Франция.

5) Международная научно-техническая конференция «Высокие технологии и перспективы интеграции образования, науки и производства», 2006, Ташкент.

6) Международная конференция по вычислительной технике и информационным технологиям, CSIT'2007, 2007, Уфа.

Публикации. По теме диссертации опубликовано 11 печатных работ, в их числе 2 статьи в центральных изданиях, входящих в перечень изданий, рекомендованных ВАК РФ, 1 - в сборнике научных трудов, 8 - в трудах и материалах международных конференций.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников, включающего 74 наименования, и приложения; общий объем составляет 122 страницы основного текста, включая 76 рисунков и 11 таблиц.

Заключение диссертации по теме «Теоретические основы информатики», Ганелина, Наталья Давидовна

4.3. ВЫВОДЫ

В четвертой главе диссертации приведено описание работы с программным комплексом AntColonyRoutnig. Представлены основные этапы работы с программой: начало работы, создание и сохранение файлов, задание характеристик метода, выбор значений параметров по умолчанию, организация режима визуализации (масштабирование, прерывание работы). Процесс работы проиллюстрирован рисунками, на которых показаны рабочие окна, меню, области задания параметров, области отображения результатов, окна рисования и отображения решения.

Интерфейс созданного программного средства ориентирован прежде всего на исследование разрабатываемого алгоритма, поэтому все параметры и характеристики метода вынесены в область рабочего окна.

Результаты исследований, содержащиеся в четвертой главе, были опубликованы в [4 - 10, 42 - 43, 45 - 47].

113

Заключение

В результате проведенных в рамках подготовки диссертационной работы исследований получены следующие теоретические и практические результаты:

1. Разработана математическая модель задачи маршрутизации для обхода отрезков на плоскости, а также контуров, задаваемых отрезками.

2. Разработан алгоритм построения кратчайшего гамильтонова цикла на заданном множестве. Классический алгоритм муравьиной оптимизации модифицирован путем введения дополнительного параметра (коэффициента смежности концов отрезка).

3. Исследована эффективность алгоритма. Рассмотрен процесс получения эффективного решения в ходе итерационного поиска. Исследовано влияние параметров алгоритма на скорость и устойчивость поиска эффективного решения. Даны рекомендации по выбору значений этих параметров.

4. Выполнена оценка вычислительной сложности разработанного л алгоритма, которая составила 0(п ). Предложены способы увеличения скорости работы алгоритма путем распараллеливания процесса вычислений и возможности изменения схемы работы алгоритма разбиением его на два этапа: разбиение на подобласти и поиск локальных решений внутри областей.

5. Проведен сравнительный анализ решений при различных вариантах значений параметров и при различных схемах работы алгоритма. По сравнению с вероятностным методом ближайшего соседа предложенный алгоритм позволяет получить решения, лучшие в среднем на 20% (оценка длины маршрута обхода).

5. Разработано программное средство для работы с произвольными множествами объектов, задаваемых отрезками. Программа протестирована на достаточном количестве исходных множеств и имеет краткое руководство пользователя.

Результаты диссертационного исследования прошли техническую экспертизу и использованы в экспериментальном проектировании в промышленной системе «Техтран-Раскрой» как составной элемент.

На основе диссертационного исследования планируется подготовка и публикация статей, методик, разделов лекционных курсов, учебных пособий.

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

Список литературы диссертационного исследования кандидат технических наук Ганелина, Наталья Давидовна, 2007 год

1. Валеева А.Ф. Конструктивные методы решения задач ортогональной упаковки и раскроя: Автореферат диссертации на соискание степени доктора технических наук. Уфа: У Г АТУ, 2006.

2. Валеева А.Ф. Применение метаэвристики муравьиной колонии к задачам двухмерной упаковки // Информационные технологии. 2005. №10. -С.36-43.

3. Валеева А.Ф., Аглиуллин М.Н. Алгоритм муравьиной колонии для прямоугольной упаковки листов // Информационный бюллетень Ассоциации математического программирования. Екатеринбург: УрО РАН. - 2003. -№10.

4. Ганелина Н.Д. Построение кратчайшего пути обхода отрезков на плоскости // Сборник научных трудов НГТУ. Новосибирск: Изд-во НГТУ. -2006. - Вып. 2(44). - 188 с. - С.35 -40.

5. Ганелина Н.Д. Применение бионических методов в задаче построения замкнутого гамильтонова цикла на отрезках. Наука. Технологии. Инновации // Материалы Всероссийской научной конференции молодых ученых.- Новосибирск: Изд-во НГТУ. 2004., Ч. 1. - С. 15 - 16.

6. Ганелина Н.Д., Фроловский В.Д. Декомпозиционный метод оптимизации проектирования управляющих программ тепловой резки металла на оборудовании с ЧПУ // Научный Вестник НГТУ. Новосибирск: Изд-во НГТУ. - 2006 - №2 (23). - С. 9 -19.

7. Ганелина Н.Д., Фроловский В.Д. Исследование методов построения кратчайшего пути обхода отрезков на плоскости // Сибирский журнал вычислительной математики. Новосибирск, 2006, №3, т. 9. - С. 201 -212.

8. Дегтярев Ю.И. Методы оптимизации. М.: Сов. радио, 1980. - 320 с.

9. Лбов Г.С. Выбор эффективной системы зависимых признаков // Сборник трудов Института математики СО АН СССР. 1965. Выпуск 19 - С.21-34.

10. Лореш М.А. Разработка и исследование алгоритмов муравьиной колонии для задач оптимального размещения предприятий: Автореферат диссертации на соискание степени кандидата технических наук. Омск:ОмГУ, -2006.

11. Мухачева Э.А., Верохотуров М.А., Мартынов В.В. Модели и методы раскроя упаковки геометрических объектов. - Уфа: УГАТУ, - 1998. - 217 с.

12. Пушкарева Г.В. Разработка и применение гибридного генетического алгоритма для автоматизации проектирования маршрутов обхода геометрических объектов: Диссертация на соискание ученой степени кандидата технических наук. 2004. - Новосибирск, НГТУ.

13. Растригин Л.А. Адаптация сложных систем. Методы и приложения. Рига: Зинатне. - 1981.-394 с.

14. Сигал И.Х. Приближённые методы и алгоритмы в дискретной оптимизации: Учебное пособие. М.: МИИТ. - 2000. - 107 с.

15. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: Учеб. пособие Новосибирск. - 1997 - 270 с.

16. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. -М.: Наука, Главная редакция физико-математической литературы-1986-354 с.

17. Фроловский В.Д. Моделирование и алгоритмизация процессов геометрического проектирования изделий из листового материала: Диссертация на соискание ученой степени доктора технических наук Новосибирск. -2001.-340с.

18. Фроловский В.Д., Эстрайх И.В. Об одной задаче оптимизации движения режущего инструмента при раскрое листового проката // Машинные методы оптимизации, моделирования и планирования эксперимента. Новосибирск: НЭТИ, 1988. - С. 60-65.

19. Фроловский В.Д., Эстрайх И.В., Петров С.В. Автоматизация проектирования процессов тепловой резки металла на оборудовании с ЧПУ // Автоматизация проектирования и производства в электромашиностроении.-М. -1989.-С. 86-93.

20. Эвристические алгоритмы оптимизации / Сборник статей. Ярославль, 1975.-217 с.

21. Alt Н., Welzl Е. Visibility graphs and obstacle-avoiding shortest paths // Z. Oper. Res. 1988. -32:145 - 164.

22. Asano Т., Ghosh S.K., Shermer T.C. Visibility in the plane // Handbook of • Computational Geometry. 2000. - P.829-876.

23. Avis D., Rappaport D. Computing monotone simple circuits in the plane // Computational Morphology. 1988. - P. 13-23.

24. Colorni A., Dorigo M., Maniezzo V. Distributed Optimization by Ant Colonies// Proc. of European Conference on Artificial Life (ECAL91). -Paris, France, 1991. P. 134-142.

25. Cordon 0, Herrera F, Stiitzle T. A Review on the Ant Colony Optimization Metaheuristic: Basis, Models and New Trends // Mathware and Soft Computing.-2002. 9(2-3): 141—175.

26. Demaine E.D, O'Rourke J. Open problems from CCCG'99 // Proc. of the 11th Canadian Conf. on Computational Geometry. Vancouver, ВС, 1999. -P.269 -272.

27. Di Caro G., Dorigo M. AntNet: Distributed Stigmergetic Control for Communications Networks // Journal of Artificial Intelligence Research. 1998. -9:317-365.

28. Dorigo M., Birattari M., Stiitzle T. Ant Colony Optimization- Artificial Ants as a Computational Intelligence Technique // IEEE Computational Intelligence Magazine. 2006.

29. Dorigo M., Caro G., Gambardella L. Ant Algorithms for Discrete Optimization //Artificial Life. 1999. - 5(2):137-172. 1999.

30. Dorigo M., Gambardella L. Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem // IEEE Transactions on Evolutionary Computation. -1997. l(l):53-66.

31. Dorigo M., Maniezzo V., Colorni. A. Ant System: An Autocatalytic Optimizing Process // Report No. TR-91-016. Milan: Politecnico di Milano, 1997.

32. Dorigo M., Maniezzo V., Colorni A. The Ant System: Optimization by a colony of cooperating agents. // IEEE Transactions on Systems, Man and Cybernetics. 1996. - Part B, Vol. 26.-1:1-13.

33. Dorigo M., Socha S., T.F. Gonzalez. An Introduction to Ant Colony Optimization // Approximation Algorithms and Metaheuristics. CRC Press. - 2007.

34. Dorigo M., Stiitzle T. The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances: Handbook of Metaheuristics. CRC Press. -2002.41. ' Everett H., Hoang C.T., Kilakos K. Noy M. Planar segment visibility graphs//

35. Computational Geometry. 2000. - 16:235-243.

36. Ganelina N., Frolovsky V. Ant Colony Approach to Defining Hamilton Cyclethon Segments // Proc. of the 9 Russian-Korean International Symposium on

37. Science and Technology (KORUS 2005). -2005. Vol. 1:601 - 603. Применение метода колонии муравьев для поиска гамильтонова цикла на отрезках.

38. Gambardella L., Dorigo М. Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem // Proc. of ML-95, Twelfth International Conference on Machine Learning. Tahoe City, С A. - Morgan Kaufmann. -1995: 252-260.

39. Garey M.R., Johnson D.S., Tarjan R.E. The planar Hamiltonian circuit problem is NP-complete // SIAM J. Comput. 1976. -5:704-714.

40. Grunbaum B. Hamiltonian polygons and polyhedra. // Geombinatorics 1994.3:83 - 89.

41. Gutjahr W. A generalized convergence result for the graph-based ant system metaheuristic // Probability in the Engineering and Informational Sciences. -2003. -P.545 569.

42. Gutjahr W. A graph-based Ant System and its convergence // Future Generation Computer Systems. 2000. - V. 16: 873-888.

43. Gutjahr W. ACO algorithms with guaranteed convergence to the optimal solution// Information Processing Letters. 2002. - V. 82(3): 145-153.

44. Gutjahr W., Albrecht A., Steinhoefl K. Converging ACO algorithm for stochastic combinatorial optimization // Proc. SAGA 2003 (Stochastic Algorithms: Foundations and Applications), Hatfield (UK). -2003. -P. 10 25.

45. Gutjahr W, Doerner K., Hard R.F. Pareto Ant Colony Optimization with IP preprocessing in multiobjective project portfolio selection // European Journal of Operational Research. -2006. P. 830-841.

46. Gutjahr W., Rauner M. An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria//Computer and Operations Research-2007.-3:642-666.

47. Hoffmann M., Toth C.D., Segment endpoint visibility graphs are Hamiltonian// Computational Geometry: Theory and Applications. 2003.-Vol.26. - 1:47-68

48. Kaelbling, L. P., Littman, M. L., Moore, A. W. Reinforcement learning: A survey // Journal of Artificial Intelligence Research. 1996. - №4: 237-285

49. Leipala Т., Nevalainen O. A plotter sequencing system // The Computer Journal. 1979; 22:313-316.

50. Mirzaian A. Hamiltonian triangulations and circumscribing polygons of disjoint line segments // Computational Geometry Theory and Applications. -1992.- 1:15-30.

51. Schoonderwoerd R., Holland O., Bruten J., Rothkrantz, L. Ant-based load balancing in telecommunications networks: Adaptive Behavior. -1996. №5(2): 169-207.

52. Schoonderwoerd R., Holland O., Bruten J. Ant-like agents for load balancing in telecommunications networks // Proc. of the First International Conference on Autonomous Agents. ACM Press. - 1997. - P. 209-216.

53. Subramanian, D., Druschel, P., & Chen, J. Ants and reinforcement learning: A case study in routing in dynamic networks // Proc. of the International Joint Conference on Artificial Intelligence (IJCAI-97). Morgan Kaufmann. - 1997.-P. 832-838.

54. O'Rourke J., Rippel J. Segment visibility graphs: several results // Proc. of the 4th Canad. Conf. Comput. Geom. 1992. - P. 35 - 38.

55. O'Rourke J., Rippel J. Two Segment Classes with Hamiltonian Visibility Graphs // Computational Geometry: Theory and Applications. 1994. - 1:209218.

56. Rappaport D. Computing simple circuits from a set of line segments is NP-complete // SIAM Journal on Computing. -1989. Vol.18. - 6:1128-1139,

57. Rappaport D. Minimum polygon transversals of line segments // Computational Geometry: Theory and Applications. -1995. 5:243-256.

58. Rappaport D. The visibility graph of congruent discs is Hamiltonian // Computational Geometry: Theory and Applications. 2003.- 25:257-265.

59. Rappaport D, Imai H., Toussaint G. Computing simple circuits from a set of line segments // Discrete Computational Geometry. -1990. 5(3):289-304.

60. Stutzle Т., Hoos H. MAX-MIN Ant System // Future Generation Computer Systems. 2003. - 16(8):889-914.

61. SttitzleT., Dorigo M. A Short Convergence Proof for a Class of AC О Algorithms // IEEE Transactions on Evolutionary Computatio.-2002. -Vol. 6(4):358-365.

62. Toth C.D., Hoffmann M. Alternating paths through disjoint line segments Information Processing Letters. 2003. -Vol. 87. - 6: 287 - 294

63. Toth C.D., Hoffmann M. Spanning Trees across Axis-Parallel Segments // Proc. of the 18th Canadian Conference on Computational Geometry (CCCG '06), Kingston(ON), Canada. -2006. -P. 101-104.

64. Urabe M. Watanabe M. On a counterexample to a conjecture of Mirzaian // Computational Geometry: Theory and Applications. -1992. Vol.2. - 1: 51-53.1. Акты внедрения