Слаботочка Книги

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 [66] 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83

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

Ясно, что первый тип наиболее желателен для быстрой сходимости алгоритма оптимизации. Экспериментальные результаты проведенных вычислений, которые будут обсуждаться в гл. 9, свидетельствуют, однако, о том, что он не является типичным. Поверхности второго и третьего типов, хотя и нехелательны, поскольку фактический максимум может быть не найден, но с практической точки зрения процедура оптимизации в таком случае не сложна. Для поверхностей отклика третьего типа процедура поиска может быть связана с затруднениями при отыскании гребня и движении по направлению к максимуму. Наиболее неприятным- явля-, ется пятый тип поверхностей отклика, при кото])ом может быть допущена большая ошибка, если поиск заканчивается на одном пз (малых) локальных максимумов (Уайлд и Бейтлер, 1967).

8.Э.З. Наибольший наблюдаемый максимум и глобальный максимум

В § 8.2 и п. 8.3.2 были рассмотрены вопросы, связанные с отысканием глобального максимума для мультимодальной поверхности отклика. Проектировщик, оптимизируя свое решение, осуществляет ряд циклов поиска, каждый раз начиная поиск с различных, случайно выбранных точек. Каждый цикл продолжается, пока наибольшее значение целевой функции не найдено. После ряда попыток найти глобальный оптимум, проектировщик может проверить найденные им максимумы. Если оказывается, что все найденные максимумы одинаковы, то он может решр1ть, что им найден глобальный максимум. Если все найденные максимумы различны, то проектировщик склоняется к мысли, что наибольший из наблюдаемых локальных максимумов не является глобальным. Эти два возможных рассуждения являются крайними; на практике чаще обнаруживают определенный максимум несколько раз, прежде чем другой относительный максимум будет обнаружен хотя бы один раз. В таком случае возникает вопрос, можно ли заключить на основе выполненных циклов поиска, что наибольший 204

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

Рассматривая случайный поиск, сделаем два пред-Положения: 1) поиск может закончиться с равной ве-.4 роятностью l/v на любом локальном максимуме, 2) местоположения начальных точек поиска статистически независимы. Практически любое математическое толкование реальной проблемы требует тем не менее К некоторых не доказываемых допущений, подобных пер-, вому из двух указанных. Поэтому, не обсуждая далее этого вопроса, ограничимся числовым примером, показывающим, как можно без потери общности рассуждений при наличии таких допущений использовать статистику наблюдений.

Предположим, что проводится шесть циклов поиска. Будем считать, что применимы поверхности отклика первого и второго типов. Условимся, что А означает максимум, достигаемый в процессе поиска более часто, чем любой другой максиму.м {или, по крайней мере, так же часто); В означает второй по частоте достижения .мак-j. симум и т. д.

Легко убедиться, что шесть циклов поиска могут дать одиннадцать существенно различных результатов. Первая возможность состоит в том, что один и тот же максимум достигается шесть раз; обозначим ее условно как 6Л. При двух принятых допущениях вероятность достижения отдельного максимума (среди v максимумов) последовательно шесть раз равна \/v. Однако шесть подъемов на любой из v пиков составляет результат, условно обозначаемый 6Л. Поэтому 6Л будет встречаться с вероятностью

Далее рассмотрим случай, когда шесть циклов поиска приводят к достижению одного максимума трижды, другого- дважды и третьего - один раз. Этот результат условно обозначим как ЗА-\-2В-\-С. Вершина Л может быть достигнута v способами, вершина В-(v-1) способами, а вершина С - (v-2) способами. Другими словами, существуют в точности 6!/(3! 2!) различных последовательностей, приводящих к результату ЗА-\-2В-\-С. Любая одна последовательность подъема на шесть вершин реализуется с вероятностью 1М, Поэтому результат ЗА-\-2В-{-С будет достигаться с вероятностью 60(v-1) (v-2)Л5.

Таблица 8.1

Одиннадцать возможных результатов шести циклов поиска и вероятности этих результатов

Наблюдаемый результат		Значение вероятности 1Голучен1га данного результата поиска при значениях v
	Вероятность получения данного результата
					1024	3125	7776	16 807	32 7G8	59 049	lOJOOO
5Л+С	6(v l)
						3125	1203	16 807	13 384	19 683	100 ООО
4А+2В-	15(v-l)
					1024		2592	16 807	32 7G8	19 683	20 0Э0
зл+зв	lO(v-l)
					1024		7776	IG 807	16 384	59 019	10 000
ЛА+В+С	15(v l)(v-2)
							2592	16 807	16 384	19 683	2500
зл+гс+с	60(v-l)(v-2)							1800		1120
							2592	1С 807	4096	19 6S3
2А+2В2С	]5(v-l){v-2)
							2592	16Й07	16 384	19683	2500
ЗА+В+С+О	20(v-I)(v-2}(v-3)							2400		2240
							2592	16 807	4096	I9G83
2A+2BC+D	45{v-l}{v-2)(v-3)							54D0	4725
						GSii		16 80?	16 384	21S7	S500
2A+B+C-\-D-Jf~E	15{v-l)(v-2Km-3)(v-4)							5400	1575	28H0
								16 807	4036	6561	1250
	f V-1 H v 2K v-3) (V-4) f v-5i									2240
							2592	1GS07	4096	19 683	12Й)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 [66] 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83