Диссертация (Разработка моделей и алгоритмов составления оптимальных расписаний выполнения программных модулей в вычислительной сети на основе эволюционного подхода), страница 7

Анализ основных подходов составления оптимальных расписанийвыполнения программных модулей в распределённых системах обработкиданныхТ.к. задачи синтеза оптимальных расписаний для выполнения комплексаИЗЗ в РСОД относятся к классу NP-сложных, то для их решения применяютсяметоды на основе эвристик.Учитывая NP-сложность, алгоритмы, в основе которых присутствуетполный перебор всех решений, для нахождения оптимального не приемлемы. Вомногих случаях такие алгоритмы являются нереализуемыми, т.к. требуют оченьбольших временных и вычислительных ресурсов.

Такие условия вызываютнеобходимостьпримененияалгоритмовнаосновеэвристик.Далеерассматриваются существующие на сегодняшний день эвристические методы,применяемые в системах планирования и распараллеливания.44Эвристические методы находят не самое эффективное решение, априближенное.Зачастуюприменяются«any-time»алгоритмы,которыепостепенно улучшают текущее приближенное решение. Примером такихалгоритмов может послужить метод «границ и ветвей».Однимизподмножествэвристическихметодовявляетсяклассэволюционных методов.Эволюционные методы являются приближенными методами решениязадач оптимизации и структурного синтеза.

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

Данный алгоритм был предложен бельгийским учёнымисследователем Марко Дориго. В его основе лежит математическая модельповедения муравьёв в колонии, при осуществлении поиска пищи.В процессе эволюции муравьи в муравейнике образовали сложнуюструктурувзаимодействия,называемую«коллективнымразумом».Припередвижении муравей выделяет особые химические вещества – феромоны.Пройдя по определённому пути к месту, где находится пища, муравей опятьвозвращается к этому месту.

Если путь является наиболее коротким, феромонымуравья не успевают рассеиваться и след становится более выраженным исильным. Другие муравьиные особи устремляются по данному пути, и тем самымещё больше усиливают феромовый след. Остальные направления движенияпостепенно рассеиваются.45Метод реализуется с помощью алгоритма, в котором каждая итерацияассоциируется с запуском т.н. искусственного муравья. Муравей пытается всоответствии с определёнными правилами найти максимально эффективныймаршрут, ведущий к кормушке (к экстремуму функции), основываясь наинформации, которую оставили его предшественники.Все муравьиные алгоритмы, независимо от модификаций, представляютследующую последовательность шагов:1.

Создание группы муравьёв.2. Поиск решений.3. Обновление феромонов.4. Дополнительные действия [34].Каждый из муравьёв выполняет следующую цепочку шагов. На каждом iтом шаге, происходит выбор условия j для установки в слот i расписания,используя «вероятности перехода».Преимуществом муравьиных алгоритмов, несомненно, является то, чтоони опираются на данные полученные всей колонией, а не только предыдущегопоколения.Алгоритм имитации отжига был заимствован из наблюдений припроведенииисследованийизменениясостоянияатомовметаллов,приосуществлении процесса отжига.

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

глобальногоминимума.46Переходя к математическому моделированию, требуется, что в решаемойзадаче синтеза оптимального расписания будет играть роль энергии и состояниекаких объектов она сможет характеризовать. Один из вариантов – этопредставление целевой функции в виде энергии. Такой вариант может бытьоснован на штрафах, которые добавляются к текущему расписанию за каждоеприсутствие в нём неэффективных моментов, а низкоэнергетическое состояниебудет представлять оптимальное расписание.В общем виде алгоритм имитации отжига для решения задач составленияоптимальных расписаний можно представить в виде следующей схемы:1. Первая итерация представляет генерацию исходного корректногорасписания, которое считается лучшим на текущее время.2. На этом шаге задаётся начальное, высокое значение температуры иоперации мутации расписания.

