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

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

Пушкарёва Галина Витальевна

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

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

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

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

Научный руководитель: доктор технических наук, доцент

Фроловский Владимир Дмитриевич

Официальные оппоненты: доктор технических наук, профессор

Лбов Геннадий Сергеевич

кандидат технических наук, доцент Гаврилов Андрей Владимирович

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

и математической геофизики СО РАН, г. Новосибирск

Защита состоится « 1 » декабря 2004 года в 14 часов на заседании диссертационного совета Д 212.173.06 при Новосибирском государственном техническом университете (630092, Новосибирск, пр. К. Маркса, 20)

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

Автореферат разослан 2004 года

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

диссертационного совета Д 212.173.06

к.т.н., доцент__/В.М. Чубич/

Общая характеристика работы

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

Траектория движения режущего инструмента состоит из следующих элементов: 1) внешних контуров вырезаемых деталей; 2) внутренних контуров; 3) траекторий, связывающих смежные контуры (вырезаемые с одной врезки); 4) траекторий переходов инструмента в выключенном состоянии от одной точки врезки к другой.

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

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

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

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

Для нахождения приближённого решения задачи было решено разработать гибридный генетический алгоритм, обладающий устойчивостью к попаданию в точки локальных экстремумов и способностью постоянно увеличивать качество популяции от поколения к поколению. Генетические алгоритмы (ГА) успешно используются при проектировании СБИС в задачах размещения,

3 | БИбл„огтНЛЙ]

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

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

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

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

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

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

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

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

2) специализация гибридного генетического алгоритма для решения задачи маршрутизации:

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

- оригинальная архитектура поиска эффективного решения задачи;

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

- алгоритм локальной оптимизации, основанный на методе циклического координатного спуска;

3) программное приложение системы AutoCAD, реализующее гибридный генетический алгоритм;

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

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

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

- критерий оптимальности, учитывающий дискретно-непрерывную структуру рассматриваемой задачи,

- геометрические ограничения, описанные аналитически в виде совокупности параметрических уравнений,

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

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

- метод кодирования хромосом, учитывающий специфику задачи маршрутизации,

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

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

3) результаты исследования влияния параметров разработанного гибридного генетического алгоритма на эффективность поиска решения.

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

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

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

- снизить энергетические затраты на резку металла;

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

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

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

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

«ближайшего соседа», на 10% лучше алгоритма «самого дешёвого включения».

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

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

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

1) Региональная научно-практическая конференция «Вузы Сибири и Дальнего Востока — Транссибу», 27-29 ноября 2002 г., Сибирский государственный университет путей сообщения, Новосибирск, Россия;

2) Региональная научная конференция студентов, аспирантов и молодых учёных «Наука. Техника. Инновации», 5-8 декабря 2002 г., Новосибирский государственный технический университет, Новосибирск, Россия;

3) 7-ая Всероссийская научно-техническая конференция «Информационные технологии в науке, проектировании и производстве», декабрь 2002 г., МВВО АТН РФ, Н. Новгород, Россия;

4) 8-ая Всероссийская научно-техническая конференция «Информационные технологии в науке, проектировании и производстве», 18 апреля 2003 г., МВВО АТН РФ, Н. Новгород, Россия;

5) Международная научно-техническая конференция «Информационные системы и технологии», 22-25 апреля 2003 г., Новосибирский государственный технический университет, Новосибирск, Россия;

6) 6th International Conference in Computer Graphics and Artificial Intelligence (3IA *2003), 14-15 of May, 2003, Limoges, France;

7) 1-ая Всероссийская научно-практическая конференция «Опыт практического применения языков и программных систем имитационного моделирования

в промышленности и прикладных разработках», 23-24 октября 2003 г., ФГУП ЦНИИ технологии судостроения, Санкт-Петербург, Россия;

8) Научно-практическая конференция «Дни науки в НГТУ», 7 марта 2004 г., Новосибирский государственный технический университет, Новосибирск, Россия;

9) 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 страницах.

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

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

Рис. 1. Технологическая карта раскроя с маршрутом вырезки деталей

Рассмотрим множество деталей технологической карты раскроя, состоящих из внутренних и внешних контуров (см. рис. 1). Каждый контур имеет начальную точку вырезки (х,,у,), принадлежащую ьму контуру (¡=1,2,.. ,п). Обозначим расстояние между начальными точками вырезки /-го иЛ-го контура

через L¡j (ij=0,l,...,n). Причём, равенство нулю индекса / (или у) означает соответствие началу координатной системы, т. е. точке (0,0).

Необходимо найти кратчайший маршрут к из множества .допустимых маршрутов

** = ('ii.xi\ )Mxi2 >У>2 ).~Л(*/Я 'Ух„ )),

где (i¡, Í2, .... in) — произвольная перестановка чисел 1, 2,..., п.

Задача принимает вид

* и-1

F(k ) = min (lo/, Ц ,«,) + S LijiJ+l (xj. *yij'xij+l >y¡J+l) + Ъ„0У>

В систему геометрических ограничений вошли полученные аналитически параметрические уравнения участков полилиний и окружностей, которыми представлены контуры деталей технологической карты раскроя:

x¡= a¡+ гj cos t¡, y¿= b¡+ ri sin t¡,

где 0 <i <m -1 (m — количество окружностей), 0<t¡< 2л, a¿b¡ — координаты центра г'-ой окружности, г, — радиус /'-ой окружности;

xij=xijl+(xij2'xijl) t,j. y¡j -y yI+(y¡j2~y¡jl) t¡j, где m < i < m+n-1 (/ra — количество окружностей и n — количество

полилиний), О <J <р-1 (p¡ — количество отрезков в /-ой полилинии), 0 < ty < 1, x¡jl.y¡jl и xij2.yij2 — координаты конечных точек /-го отрезка /'-ой полилинии; xij = a¡j+ (xyi-аф cos ty - (yiji-bij) sin ty, y¡¡ = bij+ (yiji-bjß cos ty+ (xiji-a,j) sin ty , где m < i < m+n-l (m — количество окружностей и n — количество полилиний), p¡ <j< pi+dj -1 (p¡ — количество отрезков в /-ой полилинии и d¡ — количество дуг в /-ой полилинии), 0 < ty < <ру при <ру>0 и ? у < ty < 0 при <p,j<0 (<ру — угол стянутого дугового сегмента и <ру = 4 arctg ky, где ky — кривизна этого сегмента), xy¡,yy¡ и ху2,уу2 — координаты концов j'-ой дуги /-ой полилинии, ау.Ъу — координаты центра j-ой дуги /'-ой полилинии, определяемые следующим образом:

а * Х'>2 " C0S ) ~ ~ УУ1) Si" 9ij

lJ 2(l-cos<Py) •

ь (y'Jl + y'j2 ^"cos ^ + ^X'J2 ~ Vy

Ü= 2(1 - cos <Pij )

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

Кроме геометрических ограничений, существует ряд технологических ограничений, связанных со спецификой исполнительного инструмента. В частности, в качестве таких ограничений могут являться следующие: 1) маршрут начинается и заканчивается в начале координатной системы; 2) исключается возможность пересечения резов; 3) внешний контур детали обрабатывается только после того, как обработаны все ее внутренние контуры.

В рамках этой главы сделан обзор наиболее часто используемых методов для решения задач маршрутизации. Обычно используются четыре следующих эвристических алгоритма: 1) метод ближайшего соседа (Nearest Neighbor); 2) метод включения ближайшего города (Nearest Town); 3) метод самого дешевого включения (Most Cheap Inclusion); 4) метод минимального остовного дерева (Minimum Spanning Tree). Однако методы 1 и 3 мало эффективны для сложных карт раскроя, а методы 2 и 4 не учитывают дискретно-непрерывную структуру задачи.

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

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

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

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

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

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

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

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

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

Таблица 1

№п/п Состав генов Описание составляющей

1 Порядковый номер / графического примитива (контура) в наборе Дискретная величина

2 Первая координата х, начальной точки вырезки /-го контура Непрерывная величина

3 Вторая координата у, начальной точки вырезки /-го контура Непрерывная величина

Любое решение, закодированное в хромосоме, должно удовлетворять матрице структуры технологической карты раскроя Упх.п=0'у)пхп> где и — количество контуров деталей (^-0,1,2,...,п-1). Элемент матрицы= 1, если ьый контур принадлежит внутренней области¡-го контура, иначе уу =0. В случае уу = 1 необходимо, чтобы ьый контур вырезался ранее¡-го контура.

Для построения этой матрицы решается вспомогательная задача определения вложенности контуров деталей. Контуры деталей соответствуют полилиниям и окружностям. Уровень вложенности контуров не ограничен.

На основе тестовых данных в ходе экспериментальных исследований выбираются параметры гибридного ГА согласно таблице 2.

Таблица 2

Параметры гибридного генетического алгоритма

№ Наименование параметра Обозначение Рекомендуемое

п/п значение

1 Размер популяции ЯР 20-100

2 Число генераций ТО 20-100

3 Вероятность скрещивания Р8 0.7-0.9

4 Вероятность мутации РМ 0.05-0.1

5 Степень обновления популяции 80 0.95-1.0

6 Количество попыток КР 3-5

7 Максимальная длина активного хода МБ 200-300

исполнительного инструмента (в мм)

Общую схему разработанного генетического алгоритма можно описать следующим образом:

Шаг 1. Построение матрицы вложенности контуров.

Шаг 2. Применение "жадного" алгоритма для построения маршрута.

Шаг 3. Ввод параметров расчёта.

Шаг 4. Порядковый номер попытки 1-1 (1=1,2,..,КР).

Шаг 5. Формирование начальной популяции /-ой попытки.

Шаг 6. Целенаправленное изменение хромосом начальной популяции.

Шаг 7. Порядковый номер генерации /-ой попытки/=/ 0=1,2, ...,ТО).

Шаг 8. Выделение элиты и формирование текущей/-ой популяции.

Шаг 9. Скрещивание хромосом в .¡-ой популяции.

Шаг 10. Мутация хромосом в ¡-ой популяции.

Шаг 11. Целенаправленное изменение новых хромосом.

Шаг 12. Добавление новых хромосом к ¡-ой популяции.

Шаг 13. Селекция в ¡-ой популяции.

Шаг 14. Добавление элиты к/-ой популяции.

Шаг 15. Переход к следующей популяции: ]= ¡+1.

Шаг 16. Если ./£7X7, то переход к шагу 8, иначе определение наилучшего маршрута /-ой попытки.

Шаг 17. Переход к следующей попытке: 1=1+1.

Шаг 18. Если ;<КРто переход к шагу 5, иначе определение наилучшего маршрута за время работы алгоритма.

