Параллельный алгоритм…

Результаты вычислительных экспериментов…

Рассмотрим двумерную задачу глобальной оптимизации

2	exp 1	2				2		( y1		1)( y2	1) 4					( y1 1)	4		4
( y) 1.5y1		y1		20.25( y1	y2 )								exp	2				( y2 1)
										2						2

Ограничения: g1(y) 0.01[(y1 2.2)2+(y2 1.2)2 2.25] 0 g2(y) 100[1 (y1 2)2/1.44 (0.5y2)2 ] 0 g3(y) 10[y2 1.5 1.5sin(2 (y1 1.75))] 0

Область поиска: D={y R2, 0≤y1≤4, 1≤y2≤3}

Решение: y* (0.942, 0.944), (y*) 1.489

31 из 41

Параллельный алгоритм…

Результаты вычислительных экспериментов…

Один процессор/развертка

	l	Вычислено значений
		g1		g2	g3	g4
	1	1098	623		392	152
	Два процессора/развертки
	l	Вычислено значений
		g0	g1	g2	g3	g4
	1	636	567	331	212	104
	2	632	327	193	125	61
	Всего	1268	894	524	337	165

Параметры метода

Плотность развертки m 12 Точность поиска 10 3

Найдено решение y* (0.942, 0.945)

Сводная таблица

Число Ускорение процессоров

1

2 1.93

4 2.16

6 3.80

32 из 41

Параллельный алгоритм…

Результаты вычислительных экспериментов…

g3(y)=0

y*

(y)=const

g2(y)=0 g1(y)=0

Расположение точек испытаний при использовании шести процессоров

33 из 41

Параллельный алгоритм

Ускорение сходимости (использование адаптивных резервов)

g3(y)=0

y*

(y)=const

g2(y)=0 g1(y)=0

Расположение точек испытаний при использовании шести процессоров

34 из 41

Программная реализация…

Предварительные замечания:

–Рассматриваются задачи, в которых вычисление значения функции в точке является достаточно трудоемким;

–Объем вычислений, выполняемый на каждой итерации индексного метода, может существенно отличаться;

–Вычислительные узлы при параллельном выполнении программы могут иметь разную мощность.

Вывод: эффективная параллельная реализация индексного метода может быть только асинхронной.

Программная система “Абсолют Эксперт” позволяет решать (исследовать) задачи многомерной глобальной оптимизации.

Основной режим работы системы – параллельное выполнение на кластере.

35 из 41

Программная реализация…

Оптимизация

Поисковая информация					Очередь
					характеристик

Страничная память				Архив

Обработка состояний

Функциональная структура комплекса Абсолют Эксперт

36 из 41

Программная реализация

Подсистема Оптимизация – построение объекта оптимизации, постановка задачи, определение и настройка методов, назначение заданий и выполнение процесса поиска оптимального варианта

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

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

Подсистема Архив – предназначена для организации хранения поисковой информации во внешней памяти

Подсистема Очередь характеристик – ускоряет работу алгоритмов при больших объемах поисковой информации

Подсистема Обработка состояний – унифицированная схема контроля и наблюдения за состояниями системы

37 из 41

Заключение

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

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

Изложена схема редукции размерности задачи, основанная на развертках Пеано, приведена программная реализация разверток.

Представлен параллельный алгоритм, основанный на множественных отображениях Пеано. Приведена программная реализация множественных отображений.

Дана общая характеристика программной системы Абсолют Эксперт.

Представлены результаты вычислительных экспериментов.

38 из 41

Вопросы для обсуждения

В чем состоит задача поиска оптимального решения?

В чем заключается сложность определения оптимума в задачах глобальной оптимизации?

Чем обоснована необходимость поиска глобального оптимума на неравномерном покрытии области поиска?

В чем состоит индексная схема учета ограничений ?

Опишите класс характеристических алгоритмов оптимизации.

В чем заключаются недостатки использования единственной развертки Пеано при редукции размерности?

Каким образом множественные отображения позволяют распараллелить индексный алгоритм?

Чем вызвана необходимость реализации асинхронной схемы расчетов в параллельной модификации индексного алгоритма?

39 из 41

Литература

Стронгин Р.Г. (1978).Численные методы в многоэкстремальных задачах. – М.: Наука.

Strongin R.G. (1992) Algorithms for multi-extremal mathematical programming problems employing the set of joint space-filling curves. Journal of Global Optimization, №2. P. 357–378.

Strongin R.G., Sergeyev Ya.D. (2000). Global optimization with non-convex constraints. Sequential and parallel algorithms. – Dordrecht: Kluwer Academic Publishers.

40 из 41