Роевой алгоритм планирования работы многопроцессорных вычислительных систем

Размещено на http: //www. allbest. ru/

Южный федеральный университет, Таганрог

Роевой алгоритм планирования работы многопроцессорных вычислительных систем

Б.К. Лебедев, О.Б. Лебедев, Е.О. Лебедева

Аннотация

В работе рассматривается задача составления плана выполнения комплекса программ, в многопроцессорных вычислительных системах (МВС). МВС состоит из нескольких параллельно работающих процессоров. На вход МВС поступает множество независимых потоков заявок (программ), которые необходимо распределить между процессорами. Вычислительная система может состоять как из идентичных, так и из различных по производительности процессоров. Учитывается время переключения между различными классами заявок, поступающих на процессор. Решение задачи планирования представляется как задание распределения заявок по процессорам, и определение очереди заявок на обслуживание процессором. Оптимизация при планировании в случае многоуровневой очереди заключается в минимизации времени выполнения всех заявок. В основу работы представленного алгоритма положены механизмы адаптивного поведения муравьиной колонии. Временная сложность этого алгоритма зависит от времени жизни колонии (число итераций), количества исполнителей и числа работ.

Ключевые слова: многопроцессорная система, планирование, многоуровневая очередь, распределительная задача, оптимизация, муравьиный алгоритм.

роевой алгоритм планирование многопроцессорный

Введение

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

Имеется в виду, что выполняемая программа представляется в виде неделимого целого, в связи, с чем прерывание ее работы и передача на исполнение другому процессору, в общем случае, запрещены. Каждая программа может выполняться на любом из процессоров, при этом время исполнения программы зависит от ее сложности и от быстродействия процессора. Длительность выполнения программы считается заранее известной величиной. Если для исполнения программы требуются данные получаемые в результате работы другой программы, то на множестве программ задается отношение порядка следования. В противном случае, программы считаются независимыми. Таким образом, требуется наилучшим по быстродействию или равномерности загрузки образом спланировать выполнение комплекса программ на заданном множестве процессоров, а в случае наличия связи между программами, также определить последовательность их исполнения на каждом процессоре. Рассмотренная задача планирования вычислительных процессов в многопроцессорных и многомашинных комплексах является минимаксной распределительной задачей (РЗ) теории расписаний.

Российские и зарубежные ученые разработали большое число алгоритмов и методов решения распределительных задач различающихся как эффективностью, так и областью применения. Поскольку РЗ принадлежат к классу NP-полных задач, разработка эффективных алгоритмов их решения по прежнему остается актуальной проблемой теории расписаний. Разработанные методы решения распределительной задачи принято разделять на два больших класса: точные и приближенные. Среди существующих известных и эффективных точных методов решения РЗ наибольшее распространение получили алгоритмы, построенные по схеме метода ветвей и границ (МВГ) [3]. Существенным недостатком метода ветвей и границ является экспоненциальное увеличение сложности решения относительно размерности РЗ. В ряде работ [4] предлагаются подходы, позволяющие сократить комбинационную сложность алгоритмов, построенных по схеме метода ветвей и границ [2]. Особенностью метода ветвей и границ является то, что всегда существует вероятность полного перебора и необходимы достаточно большие временные затраты, особенно при решении задач повышенной размерности.

В связи с этим широкое распространение получили приближенные методы, ориентированные на получение некоторого приемлемого или допустимого решения [5;6]. Достоинство таких методов состоит в высокой скорости решения, характеризующиеся полиномиальной или, даже, линейной зависимостью от размерности задачи. К числу недостатков следует отнести невысокую точность методов данного класса. К числу наиболее распространенных приближенных методов относятся так называемые списочные и эвристические методы. Обладая в основном, линейной сложностью решения относительно размерности задачи, списочные методы крайне эффективны с точки зрения времени решения РЗ. С другой стороны, отклонение получаемых решений от оптимального значения может достигать 30% , что часто не удовлетворяет предъявляемым требованиям к решениям. Высокая трудоемкость точных методов и низкая эффективность приближенных списочных методов резко снизили их практическое применение. В связи с этим большая часть разработок была направлена на применение эвристических подходов. Анализ существующих алгоритмов (последовательных, итерационных и т.д.), приведенный в [5-7] показывает, что для разработки более эффективного алгоритма, который отвечает предъявляемым современным требованиям, необходимы новые технологии и подходы. В последние годы интенсивно разрабатывается научное направление, объединяющее математические методы, в которых заложены принципы природных механизмов принятия решений [8,9]. Одним из таких направлений являются мультиагентные методы интеллектуальной оптимизации, базирующиеся на моделировании коллективного интеллекта [10-13].

