Пупков К.А., Коньков В.Г. - Интеллектуальные исследования (Современнаяя теория управления) (1072100), страница 23

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

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

Обзор используемых методов поиска оптимального отображения графов алгоритмов на графы ВС с учетом информационного взаимодействия в ВС показал, что большинство их к решению больших задач отображения (n > 100, p > 10) не подходит из-за большой сложности этих методов. К тому же, точность многих приближенных методов часто сильно падает при увеличении размерности задачи. Как отмечается в ряде работ, единственно приемлемым способом решения больших задач отображения является, по-видимому, использование именно стохастических подходов и алгоритмов. В этом смысле, интересным подходом является использование метода имитации отжига, хорошо зарекомендовавшего себя при решении многих задач дискретной оптимизации [87].

1. Стохастический метод попарной оптимизации подграфов

1. Описание метода.

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

Алгоритм А1:

1. Выбираем случайное начальное разрезание R, вычисляем J = J(R);

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

3. Случайно выбираем пару вершин l и m в этих подграфах (т.о. перебираются все пары вершин в этих подграфах); меняем местами эти вершины, получаем новое разрезание R’, вычисляем J’ = J(R’);

4. Если J’ > J, т.е. произошло увеличение функционала, то переходим к 3, иначе за R обозначаем R’ и переходим к 3;

5. Если зафиксирован выход функционала J(R) на стационарное решение, то конец алгоритма, иначе переходим на 2.

Описанный алгоритм является итерационным. Внешние итерации связаны с попарным просмотром подграфов, а внутренние - с просмотром вершин в этих подграфах. Переход от разрезания к разрезанию происходит, если выполняется условие перехода 5.

1. Численное исследование алгоритма.

На основе метода А1 была написана программа, с помощью которой было проведено численное исследование метода А1. В качестве графов алгоритма исследовались, в основном, двоичные деревья с числом вершин на верхнем уровне N. В качестве ВС - полносвязные графы, имеющие p вершин.

На рис. 42 построена зависимость времени работы программы T (в секундах) от N, при p = N, т.е. при одновременном увеличении и размерности графа N, и числа подграфов разрезания. Полученные зависимости позволяют сделать вывод, что сложность алгоритма А1 есть 0(pN²).

Исследование на точность метода проводилось для алгоритмов сдваивания с N = 8 при разрезании их на p = 4, 8 подграфов. Было проведено по 70 опытов для каждого случая. На рис. 43 изображена функция распределения f относительной погрешности для этих двух случаев.

Рис. 42. Зависимость времени работы алгоритмов А1 (1) и А3 (2) от размеров графа сдваивания N, при p = N.

Рис. 43. Функция распределения f относительной погрешности  алгоритма А1 при разрезании графа сдваивания с n = 15 на 1) p = 4; 2) p = 8 подграфов.

Проведенное исследование позволяет сделать следующие выводы. Как минимум кубическая (по n и p) сложность метода не позволяет использовать его при больших графах ГА и большом числе подграфов разрезания. Сходимость метода к решению не является плохой (плоской), однако, очень неудовлетворительной является точность получаемых решений. Этот недостаток, однако, может быть в некоторой степени сглажен за счет специального выбора начального разрезания.

1. Метод выбора начального разрезания.

Рис. 44. Функция распределения f относительной ошибки  алгоритма А3 при разрезании графа сдваивания с n = 15 на 1) p = 4; 2) p = 8 подграфов.

Метод использует локальные характеристики графа ГА - связность каждой вершины и ее вес. Общая схема метода такова.

Алгоритм А2:

1. Выбираем равновероятно вершину с номером 1;

2. Составляем вектор g = {g_i, i = 1, p} связанности данной вершины со всеми подграфами;

3. Выбираем подграфы, связность которых с 1 равна;

4. Вершину 1 заносим в тот из выбранных подграфов, который имеет наименьший вес и переходим на 1.

Алгоритм заканчивает работу, когда все вершины распределены по подграфам. Было проведено аналогичное исследование алгоритма А3 (метод А1 с выбором начального разрезания А2) на сложность, сходимость и точность. Результаты исследования представлены на рис. 42, 44. Выигрыш по сравнению с А1 очевиден. Уменьшилась сложность алгоритма. Улучшилась точность метода. Зато, оказалась очень плоской зависимость функционала J по итерациям. Это объясняется тем, что алгоритм А2 в большинстве случаев сразу приводит к локальному минимуму.

Хотя метод А3 и дает вполне удовлетворительные решения задачи распараллеливания для относительно небольших значений n p, его применение для отображения графов алгоритмов большой размерности на большое число процессоров проблематично, в силу значительного возрастания времени работы метода и ухудшения точности получаемых решений.

