3.7.Последовательный симплексный метод

Последовательный симплексный метод (ПСМ) относится к методам прямого поиска. Суть метода состоит в том, что движение к оптимуму осуществляется последовательным отражением вершин симплекса.

В n-мерном евклидовом пространстве n-мерный симплекс представляет собой фигуру, образованную n точками (вершинами), не принадлежащими одновременно ни одному пространству меньшей размерности. В одномерном пространстве симплекс есть отрезок прямой, в двумерном — треугольник, в трехмерном — треугольная пирамида (тетраэдр) и т.д. Симплекс называется регулярным, если расстояния между его вершинами равны. В ПСМ используются регулярные симплекс-планы. Из любого симплекса, отбросив одну его вершину, можно получить новый симплекс, если к оставшимся вершинам добавить всего одну точку.

Для выбора направления движения во всех вершинах симплекса V j , j ,...,n необходимо измерить (вычислить или оценить) значения це-

левой функции Q j . При поиске максимума наиболее целесообразно будет движение от вершины Vs с наименьшим значением Qs к противоположной грани симплекса. Шаг поиска выполняется переходом из некоторого симплекса Sn в новый симплекс Sn , путем исключения вершины Vs и построения ее зеркального отображения Vsн относительно грани, общей обоим сим-

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

x

V н

 

V н V н

V				V н
V		V		x

Рис. 3.15. Геометрия поиска ПСМ

58

ПСМ имеет следующие достоинства [6]:

поиск с применением ПСМ не требует сложных вычислений, все операции формализованы;

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

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

просто учитываются ограничения: вершина, не удовлетворяющая ограничениям, отбрасывается, как наихудшая на текущем шаге, либо на следующем.

Приведем некоторые соотношения для n-мерного регулярного симплекса (рис. 3.16). Радиус вписанной гиперсферы

r	L
	n(n ) ,
где L – длина ребра регулярного симплекса.
Радиус описанной гиперсферы
R L	n
	(n ) .
Высота симплекса
h R r L		n .
		n
	2
	3
	О	1
1
		2
Рис. 3.16. Геометрические параметры симплекса

59

Расстояние между центрами соседних симплексов, или длина шага по-

иска

r L
			.
		n(n )

Смещение центра симплекса вдоль любого направления наискорейшего движения за один шаг равно модулю проекции вектора шага на это направление

			L		(3.21)
			n(n )(n )

Координаты центра текущего симплекса

		n
x i		x ji ,i ,...,n ,	(3.22)
	n j

где x ji – координаты вершин текущего симплекса.

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

В случае, когда в ходе оптимизации необходимо увеличить размерность вектора х, n-мерный симплекс достраивают до (n ) -мерного. При

этом к вершинам n-мерного симплекса, которые теперь рассматриваются как

точки (n ) -мерного пространства (с		дополнительной			n координатой
x j,n x ,n , j ,...,n ) добавляют еще одну вершину					Vn . Координаты
этой вершины xn , ,...,xn ,n соответственно равны
x ,...,x	n	, x	h	,
		,n	n

где x ,...,x n – координаты центра исходного n-мерного симплекса в момент его достройки, определяемые из выражения (3.22); x ,n – расчетное значение (n ) -го параметра при достройке симплекса, выраженное в безразмерных единицах; hn – высота (n ) -мерного симплекса

h	R	r	L		n		.
n	n	n			(n )

Симплексный поиск с переменным шагом [6]. Постоянный размер сим-

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

60

Уменьшение размеров симплекса с сохранением вновь полученной вершины при n показано на рис. 3.17а. Исходный регулярный симплекс имеет вершины V , V , V и ребро L .

Первый симплекс после выполнения шага образуется вершинами V н , V (1) , V (1) и имеет ребро L . Вершина V н получена зеркальным отражением отброшенной вершины V , относительно грани V , V (при n грань является ребром); вершины V (1) и V (1) находятся на расстоянии L от вершины V н . После выполнения второго шага получаем второй симплекс с вершинами V (1) , V н , V (2) и ребром L и т.д.

Значения ребер симплексов равны

Lk L k ,

где k – номер шага; k – числовая последовательность, определяющая закон

изменения шага.

