Введение к работе
А&^ґЇ-'у*
Актуальность проблемы. Содержательная сторона рассматриваемой задачи связана с решением проблемы автоматизации сложного и трудоемкого процесса генерации управляющих программ для станков ЧПУ тепловой резки металла. Известные программные комплексы автоматизированного проектирования управляющих программ в значительной мере используют элементы интерактивной графики, в то время как более перспективным представляется полная автоматизация проектных решений на основе математических моделей и оптимизационных методов.
Траектория движения режущего инструмента состоит из следующих элементов: 1) внешних контуров вырезаемых деталей; 2) внутренних контуров; 3) траекторий, связывающих смежные контуры (вырезаемые с одной врезки); 4) траекторий переходов инструмента в выключенном состоянии от одной точки врезки к другой.
При резке тонколистового металла маршруты типа 3, как правило, отсутствуют, поскольку каждая деталь вырезается в этом случае с отдельной врезки. Для толстолистового проката затраты на сквозную пробивку металла оказываются столь значительны, что экономически целесообразным становится обработка деталей без выключения режущего инструмента.
Таким образом, задача состоит в минимизации траекторий холостого хода, числа врезок и оптимизации переходов от одной врезки к другой. Исходными данными для задачи построения рационального маршрута являются технологические карты раскроя. Конфигурацию плана раскроя образуют внутренние и внешние контуры вырезаемых деталей. Особенность и сложность задачи заключается в том, что она имеет дискретно-непрерывную структуру. При решении данной задачи возникает ряд различных технологических ограничений, связанных со спецификой исполнительного инструмента.
В терминах теории графов любой допустимый маршрут, который может быть спроектирован с помощью разработанного комплекса алгоритмов и программ, является гамильтоновым циклом на множестве пунктов обхода плана. Поиск оптимального гамильтонова цикла является NP-сложной задачей дискретной оптимизации. Сформулированная задача соответствует открытой задаче коммивояжера с неизвестной матрицей расстояний.
Для таких трудных с вычислительной точки зрения проблем, один из подходов состоит в том, чтобы ослабить требование глобальной оптимальности результата, заменив исчерпывающий поиск приближенным, что приводит к более эффективным алгоритмам. При этом в большинстве случаев ожидается более чем умеренный проигрыш в качестве полученного результата.
Для нахождения приближённого решения задачи было решено разработать гибридный генетический алгоритм, обладающий устойчивостью к попаданию в точки локальных экстремумов и способностью постоянно увеличивать качество популяции от поколения к поколению. Генетические алгоритмы (ГА) успешно используются при проектировании СБИС в задачах размещения,
при решении комбинаторно-логических задач, задач канальной трассировки, задачи распределения инвестиций и других экономических задач.
Способ решения рассматриваемой задачи основан на интеграции технологий искусственного интеллекта и вычислительно-поисковых процедур. Реализация комплекса алгоритмов и программ представляет собой приложение системы AutoCAD.
Цели и задачи работы:
разработка математических моделей, методов и алгоритмов решения оптимизационной задачи маршрутизации дискретно-непрерывной структуры с системой технологических и геометрических ограничений;
разработка и исследование оптимизационных алгоритмов построения Га-мильтонова цикла на множестве замкнутых геометрических объектов;
развитие современных отечественных систем сквозного проектирования.
Методы исследования. При исследовании и решении поставленной в рамках диссертационной работы задачи используются методы геометрического моделирования и проектирования, комбинаторные метаэвристические методы оптимизации, методы математического программирования, математические модели и методы параметризации, аппроксимации функций, методы вычислительной геометрии и компьютерной графики.
На защиту выносятся:
-
математическая модель задачи маршрутизации для обхода геометрических объектов с внутренними контурами, включая критерий оптимальности, геометрические и технологические ограничения;
-
специализация гибридного генетического алгоритма для решения задачи маршрутизации:
способ кодирования решения для задачи маршрутизации (структура хромосомы);
оригинальная архитектура поиска эффективного решения задачи;
модификация генетических операторов для решения задачи маршрутизации;
алгоритм локальной оптимизации, основанный на методе циклического координатного спуска;
-
программное приложение системы AutoCAD, реализующее гибридный генетический алгоритм;
-
вычислительный эксперимент на основе созданного программного обеспечения.
Научная новизна работы. Научная новизна предлагаемых решений определяется тем, что впервые проведено системное исследование по направлению интеллектуализации в САПР и предложены конструктивные методы решения задачи построения Гамильтонова контура на множестве геометрических объектов, включая объекты с внутренними контурами. Результаты диссертационного исследования:
1) математическая модель задачи маршрутизации для обхода геометрических объектов с внутренними контурами, включая
критерии оптимальности, учитывающий дискретно-непрерывную структуру рассматриваемой задачи,
геометрические ограничения, описанные аналитически в виде совокупности параметрических уравнений,
ряд технологических ограничений, учтённых при алгоритмизации и разработке программного комплекса;
2) гибридный генетический алгоритм со своей специализацией, в состав кото
рой входят:
метод кодирования хромосом, учитывающий специфику задачи маршрутизации,
оригинальная архитектура поиска эффективного решения задачи посредством гибридизации методологии генетического программирования с традиционными вычислительно-поисковыми процедурами,
модифицированные генетические операторы, которые специализированы для решения задач построения маршрутов и исключают возникновение решений, не отвечающих условию задачи;
3) результаты исследования влияния параметров разработанного гибридного
генетического алгоритма на эффективность поиска решения.
Полученные результаты дают основания полагать, что эффективное решение NP-сложных задач оптимизации дискретно-непрерывной структуры является возможным посредством интеграции технологий искусственного интеллекта с вычислительно-поисковыми процедурами.
Практическая значимость работы.
Полученные результаты диссертационного исследования позволяют предложить эффективные алгоритмы, основанные на бионических принципах, для решения широкого класса задач дискретно-непрерывной структуры. Использование этих алгоритмов при решении проблемы автоматизации подготовки управляющих программ для станков тепловой резки металла с ЧПУ позволяет:
- повысить коэффициент использования оборудования в среднем на 5-
10%;
снизить энергетические затраты на резку металла;
увеличить ресурс использования режущего инструмента за счет автоматического выбора оптимального маршрута и режимов резки металла;
сократить в несколько раз сроки проектирования;
улучшить качество проектных решений.
Программная реализация гибридного генетического алгоритма показала значительные преимущества перед классическим ГА (без целенаправленного изменения хромосом) и используемыми на практике эвристическими методами для широкого класса задач маршрутизации. Предложенный гибридный генетический алгоритм по длине пути даёт результаты в среднем на 20% лучше классического ГА (с аналогичными параметрами), на 30% лучше алгоритма
«ближайшего соседа», на 10% лучше алгоритма «самого дешёвого включения».
Достоверность результатов. Разработка математической модели задачи маршрутизации и создание на этой основе гибридного генетического алгоритма стало возможным благодаря комплексному использованию теоретических и экспериментальных методов исследования. Решение ряда новых задач теории оптимизации и вычислительной геометрии, поставленных в работе в рамках диссертации, стало возможным благодаря известным достижениям указанных научных дисциплин и не противоречит их положениям, базируется на строго доказанных выводах фундаментальных и прикладных наук, таких как математический анализ, тригонометрия и планиметрия, математическая статистика, теория оптимизации и планирование эксперимента. Созданная методика построения эффективных траекторий с использованием гибридного генетического алгоритма согласуются с опытом их проектирования.
Разработанные новые теоретические и практические решения опробованы экспериментально. Экспериментальные исследования проводились с использованием технической базы Новосибирского государственного технического университета Результаты экспериментов анализировались и сопоставлялись с известными экспериментальными данными других исследователей.
Апробация работы. Основные принципы и подходы для решения рассматриваемой задачи прошли апробацию на нескольких международных, всероссийских и региональных конференциях, обладают научной новизной и актуальностью, могут претендовать на мировой приоритет. Результаты работы и отдельные её разделы докладывались и обсуждались на следующих конференциях и семинарах:
-
Региональная научно-практическая конференция «Вузы Сибири и Дальнего Востока — Транссибу», 27-29 ноября 2002 г., Сибирский государственный университет путей сообщения, Новосибирск, Россия;
-
Региональная научная конференция студентов, аспирантов и молодых учёных «Наука. Техника. Инновации», 5-8 декабря 2002 г., Новосибирский государственный технический университет, Новосибирск, Россия;
-
7-ая Всероссийская научно-техническая конференция «Информационные технологии в науке, проектировании и производстве», декабрь 2002 г., МВВО АТН РФ, Н. Новгород, Россия;
-
8-ая Всероссийская научно-техническая конференция «Информационные технологии в науке, проектировании и производстве», 18 апреля 2003 г., МВВО АТН РФ, Н. Новгород, Россия;
-
Международная научно-техническая конференция «Информационные системы и технологии», 22-25 апреля 2003 г., Новосибирский государственный технический университет, Новосибирск, Россия;
-
6th International Conference in Computer Graphics and Artificial Intelligence (3IA*2003), 14-15 of May, 2003, Limoges, France;
-
1-ая Всероссийская научно-практическая конференция «Опыт практического применения языков и программных систем имитационного моделирования
в промышленности и прикладных разработках», 23-24 октября 2003 г., ФГУП ЦНИИ технологии судостроения, Санкт-Петербург, Россия;
-
Научно-практическая конференция «Дни науки в НГТУ», 7 марта 2004 г., Новосибирский государственный технический университет, Новосибирск, Россия;
-
8th Korea-Russia International Symposium on Science and Technology (KORUS 2004), June 26 — July 3,2004, at Tomsk Polytechnic University, Russia.
Работа выполнена при поддержке гранта МО РФ (тема — Т02-10.4-3668).
Публикации. По теме диссертации опубликовано 9 работ объёмом 50 страниц (2,5 печатных листа).
Структура и объем работы. Диссертация состоит из введения, четырёх глав, заключения и приложения. Общий объем работы составляет 168 страниц машинописного текста. Основная часть диссертации состоит из 139 страниц, включая 48 рисунков и И таблиц, библиографию, содержащую 106 названий; имеется также приложение на 29 страницах.
