Составление расписания для распределенных вычислительных сетей в условиях неточных данных

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Составление расписания для распределенных вычислительных сетей в условиях неточных данных

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

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

С популяризацией мягких вычислений одним из направлений современных исследований является разработка методов составления расписаний в условиях неопределённости. Планирование в рамках случайных величин подробно рассмотрено в [1]. В[2] показано применение комбинации нейронных сетей с генетическими алгоритмами для решении различных задач со случайными, нечёткими и неточными данными в условии.

Представив процесс распределения нагрузки для минимизации времени обработки независимых единиц в РВС как задачу распределения работ по исполнителям, работающих параллельно, и допустив, что

· производительность исполнителей различна,

· каждая работа неделима и независима,

· процесс выполнения работы непрерывен,

· в некоторый момент времени исполнитель может выполнять только одну работу,

· работа не требует предварительных операций,

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

2. Постановка задачи

Пусть дано m исполнителей, обладающих разной производительностью, и работ, сгруппированных в p типов. Каждый исполнитель k?{1,…, m} может выполнить любую работу, но для выполнения работы i-го типа исполнители могут затрачивать разное время. Этот факт учитывается технологической матрицей

В классическом случае, где t_ik?R, задачу можно свести к задаче дискретного программирования следующего вида

сеть информационный алгоритм

3. Общая схема генетических алгоритмов

Задача (2) относится к задачам дискретной оптимизации и является NP-полной [1], из чего следует, что универсального алгоритма, отличного от полного перебора, не существует. Общий подход к решению данной задачи может быть основан на нахождении субоптимального решения, что позволит экономить вычислительные ресурсы. Для этого целесообразно использовать генетические алгоритмы (ГА) - метод эвристического поиска решения задач оптимизации, основанный на имитации различных механизмов естественного отбора. Идея алгоритма заключается в манипулировании имеющейся совокупностью закодированных решений (хромосом) с помощью ряда генетических операторов и получении новых хромосом, являющихся новыми вариантами решения [3]. В отличие от случайного поиска, ГА использует информацию, накопленную в процессе эволюции (поиска) от предыдущих поколений. ГА не накладывают ограничений на вид целевой функции и область определения задачи, однако параметры работы часто подбираются эмпирически [4].

Реализация ГА обычно начинается с поиска способа кодирования хромосомы - однозначного представления варианта решения оптимизационной задачи. Каждая хромосома состоит из набора генов.

Общая схема генетического алгоритма включает следующие этапы [5]:

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

· Оценка степени приспособленности хромосом в популяции. Осуществляется на основе функции приспособленности, которая строится с учётом целевой функции задачи.

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

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

· Выполнение генетических операторов. Основными операторами являются: кроссинговер и мутация.

· Создание и оценка новой популяции. Возврат к шагу2.

Оператор кроссинговера (скрещивания)- конструкция ГА, отвечающая за создание потомков из хромосом родителей. Существует большое количество разновидностей оператора скрещивания[6-7].

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

Рис. 1. Пример работы одноточечного кроссинговера

При увеличении точек разрыва увеличивается количество способов обмена участками хромосом между особями, но если точек становится слишком много, нарушается производство приспособленного потомства [6].

Если гены хромосомы содержат бинарную информацию, то допускается использование универсального оператора кроссинговера. Вместо использования разрезающей точки (точек), используется бинарная маска, которая либо задаётся заранее, либо генерируется случайным образом. Её длина равна длине хромосомы. Потомки выводятся путём сложения по модулю 2 родителей с маской [6]. На рис. 2 представлен пример универсального кроссинговера.

Рис. 2. Пример работы универсального кроссинговера.

Оператор мутации - конструкция ГА, отвечающая за создание потомка из хромосомы родителя или её части. Существует масса операторов мутации. Например, при одноточечной мутации случайно выбирается ген в родительской хромосоме, который меняется местами с соседним геном, получая хромосому потомка. Популярным способом мутации является полное замещение родительской хромосомы случайно сгенерированной хромосомой потомка.

ГА может включать дополнительные операторы. Наиболее распространенные - оператор редукции, нацеленный на сокращение популяции вместе с исключением неудачных решений, и оператор рекомбинации, определяющий процессы, связанные со сменой поколений (итерации работы ГА) и другие[6].

4. Решение дискретной задачи планирования

Пусть для R_m||C_max за каждой задачей закреплён свой ген, значение которого отвечает за номер исполнителя. Сформировав и объединив цепи из работ одного типа, получим представление расписания в виде хромосомы

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

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

В данном случае видно, что две хромосомы представляют одинаковое решение. Так, например, в обоих случаях для работы типа 1 c₁₁=8, c₁₂=2, c₁₃=1, c₁₄=0. Аналогичная ситуация с работой типа 2: c₂₁=4, c₂₂=5, c₂₃=2, c₂₄=1. Очевидно, что значение целевой функции тоже будет одинаковым. Для уничтожения дубликата решения (родственника) перед скрещиванием одна из родительских особей замещается новой, со случайно сгенерированной хромосомой, после чего выполняется одноточечный кроссинговер.

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

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

Время работы генетического алгоритма будет ограничено числом итераций.

5. Задача составления расписания в условиях неточных данных

