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

В основу работы разработанного алгоритма положены механизмы адаптивного поведения муравьиной колонии. Особенностями являются наличие непрямого обмена информацией, который используется в муравьиных алгоритмах. Непрямой обмен — стигмержи представляет собой разнесённое во времени взаимодействие, при котором одна особь оставляет результаты своей деятельности в окружающей среде, а другие используют эту информацию позже, выполняя в той же среде аналогичные действия. Такое отложенное взаимодействие, использующее в качестве посредника окружающую среду, происходит через специальное химическое вещество — феромон (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.

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

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

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

12. Если.

l.

и переход к п. 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=Winwв, 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).

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

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