Такие методы являются итеративными, эвристическими методами случайного поиска. Особенно наблюдается стремительный рост интереса к разработке алгоритмов, инспирированных природными системами. Среди них активно рaзвивaются методы роевого интеллекта (Swarm Intelligence) [8-10], в которых совокупность простых агентов конструирует стратегию своего поведения без наличия глобального управления. Одним из новейших мультиагентных методов интеллектуальной оптимизации является метод муравьиной колонии [9]. В работе излагается метод планирования комплекса программ в многопроцессорных вычислительных системах, базирующийся на моделировании адаптивного поведения муравьиной колонии.

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

Пусть МВС состоит из n идентичных, параллельно работающих процессоров

E={ei|i=1,2,…,n}.

На вход МВС поступает множество m независимых программ

W={wj|j=1,2,…,m},

которые требуется распределить между процессорами. Если время rj непрерывного использования процессора для выполнения каждой программы wj, одинаково для всех процессоров, то множеству W сопоставляется множество

R={rj|j=1,2,…,m}.

l-м решением задачи планирования в этом случае является множество

Vl={Wli|i=1,2,…,n},

где Wli подмножество программ, выполняемых на процессоре ei:

(i,j)[((ij)&(WliVl)&(WljVl))>((WliWlj =)&(Wli= W))]. (1)

Запланированная вариантом решения Vl загрузка программами каждого процессора ei оценивается ресурсом:

Rli =rk; где rk |wk Wli . (2)

Если производительность процессоров различна, то задается время rij непрерывного использования процессора ei для выполнения программы wj. Таким образом, множествам E и W сопоставляется множество R={rij| i=1,2,…,n; j=1,2,…,m}. В этом случае формула (2) примет вид:

Rli =rik, где k|wk Wli . (3)

Представим некоторую очередь программ, поступающих на процессор ei в виде списка

Pli=p1,p2,p3,…,ps,…,pm.,

где ps это индекс программы, у которой порядковый номер в очереди Pli равен s.

Загрузка программами каждого процессора, рассчитываемая по формулам (2) или (3), не учитывает время переключения между различными заявками. Отметим, что время переключения для каждой пары соседних заявок в очереди имеет свое значение.

Продолжительность переключения между соседними в очереди заявками, поступающими на обслуживающий прибор ei, задается матрицей переключений

Тi=||tk,s||mm.

Таблица № 1 Матрица переключений Тi

*	t12	t13	t14	t15
t21	*	t23	t24	t25
t31	t32	*	t34	t35
t41	t42	t43	*	t45
t51	t52	t53	t54	*

tk,s - время переключения между соседними в очереди заявками (wk, ws).

Очередь заявок, поступающих на обслуживающий прибор, с учетом времени переключения между различными соседними заявками примет вид:

Pli = p1, t12, p2, t23, p3, ,…, ps, ts,s+1, ps+1 ,… , pm-1, tm-1,m , pm.

Здесь ts,s+1 - время переключения между соседними в очереди Pli программами с порядковыми номерами s и s+1.

Общее время Tli переключения между заявками, поступающими на вход обслуживающего прибора ei, определится как сумма переключений:

Tli =tk-1,k , где k| tk-1,k Pli.. (4)

Таким образом, загрузка Rli заявками процессора ei с учетом времени переключения между соседними заявками в очереди Pli, а также времени rij непрерывного использования процессора ei для выполнения каждой программы wj Wli определится как:

Rli =Tli +rik , где k|wk Wli (5)

Для обеспечения максимальной эффективности использования существующих ресурсов необходимо упорядочить очередь заявок в каждом списке Pli. Будем считать, что

Pl={Pli|i=1,2,…,n} -

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

В этом случае решением Zl задачи распределения заявок между обслуживающими приборами является совокупность двух множеств Vl и Pl, т.е.

Zl=(Vl; Pl).

В качестве оценки решения Zl рассматривается величина:

Fl=max(Rli). i

Наиболее распространённым критерием оптимизации при планировании в случае многоуровневой очереди является «минимаксный» критерий:

F=min Fl = min max (Rli). l l i

Это связано с тем, что в большинстве реальных задач при планировании чаще всего требует решения задача уменьшения времени выполнения всех заявок. Поскольку, чем быстрее СМО обслуживает поступающие заявки, тем выше ее производительность, а значит, и выше экономическая эффективность предприятия, использующего данную систему.

Для отображения распределения заявок по обслуживающим приборам используется полный двудольный граф

