Растригин Л.А. Адаптация сложных систем

Подождите немного. Документ загружается.

Например, при распределении одного потока заявок на два пункта

обслуживания состояние системы обслуживания можно

охарактеризовать длинами очередей l

и l

к обоим пунктам.

Дисциплиной обслуживания f будет правило, указывающее пункт

обслуживания для поступающей заявки:

то на пункт 1;

то на пункт 2; (2.5.12)

то с вероятностью c

на пункт 1.

Здесь φ — выбранная функция — например, вида

φ = c

- (1 - c

) l

, (2.5.13)

причем параметрами этой дисциплины являются с

и с

(k = 2) с

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

(2.5.14)

Как видно, выбор оптимальных значений c

, экстремизирующих заданный критерий функционирования

(например, среднюю суммарную длину очереди), является задачей

параметрической адаптации.

Если структуру дисциплины обслуживания определить трудно, то

эту задачу следует решать методом структурной адаптации. Здесь

возможно использовать оба подхода, описанных в § 1.5, —

альтернативную и эволюционную адаптацию.

В первом случае следует определить альтернативные дисциплины:

(2.5.15)

и адаптация заключается в «переключении»

указанных альтернативных дисциплин (2.5.15) таким образом, чтобы

поддерживать в каждый момент дисциплину, доставляющую

экстремальное значение критерию адаптации [296].

При эволюционном подходе алгоритм адаптации реализуется

конечным автоматом, входом которого являются состояния среды X и

системы обслуживания Y, а выходом — решение об обслуживании в

данный момент (например, направление очередной заявки на

определенный прибор обслуживания). Структура этого автомата, т. е.

функции переходов и выходов, определяется в режиме эволюционной

адаптации, т. е. путем моделирования эволюции графа такого

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

Таким образом, адаптация дисциплины обслуживания в любой

системе массового обслуживания, подверженной неконтролируемым

воздействиям, является эффективной мерой поддержания системы

обслуживания в оптимальном состоянии независимо от действия

различных непредвиденных внешних и внутренних факторов. Эти

задачи рассмотрены подробно в § 6.3.

Здесь приведены лишь некоторые примеры объектов адаптации.

Объекты адаптации «возникают» всегда, когда приходится

эксплуатировать объект, относительно которого нет четких

представлений, т. е. нет его адекватной модели. Это типичный

«черный ящик», который приспособлен удовлетворять наши

потребности. Эффективность его функционирования очень важна для

нас, что и порождает проблему адаптации. К сожалению, таких

«черных ящиков» нас окружает значительно больше, чем

«прозрачных», особенно в области технологии. Известно, что зачастую

технологический процесс возникает, служит несколько лет и

снимается (заменяется другим), так и не получив хорошего объяснения

в виде адекватной модели. А если вспомнить, что наша цивилизация

— технологическая, то легко понять, как важно, актуально и

перспективно разрабатывать методы адаптации. Они описаны в

последующих главах.

Случайный поиск

в задачах оптимизации

и адаптации

Нет такого печального случая, из

которого многие люди не извлекли бы

какую-либо выгоду, нет такого счаст-

ливого случая, который люди неосто-

рожные не обратили себе во вред.

Франсуа де

Ларошфуко

Случайный поиск, возникший как научное направление более

двадцати лет назад [159, 288], в настоящее время стал рас-

пространенным и эффективным средством решения сложных задач

оптимизации и адаптации. В этой главе рассказывается о

предпосылках появления случайного поиска и об идеях основных его

алгоритмов. Пожалуй, самой привлекательной стороной случайного

поиска является его огромная эвристическая сила, которая позволяет

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

биологического, так и социального характера [286].

§ 3.1. Рандомизация управления

Случайный поиск как метод управления и решения сложных задач

опирается на вероятностный характер окружающего нас мира.

«Господство вероятности» вовсе не является абсолютным: оно не

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

законов, которые и породили известные регулярные методы поиска

типа методов градиента и т. п. Специфика процесса познания

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

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

найти, мы с большой неохотой обращаемся к статистическим,

вероятностным закономерностям. Долго такого рода закономерностям

отказывали в праве на существование, что было сформулировано в

печально известном девизе «Наука — враг случайностей», по сути

дела запрещающем использование статистических закономерностей и

во всяком случае исключающем их применение в науке. В общем и

целом порочная, эта точка зрения имела тем не менее свои

психологические основания.

Дело в том, что психология нашего познания трудно мирится с

недетерминированностью моделей. Такие модели «некомфортны» для

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