Шаг 19. Вывод результирующего маршрута.

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

I гп<1

Хромосома А (первый родитель)

Порядковый номер контура 'а/ 'а2 'аи

Координаты точки врезки (ха1:Уа>) (ха2,Уа2) ... (хагьУап)

Хромосома В (второй родитель) у

Порядковый номер контура ¡Ы т ... ¡Ьп

Координаты точки врезки (ХЫ,УЫ) (ЧЪУЬ2) (Чп,УЬп>

Хромосома С (первый потомок)

Порядковый номер контура ¡Ьп 'Ь2 1ап

Координаты точки врезки (Чп-УЬп) (Ч2,УЬ2> (хап>Уап)

Хромосома О (второй потомок)

Порядковый номер контура 'Ы ¡а2 ... 'а1

Координаты точки врезки (ХЫ.УЫ) (Ха2,Уа2> (Ха!,Уа1)

Рис.3. Механизм операции скрещивания

гги! I гпй

Хромосома до операции мутации

Порядковый номер контура ¡а! 1а2 - Ы Щ ■

Координаты точки врезки (ХаЬУаО ... (хсв*. Уап)

Хромосома после операции мутации

Порядковый номер контура 1а1 гап ... «о2

Координаты точки врезки (Ха1.Уа1) (хагиУап) (Ха2,Уа2)

Рис.4. Механизм операции мутации

Данный генетический алгоритм можно назвать гибридным, так как в нём реализовано целенаправленное изменение хромосом с целью улучшения значений целевой функции F(k). Для этого предлагается ликвидировать имеющиеся пересечения в маршрутах, используя оператор инверсии, и применить к каждой хромосоме оператор разнообразия. Операция разнообразия вносит некоторые изменения в хромосому, не меняя порядка вырезаемых контуров. Эти изменения относятся к координатам начальных точек вырезки контуров деталей. Оператор разнообразия улучшает качество решения, используя метод циклического координатного спуска, и минимизирует количество врезок.

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

Рис.5. Графическая интерпретация алгоритма локальной оптимизации

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

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

Если изменения целевой функции В(к) для двух последних циклов не превысили заданную точность то итерационный алгоритм оператора разнообразия прекращает свою работу.

В процессе проведённого исследования оценена временная сложность разработанного гибридного генетического алгоритма как О(п ), где п — количество обрабатываемых контуров деталей.

В третьей главе осуществлён сравнительный анализ гибридного генетического алгоритма с другими, часто используемыми методами (см. рис. 6).

Рис. 6. График зависимостей длин результатных маршрутов различных методов от количества контуров деталей :1-гибридный ГА, 2-классический ГА, 3-алгоритм «ближайшего соседа», 4-алгоритм «самого дешёвого включения»

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

Был исследован на практике процесс получения гибридным ГА эффективного решения за определённое количество итераций, который теоретически вытекает из механизма его работы, представлены соответствующие зависимости средней ценности популяции и минимальной длины маршрутов в популяции от номера поколения (см. рис. 7).

Номер поколения

Рис.7. График зависимостей средней ценности популяции и минимальной длины маршрутов в популяции от номера поколения

В рамках этой главы исследовано влияние параметров ГА (см. табл. 2) на эффективность поиска, в частности на скорость его работы и качество получаемого решения. В работе приведены полученные опытным путем, усреднённые данные, графические иллюстрации вычислительного эксперимента. Рекомендованы диапазоны задаваемых пользователем значений для параметров разработанного алгоритма (см. табл. 2). Например, для параметра количество генераций (ТО) зависимости, характеризующие скорость ГА и устойчивость поиска, графически отражены на рисунках 8 и 9 соответственно. Причём, вторая зависимость показана как среднее отклонение от рекорда задачи в процентах.

Число генераций

Рис 8. График скорости гибридного ГА при исследовании влияния параметра ТО

1 6

1 4

Число генераций TG

Рис 9 График зависимости средней погрешности от числа генераций

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

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

Программный комплекс разработан в среде разработки приложений Visual LISP и представляет собой FAS-проект, включающий в себя двадцать два LISP-файла. Приложение системы AutoCAD работает на IBM-совместимых PC.

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

Входной информацией для разработанного комплекса является технологическая карта раскроя, представляющая собой рисунок системы AutoCAD. Рисунок системы AutoCAD имеет организацию, аналогичную организации базы данных, в которой элементы (графические примитивы и неграфические объекты) имеют списковую структуру. Каждый примитив обладает своим типом. Функции доступа к примитивам AutoCAD работают с примитивами рисунка, обращаясь непосредственно к их внутренней структуре.

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

Для получения случайных чисел была использована таблица случайных чисел (1500 элементов), первоначально сгенерированная в MS Excel.

Результаты работы программы сохраняются в исходном документе с расширением dwg и в текстовом файле отчёта (в рабочей директории AutoCAD).

Кроме этого, в четвёртой главе представлен интерфейс пользователя с программой, реализованный посредством языка DCL; показаны диалоговые экраны с директивами, сообщениями и запросами.

Язык DCL (Dialog Control Language) имеет много общего с языком С. Файл, написанный на языке DCL, состоит из логических единиц — директив, которые записываются в свободном формате. Директивы располагаются в файле последовательно. Каждая директива описывает поле или способ группировки полей при выравнивании внутри диалогового окна. Есть также директива для описания диалога в целом. В одном файле могут быть заданы один или несколько диалогов. Для того чтобы программа могла обратиться к диало-

гу, нужно выполнить загрузку ОСЬ-файла, содержащего описание этого диалога

Разработанное программное обеспечение использует для диалога с пользователем следующие ОСЬ-файлы

1) р^ — описание директив для выполнения пользователем,

2) рууоё ёе1 — описание диалога ввода параметров расчета,

3) ругуоё ёе1 — описание диалога о намерении пользователя относительно результатного маршрута и продолжения работы

Например, диалоговое окно ввода параметров расчета гибридного генетического алгоритма представлено на рисунке 10

Рис 10 Диалоговое окно ввода параметров расчета

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

/-' --

1-,

,-/

Поимео 1 Поинео г Поимео 3

Фигурный роскрой

Поимео 4

Рис 11 Тестовые примеры фигурного раскроя с маршрутами обхода

Рис. 12. Тестовые примеры с маршрутами обхода контуров деталей

Заключение

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

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

2. Разработан гибридный генетический алгоритм.

2.1. Создана оригинальная архитектура поиска эффективного решения задачи посредством гибридизации методологии генетического программирования с традиционными вычислительно-поисковыми процедурами.

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

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

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

2.5. Проведена оценка временной сложности гибридного генетического алгоритма, которая составила О(п2).

3. Исследована эффективность гибридного генетического алгоритма. Предложенный алгоритм по длине пути даёт результаты в среднем на 20% лучше классического ГА (без целенаправленного изменения хромосом), на 30% лучше алгоритма «ближайшего соседа», на 10% лучше алгоритма «самого дешёвого включения». Рассмотрен процесс получения эффективного решения в ходе итерационного поиска посредством гибридного ГА. Исследовано влияние параметров расчёта на скорость и устойчивость поиска эффективного решения. Даны рекомендации по выбору значений этих параметров. Отмечены перспективные направления исследования с целью повышения эффективности ГА, такие как распараллеливание процесса поиска и построение адаптивных многоуровневых генетических алгоритмов.

4. Разработан программный комплекс для среды AutoCAD, взаимодействующий с графической базой данных этой системы. Интерфейс пользователя с программой реализован средствами языка DCL. Программа протестирована на достаточном количестве технологических карт раскроя и имеет инструкцию для пользователя.

Список публикаций

1. Пушкарёва Г.В. Автоматизированное проектирование оптимальных траекторий с использованием гибридного генетического алгоритма // Материалы 8-ой Всероссийской научно-технической конференции «ИТ в науке, проектировании и производстве». - Н. Новгород: МВВО АТН РФ, 2003. - С.30-33.

2. Пушкарёва Г.В. Алгоритмы и программное обеспечение для решения задач маршрутизации // Материалы 7-ой Всероссийской научно-технической конференции «Информационные технологии в науке, проектировании и производстве». - Н. Новгород: МВВО АТН РФ, 2002. - С.22-23.

3. Пушкарёва Г.В. Генетическое программирование при автоматизированном проектировании управляющих программ для систем ЧПУ // Сборник научных трудов НГТУ. - Новосибирск, 2004. - №1(35). - С. 67-72.

4. Пушкарёва Г.В. Гибридный генетический алгоритм для автоматизированного проектирования оптимальных траекторий // Материалы 1-ой Всероссийской научно-практической конференции «Опыт практического применения языков и программных систем имитационного моделирования в промышленности и прикладных разработках».- СПб.: ФГУП ЦНИИ, 2003.-Т.2.-С.190-195.

5. Пушкарёва Г.В. Оптимизация траектории движения исполнительного инструмента тепловой резки металла на оборудовании с ЧПУ // Материалы докладов региональной научной конференции «Наука. Техника. Инновации». -Новосибирск: НГТУ, 2002. - С. 183-185.

6. Пушкарёва Г.В. Применение генетического алгоритма при автоматизированном проектировании управляющих программ термической резки металла // Материалы региональной научно-практической конференции «Вузы Сибири и Дальнего Востока — Транссибу». - Новосибирск: СГУПС, 2002. - С. 129-138.

7. Фроловский В.Д., Пушкарёва Г.В. Автоматизированное проектирование оптимальных траекторий движения исполнительного инструмента тепловой резки металла на оборудовании с ЧПУ // Материалы Международной научно-технической конференции «Информационные системы и технологии». - Новосибирск: НГТУ, 2003. - Т.1. - С.149-152.

8. Frolovsky V.D., Pushkaryova G.V. Metal cutting motion optimization for NC-programs design, using genetic algorithms // Proceedings of the 6th International Conference 3LV2003 in Computer Graphics and Artificial Intelligence. - Limoges (France), 2003. - P. 143-152. (Оптимизация процесса резки металла для проектирования NC-программ с использованием генетических алгоритмов)

9. Frolovsky V.D., Pushkaryova G.V. Design Optimization of Control Programs for Thermal Metal Cutting, Using Genetic Algorithm // Proceedings of the 8th Korea-Russia International Symposium on Science and Technology.- Tomsk (Russia), 2004.- Vol.1.- P.27-31. (Оптимизация проектирования управляющих программ для термической резки металла с использованием генетического алгоритма)

Подписано в печать Формат 60x84 1/16. Бумага офсетная.

Тираж 100 э к з . П е ч . л. 1,5. Заказ №

Отпечатано в типографии Новосибирского государственного технического университета 630092, г. Новосибирск, пр. К. Маркса, 20

*\

№20965

РНБ Русский фонд

2005-4 18925

Введение

1. Постановка задачи и метод решения

1.1. Содержание проблемы оптимизации траектории движения исполнительного инструмента

1.2. Методы решения оптимизационных задач маршрутизации

1.3. Выбор метода решения. Методология генетического программирования

1.4. Выводы 35 2. Гибридный генетический алгоритм

2.1. Общая схема разработанного гибридного генетического алгоритма

2.2. Определение вложенности контуров

2.3. Характеристика применяемых генетических операторов

2.3.1. Оператор скрещивания

2.3.2. Оператор мутации

2.3.3. Оператор селекции

2.4. Целенаправленное изменение хромосом

2.4.1. Оператор инверсии

2.4.2. Оператор разнообразия

2.5. Оценка временной сложности гибридного генетического алгоритма

2.6. Выводы 70 3. Исследование эффективности гибридного генетического алгоритма

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

3.2. Исследование процесса получения эффективного решения гибридным генетическим алгоритмом

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

3.3.1. Число генераций и количество попыток

3.3.2. Размер популяции и степень её обновления

3.3.3. Вероятности скрещивания и мутации

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

3.5. Выводы 109 4. Реализация гибридного генетического алгоритма

4.1. Программная реализация разработанного алгоритма и её связь с графической БД системы AutoCAD

4.2. Интерфейс пользователя с программой

4.3. Тестовые примеры и инструкция пользователю

4.4. Выводы 126 Заключение 127 Список использованной литературы 130 Приложение

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

Траектория движения режущего инструмента состоит из следующих элементов [80]:

1) внешних контуров вырезаемых деталей;

2) внутренних контуров;

3) траекторий, связывающих смежные контуры (вырезаемые с одной врезки);

4) траекторий переходов инструмента в выключенном состоянии от одной точки врезки к другой.

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

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

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

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

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

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

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

Для нахождения приближённого решения задачи в работе было решено разработать гибридный генетический алгоритм, обладающий устойчивостью к попаданию в точки локальных экстремумов и способностью постоянно увеличивать качество популяции от поколения к поколению. Генетические алгоритмы (ГА) успешно используются при проектировании СБИС в задачах размещения [92,99], в задачах двумерной упаковки [52], при решении комбинаторно-логических задач [102], задач канальной трассировки [93,103,104,106], задачи распределения инвестиций и других экономических задач [70]. Известны научные работы JI.A. Растригина по направлению генетических алгоритмов [67].

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

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

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

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

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

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

2) специализация гибридного генетического алгоритма для решения задачи маршрутизации:

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

- оригинальная архитектура поиска эффективного решения задачи;

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

- алгоритм локальной оптимизации, основанный на методе циклического координатного спуска.

3) программное приложение системы AutoCAD, реализующее гибридный генетический алгоритм;

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

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

- математическая модель задачи маршрутизации для обхода геометрических объектов с внутренними контурами, включая 1) критерий оптимальности, учитывающий дискретно-непрерывную структуру рассматриваемой задачи, 2) геометрические ограничения, описанные аналитически в виде совокупности параметрических уравнений, 3) ряд технологических ограничений, учтённых при алгоритмизации и разработке программного комплекса;

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

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

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

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

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

- снизить энергетические затраты на резку металла;

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

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

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

Программная реализация гибридного генетического алгоритма показала значительные преимущества перед классическим ГА и используемыми на практике эвристическими методами для широкого класса задач маршрутизации. Предложенный гибридный генетический алгоритм по длине пути даёт результаты в среднем на 20% лучше классического ГА (без целенаправленного изменения хромосом), на 30% лучше алгоритма «ближайшего соседа», на 10% лучше алгоритма «самого дешёвого включения».

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

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

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

1) Региональная научно-практическая конференция «Вузы Сибири и Дальнего Востока — Транссибу», 27-29 ноября 2002 г., Сибирский государственный университет путей сообщения, Новосибирск, Россия;

2) Региональная научная конференция студентов, аспирантов и молодых учёных «Наука. Техника. Инновации», 5-8 декабря 2002 г., Новосибирский государственный технический университет, Новосибирск, Россия;

3) 7-ая Всероссийская научно-техническая конференция «Информационные технологии в науке, проектировании и производстве», декабрь 2002 г., МВВО АТН РФ, Н. Новгород, Россия;

4) 8-ая Всероссийская научно-техническая конференция «Информационные технологии в науке, проектировании и производстве», 18 апреля 2003 г., МВВО АТН РФ, Н. Новгород, Россия;

5) Международная научно-техническая конференция «Информационные системы и технологии», 22-25 апреля 2003 г., Новосибирский государственный технический университет, Новосибирск, Россия;

6) 6th International Conference in Computer Graphics and Artificial Intelligence (3IA'2003), 14-15 of May, 2003, Limoges, France;

7) 1-ая Всероссийская научно-практическая конференция «Опыт практического применения языков и программных систем имитационного моделирования в промышленности и прикладных разработках», 23-24 октября 2003 г., ФГУП ЦНИИ технологии судостроения, Санкт-Петербург, Россия;

8) Научно-практическая конференция «Дни науки в НГТУ», 7 марта 2004 г., Новосибирский государственный технический университет, Новосибирск, Россия;

9) 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 печатных листа) [61-66, 81,96, 97].

Содержание диссертационной работы по главам:

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

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