Целевую функцию Q j необходимо измерять только в новой вершине

V jн , где j – номер вершины симплекса (на рис. 3.17 эти вершины отмечены

кружочками). А усеченным вершинам «приписывается» значение целевой функции «отрезанных» вершин.

2
		н	(1)		н
		2			3
			2
	(2)				(2)
	3			1
				(1)
	(1)	2	1
				н
3
	3
				1
	1		1
		(1)
		2
1		2			1
0
		а)

2
			н
			2
	(1)			н
		3
			1
3
(2)				1(1)
3			(2)
1			1
			2
		(1)
			2
				1
				б)

Рис. 3.17. Уменьшение а (увеличение б) размеров симплекса в процессе поиска

61

При увеличении размеров симплекса сохраняется предыдущий порядок выполнения операций, только для увеличивающейся последовательности k .

Для уменьшения размеров симплекса используется числовая последовательность

	k		,	(3.23)
		dk

где k ,...,N – номер шага; N – количество шагов поиска; d – положительное число, равное [6]

		L
d		LN			,
		N

где L , LN – длина ребра исходного и конечного симплекса, определяющего

точность отыскания экстремума.

Последовательность (3.23) при поиске без помех обеспечивает алгоритму бесконечное корректирующее воздействие, так как при ограниченном d

k .

k

Гиперболический характер изменения k при k не всегда удовле-

творяет требованиям симплексного поиска, так как после небольшого числа шагов поиска размер симплекса сокращается слишком медленно. Поэтому последовательность (3.23) применима, когда требуется небольшое число шагов для достижения области экстремума и невысокая точность поиска.

Бесконечное корректирующее воздействие не является необходимым условием для алгоритма поиска. В практических задачах число опытов, а следовательно, и число шагов поиска ограничиваются реальными возможностями, поэтому речь может идти только об ограниченном перемещении центра симплекса по направлению к цели. В случае, когда задана допустимая область поиска Х, а целевая функция достаточно гладкая, для уменьшения размеров симплекса целесообразно использовать экспоненту [6]

k

e k ,

(3.24)

где – положительное число, равное

N ln L ln LN .

Последовательность (3.24) в отличие от (3.23) обеспечивает равномерное уменьшение размеров симплекса. Закону (3.24) необходимо отдать предпочтение, когда требуется значительное число шагов для достижения области экстремума и высокая точность поиска. Однако, для последовательности

(3.24)

62

k ,

k

поэтому она применима только при заданном конечном числе шагов поиска

N.

Увеличивать размеры симплекса в процессе поиска можно также по закону (3.23) или (3.24), однако в этом случае вместо k подставляется величина k k , убывающая на единицу после выполнения каждого шага, начиная с момента принятия решения об увеличении размеров симплекса.

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

					Q(x) max,						(3.25)
							x X				, j ,...,m .
где X x : x E n , x x x ,i ,...,p, q								j	(x) b
		i	i		i					j
		Ограничения вида x x				x	являются ограничениями на переменные
				i	i	i
x	i	(в общей постановке		x ), где			x ,	x		– нижняя и верхняя допустимая
							i		i

граница изменения i-ой переменной (не обязательно для всех, p n ). Эти ог-

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

Для оптимизации используем алгоритм с запретом возврата от вершины Vsн назад к вершине Vs , что исключает колебания симплекса в области экстремума или гребня (оврага), когда устанавливается последовательность Vs Vsн Vs Vsн ... При нарушении новой вершиной Vsн ограничений задачи (3.25) (хотя бы одного) значению Qsн 900000 , заведомо наименьшее значение, и потому вершина Vsн будет отражена на следующем шаге поиска.

Незначительное нарушение ограничений (3.25) на один шаг поиска в задачах математического программирования не приводит к «взрыву» объектов проектирования.

Вращение симплекса вокруг одной из вершин указывает на то, что она подозревается на экстремум, и в этой вершине следует провести повторный эксперимент. Правило останова процедуры поиска, тем более для переменного шага, реализуется при условии, что номер текущего шага поиска k N .

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

выбранных пользователем координатах		xr , xe движения вершин симплекса
xk , а также график Qk в функции k.
Некоторые рекомендации по выбору параметров поиска [6].
Длина ребра исходного симплекса
	min x x
