§ 3.2. Предпосылки случайного поиска

Случайный поиск как метод управления имеет свою историю, связанную в основном с отстаиванием «права на существование». Однако случайный поиск возник не на пустом месте: его появлению предшествовал период предыстории, когда инструмент случайности оттачивался на решении различного рода прикладных и теоретических задач. Рассмотрим их.

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

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

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

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

Сказанное, безусловно, оправдывает применение метода проб и ошибок для решения практических задач, несмотря на его несколько одиозную славу. (Вспомним, что часто мы так «обзываем» всякую неудачную постановку эксперимента, когда априорных сведений достаточно для организации детерминированного поведения, т. е. для построения регулярного плана эксперимента. Однако подобная ситуация складывается не столь часто, как хотелось бы: априорных данных чаще бывает недостаточно, особенно в поисковых экспериментах, и неизбежно приходится обращаться к пресловутому методу проб и ошибок с его «неразумной», но спасительной случайностью.)

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

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

Однако для сложных процессов, обладающих стохастическими локальными свойствами, в лучшем случае получается стохастическое дифференциальное уравнение, интегрирование которого представляет огромные трудности, а в худшем — лишь правила перехода процесса из одного состояния в другое. Эти правила имеют определенный стохастический характер, т. е. всегда можно «разыграть» с помощью ЭВМ конкретные случайные реализации переходов и тем самым построить различные траектории процесса. Очевидно, что такие траектории случайны и каждая из них в отдельности почти ни о чем не говорит. Однако возможность построить с помощью ЭВМ большое число траекторий нашего процесса открывает широкие перспективы, которые и и использует метод Монте-Карло.

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

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

Располагая этим распределением, можно поступить двояко. С одной стороны, естественно воспользоваться известной формулой для среднего как математического ожидания, которое вычисляется с помощью интеграла:

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

имеющих плотность распределения Тогда оценка среднего х равна среднему этих чисел, т. е.

Здесь через обозначена монте-карловская оценка х на базе чисел (3.2.2). Как видно, все трудности метода заключаются в «разыгрывании» этого ряда случайных чисел в соответствии с заданным распределением Если же мы располагаем возможностью наблюдать реальный процесс, то ряд (3.2.2) представляет собой результаты конкретных наблюдений этого процесса.

Таким образом, метод Монте-Карло обходит трудности, связанные с наблюдением реального процесса, и позволяет получить ряд (3.2.2) путем моделирования случайной величины х в соответствии с имеющейся плотностью распределения Дальнейшая обработка (3.2.2) производится аналогично.

Этот подход легко обобщается На любую функцию от случайного аргумента х. Выражение

является монте-карловской оценкой среднего

Естественно задать вопрос: не проще ли — а главное, не точнее ли — вычислить интеграл (3.2.1), например, методом трапеций, чем оценивать его по формуле (3.2.3) с помощью ряда специально разыгранных чисел Ответ зависит от сложности и требуемой точности вычисления данного интеграла.

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

вычисление многомерного интеграла

представляет уже довольно сложную задачу, точность решения которой уменьшается с ростом размерности интеграла. Это и создает преимущество для метода Монте-Карло. В формуле — заданная скалярная функция вектора — плотность распределения вектора X, которая в случае независимости компонент вектора X равна где — плотность распределения компоненты х. Здесь и случайный вектор X распределен по заданному многомерному закону При этом оценка многократного (-кратного) интеграла (3.2.7) имеет вид

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

Оценка (3.2.8) является случайной величиной: для другого ряда случайных чисел она будет иной. Как всякую случайную величину, монте-карловскую оценку удобно характеризовать ее математическим ожиданием и дисперсией Эти величины обладают следующими интересными свойствами:

1 . Оценка смещена:

т. е. в среднем совпадает с точным значением интеграла (3.2.7).

2. Оценка у состоятельна:

т. е. в пределе совпадает со значением интеграла (3.2.7).

3. Ее дисперсия зависит от следующим образом:

где с — некоторая не зависящая от постоянная.

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

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

III. Метод рандомизации предложен в 30-х годах Фишером, заложившим основы математической теории эксперимента, и широко используется в планировании эксперимента. Метод также

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

а в эксперименте он наблюдает отдельные реализации зависимости

— оператор объекта. Как видно, задача заключается в синтезе модельного оператора Прежде всего исследователь строит план эксперимента, т. е. фиксирует конкретные значения обоих факторов, при которых необходимо поставить эксперимент и определить реакцию исследуемого явления. План по первому фактору должен быть таким, чтобы как можно точнее определить модель . А что делать со вторым фактором, который не входит в модель (3.2.12)? Его следует элиминировать, т. е. исключить. Если оператор объекта известен, то исключение реализуется путем обычного осреднения по исключаемому фактору:

где — плотность распределения фактора Определим интеграл (3.2.14) методом Монте-Карло — с применением формулы (3.2.4):

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

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

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

где — значение первого фактора в опыте, которое определяется стандартными методами (например, в соответствии с ортогональным или -оптимальным планом), а — случайные значения второго фактора, распределенные в соответствии с заданной функцией плотности распределения вероятностей

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

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

где — мощность шума. Известно, что линейная динамическая система однозначно характеризуется своей импульсной переходной функцией которая представляет собой реакцию этой системы на импульсное воздействие. Эту переходную функцию обычно идентифицируют с помощью так называемого уравнения Винера— Хопфа:

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

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

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

V. Гомеостат Эшби является машиной, реализующей, по сути дела, один из простейших алгоритмов случайного поиска. Эшби предложил свой гомеостат в и описал его в книге [246].

Г омеостат представляет собой линейную динамическую систему

где ; А — квадратная матрица которая может изменяться случайным образом и координаты которой ограничены:

Известно, что система (3.2.20) в случае устойчивости имеет одно устойчивое состояние в начале координат ( При неустойчивости и срабатывают упоры:

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

изменять матрицу А случайно, т. е. вводить в гомеостат элемент случайности. Алгоритм управления гомеостатом имеет вид

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

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

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

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

Аналогичная идея реализуется так называемым «усилителем мыслительных способностей», также предложенным Эшби [245]. Несколько претенциозное название этого усилителя связано с любопытной мыслью о том, что случай содержит ответы на все вопросы, а правильный ответ может реализоваться путем многоэтапной селекции, отбора. К сожалению, Эшби не указал, каким образом делать этот отбор. Во всяком случае, отбор должен опираться на проверку истинности полученного промежуточного результата путем определенных процедур вывода, позволяющих отсеивать заведомую нелепость. Эшби даже доказал теорему, что такой процесс заканчивается за конечное время. Идея доказательства опирается на очевидное соображение, что случайное исходное разнообразие можно исчерпать за конечное число этапов селекции, если на каждом этапе редукция (снижение) разнообразия конечным образом отличается от нуля.

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

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

где X — искомое состояние входа объекта, минимизирующее его выход.

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

где центрированный вектор малого случайного возмущения всех входов:

— дисперсия возмущения: Как видно, выход синхронного детектора (3.2.25) пропорционален частной производной что сразу определяет необходимое направление изменения входа. Так, при для минимизации следует уменьшать и наоборот. Это обстоятельство и используется при экстремальном управлении. На исполнительный механизм (интегратор), изменяющий параметр подается сигнал, пропорциональный выходу синхронного детектора, что и реализует обратную связь экстремального управления. Получаем систему дифференциальных уравнений, описывающих поведение управляемого объекта:

где — параметр обратной связи. Если для простоты положить то эта система уравнений в векторной форме принимает вид

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

Как видно из (3.2.28), при отсутствии случайных возмущений: т. е. при никакой минимизации не происходит, так как

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

VII. Метод случайного баланса, предложенный Саттерзвайтом [264], использует случайный план для определения

существенных факторов управляемого объекта. Пусть для простоты объект представляется линейной моделью

где — коэффициент влияния фактора а — остаточная ошибка модели и случайные ошибки наблюдения. Существенными факторами естественно называть те, изменение которых наиболее существенно изменяет выход у объекта, т. е. факторы, коэффициенты которых велики.

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

координаты которых являются независимыми и центрированными случайными величинами. Тогда имеет место

т. е. эта сумма мала, так как она с точностью до множителя является оценкой коэффициента корреляции координат, которые по условию независимы. Поэтому, умножая (3.2.29) на и суммируя по получаем с учетом (3.2.31) оценку для искомых коэффициентов влияния:

где — реакция объекта на эксперимент в точке

Очевидно, что эти оценки приближенны вследствие приближенности выражения (3.2.31) и влияния случайных помех Строго

говоря, возможно получить любые значения этих оценок, сколь угодно сильно отличающиеся от действующих. (С этого упрека методу случайного баланса обычно и начинают его критику.) Но это примерно так же маловероятно, как существенное искажение модели из-за влияния «хвостов» центрированной помехи в объекте. Приближенность и смещенность оценок, вызванные малостью числа экспериментов, не должны никого смущать, поскольку нас здесь интересует лишь соотношение между коэффициентами влияния, а не их абсолютные значения. С помощью случайных экспериментов (3.2.30) удается выделить переменные, которые претендуют на существенность. Более того, их «претензии» можно даже проранжировать по полученным оценкам из (3.2.32). Теперь из следует отобрать имеющих наибольший ранг. Пусть это будут Тогда проведенные эксперименты позволяют построить линейную регрессию

где коэффициенты определяются стандартным для регрессионного метода образом. Ввиду того что , следовательно, имеются «лишние» эксперименты, естественно проверить адекватность полученной модели (3.2.33) — например, с помощью Критерия Фишера. Это позволяет путем последовательных итераций выбрать такие факторы, которые дают адекватную модель при минимальном к, — искомые значимые факторы задачи. Теория и опыт показывают эффективность метода случайного баланса.

Как видно, случайность плана (3.2.30) в методе случайного баланса гарантирует решение поставленной задачи, т. е. выделение существенных факторов.

VIII. Смешанные стратегии в теории матричных игр с нулевой суммой впервые рассмотрены Нейманом еще в 1928 г. Ситуация матричной игры двух лиц (игроков) описывается следующим образом. Пусть первый игрок имеет стратегий поведения, а второй — т. Тогда игра задана, если определен результат игры для всех возможных вариантов использования стратегий (число таких вариантов равно Результат игры численно определяется платежной матрицей где — платеж первого игрока, использовавшего стратегию, второму, который применял стратегию. Выбор стратегий игроками происходит независимо.

Оказывается, что при отсутствии седловой точки в платежной матрице, т. е. при

оптимальной является смешанная (рандомизированная) стратегия, определяемая для первого игрока вероятностями

где — вероятность использования стратегии (эта теорема доказана в работе [139]). Аналогичные вероятности определяют смешанную стратегию второго игрока.

Здесь рандомизация связана не столько с максимизацией выигрыша, сколько с минимизацией проигрыша. Случай здесь играет роль «дымовой завесы», не позволяющей противнику действовать наверняка. При отсутствии активности одного из игроков оптимальное решение всегда лежит в области чистых, или детерминированных, стратегий. Чистая стратегия оптимальна также при наличии в платежной матрице седловой точки, т. е. когда в выражении (3.2.34) стоит знак равенства.

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

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