Предположим, что исходная информация для задачи R_m||C_max является приближенной и выражается в виде интервальных чисел, которые относятся к классу неточных величин. Они являются самым общим способом представления неопределённой информации о времени выполнения работ.

Согласно[8] под интервальным числом[a] будем понимать вещественный отрезок , где . Распространёнными характеристиками интервального числа являются ширина числа и его медиана . При получим обычное число [8].

Пусть исходные данные представлены в виде интервальной технологической матрицы - матрицы, компоненты которой представляют собой интервальные значения времени выполнения работ. Для решения задачи планирования на основе ГА, предлагаются следующие подходы, позволяющие получить субоптимальный план.

Сведение задачи к её дискретному варианту подразумевает, что в широком смысле можно получить с помощью вычисления б ?[0,1] значений элементов по формуле[2]

При различных получим следующие варианты планирования:

· б>1, пессимистичное планирование (оптимизация по максимальному времени выполнения работ);

· б>0, оптимистичное планирование;

· б>0,5, в результате чего , планирование по центральным величинам;

· б~б_ik, в результате чего формируется отдельная матрица , по которой каждому элементу [t_ik] ставится в соответствие свой коэффициент б_ik для преобразования .

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

· проблема обучения- очевидно, что сразу оптимальные коэффициенты б_ik получить не удастся, следовательно их подбор превращается в отдельный итерационный процесс, причём с учётом изменений условия задачи R_m||C_max; кроме того, требуется активное выполнение пробных действий, явным образом организованный поиск методом проб и ошибок;

· проблема оценки - сложно определить, насколько текущее значение б_ik лучше или хуже другого; проблема усугубляется тем, что .

Независимо от выбора б неопределённость об времени выполнения работы «ликвидируется» ещё до входа в ГА, в результате чего он оперирует уже вещественными числами.

Другой способ основывается на том, что решением задачи(2), в конечном итоге, является хромосома-победитель, выявленная из всей популяции с помощью функции приспособленности. Однако ранжировать хромосомы при наличии неопределённости в ней можно различными способами. Пусть ГА оперирует непосредственно интервальными числами. В силу простоты функции приспособленности достаточно опираться на интервальную арифметику [8].

Пусть функция приспособленности для хромосомы-решения C, содержащая неопределённость имеет вид (учитывая c_ik?0)

Для реализации оператора используется распространённый способ сравнения интервальных чисел

зачастую при б=0.5 [8-9]. Однако конкретно для задачи(2) допустимм вариант

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

6. Вычислительный эксперимент

Для реализации вычислительного эксперимента разработана компьютерная программа на языке C с применением технологии параллельного программирования OpenMP. Целью вычислительного эксперимента заключается в анализе влияния способа сравнения хромосом на конечное расписание. Сравним стандартный способ (7) при б=0.5 и способ на основе приоритета (8).

Пусть имеется m=3 исполнителя и n=500 работ, сгруппированных в p=4 типов: n₁=180, n₂=80, n₃=140, n₄=100. Зададим технологическую матрицу:

Случайным образом сгенерировав начальную популяцию из10000 особей, ГА выполнил 35000 итераций. При переходе от одной итерации к другой случайным образом мутировали 32 особи. В результате были получены следующие субоптимальные решения:

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

Сравним два полученных плана. Отметим, что . Видно, что при распределении работ по плану C₂, построенному с применением приоритетного сравнения, снижаются максимально возможные временные затраты, а также формируется расписания с более чёткими границами по времени, что следует из .

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

Этот способ в сочетании с нейронными сетями позволяет получить гибридный алгоритм, сочетающий эффективность и адаптивность к изменяющимся условиям работы РВС.

Литература

сеть информационный алгоритм

1. Pinedo M.L. Scheduling: theory, algorithms, and systems. - Springer Science & Business Media, 2012.

2. Лю Б. Теория и практика неопределенного программирования / Б. Лю; Пер. с англ. - М.: БИНОМ. Лаборатория знаний, 2014. - 416 с.

3. Панченко Т.В. Символьная модель ГА // Генетические алгоритмы: учебно-методическое пособие. - Астрахань: Издательский дом «Астраханский университет». - С. 41-50.

4. Родькина М.Б. Разработка эволюционных алгоритмов для решения задач теории расписаний в условиях неопределённости: Автореф. дис. канд. техн. каук. - Воронеж, 2013. - 16 с.

5. Пегат А. Самоорганизация и самонастройка нечётких моделей методом поиска // Нечёткое моделирование и управление. - 2-е изд. - М.: БИНОМ. Лаборатория знаний, 2013. - С. 530-538.

6. Гладков Л.А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. - М.: ФИЗМАТЛИТ, 2006. - 320 с.

7. Каширина И.Л. Введение в эволюционное моделирование. - Воронеж, 2007. - 39 с.

8. Добронец Б.С. Интервальные числа // Интервальная математика: учеб. пособие. - Красноярск: Краснояр. гос. ун-т. - С. 31-33.

9. Левин В.И. Сравнение интервальных чисел и оптимизация систем с интервальными параметрами // Автомат. и телемех. - №4. - 2004. - С. 133-142.

Размещено на Allbest.ru