Hnm=(EW, U), где E={ei|i=1,2,…,n}

- множество вершин (первая доля), соответствующих множеству обслуживающих приборов, а

W={wj|j=1,2,…,m} -

множество вершин (вторая доля), соответствующих множеству заявок (потоков). U - множество ребер, связывающих вершины множества E с вершинами множества W. Конкретное решение задачи распределения заявок представляется в виде подграфа

Hl=(EW, Ul). HlHnm, UlU.

Вершина wjW связана с вершиной eiE в том и только в том случае, когда wj назначена в ei. Пусть Uli множество ребер двудольного графа Hl,связывающих вершину ei с вершинами множества Wli.

Uli=Ul.

Для наглядности представления конкретного распределения заявок (рис. 1) множество заданий W сгруппировано в подмножества Wli, где Wli- подмножество заявок, поступающих на обслуживающий прибор ei.

Отличительной особенностью представленного двудольного графа

Hl=(EW, Ul)

является то, что число ребер множества Uli равно числу вершин множества Wli. Каждое ребро uzUli, с одной стороны, инцидентно вершине ei, а с другой стороны, инцидентно одной и только вершине wkWli.

Назовем двудольный граф, представляющий распределение заявок, граф - распределением Hl. Отметим, что в графе - распределении Hl локальная степень любой вершины wjW равна единице, а локальная степень вершины ei равна мощности множества Wli, т.е.

с(wj)=1, с(ei)= |Wli|.

Таким образом, поиск распределение заявок сводится к поиску на полном двудольном графе Hnm подграфа Hl.

Рис. 1 Интерпретация распределения программ в МВС

2. Разработка алгоритма планирования на основе моделей адаптивного поведения муравьиной колонии

В основу работы разработанного алгоритма положены механизмы адаптивного поведения муравьиной колонии. Особенностями являются наличие непрямого обмена информацией, который используется в муравьиных алгоритмах. Непрямой обмен - стигмержи представляет собой разнесённое во времени взаимодействие, при котором одна особь оставляет результаты своей деятельности в окружающей среде, а другие используют эту информацию позже, выполняя в той же среде аналогичные действия. Такое отложенное взаимодействие, использующее в качестве посредника окружающую среду, происходит через специальное химическое вещество - феромон (pheromone).

Метаэвристика муравьиного алгоритма базируется на комбинации двух технологий поиска. Общая структура строится на базовом методе, в который включается та или иная встроенная процедура. Встроенная процедура - это в большинстве случаев самостоятельный алгоритм решения той же задачи, что и метаэвристический метод в целом. Базовый метод заключается в реализации адаптивной итерационной процедуры поиска лучшего решения среди решений, формируемых с помощью встроенной процедуры. В качестве встроенной процедуры служит конструктивный алгоритм построения муравьем некоторой конкретной интерпретации решения. Конструктивный алгоритм, построенный на модели адаптивного поведения искусственных муравьев, играет ключевую роль [8]. Не менее важное значение имеет модель окружающей среды, используемая в качестве посредника при обмене информацией. Классификация гибридных метаэвристик детально рассмотрена в работе [14-16].

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

Рассмотрим принципы планирования методами муравьиной колонии. Будем считать, что подсчет величины Rli производится по формуле (5). Поиск оптимального решения осуществляется по критерию F (см.7).

Работа поисковой процедуры начинается с построения в соответствии со спецификой решаемой задачи графа поиска решений (ГПР). Структура ГПР должна позволять формировать отображение и поиск интерпретации IDl решения

Zl=(Vl;Pl).

ГПР формируется на основе интеграции трех составляющих - полного двудольного графа Hnm, полного графа G и звездного графа GZ.

На первом этапе формируется полный двудольный граф Hnm =(EW, U1), используемый для построения интерпретации множества Vl. Вторая составляющая графа поиска решений связана с необходимостью упорядочивания заявок, т.е. фактически введения приоритета для заявок каждой группы потоков, обслуживаемых одним прибором. Этот этап связан с диверсификацией графа поиска решений и организацией поиска решений на этом графе.

На втором этапе построения графа поиска решений формируется граф

GHnm=(EW, U1U2)

на основе интеграции двух графов: полного двудольного графа

Hnm=(EW, U1) и полного графа G=(W, U2).

Другими словами GHnm состоит из двух подграфов -

Hnm=(EW, U1) и подграфа G=(W,U2),

использующих одно множество вершин

W. |U1|=nm, |U2|=m(m-1). В графе GHnm=(EW,U1U2)

