В.А. Костенко, А.В. Плакунов - Алгоритм построения одноприборных расписаний, основанный на схеме муравьиных колоний (статья) (1121259), страница 2
Текст из файла (страница 2)
ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ№6201390КОСТЕНКО, ПЛАКУНОВподциклподциклчисло работ в цепочкеtцепочка работрезерв времени вначале подцикларезерв для сдвигарасписаниярезерв времени вконце подциклаРис. 3. Циклическая схема обмена даннымики”, не должен приводить к нарушению директивного времени завершения работы или требования к минимальному резерву времени в конце подцикла;10) последовательность номеров сообщений, которым соответствуют работы в каждой из цепочек, должна являться подпоследовательностью некоторой глобальной последовательностиномеров сообщений, записанной в памяти контроллера шины.Ограничения 4)–10) типичны для авиационных и навигационных систем для схемы организации обменов с подциклами. Такие дополнительные ограничения будем обозначать какg i (H , xi ), i = 4,10, где xi – численное значение требования, например, для ограничения 8) это максимально допустимое число работ в цепочке.Задача построения статических расписаний обменов по шине с централизованным управлением формулируется следующим образом:max { H g i (H , xi ), i = 4,10}.H ∈H *Задача без дополнительных ограничений max H известна в теории расписаний как задача оH ∈ H*выборе максимального числа совместимых заявок и является NPтрудной.
Однако есть частныезадачи этой задачи, которые являются полиномиально разрешимыми. Например, для частнойзадачиmax { H t j = f j − s j ∀ j}H ∈ H*известен оптимальный жадный алгоритм сложности O(n ⋅ lnn) [16].2. Общая схема муравьиных алгоритмов. Интересным результатом кооперативного поведениябиологических муравьев является нахождение кратчайшего маршрута от источника пищи к гнезду. Рассмотрим, как кооперативное поведение биологических муравьев позволяет найти кратчайший маршрут к источнику пищи. Пусть гнездо соединено с источником пищи двумя ребрамиразной длины. Муравьи при прохождении маршрута откладывают феромоны, и чем больше муравьев прошло по ребру, тем выше концентрация феромонов на этом ребре.
Чем выше концентрация феромонов на ребре, тем выше вероятность, что муравей пойдет по нему. Изначально вероятности выбора маршрутов равны. Муравьи, выбравшие короткое ребро, возвращаются быстрее. Количество феромонов на коротком ребре растет быстрей и, следовательно, повышаетсявероятность его выбора, т.е. через некоторое время по нему будет проходить большинство муравьев. Со временем феромоны испаряются, что позволяет муравьям адаптировать поведение подизменение внешней среды.Общую схему работы муравьиных алгоритмов можно представить в следующем виде [9, 10]:1) задание начального количества феромона на ребрах графа, количества и начального положения муравьев;2) построение муравьями путей (каждый муравей строит путь независимо от остальных);ИЗВЕСТИЯ РАН.
ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ№62013АЛГОРИТМ ПОСТРОЕНИЯ ОДНОПРИБОРНЫХ РАСПИСАНИЙ913) вычисление целевой функции для каждого пути;4) обновление количества феромона на ребрах;5) если условие останова не выполнено, то переход к п. 2.Муравьи строят маршруты, последовательно переходя от вершины к вершине, руководствуясь при этом определенным алгоритмом для определения списка вершин, доступных на данномэтапе (например, при решении задачи коммивояжера используется табусписок недоступныхвершин, в который добавляются пройденные муравьем вершины).
Выбор очередной вершинызависит от количества феромона и значения эвристической функции на ребрах, ведущих из текущей вершины в вершины, доступные на данный момент. Эти значения определяют вероятность перехода в ту или иную вершину, после чего очередная вершина выбирается по правилу рулетки. В конце каждой итерации для каждого найденного маршрута вычисляется значение целевой функции. Оно используется для вычисления количества феромона, добавляемого на ребра,входящие в данный маршрут.Операция построение муравьем пути.
Муравей строит путь, переходя из одной вершины в другую. Пройденные муравьем вершины добавляются в табусписок (память муравья), чтобы избежать повторного их посещения. Вероятность перехода муравья из iй вершины в jю зависит отколичества феромона на данном ребре, значения локальной эвристической функции на ребре исостояния табусписка. Вероятность перехода kго муравья из iй вершины в jю на tй итерацииалгоритма рассчитывается по следующей формуле:⎧τijα (t ) ηβij (t )⎪Pij,k (t ) = ⎨⎪⎩0, j ∈ Lk .∑ταil(t ) ηβil (t ),j ∉ Lk ,l ∈ JkЗдесь τij (t) – количество феромона на ребре (i, j), ηij (t) – значение эвристической функции на ребре (i, j), α ≥ 0 и β ≥ 0 – параметры алгоритма, определяющие важность феромонного следа и эвристической функции, Lk – множество вершин, включенных в табусписок муравья k.Операция обновление количества феромона на ребрах.
После того, как все муравьи завершилипостроение путей, обновляется количество феромона на ребрах:mτij (t + 1) = (1 − p) τij (t ) +∑ Δτk =1ij,k⎧F (Tk (t )) , (i, j ) ∈ Tk (t ) ,⎩0, (i, j ) ∉ Tk (t ) .(t ) ; Δτij,k (t ) = ⎨Здесь Tk(t) – путь, построенный kм муравьем, а F(T) – целевая функция, определяющая качество пути, m – количество муравьев, p ∈ [0, 1] – коэффициент испарения феромонов. Испарениеферомонов вводится для избегания попадания алгоритма в локальный оптимум, когда первыйнайденный путь с относительно хорошим значением целевой функции становится единственнозначимым.Основными задачами, которые необходимо решить для того, чтобы использовать муравьиныйалгоритм для решения задачи построения расписания, являются:1) сведение задачи построения расписания к задаче нахождения на графе пути, обладающегоопределенными свойствами;2) задание эвристической функции на ребрах графа;3) определение алгоритма построения маршрута муравьем (например, правила формирования табусписка вершин);3.
Алгоритм построения расписания обменов. 3.1. О б щ а я с х е м а р а б о т ы а л г о р и т м а.Для применения муравьиного алгоритма к задаче построения расписания обменов разобьем этузадачу на две подзадачи следующим образом:1) определение последовательности размещения работ в расписание;2) определение места в расписании для каждой работы. Работы выбираются в соответствии споследовательностью, построенной в п.
1).Такое разбиение обусловлено тем, что оно позволяет применить муравьиный алгоритм к подзадаче 1). Для размещения работ в расписание в соответствии с построенной муравьиным алгоритмом последовательностью будет использоваться жадный алгоритм, который опишем ниже.Общая схема алгоритма имеет следующий вид:1) построение муравьями путей в графе;ИЗВЕСТИЯ РАН.
ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ№6201392КОСТЕНКО, ПЛАКУНОВ2) применение алгоритма размещения работ в расписание, на вход которому подаются последовательности вершин, построенные муравьиным алгоритмом;3) вычисление целевой функции;4) обновление количества феромона на ребрах графа;5) если условие останова не выполнено, переход к п. 1).Преимуществом данной схемы является то, что для построения расписания по заданной последовательности работ в п. 2) может применяться любой алгоритм без существенных измененийв остальных пунктах.3.2.
С в е д е н и е з а д а ч и п о с т р о е н и я р а с п и с а н и я к з а д а ч е н а х о ж д е н и ян а г р а ф е п у т и. Первый способ сведения задачи основан на соответствии вершин графа работамв задаче. Сопоставим каждой работе Ai из J вершину ri. Также введем специальную вершину О, с которой будет начинаться маршрут каждого муравья. Получим граф G = V , E , где V = {O, r1, r2, ..., rn} –множество вершин, E = {(u, v )| u, v ∈ V , u ≠ v} – множество ребер (между любыми двумя вершинами есть два ориентированных ребра) и, таким образом, G – полносвязный ориентированныйграф.Для первого способа сведения задачи верно следующее утверждение:У т в е р ж д е н и е.
Каждому пути в графе G соответствует ровно одно расписание, и для одногои того же расписания может существовать более одного пути, по которому его можно построить.Д о к а з а т е л ь с т в о . Алгоритм построения расписания по последовательности работ детерминирован, поэтому каждому пути в графе G соответствует ровно одно расписание. Вторую частьутверждения можно доказать, приведя соответствующий пример: исходными данными являетсянабор из двух сообщений. Каждому сообщению соответствует ровно одна работа, причем множества подциклов, в которые эти работы можно разместить, не пересекаются. Так как работы немогут быть размещены в одном подцикле, то они не могут быть и в одной цепочке.
Это означает,что место в расписании для этих работ одинаково вне зависимости от взаимного расположенияэтих работ в пути. Таким образом, два различных пути в графе G соответствуют одному и тому жерасписанию.Второй способ сведения задачи основан на соответствии вершин графа сообщениям в задаче.Сопоставим каждому сообщению Mi из SM вершину vi. Аналогично введем специальную вершину О, с которой будет начинаться маршрут каждого муравья.
Получим граф G = V , E , гдеV = {O,v1,v 2, ..., v n} – множество вершин, E = {(u, v )| u, v ∈ V , u ≠ v} – множество ребер (междулюбыми двумя вершинами есть два ориентированных ребра), и аналогично получим, что G –полносвязный ориентированный граф.Для второго способа сведения задачи также верно приведенное выше утверждение.Преимуществами второго способа сведения задачи построения расписания к задаче поискана графе пути являются:1) меньшее число вершин в графе, что приводит к снижению вычислительной сложности и ксужению пространства поиска путей с высоким значением целевой функции;2) повышенная вероятность размещения всех работ одного сообщения, что важно при построении реальных систем.Исследования показали, что алгоритм, использующий второй способ сведения задачи, показывает лучшие результаты.
Поэтому этот алгоритм будет применяться для исследований в разд. 4.3.3. Л о к а л ь н ы е э в р и с т и ч е с к и е ф у н к ц и и н а р е б р а х г р а ф а. Для первогоспособа сведения задачи построения расписания к задаче нахождения пути на графе предложены следующие способы задания эвристической функции на ребрах графа:1) η1ij = 1 ( f j − s j ) , где fj и sj – соответственно директивное время завершения и директивноевремя начала работы – чем ýже директивный интервал работы, тем раньше ее предпочтительноразместить;2) ηij2 = t j ( f j − s j ) , где tj – время выполнения работы – чем ýже директивный интервал работыи чем больше времени нужно на ее выполнение, тем раньше ее предпочтительно разместить;3) η3ij = 1 NS , где NS – количество подциклов, в которые может быть размещена j:я работа ссоблюдением технологических ограничений и требований реального времени – чем меньше эточисло, тем раньше работу предпочтительно разместить.Для второго способа сведения задачи предложены следующие способы задания эвристической функции на ребрах графа:ИЗВЕСТИЯ РАН.
ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ№62013АЛГОРИТМ ПОСТРОЕНИЯ ОДНОПРИБОРНЫХ РАСПИСАНИЙ931) µ1ij = 1/( p Rj − p Lj ), где p Lj и p Rj – соответственно левый и правый фазовые сдвиги – аналог эвристики η1ij ;2) µij2 = wi ( p Rj − p Lj ) , где wj – число слов данных в сообщении – аналог эвристики ηij2 ;3) μ 3ij = 1 τ j , где τ j – период передачи сообщения – эвристика, известная как rate monotonic [17].Такие эвристические функции позволяют выбирать для частных задач, какой из параметровработ или сообщений наиболее важен с точки зрения точности алгоритма при выборе очереднойвершины графа. Если таких параметров более одного, возможно использование взвешеннойсуммы любых из перечисленных выше эвристик.3.4. А л г о р и т м п о с т р о е н и я м а р ш р у т а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
