Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 19
Текст из файла (страница 19)
После того, как все муравьизавершили построение путей, обновляется количество феромона на ребрах:m ij t 1 1 p ij t ij , k t k 1 F Tk t , i, j Tk t ij , k t 0, i, j Tk t Здесь Tk(t) – путь, построенный k-м муравьем, а F(T) – целевая функция,определяющая качество пути, m – количество муравьев, p[0,1] – коэффициент испаренияферомонов. Испарение феромонов вводится для избегания попадания алгоритма влокальный оптимум, когда первый найденный путь с относительно хорошим значениемцелевой функции становится единственно значимым.Основными задачами, которые необходимо решить для того, чтобы использоватьмуравьиный алгоритм для решения конкретной задачи условной оптимизации, являются:1.
Сведение задачи условной оптимизации к задаче нахождения на графемаршрута, обладающего определенными свойствами.2. Задание локальной эвристической функции на ребрах графа.3. Определениеалгоритмапостроениямаршрутамуравьем(например,определение правила формирования табу-списка вершин).955.3. Модификации муравьиных алгоритмовМодификации муравьиных алгоритмов были разработаны с целью устранитьследующие основные недостатки базового алгоритма:возможность потери наилучшего найденного решения;низкой скоростью сходимости к оптимуму из-за приблизительно равноговклада в обновление феромонов хороших решений из различных областейпространства решений;хранением в памяти алгоритма (количество феромона на ребрах) заведомоне перспективных решений.Решить эти проблемы путем выбора соответствующих значений коэффициентаиспарения феромонов (p) и параметров , , определяющих важность феромонного следаи локальной целевой функции удается не для всех задач.5.3.1.
Максиминный алгоритмМаксиминная схема алгоритма позволяет решить проблему быстрой сходимостимуравьиного алгоритма к локальному оптимуму. Для этого к базовой схеме добавляютсятри правила:1. На каждой итерации феромон добавляется только на лучшее из решений, срединайденных на данной итерации;2. Ограничивается минимальное и максимальное количество феромона на ребрах: ij [ min ; max ] ;3. Изначально количество феромона на всех ребрах равно max.Изначально одинаковое количество феромона на всех ребрах уменьшает вероятностьвыбора одного и того же маршрута разными муравьями, а условие ij [ min ; max ]непозволяет одному относительно хорошему решению доминировать над другими. Такимобразом, эти ограничения позволяют разнообразить находимые алгоритмом маршруты иизбежать попадания в локальный оптимум. Кроме того, для дополнительного расширенияобласти поиска в максиминном алгоритме применяется механизм «сглаживания следов»:количество откладываемого на ребрах феромона пропорционально величине max ij .965.3.2.
Модификация с поглощением феромонаМодификация с поглощением феромона – ещё один метод, применяющийся длярасширения области поиска решений. Проходя по ребру при построении пути, муравейпоглощает часть феромона на этом ребре: ij ij (1 d ) , где d – доля поглощаемого феромона.Таким образом, ребро, по которому уже прошел один из муравьев, сразу теряет своюпривлекательность для других муравьев, что заставляет их выбирать другие ребра.5.3.3.
Совместное использование с алгоритмами локального поискаСуть подхода заключается в том, что на каждой итерации муравьиного алгоритмаалгоритмы локального поиска пытаются улучшить найденные решения. Обычноприменяются локально-оптимальные алгоритмы.Для задачи коммивояжера, часто используются алгоритмы локального поиска,которые улучшают маршрут заменой заданного количества ребер.5.4. Муравьиные алгоритмы для решения задачи построения статикодинамических расписания (два способа представления задачи)Математическая постановка задачи приведена в разделе1.4.2.5.4.1. Первый способ сведения задачи построения статико-динамическогорасписания к задаче нахождения на графе маршрутаПостроим полносвязный граф G=<N,A>, где: N={ni|i[1..n]}{O} – множество вершин; A={(ni,nj)|i,j[1..n],ij}{(O,ni)|i[1..n]}> – множество ребер.Каждой вершине графа соответствует одна из размещаемых работ.
Кроме того,добавляется еще одна вершина О, соответствующая началу расписания.Муравьиный алгоритм строит маршруты, в которых все вершины включены ровноодин раз. Каждому такому маршруту соответствует последовательность работ, такая что,в нее включены все работы из исходно заданного набора и каждая работа включена вданную последовательность один раз.
Опишем алгоритм для построения расписания потакойпоследовательностиработ.ПустьданапоследовательностьработSL={aik|aikSW;i,k[1..n]}. Первый индекс означает номер работы, второй - номер местаработы в последовательности. Построим расписание SP по следующему алгоритму:4. Инициализация расписания: Time=0 – текущая длина расписания; k=1 – номерместа размещаемой работы в SL; SW0= – список работ в добавляемом окне;975. Установка начальных параметров окна: S=max(Time,sik), F=fik – границыдобавляемого окна; T=2 – минимальная необходимая длина окна с учетомдобавленных работ; R=rik – раздел для работ в окне;6. Обновление значений параметров окна с учетом новой добавляемой работы:S’=max(S,sik), F’=min(F,fik), T’=T+tik;7. Добавление работы в текущее окно: если rik=R , T’F’–S’ (условиякорректности не нарушаются), то:S=S’, F=F’, T=T’, SW0=SW0{aik}, k=k+1,если kn (список SL еще не пройден), переход к п.3;8.
Проверка возможности добавления работы в новое окно: если fik–F–<tik , тоk=k+1, если kn переход к п.3 – данная работа не может быть размещена ни втекущее окно, ни в новое окно (дальше в списке еще могут быть работы,которые можно разместить в текущее окно);9. Закрытие окна: F=S+T – устанавливаем время закрытия окна минимальновозможным;10. Добавление данного окна в расписание: SP=SP{<S,F,SW0>};11. Пересчет длины расписания: Time=F+, k=k+1;12. Если k n (список еще не пройден), переход к п.2.Расписание, построенное при помощи данного алгоритма, будет удовлетворятьвсем условиям корректности:13. Условие корректности 1 выполняется, т.к. каждая вершина встречается впостроенном маршруте ровно один раз, и соответствующая ей работаразмещается лишь в одно окно;14. Условие 2 выполняется, т.к.
S’=max(S,sik)sik; F’=min(F,fik)fik (п.3);15. Выполнение условий 3 и 5 обеспечивается проверками в п.4 алгоритма – еслиограничения нарушаются, работа не размещается в данное окно;16. Условие 4 выполняется, т.к. Si+1Time (п.2), где Time=Fi+п.8Такимобразом,припомощиописанногоалгоритмапозаданнойпоследовательности работ однозначно строится корректное расписание. Фактически,данный алгоритм устанавливает соответствие между пространством расписаний ипространствомпоследовательностейработ,которое,всвоюочередь,являетсяпространством поиска для муравьиного алгоритма.Недостатком данного подхода является то, что множество корректных расписанийсодержит больше элементов, чем множество последовательностей работ, т.е.
существуютрасписания, для которых не существует соответствующих им цепочек работ. Причина98заключается в том, что последовательность работ не задает однозначно распределениеработ по окнам. Более того, можно привести пример задач, для которых оптимальноерасписание не будет принадлежать к пространству поиска муравьиного алгоритма.Пример исходных данных такой задачи: SW={a1=<0,11,4,1>,a2=<4,11,2,1>,a3=<4,11,2,1>},==1(рис.5.2.).Прямоугольникамипоказаныдирективныеинтервалы,заштрихованными областями – время выполнения работ. Раздел у всех работ одинаковый.Рисунок 5.2.
Исходные данные.На рис. 5.3. показаны все возможные расписания, которые могут быть построеныприведенным алгоритмом по различным маршрутам в графе. Все эти расписания неявляются оптимальными.Рисунок 5.3. Построенные расписания.При этом расписание, в котором все работы размещены, существует (рис.5.4.).Рисунок 5.4. Оптимальное расписание.Можновыдвинутьгипотезу,чтонесуществуетдетерминированногополиномиального алгоритма A построения расписания по маршруту в графе G такого, чтодля (SW,,):SL:A(SL)=SP0, где SP0 – оптимальное расписание. Т.е.
не существуетдетерминированного полиномиального алгоритма, который для любой частной задачи могбы построить оптимальное расписание по одному из возможных маршрутов. По крайне99мере, пока такой алгоритм найти не удалось, однако нет и доказательства, что такогоалгоритма не существует.В качестве локальной целевой функции на ребрах графа G используется следующая 1 1 , если 0функция: ij 0 , если 0, где f j t j si ti – разница во времени междуминимальным временем завершения i-й работы и максимальным временем начала j-йработы. Если θ < 0, то j-я работа не может идти в расписании после i-й.
В противномслучае, чем меньше значение θ, тем меньше максимальный возможный промежуток врасписании между работами, соответствующими вершинам i и j, и тем больше значениелокальной целевой функции.Целевая функция для оценки качества маршрута задается отношением количестваработ, размещенных в расписание без нарушения условий корректности, к количествуисходных заданных работ. Значение данной функции вычисляется алгоритмом, строящимрасписание по маршруту.5.4.2. Второй способ сведения задачи построения статико-динамическогорасписания к задаче нахождения на графе маршрутаЧтобы устранить недостаток первого подхода, предлагается использоватьизмененное представление задачи в виде поиска маршрута на графе, в котором каждойработе будет соответствовать не одна, а две вершины.
Появление в маршруте первой изэтих вершин будет означать размещение работы без закрытия текущего окна. Другаявершина будет соответствовать размещению работы с закрытием окна. Соответственно, вмаршруте может присутствовать только одна вершина из каждой такой пары.Построим граф G’=<N’,A’>, гдеN’={ni+,ni–|i[1..n]}{O} – множество вершин; вершина ni+ соответствуетразмещению работы без закрытия текущего окна, ni– – размещению работы с закрытиемокна.