каждая вершина eiE связана со всеми вершинами множества W. Каждая вершина wjW, с одной стороны связана со всеми вершинами множества E, а с другой стороны связана со всеми вершинами множества W. Третий этап диверсификации ГПР связан с добавлением третьей составляющей ГПР - звездного графа

GZ =(WO, U3).

Используемая в качестве стартовой вершины центральная вершина O звездного графа GZ, связывается множеством ребер U3 с каждой wjW, |U3|=m. Звездный граф GZ предназначен для выбора первой вершины wjW, включаемой в состав маршрута Ml. Таким образом, диверсифицированный граф поиска решений имеет вид:

D=HnmGGZ, D=(EWO,U1U2U3).

Отметим, все три составляющие графа D - полный двудольный граф Hnm, полный граф G и звездный граф GZ используют одно множество вершин W.

Локальные степени вершин графа D:

 с(ei)=m. с(wj)=n+m. с(O)=m.

На рис. 2 приведен диверсифицированный граф поиска решений D для |E|=3, |W|=5.

U1={(ei,wj)|i=1,2,3; j=1,2,3,4,5}.

U2={(wi,wj)|ij; i=1,2,3,4,5; j=1,2,3,4,5}.

U3={(O,wj)|j=1,2,3,4,5}.

Рис. 2 Диверсифицированный граф поиска решений

Интерпретация IDl на ГПР D решения задачи загрузки заявками обслуживающих приборов с учетом времени tks переключения между различными заявками в очереди Pli, а также времени rij непрерывного использования процессора ei для выполнения каждой заявки wj включает две части. Первая часть представляет собой маршрут Ml, построенный агентом, стартующим из вершины O на полном подграфе

G=(W, U2)

графа D. Маршрут Ml начинается с вершины O и включает все вершины подграфа G. Вторая часть представляет собой подграф

Hl=(EW, U1l) полного двудольного графа

Hnm=(EW, U1), U1lU1, |U1l|=m.

Hl отражает разбиение множества вершин W на подмножества Wli.

IDl =(Ml, Hl).

На основе маршрута Ml и подграфа Hl для каждого обслуживающего прибора ei определяется множество заявок Wli и формируется очередь Pli. Заявки каждого подмножества Wli поступают на обслуживающий прибор ei в том порядке, в котором они расположены в маршруте Ml друг относительно друга. Время tks переключения между соседними заявками (wk, ws) в очереди Pli определяется из таблицы 1.

Пример. Пусть на графе поиска решений D, представленном на рис. 2, построен маршрут Ml =o > w1 > w5 > w2 >w3 > w4 и сформирован граф Hl, задающий разбиение множества заявок W на подмножества:

Wl1={w1,w5,w2}; Wl2={w3}; Wl3={w4}.

Распределение заявок по обслуживающим приборам, с учетом времени tks переключения между различными заявками, представлено на рис. 3. На рис. 4 представлено решение Zl=(Vl;Pl) соответствующее

IDl=(Ml, Hl).



Рис. 3 Распределение заявок по обслуживающим приборам, с учетом времени

Рис. 4 Полученное решение

Рассмотрим базовую поисковую процедуру. Поиск решения начинается с задания размера популяции искусственных муравьев. Вершина О в графе D является стартовой для всех муравьев. Моделирование поведения муравьёв связано с распределением феромона на ребрах графа D. На начальном этапе на всех ребрах

U=U1U2U3

графа D откладывается одинаковое (небольшое) количество феромона равное Q/v, где

v=|U|.

Параметр Q задается априори. Будем обозначать граф D после отложения на нем на итерации t феромона, как D(t). После начального отложения - D(0). Процесс поиска решений итерационный. Каждая итерация t включает 3 этапа.

На первом этапе каждой итерации t выполняются процедуры муравья. Каждый агент al формирует на ребрах графа D(t-1) интерпретацию решения - свой собственный граф Hl(t) и маршрут Ml(t). На основе интерпретации

IDl=(Ml(t);Hl(t)),

формируется решение

Zl(t)=(Vl(t);Pl(t))

для которого подсчитывается оценка решения Fl(t).

Обозначим как Ul(t)U множество всех рёбер, соответствующих ребрам построенного графа Hl(t) и ребер, входящих в состав маршрута Ml(t). На втором этапе итерации t, каждый муравей al откладывает феромон на ребрах множества Ul(t). Количество феромона фl(t), откладываемое муравьем al на каждом ребре ukUl(t), определяется следующим образом:

фl(t)= Q / Fl(t),

где t-номер итерации, Q - общее количество феромона, откладываемое муравьем на ребрах множества Ul(t), Fl(t) - целевая функция для решения, полученного муравьем al на t-ой итерации. Чем меньше Fl(t), тем больше феромона откладывается на ребрах и, следовательно, тем больше вероятность выбора этих ребер при построении интерпретации решения

IDl=(Ml,Hl)

на следующей итерации.

Обозначим как fk(t) суммарное количество феромона, скопившееся на каждом ребре

ukU1U2U3

ГПР, после выполнения второго этапа итерации t.

После того, как каждый агент сформировал решение и отложил феромон, на третьем этапе итерации t происходит общее испарение феромона на каждом ребре uk ГПР в соответствии с формулой:

fk(t) = fk(t)(1- с), (8)

где с - коэффициент обновления.

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

Рассмотрим теперь конструктивный алгоритм построения муравьем интерпретации решения

IDl =(Ml,Hl).

Отметим, что маршрут Ml и подграф Hl используют одно множество вершин W. Любой маршрут Ml начинается со стартовой вершины O. Поэтому первой в маршрут Ml включается вершина O.

Начиная с первого шага, маршрут Ml и подграф Hl формируются последовательно и одновременно. Обозначим как Wend множество вершин wjW, вошедших в формируемый маршрут, а как Win множество свободных вершин wjW, еще не вошедших в формируемый маршрут.

WendWin=W.

Пусть вершина wбWend, является последней вершиной, включенной на некотором шаге в маршрут Ml, и маршрут еще полностью не сформирован. Параметры Wend, wб, Win являются параметрами состояния процедуры построения маршрута Ml и подграфа Hl.

На первом шаге построения Ml параметры состояния имеют следующие значения:

wб=O, Win=W, Wend = .

На каждом шаге последовательной процедуры выбирается вершина wвWin, которая вместе с ребром (wб,wв) включается в маршрут Ml и, одновременно для wв выбирается вершина ei, что равносильно включению ребра (wв, ei) в Hl. Выбор wв осуществляется следующим образом. Для вершины wб определяется набор ребер Uin, связывающих wб со всеми вершинами wвWin. Для каждого ребра (wб,wв)Uin, связывающего вершину wб с вершиной wвWin определяется параметр fбв - суммарный уровень феромона на этом ребре. Вероятность Pбв включения ребра (wб,wв)Uin и вершины wв, в формируемый маршрут определяется следующим соотношением:

Pбв=fбв / ?в ( fбв). (9)

Агент с вероятностью Pбв выбирает одно из ребер (wб,wв)Uin, которое включается в формируемый маршрут.

После этого для выбранной вершины wв определяется набор U1в U1 ребер, связывающих wв со всеми вершинами eiE. Для каждого ребра (wв,ei)U1в, определяется параметр fвi - суммарный уровень феромона на этом ребре. Вероятность Pвi включения ребра (wв, ei)U1в в формируемый двудольный подграф Hl определяется следующим соотношением:

Pвi=fвi / ?i ( fвi). (10)

Агент с вероятностью Pвi выбирает одно из ребер множества U1в, которое включается в формируемый двудольный подграф Hl.

Временная сложность этого алгоритма зависит от времени жизни колонии t (число итераций), количества исполнителей n и числа работ m, и определяется как O(t•n2•m).

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

Алгоритм поведения популяции агентов (муравьев).

1.Задается: число исполнителей - n; число работ - m; начальное количество феромона - Q.

2.Строится граф поиска решений

D =(EWO, U1U2U3).

3.На ребрах ГПР D откладывается начальное количество феромона, равное Q/v, где

v=|U|.

4.Задается: число итераций - NT; число муравьев формирующих независимо друг от друга решения на одной итерации - NA.

5.t=1. (t- номер итерации).

6.l=1. (l- номер агента).

7.(Алгоритм муравья). Муравей al строит на ГПР D интерпретацию решения

IDl =(Ml, Hl).

8.На основе интерпретации решения IDl =(Ml;Hl) формируется решение

Zl=(Vl;Pl)

для которого рассчитывается оценка Fl(t).

9.Если

l<NA, то l=l+1

и переход к пункту 7, иначе переход к п. 10.

10.l=1.

11.Муравей al откладывает на ребрах множества Ul(t)U, соответствующих ребрам построенного графа Hl(t) и ребрах, входящих в состав маршрута Ml(t) феромон в количестве

фl(t)= Q / Fl(t).

12.Если

l<NA, то l=l+1

и переход к п. 11, иначе переход к п. 13.

13.На третьем этапе итерации t происходит общее испарение феромона на всех ребрах ГПР D в соответствии с формулой:

fij=fij(1-с),

где с -коэффициент обновления.

14.Находится агент с лучшим решением F*(t), полученным после выполнения t итераций, которое запоминается.

15.Если

t< NT, то t= t +1

и переход к п. 6, иначе переход к п. 16.

16.Конец работы алгоритма.

Рассмотрим теперь конструктивный алгоритм построения муравьем интерпретации решения

IDl =(Ml;Hl).

Алгоритм муравья.

1.Агент al помещается в стартовую вершину O. В маршрут Ml включается вершина O. 2.Формируются параметры состояния:

wб=O, Win=W, Wend=.

U1l=. Hl=(EW, )

3.Для вершины wб определяется набор ребер U2in, связывающих wб со всеми вершинами wвWin.

4.Для каждого ребра (wб,wв)U2in, связывающего вершину wб с вершиной wвWin определяется параметр fбв - суммарный уровень феромона на этом ребре.

5.Рассчитывается вероятность Pбв включения ребра (wб,wв)U2in и вершины wв, в формируемый маршрут Ml,

Pбв=fбв/?в(fбв).

6.Агент с вероятностью Pбв выбирает одно из ребер (wб,wв)2Uin и вершину wв.

7.Вершина wв включается в маршрут Ml.

8.Обновляются значения параметров состояния:

Wend=Wendwв, Win=Win\wв, wб = wв.

9.Для выбранной вершины wв определяется набор U1вU1 ребер, связывающих wв со всеми вершинами eiE.

10.Для каждого ребра (wв,ei)U1в, определяется параметр fвi- суммарный уровень феромона на этом ребре.

11.Вероятность Pвi включения ребра (wв, ei)U1в в формируемый двудольный подграф Hl определяется следующим соотношением

Pвi=fвi/?i(fвi).

12.Агент с вероятностью Pвi выбирает одно из ребер (wб,wв)U1в, которое включается в граф Hl.

U1l=U1l (wб,wв).

13.Если Win=, а Wend=W, то переход к п. 14, иначе переход к п. 3.

14.Интерпретация решения

IDl =(Ml;Hl)

полностью сформирована.

Конец работы алгоритма муравья.

3. Экспериментальные исследования

Алгоритм распределения программ на многопроцессорных вычислительных системах был запрограммирован на языке С++ на платформе Windows. При этом все исследования проводились на компьютере типа Intel® Core™ i5 CPU 3.33 GHz и ОЗУ размером 4 Гб. При выполнении экспериментов необходимо было исследовать эффективность и качество предложенных механизмов муравьиной колонии для решения задачи планирования многоуровневой очереди. Для этого была применена процедура формирования контрольных тестов с известным оптимумом.

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

Для получения достоверных выводов был проведен не один, а серия опытов-экспериментов. Временная сложность этого алгоритма зависит от времени жизни колонии t (число итераций), количества обслуживающих приборов n и числа заявок m, и определяется как O(t•n2•m). Тестовые испытания показали, что в 98% случаев пространство синтезированных решений включает глобальное оптимальное решение.

Исследование сходимости алгоритма выполнялось следующим образом. Запоминался номер итерации, после которой не наблюдалось улучшения оценки-критерия, для каждого эксперимента. В каждой серии из 50 испытаний определялись минимальный и максимальный номера итерации. Кроме этого рассчитывалось среднее значение количества итераций, после которого не наблюдалось улучшения оценки-критерия. Для каждой серии испытаний определялось лучшее решение, которое фактически являлось оптимальным. В результате экспериментов установлено, что при объеме популяции М=90 алгоритм сходится в среднем на 120 итерации.

Сравнение значений критерия, полученных муравьиным алгоритмом на тестовых примерах, с известным оптимумом показало, что у 90% примеров полученное решение было оптимальным, у 15% примеров решения были на 3% хуже оптимального, а у 5% примеров решения были хуже не более, чем на 2%. По сравнению с существующими алгоритмами [3-10] достигнуто улучшение результатов на 2- 3 %.

Заключение

Несмотря на достаточно большое число разработанных моделей, и алгоритмов оптимизации планирования и диспетчеризации многопроцессорных вычислительных систем, исследователи часто сталкиваются с рядом проблем, к числу которых относятся трудность в обосновании качества результатов анализа, учитывающего специфику задачи. Отсюда можно сделать вывод о целесообразности дальнейшего развития методов планирования и диспетчеризации МВС, позволяющих решать указанные проблемы. К числу перспективных тенденций относятся стохастические поисковые алгоритмы оптимизации, которые в разных публикациях называют поведенческими, метаэвристическими, вдохновленными (инспирированными) природой, роевыми, многоагентными, популяционными и т.д. В работе рассматриваются новые принципы решения задачи планирования работы МВС на основе моделей адаптивного поведения муравьиной колонии. Разработаны модифицированные механизмы поведения муравьев и структура пространства решений, в рамках которого организован поисковый процесс, базирующийся на моделировании адаптивного поведения роя муравьев.

