Документ: 2426, страницы 116-120 | Студенческое хранилище

Последовательность вершин S* глобального оптимального пути длиной L* сохраняется и при уменьшении значения L* по (3.91) также обновляется.

4.5. После завершения каждой итерации происходит обновление феромона на всех дугах графа по известной зависимости [199, 217]

τi1, j1(g +1) = (1- p f )×τi1, j1(g)+ Dτi1, j1(g),	(3.92)
где pf – коэффициент испарения феромона, p f Î[0,1];	i1 [1; ng];
j1 [1; ng].

Dτi1, j1(g) =	rкол
Dτi1, j1(g) =	å Dτi1, j1,r (g);
	r=1
ìQ Lr (g)	если (i1, j1)Î Sr (g);
Dτi1, j1,r (g)= í0 если	(i1, j1)Ï S	r	(g),
î		r

(3.93)

(3.94)

где Sr(g) – последовательность вершин графа, пройденных агентом r на итерации g; Lr(g) – величина целевой функции (длина пути, пройденного агентом r) на итерации g; Q – постоянная.

4.6. Уровень феромона на ребрах глобального оптимального пути длиной L* после каждой итерации дополнительно увеличивается на величину [62, 85, 110, 199, 217]

Dτ	e	(g)= e ×Q L* ,	(3.95)
	e	r

где er – количество элитных агентов.

5. Цикл завершается после выполнения заданного числа итераций: g≥G. После этого выполняется локальная оптимизация лучшей найденной траектории S* глобального оптимального пути L* с учетом препятствий рабочей области по методике, изложенной в разделе 3.5, на этом завершается работа алгоритма.

Детализированная блок-схема модифицированного алгоритма роевого интеллекта для пяти учитываемых обобщенных координат груза в последовательном исполнении приведена на рис. 3.19.

Распараллеливание модифицированного алгоритма роевого ин-

теллекта. При разработке параллельных алгоритмов и многопоточных приложений на их основе внимание в первую очередь уделяется той части задачи, выполнение которой занимает наибольшее время [8, 85].

115

	Пуск	1		2
	Ввод исходных данных: sнач=(xн0,yн0,zн0,γн0,ωн0); sкон=(xк0,yк0,zк0,γк0,ωк0); { R		};	2
			};
		ig
	imax;jmax;kmax;lmax;mmax; [YПР]; rкол; α; β; er; G; cγω; Gr; u; [T]; δopt; lзап_г; lзап_в			3
				3
	Построение массива гиперповерхности [Ymin] по методике раздела 3.4			4
				4
Формирование матрицы смежности [A] с использованием массива гиперповерхности
	[Ymin] по (3.81)
				5

Вычисление ассоциированных расстояний Li,j по (3.18) или (3.84). Вычисление мат-

рицы видимости [N] по [A] и Li1,j1 по (3.85). Задание L*=∞. Вычисление iнач, jнач, kнач, lнач, mнач по (3.54). Положить i(1)=iнач; j(1)=jнач; k(1)=kнач; l(1)=lнач; m(1)=mнач

g=1:G

6

22

7

19

r=1:rкол

Выбор пути, оп-

тимального на

Вычисление дли-

i=2:(imax–1)

8

данной итерации

ны пути Lr(g)

*

агента r по (3.89)

L (g) по условию

9

(3.90)

nm=0

20

23

Генерация слу-

10

*

dj=–1:+1

чайного числа

Сравнение L (g) и

11

L*, обновление L*

Rand в интервале

по (3.91); обнов-

j(i)=j(i–1)+dj;

[0;1]

Ограничения: j(i)£jmax; j(i)³1

21

ление последова-

Определение

тельности вершин

12

dk=–1:+1

индексов j(i),

глобального оп-

13

k(i), l(i), m(i)

тимального пути

k(i)=k(i–1)+dk;

новой верши-

S*; обновление

Ограничения: k(i)£kmax; k(i)³1

ны пути Sr(g)

феромона по

агента r по

(3.92) и (3.95)

24

dl=–1:+1

14

(3.88)

15

Локальная опти-

мизация лучшей

l(i)=l(i–1)+dl;

найденной траек-

Ограничения: l(i)£lmax; l(i)³1

тории S* гло-

16

dm=–1:+1

бального опти-

17

мального пути L*

m(i)=m(i–1)+dm; nm=nm+1;

по методике раз-

Ограничения: m(i)£mmax; m(i)³1

дела 3.5

18

25

Вычисление P(nm) по (3.86) и

σ(nm) по (3.87) для смежной с те-

Вывод резуль-

татов: S*, L*

кущей вершины с индексами i, j,

26

k, l, m

Останов

Рис. 3.19. Блок-схема последовательного алгоритма роевого интеллекта для пяти учитываемых обобщенных координат груза

116

	Пуск	1		2
				2
	Ввод исходных данных: sнач=(xн0,yн0,zн0,γн0,ωн0); sкон=(xк0,yк0,zк0,γк0,ωк0); { R		};
		ig
	imax;jmax;kmax;lmax;mmax; [YПР]; rкол; α; β; er; G; cγω; Gr; u; [T]; δopt; lзап_г; lзап_в			3
				3

	Построение массива гиперповерхности [Ymin] по методике раздела 3.4
				4
Формирование матрицы смежности [A] с использованием массива гиперповерхности
	[Ymin] по (3.81)

5

Вычисление ассоциированных расстояний Lij по (3.18) или (3.84). Вычисление мат-

рицы видимости [N] по [A] и Li1,j1 по (3.85). Задание L*=∞. Вычисление iнач, jнач, kнач, lнач, mнач по (3.54). Положить i(1)=iнач; j(1)=jнач; k(1)=kнач; l(1)=lнач; m(1)=mнач

g=1:G

6

10

Выбор пути, оп-

7

9

тимального на

8

Независи-

данной итерации

мый поиск

...

мый поиск

L*(g) по условию

пути аген-

(3.90)

том r=1

том r=2

том r= rкол

11

Сравнение L*(g) и L*, обновление L* по (3.91); обновление последовательности вершин глобального оптимального пути S*; обновление феро-

мона по (3.92) и (3.95)

			12
14	13		12
14	13	Локальная оптимизация лучшей траектории S*
Останов	Вывод резуль-	глобального оптимального пути L*
	татов: S, L	по методике раздела 3.5
		по методике раздела 3.5

Рис. 3.20. Блок-схема распараллеленного алгоритма роевого интеллекта (затемнены блоки, выполняемые параллельно) для пяти учитываемых обобщенных координат груза

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

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

117

висимо от других; обновление следа феромона от всех агентов на текущей итерации.

	…							12
		1						12
		1				Вычисление дли-
	i=2:(imax–1)						ны пути Lr(g)
		2				агента r по (3.89)
	nm=0	2						13
	nm=0
	dj=–1:+1	3			Генерация слу-
	dj=–1:+1		4		чайного числа ω
			4		в интервале [0;1]
	j(i)=j(i–1)+dj;				в интервале [0;1]			14
	j(i)=j(i–1)+dj;
Ограничения: j(i)£jmax; j(i)³1							Определение
							индексов j(i),
	dk=–1:+1		5				индексов j(i),
			5				k(i), l(i), m(i)
				6			k(i), l(i), m(i)
				6			новой верши-
	k(i)=k(i–1)+dk;						новой верши-
	k(i)=k(i–1)+dk;						ны пути Sr(g)
Ограничения: k(i)£kmax; k(i)³1							ны пути Sr(g)
Ограничения: k(i)£kmax; k(i)³1							агента r по
	dl=–1:+1		7				(3.88)

			8
			8
	l(i)=l(i–1)+dl;
Ограничения: l(i)£lmax; l(i)³1

9

dm=–1:+1

10

m(i)=m(i–1)+dm; nm=nm+1;

Ограничения: m(i)£mmax; m(i)³1

Вычисление P(nm) по (3.86) и11 σ(nm) по (3.87) для смежной с текущей вершины с индексами i, j, k, l, m

…

Рис. 3.21. Блок-схема выполняемого параллельно kernelядра алгоритма роевого интеллекта для пяти координат, описывающих положение груза

Анализ программной реализации описанного выше последовательного алгоритма, учитывающего 5 координат, определяющих положение груза в пространстве, показал, что суммарное время выполнения подэтапа 2-го этапа, заключающегося в последовательном независимом поиске пути агентами колонии, составляет в среднем около 86 % от общего времени выполнения всей программы. В то же время данный блок задачи, в отличие от всех остальных, является информационно независимым.

118

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

Блок-схема распараллеленного в соответствии с приведенным подходом алгоритма роевого интеллекта, учитывающего 5 координат, приведена на рис. 3.20, 3.21.

В соответствии с законом Амдала (Amdahl) ускорение Sпр процесса вычислений при использовании pпр параллельных процессов ограничивается величиной [8]

Sпр ≤		1		,	(3.96)
	fпо + (1	− fпо )
			pпр

где fпо – доля последовательных операций в рассматриваемом алгоритме.

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

Согласно приведенной формуле (3.96), возможно 7-кратное ускорение по сравнению с последовательным алгоритмом роевого интеллекта (верхняя оценка ускорения Sпр≈7), что подтверждено результатами вычислительных экспериментов.

Вычислительные реализации разработанных последовательной и параллельной модификаций алгоритма роевого интеллекта и описанной методики на его основе в средах Microsoft Visual C++ и MATLAB показали работоспособность и эффективность алгоритмов роевого интеллекта для решения поставленной задачи. Для распараллеленного алгоритма были разработаны программные реализации с использованием гибридной технологии: массивно-параллельных вычислений на графических процессорах Compute Unified Device Architecture (NVIDIA CUDA) совместно с библиотекой параллельного программирования систем с распределенной памятью Message Passing Interface (MPI) и открытого стандарта параллельного программирования многопоточных систем с общей памятью Open Multi-Processing (OpenMP).

119

Материал: 2426

Смотрите также: