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

На правах рукописи

Ганелина Наталья Давидовна

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

Специальность 05 13 17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

ООЗ1В14Ь4

Новосибирск - 2007

003161494

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Новосибирский государственный технический университет»

Научный руководитель Официальные оппоненты

Ведущая организация

доктор технических наук, профессор Фроловский Владимир Дмитриевич

доктор технических наук, профессор Лбов Геннадий Сергеевич, кандидат технических наук, доцент Постовалов Сергей Николаевич

Сибирский государственный университет телекоммуникаций и информатики, г Новосибирск

Защита состоится 14 ноября 2007 г в 16 00 на заседании диссертационного совета Д212 173 06 в Новосибирском государственном техническом университете по адресу 630092, г Новосибирск, пр К Маркса, 20

С диссертацией можно ознакомиться в библиотеке Новосибирского государственного технического университета

Автореферат разослан « октября 2007 г

Ученый секретарь

диссертационного совета МЛ,.- Чубич В М

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Задачи исследования

1 Разработка математической модели представления множества отрезков

2 Разработка алгоритма построения маршрута обхода отрезков на плоскости

3 Разработка алгоритма построения кратчайшего гамильтонова цикла на множестве произвольно ориентированных отрезков

4 Исследование эффективности различных модификаций алгоритма на множестве отрезков Оценка вычислительной сложности алгоритма

5 Разработка программного обеспечения на базе предложенной модели Анализ эффективности разработанных алгоритмов на основе результатов численных экспериментов

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

Моделирование и вычислительные эксперименты проводились с использованием программного обеспечения, реализованного на С++.

Научная новизна

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

2 Разработан метод, основанный на классическом методе муравьиной оптимизации, который модифицирован путем введения дополнительного

параметра в структуру алгоритма принятия решения - коэффициента смежности

Достоверность результатов

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

Практическая значимость работы

Разработанные методы и алгоритмы и созданное на их основе программное обеспечение могут быть использованы

- для построения маршрутов движения режущего инструмента станков ЧПУ тепловой резки металла,

- для построения маршрутов обхода фигур на плоскости, заданных отрезками

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

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

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

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

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

Апробация работы

Основные результаты диссертации докладывались на

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

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

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

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

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

6 Конференции - конкурсе работ студентов, аспирантов и молодых ученых* «Технологии Microsoft в теории и практике программирования» (Новосибирск, Академгородок, 2007)

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

Публикации

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

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

В первой главе приводится обзор основных подходов к задаче построения цепей и циклов на отрезках

Большинство исследований направлены на построение маршрутов обхода отрезков на основе графа видимости концов отрезков {segment endpoint visibility graph) либо на выделении отдельных подмножеств отрезков (например, множества независимых и цело-координатных отрезков) и разработке для них итерационных процедур Такая постановка задачи значительно сужает область применения разработанных методов

Граф видимости концов отрезков представлен на рис 1, множества независимых и цело-координатных отрезков - на рис 2 и рис 3 соответственно На рис 1 показаны отрезки исходного множества, пунктиром выделены аугментальные дуги Концы отрезков «видят» друг друга, если прямая, соединяющая их, не пересекает ни один из отрезков исходного множества

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

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

Рис 1 Граф видимости концов отрезков

Рис 2 Набор независимых отрезков

I

I

I I — I

Рис 3 Множество цело-координатных отрезков

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

Также в первой главе приведена характеристика эвристических методов, ориентированных на решение поставленной задачи, для которой доказана ее ЛУ-полнота На основе представления исходного множества отрезков в виде полносвязного неориентированного взвешенного графа и желаемых характеристик процедур поиска результирующего маршрута в качестве методологии решения была выбрана муравьиная оптимизация

Множество отрезков для решения задачи представлено графом, вершины которого суть концы отрезков, ребра - отрезки и всевозможные переходы между ними Ребра, соответствующие переходам между отрезками, имеют два веса константную величину, характеризующую расстояние между точками концов отрезков, и переменную величину, изменяющую свое значение в ходе работы алгоритма (рис 4) Отрезок, составляющий ломаную или часть замкнутой фигуры, помечен весом, отражающим необходимость сквозного прохождения по отрезку (коэффициент смежности) (рис 6)