Ключевая проблема, которая была решена в данной работе, связана с разработкой композитной структуры пространства решений, позволяющей отображать и осуществлять поиск интерпретаций задачи. Пространство формируется на основе интеграции трех составляющих - полного двудольного графа Hnm, полного графа G и звездного графа GZ. Это позволило формировать гибридную интерпретацию решения задачи загрузки заявками обслуживающих приборов с учетом времени переключения между различными заявками в очереди, а также времени непрерывного использования процессора для выполнения каждой заявки. Поиск решений в соответствии с метаэвристикой муравьиной колонии основывается на комбинации двух алгоритмов: базовый алгоритм реализует итерационную процедуру поиска лучшего решения и конструктивный алгоритм построения муравьем некоторой конкретной интерпретации решения. Такой подход является источником усовершенствования каждой из процедур в отдельности, что ускорит процесс достижения целевого состояния.

Работа выполнена при финансовой поддержке РФФИ грант №17-07-00997.

Литература

1. Лазарев А.А., Гафаров Е.Р. Теория расписаний. Задачи и алгоритмы. - М.: МГУ им. М.В. Ломоносова, 2011. - 158 с.

2. Ларионов С.А., Майоров Г.И. Вычислительные комплексы, системы и сети. - СПб.: Энергоатомиздат, 1987. - 186 с.

3. Романовский И.В. Алгоритмы решения экстремальных задач. - М.: Наука, 1977. - 148 с.

4. Нейдорф Р.А., Жикулин А.А. Быстродействующая модификация алгоритма оптимизации решения // Труды конгресса по интеллектуальным системам и информационным технологиям «AIS-IT'14». Научное издание в 4-х томах. Т.1. - М.: Физматлит, 2014. - C. 15-22.

5. Кобак В.Г., Будиловский Д.М. Сравнительный анализ приближенных алгоритмов решения минимаксной задачи для однородных приборов // Вестн. Донск. гос. техн. ун-та, 2006. - № 4. - С. 327-334.

6. Нейдорф Р.А., Жикулин А.А. Исследование вариантов модификации приближенных алгоритмов решения однородных распределительных задач, повышающих их эффективность // Инновация, экология и ресурсосберегающие технологии (ИнЭРТ-2012): Труды X Междунар. науч.-техн. форума. - Ростов н/Д: ИЦ ДГТУ, 2012. - С. 370-375.

7. Нейдорф Р.А., Жикулин А.А. Селективно-перестановочный метод приближенного решения однородной распределительной задачи. Комбинационные перестановки // Известия ЮФУ. Технические науки. Тематический выпуск «Интеллектуальные САПР». - Таганрог: Изд-во ТТИ ЮФУ, 2013. - № 7(144). - С. 167-172.

8. Dorigo M., Stьtzle T. Ant Colony Optimization. MIT Press, Cambridge, MA, 2004. - 226 p.

9. Лебедев О.Б. Модели адаптивного поведения муравьиной колонии в в задачах проектирования. Монография. -Таганрог. Изд-во ЮФУ, 2013. - 199 с.

10. Raidl G.R. A Unified View on Hybrid Metaheuristics. In: Lecture Notes in Computer Science. Springer- Verlag, 2006. - pp. 1-12.

11. Лебедев Б.К., Лебедев О.Б. Моделирование адаптивного поведения муравьиной колонии при поиске решений, интерпретируемых деревьями // Известия ЮФУ. Изд-во ТТИ ЮФУ, 2012 -№7. - С. 27-35.

12. Лебедев В.Б., Лебедев О.Б. Роевой интеллект на основе интеграции моделей адаптивного поведения муравьиной и пчелиной колоний // Известия ЮФУ. Изд-во ТТИ ЮФУ, 2013, №7. - С. 41-47.

13. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Разбиение на основе моделирования адаптивного поведения биологических систем. Нейрокомпьютеры: разработка, применение. 2010. -№2. - С. 28-34.

14. Карпенко А.П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. - Москва: Издательство МГТУ им. Н.Э. Баумана, 2014. - 446 с.