- в третьей главе диссертации исследована эффективность гибридного генетического алгоритма, для этого проведён сравнительный анализ разработанного алгоритма с другими, часто используемыми методами, рассмотрен процесс получения эффективного решения в ходе итерационного поиска, исследовано влияние параметров расчёта на скорость и устойчивость поиска эффективного решения, даны рекомендации по выбору значений этих параметров и отмечены перспективные направления исследования с целью повышения эффективности ГА;

- в четвёртой главе диссертации описан разработанный программный комплекс для среды AutoCAD, работающий во взаимодействии с графической базой данных этой системы, и интерфейс пользователя, реализованный средствами языка DCL; представлены тестовые примеры с картами раскроя и инструкция для пользователя.

Результаты исследования, содержащиеся в этой главе, были опубликованы в [63, 64, 81, 96, 97].

ЗАКЛЮЧЕНИЕ

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

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

2. Разработан гибридный генетический алгоритм.

2.1. Создана оригинальная архитектура поиска эффективного решения задачи посредством гибридизации методологии генетического программирования с традиционными вычислительно-поисковыми процедурами.

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

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

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

3. Исследована эффективность гибридного генетического алгоритма. Предложенный алгоритм по длине пути даёт результаты в среднем на 20% лучше классического ГА (без целенаправленного изменения хромосом), на 30% лучше алгоритма «ближайшего соседа», на 10% лучше алгоритма «самого дешёвого включения». Рассмотрен процесс получения эффективного решения в ходе итерационного поиска посредством гибридного ГА. Исследовано влияние параметров расчёта на скорость и устойчивость поиска эффективного решения. Даны рекомендации по выбору значений этих параметров. Отмечены перспективные направления исследования с целью повышения эффективности ГА, такие как распараллеливание процесса поиска и построение адаптивных многоуровневых генетических алгоритмов.

4. Разработан программный комплекс для среды AutoCAD, работающий во взаимодействии с графической базой данных этой системы. Интерфейс пользователя с программой реализован средствами языка DCL. Программа протестирована на достаточном количестве технологических карт раскроя и имеет инструкцию для пользователя.

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

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

1. Автоматизация технологической подготовки заготовительного производства / Под ред. Г.П. Гырдымова. Ленинград: Машиностроение, 1990. - 350с.

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. -М.: Наука, 1987. -247 с.

3. Альбрехт Э.Г. и др. Методы оптимизации. Введение в теорию решения экстремальных задач: Учебное пособие. — Екатеринбург: Уральский гос. ун-т, 1993.-165 с.

4. Аттетков А.В. и др. Методы оптимизации: Учебник для втузов. — М.: МГТУ им. Н.Э. Баумана, 2001. 439 с.

5. Банди Б. Методы оптимизации. Вводный курс: Пер. с англ. М.: Радио и связь, 1988.-215 с.

6. Банди Б. Основы линейного программирования: Пер. с англ. — М.: Радио и связь, 1989. 176 с.

7. Банк Б. И др. Математическая оптимизация: вопросы разрешимости и устойчивости. М.: МГУ, 1986. - 216 с.

8. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. М.: Наука, 1989. - 160 с.

9. Батищев Д.И. Генетические алгоритмы решения экстремальных задач: Учебное пособие. Воронеж, 1995. - 189 с.

10. Васильев О.В. Лекции по методам оптимизации: Учебное пособие. Иркутск: Изд-во Иркутского ун-та, 1994. - 340 с.

11. Васильев Ф.П. Методы оптимизации. М.: Факториал Пресс, 2002. — 823 с.

12. Верхотуров М.А., Верхотурова Г.Н., Логинов Е.В. Применение метода "Поиск с запретами" (TS) для решения задач нерегулярного раскроя-упаковки // Принятие решений в условиях неопределенности. Уфа: УГАТУ, 2000. - С. 123-127.

13. Владимирова Н.Ю., Сигал И.Х. Параметризация при решении некоторых классов задач дискретной оптимизации большой размерности. М.: ВЦ РАН,2001.-79 с.

14. Габасов Р.Ф. и др. Конструктивные методы оптимизации: В 5 ч. — Минск: Университетское, 1998.

15. Габасов Р.Ф., Кириллова Ф.М. Методы оптимизации: Учебное пособие. -Мн.:БГУ, 1981.-350 с.

16. Галеев Э.М. Оптимизация: Теория. Примеры. Задачи. М.: УРСС, 2002. -302 с.

17. Гилл Ф.И. др. Практическая оптимизация: Пер. с англ. М.: Мир, 1985. -509 с.

18. Глебов Н.И. Об условиях разрешимости оптимизационных задач жадным алгоритмом // Дискретный анализ и исследование операций. Июль-декабрь2002. Серия 2. -Том 9, №2. - С.3-12.

19. Гончаров Е.Н., Кочетов Ю.А. Вероятностный поиск с запретами для дискретных задач безусловной оптимизации // Дискретный анализ и исследование операций. Июль-декабрь 2002. - Серия 2. - Том 9, №2. - С. 13-30.

20. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.: Мир, 1982.-416 с.

21. Давиденко В.Н., Курейчик В.М. Генетический алгоритм для трассировки двухслойных каналов // Автоматизация проектирования. 1999. №1. - С. 3441.

22. Даффин Р. и др. Геометрическое программирование: Пер. с англ. М.: Мир, 1972.-311 с.

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

24. Дробязко О.Н. Оптимизация в САПР, часть 1: Учебное пособие. Барнаул: АлтГТУ, 2000. - 70 с.

25. Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации. -М.: Наука, 1982. 432 с.

26. Еремеев А.В. Генетический алгоритм для задачи о покрытии // Дискретный анализ и исследование операций. Январь-июнь 2000. - Серия 2. - Том 7, №1. -С. 47-60.

27. Ериклинцев В.В., Фридман С.С., Розенфельд В.Х. Оптимизация раскроя проката. М.: Металлургия, 1984. - 362 с.

28. Ерош И.Л. Дискретная математика. Комбинаторика: Учебное пособие. -СПб.: СПбГУАП, 2001. 35 с.

29. Жадан В.Г. Дополнительные главы методов оптимизации: Учебное пособие для вузов. М.: МФТИ, 2002. - 72 с.

30. Жадан В.Г. Численные методы линейного и нелинейного программирования: вспомогательные функции в условной оптимизации. М.: ВЦ РАН, 2002. -159 с.

31. Жак С.В. О методах решения задач, сочетающих эвристику и случайный выбор // Кибернетика. 1972. №1. - С.119-121.

32. Жиглявский А.А. Методы поиска глобального экстремума. М.: Наука, 1991.-248 с.

33. Зайцева Е.Н., Станкевич Ю.А. Некоторые современные методы решения оптимизационных задач.http://bsuinet 125 .bsu.unibel.by/conferences/nite/doklad 13 .html

34. Измаилов А.Ф. Численные методы оптимизации: Учебное пособие. М.: Физматлит, 2003. - 300 с.

35. Канторович J1.B., Залгаллер В. А. Рациональный раскрой промышленных материалов. Новосибирск: Наука, 1971.- 298 с.

36. Карапетян Г.К., Шульденов Г.А. Однопроходный алгоритм линейной аппроксимации последовательности точек на плоскости // Кибернетика. 1984. №1. - С. 114-117.

37. Карманов В.Г. Математическое программирование: Учебное пособие. — М.: Физматлит, 2000. 263 с.

38. Ковалёв М.М. Дискретная оптимизация. Целочисленное программирование. Минск: БГУ, 1977. - 191 с.

39. Комплекс программ "Маршрут" (руководство пользователя) / Моск. гос. техн. ун-т им. Н.Э.Баумана, каф. Системы автоматизированного проектирования. http://vikt.mega.ru/route.html.

40. Коннов В.В. и др. Геометрическая теория графов. М.: Народное образование, 1999.-240 с.

41. Корнеев В.В., Гареев А.Ф., Васютин С.В., Райх В.В. Базы данных. Интеллектуальная обработка информации. М.: Нолидж, 2000. - 352 с.

42. Костюк Ю.Л., Жихарев С.А. Эффективный алгоритм приближённого решения метрической задачи коммивояжера // Дискретный анализ и исследование операций. Январь-июнь 2000. - Серия 2. - Том 7, №1. - С. 65-74.

43. Кочетов Ю., Младенович Н., Хансен П. Локальный поиск с чередующимися окрестностями // Дискретный анализ и исследование операций. Январь-июнь 2003. - Серия 2. - Том 10, №1. - С. 11-43.

44. Красовская М.А. Методы и алгоритмы нелинейного программирования в АСУ: Учебное пособие. М.: МАИ, 1994. - 40 с.

45. Кузюрин Н.Н. Вероятностные приближённые алгоритмы в дискретной оптимизации И Дискретный анализ и исследование операций. Июль-декабрь 2002. - Серия 2. - Том 9, №2. - С. 97-114.

46. Курейчик В.М. Генетические алгоритмы и их применение в САПР, интеллектуальные САПР // Межведомственный тематический научный сборник. -Таганрог, 1995. С. 7-11.

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

48. Лихтенштейн В.Е. Модели дискретного программирования. М.: Наука, 1971.-239 с.

49. Мастяева И.Н. Методы оптимизации: Текст лекций. М.: МЭСИ, 1990. -66с.

50. Медынский М.М., Антоний Е.В. Численные методы нелинейной оптимизации: алгоритмы и программы: Учебное пособие. М.: МАИ, 2003. - 189 с.

51. Мудров В.И. Задача о коммивояжере. М.: Знание, 1969. - 62 с.

52. Мухачева Э.А. Рациональный раскрой промышленных материалов. Применение в АСУ. М.: Машиностроение, 1984. - 176 с.

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

54. Напалков А.В. Эвристическое программирование: Учебное пособие. Ростов н/Д: Изд-во Ростовского ун-та, 1971. - 127 с.

55. Ногин В.Д., Протодьяконов И.О., Евлампиев И.И. Основы теории оптимизации: Учебное пособие / Под ред. И.О. Протодьяконова. М.: Высш. шк., 1986.-384 с.

56. Новиков Ф.А. Дискретная математика для программистов. СПб.: Питер, 2001.-304 с.

57. Норенков И.П. Эвристики и их комбинация в генетических методах дискретной оптимизации // Информационные технологии. 1999. №1. - С. 2-7.

58. Полещук Н.Н. VisualLISP и секреты адаптации AutoCAD. СПб.: БХВ-Петербург, 2001. - 576 с.

59. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. - 478 с.

60. Пушкарёва Г.В. Генетическое программирование при автоматизированном проектировании управляющих программ для систем ЧПУ // Сборник научных трудов НГТУ. 2004. №1. - С. 67-72.

61. Пушкарёва Г.В. Оптимизация траектории движения исполнительного инструмента тепловой резки металла на оборудовании с ЧПУ // Материалы докладов региональной научной конференции «Наука. Техника. Инновации». -Новосибирск: НГТУ, 2002. С.183-185.

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

63. Редько В.Г. Эволюционная кибернетика: Тезисы курса лекций / Институт прикладной математики им. В.М. Келдыша РАН. -http://www.keldvsh.ru/BioCvber/Lectures.html.

64. Редько В.Г., Дябин М.И., Елагин В.М., Карпинский Н.Г., Половянюк А.И., Сереченко В.А., Ургант О.В. К микроэлектронной реализации эволюционного оптимизатора // Микроэлектроника. 1995. №3. - С.207-210.

65. Романов В.П. Интеллектуальные информационные системы в экономике: Учебное пособие / Под ред. Н.П. Тихомирова. М.: Экзамен, 2003. - 496 с.

66. Рубиштейн М.И. Задачи и методы комбинаторного программирования. -М.: Наука, 1976.

67. Сигал И.Х. Последовательность применения алгоритмов приближённого решения в комбинированном алгоритме решения задачи коммивояжера // Журнал вычислительной математики и математической физики. 1989. Т.29. №11. — С. 1714-1721.

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

69. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы. -М.: Физматлит, 2002. 237 с.

70. Слэйк Дж.Р. Искусственный интеллект. Подход на основе эвристического программирования: Пер. с англ. -М.: Мир, 1973. 319 с.

71. Смирнов А.П. Методы оптимизации: Учебное пособие. М.: МИСиС, 2002.- 134 с.

72. Сухарев А.Г. Оптимальный поиск экстремума. М.: МГУ, 1975. - 100 с.

73. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. -М.: Наука, 1986. 328 с.

74. Стоян Ю.Г., Яковлев С.В. Математические модели и оптимизационные методы геометрического проектирования. Киев: Наук, думка, 1986. - 286 с.

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

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

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

78. Хахулин Г.Ф. Постановки и методы решения задач дискретного программирования: Учебное пособие. М.: Изд-во МАИ, 1992. - 59 с.

79. Хохлюк В.И. Задачи целочисленной оптимизации. Алгоритмы: Учебное пособие. Новосибирск: НГУ, 1980. - 91 с.

80. Шабунин М.И., Шеверов В.Г. Некоторые вопросы математического программирования. Дискретное программирование: Учебное пособие. — Долгопрудный, 1980. 102 с.

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

82. Bard J.F. and Feo N.F. Operations Sequencing in Discrete Parts Manufacturing // Management Science.- 1989.- 35:249-255.

83. Bellman R. Dynamic Programming // Princeton University Press, USA, 1957.

84. Bellman R.E. and Dreyfus S.E. Applied Dynamic Programming // Princeton University Press, USA, 1962.

85. Cohoon J.P. and Paris W.D. Genetic placement // IEEE Trans. Comput.-Aided Des. Integrated Circuits & Syst.- 1987.- Vol.6.- 6:956-964.

86. Davidenko V.N., Kureichik V.M., and Miagkikh V.V. Genetic Algorithm for Restrictive Channel Routing Problem // Proc. of the 7th International Conf. on Genetic Algorithms.- M. Kaufmann Publisher.- San Mateo, California, 1997.- P.636-642.

87. Dereli T. and Filiz I.H. Optimizing Cutting Parameters in Process Planning of Prismatic Parts by Using Genetic Algorithms // International Journal of Production Research.- 2001.- Vol. 39.- 15:3303-3328.

88. Feo N.F. and Bard J.F. The Cutting Path and Tool Selection Problem in Computer-Aided Process Planning // Journal of Manufacturing Systems.- 1989.- 8:17-26.

89. Goldberg D.E. Genetic Algorithms in Search, Optimization and Machine Learning // Adison Wesley, Reading, MA, 1989.

90. Goodman E., Tetelbaum A. and Kureichik V. A Genetic Algorithm Approach to Compaction, Bin Packing, and Nesting Problems // Case Center Technical Report № 940702.- Michigan State University, 1994.

91. Hart J.P. and Shogan A.W. Semi-Greedy Heuristica: An Empirical Study // Operation Research Letters.- 1987.- 6:107-114.

92. Holland J. Adaptation in Natural and Artificial Systems // University of Michigan Press Ann Arbor, USA, 1975.

93. Kureichik V.M. et all. Some New Features in Genetic Solution of the Traveling Salesman Problem // Proc. of the Second Intl. Conf. Adaptive Computing in Engineering, Design and Control.- Plymouth, UK, 1996.- P. 294-296.

94. Lieng J., Thulasiraman K. A Genetic Algorithm for Channel Routing in VLSI Circuits // Evolutionary Computation.- MIT, 1994, 1(4). P. 293-311.

95. Liu X., Sakamoto A., Shimamoto T. Restrictive Channel Routing with Evolution Programs // Trans. IEICE.- 1993.- Vol. E76-A.- 10:1738-1745.

96. O'Rourke J. and Rippel J. Two Segment Classes with Hamiltonian Visibility Graphs / Перевод М.Ю. Ратаева // Вычислительная геометрия. 1994. №4. - С. 209-218.

97. Rahmani А.Т. and Ono N. A Genetic Algorithm for Channel Routing Problem // Proc. 5th Intl. Conf. on Gas.- 1993.- P. 494-498.