увидеть скрытую невыясненную детерминированную закономерность.

Это желание вполне обоснованно, так

Рис. 3.1.1. Модель изучаемого явления.

как очень часто явление считается случайным в силу его плохой

изученности, по мере же изучения удается построить его детер-

минированную модель.

Рассмотрим модель этого феномена. Пусть изучаемое явление

представляет собой некий преобразователь п причин и

, и

,...,и

следствие у (рис. 3.1.1):

y = f

(и

,...,и

), (3.1.1)

где f

— регулярный оператор объекта, а причины и

,...,и

изменяются

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

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

будет известно состояние всех его причин. Только в этом случае

можно точно предсказать значение следствия. Но достаточно не знать

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

следовательно, могло рассматриваться как случайное. (Заметим, что

непредсказуемость и случайность не тождественны. Случайность

всегда подразумевает наличие определенных устойчивых

статистических свойств явления — вероятности, среднего, дисперсии

и т. д., в то время как непредсказуемость этого не требует.)

Как видно, появление случайности здесь является прямым

следствием отсутствия необходимой информации. Чем большей

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

более оно определенно для нас. С этих позиций можно легко провести

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

Действительно, детерминированное явление отличается малым числом

легко наблюдаемых причин, а стохастическое — большим

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

Отсюда ясно, почему стохастические явления начали изучать

сравнительно недавно. Естественно, что наука сначала рассматривала

лишь простейшие явления, зависящие от небольшого числа причин, и

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

стохастических моделей.

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

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

антность. Однако такое описание не во всех случаях удается по-

строить и приходится ограничиваться статистическими законо-

мерностями типа: «в ситуации S с вероятностью р происходит событие

A...». Можно ли отказать подобным закономерностям

в существовании? Разумеется, нельзя! Первыми это поняли физики,

когда в конце первой четверти нашего века осознали неизбежность

«странного» стохастического мира. Было установлено, что законы

микромира вообще не могут быть регулярными, они в принципе

имеют стохастический характер. Например, нельзя сказать наверняка,

попадет данная микрочастица в мишень или нет, — самый точный

ответ в этом случае может состоять в указании вероятности

интересующего нас события. И только!

Такая вероятностная точка зрения на закономерности окру-

жающего нас мира быстро распространилась и на другие области

науки и техники. Не только трудности сбора информации при

изучении сложных явлений заставили обратиться к идее стоха-

стичности. Есть и еще одно довольно неожиданное преимущество

стохастических моделей: они очень просты и удобны. Дело в том, что

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

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

потребность иметь его детерминированную модель. Ведь модель

нужна не сама по себе, а либо для прогнозирования, либо для

управления, т. е. для принятия каких-то управляющих решений,

которые, как правило, не требуют точных моделей (точнее:

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

широко и эффективно пользоваться стохастическими моделями. В

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

моделей. Случайный механизм почти всегда проще

детерминированного. Именно это обстоятельство заставляет

обращаться не к детерминированным, а к стохастическим моделям.

Стохастические модели — это способ описания окружающего нас

мира. Выражается он в указании, какие и насколько частые

отклонения возможны в детерминированной модели. Стохастическая

модель включает в себя детерминированную как частный случай, как

результат некоего осреднения. Кроме того — что самое главное — она

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

Здесь нет случайности в явном виде — это лишь осмысление

результатов действия случайности.

Человек уже давно заметил, как сильно он зависит от случайных

факторов, которые буквально осаждают его со всех сторон. Живя в

вероятностном мире, человечество волей-неволей должно было

выработать меры борьбы с негативными последствиями случая.

Изобретение стохастических моделей явилось одной из наиболее

эффективных мер.

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

управление, т. е. организация и реализация мер по устранению

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

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

на объект, с помощью которых его можно перевести в требуемое

целевое состояние независимо от случайных внешних и внутренних

факторов, действующих на этот объект. Не будь случайных факторов

— не нужно было бы и управления. Таким образом, изобретение

управления является реакцией на стохастичность нашего мира, это

способ борьбы со случайностью, мера элиминирования, исключения

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

целей.

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

— он может быть вполне приемлемым, желательным и даже

счастливым. Едва ли стоит приводить примеры: у каждого из нас есть

в памяти много удивительных счастливых случайностей, которые

произошли в нашей жизни. Но не о них сейчас речь. Естественно

задать вопрос: а нельзя ли к счастливой случайности относиться не

пассивно, т. е. не дожидаться ее реализации, как «манны небесной», а

активно идти ей навстречу, искать ее и использовать для своих нужд?

Эта соблазнительная идея «утилизации» случайности в последнее

время получает значительное распространение. Здесь имеют

место два направления использования случайности. Первое связано

с обобщающими возможностями вероятностных моделей, которые

содержат в себе как частный случай регулярные модели и

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

ценнейшим качеством, которое дало новые направления современной

науки и техники в виде теорий вероятностей, массового

обслуживания, надежности, принятия решений и т. д. [217—219].

Однако не это направление будет нас здесь интересовать.

Обратимся ко второму направлению, связанному со случайным

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

сложных объектов. Под «объектом», как и в § 1.1, будем

подразумевать некую часть окружающего нас мира, состояние

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

управление. Такой «частью» может быть модель объекта, и

объектом в этом случае является модель, с помощью которой

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

впоследствии на практике. Дело в том, что для принятия решения об

очередном акте управления объектом необходимо получить

информацию о его состоянии. Чем сложнее объект, тем больше такой

информации необходимо иметь. И процесс сбора информации, и

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

рандомизированными (от английского слова random — случайный).

Оказывается, что для сложных объектов управления такая

рандомизированная стратегия поиска решения часто бывает более

выгодной, чем регулярная, детерминированная.

Проще говоря, случайное поведение в процессе управления

сложным объектом часто бывает более эффективным, чем регулярное.

Этот на первый взгляд парадоксальный результат имеет глубокие

обоснования как математического, так и методологического характера,

которые будут приведены ниже.

Случайный поиск — или стохастический, статистический, ве-

роятностный, рандомизированный поиск — представляет собой

достаточно универсальный метод решения сложных задач, вы-

двигаемых современной наукой, техникой и народным хозяйством.

Рассмотрим основные предпосылки, черты, особенности и специфику

применения случайного поиска как очень эффективного современного

метода оптимизации и адаптации сложных объектов.

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

Случайный поиск как метод управления имеет свою историю,

связанную в основном с отстаиванием «права на существование».

Однако случайный поиск возник не на пустом месте: его появлению

предшествовал период предыстории, когда инструмент случайности

оттачивался на решении различного рода прикладных и

теоретических задач. Рассмотрим их.

I. Простейший, всем известной схемой, использующей идею

случайного поиска, является метод, называемый обычно методом

проб и ошибок. Строго говоря, его нельзя даже назвать методом, так

как довольно трудно точно определить, в чем же он состоит. В

действительности правильнее было бы говорить о методе случайных

проб и исправления ошибок.

Как видно, метод предполагает возможность случайных экс-

периментов (проб) с некоторыми объектами, причем допустим

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

характера, и их последствия легко устранимы (исправимы), т. е.

стоимость исправления допущенной ошибки невелика. Такова

ситуация, типичная для применения метода проб и ошибок. Само

применение метода связано прежде всего с использованием идеи

случайности: здесь пробы (эксперименты) всегда случайны, по-

скольку для их организации нет никаких иных соображений. В

самом деле, если бы такие соображения были, то отпала бы

необходимость в методе проб и ошибок.

Итак, метод проб и ошибок опирается на два существенных

предположения — нероковой характер ошибок и отсутствие ап-

риорных соображений о том, как и в каком направлении делать

пробы. Эти предположения почти неизбежно приводят к случаю.

Действительно, случайность в такой ситуации является

единственно разумной мерой: случайность почти ничего не стоит и

всегда содержит в себе искомое решение. Это значит, что достаточно

длительный поиск всегда приведет к решению задачи.

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

ошибок для решения практических задач, несмотря на его несколько

одиозную славу. (Вспомним, что часто мы так «обзываем» всякую

неудачную постановку эксперимента, когда априорных сведений

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

построения регулярного плана эксперимента. Однако подобная

ситуация складывается не столь часто, как хотелось бы: априорных

данных чаще бывает недостаточно, особенно в поисковых

экспериментах, и неизбежно приходится обращаться к пресловутому

методу проб и ошибок с его «неразумной», но спасительной

случайностью.)

II. Метод Монте-Карло появился в 1943 г. и с тех пор стал одним

из самых распространенных вычислительных методов. Метод Монте-

Карло представляет собой наиболее эффективное (и эффектное)

применение случайности. Математически он, как правило, связан с

вычислением многомерных интегралов в заданных областях, а

содержательно — с определением характеристик моделируемых

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

прежде всего тем, что он явился основой для моделирования сложных

процессов (например, технологических) с помощью ЭВМ.

Дело в том, что очень часто мы много знаем о деталях инте-

ресующего нас процесса, но почти ничего не можем сказать о его

поведении в целом. Иначе говоря, по локальному поведению процесса

необходимо определить его интегральные свойства. В простейшем

случае, когда локальные свойства процесса удается описать в виде

регулярных дифференциальных отношений, получаем

дифференциальное уравнение, интегрирование которого и позволяет

определить глобальные свойства процесса. Примером такого

уравнения является известный второй закон Ньютона.

Однако для сложных процессов, обладающих стохастическими

локальными свойствами, в лучшем случае получается стохастическое

дифференциальное уравнение, интегрирование которого представляет

огромные трудности, а в худшем — лишь правила перехода процесса

из одного состояния в другое. Эти правила имеют определенный

стохастический характер, т. е. всегда можно «разыграть» с помощью

ЭВМ конкретные случайные реализации переходов и тем самым

построить различные траектории процесса. Очевидно, что такие

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

говорит. Однако возможность построить с помощью ЭВМ большое

число траекторий нашего процесса открывает широкие перспективы,

которые и и использует метод Монте-Карло.

Действительно, поскольку каждая полученная траектория мо-

делирует поведение реального процесса, то интересующие нас

свойства процесса можно определить, обрабатывая траекторий как

различные наблюдения реального процесса. Например, таким

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

уклонения, дисперсию и другие вероятностные свойства нашего

процесса. Как видно, суть метода Монте-Карло состоит в

многократном моделировании («разыгрывании») случайного по-

ведения процесса и принятии каких-то необходимых решений на этой

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

локальное случайное поведение процесса с целью определения его

интегральных, глобальных характеристик, на основе которых

применяются управленческие решения.

Приведем пример применения метода Монте-Карло для решения

такой простой задачи, как определение среднего случайной

переменной. Прежде всего нужно уметь моделировать эту случайную

переменную, для чего необходимо знать ее распределение, с

помощью которого описывается локальное поведение исследуемого

процесса. Пусть р(х) — плотность распределения (х — значение

случайной величины).

Располагая этим распределением, можно поступить двояко. С

одной стороны, естественно воспользоваться известной формулой для

среднего как математического ожидания, которое вычисляется с

помощью интеграла:

(3.2.1)

С другой стороны, можно для оценки применить

метод Монте-Карло. В данном случае он заключается в том, чтобы

оценить среднее с помощью ряда специально генерированных

случайных чисел

, ..., x

, (3.2.2)

имеющих плотность распределения p(X). Тогда оценка среднего х

равна среднему этих чисел, т. е.

(3.2.3)

Здесь через обозначена монте-карловская

оценка на базе N чисел (3.2.2). Как видно, все трудности метода

заключаются в «разыгрывании» этого ряда случайных чисел в

соответствии с заданным распределением р(х). Если же мы

располагаем возможностью наблюдать реальный процесс, то ряд

(3.2.2) представляет собой результаты конкретных наблюдений

этого процесса.

Таким образом, метод Монте-Карло обходит трудности, связанные

с наблюдением реального процесса, и позволяет получить ряд (3.2.2)

путем моделирования случайной величины х в соответствии с

имеющейся плотностью распределения р(х). Дальнейшая обработка

(3.2.2) производится аналогично.

Этот подход легко обобщается На любую функцию y=f(x) от

случайного аргумента х. Выражение

(3.2.4)

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

(3.2.5)

Естественно задать вопрос: не проще ли — а

главное, не точнее ли — вычислить интеграл (3.2.1), например,

методом трапеций, чем оценивать его по формуле (3.2.3) с помощью

ряда специально разыгранных чисел (3.2.2)? Ответ зависит от слож-

ности и требуемой точности вычисления данного интеграла.

В одномерном случае, когда х — скаляр ( ), среднее ,

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

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

X = (x

, ..., x

) (3.2.6)

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

(3.2.7)

представляет уже довольно сложную задачу,

точность решения которой уменьшается с ростом размерности n

интеграла. Это и создает преимущество для метода Монте-Карло. В

формуле (3.2.7) f(X) — заданная скалярная функция вектора X, р(Х) —

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

компонент вектора X равна р(Х) = p

) ... р

(х

), где p

) —

плотность распределения j-й компоненты x

. Здесь и случайный

вектор X распределен по заданному многомерному закону р(Х). При

этом оценка многократного (n-крат-ного) интеграла (3.2.7) имеет вид

(3.2.8)