Материал: 2426

1. Задание численных значений исходных данных: sнач=(xн0, yн0,

zн0, γн0, ωн0); sкон=(xк0, yк0, zк0, γк0, ωк0); { Rig }; imax; jmax; kmax; lmax; mmax;

[YПР]; rкол; α; β; er; G; cγω; u; [T]; δopt; lзап_г; lзап_в. Параметры соответствуют описанным при постановке задачи в разделе 3.1, за исключени-

ем следующих собственных параметров алгоритма роевого интеллекта, задаваемых эмпирически: rкол – количество независимых агентов; α и β – весовые относительные коэффициенты значимости феромона и видимости; G – количество итераций алгоритма роевого интеллекта; [T] – матрица феромонов (с начальными постоянными значениями уровня); er – количество элитных агентов.

2. По методике, изложенной в разделе 3.4, формируется массив [Ymin] гиперповерхности минимальных значений вертикальных координат условного центра груза с учетом его угловых координат:

Ymin(i,k,l,m), i [1; imax]; k [1; kmax]; l [1; lmax]; m [1; mmax].

3. Используя вложенные циклы по i, j, k, l, m, определяющие координаты x, y, z, γ, ω соответственно, c использованием массива [Ymin] гиперповерхности минимальных значений вертикальных координат условного центра груза с учетом его угловых координат формируется

квадратная матрица смежности вершин графа A=[ai1,j1]ing1, j1=1 размером ng×ng, элементы которой равны:

Причем по (3.81) проверяются только смежные с текущей вершины, поскольку перемещение осуществляется только в определенные вершины-преемники, смежные с текущей:

i1=m∙lmax∙kmax∙jmax∙imax+l∙kmax∙jmax∙imax+k∙jmax∙imax+j∙imax+i; j1=mp∙lmax∙kmax∙jmax∙imax+lp∙kmax∙jmax∙imax+kp∙jmax∙imax+jp∙imax+ip; (3.82)

ip [i–1; i+1]; jp [j–1; j+1]; kp [k–1; k+1]; lp [l–1; l+1]; mp [m–1; m+1].

Отсутствие дуги подтверждается в случае, если условие (3.55) не выполняется хотя бы для одной из двух точек: i1 с индексами координат i, j, k, l, m или j1 с индексами ip, jp, kp, lp, mp.

Остальные элементы матрицы [A] принимаются равными 0. Матрица смежности [A] полностью определяет структуру графа с учетом геометрии препятствий в рабочей области, про которые принято до-

110

пущение об их неподвижности, и геометрии объекта (точек (Rg)ig ,

ig [1; cг]).

4. Алгоритм роевого интеллекта состоит в последовательности итераций g1, g2, …, G, на каждой из которых rкол агентов независимо друг от друга совершают полный цикл движения из sнач в sкон, двигаясь только через смежные вершины. Выбор вершины sj1 для перехода в нее отдельного агента из текущей вершины si1 осуществляется при помощи вероятностного правила на основе двух компонент – видимости ηi1,j1 и уровня феромонов τi1,j1, которые ассоциированы с вершинами, смежными с текущей.

Каждая дуга (si1, sj1) Nr имеет весовой коэффициент ηi1,j1. В терминах традиционного алгоритма роевого интеллекта, разработанного для решения задачи коммивояжера, ηi1,j1 – это видимость между вершинами si1 и sj1. Это величина, обратная значению целевой функции

[62, 85, 110, 199, 217]:

где Li1,j1 – значение целевой функции между вершинами si1 и sj1, опре-

деляемое по (3.18) (СВД); i1 [1; ng]; j1 [1; ng].

Предложен и исследован на применимость другой способ определения видимости ηi1,j1 для вершины sj1, смежной с текущей рассматриваемой вершиной si1. Видимость предлагается определять как предполагаемое (прогнозируемое) значение целевой функции между смежной вершиной sj1 и конечной вершиной sкон без учета препятствий. Данный подход используется в эвристических алгоритмах поиска кратчайшей траектории на графах, в частности в алгоритме А* и его модификациях, и доказал свою эффективность [74, 175]. «Жадная» эвристическая функция расстояния до ближайшего соседа (3.18) из классического алгоритма роевого интеллекта заменяется эвристической функцией оценки предполагаемого расстояния до цели:

Li1, j1 = (xj1 -xк0)2 +(yj1 -yк0)2 +(zj1 -zк0)2 +cγω ×(γ j1 -γк0)2 +(ωj1 -ωк0)2 . (3.84)

Для работы алгоритма используются две квадратные матрицы:

видимости N=[ηi1,j1]ing1, j1=1 и феромонов T(g)=[τi1,j1]ing1, j1=1, где τi1,j1(g) – количество феромонов на дуге (si1, sj1) на итерации g. В начальный момент времени все элементы матрицы феромонов T принимаются равными некоторому постоянному малому положительному значению.

111

Рис. 3.18. Возможные состояния-«преемники» для текущего состояния груза

впространстве: а – пространственный вид; б – вид сзади; в – вид сбоку;

г– вид сверху; д – углы поворота

Матрица видимости [N] получается путем умножения соответствующих значений целевой функции (3.18) между текущей и всеми смежными вершинами по прямой либо между всеми смежными и ко-

112

нечной вершинами по прямой (3.84) без учета препятствий на соответствующие элементы матрицы смежности [A] (3.81):

Для практической реализации алгоритма предлагается использовать подходы из области искусственного интеллекта. Формализуем функцию определения «преемника» для произвольного состояния объекта [175]. Отдельный агент перемещает груз по узлам графа на равномерной сетке. В соответствии с принятым при постановке задачи расположением осей неподвижной системы координат приращение индекса i (координаты x) на единицу целесообразно на каждом шаге агента, т.к. уменьшает расстояние до цели и общее число шагов. Остальные 4 координаты груза могут как увеличиваться так и уменьшаться на один линейный или угловой шаг, или же оставаться неизменными (рис. 3.18).

Для каждой вершины графа в общем случае получим Fпр=(qv)wv вершин-«преемников», где qv=3 – число вариантов выбора по отдельной координате; wv=4 – количество координат, допускающих многовариантность при выборе преемника. В нашем случае Fпр= = (qv)wv =34=81. Однако, учитывая, что некоторые вершины графа непроходимы вследствие пересечения груза с препятствиями, общее число «преемников» Fпр для каждой конкретной вершины может быть меньше 81. В некоторых пространственных состояниях число вер- шин-«преемников» может быть равно 0, в этом случае путь тупиковый, он убирается из рассмотрения.

Вероятность перехода отдельным агентом из текущей вершины si1 в смежную вершину sj1 определяется по известному правилу [199,

217]

где α и β – весовые относительные коэффициенты значимости феромона и видимости соответственно, α+β=1,0.

4.1. Для реализации выбора отдельной вершины из списка смежных с текущей вершин одномерный вектор вероятностей Pi1,j1, j1 [1; u] преобразуется в одномерный вектор сумм вероятностей σj1, элементы которого определяются следующим образом:

113

Компоненты вектора сумм вероятностей σj1 представляют собой последовательность монотонно возрастающих чисел со значениями в интервале [0,1]. Последний компонент вектора сумм вероятностей имеет значение σu=1. Затем при помощи генератора случайных чисел получается число Rand в интервале [0,1] с равномерным законом распределения. Вершина-«преемник» определяется как компонент вектора сумм σj1, ближайший меньший к Rand:

где – знак логического умножения (конъюнкции).

4.2. При достижении индексом i (индекс координаты x), который детерминированно увеличивается на 1 при каждом шаге агента, значения (imax–1), построение пути агентом завершается. После того, как на итерации g построен путь Sr(g) для отдельного агента колонии с номером r (r [1; rкол]), определяется длина этого пути как сумма функций стоимости всех дуг вида (3.18), входящих в данный путь:

4.3. После нахождения путей перемещения для всех rкол агентов колонии из совокупности путей {S1(g), S2(g),…, Srкол (g)} выбирается путь с минимальным значением функции стоимости пути на данной итерации алгоритма g:

Последовательность вершин Sr(g) в описываемой реализации представляет собой матрицу размером [imax´4], в каждой строке которой хранятся индексы j(i), k(i), l(i), m(i) вершины пути, имеющей индекс i.

4.4. Затем длина оптимального пути на данной итерации L*(g) сравнивается с текущим значением длины глобального оптимального

114