Лекция 10 (1121239)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Концепция построения алгоритмов (биологическая модель)

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

Общая схема работы муравьиных алгоритмов

1. Задание начального количества феромона на ребрах графа, количества и начального положения муравьев.

2. Построение муравьями пути (каждый муравей строит путь независимо от остальных).

3. Вычисление целевой функции для каждого пути.

4. Обновление количества феромона на ребрах.

5. Если условие останова не выполнено, то переход к п.2.

Операция построение муравьем пути

• Муравей строит путь, переходя из одной вершины в другую.

• Пройденные муравьем вершины добавляются в табу-список (память муравья), чтобы избежать повторного их посещения.

• Вероятность перехода муравья из i-й вершины в j-ю зависит от количества феромона на данном ребре, значения локальной целевой функции на ребре и состояния табу-списка.

Вероятность перехода k-го муравья из i-й вершины в j-ю на t-й итерации алгоритма рассчитывается по следующей формуле:

_ij(t) - количество феромона на ребре (i,j),

- значение локальной целевой функции на ребре (i,j),

L_k – множество вершин, включенных в табу-список муравья k,

 и  - параметры алгоритма, определяющие важность феромонного следа и локальной целевой функции.

Операция обновление количества феромона на ребрах

T_k(t) – путь, построенный k-м муравьем,

F(T) – целевая функция, определяющая качество пути,

m – количество муравьев,

p[0,1] – коэффициент испарения феромонов.

1. Сведение задачи условной оптимизации к задаче нахождения на графе маршрута, обладающего определенными свойствами.

2. Задание локальной эвристической функции на ребрах графа.

3. Определение алгоритма построения маршрута муравьем (например, определение правила формирования табу-списка вершин).

Модификации муравьиных алгоритмов были разработаны с целью устранить основные недостатки базового алгоритма:

• возможность потери наилучшего найденного решения;

• низкой скоростью сходимости к оптимуму из-за приблизительно равного вклада в обновление феромонов хороших решений из различных областей пространства решений;

• хранением в памяти алгоритма (количество феромона на ребрах) заведомо не перспективных решений.

Максиминная схема алгоритма позволяет решить проблему быстрой сходимости муравьиного алгоритма к локальному оптимуму. Для этого к базовой схеме добавляются три правила:

1. На каждой итерации феромон добавляется только на лучшее из решений, среди найденных на данной итерации;

2. Ограничивается минимальное и максимальное количество феромона на ребрах: ;

3. Изначально количество феромона на всех ребрах равно _max.

Изначально одинаковое количество феромона на всех ребрах уменьшает вероятность выбора одного и того же маршрута разными муравьями.

Условие не позволяет одному относительно хорошему решению доминировать над другими.

Эти ограничения позволяют разнообразить находимые алгоритмом маршруты и избежать попадания в локальный оптимум.

Кроме того, для дополнительного расширения области поиска в максиминном алгоритме применяется механизм «сглаживания следов»: количество откладываемого на ребрах феромона пропорционально величине .

Модификация с поглощением феромона – ещё один метод, применяющийся для расширения области поиска решений. Проходя по ребру при построении пути, муравей поглощает часть феромона на этом ребре:

, где d – доля поглощаемого феромона.

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

Усиление сходимости к оптимуму в его окрестности.

Элитные муравьи.

Элитные муравьи откладывают феромоны только на ребрах наилучшего маршрута найденного сначала работы алгоритма.

Ранговый муравьиный алгоритм.

Найденные на каждой итерации решения ранжируются.

Только (w-1) лучших муравьев и один элитный откладываю феромоны.

Совместное использование с алгоритмами локального поиска

Суть подхода заключается в том, что на каждой итерации муравьиного алгоритма алгоритмы локального поиска пытаются улучшить найденные решения. Обычно применяются локально-оптимальные алгоритмы.

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

Список кандидатов

Используется для решения задач большой размерности.

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

Муравей выбирает вершину не из списка кандидатов только тогда, если он прошел его уже полностью.

Штовба С.Д. Муравьиные алгоритмы: теория и применение// Программирование. 2005. №4.

Задача построения статико-динамических расписаний

Пусть задано множество работ:

SW={a_i=<s_i,f_i,t_i,p_i>|i[1..n]}, где

• [s_i,f_i) – директивный интервал;

• t_i – время выполнения работы;

• p_i – номер раздела работы;

•  и , определяющие, временные затраты на переключение контекста между окнами и резерв свободного времени внутри каждого окна.

Требуется построить расписание, представляющее собой набор окон:

SP={w_i=<S_i,F_i,SW_i>|i[1..m]}, где

• S_i – время открытия окна;

• F_i – время закрытия окна;

• SW_i={aⁱ_j}SW – множество работ, выполняемых внутри окна.

Ограничения корректности расписания:

1. (i,j)[1..m],ij:SW_iSW_j= – множества работ, размещенных внутри разных окон, не пересекаются;

2. i[1..n],j[1..m],a_iSW_j:s_iS_j<F_jf_i – временной интервал окна лежит внутри директивных интервалов работ, выполняющихся в окне;

3. (i,j)[1..n],k[1..m],a_i,a_jSW_k:p_i=p_j – разделы работ, размещенных внутри одного окна, совпадают;

4. (i,j)[1..m],i<j:S_jF_i+ – окна не пересекаются и между любыми двумя соседними окнами есть промежуток не короче времени, необходимого на переключение контекста;

5. – суммарное время выполнения всех работ из одного окна с учетом резерва времени не больше, чем длина окна.

Способ сведения задачи построения статико-динамического расписания к задаче нахождения на графе маршрута

Построим полносвязный граф G=<N,A>, где:

• N={n_i|i[1..n]}{O} – множество вершин;

• A={(n_i,n_j)|i,j[1..n],ij}{(O,n_i)|i[1..n]}> – множество ребер.

Каждой вершине графа соответствует одна из размещаемых работ. Кроме того, добавляется еще одна вершина О, соответствующая началу расписания.

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

Пусть дана последовательность работ SL={a_ik|a_ikSW;i,k[1..n]}. Первый индекс означает номер работы, второй - номер места работы в последовательности. Построим расписание SP по следующему алгоритму:

1. Инициализация расписания: Time=0 – текущая длина расписания; k=1 – номер места размещаемой работы в SL; SW⁰= – список работ в добавляемом окне;

2. Установка начальных параметров окна: S=max(Time,s_ik), F=f_ik – границы добавляемого окна; T=2 – минимальная необходимая длина окна с учетом добавленных работ; R=r_ik – раздел для работ в окне;

3. Обновление значений параметров окна с учетом новой добавляемой работы: S’=max(S,s_ik), F’=min(F,f_ik), T’=T+t_ik;

4. Добавление работы в текущее окно: если r_ik=R , T’F’–S’ (условия корректности не нарушаются), то: S=S’, F=F’, T=T’, SW⁰=SW⁰{a_ik}, k=k+1, если kn (список SL еще не пройден), переход к п.3;

5. Проверка возможности добавления работы в новое окно: если f_ik–F–<t_ik , то k=k+1, если kn переход к п.3 – данная работа не может быть размещена ни в текущее окно, ни в новое окно (дальше в списке еще могут быть работы, которые можно разместить в текущее окно);

6. Закрытие окна: F=S+T – устанавливаем время закрытия окна минимально возможным;

7. Добавление данного окна в расписание: SP=SP{<S,F,SW⁰>};

8. Пересчет длины расписания: Time=F+, k=k+1;

9. Если k  n (список еще не пройден), переход к п.2.

• Условие корректности 1 выполняется, т.к. каждая вершина встречается в построенном маршруте ровно один раз, и соответствующая ей работа размещается лишь в одно окно;

• Условие 2 выполняется, т.к. S’=max(S,s_ik)s_ik; F’=min(F,f_ik)f_ik (п.3);

• Выполнение условий 3 и 5 обеспечивается проверками в п.4 алгоритма – если ограничения нарушаются, работа не размещается в данное окно;

• Условие 4 выполняется, т.к. S_i+1Time (п.2), где Time=F_i+п.8

SW={a₁=<0,11,4,1>,a₂=<4,11,2,1>,a₃=<4,11,2,1>}, ==1

Построенные расписания по различным маршрутам.

Оптимальное расписание.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций