Тема 2.3. Оптимизационные модели

Тема 2.3.1. Методы оптимизации

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

План изучения темы (перечень вопросов, обязательных к изучению):

1. Создание материалов;

2. Понятие рендеринга;

3. Методы рендеринга.

Краткое изложение теоретических вопросов:

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

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

За критерий оптимальности принимается некоторая функция F(x), называемая целевой функцией. Целевая функция аналитически выражает зависимость оптимизируемого показателя от некоторых параметров x, значения которых можно изменять, называемых управляемыми параметрами

хi, i = 1,2,...,n.

Управляемые параметры xi являются независимыми друг от друга и в процессе оптимизации могут изменяться в известных пределах (допустимой области) Dx. Аналитически область допустимых значений может задаваться аналитически в виде набора функций

Ψ k (x 1,..., x n)= 0

В общем виде математическую задачу оптимизации можно сформулировать следующим образом:

Минимизировать (максимизировать) целевую функцию с учетом ограничений на управляемые переменные.

Под минимизацией (максимизацией) функции n переменных F(x)=F(x1,...,xn) на заданном множестве Dx понимается определение глобального минимума (максимума) этой функции на заданном множестве Dx.

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

Максимизация целевой функции (F(x) ->max) эквивалента минимизации противоположной величины (−F(x)->min), поэтому можно рассматривать только задачи минимизации.

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

Численные методы решения задач одномерной оптимизации

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

F(x) ->min, x принадлежит [a, b].

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

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

Большим достоинством прямых методов является то, что от целевой функции не требуется дифференцируемости и, более того, она может быть не задана в аналитическом виде. Единственное, на чем основаны алгоритмы прямых методов минимизации, это возможность определения значений F(x) в заданных точках.

Самым слабым требованием на функцию F(x), позволяющим использовать эти методы, является ее унимодальность (наличие одного минимума в области допустимых значений). Поэтому далее будем считать функцию F(x) унимодальной на отрезке [A, B].

Метод перебора

Метод перебора или равномерного поиска является простейшим из прямых методов минимизации и состоит в следующем.

Разобьем отрезок [A, B] на n равных частей точками деления:

xi=A+i·(B − A)/n, i=0,...n

Вычислив значения F(x) в точках xi, путем сравнения найдем точку xm, где m - это число от 0 до n, такую, что

F(xm) = min F(xi) для всех i от 0 до n.

Погрешность определения точки минимума xm функции F(x) методом перебора не превосходит величины ε = (B − A)/n.

Метод дихотомии

Метод применяется для нахождения экстремума-максимума или экстремума-минимума нелинейных одномерных унимодальных целевых функций.

Суть метода в следующем. Пусть целевая функция F(х) задана на интервале A≤ x ≤ B. Отрезок на каждом этапе делится пополам. За первые две поиско-

	вые точки принимаются x1 =	A + B	− ε,	x 2=	A + B	+ ε, где ε величина, мень-
		2			2
	шая половины требуемой абсолютной			погрешности решения. Вычисляя зна-

чения целевой функции F(x) в точках x1, x2 уточняется направление поиска. Если отыскивается экстремум-минимум и F(х1) < F(х2), то смещается правая граница первоначального интервала неопределенности[B-А],т.е. полагается В = x2, если F(х1) > F(x2), то смещается левая граница А = x1. Если новый интервал неопределенности [В−А] больше заданной погрешности решения ε, то де-

ление пополам продолжается. Если B−A ≤ ε, то решение получено x*= A +2 B, F(x) = F(x*).

Метод Фибоначчи

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

Nn=Nn-1+Nn-2,при N1=N2=1.

Первоначальный интервал неопределенности [В−А] принимается пропорциональным некоторому числу Фибоначчи Fn, определенному в зависимости

от требуемой абсолютной погрешности решения ε как первое число Фибоначчи, большее (В−А)/ε, т.e.

Nn>(B−A)/ε.

Координаты первых двух поисковых точек x1, x2 делят отрезок [B−A] на

участки, пропорциональные Nn-2	и Nn-1,т.е. x1= A +	N n − 2	(B − A),x2= A +	N n − 1	(B + A).
		N n		N n

Если измеренное или вычисленное значение целевой функции F(x1) < F(x2) при необходимости отысканияэкстремума-минимума,то смещается правая граница первоначального интервала неопределенности, т.е. B = x2. Если F(x) >F(x2), то смещается левая граница, т.е. принимается A = x1. Тогда длина нового интерва-

	ла неопределенности становится пропорциональной Nn-1,то есть равной			F n − 1
				F
				n
	части первоначального интервала неопределенности. После	к-oйитерации
	длина к -гоинтервала неопределенности становится равной	N n − k	части пер-
		N n

воначального интервала неопределенности, а поисковые точки в нем,будут

иметь координаты x 1 (k) =A +	N n − k − 2 (B − A)	, x 2	(k) =	A +	N n − k − 1 (B − A)	Число итераций
	N n − k				N n − k

m необходимых для получения решения с заданной абсолютной погрешности ε известно заранее и равно n-2,так как N1=N2=1.

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

Лабораторные работы:

1. Построение фотореалистичного изображения.

Задания для самостоятельного выполнения

1. Выполнение и сдача лабораторных работ.

Форма контроля самостоятельной работы:

- Защита лабораторных работ;

- Устный опрос.

Вопросы для самоконтроля по теме:

1. Как создать материал?

2. Как задать текстуру материала?

3. Какие параметры имеются в Редакторе текстур?

4. Что такое рендеринг?

5. Что такое пре-рендеринг?

6. Какими методами возможно освещение сцены?