6

4

xi 2

2

0

2 0 2 4 6

xi 1

Рис. 3.23. Окончание

3.11. Глобальный поиск

Во многих практических задачах приходится иметь дело с многоэкстремальными целевыми функциями (рис. 3.24).

Q		x		x
				локальный
				экстремум
				линия водораздела
				зон притяжения
		x	глобальный	x
I	II	x	экстремум
x		x
а)			б)

Рис. 3.24. Природа многоэкстремальности

В первом случае (рис. 3.24, а), при поиске максимума, если поиск начнется в зоне I, то локальные алгоритмы приведут в точку x , а из зоны II в точку x . Здесь многоэкстремальность обусловлена наличием ограничений и начальной точкой поиска x . Во втором случае (рис. 3.24, б) многоэкстре-

82

мальность обусловлена видом целевой функции Q(x) . Универсальных мето-

дов поиска глобального экстремума нет. Здесь широко используются методы случайного поиска [3].

Пусть задано допустимое множество Х системой ограничений типа неравенств (рис. 3.25).

x

А

x

Рис. 3.25. К задаче глобального поиска

На допустимом множестве, применяя генератор случайных чисел, например, равномерного распределения, разбросаем случайные точки xk (век-

торы) xk X для k ,...,N (первая итерация). Точки отмечены на рис. 3.25 крестиками «х». Во всех точках вычислим Q xk и запомним только то значение Qk и соответствующий ему вектор xk , которые доставляют экстремум, т.е. наилучшие среди всех «разбросанных» точек xk

Qk extrQ xk .

xk X

Точка xk (точка А на рис. 3.25) подозревается на глобальный экстре-

мум и является точкой «притяжения». Из нее вновь производим генерацию случайных точек (векторов) xk ,x ,...,N (вторая итерация), например, гене-

ратором нормального распределения с параметром mx xk , и средним квадратическим отклонением x . Точки отмечены на рис. 3.25 «+» (плюсами). В

соответствие с законом распределения они концентрируются в области точки А. Хотя, отдельные точки попадут и в отдаленные зоны множества Х. Значение x выбирается исходя из размеров допустимого множества Х и правила

«трех сигма» x . Процедура поиска вновь повторяется на новой последовательности xk .

83

векторная функция размерности l

Найденные наилучшие значения в обеих итерациях сравниваются. Вы-

бирается наилучшая x , которая является начальной точкой поиска локального случайного поиска, либо комплекс-метода.

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

Для повышения эффективности поиска применяют адаптацию параметров алгоритмов случайного поиска в функции успеха. Существуют и другие алгоритмы глобального поиска [3].

3.12. Многокритериальные задачи

Часто целевая функция не одна, а несколько, то есть функция Q(x)

Q(x) Q (x),Q (x),...,Ql (x) .

И задача состоит в одновременной минимизации (максимизации) всех критериев. Очевидно, если оптимизировать каждый критерий в отдельности, то локальные экстремумы не могут служить решением многокритериальной задачи (рис. 3.26).

Q

Q	Q

х

x

x

Рис. 3.26. Двухкритериальная целевая функция

Если один из критериев Qi (x) требует минимизации, а остальные мак-

симизации, то умножением его на «-1» сведем задачу к поиску максимума векторной целевой функции Q(x) .

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

84

Пример	3.5.		Пусть		l ,	n ,		Q x x min ,
		min , xi , i , .
Q x x
Нетрудно видеть,			что для	Q x		( , ) ,	Q x		( , ) .		Очевидно

каждой точке в пространстве Х соответствует точка в пространстве критериев Q, тогда область допустимых состояний Х в пространстве параметров отражается в определенную область S пространства критериев (рис. 3.27).

Очевидно, в пространстве критериев всегда можно выделить подмножество S точек Q S , для которых уже не найдется более предпочтитель-

ных Q. Этому подмножеству S соответствует подмножество x X в пространстве параметров (см. рис. 3.27), которое обычно называется множеством Парето, переговорным множеством или областью компромисса. Важность этого множества заключается в том, что именно оно содержит решение

многокритериальной задачи. В нашем примере подмножеству S соответст-

вует подмножество x – отрезок, соединяющий точки обоих минимумов функций Q и Q . Таким образом с формальной точки зрения множество Па-

рето можно считать решением многокритериальной задачи. Но на практике всегда необходимо не множество решений, а одно.

Q
8
6
4
А
2
S
В	Q
1	2
а)

x
		x
1
Х		x
-1		1
x		x
-1

б)

Рис. 3.27. Пояснения к примеру 3.5

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

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

85

Q j (x) extr ,

x

x X ,

: Qi (x) qi ,i j,i , ,...,l.

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

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

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

l	l
q(x) iQi (x) или q(x) Qi (x) i ,
i	i

где i - весовые коэффициенты, которые задаются на основе априорной (до-

полнительной) информации.

Можно использовать и другие свертки, но суть в задании весовых коэффициентов.

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

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

86