Лекции All in One (1121240), страница 3

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

Текст из файла (страница 3)

Задача:

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

Для частной задачи:

известен оптимальный жадный алгоритм сложности O(n∙log n) [Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000.].

В задаче построения статических расписаний обменов по шине с централизованным управлением присутствуют дополнительные ограничения:

Задача для схемы с подциклами

s₁

f₁

s₂

f₂

s₃

f₃

_φ1

_φ1

_φ1

...

_φ2

_φ2

_φ2

0

2*T

T

3*T

число работ в цепочке

цепочка работ

резерв времени в начале подцикла

резерв времени в конце подцикла

резерв для сдвига

расписания

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

2. время выполнения работ не должно пересекать границы подцикла;

3. время начала цепочки работ относительно начала соответствующего подцикла не должно быть меньше заданного значения;

4. в конце подцикла должен быть зарезервирован интервал времени, длительность которого не меньше, чем заданная доля длительности подцикла;

5. число работ в цепочке не должно превышать заданного значения;

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

Задача для схемы без подциклов

1. число работ в цепочке не должно превышать заданного значения;

2. суммарная длительность выполнения работ цепочки не должна превышать заданного значения;

3. интервал времени между последовательными цепочками должен быть не меньше заданного значения;

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= – множества работ, размещенных внутри разных окон, не пересекаются;

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

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

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

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

Математическая формулировка задачи построения расписания обменов по каналу с централизованным управлением для схемы с подциклами.

Математическая формулировка задачи построения расписания обменов по каналу с централизованным управлением для схемы без подциклов.

Лекция 3

См презентацию

Лекция 4

Л.А. Растригин. Статистические методы поиска.- М.: Наука, 1968.

Основой методов случайного поиска служит итерационный процесс:

_k – величина шага,

  (₁,,_n) – некоторая реализация n-мерного случайного вектора .

min f(X)

g_i(X)  0, i=1,,m (1.1.)

X  S

Н
енаправленный случайный поиск (метод Монте-Карло)

Алгоритмы направленного случайного поиска без самообучения определяются двумя элементами:

1. Алгоритмом выбора пробных состояний на текущем шаге.

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

Алгоритмы направленного случайного поиска:

• алгоритм с парной пробой,

• алгоритм с возвратом при неудачном шаге,

• алгоритм с линейной экстраполяцией,

• алгоритм наилучшей пробы,

• алгоритм статистического градиента.

C1<C2<C3

Построить алгоритм с возвратом при неудачном шаге.

min f(X)

g_i(X)  0, i=1,,m (1.1.)

X  S

Шаг 1. Выбрать:

• параметр точности ε > 0,

• начальный шаг α > 0,

• коэффициент уменьшения шага γ > 1,

• предельное число неудачных попыток K,

• начальное приближение .

Вычислить:

целевую функцию .

Шаг 2. построить алгоритм

Шаг 1. Выбрать:

• параметр точности ε > 0,

• начальный шаг α > 0,

• коэффициент уменьшения шага γ > 1,

• предельное число неудачных попыток K,

• начальное приближение .

Вычислить: целевую функцию .

Шаг 2. Установить счетчик неудачных попыток: j=1.

Шаг 3. Получить реализацию случайного вектора ξ.

Шаг 4. Найти пробную точку: .

Шаг 5. Проверить выполнение ограничений и Y∈S. Если ограничения выполняются, то перейти к шагу 6, иначе к шагу 3 (возможно также считать это неудачной попыткой – переход к шагу 7).

Шаг 6. Вычислить f(Y). Если f(Y) < f(X), то X = Y, f(X) = f(Y), и перейти к шагу 3. Иначе, перейти к шагу 7.

Шаг 7. Увеличить счетчик попыток j = j + 1. Если j ≤ K, то перейти к шагу 3, иначе к шагу 8.

Шаг 8. Проверка условия достижения точности. Если α < ε, то поиск завершить, полагая , . Иначе – положить

α = α/γ и перейти к шагу 2.

Алгоритмы случайного направленного поиска с самообучением заключаются в перестройке вероятностных характеристик поиска, т.е. в определенном целенаправленном воздействии на случайный вектор .

Это достигается введением вектора памяти

- вероятность выбора положительного направления по j-ой координате на k-ом шаге.

Алгоритмы направленного случайного поиска с самообучением определяются тремя элементами:

1. Алгоритмом выбора пробных состояний на текущем шаге.

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

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

Самообучение методом исключения.

Ограничение – число возможных направлений конечно.

Исключаются из рассмотрения «неудачные» направления → повышается вероятность отыскания «удачных» направлений.

Недостаток - большой объем памяти.

Покоординатное экспоненциальное обучение.

Элементы вектора Х изменяются на строго определенную по модулю величину. Она одинакова для всех элементов. Разница лишь в направлении изменения.

Число возможных направлений:

Алгоритм покоординатного самообучения с произвольным законом изменения вероятности.

Пусть

Вид функции может быть различным, но она должна быть:

• монотонной,

• неубывающей.

Линейная зависимость:

Экспоненциальная зависимость:

- шаг, определяющий скорость обучения.

Избежать передетерминирования можно наложив ограничения на область изменения w:

Чувствительность алгоритма к выбору наилучшего направления поиска можно улучшить, учитывая степень участия каждого элемента вектора Х в изменении целевой функции:

Для задач с существенно нерегулярным рельефом целевой функции актуально достаточно быстрое забывание сведений, полученных ранее:

k – параметр забывания

При отсутствии опыта и алгоритм вырождается в равновероятностный поиск:

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

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

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