15. Засядко Г.Е. Представление графовых моделей данных в виде n-арных деревьев // Инженерный вестник Дона, 2017, №2. URL: ivdon.ru/ru/magazine/archive/N2y2017/4166.

16. Пшихопов В.Х., Шевченко В.А., Медведев М.Ю., Гуренко Б.В. Управление распределенными системами подводной робототехники с использованием адаптивной эталонной модели // Инженерный вестник Дона, 2017, №2. URL: ivdon.ru/ru/magazine/archive/N2y2017/4130.

References

1. Lazarev A.A., Gafarov E.R. Teoriya raspisaniy. Zadachi i algoritmy. [Theory of schedules. The tasks and algorithms]. Moscow: Moscow State University M.V. Lomonosov. 2011. 158 p.

2. Larionov S.A., Mayorov G.I. Vychislitel'nyye kompleksy, sistemy i seti. [Computing systems, systems and networks]. St. Petersburg: Energoatomizdat. 1987. 186 p.

3. Romanovskiy I.V. Algoritmy resheniya ekstremal'nykh zadach. [Algorithms for solving extremal problems]. Moscow: Nauka. 1977. 148 p.

4. Neydorf R.A., Zhikulin A.A. Trudy kongressa po intellektual'nym sistemam i informatsionnym tekhnologiyam «AIS-IT'14». Nauchnoye izdaniye v 4-kh tomakh. T.1. [Proceedings of the Congress on Intelligent Systems and Information Technologies «AIS-IT'14». Scientific publication in 4 volumes. vol.1.] Moscow: Fizmatlit. 2014. рр. 15-22.

5. Kobak V.G., Budilovski, D.M. Vestn. Donsk. State. Tech. Un-ta. 2006. рр. 327-334.

6. Neydorf R.A., Zhikulin A.A. Trudy X Mezhdunar. nauch.- tekhn. Foruma: Innovatsiya, ekologiya i resursosberegayushchiye tekhnologii (InERT-2012) [Innovation, Ecology and Resource-Saving Technologies (InERT-2012): Proceedings of the Xth International. Scientific-techn. Forum]. Rostov on Don: DSTU. 2012. рр. 370-375.

7. Neydorf R.A., Zhikulin A.A. Izvestiya SFU. Tekhnicheskiye nauki. Tematicheskiy vypusk «Intellektual'nyye SAPR» [Izvestiya SFU. Technical science. Thematic issue "Intellectual CAD"]. Taganrog: SFU, № 7 (144). 2013. рр. 167-172.

8. Dorigo M., Stьtzle T. Ant Colony Optimization. MIT Press, Cambridge, MA. 2004. 226 p.

9. Lebedev O.B. Modeli adaptivnogo povedeniya murav'inoy kolonii v zadachakh proyektirovaniya [Models of adaptive behavior of ant's colony in design problems]. Taganrog SFU. 2013. 199 p.

10. Raidl G.R. A Unified View on Hybrid Metaheuristics. In: Lecture Notes in Computer Science. Springer-Verlag. 2006. рр.1-12.

11. Lebedev B.K., Lebedev O.B. Izvestiya SFU. Tekhnicheskiye nauki. Tematicheskiy vypusk «Intellektual'nyye SAPR» [Izvestiya SFU. Technical science. Thematic issue "Intellectual CAD"]. Taganrog: SFU, № 7. 2012. рр. 27-35.

12. Lebedev V.B., Lebedev O.B. Izvestiya SFU. Tekhnicheskiye nauki. Tematicheskiy vypusk «Intellektual'nyye SAPR» [Izvestiya SFU. Technical science. Thematic issue "Intellectual CAD"]. Taganrog: SFU, № 7. 2013. рр. 41-47.

13. Kureychik V.M., Lebedev B.K., Lebedev O.B. Neyrokomp'yutery: razrabotka, primeneniye [Neurocomputers: development, application]. Moscow: №2, 2010. рр. 28-34.

14. Karpenko A.P. Sovremennyye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennyye prirodoy [Modern algorithms of search optimization. Algorithms inspired by nature]. Moscow: MSTU N.E. Bauman. 2014. 446 p.

15. Zasyadko G.E. Inћenernyj vestnik Dona (Rus), 2017, №2. URL: ivdon.ru/ru/magazine/archive/N2y2017/4166.

16. Pshikhopov V.Kh., Shevchenko V.A., Medvedev M.Yu., Gurenko B.V. Inћenernyj vestnik Dona (Rus), 2017, №2. URL: ivdon.ru/ru/magazine/archive/N2y2017/4130.

Размещено на Allbest.ru

...