Возможна ситуация (вырожденный случай), когда исходное множество содержит точки (рис 5) Отрезки также можно «сжать» в точки, то есть идентифицировать отрезок точкой, лежащей на нем (Идентифицирующей точкой может служить любая точка на отрезке ) Это приведет к сокращению области поиска, однако и конечный результат может содержать значительную

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

о

Ри

5,

о р,

рп

Р)

О^т.-

I чч.

Рис 4 Представление множества отрезков графом

А

О

Рис 5 Представление множества точек

Х>'

Рн

Рис 6 Веса ребер графа

Целевая функция в общем случае представляет собой сумму длин отрезков и переходов между ними

п-1

п-1

Л

2/,+ I Ц,

^г=0 г,./=0 ^

ЛХ) = ПШ1

где г — отрезок , « = 0, 1, , п - 1, - длина отрезка X,

»> г/

(г, 7 = 0, 1, , я - 1) - расстояние между отрезками ^ и , Ь^ еК,

К- множество допустимых перемещений (маршрутов)

Во второй главе рассмотрены основные элементы, процедуры и свойства алгоритма колонии муравьев

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

Элементами эвристики колонии муравьев являются простые агенты, наделенные определенными свойствами, некоторая информация о локальном положении (численная характеристика перехода между звеньями маршрута, призванная охарактеризовать полезность звена для построения конечного решения), механизм принятия решения — выбора последующего звена Простые агенты - муравьи наделены памятью, способностью оценивать локальную информацию Существуют они, очевидно, в дискретном времени

Информация о местоположении муравья и характеристиках соседних объектов представлена двумя параметрами феромоном и расстоянием Оба параметра описывают переход между парой точек, текущей, в которой находится муравей, и одной из множества допустимых При моделировании природного феромона (вещества, оставляемого каждым муравьем на пути следования, чем больше феромона на пути, тем больше муравьев выберут этот путь -эффект обратной связи) в нашей модели вводится коэффициент -положительное число, для вычисления величины которой учитывается длина наименьшего пути, найденного со времени начала поиска, а также коэффициенты обновления (испарения и добавления) феромона, что позволяет управлять выбором пути и механизмом обратной связи

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

преобразование последовательности переходов в решение задачи поиска маршрута Возможно также добавление методов локального улучшения решения Так, автор первоначального метода М Дориго использовал метод ротаций Лина-Кернигана В разработанном нами методе присутствуют алгоритмы обнаружения и устранения самопересечений пути

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

Процесс принятия решения в общем случае представлен формулой (1) Вероятность перемещения к — то муравья из точки г в точку у на /-ом шаге определяется

УФК]

у е аИсмей

к'

I т£.а11оу>ес1^

(1)

и

в противном случае

V18,= <

где )

\г!тУ,тФ1 +1

и

allowed^ - список отрезков, еще не пройденных к-ъш муравьем, pt - точка -

конец отрезка г, t]tJ - видимость пути (функция, обратно пропорциональная

расстоянию между двумя точками), rtJ (t) - величина феромона на дуге (i,j), af -

adjacent force - коэффициент смежности, а и /? - параметры, контролирующие относительный приоритет феромона г на пути и видимости следующего отрезка (важность феромона и коэффициент видимости пути соответственно)

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

где д - случайное число на отрезке [0, 1], д0 - параметр баланса между использованием накопленных знаний и исследованием новых решений (О < до 1 1), г - случайный отрезок, выбранный на основе вероятностей, посчитанных по формуле вероятности выбора (1)

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

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

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

5 = < j sallowed^

г, в противном случае

шах

{

}

(2)

