САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ
Прикладная математики и информатика
Исследования операций и принятия решений в задачах оптимизации,
управления и экономики
Васильев Михаил Александрович
ИММУННЫЙ АЛГОРИТМ СОСТАВЛЕНИЯ РАСПИСАНИЙ
Бакалаврская работа
Научный руководитель:
к. ф.-м. н., доцент Григорьева Н. С.
Рецензент:
к. ф.-м. н., доцент Агафонова И. В.
Санкт-Петербург
2016
SAINT PETERSBURG STATE UNIVERSITY
Applied Mathematics and Computer Science
Operation Research and Decision Making in Optimisation, Control and
Economics Problems
Vasilev Mikhail
Immune algorithms of schedule constructing
Bachelor’s Thesis
Scientific supervisor:
docent Grigorieva N. S.
Reviewer:
docent Agafonova I. V.
Saint Petersburg
2016
Содержание
1 Постановка задачи
4
2 Алгоритмы решения
5
3 Иммунный алгоритм
3.1 Иммунные системы . . . . . . . . . . . . . . . . . . . . . .
3.2 Иммунный алгоритм в общем виде . . . . . . . . . . . . .
6
6
6
4 Алгоритм IASC
4.1 Мутации . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Мутации для корня MT . . . . . . . . . . . . . . .
4.1.2 Мутации для потомков MT . . . . . . . . . . . . .
7
8
8
8
5 Реализация
5.1 Алгоритм IASC — псевдокод . . . . . . . . . . . . . . . . .
9
9
6 Результаты
12
3
Введение
В течение жизни мы регулярно сталкиваемся с расписаниями: транспорт, телевизионные передачи, кино, занятия в школе и институте и
прочее. Для решения таких вопросов мы используем интуитивный подход. Однако в таких отраслях как автоматизация объёмного производства требуется оптимизировать общее время работы. Теория расписаний — как направление в исследовании операций началось с работы
Г. Ганта в 1910, представившим диаграммы для управления проектами. Термин «теория расписаний» был предложен Р. Белламном в 1956
году. Большинство задач теории расписаний являются NP - трудными, поэтому решение задач больших размерностей требует больших
временных затрат. К решению полиномиально неразрешимых задач
применяют эвристики — алгоритмы, дающие приближенное решение
за приемлемое время. Схемы, объединяющие основные эвристические
методы и более эффективно исследующие пространство поиска, называемые метаэвристиками были представлены Ф.Гловером в 1986 году.
В данной работе будет представлен метаэвристический алгоритм решения задачи о расписании, представленной сетевым графиком, его
реализация и применение.
1. Постановка задачи
Рассмотрим задачу из класса MSP (Multiprocessor scheduling problem):
дано n заданий, m процессоров, на множестве заданий задано отношение частичного порядка: ≺.
Каждое задание i имеет время выполнения ti , i = 1 . . . n.
На каждом процессоре в любой момент времени может выполняться не
более одного задания.
Обозначим: ri - время начала выполнения задания i.
Тогда длиной расписания назовём величину C = max {ri + ti }.
i=1...n
Необходимо построить расписание без прерываний, минимальной длины, то есть: C → min.
Интерпретация в виде графа:
G = G⟨V, E⟩ — ориентированный граф.
4
V — множество заданий.
E — множество рёбер, где существование ребра eij означает что задание
i предшествует заданию j : i ≺ j, то есть j может начать выполняться
только после выполнения i.
2. Алгоритмы решения
Задача MSP является NP - трудной в сильном смысле, то есть для
нее не только не существует алгоритмов, решающих задачу за полиномиальное время, но и не существует быстрых алгоритмов, проверяющих что данное решение является оптимальным. Таким образом, для
решения используются приближенные алгоритмы, дающие допустимое
решение за приемлемое время. Одним из подклассов приближенных методов являются метаэвристические алгоритмы, преимуществом которых является исследование большего пространства поиска нахождения
близкого к оптимальному решения.
В общем виде метаэвристические алгоритмы состоят из следующих
компонент:
• Нахождение начального решения
• Поиск окрестностей для решения, определение переходов между
ними
• Отбор кандидатов в решение из окрестностей, определение критериев принятия наилучшего решения
• Определение критерия остановки алгоритма
Метаэвристики состоят из двух категорий: методы локального поиска
и эволюционные методы. Методы первой категории позволяют найти
оптимум, модифицируя текущее решение. Эволюционные алгоритмы
состоят из методов, модифицирующих некоторое множество текущих
решений и последующем выборе лучшего.
5
В данной работе будет рассмотрен один из эволюционных методов
— Иммунный алгоритм, а так же его применение для решения задачи
MSP.
3. Иммунный алгоритм
3.1. Иммунные системы
Иммунитетом живых существ называется устойчивость и сопротивление организма чужеродным агентам и инфекциям, а так же минимизация воздействия от них. Иммунитет — одна из самых сложных систем организма, её способности и особенности положили в основу новое
направления в информационных технологиях — иммунокомпьютинг.
Первые искусственные иммунные сети появились в 1980-х годах в
публикациях Фармера, Паккарда и Перельсона. Первая книга об искусственных иммунных системах, за авторством Д. Дасгупты вышла в
1998 году.
В иммунологии чужеродные организмы называются антигенами.
Для его уничтожения, иммунитет вырабатывает клетки — антитела,
которые связываются с чужеродным агентом и уничтожают его. Основным способом обнаружения антител является сравнение определённых
свойств (лимфоцитов) у различных агентов. Для сравнения используется принцип негативной селекции, заключающийся в том, что свойства, задаваемые иммунитетом, отсутствуют в организме, то есть если
у агента обнаружены эти свойства, то он — чужой. Затем происходит
клональная селекция — организм вырабатывает антитела, максимально похожие на антигенов, для последующего очищения от чужеродных
тел.
3.2. Иммунный алгоритм в общем виде
В общем виде иммунный алгоритм для задачи оптимизации выглядит следующим образом:
Шаг 1: Создаётся популяция π — набор начально сгенерированных
решений, фиксируется лучший экземпляр.
6
Шаг 2: Каждое решение из π клонируется на множество — cl и для
каждого клона из cl применяется мутации — малое изменение решения.
Шаг 3: Среди мутированных клонов ищется лучший экземпляр и, в
случае если он оказывается лучше чем исходное решение в популяции,
то текущее решение в популяции, заменяется на лучший клон. Если не
выполнен критерий остановки алгоритма, то возвращаемся на Шаг 2.
Критерием остановки алгоритма является достижение лимита по времени, достижение лимита по итерациям, отсутствие улучшения решения на протяжении многих итераций.
4. Алгоритм IASC
Для решения задачи MSP автором был разработан алгоритм IASC
(Immune algorithm for schedule constructing) , основной идеей которого является локальное улучшение расписания на множестве «задание — предшественники».
Обозначим:
π - популяция — набор расписаний
M T (i) = {i, j1 , . . . jk | jl ≺ i} — мутационное множество решения i —
есть набор из задания i и множества его предшественников.
Отметим, что M T (i) — дерево с корнем в i.
Поставим в соответствие каждому допустимому решению из π(i) — мутационное множество M T (i). Именно на множестве M T (i) каждое расписание π(i) и будет осуществлять мутации.
Алгоритм:
Шаг 1: Генерируется начальное расписание π0 .
Шаг 2: Создаётся популяция π из n решений π0 .
Шаг 3: Для каждого решения π(i) из π создаётся клон — π(i)r .
7
Шаг 4: На π(i)r осуществляется мутация корня дерева M T (i) — вершины i, высчитывается целевая функция мутированного клона π(i)∗r .
Шаг 5: В случае, если решение π(i)∗r — допустимое, на нем осуществляется мутация потомков дерева M T (i) — вершин j1 . . . jk . В противном
случае, мутации производятся на исходном решении π(i).
Шаг 6: Высчитывается целевая функция мутированного клона π(i)∗c .
Затем в качестве расписания в популяции π(i) берётся решение с лучшим временем из π(i), π(i)∗r , π(i)∗c .
После обхода всей популяции, в случае если не выполнен критерий
остановки алгоритма, переход на Шаг 2.
4.1. Мутации
4.1.1. Мутации для корня MT
1) Пусть i — корень дерева M T , а pr(i) = {j1 . . . jk } — предшественники
задания i.
2) Выбирается базовое задание j1 .
3) Осуществляется перестановка задания i в расписании так, что бы
оно стояло после базового, либо параллельно с ним. Соответственно
задание x, стоящее на выбранном месте, ставится на то место, на котором было i.
3*) В случае, если множество предшественников — пусто, то есть задание i может начать выполняться с момента времени 0, перестановка
осуществляется с любым заданием на первом процессоре
4) На следующей итерации, в качестве базового, берется задание j2 ,
и так далее, и вновь с j1 .
4.1.2. Мутации для потомков MT
1) Выбирается базовая вершина j1 , из множества потомков дерева M T .
Осуществляется перестановка вершины на другой процессор, либо на
8
этот же процессор, но раньше в расписании. Соответственно задание x,
стоящее на выбранном месте ставится на то место, на котором было j1 .
2) На следующей итерации, в качестве базового, берется задание j2 ,
и так далее, и вновь с j1 .
Результатом мутаций решения π(i) — будет последовательное изменение позиции в расписании корневой вершины i и её предшественников.
5. Реализация
Алгоритм IASC был реализован на языке MATLAB.
В качестве исходных данных, были взяты условия из банка Optimal
Schedules for Prototype Standard Task Graph Set [3] — где для большинства задач оптимальное решение известно.
Входные данные для программы соответствуют формату STG (Standard
Task Graph Set):
- 1-я строка: n
- i-я строка: i ti h(i) pr(i), где:
i - номер задания
ti - время выполнения
h(i) - количество предшествующих заданий
pr(i) - список предшествующих заданий
5.1. Алгоритм IASC — псевдокод
9
Algorithm 1 Main function
1: function MAIN(Graph : G)
▷ Генерируем начальное решение
2:
S:=initialSolution(G)
▷ Создаём популяцию
3:
population := copy(S,n)
4:
iteration = 0
5:
while !stop do
6:
iteration++
7:
for i = 1:n do
8:
currentTime := time(population(i))
9:
rootMutate := mutateRoot(population(i))
10:
rootTime := time(rootMutate)
11:
if rootTime == Inf then
▷ Недопустимое решение
12:
childMutate := mutateChild(population(i))
13:
else
14:
childMutate := mutateChild(rootMutate)
15:
end if
16:
childTime := time(childMutate)
▷ Обновляем популяцию
17:
if childTime <= currentTime then
18:
population(i) := childMutate
19:
else
20:
if rootTime <= currentTime then
21:
population(i) := rootMutate
22:
end if
23:
end if
▷ Обновляем индексы мутаций
24:
population(i).rootIndex = rootMutate.rootIndex
25:
population(i).childIndex = childMutate.childIndex
26:
end for
27:
stop = (iteration == 10000)
▷ Критерий остановки
28:
end while
29: end function
10
Algorithm 2 Schedule time function
2:
4:
6:
8:
10:
12:
14:
16:
18:
20:
22:
24:
26:
28:
30:
32:
34:
36:
function TIME(Schedule : A)
▷ Вектор оставшихся времён выполнения заданий
elapsedTimes := [t1 . . . tn ]
currentTime := 0
stop := false
while !stop do
readyTasks = []
▷ Находим задания готовые к выполнению
readyIndexes = []
minTime := Inf
for i = 1:m do
task = A(i,1)
ready := true
for j = 1:length(G(endEdges,i)) do
if ElapsedTimes(endEdges(i,j) != 0) then
ready := false
end if
end for
if ready == true then
readyTasks.add(task)
readyIndexes.add(i)
minTime := min(elapsedTimes(task),minTime)
end if
end for
for j = 1:length(readyTasks) do
elapsedTimes(j) -= minTime
if elapsedTimes(j) == 0 then
A(readyIndexes(j),1).removeFromArray
end if
end for
currentTime += minTime
stop == elapsedTimes.equal(zeros(1,n))
if (readyTasks == [] && !(stop)) then
▷ Недопустимое решение
return Inf
end if
end while
return currentTime
end function
11
6. Результаты
Алгоритм был запущен на пакетах задач из [3] с фиксированным
числом заданий (50, 100, 300) и процессоров (2, 4, 8, 16). Общее число
задач в каждом пакете — 180. Критерий остановки алгоритма — достижение оптимального результата, или достижение 1000-ой итерации.
opt )
Ошибка алгоритма вычислялась по следующей формуле: (faf−f
, где
opt
fa — решение полученное алгоритмом, fopt — оптимальное решение.
Были получены следующие результаты:
N — число заданий
M — число процессоров
MeanItearation — среднее число итераций
MeanTime — среднее время выполнения (в секундах)
MeanError — средняя ошибка
Optimals — процент заданий, в которых оптимальное решение было
найдено.
N
50
50
50
50
100
100
100
100
300
300
300
300
M
2
4
8
16
2
4
8
16
2
4
8
16
MeanIteration
804
910
751
105
920
970
917
440
981
1000
985
800
MeanTime
20
25
29
8
44
65
85
95
120
145
186
260
MeanError
0.1001
0.197
0.147
0.0081
0.125
0.239
0.212
0.035
0.169
0.374
0.280
0.086
Optimals
10
8
25
90
5
3
8
56
2
0
2
19
На представленном ниже графике показана зависимость величины ошибки от количества процессоров, для n = 50, 100, 300. Как видно, с ростом
12
числа заданий, растёт величина ошибки, однако начиная с 4-х процессоров, при фиксированном n, величина ошибки падает.
Для задач больших размерностей из [3] был выбран критерий остановки алгоритма — отсутствие улучшения решения на протяжении 100
итераций. Ошибка алгоритма вычислялась по той же формуле, что и
в задачах малых размерностей. В общем случае, результаты работы
алгоритма для n > 500 удовлетворительные. Ошибка на всех задачах
не превышала 0.64. Аналогично задачам малых размерностей, величина ошибки была прямо пропорциональна числу заданий, и обратно
пропорциональная числу процессоров (m > 4).
Заключение
Алгоритм IASC был запущен на более чем 2-х тысячах задач. Лучшие результаты были получены на задачах с большим числом процес13
соров и малым числом заданий: c ростом числа заданий растёт ошибка
и число итераций, необходимые для достижения оптимального результата, либо определённой планки погрешности вычислений, а с ростом
числа процессоров, несмотря на более трудоёмкие вычисления, алгоритм стабильно выдавал лучшие результаты.
Зачастую, обнаружение локального минимума в решении из популяции закрывало все возможности для улучшения — логика мутаций в
приведённом алгоритме может сойтись на случай, когда каждую итерацию будут производиться модификации, не приводящие к улучшению
результата, и, как следствие, глобальный минимум не будет достигнут.
Простота реализации, универсальность и гибкость иммунных сетей позволяет использовать их для решения большого количества NPтрудных задач. Представленный автором алгоритм IASC является иммунной сетью всего с двумя мутациями, однако погрешности алгоритма
являются невысокими. Дальнейшее расширение сети позволит добиться ещё более точных результатов.
14
Список литературы
[1] В. С. Блюм и В. П. Заболотский Иммунная система и иммунокомпьютинг // Санкт-Петербургский институт информатики и автоматизации РАН стр 2-10
www.smolensk.ru/user/sgma/MMORPH/N-16-html/blum/blum.pdf
[2] О. А. Щербина Метаэвристические алгоритмы для задач комбинаторной оптимизации // Таврический вестник информатики и математики 1(24) 2014 г. стр 3-5
tvim.info/files/56_72_Shcherbina.pdf
[3] Kasahara Lab Waseda University Optimal Schedules for Prototype
Standard Task Graph Set
www.kasahara.elec.waseda.ac.jp/schedule/index.html
[4] Лазарев A. А.и Гафаров E.P. Теория расписаний задачи и алгоритмы // МГУ им. Ломоносова 2011 г. стр 13-25
physcontrol.phys.msu.ru/materials/PosobieLazarev/TeorRasp.pdf
[5] Алексеев Г.А. Иммунный алгоритм для задач составления расписаний // СПбГУ кафедра Исследования Операций 2013 г. стр 2-10
[6] Григорьева Н.С. Теория расписаний методические указания //
СПбГУ кафедра Исследования Операций 1995 г. стр 3-5
15
Отзывы:
Авторизуйтесь, чтобы оставить отзыв