Применение алгоритма муравьиной колонии для построения оптимальной гиперсети

Постановка задачи. Одним из наиболее эффективных методов выбора трассы для прокладки инженерных коммуникаций является гиперсетевой подход, в котором описывается топологическая иерархия проектируемых коммуникаций. Суть гиперсетевого подхода заключается в одновременном использовании двух типов взаимосвязанных структур [1]: первичной и вторичной сетей. В качестве первичной сети понимается математическая или цифровая модель местности (ЦММ), учитывающая особенности заданной территории, а в качестве вторичной — конфигурация проектируемой коммуникации.

Задача выбора маршрута прокладки инженерных сетей включает в себя необходимость поиска оптимальной по критерию минимальности затрат трассы с учетом ограничительных условий, определяемых характеристиками проектируемых сетей и заданной территории. Возможны следующие частные случаи выбора трассы для прокладки инженерных коммуникаций: определить трассы от заданной стартовой точки к заданной конечной точке; определить трассы от заданной стартовой точки к множеству конечных точек; определить трассы от множества стартовых точек к заданному множеству конечных точек. Все эти задачи можно свести к соответствующим задачам в гиперсетях [2].

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

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

Пусть граф возможных трасс описывается графом первичной сети PS = (А", У), а структура проектируемой коммуникации — графом вторичной сети WS = (У С A, R) некоторой гиперсети S [1].

Определение 1. Гиперсеть S = (А, V. R; Р, F₁W) — это математическая модель системы сетевых структур (см. рис. 1), включающей в себя следующие объекты:

А = Д1,Т2: --ч^п) — множество узлов первичной сети;

V = (щ, V2, -J’s) — множество ветвей первичной сети;

R = (7’1,Г2, ...,r_m) — множество ребер вторичной сети;

Р : V -д 2^Л — отображение, сопоставляющее каждому элементу v Е V множество F(u) С А, тем самым отображение Р определяет граф первичной сети PS = (А, У; F);

F : R -Д 2^_s — отображение, сопоставляющее каждому элементу г Е R множество трасс F^Pp образующих простой маршрут в графе PS = (А, У; F), причем семейство 2p_S содержит такие подмножества, маршруты которых составляют связную часть графа PS. Отображение F определяет гиперграф FS = (У, R;Fy Множество всех маршрутов F^r), сопоставляющее каждому ребру г Е R графа WS единственный маршрут в графе PS, назовем вложением графа WS в PS.

Vr Е R W : г —> 2^Р^^^Г^ — отображение, сопоставляющее каждому элементу г Е R подмножество ИЦ?’) С P^F(r)), где P^F^r^ = У — множество вершин в PS, инцидентных маршрутам F(r) С У. Отображение W определяет граф вторичной сети ТУ S = (У, F; ТУ).

Пусть известны /Ц) — длина ветви v Е У графа PS^-, р^г) — длина ребра г Е R графа WS, равная р^ = ^ 1^', ^а1^и) ~ удельная стоимость земли, отведенной под строи- vEFE)

тельство на ветвях v Е У; ЬЦу) — удельная стоимость земляных работ на ветви и Е У для ребра г Е R; с(г) — стоимость приобретения и монтажа коммуникаций г Е R между заданными парами точек; d^^ — стоимость эксплуатационных работ.

Задача заключается в реализации ребра графа WS (прокладке коммуникаций) по соответствующим маршрутам в графе PS таким образом, чтобы функционал

Q(S) = (5271 ‘ аМ + ^2ьЛт ‘1Н + (^^-c^R^d^rH ■ р(г) (1) \1>GV            vEV /           \геГ?            rER / принимал минимальное значение, где 71 и 72 — коэффициенты дисконтирования для стоимостей строительных работ и оборудования соответственно. Коэффициент дисконтирования — это коэффициент для приведения экономических показателей разных лет к сопоставимым по времени величинам. Первое слагаемое в выражении Q^S^ представляет собой стоимость земли, отведенной под строительство, и земляных работ на ветви v Е V графа PS, по которым проходят ребра т Е R графа ЖS', а второе — стоимость приобретения и монтажа коммуникаций и его эксплуатации. Таким образом, модель гиперсети, в отличие от графов, позволяет учесть взаимосвязанную совокупность первичных и вторичных сетей с учетом всех структурных параметров и экономических характеристик проектируемой коммуникации и области размещения.

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

Пусть область П представляет собой проекцию заданной территории на некоторой плоскости. Введем области запрета Q_s,s = 1,2,..., S', такие, что Q_s С Q; Q_s |J Q₉ = ф, sEq

Vs, 9 = 1,2, ...,S заданы своими границами. В качестве областей запрета могут выступать участки, не проходимые для прокладки коммуникаций: овраги, водоемы, заболоченные или лесистые участки и т. д. Кроме того, это могут быть участки социального и сельскохозяйственного назначения: существующие коммуникации, территории промышленных предприятий, населенные пункты, территории оборонных объектов, заповедные зоны и т. д.

Пусть д — некоторый маршрут в графе первичной сети PS. Этот маршрут должен удовлетворять следующим условиям: д С Q — нахождение маршрута внутри исследуемой области; д ^ Q_s, s = 1, 2,..., S, 'Vs — непрохождение маршрута через области запрета. Узлы графа первичной сети PS, попавшие в какую-либо из областей Q_s,s = 1,2, ...,S, изолируются, т. е. весу ветвей, соединяющих данный узел со всеми смежными с ним узлами, присваивается значение бесконечности.

Пусть дДс) — ресурсное ограничение на ветви v Е V графа первичной сети PS для ребра г Е R графа вторичной сети ЖS'. Тогда условие ( 52 71" афф + 52 Ь_ГФФ I • /(у) >  q_y фф означает нецелесообразность прокладки маршрута на участке и G V для ребра г Е R.

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

Теперь определим правила построения множества ребер R вторичной сети ЖS'. Возможность прокладки коммуникаций между заданными парами узлов обычно ограничивается характером рельефа местности — его крутизной. Для этого введем следующее обозначение: а — угол между отрезком в пространстве, соединяющим некоторые пары узлов, и горизонтальной плоскостью Q. Для каждого типа инженерной коммуникации можно ввести следующие дополнительные обозначения: а„_р — предельно допустимый угол прокладывания коммуникаций вверх по склону; адошт k^adowm < 0) — предельно допустимый угол прокладывания коммуникаций вниз по склону; a_Side — предельно допустимый угол прокладывания коммуникаций горизонтально по поверхности склона.

Возможны следующие случаи для выбранного типа коммуникаций: если а ^ аир, то прокладка инженерной коммуникации вверх по склону разрешена, в противном случае — нет; если а > адошт, то прокладка инженерной коммуникации вниз по склону разрешена, в противном случае — нет; если а ^ ДзгЛеЬ то прокладка инженерной коммуникации горизонтально по поверхности склона разрешена, в противном случае — нет.

Пусть qt\r^ — ресурсное ограничение на ребра г Е R графа вторичной сети WS для ветви и Е V графа первичной сети. Тогда условие I ^2 72 ■ c(r) + ^2 ^МД I ' p(r) > 9r(v) veR         тек / означает нецелесообразность реализации ребер г Е R в участках v Е V.

Невыполнение одного из условий правила построения ребер вторичной сети влечет за собой нецелесообразность выбора маршрута прокладки на участке и Е Пдля данного типа инженерной коммуникации.

Тогда задача заключается в построении на множестве узлов ¥ некоторого графа WS = (У С X, R), имеющего конфигурацию, соответствующую проектируемой коммуникации, и такого отображения F*(r) С F(r) ребер г Е R графа ЖS' по соответствующим маршрутам у £ У в графе PS, при которых функционал (1) принимает минимальное значение при выполнении условий правила построения элементов первичной и вторичной сети.

Муравьиный алгоритм. Для поиска оптимального маршрута между заданными парами вершин в графе первичной сети PS для реализации ребер графа вторичной сети WS можно использовать муравьиные алгоритмы [4], адаптированные к прикладной задаче трассировки инженерных коммуникаций. Моделирование поведения муравьев связано с распределением феромона на тропе — ветви графа первичной сети. При этом вероятность включения ветви в маршрут отдельного муравья пропорциональна количеству феромона на этой ветви, а количество откладываемого феромона пропорционально длине маршрута. Чем короче маршрут, тем больше феромона будет отложено на его ветвях, следовательно, большее количество муравьев будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости — большинство муравьев двигается по локально оптимальному маршруту. Избежать этого можно, моделируя отрицательную обратную связь в виде испарения феромона. При этом если феромон испаряется быстро, то это приводит к потере памяти колонии и забыванию хороших решений, с другой стороны, большое время испарения может привести к получению устойчивого локального оптимального решения.

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

Муравьи имеют собственную „память". Поскольку каждая вершина может быть по сещена только один раз, то у каждого муравья есть список уже посещенных вершин — список запретов Т^. Используя этот список, муравей гарантированно не попадет в одну и ту же вершину графа первичной сети PS дважды. Ясно, что список запрета возрастает при совершении маршрута и обнуляется в начале каждой итерации алгоритма. Обозначим через У^ список вершин первичной сети PS, в которые необходимо попасть муравью к, находящемуся в вершине г. Понятно, что У^. является дополнением к списку табу.

Муравьи обладают „зрением". Видимость — это локальная статическая информация, выражающая желание попасть к вершине Vj из вершиныщ. Видимость — величина, обратная расстоянию между вершинами щ и щ: т]^ = ——, где D.^ — расстояние между вершинами щ и ц^.

Муравьи обладают „обонянием¹¹ — они могут улавливать уровень феромона, подтверждающий желание попасть к вершине 13 из вершины г₇; на основании опыта других муравьев. В отличие от видимости, уровень феромона является более глобальной и динамичной информацией — она изменяется после каждой итерации алгоритма, отражая приобретенный муравьями опыт. Количество виртуального феромона на ветви Vij = (гущД на итерации t обозначим через Тц^).

Важную роль в муравьиных алгоритмах играет вероятностно пропорциональное правило, определяющее вероятность перехода А>го муравья из вершины щ в вершину Vj на t-й итерации:

Pijk^ = -^(^--- еСЛИ j у levt,k

P-tpk^ = 0, если з ^ Vt,k где а, (3 — параметры, задающие веса уровней феромона. При а = 0 будет выбрана ближайшая вершина, что соответствует жадному алгоритму в классической теории оптимизации. Если (3 = 0, тогда работает лишь феромонное усиление, что влечет за собой быстрое вырождение маршрутов к одному субоптимальному решению. Заметим, что правило (2) определяет лишь вероятности выбора той или иной вершины. Правило (2) не изменяется в ходе алгоритма, но у двух разных муравьев значение вероятности перехода будет отличаться, т. к. Pij.k^ — функция от V^k — списка еще не посещенных вершин муравьем к. Другими словами, муравьи имеют разный список разрешенных вершин.

Пройдя ветви и^ = (щ,щ), муравей к откладывает на них некоторое количество феромона, которое должно быть связано с оптимальностью сделанного выбора. Пусть T_k(t) есть маршрут, пройденный муравьем к на Кой итерации, L_k(t) — длина этого маршрута, a Q — регулируемый параметр, значение которого выбирают вместе с длиной оптимального маршрута. Тогда откладываемое количество феромона муравьем к на Кой итерации может быть определено в виде

Ar«*(t) = (      М^€Т‘№^->

[ О, (к,щ) ^ T_k(t\

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

тД£ + 1) = (1-р)-Ту(Д + АтуД),                     (3)

m где АтуД) = Е ^Tij,k(t)i тп. — количество муравьев в колонии. fc=i ’

В начале алгоритма количества феромона на ребрах принимается равным небольшому положительному числу Щ-

Дополнительная модификация алгоритма может состоять в ведении так называемых „элитных11 муравьев, которые усиливают ребра наилучшего маршрута, найденного с начала работы алгоритма. Обозначим через Т* наилучший текущий маршрут, через L* — его длину. Тогда если в колонии есть е элитных муравьев, то ребра маршрута получат дополнительное количество феромона

/\.T_e = e-Q/L*. (4)

В настоящей работе общее количество муравьев равно количеству вершин вторичной сети, из которых необходимо проложить маршрут до заданных вершин, и остается постоянным на протяжении выполнения алгоритма. Таким образом, на начальном этапе алгоритма муравьи размещаются в вершинах вторичной сети, из которых необходимо проложить оптимальный маршрут до заданных вершин. Муравьи прокладывают маршрут в порядке, определяемом последовательностью по метрикам 1 и 2, приведенным в работе [5]. Приведем основные правила и определения для вычисления метрик 1 и 2.

Определение 2. Если Vr Е V b_T^ = const, то заданная территория является однородной, в противном случае она называется неоднородной. Граф первичной сети, соответствующей однородному случаю, будем обозначать Р8_ОД., а неоднородному — Р8_неод..

Следует отметить, что если Vv 6 V ЬДи) = const, то маршрутом графа Р8_0Д. для реализации ребер т Е R графа WS = (У, R) может быть любое направление (все направления равнозначны), поскольку в этом случае стоимости строительных (земляных) работ по всем ветвям графа Р8_ОД. одинаковы.

Определение 3. Гиперсеть, построенную путем вложения графа VES в Р8_0д. (Р8_НСОД.), назовем однородной (неоднородной) и обозначим через 8_ОД. (8_НСОДУ Ясно, что кратчайший маршрут для ребра г Е R графа TES в графе Р8_0д. равен евклидову расстоянию между вершинами х, у графа Р8_ОД..

Для построения списка ребер потребуются следующие понятия.

Метрика 1: для каждого ребра Tk Е R вычислим

Ц’>.^=Е Ди^Л^Пю). (5) j где: к Д j, % = Р^т^ и Vj = Р(ру), т. е. множество ветвей графа Р8неод_, по которым проходят ребра Тк и Tj соответственно. Такая метрика позволяет определить, насколько ребра г Е R расходятся друг от друга при реализации в графе PSKCO!V Далее производится улучшение начальных решений путем перереализации в графе УбДод., начиная с самого удаленного ребра.

Метрика 2: для каждого ребра /д Е R вычислим pwn - |(иущ)\(ц,гкд)|. (в)

где Vk = Р(тк) — множество ветвей графа Р8_неод., У_к^д' = Р^^д'^ — множество ветвей графа Р8_0д., по которым проходят ребра г к и х_к^д' соответственно. Такая метрика позволяет выяснить, насколько расходятся маршруты Vk = Р^Гк) и У_А^ОД' = ЕДД') в графах Р8_НСОД. и Р8_0д. для ребер Хк и х°_к^д' соответственно. Для достижения быстрой сходимости первичного приближения к оптимальному процессу перереализаций необходимо начать с ребра, наиболее „удаленного" от всех по данной метрике.

Таким образом, для улучшения начального решения путем перереализаций ребер х Е R графа IES' по новым трассам в обоих случаях надо упорядочить по убыванию метрики, в результате чего получим список ребер {гД, г = 1, ...,т.

Правила построения гиперсети S. Таким образом, каждую трассу в первичной сети PS для прокладки ребер вторичной сети WS протягивают муравьи, которые характеризуются списком запрета Т^, состоящим из узлов графа первичной сети PS, которые муравьи т уже посещали. Множество муравьев образует колонию, подчиняющуюся некоторым поведенческим правилам, определяемым составленным нами набором правил трассировки (ПТ): ПТ1 — выбора направления прокладки локальной трассы из вершины Ui в вершину Uj графа первичной сети PS; ПТ2 — объединения трасс одной связывающей сетью инженерных коммуникаций; ПТЗ — перехода с тупиковых трасс; ПТ4 — отсечения глухих ответвлений.

ПТ1:

ЕСЛИ (смежная вершина j ф Т^)

И (величина [тд(^)]“ • фу]/3 максимальна для всего множества допустимых направлений) ТО (выбрать ветви (г, j) и добавить; в

Формализованная запись ПТ1 имеет вид

{(м)1ЖЛ j ^ Г^н, VijW ‘ Н₃"\^Р "^ шах} .

Величина т^ определяется по следующей формуле

Пч = у---------------------------г-----------------------------------\-------' (⁷)

Е 71 ' Ф’г^ + Е Ф(Еу) • 1И + Е 72 • Фу) + Е ФФ I • P^ij) уг’уЕУ             ryEY      У            yryGR            ^rij^R      У

ПТ2:

ЕСЛИ (муравей к достиг трассы, проложенной муравьем к')

ТО (трассы муравьев к и к' объединяются)

И (муравей к удаляется из колонии).

ПТЗ:

ЕСЛИ (не существует ветви (г, j), которая может быть добавлена на текущем шаге к Т^) ТО (муравей перемещается в выбранный случайным образом узел на проложенной им трассе).

ПИЗ позволяет муравью выбраться из тупика в случае попадания в таковой.

ПТ4:

ЕСЛИ (вершина г графа первичной сети PS принадлежит единственной ветви (г, У), входящей в трассу)

И (вершина г не является частью трассы)

ТО (ребро (г, У) удаляется из множества ребер трассы).

Тем самым по предложенной схеме можно построить гиперсеть S, удовлетворяющую условию (1) в соответствии с правилами построения трассы ПТ1 ПТ4.

Модифицированный алгоритм муравьиной колонии для построения S. Первичное приближение:

Шаг 1.1. Ввод значений параметров элементов PS и WS , т. е.: 1(и\ р(г), а(у), Ф(у), с(т),

Шаг 1.2. Построить гиперсети 8_ОД. и <9_Нсод. с помощью: а) алгоритма Флойда; б) „жадного“ алгоритма;

Муравьиный алгоритм (улучшение):

Шаг 2.1. Инициализация параметров алгоритма а, /3, е, Q;

Шаг 2.2. Для всех ветвей первичной сети вычислить р,у по формуле (7), инициализация начальной концентрации феромона;

Шаг 2.3. Размещение муравьев в вершинах вторичной сети, из которых необходимо проложить оптимальный маршрут до заданных вершин;

Шаг 2.4. Присвоить j := 1; обозначить через S^ гиперсеть, построенную па ; й итерации; положить б'нсод. = S^j и 5'од. = S^j-1 для всех j ^ 2;

Шаг 2.5. Вычислить по формулам (5) и (6): а) метрику 1; б) метрику 2.

Шаг 2.6. Если выбрана метрика 1 или 2, то упорядочить ребра г Е R по убыванию величин p(r_k; г^ или ^(г/гД’Д') и присвоить муравьям номера г = 1,2, ...т; г := 1;

Шаг 2.7. Выбрать i-ого муравья и построить для него маршрут по правилу (2) с учетом ПТ1 ПТ2. Присвоить i := г + 1; если г < т, то перейти на Шаг 2.7.;

Шаг 2.8. Вычислить Q^Y Если Q^S^ = Q^S^Y ^то псевдооптимальная гиперсеть S построена, иначе j := j +1 ; обновить следы феромона на ветвях первичной сети (3) и (4). Переход на Шаг 2.5.

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

Выводы. Приведены основные правила построения гиперсети для задачи прокладки инженерной коммуникации на заданной территории, включающие правила построения множества вершин X и ветвей V первичной сети PS и множества ребер R вторичной сети WS.

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

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