Мутация расписания обеспечивается с помощьюследующих действий: изменение времени выполнения потока; изменениепроцессора, выполняющего поток; обмена мест двух потоков в расписании.3. На основе введённых операций мутации и текущего лучшего решенияпроисходит генерация нового корректного расписания, немного отличающегосяот текущего.4. Поиск изменения целевой функции:- если решение не ухудшилось, то новый вариант расписания становитсялучшим на текущий момент;- если решение ухудшилось, то новое расписание становится текущимтолько с некоторой вероятностью. Соответственно, с максимальной вероятностьюпредыдущее расписание сохраняется в качестве текущего.Таким образом, допускается увеличение целевой функции, но вероятностьэтогоэкспоненциальноуменьшается.Данныйподходпредназначендляпреодоления локальных экстремумов.5.

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

Если критерий останова не выполнен, осуществляется переход к п. 3.Критериями останова могут быть следующие условия: выполнение заданного числа итераций. выполнение заданного числа итераций без улучшения значения целевойфункции на заданное значение.Для увеличения эффективности данного алгоритма можно сохранять nлучших решений, а также m последних расписаний, что обеспечиваетпредотвращение зацикливания процесса синтеза оптимального расписания.Для повышения точности получаемого с помощью алгоритма решениятребуется обеспечить более медленное изменение температуры. При этомалгоритм начинает намного тщательнее исследовать пространство поискарешений, но отрицательным моментом будет существенное увеличение времениего работы.

В связи с этим функцию температуры необходимо подбиратьиндивидуально для решения каждой конкретной задачи [35].Следующий эволюционный метод носит название «метод роя частиц».Данный метод впервые был предложен в 1995 г. в работе Р. Эберхарта и Д.Кеннеди.В этом методе частицы, в каждый момент времени, имеют в пространствепараметров задачи некоторое положение и скорость. Правила, по которымчастица меняет свое положение и скорость, определяются на основе вычисленияцелевой функции частицы.

В основе классического метода роя частиц лежитследующий принцип: на каждой итерации для определения следующегоположения частицы учитывается информация о наилучшей частице от «соседей»и информация о данной частице на том шаге, когда этой частице соответствовалонаилучшее значение целевой функции. Так же существуют модификации48классической модели, учитывающие значения целевой функции всех частиц роя,в некоторых моделях частицы группируются в несколько роев и т.д.В классической реализации метода роя частиц, использующей метрическоешкалирование, следующая позиция частицы с идентификатором i определяется поформуле:xi(t+1) = xi(t)+ vi(t+1),(1.3.1)где vi(t+1) – скорость передвижения частицы с идентификатором i изпозиции xi(t) в позицию xi(t+1).Начальное состояние определяется как: xi(0), vi(0).

Данная формулапредставлена в векторной форме. Лучшие частицы с точки зрения целевойфункции объявляются «центром притяжения». Векторы скоростей всех частицустремляются к этим центрам.Алгоритм роя частиц находит очень широкое применение, так как поэффективности он может конкурировать с другими эвристическими методами, аалгоритмическая простота уменьшает сложность реализации [36].Несомненнымитипичнымипредставителямиклассаэволюционныхметодов являются генетические алгоритмы (ГА).ГА – один из эвристических методов приближённого поиска, в основекоторого лежит эволюционная модель. Этот метод используется в разныхобластях, где невозможно найти лучшее решение и требуется найти решениемаксимально приближенное к оптимальному [35], [37] ,[38].На сегодняшний день существует много разновидностей этого метода,таких как ГА с дублированием узла [39], ГА с миграцией элитных особей [40],гибридный ГА [41], ГА с мульти-популяцией [42], ГА с сохранением видов [43] идр.Данное исследование посвящено именно этой группе методов на основеэволюционного подхода, в связи с их распространённостью при составленииоптимальных расписаний в РСОД.49Далее рассматривается ГА в классическом виде.

Алгоритм основан напредставлении решений в виде хромосом, элементы которых называются генами.Популяцию представляет множество хромосом.ГА в классическом виде (рисунок 1.3.1) представляет два генетическихоператора рекомбинации: оператор скрещивания (синонимы: кроссинговер,кроссовер) и оператор мутации. Помимо основных классических операторовтакже могут находить применение и другие, такие как: инверсии, плагиата(plagiarism operator), транспозиции, вставки-удаления. В результате рекомбинациивозникаютновыесовокупностигенов.Такимобразом,производитсяисследование пространства поиска решений.Рис. 1.3.1. Блок-схема классического генетического алгоритма50После обработки хромосом генетическими операторами скрещивания имутации, особи новой популяции выбираются оператором селекции.