книги / Системы экстремального управления

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

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

Б. Модификации сканирования. Всякая модификация сканирования связана с необходимостью знать нечто боль­ ше об объекте, чем его многоэкстремальность. Так, весьма полезными являются априорные сведения о величине зоны притяжения глобального экстремума S* (эти зоны показаны стрелками на рис. 10.1.1 и 10.1.3). Часто помо­ гает знание максимально возможного наклона экстре­ мальной характеристики. И так далее.

Рассмотрим несколько естественных модификаций ска­

номера i. Это означает, что априорная вероятность обнару­ жить глобальный экстремум в каждом из промежутков

Эту задачу очень просто решить графически. Для этого следует построить функцию распределения

X

и «рассечь» ее N равноотстоящими горизонтальными пря­ мыми. Абсцисса каждого из пересечений определяет гра­ ницу промежутков. Теперь нетрудно определить поло­ жение экспериментов для сканирования. Они располо­ жатся в центре тяжести:

x i ~

Эта процедура проиллюстрирована на примере, пока­

найти глобальный экстремум. В этой зоне можно произ­ вести дальнейшее уточнение с шагом Д8 < Д2 и т. д.

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

т.е. глобальный экстремум «теряется».

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

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

Точки х, в которых определяется значение показателя качества, «разыгрываются» случайно в соответствии с за­ данным законом распределения р (х). Если априорных

сведений о законе распределения не имеется, то естест­ венно каждую точку в равной мере «подозревать» в гло­ бальности и поэтому считать р (х) равномерным законом, т. е. р (х) = const. Этот метод не без основания иногда называют методом Монте-Карло, подчеркивая тем самым его статистический характер.

Пусть | — случайное число. Тогда алгоритм слепого поиска записывается в виде

Xi = l (i = 1, ., N), (10.2.6)

где случайное число £ имеет заданную плотность распреде­ ления р(£), N — число экспериментов, выделенное для отыскания глобального экстремума. При этом процесс за­ поминания остается прежпим (1 0 .2 .2 ).

2) Поиск с уточнением. Этот алгоритм является анало­ гом рассмотренного выше алгоритма сканирования с уточ­ нением. Поиск сводится к следующему.

На первом этапе осуществляется слепой поиск на базе

в точке с наименьшим показателем качества. Следующие N 2 экспериментов распределяются в указанном отрезке и определяется точка, показатель качества которой мини­ мален. Далее, вокруг этой точки выделяется отрезок дли­ ной к2 (Ь — а), в котором делается третий этап слепого поиска, и т. д. Как видно, зона поиска на каждом этапе уменьшается в 1 /к раз, что позволяет уточнить положение глобального экстремума. Однако с уменьшением зоны поиска увеличивается и вероятность утери глобального экстремума, т. е. вероятность того, что он окажется вне пределов зоны поиска очередного этапа. Поэтому подобное измельчение нецелесообразно продолжать слишком дол­ го. Вполне достаточно ограничиться двумя-тремя этапами такого поиска.

Развитием й обобщением поиска с уточнением является следующий алгоритм поиска.

3) Поиск с разведкой. Смысл этого глобального поиска заключается в следующем. Априорно (т. е. заранее) пред­ полагается известным вид плотности распределения пока­ зателя качества Q (х) при равномерном случайном располо­ жении проб х. Эта плотность распределения известна

оценки плотности распределения в первой и второй зонах

Для этого достаточно определить математическое ожида­ ние наименьшего из N — N 0 случайных чисел, распреде­ ленных по первому (Mj) и второму (М2) законам (10.2.12). Если Мх < М2, то оставшиеся испытания следует распре­ делять в первой зоне Dx. При Мх М2 предпочтение следует отдать зоне D2.

Поступая таким образом, можно быть уверенным, что в среднем будет получено наименьшее в данных условиях значение показателя качества, которое можно считать оценкой глобального экстремума на базе N эксперимен­ тов. Очевидно, что результат во многом зависит от величи­ ны N 0. Действительно, при малом N 0 оценки математиче­ ских ожиданий наименьших значений М г и М 2 будут слишком грубыми, что повышает вероятность ошибочного выбора одной из зон. Если же N 0 велико, то Мг и М2, а вместе с ними и зона определяются правильно. Но остав­ шееся число экспериментов N — N 0 слишком мало, чтобы достаточно точно оценить глобальный экстремум. В этом случае результат также будет слишком приближенным. Следовательно, N 0 должно быть оптимальным.

Рассмотрим пример. Пусть априорно известно, что значение показателя распределено по экспоненциальному

одной и другой зои и подстановке их в формулу (10.2.14) С последующим определением Мх ^ М%.

§ 10.3. Глобальный поиск в обстановке помех

Рассмотрим следующую задачу глобального поиска. Пусть значения показателя качества наблюдаются в N фиксированных состояниях хх, ., XN (рис. 10.3.1), при­ чем измерения производятся с дискретными независимыми

Рис. 10.3.1. Пример глобальной харак­ теристики объекта в обстановке помех.

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

меха, как обычно, предполагается нормальной и центриро­ ванной). Задача заключается в отыскании такого состоя­

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

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

Одним из таких критериев можно считать вероятность того, что Xi является глобальным экстремумом, т. е.

Однако это не один, а N критериев. Их можно объединить в один — энтропию, которая в данном случае будет харак­ теризовать уровень неопределенности в положении гло­ бального экстремума:

г= 1

Очевидно, что стратегия поиска должна строиться так, чтобы энтропия (10.3.4) уменьшалась быстрейшим обра­ зом, т. е. на каждом шаге получать максимальную инфор­ мацию. Прекращение поиска естественно связать с опре­ деленным уровнем энтропии Э0, т. е. критерием останова считать удовлетворение неравенства

нии (дисперсии of наблюдений в каждой точке предпола­ гаются неизвестными):

Э = Э (пц щ, ., nN). (10.3.6)

Среднее значение показателя качества на базе и* измере­ ний в £-й точке xt равно

П.

<1о-з л >

г }=1

где / — номер измерения в этом состоянии, Q,- (xî) — /-е наблюдение в i-м состоянии. Дисперсия этого среднего

значения, как известно, равна

i

Для определения вероятности P f (10.3.3) необходимо сна­ чала вычислить вероятность того, что из двух состояний (х, и Xj) t-e имеет меньшее значение функции качества, чем /:е:

Так как помеха е нормальна и центрирована, то для Ри имеет место следующее очевидное выражение:

(10.3.10)

где Ф — функция Лапласа [8.1].

Действительно, математическое ожидание разности Qi — Qj можно приближенно оценить лишь по имеющим­ ся замерам:

При N = 2, когда имеется всего два состояния, величи­ на Рц равна Р^ a Pj = 1 — P ti. Для N > 2 эта вероят­ ность равна

Подставляя полученное значение Pi в выражение для энтропии (10.3.4), получим ее аналитическую зависимость от чисел пх, п2, ., щу (10.3.6), причем числа nt входят явным образом через выражение для дисперсии (10.3.12). Теперь нетрудно выработать стратегию глобального поис­ ка. Будем последующие измерения располагать в том состоянии, которое обеспечит наибольшее снижение энт­ ропии. Для этого вычислим величину энтропии при уве­

личении числа наблюдений в каждом состоянии на едини­ цу. Для этого достаточно изменить в формуле (10.3.12) rai-bni+l, подставить ее в (10.3.10), а последнюю — в (10.3.4). Получаем N значений энтропии:

и определит номер состояния Xj, где следует делать оче­ редной замер показателя качества, так как именно в этом состоянии эксперимент снижает энтропию наибольшим образом. Далее, измеряя значение показателя качества в точке Xj, получаем Q' (жД. Теперь следует произвести коррекцию среднего значения показателя качества в этой точке. Это делается по очевидной формуле:

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

Для того чтобы запустить изложенную процедуру, необходимо сделать сначала эксперименты во всех N точ­ ках Xi. Полученные значения показателя качества Q\ дают возможность вычислить матрицу (10.3.10), при помо­ щи которой определяются вероятности (10.3.13), которые образуют энтропию (10.3.4). Далее необходимо «разыг­ рать» эффект от постановки эксперимента в одном из N состояний, т. е. оценить значение энтропии при измерении показателя качества в каждой из точек жг. Расчет позво­ ляет определить номер того состояния, где следует ставить эксперимент. Определив значение показателя качества в этой точке (с помехой измерений), необходимо сделать коррекцию среднего значения показателя в этой точке. Таким образом, на каждом этане поиска для каждого i-ro состояния Xi необходимо хранить следующую инфор­