L					n(n )
	i	i				.		(3.26)
	n

63

Длина ребра конечного симплекса

L n , (3.27)

N	n

где xN x* – точность отыскания экстремума, как норма невязки между

конечной точкой (вершиной) и точкой экстремума.

Для выбора параметров изменения длины ребра симплекса d или в формулах (3.23) и (3.24), а также числа шагов поиска N необходимо оценить максимально возможное расстояние от исходной точки до точки экстремума

x*

n x

max i

i

Далее используя графики max / L

x / .

f (N) и соотношения L / LN , и n

находят N [6].

Если в задачах имеются и функциональные ограничения, то задача выбора L усложняется, так как в n-ом пространстве трудно априори выбрать

«габариты» симплекса. Предлагается следующее простое правило выбора L . Задаем согласно (3.26) начальное значение L и строим симплекс относительно исходной точки x . Если нарушено хотя бы одно из ограничений задачи (3.25), значение L уменьшается наполовину L . L и так до тех

пор, пока не будут выполнены все ограничения (3.25). Далее находим соотношение H max / L .

Графики (номограммы) выбора числа экспериментов N в [6] можно упростить для (3.23) и (3.24) и разных соотношений L / LN и n одним выраже-

нием (как среднее по множеству)

H	N	,	(3.28)
	( )
откуда N H .

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

Можно процедуру поиска начинать с разных исходных точек. Если они дают одинаковые результаты, то задача (3.25) решена.

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

64

Для нормирования следует воспользоваться процедурами планирования активного эксперимента.

Описание алгоритма. Исходными данными являются: n – размерность симплекса; x i – координаты центра исходного симплекса; x , x – позиционные и функциональные q(x) b ограничения; последовательности (3.23) или (3.24); целевая функция Q(x) ; r,e n – номера координат для построе-

ния графика перемещения координат вершин симплекса при поиске; – точность отыскания экстремума, kp – константа, определяющая поиск максимума ( kp 1) или минимума (kp 0) .

Порядок выполнения операций следующий:

1) вокруг исходной точки с координатами 0 построить симплекс, удовлетворяющий ограничениям (3.25). Расчет координат вершин симплекса произвести по формуле

x ji x i Lo ,

где i ,...,n – номер переменной,; j ,...,n – номер вершины симплекса,;– переменная, определяемая из выражения

,при i j ,

,при i j ,

i(i )

i

,при i j .

(i )

rnd (1) x x

.

Если исходная точка x X

, то x

0i

x

0

i

i

i

Далее осуществляется расчет N , LN , параметра или d изменения

ребра симплекса.

Во всех вершинах исходного симплекса найти значение

Qj Q x j

, j ,...,n ,

и если текущая x j не удовлетворяет ограничениям задачи,

то при поиске

максимума Qj 900000 j , и 900000 j

пр поиске минимума. Это позво-

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

Положить номер шага поиска k n ; Yk Qk – массив для построения графика Qk ; Х – массив координат вершин симплекса;

2) из всех вершин текущего симплекса, выбрать вершину с наименьшим (поиск максимума) значением Q j , причем j p , где р – номер новой

вершины на предыдущем шаге поиска (запрет возврата)

65

Qs min Q j .

j p

Положить s j , p s , где s – номер отраженной и новой вершины симплекса;

3) вычислить координаты вершины Vsн нового симплекса по формуле

xsiн	n	n	xsi ,i ,...,n ;
	x ji	n
	n j

4) проверить выполнение ограничений (3.25) для точки с координатами

xsiн :

если эта точка удовлетворяет ограничениям, то перейти к п.5),

иначе Qsн 900000 и перейти к п.6);

	5)	определить значение Qн в вершине с координатами xн			, i ,n ;
		s		si
Y Qн		– массив для построения графика Q	k	;
k	s
	6) положить k k , m j m j ; ms		, здесь m j – число последова-

тельных шагов поиска, в которых вершина с номером j не отражалась. Для новой (отраженной) вершины ms ;

7) присвоить

j s , x

ji

xн ,i ,...,n ,

Q

j

Qн . Вычислить координаты

si

s

остальных вершин текущего симплекса

xн

xн

x

xн

k

, j ,...,n , j s, i ,...,n ;

ji

ji

si

si

k

8) провести анализ m j , j ,...,n :

если m j n , перейти к п.9);

иначе d j ,

вычислить

Q Q xн

(повторный эксперимент),

d

d

md , перейти к п.9);

9) проверить число шагов поиска k:

если k N , перейти к п.2);

если k N , перейти к п.10);

10)	вывести на печать оптимальные значения x*j,i , Q*j ,
i ,...,n,	j ,...,n и траекторию движения координат вершин симплекса

Х k для двух выбранных переменных xr , xe на двухкоординатный график и график Yk от k.

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

В условиях нарушения позиционных и функциональных ограничений ПСМ с переменным шагом имеет худшие показатели в сравнении со стандартными процедурами Mathcad (см. рис. 3.18). ПСМ плохо работает в усло-

66

виях «угловых» ограничений и неудовлетворительно движется вдоль ограничений задачи.

Пос ледовательный с имплекс ный метод с переменным шагом, запретом возврата, рас четом параметров поис ка. Поис к макс имума kp=1, минимума kp=0

n 3	- размернос ть вектора х 0.01 - точнос ть отыс кания экс тремума

N1 1 чис ло итерации для "впис ывания" ис ходной точкив ограничениях задачи

0

Позиционные ограничения									OR IGIN 1			kp 1
		10					3
xmax			10		xmin 0
			10				0
			5							1		1
X0			5 - ис ходная точка						a		1	xx 1	- параметры модели
			5								1	1
	1
b		1					параметры функциональных ограничений задачи
	1						r 1	e 2 - координатные ос и для пос троения графика
				n				2
Q(y)
					ai yi xxi целевая функция
				i 1
				n			bi yi
g1(y)								b1 7			- функциональные ограничения
				i 1									x3 0
Q1(x1 x2) a						1	x1 xx 2 a		2	x2 xx 2		q(x1 x2) b		1	x1 b	2	x2 b1 b	3	x3
								1			2

Q1	q

Рис. 3.18. Программа последовательного симплексного метода с переменным шагом, запретом возврата, с расчетом параметров поиска. Поиск максимума

67

Рас чет ис ходного и конечного ребра с имплекс а

( L0 rmax)

for

i 1 n

d

i

xmax xmin

i

i

rmin min(d)

1

L0

rmin

n (n 1) 2

2 n

2

1

n

2

rmax

di 2

i 1

( L0

rmax)

				1
LN		n		2
	2
		n 1

LN 0.012 L0 3.429 rmax 15.78

Проверка выполнения позиционных функциональных ограничений

poz(y)

sum 0

fogr (y)

sp1 0

if g1(y) b1

for i 1 n

sp1 1

otherwise

sp

i

0

if y

i

xmax y

i

xmin

sp1

i

i

sp i

1

otherwise

sum sum sp i

sm sum

sm

Ос новной блок программы

( X Y )

k n 1

p n 2

w n 1

N 8

rmax

L0

1

(ln(L0) ln(LN))

N

(k) exp( k)

for t 1 N1

for j 1 n 1

for

i 1 n

0 if

i j 1

1

if i j 1

2

i

(i 1)

i

if i

j 1

2(i

1)

X0

i

xmin rnd(1)

xmax xmin

if poz(X0) 1 fogr (X0)

1

i

i

i

Рис. 3.18. Продолжение

xj i X0i L0

Xj i xj i

zzi xj i

68

XT XT

for j 1 n 1

1

if i j 1

2 i

(i

1)

i

if i

j 1

2(i 1)

i

i

i

i

X0

xmin rnd(1)

xmax xmin

if poz(X0) 1 fogr (X0) 1

xj i X0i L0

Xj i xj i

zzi xj i

XT XT

for

j 1 n 1

z j XT j

f

j

j

Q z

j

j

f

j

900000 j

if

poz z

1

fogr

z

1

kp

1

poz z j 1

fogr z j 1

f

900000 j

if

kp

0

j

Yj fj

mj 0

while k N

ft sort (f)

ft reverse (ft )

if

kp 0

fm ft

1

for j 1 n 1

s j

if

fj

fm

fm ft

2

if s

p

for j 1 n 1

s j

if

fj

fm

p s

for i 1 n

n 1

2

(2 n)

xnovs i

xj i

xs i

n

n

j 1

znovi xnovs i

fs Q(znov)

fs 900000 k if (poz(znov) 1 fogr (znov) 1) kp

1

fs 900000 k

if (poz(znov)

1 fogr (znov) 1) kp

0

for j 1 n 1

mj mj 1

ms 0

Рис. 3.18. Продолжение

k k 1

for i 1 n

xs i xnovs i

69

for j 1 n 1

for i 1 n

x

xnov

x

xnov

(k)

if

j s

s

fs 900000 k

if (poz(znov) 1

j 1 n 1

for

mj mj 1

ms 0

k k 1

for

i 1 n

xs i xnovs i

for

j 1 n 1

i 1 n

for

xnov

x

xnov

x

i

i

j

s

j i

s i

j 1 n 1

for

for

i 1 n

Xw j i xj i

Yk fs

w w n 1

mp max(m)

( continue )

if mp n 2

for

j 1 n 1

d j if mj

mp

for

i 1 n

zz x

i

d i

fd Q(zz)

k k 1

Y f

d

k

md 0

( X Y )

fogr (znov) 1)

kp 0

(k)

(k 1)

if j s

Результаты поис ка

							1
		1	2	3
						1	-9·105
	1	1.294	4.01	4.3
						2	-33.815
	2	4.724	4.01	4.3
						3	-50.685
	3	3.009	6.98	4.3
						4	-57.246
	4	3.009	5	7.1
						5	-82.3
	5	5.867	6.65	6.167
						6	-63.272
	6	4.886	4.385	4.565
						7	-31.657
	7	3.414	6.933	4.565	Y
X						8	-9·105
	8	3.414	5.234	6.968
						9	-18.293
	9	5.89	6.663	5.75
						10	-33.869
	10	5.048	4.72	4.375
						11	-30.836
	11	3.786	6.906	4.375
	12	6.03	6.744	3.23		12	-20.667
	13	4.02	5.583	2.238	Рис. 3.18. Продолжение	13	-20.33
	14	4.902	4.842	4.072		14	-13.181
	15	3.819	6.719	4.072		15	-15.156
	16	5.745	6.58	...	70	16	...

	7	3.414	6.933	4.565
X	8	3.414	5.234	6.968
	9	5.89	6.663	5.75
	10	5.048	4.72	4.375
	11	3.786	6.906	4.375
	12	6.03	6.744	3.23
	13	4.02	5.583	2.238
	14	4.902	4.842	4.072
	15	3.819	6.719	4.072
	16	5.745	6.58	...
	m 1 rows(X)			k 1 rows(Y)

Y	8	-9·105
	9	-18.293
	10	-33.869
	11	-30.836
	12	-20.667
	13	-20.33
	14	-13.181
	15	-15.156
	16	...

Решение процедурой Mathcad
y X0
Given	y xmin			y xmax
g1(y) b1
		3
xy MaximizeQ( y)	xy	2		Q(xy) 6
		2		z 0 10
Qo Q(xy)				b1 b3 xy3 b1 z
				x2(z)
				b2

Перемещение с имплекс а в прос транс тве координат

10

8

Xm e 6

xy2

x2(z) 4

2

00	2	4	6	8	10
			Xm r z

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

Как следует из результатов (см. рис. 3.18) x0 X x01 5 . Программа в соответствие с алгоритмом переместила ее в допустимое множество Х.

71

3.8.Метод Нелдера–Мида

Метод Нелдера-Мида является развитием последовательного симплексного метода.

Описание алгоритма для задачи поиска минимума целевой функции без ограничений [5]. Исходными данными являются: n – размерность симплекса; xн – координаты исходной (начальной) точки поиска; L – размер ребра ис-

ходного симплекса (для простоты L ); α – коэффициент отражения ( , обычно выбирается ); – коэффициент сжатия ( , обычно выбирается . ); – коэффициент растяжения ( , обычно выбирается );– значение константы для условия останова. Порядок выполнения операций следующий:

1) относительно исходной точки xн построить симплекс с координата-

ми вершин

xij xнi L ei , i ,...,n, j ,...,n ,

где i – номер переменной, j – номер вершины симплекса, xнi – координата исходной точки, L – длина ребра исходного симплекса, ei – единичный век-

тор по i-ой координате.

Во всех вершинах исходного симплекса найти значение

Qj Q x j , j ,...,n ;

2) осуществить сортировку вершин текущего симплекса в порядке возрастания Q j . Выбрать вершину с наибольшим (поиск минимума) Q j , поло-

жить s j, где s – индекс худшей вершины; выбрать следующее за наибольшим значение функции Qp и наименьшее значение функции Ql и соответствующие им точки xs , x p , xl ;

3) рассчитать центр тяжести всех точек текущего симплекса, за исключением точки xs

	n
x i	x ji ,i ,...,n ;
	n j
	j s

4) отразить точку xs относительно точки x , получить точку xr (рис.

3.19а)

xr ( )x axs ,

и вычислить Qr Q xr ;

5) сравнить значения функций Qr и Ql :

а) если Qr Ql (сравнение с лучшей вершиной текущего симплекса), то направление из точки x в точку xr считается удачным и можно произвести растяжение симплекса в этом направлении. Рассчитать точку xe (рис. 3.19б)

72

		xe xr ( )x ,
и вычислить Qe Q xe , иначе переход к п. 5 г);
	x p		x p	x е
				x r
				x
x s	x	x r	x s
	x l			x l
	а)			б)
	Рис. 3.19. Отражение а) и растяжение б) симплекса

б) если Qe Ql , то заменяем точку xs на точку xe и переход к п. 9);

в) если Qe Ql , то отбрасываем точку xe , заменяем точку xs на точку xr и переходим к п. 9);

г) если Ql Qr Qp , то xr является лучшей точкой по сравнению с другими двумя точками симплекса и мы заменяем точку xs на точку xr и пе-

реход к п. 9) иначе к п. 5д) и т.д.;

д) если Qr Ql и Qr Qp , то переход к п. 6); 6) сравнить значения функций Qr и Qs :

а) если Qr Qs , то выполнен неудачный шаг и необходимо сжать симплекс (рис. 3.20а)

	xm xs ( )x ,
вычислить Qm Q xm и перейти к п. 7);
x p	x r	x p	x	x r
			m
	x		x
xm		x s
x s
	x l			x l
	а)		б)

Рис. 3.20.Сжатие симплекса

73

б) если Qr Qs , то сначала заменим точку xs на точку xr , и произве-

дем сжатие симплекса (рис. 3.20б)

xm xr ( )x ,

вычисляем Qm Q xm и переходим к п. 7); 7) сравнить значения функций Qm и Qs :

а) если Qm Qs , то заменяем точку xs на точку xm и переход к п. 9);

б) если Qm Qs , то очевидно, что все наши попытки найти значение меньшее Qs закончились неудачей, поэтому мы переходим к п. 8);

8) уменьшить размер симплекса делением пополам расстояния от каж-

дой точки симплекса x j

до точки xl ,

определяющей наименьшее значение

функции

x

x

x ji xli

, i ,...,n,

j ,...,n ,

ji

li

затем вычисляем Qj Q x j для

j ,...,n и переход к п. 9);

9) вычислить среднее значение вершин текущего симплекса

n

Qср

Q j

n j

и оценку среднеквадратического отклонения

n

SQ

Q j Qср .

n j

Если SQ , то все значения функции очень близки друг к другу, симплекс «сжался» у точки экстремума и поэтому переход к п. 10); иначе к п. 2);

11)останов процедуры. Вывод на печать результатов поиска.

В системе Matlab метод Нелдера-Мида представлен функцией fminsearch, обеспечивающей безусловную минимизацию. Обращение к функции

[x, Q, exitflag, inform]= fminsearch(@функция, x0).

%Метод Нелдера-Мида function PSM

clear all X0=-3:0.1:3;Y0=-2:0.1:5; [X,Y]=meshgrid(X0,Y0); s=size(X);Z=zeros(s); for i=1:s(1)

for j=1:s(2) Z(i,j)=Rosenbrock([X(i,j);Y(i,j)]);

end

end axes('Xlim',[-3,3],'Ylim',[-2,5]); axis equal;grid off;hold on; v=1:2:10;V=10:4:20;

Рис. 3.21. Метод Нелдера-Мида в Matlab

74

contour(X,Y,Z,[v V]); xlabel('x1');ylabel('x2')

% options=optimset('Display','final','GradObj','on','Hessian','on'); x0=[-2;2];

line(x0(1),x0(2),'Marker','.','MarkerSize',10); [x,Q,e_flag,out]=fminsearch(@Rosenbrock,x0) line(x(1),x(2),'Marker','.','MarkerSize',20); plot([x0(1),x(1)],[x0(2),x(2)],'k-');

colormap copper

function [f,g,H]=Rosenbrock(x) f=5*(x(2)-x(1)^2)^2+(1-x(1))^2;

1.0000

1.0000

Q = 1.8161e-009 e_flag = 1

out = iterations: 61

funcCount: 115

algorithm: 'Nelder-Mead simplex direct search' message: [1x196 char]

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

75

3.9.Комплекс-метод Бокса

Комплекс-метод является модификацией метода Нелдера-Мида, но в силу «облачности» перемещения случайных точек, позволяет учитывать позиционные и функциональные ограничения задачи [5].

Пусть, необходимо

Q(x) min,

x X

где X x : x En , xi xi xi , i ,...,n, q j (x) bj , j ,...,m .

Если целевая функция выпукла и функции q j (x) тоже выпуклы, то за-

дача будет иметь единственное решение.

В отличие от ПСМ и метода Нелдера-Мида число вершин «комплекса» l n .

Описание алгоритма. Исходными данными являются: n – размерность вектора х; xi , xi – нижняя и верхняя допустимая граница изменения i-ой переменной, программируемые в процедуре-функции; q j (x) bj – функцио-

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

останова поиска.

Порядок выполнения операций следующий:

1) построить «комплекс», удовлетворяющий позиционным и функцио-

нальным ограничениям задачи
x	ji	x x x , i ,...,n ,			j ,...,l ,
		i	i	i

где rnd ( ) – равномерно-распределенное случайное число в интервале

[0,1].

Если на j-ой итерации точка (вершина) «комплекса» не удовлетворяет хотя бы одному функциональному ограничению задачи (позиционные при таком формировании выполняются автоматически), то она смещается на половину расстояния до центра тяжести множества уже принятых точек (вер-

шин) «комплекса»			xsi x i , s j, p j, x
x	si			ji	x	si	,i ,...,n ,

где xsi – координаты вершины, не удовлетворяющей функциональному ограничению,

p

x i p j x ji ,i ,...,n ,

где x i - центр тяжести множества уже принятых р вершин «комплекса».

76

Если точка xsi все еще не удовлетворяет функциональному ограниче-

нию, то изложенная процедура «усечения» повторяется до полного выполнения функциональных ограничений задачи;

2) вычисление целевой функции для всех вершин «комплекса»

Qj Q x j , j ,...,l ;

3) сортировка вершин текущего «комплекса» в порядке возрастания Q j . Выбрать вершину с наибольшим (поиск минимума) Q j , s j , где s – ин-

декс худшей вершины, и с наименьшим значением Ql , l – индекс лучшей

вершины;

4) вычисление координат центра тяжести x текущего «комплекса», за исключением координаты xs

		l
x i		x ji ,i ,...,n ;
	l j ,
		j s

5) отразить худшую вершину «комплекса» относительно точки x

xr ( )x xs

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

xi xri xi ,i ,...,n .

Если нарушена нижняя граница i-ой переменной, то

h i, xrh xri , xri xrh ,

где , рекомендуется , , если нарушена верхняя граница i-ой переменной, то

xrh xri , xri xrh ;

7) проверка выполнения функциональных ограничений
	q j xr	bj , j ,...,l .
Если нарушено хоть одно ограничение, то точку xr смещают на поло-
вину расстояния между xr	и центром x
	xн xri	x i ,i ,...,n .
	ri
Затем производится	повторная	проверка точки xнr на выполнение

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

xri xriн ,i ,...,n ;

8) вычисление целевой функции в новой точке

Qr Q xr ;

77