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

• Автор: Ганелина, Наталья Давидовна
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Новосибирск
• Количество страниц: 124 с. : ил.

Оглавление
Введение
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. Выводы
4. Описание программного комплекса i.
Руководство пользователя
4.1. Описание интерфейса
4.2. Краткое руководство пользователя
4.3. Выводы
Заключение
Список использованной литературы


Программная реализация модифицированного алгоритма муравьиной оптимизации показала значительные преимущества перед часто используемыми на практике эвристическими методами для широкого класса задач маршрутизации. Достоверность результатов. Разработка математической модели задачи маршрутизации и создание на этой основе алгоритма стало возможным благодаря комплексному использованию теоретических и экспериментальных методов исследования. Решение ряда новых задач теории оптимизации и вычислительной геометрии, поставленных в работе в рамках диссертационного исследования, стало возможным благодаря известным достижениям указанных научных дисциплин и не противоречит их положениям, базируется на строго доказанных выводах фундаментальных и прикладных наук, таких как математический анализ, планиметрия, математическая статистика, теория оптимизации и планирование эксперимента. Разработанные новые теоретические и практические решения опробованы экспериментально. Экспериментальные исследования проводились с использованием технической базы Новосибирского государственного технического университета. Результаты экспериментов анализировались и сопоставлялись с известными экспериментальными данными других исследователей. Результаты работы, отраженные в программе автоматического проектирования маршрутов раскроя, прошли техническую экспертизу на предприятии и использованы в экспериментальном проектировании в промышленной системе «Техтран-Раскрой» как составной элемент. Апробация работы. Основные принципы и подходы для решения рассматриваемой задачи прошли апробацию на нескольких международных, региональных конференциях, обладают научной новизной и актуальностью, могут претендовать на мировой приоритет. Всероссийская научная конференция молодых ученых «Наука. Технологии. Инновации», г, Новосибирск, НГТУ. Международная конференция по компьютерной графике и ее приложениям Графикон, , гг. Новосибирск. Российско - корейский международный симпозиум по науке и технологиям, КСЖШ , Новосибирск, НГТУ. Международная конференция по компьютерной графике и искусственному интеллекту, А’, г, Лимож, Франция. Международная научно-техническая конференция «Высокие технологии и перспективы интеграции образования, науки и производства», , Ташкент. СТ’, , Уфа. Публикации. По теме диссертации опубликовано печатных работ, в их числе 2 статьи в центральных изданиях, входящих в перечень изданий, рекомендованных ВАК РФ, 1 - в сборнике научных трудов, 8 - в трудах и материалах международных конференций. Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников, включающего наименования, и приложения; общий объем составляет 2 страницы основного текста, включая рисунков и таблиц. На практике часто возникают ситуации, когда необходимо построить кратчайший маршрут проезда между заданными точками или наилучшим образом разместить пункты сервиса на дорогах, предприятия на территории, коммутаторы в телефонной сети и т. Это широко известные задачи маршрутизации и размещения. Многие из таких задач могут быть описаны с помощью оптимизационных моделей и сведены к решению дискретных задач. При анализе работы графопостроителя возникает сходная задача маршрутизации - построение оптимального пути обхода некоторых фигур. К рассматриваемой категории относится и вопрос построения маршрута обхода отрезков на плоскости и простейших фигур, составленных из отрезков. Технологический аспект задачи связан с программированием станков ЧПУ тепловой резки металла [, , ]. Одним из элементов управляющей программы станка является построение траектории переходов инструмента в выключенном состоянии от одной точки врезки к другой. Такие переходы и формируют исходное множество отрезков для поставленной задачи. Решаемая задача заключается в автоматизации проектирования оптимальных траекторий замкнутых маршрутов в двумерной дискретной области, заданной произвольным множеством непересекающихся отрезков или элементами технологической карты раскроя.