Курс Алгоритмы оптимизации, основанные на методе проб и ошибок (1121255), страница 10

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

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

 HP1,HP2  HP* :  (HP1,HP2) =  (HP2,HP1)Доказательство. Пусть S - цепочка минимальной длины, переводящая расписаниеHP1 в расписание HP2. Тогда  (HP1,HP2)=L(S). Из теоремы 1 (см. раздел 3) следует, чтосуществует обратная допустимая последовательность S1   (HP2), S1(HP2)= HP1 такая, чтоL(S1) = L(S) и поэтому  (HP2,HP1)  L(S1)=L(S)=  (HP1,HP2).

Теперь докажем, чтострогое неравенство:  (HP2,HP1)<  (HP1,HP2) не может выполняться. Если бы этонеравенство выполнялось, то это означало бы существование цепочки операцийS*   (HP2), S*(HP2)=HP1,где L(S*) =  (HP2,HP1) < L(S). В этом случае должнасуществовать и обратная к S* цепочка S*1   (HP1), S*1(HP1)= HP2, причем L(S*1)=L(S*).Это, в свою очередь, означает, что L(S*1)<L(S)=  (HP1,HP2), что противоречитпредположениюоминимальностицепочкиS.Такимобразом,неравенство (HP1,HP2)<  (HP2,HP1) не может иметь места, и всегда верно равенство  (HP1,HP2) = (HP2,HP1).Свойство 3. HP1,HP2,HP3  HP* :  (HP1,HP3)   (HP1,HP2) +  (HP2,HP3)(неравенство треугольника).Доказательство. Пусть S1 - цепочка минимальной длины, переводящая расписаниеHP1 в расписание HP2, и S2 - цепочка минимальной длины, переводящая расписание HP2 врасписание HP3.

По определению метрики L(S1)=  (HP1,HP2) иL(S2)=  (HP2,HP3).Построим цепочку S = S1 + S2. Очевидно, что S(HP1)=HP3 и цепочка S допустима. Приэтом L(S)=L(S1)+L(S2). Искомое неравенство вытекает из неравенства  (HP1,HP3)  L(S).Выполнение свойств 1-3 позволяет заключить, что функция  (HP1,HP2) действительноявляется метрикой в пространстве HP* корректных расписаний.463.6.2. Разбиение исходного пространства решений на областиРазбиение исходного пространства решений на области достигается введениемдополнительной разметки на граф модели поведения прикладной программы H длякаждой области, которая расширяет ограничения на поведение программы.

В качествеисходнойобластиберетсявсепространстворасписаний,разбиваемоенатринепересекающиеся подобласти. Для этого фиксируются два произвольных рабочихинтервала, не связанных транзитивным отношением порядка:в первой области эти рабочие интервалы распределены на разные процессоры;во второй рабочие интервалы обязаны выполняться на одном процессоре, причемвторой рабочий интервал выполняется после первого;в третьей области рабочие интервалы обязаны выполняться на одном процессоре,причем первый рабочий интервал следует после второго.На рис. 3.5. схематично изображен принцип разбиения пространства расписаний наобласти.

На первом этапе выбираются два рабочих интервала (2 и 4), не связанныеотношением порядка, затем пространство решений разделяется на три области, какпоказано на рисунке. Каждой из областей HPi , образующих пространство HP1* 5 , можнопоставитьвсоответствиеграфH i  ( P,   , J , K ) .P-множествовершин,соответствующих рабочим интервалам. Дугам    отвечают связи, определяющиевзаимодействия между рабочими интервалами. Все связи  присутствующие в Hсохраняются в H i . Отношение  задает дуги, устанавливающие дополнительныеограничения на порядок выполнения рабочих интервалов в каждой области.

Отношение   транзитивно и ациклично. Отношения J и K соответствуют ограничениям напривязку рабочих интервалов:два рабочих интервала pi и p j связаны отношением J, ( pi , p j )  J , если онидолжны выполняться на одном процессоре;два рабочих интервала pi и p j связаны отношением K, ( pi , p j )  K , когдаони распределены на разные процессоры.47Рабочие интервалывыполняются на разныхпроцессорах1245673Рабочие интервалывыполняются на одномпроцессоре. Второй послечетвертого1245678Рабочие интервалывыполняются на одномпроцессоре.

Четвертый послевторогоВыбор двух рабочихинтервалов3812456738Рис 3.5. Принцип разбиения пространства расписаний на области..Отношения J и K симметричны и J  K   , аJ транзитивно. Все метки,присутствующие в графе H, сохраняются в графе H i . Расписание HP являетсякорректным в области HPi , если выполнены условия:1) каждый рабочий интервал должен быть назначен на процессор;2) любой рабочий интервал назначен лишь на один процессор;3) частичный порядок    , заданный в HPi сохранен в HP;4) расписание HP должно быть беступиковым. Условием беступиковости являетсяотсутствие циклов в графе HP при неограниченном размере буферов обмена;5) отношение J должно быть сохранено в HP: любые два рабочих интервала,связанные отношением J, должны быть назначены на один и тот же процессор;6) отношение K сохраняется в HP: любые два рабочих интервала, связанныеотношением K, должны быть назначены на разные процессоры.Алгоритм разбиения исходного пространства решений на области.

Введёмследующие обозначения:pPpredи ppred– множества вершин и дуг графа Hсоответствующие рабочим интервалам, которые предшествуют рабочему интервалу p, вppтом числе и транзитивно, Pancи  anc– множества вершин и дуг графа, отвечающиерабочим интервалам, которые следуют за рабочим интервалом p, в том числе и48транзитивно, Pp - множество рабочих интервалов, не связанных с рабочим интервалом pотношением порядка    , в том числе и транзитивно. Для разбиения пространства наподобласти используется алгоритм, состоящий из следующих шагов.Ш а г 1. Задать количество областей разбиения.Ш а г 2. В список графов поместить граф, соответствующий всему пространствурасписаний: H  ( P, , , ) .Ш а г 3.

