Пупков К.А., Коньков В.Г. Интеллектуальные системы (1-е изд., 2001) (1245264), страница 27

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

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

Функция распределения f относительной ошибки  алгоритма А3 приразрезании графа сдваивания с n = 15 на 1) p = 4; 2) p = 8 подграфов.Метод использует локальные характеристики графа ГА - связностькаждой вершины и ее вес. Общая схема метода такова.Алгоритм А2:1. Выбираем равновероятно вершину с номером 1;2.

Составляем вектор g = {gi, i = 1, p} связанности данной вершины со всемиподграфами;3. Выбираем подграфы, связность которых с 1 равна;4. Вершину 1 заносим в тот из выбранных подграфов, который имеетнаименьший вес и переходим на 1.893.4. Стохастический метод Монте-Карло1.Ps ( R ) Аналоговое решение оптимизационной задачираспараллеливания вычислений.Для эффективного решения поставленной оптимизационной задачи длябольших размерностей графов алгоритма и ВС, в данном параграферазрабатывается стохастический метод Монте-Карло.

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

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

Пустьвероятность P(R, t) обнаружить частицу в момент t в точке с координатами Rподчиняется уравнению Фоккера-Планка:P  J 2 P P   Dt  R   R  R2(156)Стационарное распределение вероятностей для уравнения (156) запишетсяследующим образом1  D J ( R)ez(157)Максимум вероятности (157) соответствует такому расположению частиц поподграфам, которое доставляет минимум функционалу J. СоотношениеЭйнштейна D = связывает подвижность  и коэффициент диффузии ,характеризующий тепловые флуктуации. Распределение (157) являетсяраспределением Больцмана с температурой .Тепловые флуктуации ведут к перебросам частиц между минимумамипотенциала J(R). Если два минимума разделены потенциальным барьером J, тосреднее время перехода между ними оценивается как t exp(J / J).Характерное время установления равновесного распределения вероятностей притемпературе J тем больше, чем выше потенциальные барьеры и нижетемпература J.Если в область абсолютного минимума попадают другие локальныеминимумы, отделенные от него потенциальным барьером J  , то приналичии флуктуаций динамическая система не может отличить их отабсолютного минимума.

Чтобы избежать этого, используют имитацию«отжига» системы [87], постепенно понижая температуру J и устремляя ее кнулю. Чтобы длительность отжига, гарантирующего правильное отысканиеглобального минимума J, не была экспоненциально велика, его нужно начинатьс температуры J = Jmax.2.Описание метода Монте-Карло.Стационарное решение (157) моделируется методом Монте-Карло.Общая схема метода такова.1. Полагаем начальную температуру равной 0.2. Выбираем равновероятно начальное расположение вершин R и вычисляемего эффективность J = J(R).3.

На каждой итерации t случайным образом перебираем все частицывершины. Для каждой из вершин случайно выбираем новый подграф иопределяем приращение функционала J при переносе в него даннойвершины. Если J < 0, то вершина переносится в новый подграф, иначе онапереносится в него с вероятностью exp(-J/).4. Понижаем температуру по закону  = 0 / t.5. Если зафиксирован выход системы части на стационарное значениефункционала J, то конец алгоритма, иначе переход на 3.3.Результаты численного тестирования.90С помощью программы, реализующей метод Монте-Карло, былопроведено исследование данного метода. В качестве графов алгоритмовисследовались графы, состоящие из P двоичных деревьев, имеющих N вершинна верхнем ярусе, для которых аналитически вычисляется значение Jmin.

Будемобозначать такие графы за B(N, P).На рис. 45 изображена зависимость точности от номера итерации дляграфа алгоритма В(10, 10). Граф вычислительной системы содержит 10 вершин,связанных каждая с каждой. Кривые соответствуют четырем значениям 0 = 0.1, 0.2, 0.5 и 5. Полученные зависимости позволяют сделать следующий вывод.Чем меньше 0, тем более быстрой является сходимость метода. Однако, придостаточно малых 0 метод начинает застревать в локальных минимумах.Предельным случаем является 0 = 0, когда метод быстро сходится кнекоторому ближайшему от R локальному минимуму.Рис. 46. Сходимость ошибки Е, показывающая способность метода МонтеКарло выходить из локальных минимумов функционала J.Рис. 45. Сходимость ошибки Е в методе Монте-Карло для различных значенийначальной температуры J0: 1) J0 = 0.1; 2) J0 = 0.2; 3) J0 = 0.5; 4) J0 = 2.На рис.

46 построена зависимость E(t), которая демонстрируетспособность метода выходить из локальных минимумов функционала J(R). Вэтом случае ГА = В(100, 1), p = 10. В момент t = 0 - 0 =0, поэтому алгоритмдостаточно быстро приводит систему в локальный минимум. В момент t = 50полагается 50 = J50, после чего наблюдается выход из локального минимума.Были проведены расчеты по определению сложности метода, которыепоказали, что время достижения методом заданной точности E имеет порядок0(pn2).Рис. 47. Время достижения одинаковой точности алгоритмов 1) А3 и 2) МонтеКарло от p при n = 16p - 1.91На рис.47 отражены результаты сравнительного анализа предложенногоалгоритма и алгоритма попарной оптимизации подграфов А3.

Изображеназависимость времени работы алгоритмов от p при ГА = В(8p, 1). Кривая 1соответствует времени работы алгоритма попарной оптимизации, а кривая 2 времени работы алгоритма Монте-Карло по достижении точности достигнутойпри реализации метода А3. Видно преимущество подхода, основанного наметоде Монте-Карло, при решении больших задач распараллеливания.923.5. Стохастический метод наискорейшего спуска1.Описание метода.Хотя метод Монте-Карло, описанный в предыдущем пункте, и оказалсяпригодным к решению больших задач отображения алгоритмов намультитранспьютерные ВС, его слабым местом является достаточно медленнаясходимость.

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

Общая схемаметода такова.Полагаем начальную температуру равной  = a.Выбираем равновероятно начальное расположение вершин R и вычисляемего эффективность J = J(R).3. На каждой итерации t случайным образом перебираем все частицывершины. Для каждой из вершин определяем вектор значений функционалаJi при переносе данной вершины во все подграфы. Случайным образомперемещаем вершину в другой подграф, при этом вероятность переноса1.2.вершины в i - ый подграф равна exp(1 J i )4.5.n exp(1 J j ) .j 1Понижаем температуру по закону  = 1 / (a + t / b).Если зафиксирован выход системы части на стационарное значениефункционала J, то конец алгоритма, иначе переход на 3.При больших значениях температуры все переходы в системe частицвершин являются равновероятными.

При уменьшении же температуры системыувеличивается вероятность перехода в подграф с максимальным уменьшениемфункционала J(R). При достаточно низких значениях температуры вероятностьтолько одного перехода становится равной 1. Этот механизм гарантируетсходимость метода. Параметры a и b позволяют регулировать скоростьсходимости метода (подобно значению начальной температуры в методеМонте-Карло).Рис.

48. Сходимость функционала в методе Монте-Карло (1) и методенаискорейшего спуска (2, 3) при решении задачи с n = 27 и p = 8.2.Реализация метода.На основе метода была создана программа, с помощью которой былопроведено численное исследование метода. Это исследование показало болеевысокую скорость сходимости, чем в методе Монте-Карло. На рис. 48построены графики зависимости функционала J по итерациям алгоритмаМонте-Карло и стохастического алгоритма наискорейшего спуска. Кривая 1соответствует наиболее методу Монте-Карло в случае наиболее быстрогополучения оптимального решения.

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

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