3.4. Стохастический метод Монте-Карло

1. Аналоговое решение оптимизационной задачи распараллеливания вычислений.

Для эффективного решения поставленной оптимизационной задачи для больших размерностей графов алгоритма и ВС, в данном параграфе разрабатывается стохастический метод Монте-Карло. В сформулированной задаче каждому варианту R разрезания графа алгоритма на подграфы соответствует функционал времени счета J(R). Требуется определить такое разрезание R, которое доставляет минимум функционалу J. Заметим, что эквивалентом варианта разрезания является определенное расположение вершин графа ГА в подграфах, а R соответствует их «координатам».

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

(155)

Под действием поля частицы - вершины графа - будут стремиться расположиться по подграфам так, чтобы доставить минимум функционалу J. Однако расчет координат по детерминистическому уравнению (155) может привести к попаданию частиц в один из локальных минимумов, из которого они не в состоянии выбраться. Поэтому, в систему вводятся дополнительные стохастические силы, приводящие к тепловым флуктуациям частиц, которые помогают им выбраться из локальных минимумов. Тогда процесс поиска оптимального расположения частиц в подграфах будем моделировать процессом случайного блуждания в потенциальном силовом поле J(R). Пусть вероятность P(R, t) обнаружить частицу в момент t в точке с координатами R подчиняется уравнению Фоккера-Планка:

(156)

Стационарное распределение вероятностей для уравнения (156) запишется следующим образом

(157)

Максимум вероятности (157) соответствует такому расположению частиц по подграфам, которое доставляет минимум функционалу J. Соотношение Эйнштейна D =  связывает подвижность  и коэффициент диффузии , характеризующий тепловые флуктуации. Распределение (157) является распределением Больцмана с температурой .

Тепловые флуктуации ведут к перебросам частиц между минимумами потенциала J(R). Если два минимума разделены потенциальным барьером J, то среднее время перехода между ними оценивается как t exp(J / J) . Характерное время установления равновесного распределения вероятностей при температуре J тем больше, чем выше потенциальные барьеры и ниже температура J.

Если в область абсолютного минимума попадают другие локальные минимумы, отделенные от него потенциальным барьером J  , то при наличии флуктуаций динамическая система не может отличить их от абсолютного минимума. Чтобы избежать этого, используют имитацию «отжига» системы [87], постепенно понижая температуру J и устремляя ее к нулю. Чтобы длительность отжига, гарантирующего правильное отыскание глобального минимума J, не была экспоненциально велика, его нужно начинать с температуры J = J_max.

1. Описание метода Монте-Карло.

Стационарное решение (157) моделируется методом Монте-Карло. Общая схема метода такова.

1. Полагаем начальную температуру равной _0.

2. Выбираем равновероятно начальное расположение вершин R и вычисляем его эффективность J = J(R).

3. На каждой итерации t случайным образом перебираем все частицы-вершины. Для каждой из вершин случайно выбираем новый подграф и определяем приращение функционала J при переносе в него данной вершины. Если J < 0, то вершина переносится в новый подграф, иначе она переносится в него с вероятностью exp(-J/).

4. Понижаем температуру по закону  = ₀ / t.

5. Если зафиксирован выход системы части на стационарное значение функционала J, то конец алгоритма, иначе переход на 3.

1. Результаты численного тестирования.

С помощью программы, реализующей метод Монте-Карло, было проведено исследование данного метода. В качестве графов алгоритмов исследовались графы, состоящие из P двоичных деревьев, имеющих N вершин на верхнем ярусе, для которых аналитически вычисляется значение J_min. Будем обозначать такие графы за B(N, P).

На рис. 45 изображена зависимость точности от номера итерации для графа алгоритма В(10, 10). Граф вычислительной системы содержит 10 вершин, связанных каждая с каждой. Кривые соответствуют четырем значениям ₀ = - 0.1, 0.2, 0.5 и 5. Полученные зависимости позволяют сделать следующий вывод. Чем меньше ₀, тем более быстрой является сходимость метода. Однако, при достаточно малых ₀ метод начинает застревать в локальных минимумах. Предельным случаем является ₀ = 0, когда метод быстро сходится к некоторому ближайшему от R локальному минимуму.

Рис. 45. Сходимость ошибки Е в методе Монте-Карло для различных значений начальной температуры J₀: 1) J₀ = 0.1; 2) J₀ = 0.2; 3) J₀ = 0.5; 4) J₀ = 2.

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

Список файлов книги