Реализация метода ближайшего соседа в рамках разрабатываемого алгоритма стала возможна благодаря его бикритериальности (введение параметра оценки пути с помощью феромона). Алгоритм может работать в следующих режимах (табл 1) Управлять работой алгоритма можно с помощью параметров коэффициента привлекательности пути а, коэффициента видимости пути /?, уровня использования знаний до, а также коэффициентов обновления феромона

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

Рекомендуемые значения коэффициента смежности, как и остальных параметров, определялись в ходе эксперимента Благодаря нормализации значений видимости пути и важности феромона коэффициент смежности изменяется в интервале [0, 1] Теоретически значение коэффициента смежности можно увеличивать, однако на качество решения данная процедура не имеет значительного влияния Как один из вариантов определения коэффициента смежности использовался полный запрет перехода от контура к близлежащему отрезку

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

Ниже на рис 7 представлен результат работы алгоритма на простейшей карте раскроя и на произвольном множестве отрезков (рис 8) Тонкими линиями показаны переходы между отрезками

В табл 2 представлены численные характеристики найденных решений

Варианты работы алгоритма

а fi 4о Вид формулы выбора отрезка Схема работы метода

0 0 0 к J —, j, т е allowedь PlJ W"i(|| [ 0, в прот случае Равновероятный выбор, полный перебор

0 0 1 s = l, j е allowed^ Равновероятный выбор

0 1 0 Ь J ---р-/ е allowed и „2 . [l,m\ К те allowed ^ 0,в противном случае Вероятностный принцип жадности

0 1 1 max i ) jeallowed^ Метод ближайшего соседа

1 0 0 МО] „ , теа^мес!, к 0, в противном случае Вероятностный метод обратной связи

1 0 1 s= max { |f 0)J " } j sallowed ^ Метод обратной связи

1 1 0 [ ШвЫ' г . Вероятностный метод колонии муравьев без подкрепления

теаистеа^ 0, в противном случае

1 1 1 [ г, в противном случае Метод колонии муравьев без возможности вероятностного поиска

а)

б)

Рис 7 Сравнительный анализ решений

В таблице использованы обозначения- а/"- коэффициент смежности, АС -метод колонии муравьев, ОН — принцип жадности, ЯБ - стратегия случайного поиска, 1 - длина найденного маршрута (тт) за время Г (тя) и за количество итераций п, число пересечений в результирующим маршруте - Мт(

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

и

1С

/ г

Хк

Л

/

Рис 8 Гамильтонов цикл на произвольном множестве отрезков (тонкими линиями показаны переходы между отрезками)

Пример работы алгоритма

Рис I Решение Процесс решения

й / Г п Ягы пД п/1 пД п/1 пД

а АС 0,1 4 337 3 31 1 1/ 4 711 6/ 4 480 12/ 4 607 23/ 4 336 29/ 4 574

6 АС 1 4319 2 19 1 1/ 4 572 12/ 4 503 15/ 4 349 16/ 4 345 17/ 4 338

в гаи 0,1 6 326 30 315 20 1/ 7 961 30/ 6 951 118/ 6 408 174/ 6 915 304/ 6 484

г вн 1 5 271 8 90 14 1/ 5 835 13/ 6 068 20/ 5 694 - -

- 0,1 И 611 99 921 1037 190 1/ 13 669 7/ 13 054 14/ 13 058 247/ 12 780 1037/ 11 611

- 1 И 570 285 097 2 876 181 1/ 13 958 12/ 12 457 1 155/ 12 218 2440/ 12 651 2 876/ 11 570

а)

б)

Рис 9 Маршрут движения режущего инструмента (метод колонии муравьев) а) - карта раскроя, б) - фрагмент карты раскроя, холостой ход режущего инструмента Длина холостого хода - 19 703 мм

Четвертая глава диссертации посвящена описанию работы пользователя с программным комплексом Ant Colony Routing Для реализации предлагаемых алгоритмов было создано программное средство, разработанное с помощью С++ Builder 6 0 под Windows В основу положена идеология объектно-ориентированного программирования

Входной информацией является набор отрезков, заданных координатами концов Исходное множество отрезков можно нарисовать или получить из карты раскроя, представленной рисунком в системе AutoCAD Результаты построения маршрута могут отображаться в окне программы Как на каждом этапе получения лучшего решения, представляя динамику процесса, так и по окончании выполнения задачи в целях экономии вычислительных ресурсов Пользователь имеет возможность изменять значения всех параметров алгоритма, воспользовавшись списком рекомендованных значений, приведенных в главе 2 диссертации, по умолчанию параметрам присваиваются значения, полученные в ходе исследования свойств алгоритма Помимо визуализации предусмотрена возможность сохранения результатов в виде файла, данные из которого могут быть в дальнейшем переданы в AutoCAD для более детального просмотра

Основные результаты работы

1 Разработана модель представления множества отрезков на плоскости

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

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

4 Выполнена оценка вычислительной сложности алгоритма, которая составила 0(п3), где п - размерность задачи, то есть число отрезков

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

Основные научные и практические результаты диссертации опубликованы в следующих работах

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

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

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

4 Ганелина Н Д Исследование метаэвристических методов решения задач маршрутизации на плоскости / Ганелина Н Д , Дегтярева А И // Труды 16-ой Международной конференции по компьютерной графике и ее приложениям «Графикон 2006» - Новосибирск Институт ВМ и МГ СО РАН — 2006 - С 303-307

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

6 Ганелина НД Решение задачи поиска гамильтонова цикла на отрезках методом муравьиных колоний / Ганелина Н Д, Фроловский В Д // Труды 15 Международной конференции по компьютерной графике и ее приложениям «Графикон, 2005» - Новосибирск Институт ВМ и МГ СО РАН -2005 - С 207-210

7 Ganelma N Constructing the shortest closed tour on a set of line segments using ant colony approach / Ganelma N, Frolovsky V // Proceedings of the 9th International Conference m Computer Graphics and Artificial Intelligence 3IA'2006- Limoges (France) - 2006, P 197 - 202 [Построение кратчайших замкнутых циклов на множестве отрезков с помощью алгоритма колонии муравьев]

8, Ganelma N Ant Colony Approach to Defining Hamiltoman Cycle on Segments / Ganelma N, Frolovsky V H Proceedings of the 9th Russian-Korean International Symposium on Science and Technology (KORUS 2005) -2005 -Vol 1 601 - 603 [Применение метода колонии муравьев для поиска гамильтонова цикла на отрезках]

9 Ganelma N D Ant colony1 approach m tube-passmg problem 11 Труды международной научно-технической конференции «Высокие технологии и перспективы интеграции образования, науки и производства» - Ташкент -2006 - т 1 - С 90 - 94 [Применение метода муравьиных колоний для решения трубопроводной задачи]

10 Ganelma N Constructing the shortest Hamiltoman circuits and cycles on a set of lme undirected segments // Труды 16-ой Международной конференции по компьютерной графике и ее приложениям «Графикон 2006» - Новосибирск, Институт ВМ и МГ СО РАН - 2006 - С 27-31 [Построение кратчайших гамильтоновых цепей и циклов на множестве отрезков]

11 Ganelma N D Constructing tours on a set of plane geometric objects / Ganelma N, Frolovsky V // Proceedings of the 9th International Workshop on Computer Science and Infonnation Technologies CSIT'2007 - Ufa-Kracnousolsk (Russia)-2007-Vol 2 216-221 [Формирование маршрутов обхода геометрических объектов на плоскости]

Отпечатано в типографии Новосибирского государственного технического университета 630092, г Новосибирск, пр К Маркса, 20 Тел /факс (383) 346-08-56 Формат 60 х 84 1/16 Объем 1,5 п л Тираж 100 экз Заказ № /3 // Подписано в печать 09 10 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. Разработано программное средство для работы с произвольными множествами объектов, задаваемых отрезками. Программа протестирована на достаточном количестве исходных множеств и имеет краткое руководство пользователя.

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

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

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

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. Акты внедрения