В.А. Костенко, А.В. Плакунов - Алгоритм построения одноприборных расписаний, основанный на схеме муравьиных колоний (статья) (1121259), страница 3
Текст из файла (страница 3)
Алгоритм аналогичен алгоритму из разд. 2 суточнением, что в качестве табусписка Lk используется список посещенных вершин.3.5. А л г о р и т м р а з м е щ е н и я р а б о т в п о д ц и к л ы. Для построения расписания попути в графе требуется преобразовать последовательность вершин пути в последовательность работ. Для первого способа соответствие между множеством вершин и множеством работ взаимооднозначно: если P = { pi | i = 1, n jobs } – последовательность вершин и Aj – работа, соответствующаявершине pj, то A = { A j | j = 1, n jobs } – последовательность работ.Пусть теперь P = { pi | i = 1, n} – последовательность вершин для второго способа сведения задачи построения расписания к задаче нахождения на графе пути и Mj – сообщение, соответствующее вершине pj.
Последовательность работ A строится следующим образом:1) сообщения выбираются в последовательности, определяемой последовательностью вершин (выбор сообщения Mi);2) сортировка работ множества Ji по возрастанию их левой границы директивного интервала;3) добавление отсортированного множества работ во множество A с сохранением порядка;4) переход к п.
1), если не все вершины просмотрены.Построение расписания по последовательности работ выполняется разновидностью жадногоалгоритма, называемой алгоритмом упаковки [7]. Алгоритм упаковки был специально разработан для применения в системах, использующих схему организации обменов с подциклами, ипозволяет эффективно учитывать ограничение g10.Схема алгоритма упаковки выглядит так:1) во время построения расписания снимается ограничение на количество цепочек в подцикле;2) подциклы сортируются по критерию заполненности, т.е. в порядке увеличения суммарнойдлительности выполнения всех работ, включенных в подцикл.
При одинаковом значении критерия сортировка происходит по увеличению времени старта подцикла;3) очередной подцикл выбирается по порядку из отсортированного в п. 2 списка, если размещение работы в подцикл не нарушит всех ограничений gi:3.1) в выбранном подцикле просматриваются все цепочки в порядке увеличения их временстарта;3.2) для очередной цепочки производится попытка разместить работу в ее конец. Если размещенная таким образом работа пересекается со следующей цепочкой подцикла, все работы следующих цепочек сдвигаются вправо, если это возможно;3.3) если работу нельзя разместить в конец ни одной из цепочек, цепочки просматриваютсязаново в том же порядке;3.4) для очередной цепочки ∀ i производится попытка разместить работу между работами сномерами в цепочке i и i + 1.
Все работы, номер которых больше или равен i + 1, сдвигаютсявправо на интервал времени, равный длительности размещаемой работы, если это возможно;4) если работа не была размещена ни в одну из существующих цепочек подцикла, то создается новая цепочка, содержащая только размещаемую работу, если это не нарушает всехограничений gi;5) если создание новой цепочки невозможно, п. 3), 4) выполняются для следующего по порядку подцикла.
Работа размещается в первый подходящий для этого подцикл. Если работу не удается разместить ни в один подцикл, она помещается в список неразмещенных работ.ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ№6201394КОСТЕНКО, ПЛАКУНОВПосле проведения вышеописанных действий для каждой работы из множества A цепочки работ в каждом подцикле объединяются:1) цепочки одного подцикла ci сортируются в порядке убывания их времен старта, при этомцепочка C0 с максимальным временем старта не учитывается;2) все работы цепочки ci копируются в начало цепочки C0 с сохранением порядка, цепочка ciпосле этого удаляется. Если какиелибо работы после копирования начинают нарушать любое изограничений gi, такие работы удаляются и считаются неразмещенными;3) пункт 2 повторяется до тех пор, пока не будут просмотрены все цепочки подцикла.После такой операции в каждом подцикле остается не более одной цепочки, что позволяетполучить корректное расписание.3.6.
О б н о в л е н и е ф е р о м о н а. Алгоритм обновления феромона аналогичен соответствующему алгоритму из разд. 2 с условием, что феромон обновляется только на путях с наибольшимзначением целевой функции на данной итерации. Кроме того, максимальное и минимальное допустимое количество феромона на ребре было ограничено.4. Численное исследование свойств алгоритма. 4.1.
М е т о д и к а п р о в е д е н и я и с с л е д о в а н и я. Исследование проводилось на наборах данных, сгенерированных на основе реальныхданных. При генерации наборов варьировалось число слов данных в сообщениях, общее число сообщений и количество сообщений с одинаковой частотой и фазовыми сдвигами. В зависимости от свойств сгенерированного набора сообщений данные разбивались на несколько классов.Отличие классов исходных данных друг от друга заключалось в структуре фазовых сдвигов. Сообщения, претендующие на размещение работ в одни и те же подциклы, делились нанесколько групп, причем сообщения одной группы имели одинаковую частоту и фазовыесдвиги (частотнофазовые группы).
Такое разделение было выбрано на основе структуры реальных данных.В наборах сообщений класса исходных данных А в каждом подцикле выделяется две основных частотнофазовых группы, интервалы которых частично пересекались. В наборах сообщений класса исходных данных Б имелось три частотно фазовых группы, причем интервал первойиз групп включал в себя интервал второй группы и частично включал интервал третьей группы,притом второй и третий интервалы не пересекались. В каждом классе имелось 120 сгенерированных наборов исходных данных.Исследование муравьиного алгоритма проводилось путем однократного запуска на всех наборах каждого класса.
Алгоритм выполнял 100 итераций, если не было найдено оптимального решения. Для построения графика полученные результаты сортировались по возрастанию значения целевой функции. Одна точка на графике соответствует усреднению пяти результатов запуска алгоритма.
Во всех случаях для алгоритма, основанного на схеме муравьиных колоний, вкачестве эвристической функции использовалась взвешенная сумма µ 2 и µ 3 .Жадные алгоритмы, с которыми проводилось сравнение, построены по схеме, описанной вразд. 3.5. Последовательность сообщений для размещения в расписание определялась в соответствии с жадным критерием, а не последовательностью сообщений, которая получена муравьиным алгоритмом.4.2. С р а в н е н и е р а з р а б о т а н н о г о а л г о р и т м а с ж а д н ы м а л г о р и т м о м. Нарис.
4 показано сравнение муравьиного алгоритма с жадным алгоритмом по значению целевойфункции (отношение числа размещенных в расписание работ к числу планируемых работ) наклассе исходных данных А. В жадном алгоритме 1 в качестве критерия сортировки сообщенийиспользовалась взвешенная сумма µ2 и µ3 (аналогично задавалась эвристика муравьиного алгоритма), тогда как в жадном алгоритме 2 – взвешенная сумма µ1 и µ2.Из рисунка видно, что муравьиный алгоритм получает решения с более высоким значениемцелевой функции, чем оба жадных алгоритма, при этом при значениях загрузки канала от 0.35 до0.55 разница в качестве решений между муравьиным алгоритмом и жадным алгоритмом 1 отличается значительно.
На этом же отрезке жадный алгоритм 2 показывает лучшие результаты, чемжадный алгоритм 1.На рис. 5 представлено аналогичное сравнение алгоритмов на классе исходных данных Б.На классе исходных данных Б жадный алгоритм 2 показывает более низкое качество решенийпри всех значениях загрузки канала, тогда как качество решений муравьиного алгоритма попрежнему выше, чем у обоих жадных алгоритмов.ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ№62013АЛГОРИТМ ПОСТРОЕНИЯ ОДНОПРИБОРНЫХ РАСПИСАНИЙ95Значение целевой функции1.00.90.80.70.60.5муравьиный алгоритмжадный алгоритм 1жадный алгоритм 20.40.30.20.100.30.40.50.60.70.80.91.0Загрузка каналаРис. 4. Сравнение алгоритмов на классе исходных данных АЗначение целевой функции1.00.90.80.70.60.5муравьиный алгоритмжадный алгоритм 1жадный алгоритм 20.40.30.20.100.40.50.60.70.80.91.0Загрузка каналаРис. 5.
Сравнение алгоритмов на классе исходных данных БЗаключение. В данной работе предложен алгоритм для решения задачи построения расписания обменов по каналу с централизованным управлением, основанный на схеме муравьиных колоний. Рассмотрены два подхода к построению такого алгоритма. Отмечены преимущества второго подхода по сравнению с первым.По результатам исследований на реальных данных муравьиный алгоритм, основанный насоответствии вершин графа сообщениям в исходных данных, показал лучшую точность посравнению с жадными алгоритмами. Из проведенных исследований можно сделать вывод, чторазработанный алгоритм является более универсальным и показывает лучшие результаты, чемсуществующие алгоритмы для данной задачи на всех рассмотренных классах реальных исходных данных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
