Содержание к диссертации
Введение
1. Постановка и анализ методов решения задачи построения маршрута обхода отрезков на плоскости 10
1.1. Описание проблемы оптимизации маршрута обхода отрезков на плоскости. Основные определения 11
1.2. Основные методы решения задачи построения цепей и циклов на множестве отрезков 15
1.2.1. Принцип жадности 16
1.2.2. Построение простых цепей и циклов на графе видимости концов отрезка. Выпуклая оболочка множества отрезков 21
1.2.3. Независимые и цело-координатные отрезки 38
1.2.4. Алгоритмы Хоффманна на графах видимости концов отрезков 43
1.3. Анализ эвристических методов решения 52
1.4. Формирование графа на основе заданного множества отрезков 54
1.5. Выводы 57
2. Метод колонии муравьев 58
2.1. Основные элементы, параметры и процедуры метаэвристики муравьиной оптимизации 58
2.2. Механизм обратной связи в процессе управления поведением муравья 63
2.3. Алгоритм поведения муравья в процессе принятия решения 65
2.4. Оценка вычислительной сложности алгоритма 71
2.5. Выводы 72
3. Исследование эффективности алгоритма. Влияние параметров алгоритма на качество решения 73
3.1. Сравнительный анализ разработанного алгоритма с другими методами 73
3.2. Влияние параметров алгоритма на качество решения 77
3.3. Исследование различных конфигураций отрезков 83
3.4. Исследование сходимости алгоритма 92
3.5. Средства повышения эффективности применения алгоритма 94
3.6. Выводы 96
4. Описание программного комплекса Ant colony routing. Руководство пользователя 97
4.1. Описание интерфейса 97
4.2. Краткое руководство пользователя 106
4.3. Выводы 112
Заключение 113
Список использованной литературы
- Основные методы решения задачи построения цепей и циклов на множестве отрезков
- Алгоритмы Хоффманна на графах видимости концов отрезков
- Алгоритм поведения муравья в процессе принятия решения
- Исследование различных конфигураций отрезков
Введение к работе
Настоящая диссертация посвящена проблемам построения маршрутов обхода отрезков на плоскости.
Актуальность проблемы. Прикладной аспект поставленной задачи связан с автоматизацией процесса генерации управляющих программ для станков ЧПУ тепловой резки металла, которые являются результатом сквозного цикла обработки информации от чертежа детали до программ ее изготовления в М7-кодах конкретного оборудования [21-25]. Одним из элементов траектории режущего инструмента является переход инструмента в выключенном состоянии от одной точки врезки к другой. Для толстолистового проката затраты на сквозную пробивку металла оказываются столь значительны, что экономически целесообразным становится обработка деталей без выключения режущего инструмента.
Задача состоит в оптимизации переходов режущего инструмента от одной точки врезки к другой. Исходными данными для задачи построения рационального маршрута являются технологические карты раскроя. Конфигурацию исходного множества формируют отрезки, соединяющие точки врезки.
В терминах теории графов любой допустимый маршрут, который может быть спроектирован с помощью разработанного комплекса алгоритмов и программ, является гамильтоновым циклом на множестве пунктов обхода. Поиск оптимального гамильтонова цикла является М'-сложной задачей дискретной оптимизации.
Аналогичные по формальной постановке прикладные задачи могут быть сформулированы при построении рациональных коммуникационных сетей, при решении прикладных задач размещения и обслуживания оборудования и т.п.
Для таких трудных с вычислительной точки зрения проблем, один из подходов состоит в том, чтобы ослабить требование глобальной оптимальности
5 результата, заменив исчерпывающий поиск приближенным, что позволит использовать более эффективные алгоритмы. При этом в большинстве случаев ожидается более чем умеренный проигрыш в качестве полученного результата.
При решении поставленной задачи в основном применяются эвристические методы и комбинированные алгоритмы, так как для ее решения на количестве элементов реальных практических задач не существует точных методов, дающих результат за приемлемое время.
Для нахождения приближенного решения задачи в работе было решено использовать модифицированный алгоритм муравьиной оптимизации, обладающий устойчивостью к попаданию в точки локальных экстремумов и способностью постоянно улучшать качество решения. Муравьиная оптимизация успешно используется в различных областях [14, 30, 31, 34, 35, 61-63], в том числе и для оптимизации раскроя [1 - 3].
Способ решения рассматриваемой задачи основан на интеграции технологий искусственного интеллекта, математического программирования и вычислительно-поисковых процедур. Реализация комплекса алгоритмов и программ представляет собой приложение системы AutoCAD.
Цели и задачи работы:
разработка математических моделей, методов и алгоритмов решения оптимизационной задачи маршрутизации;
разработка и исследование оптимизационных алгоритмов построения гамильтонова цикла на множестве отрезков и геометрических объектов, состоящих из отрезков;
развитие современных отечественных систем проектирования.
Методы исследования. При исследовании и решении поставленной в рамках диссертационной работы задачи используются методы геометрического моделирования и проектирования, комбинаторные метаэвристические методы оптимизации, методы математического программирования, математические
модели и методы параметризации, аппроксимации функций, методы вычислительной геометрии и компьютерной графики.
Положения, выносимые на защиту:
1) математическая модель задачи маршрутизации для обхода
геометрических объектов, составленных из отрезков;
модификация алгоритма муравьиной оптимизации для решения задачи маршрутизации;
программное приложение системы AutoCAD, реализующее алгоритм муравьиной оптимизации;
4) численные эксперименты на основе созданного программного
обеспечения.
Научная новизна работы. Данная работа направлена на исследование и развитие бионических принципов, моделей и методов класса муравьиной оптимизации. Основное отличие предлагаемой методики от известных вариантов алгоритмов заключается в использовании дополнительного параметра (коэффициента смежности), позволяющего управлять движением по кусочно-ломаным траекториям и замкнутым объектам. Постановка задачи поиска гамильтоновых циклов на отрезках по сравнению с аналогичными проблемами, исследуемыми зарубежными учеными [50, 59, 60, 64-69], имеет принципиальное отличие, состоящее в требовании включения в гамильтонов цикл отрезка, а не только его концов. Маршрут строится на множестве произвольно ориентированных отрезков.
Новизна предлагаемых решений определяется универсальностью и возможностью адаптации методов решения задачи построения гамильтонова цикла на множестве геометрических объектов, заданных отрезками.
Полученные результаты дают основания полагать, что эффективное решение JVP-сложных задач оптимизации дискретно-непрерывной структуры является возможным посредством интеграции технологий искусственного
7 интеллекта с методами математического программирования и вычислительно-поисковыми процедурами.
. Практическая значимость работы. Полученные результаты диссертационного исследования позволяют предложить эффективные алгоритмы, основанные на бионических принципах, для решения широкого класса задач дискретно-непрерывной структуры. Использование этих алгоритмов при решении проблемы автоматизации подготовки управляющих программ для оборудования термической резки металла с ЧПУ позволяет:
повысить коэффициент использования оборудования;
снизить энергетические затраты на резку металла, увеличить ресурс использования режущего инструмента за счет автоматического выбора оптимального маршрута обхода заготовок;
сократить сроки проектирования;
повысить качество проектных решений.
Программная реализация модифицированного алгоритма муравьиной оптимизации показала значительные преимущества перед часто используемыми на практике эвристическими методами для широкого класса задач маршрутизации.
Достоверность результатов. Разработка математической модели задачи маршрутизации и создание на этой основе алгоритма стало возможным благодаря комплексному использованию теоретических и экспериментальных методов исследования. Решение ряда новых задач теории оптимизации и вычислительной геометрии, поставленных в работе в рамках диссертационного исследования, стало возможным благодаря известным достижениям указанных научных дисциплин и не противоречит их положениям, базируется на строго доказанных выводах фундаментальных и прикладных наук, таких как математический анализ, планиметрия, математическая статистика, теория оптимизации и планирование эксперимента. Созданная методика построения
8 эффективных траекторий с использованием разработанного алгоритма согласуются с опытом их проектирования.
Разработанные новые теоретические и практические решения опробованы экспериментально. Экспериментальные исследования проводились с использованием технической базы Новосибирского государственного технического университета. Результаты экспериментов анализировались и сопоставлялись с известными экспериментальными данными других исследователей. Результаты работы, отраженные в программе автоматического проектирования маршрутов раскроя, прошли техническую экспертизу на предприятии и использованы в экспериментальном проектировании в промышленной системе «Техтран-Раскрой» как составной элемент.
Апробация работы. Основные принципы и подходы для решения рассматриваемой задачи прошли апробацию на нескольких международных, региональных конференциях, обладают научной новизной и актуальностью, могут претендовать на мировой приоритет. Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах:
Всероссийская научная конференция молодых ученых «Наука. Технологии. Инновации», 2004 г, Новосибирск, НГТУ.
Международная конференция по компьютерной графике и ее приложениям Графикой, 2005,2006 гг., Новосибирск.
Российско - корейский международный симпозиум по науке и технологиям, KORUS 2005, Новосибирск, НГТУ.
Международная конференция по компьютерной графике и искусственному интеллекту, 31А'2006, 2006 г, Лимож, Франция.
Международная научно-техническая конференция «Высокие технологии и перспективы интеграции образования, науки и производства», 2006, Ташкент.
9
6) Международная конференция по вычислительной технике и
информационным технологиям, CSIT'2007, 2007, Уфа.
Публикации. По теме диссертации опубликовано 11 печатных работ, в их числе 2 статьи в центральных изданиях, входящих в перечень изданий, рекомендованных ВАК РФ, 1 - в сборнике научных трудов, 8 - в трудах и материалах международных конференций.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников, включающего 74 наименования, и приложения; общий объем составляет 122 страницы основного текста, включая 76 рисунков и 11 таблиц.
Содержание диссертационной работы по главам:
в первой главе диссертации приводится постановка проблемы оптимизации пути обхода отрезков на плоскости, характеристика популярных методов решения оптимизационных задач маршрутизации, обоснование выбранного метода решения;
во второй главе диссертации дана характеристика реализованного алгоритма муравьиной оптимизации с указанием схемы работы алгоритма, проведена оценка вычислительной сложности метода;
- в третьей главе диссертации проведен сравнительный анализ решений
методом колонии муравьев, методом ближайшего соседа и с помощью
случайного поиска; описаны основные параметры метода и их влияние на
работу алгоритма; намечены перспективные направления данного исследования,
средства повышения эффективности применения разработанного алгоритма;
рассмотрен вопрос сходимости метода; выполнена оценка вычислительной
сложности разработанного алгоритма;
- в четвертой главе диссертации представлено краткое руководство
пользователя, описание интерфейса и примеры работы с программным
комплексом.
Основные методы решения задачи построения цепей и циклов на множестве отрезков
В 1978 году финские ученые Лейпала (Leipala) и Невалайнен (Nevalaineri) представили систему управления работой графопостроителем [59]. В качестве исходных данных рассматривался набор отрезков, задаваемых точкам начала и конца (рис. 1.3).
Время работы пера графопостроителя состоит из двух величин: рисование собственно отрезков, а также общее время перемещения между точкой завершения отрисовки предыдущей линии и точкой начала новой. В первом случае перо опущено, во втором - поднято (что является аналогом перемещения режущего инструмента в режиме холостого хода). Неоптимальные перемещения второго типа приводят к потере времени, длина таких перемещений должна быть сведена к минимуму, то есть необходимо найти такую последовательность отрезков, чтобы длина переходов между ними была минимальной. При этом время отрисовки линий не зависит от выбора последовательности рисования элементов.
Если перо должно вернуться в исходную точку, то описываемая задача сводится к трубопроводной задаче, озвученной Лайсгангом (Liesegang) в 1976 году [59]. Рассмотрим ее подробнее.
Пусть задано некоторое множество «труб» (в нашем случае, отрезков). Необходимо построить маршрут, который проходит по каждой трубе таким образом, что общая длина пути минимальна. Лайсганг предлагал использовать метод ветвей и границ для поиска точного решения поставленной задачи. Однако время поиска решения, в этом случае, находится в экспоненциальной зависимости от числа труб. В реальных условиях работы плоттера число отрезков велико, а на время решения наложены жесткие ограничения.
Сходная задача была рассмотрена группой ученых во главе с Фредериксоном (Frederickson) в 1978 [59]. Движения крана по аналогии с движением пера должны осуществляться некоторым предопределенным образом. Кран переносит грузы между фиксированными точками. После разгрузки точку, в которой кран должен поднять новый груз, необходимо выбрать таким образом, чтобы суммарное перемещение крана было минимальным.
Были рассмотрены различные варианты озвученной задачи (в том числе построение замкнутого маршрута, маршрута с фиксированной начальной точкой) и было показано, что все они принадлежат к классу JVP-полных. Таким образом, была признана необходимость разработки приближенных методов решения поставленной задачи.
Дополнительная сложность возникала из-за отсутствия каких бы то ни было ограничений на число отрезков. Однако в последнее время вопросы выделения памяти стоят не так остро, как это было 30 лет назад.
Лейпала и Невалайнен применили метод ближайшего соседа и правило локальных перестановок для улучшения решения. Система управления была описана с помощью FORTRAN. В качестве модели ученые выбрали детерминированный вариант, то есть точки концов отрезков были известны заранее, а также модель с равномерным распределением отрезков на плоскости.
В качестве одного из параметров исследования была выбрана «степень эвристики» N. На некотором шаге выбор осуществлялся из 2N точек - концов отрезков, которые должны быть включены в оставшийся маршрут. На рис. 1.4 представлены результаты решения задачи. Время работы плоттера в зависимости от степени эвристики (N). Опыт проводился на множестве из 100 отрезков, заданных случайным образом.
Как показывает график, при N =\5 увеличение N приводит к резкому сокращению времени работы плоттера. Однако эффект становится незначительным при больших значениях N.
Таким образом, очевидно, что для эффективной работы алгоритма необходимо сокращать пространство допустимых решений.
На рис. 1.5 показаны составляющие времени работы процессора (время генерации множества отрезков, время разработки управляющей программы и стандартное время работы системы, когда записываются значения управляющих символов). Графики показаны для 100 и 200 отрезков. Если вычесть время работы системы, то получится линейная зависимость от степени эвристики N.
При малых значениях N, как отмечают ученые, наблюдается снижение времени работы, поскольку программа управления плоттером сокращает общее число управляющих символов.
Алгоритм выбора последующего отрезка основывался на правиле ближайшего соседа и кратко описывался следующим набором действий.
Пусть S - текущее множество, включающее N отрезков. Выберем из 2N точек (точки концов отрезков) ближайшую к точке текущего положения пера. Нарисуем линию, изменим координаты положение пера, и удалим выбранный отрезок из множества S. Добавим новый отрезок в S и повторим вышеописанную процедуру.
Число отрезков N, рассматриваемое на каждом шаге, называется степенью эвристики. Эффективность решения задачи методом ближайшего соседа можно оценить следующим образом. Если К - число отрезков, равномерно распределенных на участке площадью R, то длина холостого хода (переходов между отрезками): где N- степень эвристики.
Принцип жадности, использованный финскими учеными, применяется и сейчас для множества задач. Наиболее популярны три следующих алгоритма принципа жадности [16]: - метод ближайшего соседа (Nearest Neighbor), - метод включения ближайшего города (Nearest Town), - метод самого дешевого включения (Most Cheap Inclusion).
В методе ближайшего соседа пункты обхода графа последовательно включаются в маршрут, причем, очередная включаемая точка должна быть ближайшей к последней выбранной среди всех остальных, еще не включенных в состав маршрута.
Метод ближайшего города на каждом шаге алгоритма проводит допустимый маршрут по текущему подмножеству точек, уже включенных в маршрут, добавляя к нему новую из числа еще не включенных в маршрут, для которой найдется ближайший сосед из числа точек уже принадлежащих маршруту обхода.
Алгоритмы Хоффманна на графах видимости концов отрезков
Доказательство своих теорем Хоффманн базирует на следующих утверждениях. Пусть L - множество непересекающихся отрезков на плоскости, Vi - множество точек-концов отрезков L, Р - многоугольник, построенный на множестве отрезков L. Многоугольник Р назовем простым, если он составляет часть плоскости, ограниченную простой замкнутой кривой дР, состоящей из отрезков заданного множества. Пусть V(P) циклическая последовательность вершин Р на кривой дР. Если Р является простым многоугольником, дР не пересекает ни один отрезок из L, множество вершин Р совпадает с Vi, тогда Р -гамильтонов многоугольник. Основная лемма звучит так. Для множества L непересекающихся отрезков на плоскости в общем положении и yz - отрезка выпуклой оболочки множества отрезков convi jL) , существует простой многоугольник Р с вершинами из Vi и множество S попарно неперекрывающихся простых многоугольников внутри Р, таких, что 1) yz является стороной Р; 2) для каждого отрезка / є L последовательность вершин многоугольника V(P) включает либо оба конца отрезка /, либо отрезок / лежит внутри области многоугольника / с int(p); 3) для каждого отрезка / є L найдется многоугольник D 3D є S такой, что / с int(l ), либо для всех DES If] int(Z)) = 0; 4) каждый из многоугольников D є S является выпуклым; 5) каждый многоугольник D є S имеет общую сторону с Р, причем эта сторона отлична от .
Очевидно, что на первом шаге, когда Р совпадает с выпуклой оболочкой, выполняется первое условие. Затем, на каждом шаге многоугольник Р и множество S изменяются таким образом, что множество вершин V(P) не уменьшается и свойство 1 остается неизменным. По выполнения первого шага выполнено также условие 2. Разбиение многоугольника Р на несколько многоугольников с помощью диагональных отрезков не приведет к нарушению условия 3. А последующие призваны сохранить и оставшиеся свойства 4 и 5. На каждом этапе происходит изменение многоугольника так, что одно из его ребер заменяется некоторым участком цепочки обхода либо два последовательных ребра заменяются одним.
Для построения гамильтонова многоугольника согласно алгоритму, разработанному Хоффманном, необходимо ввести следующие определения. Хоффманн описывает множество фреймовых многоугольников {frame), обладающих рядом свойств. Для множества L непересекающихся отрезков на плоскости многоугольник Р называется фреймовым (остовным или фреймом), если 1) VLczPuV(P) zVL; 2) дР не содержит ни один из отрезков множества L; 3) каждая вершина v многоугольника Р встречается в V(P) не более чем дважды; стороной многоугольника Р считается отрезок, соединяющий две последовательный вершины V(P); 4) если последовательность вершин такая, что V(p)={...abc...dbe..), тогда оба угла Zeba, Zcbd выпуклые (возможно, что а совпадает с е (а = е) или c = d); 5) если для некоторых вершин abeL aeV{P) и be mt(p) , то вершина а включена в множество V{P) только один раз и лежит на выпуклой оболочке.
Ниже на рис. 1.29 показаны примеры фреймов (а), а также многоугольников, не являющихся фреймовыми из-за невыполнения свойства 4 {а ж, б) или пересечения отрезков (в). (Более толстыми линиями нарисованы заданные отрезки, пунктиром - стороны многоугольников. Буквами обозначены вершины отрезков.)
Если некоторая вершина встречается дважды в V(P), то она является началом и концом цепочки (reflex vertex) и не может быть включена в цепочку в ином качестве. Будем считать такие вершины замыкающими.
Назовем направлением или ориентацией многоугольника (orientation) и(Р) фрейма Р функцию и:У(р)- {-1,\}, заданную для каждой вершины aeV(p), такой, что a, b - концы отрезка из множества заданных, а точка Ь лежит внутри многоугольника abeL,beint(p). Для некоторой вершиныд є V[P) обозначим а+] и а"1 вершины множества V(P), следующие за а против часовой стрелки и в направлении движения часовой стрелки соответственно. Рассмотрим ломаную \Рг Pi Р\) составляющую часть периметра многоугольника, такую, что никакой отрезок L ее не пересекает (рис.1.30 ). Пусть ломаная сагс(ръ рі, рг) будет кратчайшей ломаной между р\ и р3 , причем ни один из концов отрезков не лежит в области, ограниченной замкнутой кривой carc{p],p2,p )[j(p2,p2,p]).
Рассмотрим данную процедуру с позиции построения алгоритма. Входными данными служат фрейм Р, направление и, вершина а є V(p) такая, что abeL и ЬёУ(Р). Пусть с-а" а . Заменим ребро ас дугой abijcarc (b,a,c). При этом для всех вершин р дуги carc{b,a,c) и(р):=и(а). Выполнив эти действия мы получим многоугольник Р . Необходимо отметить, что полученный таким образом многоугольник может оказаться не простым, поскольку некоторые вершины carc{b,a,c) уже могли быть включены в V{P) ранее. Вершина Ъ при таком построении будет замыкающей. Назовем описанную процедуру построением крайнего многоугольника (build cap), а последовательность замыкающих вершин bvb2,...bk, такую, что a,bx,b2,..hk,c цепочка следующих друг за другом вершин V(P), i = \,...,k, conv(abv..bkc)C\ L = 0, - крайней (cap). Замыкающая вершина V(P), не являющаяся крайней, соответственно, называется не крайней. Цепочку a,b ,b2,...bk,c следующих друг за другом вершин фрейма Р назовем клином (wedge), если bx,b2,...bk - крайние вершины Р, причем каждая из них встречается в V(P) дважды. Пример клина показан на рисунке 1.32. Следующим шагом алгоритма, очевидно, является избавление от клиньев. Эта процедура выполняется простой заменой ломаной a,b],b2,...bk,c на дугу ас (рис. 1.32).
Алгоритм поведения муравья в процессе принятия решения
В общем случае вероятность перемещения муравья из точки і в точку у на 7-ой итерации определяется: f Ш-М г /м р ,/,-, 7 sallowed\ р/( Н 1к(0Г-кГ , (2.4) О, в противном случае где allowed - список отрезков ещё не пройденных к-ът муравьем, щ видимость пути, Ту \t) . величина феромона на аугментальной дуге (/,/), а и /? параметры, контролирующие относительный приоритет феромона на пути и видимости следующего отрезка (важность феромона и коэффициент видимости пути соответственно).
Для уменьшения влияния обратной связи и увеличения вероятности нахождения новых решений вводится коэффициент использования знаний до, упомянутый выше. Тогда в качестве последующего отрезка выбирается ближайший, на пути к которому больше феромона: s = max { ЫО} -hyY \ я % .... jeallowedfr , \Z.J) г, в противном случае где q - случайное число на отрезке [0, 1], q0 - параметр баланса между использованием накопленных знаний и исследованием новых решений (О qo 1), г - случайный отрезок, выбранный на основе вероятностей, посчитанных по формуле вероятности выбора (2.4).
Если муравей находится на ломаной, то вместо коэффициента видимости пути используется коэффициент смежности. При увеличении значения коэффициента смежности муравей пытается выстроить путь, не покидая текущий контур. Строго говоря, необходимо заставить муравья пройти весь контур (ломаную) целиком без рассмотрения возможности перехода на другие отрезки. Это значительно ограничит область допустимых решений. Однако в общем случае возможно прерывание обхода контура, поскольку мы не оговаривали ограничение на сквозной проход (рис .2.1).
Значение коэффициента смежности отрезков выбирается таким образом, чтобы нейтрализовать действие механизма обратной связи, то есть, чтобы величина коэффициента была сравнима или превосходила величину феромона на дугах.
При сквозном проходе (рис.2.2) возникает ситуация, когда маршрут пересекает исходные отрезки (ломаные) или аугментальные ребра собственного пути.
Для установления некоторого соотношения между необходимостью соблюдать оба ограничения (запрет на пересечения и сквозное прохождение) оставим муравью возможность рассмотрения переходов к близлежащим отрезкам, не изменяя при этом целевую функцию (учет количества самопересечений, формула (1.2)). af- adjacent force - коэффициент смежности, # - конец отрезка і, ,pj.\ -конец отрезка/ Или s определяется вероятностью р. 0)Ч IkCOr-K.] . (2.7) meallowedk О, в противном случае где VISj = af,j = i + hPi = Pj-i nvism=i af,m = i + l,pi = pm_l
Рекомендуемые значения коэффициента смежности определялись в ходе эксперимента. Благодаря нормализации значений видимости пути и важности феромона коэффициент смежности изменяется в интервале [0, 1]. Теоретически значение коэффициента смежности можно увеличивать, однако на качество решения данная процедура не имеет значительного влияния. В качестве одного из вариантов определения коэффициента смежности использовался полный запрет перехода от контура к близлежащему отрезку.
Таким образом, процесс принятия решения при выборе следующего шага основывается на следующих рассуждениях (рис. 2.3):
Рассмотрим различные варианты работы алгоритма колонии муравьев (табл. 2.2). Поскольку метод включает два критерия для принятия решения (феромон и видимость пути или коэффициент смежности), то возможно сведение к однокритериальнои задаче, когда учитывается лишь один из критериев. Обозначения: а - коэффициент привлекательности пути, /3 -коэффициент видимости пути, qcr уровень использования знаний.
Укрупненная схема работы алгоритма представлена на рис. 2.4. Если отрезок j может быть включен в путь (принадлежит множеству допустимых) Если отрезок j не является частью ломаной, включающей текущее звено Если используются накопленные знания Выбрать отрезок по формуле (2.5) Иначе (накопленные знания не используются) Выбрать отрезок по формуле (2.4) Иначе (муравей движется по ломаной или замкнутой фигуре) Если используются накопленные знания Выбрать отрезок по формуле (2.6) Иначе (накопленные знания не используются) Выбрать отрезок по формуле (2.7) Иначе (все возможные отрезки включены в маршрут)
Исследование различных конфигураций отрезков
Пусть задано множество отрезков. При решении задачи методом со значениями параметров, выбранными по умолчанию (в результате анализа экспериментальных данных), найденное решение будет следующим (рис. 3.6)
Характеристики решения: решение найдено на 553 итерации за время 1 642 ms, длина пути 1 736,5 тт. Количество отрезков - 16. Изменим количество муравьев (табл.3.2).
По умолчанию число муравьев равно числу отрезков. При недостаточном количестве муравьев алгоритм с трудом находит решение, далекое от оптимального, причем время поиска решения велико. При увеличении числа муравьев возникает опасность быстрой стагнации, поскольку количество феромона на дугах становится большим, снижается способность поиска новых решений. Однако на простых конфигурациях этот параметр оказывает не слишком большое влияние на качество решения. Как правило, лучшие решения получаются при задании количества муравьев равным числу исходных точек поиска или не превосходящим его удвоенного значения.
Влияния коэффициента важности феромона.
Поскольку феромон - параметр, дополнительно введенный в качестве оценки привлекательности пути при выборе решений, очень важно исследовать его влияние на качество получаемых решений (табл.3.3). К сожалению, в рамках данного исследования не удалось выявить функциональную зависимость между величиной феромона и видимостью пути. Однако в ходе экспериментов получены сочетания параметров, позволяющие получать наилучшие результаты.
Очевидно, что превалирование параметра важности феромона приведет к ускорению работы алгоритма, однако решение будет недостаточно близко к оптимальному, хотя и попадет в некоторую окрестность оптимальной величины. Возможна также ситуация (при малых значения важности феромона), когда алгоритм входит в области стагнации, новые решения практически не отличаются от уже имеющихся, причем решения далеки от оптимального.
Влияния коэффициента видимости пути.
При доминировании критерия видимости пути (табл.3.4) алгоритм приобретает характер стратегии поиска по принципу жадности, причем поиск осуществляется со всех точек одновременно с учетом вероятностной составляющей. Такой подход целесообразно применять для нахождения локального решения, в частности, для улучшения уже имеющихся маршрутов, либо как начальное решение для эвристических процедур.
На сложных конфигурациях влияние параметра видимости пути более очевидно. Однако уже исходя из представленных данных можно заключить, что без учета коэффициента видимости пути решение будет неудовлетворительным: решения далеки от оптимального, число итераций велико. При значительном увеличении приоритета данного параметра решение близко к лучшему.
Влияние коэффициента локального и глобального испарения.
С помощью обновления феромона осуществляется управление механизмом обратной связи (табл. 3.5 - 3.6). В случае, когда обновление феромона не используется, эффект обратной связи исчезает и алгоритм приобретает характер стратегии вероятностного поиска на основе принципа жадности.
В случае, когда коэффициенты испарения малы, и увеличение феромона на дугах приводит к доминирующему характеру критерия привлекательности пути, алгоритм чаще попадает в области стагнации.
Увеличение коэффициента испарения, безусловно, приводит к тому, что найденные решения практически не влияют на последующий процесс решения. Тем не менее, более важным является сочетание глобального и локального испарений (см. ниже).
Если отдавать предпочтение глобальному испарению феромона, то алгоритм находит решение раньше, однако его величина далека от оптимального. Превалирование локального испарения способствует увеличению числа итераций, однако и качество решений возрастает. Наилучшие комбинации коэффициентов испарения: (0,5, 0,5), (0,1, 0,1), (0,5, 0,1), то есть либо малое испарение, либо незначительное превалирование глобального испарения для увеличения скорости алгоритма.
При больших значениях коэффициента испарения алгоритм практически не использует накопленную информацию.
Вопрос использования накопленной информации, или знаний, решается с помощью специального коэффициента - уровня использования знаний. Рассмотрим его влияние на качество решения (табл.3.8).