Выбрать первый граф H  ( P,  , J , K ) из списка и построить три графа для трехнепересекающихся областей следующим образом.Ш а г 3.1. P̂ = P , где P̂ - временное множество рабочих интервалов. В начале каждойитерации оно совпадает с множеством P всех рабочих интервалов.Ш а г 3.2. Выбрать из P̂ рабочий интервал pi , для которого критический пусть в графеpii( Ppred,  ppred, J , K ) минимален и удалить pi из множества P̂ . Если P̂ пусто, закончитьразбиение, сообщив о невозможности его продолжения.Ш а г 3.3. Для выбранного рабочего интервала pi построить множество Ppi .

Если онопусто, перейти к шагу 3.2 и рассмотреть следующий рабочий интервал из P̂ . Если Ppi непусто, то использовать из него рабочий интервал p j , соответствующий минимальномуppкритическому пути в графе ( Pancj ,  ancj , J , K ) .Ш а г 3.4. Построить графы H1 , H 2 , H 3 для областей HP1 , HP2 , HP3 :H1  ( P,  ( pi , p j ), J  ( pi , p j )  ( p j , pi ), K )H 2  ( P,  ( p j , pi ), J  ( pi , p j )  ( p j , pi ), K )H 3  ( P,  , J , K  ( pi , p j )  ( p j , pi ))Ш а г 4. Удалить граф H из списка и добавить три построенные графа H1 , H 2 , H 3 в егоконец. Если количество графов в списке меньше заданного количества областейразбиения, перейти к шагу 3.Данный алгоритм позволяет так осуществлять разбиение на области, чтокритические пути в графах областей разбиения будут существенно отличаться междусобой за счёт выбора на шагах 3.2 и 3.3 рабочих интервалов, отстоящих как можно“дальше” другот друга:первыйрабочийинтервалимеетмалое количествопредшественников, второй является предшественником малого количества рабочихинтервалов.

Это позволяет отбросить большое количество областей (без запуска в них49алгоритма имитации отжига), в которых критический путь больше времени выполнениярасписаний, полученных при запуске алгоритма имитации отжига в других областях.3.6.3. Операции преобразования расписания внутри областиАлгоритмы выполнения операций O1 и O2 должны обеспечивать их замкнутостьвнутри области.Введём следующие обозначения: I1  { pi  P | ( pi , p)  J } – множество рабочихинтервалов, которые должны выполняться на одном процессоре с рабочим интервалом p;I2 {pj P | ( p j , pi )  K } - множество рабочих интервалов, для которых запрещеноpi I1выполнение на одном процессоре с рабочим интервалом p; SP – множество всехпроцессоров; SPHPp - процессор, на который распределён рабочий интервал p в расписанииHP.Алгоритм выполнения операции O1 включается следующие шаги:Ш а г 1.

Случайным образом выбирается рабочий интервал p.Ш а г 2. Строится множество процессоров SP , на которые возможно перенести рабочийинтервал p: SP  SP \pkHP SP.pk I 2Ш а г 3. Случайным образом выбирается процессор из SP и на него переносятся всерабочие интервалы из множества I1 .Алгоритм выполнения операции O2 включается следующие шаги:Ш а г 1. Случайным образом выбирается рабочий интервал p.Ш а г 2. Определяется допустимый диапазон ярусов [ Llow  1, Lhigh  1] .

Этот диапазонвыбирается таким образом, что рабочий интервал p может быть перенесён на любой ярусиз найденного диапазона.Ш а г 3. Ярус из допустимого диапазона выбирается случайным образом и на негопереносится рабочий интервал p.Сложность алгоритмов применения операций O1 и O2равна O(N). Так какоперации преобразования в области совпадают с операциями преобразования на всёмпространстве решений, но применяются к графам с дополнительными дугами, тосохраняется свойство полноты и замкнутости для области.503.6.4. Распределение областей по узлам вычислительной системыРаспределение областей по узлам вычислительной системы осуществляется так,чтобы обеспечить максимально равномерную загрузку процессоров в течении всеговремени работы параллельного алгоритма имитации отжига.

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

Пусть n – количество областей разбиения, а m – количество узловвычислительной системы, осуществляющих поиск решений в областях (n > m). Областиупорядочиваются по критическому пути в графах. Тогда в i-й узел (1  i  m) будутраспределены области с номерами j : j mod m = i (1  j  n). (рис. 3.6.).Proc 1ProcProc 3Proc m123mm+1m+2m+32mn-m-1n-mn-mn-2n-1nРис. 3.6. Распределение областей поузлам вычислительной системы.Для параллельной работы алгоритма и отсечения областей используется следующаястратегия:1) каждый узел осуществляет поиск решений в областях, начиная просматриватьобласти с наименьшим критическим путем;2) в каждой области выполняется фиксированное число итераций. После этогокаждый узел исключает из дальнейшего рассмотрения области с критическим путем,большим, чем время выполнения наилучшего расписания, полученного этим узлом;3) если было отсечено заданное количество областей, то узел инициирует обмен,передавая время наилучшего расписания остальным узлам, которые в свою очередьвыполняют отсечение областей с учетом переданного им времени;514) узел производит отсечение области, если в течение заданного числа итераций вданной области не произошло уменьшение целевой функции (времени выполнениярасписания).

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

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

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