книги / Решение некоторых многоэкстремальных задач методом сужающихся окрестностей

Рис. 24.

Т а б л и ц а 3.2

	Вид метрики	Н аименьш ее	Н аибольш ее	а 3	Среднее
		значение ос	значение 3	2	значение
	Транспозиционная	и з	350,41	175,77	108,43
	Алфавитная	5,64	23,08	14,36	11,18
	Цепная	9,85	659,78	334,82	248,07
	Инверсная	5,39	734,26	369,82	267,64
	Лексикографическая	5,73	14,75	10,24	9,81

92

функционала при этом равно 267,64. В случае лексикографической
метрики получаем картину,	распределения, представленную на
рис. 24. Здесь математическое	ожидание равно 9,81. На рис. 25

и 26 показаны гистограммы для случаев алфавитной и цепной метрик

соответственно. Средние значения	g (р) при	этом	равны 11,18
и 248, 07. Результаты исследования	сведены в	табл.	3.2.

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

Однако строгое доказательство этого утверждения пока удалось провести лишь для нормального закона распределения, а в ослаб­

ленном виде для логнорд>ального.
§ 3. Уменьшение дисперсии
Рассмотрим, какие изменения происходят с дисперсией					слу­
чайной величины при	переходе		от нормального	распределения
к его усечению на некоторый интервал.				закону	(3.2),
Пусть случайная величина		г	распределена по
а случайная величина	у — по	закону (3.5). Как		известно,	дис­

персия величины г равна о3. Вычислим дисперсию величины у.

По	определению		d (у) =	((У -	(у)?) - (у2) - (у)2.		(3.39)
Из	соотношения		(3.18)	следует
	(у)2 =		т2 +	У2 am	ехр (— Л2) — ехр (— В2)	,
				Уп"	Е(В)— Е(А)	"т*
	+	а2 .	ехр (— 24») — 2exp (— 42 — В*)-+ exp (— 2В2)				(3.40)
		2п			[£ (В) — Е (4)]2
где числа Л и В определяются по формуле (3.16),
	Второй момент случайной величины у определим как
	«•> -	I л и » W -

Для вычисления этого интеграла воспользуемся заменой перемен­
ной (3.14). Получим
		в
	(У2) — уЛ - J (У~2 аи + т)2ехр (— и2) du.			(3.41)
Учитывая	соотношение (3.16),		находим
	2	в	в
(&) =	р	1 “2 ехР ( ~ “а) du + 2^ - - ° т j и ехр (— (и2) du -f

93

				au =	?2 ■( ы2 exp (— u2)du -+•
					VnP {
+	[exp ( - A2) -			exp ( -	В2)] + Л ? - [ Е ( В ) - Е (A)].				(3.42)
V n P
Необходимо вычислить
			a	и2 exp (— и2) du.
			У
Воспользуемся интегрированием					по	частям:
в								В
]* и2 exp (— u?)du = --- Y u ехР (— иа) |5 + *4“ I ехР									“
3								Л
=	Л е х р ( - 4 ^ - Д е х р ( - В2) +					/ я . [£ (fl) _ Е (Д)]>			(3.43)
Из соотношений		(3.42)	и (3.43) получаем
	<у‘> - ° ’ +		у х	А ехр (— Л2) — В ехр (— В2)
					Е ( В ) - Е		(Л)
	,	V 2 a m	ехр (— А 2) —			ехр (— В 2)		, тЛ	(3.44)
	+ _ 7 й			Е ( В ) - Е ( А ) ,				+ т '
Вследствие формул (3.39), (3.40) и (3.44) находим
d(y) = a2 +			а2	А ехр (— Л2) — В			ехр (— В 2)
			■утг	'	Е ( В ) - Е ( А )
		ехр (— 2Л2) — 2 ехр (— А 2 — В 2)					+	ехр (— 2В2)	(3.45)
	2я			( Е ( Б ) - Е ( А ) I2
Теорема	3.3.	Дисперсия случайной величины у, распределен­

ной по закону (3.5), не превосходит дисперсии случайной величины

г, распределенной по нормальному закону				(3.2).			величины	г
Д о к а з а т е л ь с т в о .			Поскольку	дисперсия
равняется о2, из формулы (3.45) следует, что						для доказательства
теоремы достаточно		проверить справедливость				неравенства
	о2	А ехр (— <42) — В ехр (— В2)				^
	W		Е ( В ) - Е ( А )			<
а 2	ехр (— 2А 2) — 2 ехр (— А 2 — В2) +					ехр (— 2В2)
2я			[ Е (В) — Е (Л)]2
Поскольку Е (х)	монотонно		возрастающая		функция		и- В >	А,
это неравенство	эквивалентно следующему:
	А ехр (— А2) — В ехр (— В2) <
ехр (— 2Л2) — 2 ехр (— А 2 — В2) +					ехр (— 2В2)		(3.46)
^		2 / i t	[ Е (В) — Е (Л)]

94

Пользуясь определением (3.10) функции Я (ж), переписываем нера­ венство (3.46) в виде

в
(е~А‘ — е~в‘)2 — 2 (Ае~А‘— Ве~т) j er-*'dx> 0.	(3.47)

Таким образом, доказательство теоремы сведено к доказательству

неравенства	(3.47).
Рассмотрим прежде всего случай, когда
	В > А > 0.	(3.48)
Введем функцию
	в
и (А,	В) = (е~Аг — e r * f — 2 (Ae~At — Ве~В!) J е~хЧх.	(3.49)
	А

Дифференцируя эту функцию по В при фиксированном Л, полу­ чаем

dUав = ^Ве-в*(егА*— ег~В2)— 2 (АегАг — Вег~вг)етвг —

в

— 2e-B*(2B*— \ ) \ e - x'dx.

А

Разделив правую часть этого равенства на положительную величину 2е~в\ получим новую функцию

		в
v (А, В) = 2Ве~Аг— Вег* — Ае~А‘ — (2В2— 1) J e~x,dx,
		А
причем знаки функций о (Л, В) и ди^	совпадают.
Дифференцируя функцию v (А, В) по	В при	фиксированном
А, находим
дх>(*'в В) = 2 (е~А' — 2В J <r-x‘dx^ .
Рассмотрим функцию
в
w (Л, В) = е~А*— 2В j e~xtdx,
А
знак которой совпадает со знаком функции	Art t А	Л )
	—	•

Легко видеть, что при В > 0 она является монотонно убываю­ щей функцией от В. При этом

w (Л, Л) = erAi > 0,	(3.50)
lim w (Л, В) = — оо.	(3.51)
В-+ оо

95

Вследствие непрерывности функции а» (Л, В) из формул (3.50)

и (3.51) следует существование числа В0 такого, что
w{A,	В0) =	0,
причем В0 > А.	В0 функция v(A, В), как функция
Следовательно, при А < В <
от В, монотонно возрастает, а при В >			В0 она монотонно убывает,
	поскольку ее производная меня­
	ет знак с плюса на минус.
		Нетрудно			видеть, что
				v(A,	Л) =	0,
			lim v(A,		В) = — оо.
			В-*-со
	Поэтому функция v {А, В)						име­
	ет	вид,		представленный			на
	рис.		27.	образом,		существует
		Таким
Рис. 27.	точка Вг такая, что при А <						В <
	<	Bt	выполнено			неравенство
	v (А, В )> 0 , а при В >• Вх спра­

ведливо о (Л, В) < 0.			Поскольку		знак функции v(A, В) совпадает
со знаком производной от функции и (А, В) по В, то и (А, В),							как
функция от В,		монотонно возрастает при В <				Вх и монотонно убы­
вает при В >		В1# Значит, минимальные значения функция и (А, В)
принимает при В = Л и В = -f					оо.
Поскольку		и (А, А) = 0, для доказательства неравенства (3.47)
при условии		(3.48)	достаточно		проверить	справедливость	не­
равенства				И т«(Л ,	В )> 0 .	(3.52)
				В-+СО
Вследствие	определения			(3.49)	со
		lim и (А,		В) = е -24*— 2Ае~А‘ [ e~x'dx.
		В-*°°			А
Рассмотрим	функцию
		q (A )~ e ~ * — 2A $tr*dx.				(3.53)

Нетрудно видеть, что знак функции q (Л) совпадает со знаком пре­ дыдущего выражения. Имеем

- Т Г 1 ------	(3.54)
Следовательно, функция q (Л) монотонно	убывает. Покажем,
что	(3.55)
Н т ?(Л) = 0.
Л-*оо

96

Условие	(3.56)
lim e~Af = 0

А-+оо

очевидно, а предел второго слагаемого в правой части (3.53) вы­

числим	G использованием		правила		Лопиталя
		оо
	со	f	e~*'dx
lim 2А f e-^dx =		lim - — -----=		lim ~		e . - =	lim 2A2e^A* = 0.
A -¥OO	j	/4-*00	*	•	Л-*оо	* ■	/4-VOO
	A		2 A			2 A 2	(3.57)

Из формул (3.56) и (3.57) вытекает соотношение (3.55), а из (3.54) и (3.55) следует, что функция q(A) всюду неотрицательна. Поэтому справедливо неравенство (3.52), а значит и основное нера­ венство (3.47).

Напомним, что проведенное доказательство неравенства (3.47) опирается на неравенство (3.48).

Рассмотрим случай, когда
5 > 0 > А	(3.58)

При этом неравенство (3.47) является очевидным. В самом деле, если верно (3.58), то в левую часть неравенства (3.46) входит отри­ цательная величина, а в правую — положительная. Между тем неравенства (3.46) и (3.47) эквивалентны.

Наконец, рассмотрим ситуацию, когда

А < В <		0.		(3.59)
Вследствие четности функции е-* имеем
в	— А
J er-^dx =	|	e~x'dx.		(3.60)
А
С учетом соотношений (3.49) и (3.60) находим
и (А, В) = [е—<—«* —			—
	— А
— 2 ((— В) e-t-BY — (— А) е_(_'4)!|	J	e~x‘dx = u(— B, — А).		(3.61)
	—в

Неравенство (3.59) можно переписать в виде

— А > — В > 0.

Из этого неравенства и соотношения (3.61) еледует неравенство и (— В, — Л )> 0.

Теорема доказана.

Сделаем некоторые замечания по поводу теоремы 3.3. Утверждается, что дисперсия величины у не превосходит дис­

персии величины г. В случае, когда интервал (а,Ь) конечен, из струк­

7

9—961

97

туры доказательства теоремы 3.3 следует, что между дисперсиями имеем строгое неравенство. Действительно, функция ди (А, В)/дВ на некотором интервале строго положительна. Значит, функция f(A, В) строго монотонно возрастает по переменной В при условии, что в начале интервала она равна нулю. Следовательно, неравенство (3.47) можно заменить следующим:

ь

{е~аг— е~ь*)2— 2 (ае~а2— be~b°) Це~хЧх > 0.

а

Интуитивно ясно, что уменьшение дисперсии будет происходить при усечении любого закона распределения. Однако получить строгое доказательство этого факта нам пока удалось только для нормального закона.

Факт уменьшения дисперсии известен также и для следующего вырожденного случая. Как известно, для случайной величины

распределенной по	закону	Коши
о (2 ) =	Р II <	z) = -J- +	arctg ■г-а — ,

дисперсия не существует. Между тем, для усеченного закона Коши дисперсия является конечной величиной (см., например, Г251), Большое количество просчитанных примеров, а также некого* рые интуитивные соображения дают возможность предположить, что справедливо следующее утверждение, более сильное, чем тео­

рема 3.3.			величина,		распределенная, по				закону
Пусть tji — случайная
	0					если г >		а19
Pi (г) =		f e x p f - ^ f l dxt				если ах < г <			blf
	VbioPi I		У[	\ V 2 a )	J
где					,	если г >		blt
а у2— случайная		величина,		распределенная		по закону
	0				,	если	г <	а2,
Р*{г)	7Ё	р- Ь [ - ( 1^			dx,	если	а2 <	г <	62,
							г >	Ь2,
где	1				,	если

Если выполнено неравенство ах < о, С 6, < Ьъ дисперсия случай­ ной величины у2 меньше, чем дисперсия случайной величины уг.

Иными словами, дисперсия уменьшается не только при переходе от основного закона распределения к его усечению, но и при пере­ ходе от одного усеченного закона распределения к другому, если интервал, на котором сосредотачивается закон, уменьшается.

К сожалению,	доказательство этого утверждения, сводящееся
к доказательству	неравенства

„Г Л ехр (— А\) — В2ехр (— В\)

2 У п [

Е (Bj) — Е (Л*)

^Г ехр (— Al) — ехр (— в|) I2

<l Е ( В 0 - Е ( Л 0

где

Е(ВО -В (АО

Г ехр (— А\) — ехр (— В\)	]2	J •
JЕ ( В , ) - Е ( А[1)

Л	_ аг— т t D			— т	л	а 2 — т	р ^2 — т
	~	V2 а ’	D l~~	V2o '	2 “	У2о ’	2 ~ У Т ~
нам	не	удалось	провести.

Проиллюстрируем уменьшение дисперсии следующим численным

примером. В	качестве модельного выберем функционал (3.38),
в котором п =	84, а числа М{ заданы в табл. 3.1.

Проведем анализ значений функционала (3.38) в соответствии со схемой, приведенной в § 2 данной главы. При этом будем вычис­

лять выборочные дисперсии, точ­								Т а б л и ц а 3.3
нее стандартные			отклонения,
получаемых результатов.
Стандартное отклонение, вы­						М ет р ц КСД		С тан дарт­
численное	после	1000		бросков				ное о т ­
								клонение
чистого случайного			поиска, со­
ставляет	123,1.	Выберем пере­							64,46
становку	р0 в качестве			центра	Транспозиционная
окрестности и рассмотрим выбор­					Алфавитная				3,27
ки в 1000 значений функционала					Цепная			153,16
					Инверсная			135,30
(3.38) при	условии,		что переста­		Лексикографическая				3,64
новки выбираются из шара ради­
уса пять. В табл. 3.3 приведены							Т а б л и ц а		3.4
				Значения дисперсии при радиусах шара
М етрика		50		25	10	5	3	2	1
Цепная		135,25		134,90	136,85	151,80	157,93	153,74	0,00
Лексикографиче­		4,09		3,55	2,96	3,69	3,01	1,00	1,31.
ская
Алфавитная		134,31		32,70	8,36	3,08	2,79	0,82	0,41
Инверсная		134,39		133,58	143,01	137,97	136,38	138,98	136,36
Транспозиционная		120,17		105,37	79,54	63,85	50,63	45,09	40,80

7*

90

стандартные отклонения полученных выборок при различных мет­ ризациях пространства перестановок.

В табл. 3.4 иллюстрируется зависимость дисперсии от радиуса шара. Центр шара, по-прежнему, находится в перестановке р0, а выборочные дисперсии определяются на основе 1000 вычислений значений функционала (3.38).

§ 4. Метод сужающихся окрестностей

Рассмотрим функционалы, заданные на множестве перестано* вок, для которых их значения распределены по нормальному за­ кону (3.2). Пусть лучшее из полученных значений функционала равно h. Тогда вероятность появления новых улучшений определя­

ется как

А

или с учетом обозначения (ЗЛО)

(3.62)

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

Как показано в предыдущих параграфах, при выборе переста­ новок, на которых рассматривается функционал /, из различных щаров в пространстве перестановок происходят изменения в па­ раметрах т и о закона распределения.

В связи с этим изменяется и вероятность (3.62). Характер этих изменений является основным критерием при определении направ­ ления поиска в предлагаемом методеминимизации, который мы Назвали методом сужающихся окрестностей.

Метод сужающихся окрестностей сводится к проведению несколь­ ких режимов поиска. Первый режим представляет собой «слепой* случайный поиск. Произвольным образом генерируются перестанов­ ки р из пространства П и вычисляются значения функционала f(p). Этот процесс продолжается определенное число шагов, после чего выбирается лучшее значение f* функционала / и соответствую­ щая ему перестановка р*. Все полученные значения функционала рассматриваются как наблюденные значения случайной величиньц

По ним подсчитываются выборочное математическое ожидание т

и выборочная дисперсия а2. Затем, пользуясь гипотезой о характере района распределения, вычисляем вероятность P f получить значение функционала лучшее, чем f*. Перед первым прохождением режима по­

лагаем Р = 0. Если окажется, что Р >• Р, то полагаем Р равным

Р, а режим повторяем. Если же, напротив, Р < Р, то происходит переход к следующему режиму.

100