Варшавский В. И., Поспелов Д. А.

Варшавский В. И., Поспелов Д. А.

Оркестр играет без дирижера: размышления об эволюции некоторых технических систем и управлении ими.—М.: Наука. Главная редакция физико-математической литературы, 1984.— 208 с., 50 илл.

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

Издательство «Ника» Главная редакция

физико-математической Литературы, 1981

ВМЕСТО ПРЕДИСЛОВИЯ

13 февраля 1922 года в Москве состоялось пер" вое публичное выступление Персимфанса — Первого симфонического ансамбля Моссовета. Это выступление стало настоящей сенсацией для всех профессионалов и любителей музыки.

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

А музыканты Персимфанса сидели совсем иначе. Струнные сидели, образуя полный круг (частично спиной к зрителям!), а духовые располагались в середине этого круга. Каждый музыкант видел каждого, ибо в Персимфаисе каждый слушал каждого и всех, а все слушали каждого. Не было никакого трюка. Взаимодействуя непосредственно друг с другом, прекрасные музыканты, входившие в Перспмфанс, легко обходились без дирижера.

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

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

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

Авторы ее поставили перед собой задачу рассказать на популярном уровне о проблемах управления в сложных системах, которые в теории управления принято называть большими. В подобных системах часто приходится переходить от централизованного управления к децентрализованному. Это представляет собой как бы плату за сложность, присущую большим системам. Централизованное управление в них, как правило, неэффективно, а в ряде случаев просто невозможно. Но откуда берутся столь сложные системы? Не есть ли категория больших систем паду' манной? Как мы постарались показать в книге, мир больших систем, окружающих человека, все время обогащается. Рост сложности искусственных систем, создаваемых человеком, происходит постоянно. Идет эволюционное развитие созданных ранее искусственных систем, в какой-то степени напоминающее эволюцию в мире живых организмов. Децентрализованное управление—закономерное порождение этой эволюции. И наша задача — убедить читателей в справедливости этих утверждений.

Глава 2 ПРОСТО ЛИ СУЩЕСТВОВАТЬ В СЛОЖНОМ МИРЕ?

«Подражанье, повторенье — мира этого дела.

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

Награждались бы старанья, исполнялись бы желанья,

А возмездия угроза бесполезная спала».

Омар Хайям

Парадоксы целесообразности

Лиса вернулась с богатой добычей. Часть ее насытила лисий выводок, а оставшуюся пищу лиса прячет «на черный день». Тщательно роет яму, кладет в нее мясо и засыпает его землей. Наблюдая за ее поведением, можно прийти к выводу, что цель действий лисицы порождена ее «интеллектом». Столь целесообразно и «разумно» ее поведение.

Но судьба оказалась для нашей героини по очень счастливой. Она попала в западню и стала жительницей зоопарка. Теперь ей уже не приходится тратить силы на добывание пищи. Ее кормят служители. Но что делать лисе, когда пищи избыток? Конечно, спрятать! И лиса скребет когтями бетонный пол вольера, а через некоторое время, когда «яма» готова, «прячет» в нее мясо. И после этого перестает обращать внимание на остаток трапезы, который, конечно, так и остается лежать на полу вольера. Лиса просто игнорирует его, не видит «зарытое» мясо. То, что в привычной для животного среде выглядело целесообразно, в условиях другой реальности становится лишенным каких-либо черт разумности.

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

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

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

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

Простейшие лабиринты — Т-образные. На рис. 2.1 показано два таких лабиринта. Рассмотрим сначала верхний. Его использовал для своих опытов с обычными дождевыми червями американец Йеркс. В начале опыта черви помещались на площадку в основании буквы Т. Эту площадку ярко освещали, и червь начинал движение, стремясь найти более комфортабельное место. Там, где коридор имел раз-

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

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

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

Рассмотрим теперь нижний лабиринт, показанный на рис. 2.1. Его использовал другой зоопсихолог— Торндайк для опытов с крысами. При разветвлении коридора голодная крыса, привлекаемая запахом приманки, должна сделать альтернативный выбор между левым и правым коридорами. Но в каждом из них крысу ждут неприятные ощущения от раздражения электрическим током. Эти раздражения происходят с фиксированными вероятностями Рп и Pл , которые не изменяются в одной серии опытов. Цель эксперимента — определить, сможет ли крыса в процессе обучения научиться выбирать только тот коридор, ведущий к пище, в котором вероятность электрического раздражения меньше.

Опыты Торндайка повторяли неоднократно. В экспериментах принимали участие не только кры-

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

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

И лишь через 50 лет наступило время посмотреть па поведение червей и крыс с иной точки зрения.

Маленькая зверушка»

Моделирование и объяснение эффекта Йеркса и Торндайка были получены в цикле исследований по моделированию простейших форм поведения, выполненных в 60-х годах нашего века оригинальным и глубоким советским ученым, оказавшим заметное влияние на все развитие работ в области моделирования поведения, Михаилом Львовичем Цетлиным. Он был одповременно и изобретательным инженером, и великолепным математиком. Активно и вовсе не дилетантски интересовался медициной и биологией. Талант инженера, превосходная математическая интуиция и способность к точной, но одновременно весьма образной интерпретации фактов самых раз-

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

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

Вернемся к схеме опыта Торндайка. На рис. 2.2 показана некоторая интерпретация этой схемы. Маленькая зверушка воспринимает из окружающей среды сигналы, которые являются оценками действий, совершенных ею перед этим. Эти оценки будут нами рассматриваться как двоичные: поощрение за выполненное действие (нештраф) и наказание за него (штраф). Зверушка может выбирать свои действия из некоторого заданного конечного набора D==[di, ds, ..., dn]. Значения оценок действия (будем их обозначать 1 и 0) формируются средой. Одна среда

отличается от другой тем, как вырабатываются оценки. Рассмотрим один важный частный случай, когда среда формирует эти оценки следующим образом. Если зверушка делает в некоторый момент действие di , то с вероятностью Pi среда выдает оценку «наказание» (штраф) и с вероятностью 1—Pi —оценку «поощрение» (нештраф). Если с течением времени значения Pi остаются неизменными, то такая среда называется стационарной. Для полного определения стационарной среды достаточно задать вектор E=(P1,P2,...,Pn).

Вернемся к опыту с крысой, описанному выше. В нем мы имеем дело со стационарной средой вида Е=(Рп,Рл), компоненты которой характеризуют вероятности наказаний (болевых раздражений) при выборе крысой правого или левого коридоров в Т-образном лабиринте. Эти выборы характеризуют множество действий крысы.

М. Л. Цетлин поставил перед собой вопрос: «Сколь сложным должна быть зверушка, которая подобно крысе в опытах Торндайка могла бы адаптировать свое поведение к стационарной среде так, чтобы всегда вести себя наиболее целесообразным образом?» Но прежде чем дать ответ на подобный вопрос, следует уточнить само понятие целесообразности поведения.

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

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

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

Пусть, например, в Т-образном лабиринте Рп=0,9, а Рл = 0,4. Если бы крыса заранее знала эти вероятности, то она, конечно, всегда бы предпочитала бежать в левый коридор. Суть опытов Торнданка а том, что именно это предпочтение и сформируется у крысы после некоторого опыта предварительного обучения. Если при наших значениях вероятностей штрафов за действия крысу поставить в условия равновероятного выбора (ввести открывающиеся равновероятно дверцы), то суммарное значение штрафа для нее будет равно М == 0,5*0,9 + 0,5*0,4 == 0,65. Поведение крысы будет целесообразным, если суммарный штраф, накопленный ею, будет меньше 0,65. А наилучшим ее поведением будет то, при котором этот штраф достигнет своего минимума (при выборе только левого коридора). В этом случае М=0*0,9+1*0,4=0,4.

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

Доживем до понедельника»

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

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

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

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

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

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

Посмотрим на рис. 2.11. На нем изображен граф смены состояний некоторого вероятностного автомата. Его особенность состоит в том, что для каждой группы состояний (на рисунке группы состояний оконтурены пунктирными линиями) имеется ненулевая вероятность перейти в особое состояние, в котором автомат погибает (на рисунке оно заштриховано). Состояния можно интерпретировать, например, следующим образом: 1 — летучая мышь производит поиск и с вероятностью 0,3 обнаруживает бабочку, а с вероятностью 0,7 пропускает ее (для первой группы состояний); 2—летучая мышь определяет направление своего движения и расстояние до жертвы, причем с вероятностью 0,8 цель при этом не теряется; 3 — летучая мышь настигает бабочку и уничтожает ее с вероятностью 0,95. Что же может противопоставить преследователю бабочка? В чем заключаются ее действия? Будем рассматривать каждую группу состояний автомата как определенную

среду, задаваемую той стратегией бабочки, которой она придерживается. Трем группам состояний, показанных на рис. 2.11, можно, например, соотнести следующие стратегии: прямой полет (E1), пикирование или кабрирование (E2) и хаотическое движение (Ез). Действия бабочки сводятся к смене сред, переключению их. При этом бабочка может реализовать действие лишь в состояниях 2 и 3. На рис. 2.11 эти действия показаны двойными стрелками

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

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

Пусть, например, как и в нашем примере, имеется три случайных среды, которые автомат может переключать своими действиями. И пусть имеется три обычных состояния и три поглощающих (летальных), в которых автомат погибает. Первые три мы, как и ранее, будем обозначать цифрами 1, 2, 3, а поглощающие состояния — цифрами 4, 5, 6. Вместо рисунка, подобного рис. 2.11, зададим три матрицы переходов автомата в трех возможных средах (табл 2.1)

Таблица 2.1

				Состо	ЯНИЯ
Среда	Состояния	1	2	3	4	5	6
	1	0,9			0,1
	2	0,95				0,05
Е1	3 4	0,8			1		0,2
	5					1
	6						¹
	1		0,9		0,1
	2		0,7			0,3
E2	3 4		0,95		1		0,05
	5					1
	6						1
	1			0,9	0,1
	2			0,92		0,08
E3	3 4			0,7	1		0,3
	5					1
	6						1

В табл. 2.1 указаны только ненулевые значения переходных вероятностей Пиij. Если начальное состояние автомата есть i (i== 1, 2, 3), то время жизни автомата можно вычислить по формуле

Здесь М* — время жизни автомата с начальным состоянием j при оптимальном переключении им сред, d(i) — значение функции выхода автомата для состояния с номером i, т. е. номер той среды, на которую автомат переключает в этом состоянии текущую среду, Пиij(d (i)) — переходные вероятности смены состояний в среде с номером d(i). Очевидно, что оптимальное переключение d*(i) будет достигнуто тогда, когда будет получен maxМj для всех j (или max min Mj,

Мы не рассчитываем на то, что читатель будет в состоянии выдержать аналитические выкладки, лежащие в основе процедуры построения оптимального переключения. Отметим только, что такая процедура существует. И строго показано, что она позволяет автомату вероятностного типа осуществлять поиск оптимального способа переключения сред. Для подготовленного читателя укажем лишь на то, что, по сути своей, эта процедура есть модификация схемы динамического программирования Беллмана. Для нашего примера оптимальное переключение задается следующей функцией выхода: d{1)=3, d(2)==3, d(3)=2. При этом M3*= 15,47; М2*=15,23;

M1*=13,92. Общее время жизни автомата, выполняющего переключение сред, в полтора раза больше времени его жизни в пассивном режиме. А, значит, ночная бабочка совсем не зря тратит усилия на смену стратегии своего полета.

От индивида к коллективу

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

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

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

Прежде чем перейти к решению этих проблем, остановимся на той концептуальной схеме, которая будет лежать в основе всех наших дальнейших рассуждений. Читатель легко соотнесет ее с моделями, которые обсуждались нами в гл. 1 нашей книги. Эта модель изображена на рис. 2.12. Коллектив из

k автоматов взаимодействует со средой. Каждый из них делает это самостоятельно, не зная не только о действиях других членов коллектива, но и об их существовании. Для каждого автомата остальные участники коллектива как бы растворяются в среде, выступают по отношению к данному автомату как часть среды. Если в некотором такте взаимодействия автоматы зафиксировали свои действия, то среда воспринимает их как комбинированное воздействие, описываемое набором (di₁¹, di₂², ..., di_k^k), где верхний индекс указывает номер автомата в коллективе, а нижний — выбранное им действие. Среда может формировать оценочные сигналы на автомат либо на основании действий некоторой части или всех автоматов, либо на основании действий только данного автомата. Во втором случае коллектив разваливается и вся задача коллективного поведения сводится к рассмотрению k независимых друг от друга задач индивидуального поведения. Этот крайний случай не представляет интереса, и в дальнейшем мы его исследовать не будем. В первом же случае среда может как-то регулировать совместное воздействие автоматов и он представляет для нас принципиальный интерес.

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

И, наконец, вполне правомерно рассматривать все k автоматов и механизм непосредственного обмена (если он существует) как подсистемы некоторого организма, взаимодействующего со средой. Такая трактовка в ряде конкретных моделей будет нами использована в последующих главах книги.

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

Когда все одинаковые

Давайте теперь несколько усложним нашу модель. Чем вызвана необходимость ее изменения?

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

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

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

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

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

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

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

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

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

Из рис. 3.6 видно, что правее точки а0 выигрыш каждого участника на второй стратегии выше, чем на первой, к смена первой стратегии на вторую выгодна для игрока. Однако переход игрока с первой стратегии на вторую уменьшает долю игроков, выбравших первую стратегию, смещая ее к точке а0. Левее точки а0 выгоднее оказывается первая стратегия, и переход игроков со второй стратегии на первую увеличивает долю игроков на первой стратегии, смещая ее к точке а0. В точке же а0 выигрыши на обеих стратегиях одинаковы. Если в точке а0 игрок перейдет с первой стратегии на вторую, то доля игроков, выбравших первую стратегию, уменьшится и соответственно уменьшится выигрыш на второй стратегии, что делает такой переход невыгодным для игрока, осуществляющего этот переход. Аналогично в точке а0 оказывается невыгодным для игрока переходить со второй

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

точкой Нэша.

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

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

для первого участка 400*Х—0,02*Х³,

для второго участка 280*Y— 0,4*Y².

Тогда, если 80 рабочих будут работать на первом участке, то общая выработка на этом участке будет равна 21 760 руб., т. е. по 272 руб. на человека. На втором участке при этом будут работать 20 человек, которые обеспечат выработку 5440 руб., т. е. те же, что и на первом участке 272 руб. на одного рабочего. Суммарная выработка на обоих участках равна 27 200 руб., и ни одному из рабочих не выгодно изменять место своей работы. Действительно, например, переход рабочего со второго участка на первый уменьшает его заработок на 3 руб.

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

на 8 руб. 40 коп. за счет работающих на втором участке.

Из сказанного видно, что, с одной стороны, распределение рабочих по участкам, при котором 80 человек работают на первом участке, а 20 на втором устойчиво по Нэшу, но, с другой стороны, переход рабочих с первого участка па второй приводит к увеличению общей производительности. Общая выработка достигает максимума, когда на первом участке остается 51 человек, а остальные 49 работают на втором участке. При этом общая выработка на первом участке становится равной 17748 руб., при заработке каждого рабочего, равном 348 руб., а на втором участке выработка достигает 12740 руб., при заработке каждого рабочего в 260 руб. Выработка на обоих участках при этом возрастает по сравнению с точкой Нэша на 12 % и достигает 30488 руб. Для большей наглядности все данные сведены в табл. 3.1.

Таблица 3.1

	Точка Нэша	Точка Мора
Зарплата на первом участке	272	348
Зарплата на втором участке	272	260
Средняя зарплата	272	304,88
Доход на первом участке	21 760	17748
Доход на втором участке	5 440	12740
Суммарный доход	27200	30488

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

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

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

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

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

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

Пусть а_{1 и}а₂ (а₂=1—а₁) — доли автоматов, выбравших в некоторой партии игры первую и вторую стратегии соответственно. Пусть P₁ и P₂ —вероят-

ности единичного выигрыша, равного для нашего примера 400 руб., и, значит, (1—p₁) и (1—p₂) — вероятности единичного проигрыша той же суммы. Тогда функции, задающие игру, определяют математическое ожидание единичного выигрыша при

p₁==1—0,25а₁² и p₂==0,85—0,05а₂.

При а₁==0,8 и а₂==0,2 автоматы, выбравшие первую стратегию, будут выигрывать с вероятностью 0,84 и проигрывать с вероятностью 0,16. Если, как мы предположили, единичные выигрыши и проигрыши равны :±400 руб., то математическое ожидание выигрыша на первой стратегии будет равно (0,84—0,16)*400=272 руб., что совпадает с выигрышем в точке Нэша.

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

(1 —p₁)a₁ = (1 —p₂)a₂ или 0,25а₁³ =(0,15+0,05а₂)а₂.

Решением этого уравнения служит а₁=0,63 и а₂==0,37. При этом в каждый момент времени 0,63 всех автоматов будет изменять свою стратегию с первой па вторую и столько же автоматов будет перехо-дить со второй стратегии на первую.

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

тов уменьшает вероятность смены действия. Однако для каждой вероятности смены действия существует ситуация динамического равновесия, которая, как мы уже говорили выше, с ростом глубины памяти стремится к точке Нэша. Теперь средний выигрыш в игре зависит от взаимного расположения точек, соответствующих партиям игры. Обозначим через а_A долю автоматов, выбравших первую стратегию в партии Антоса, через a_н — долю автоматов, выбравших первую стратегию в партии Нэша, и через а_м—долю автоматов, выбравших

первую стратегию в партии максимальной цены. Пусть а_н> >а_А>а_м, что, кстати, имеет место в нашем примере, где а_н= =0,8, а_А==0,63, а_м= =0,51. Тогда с ростом глубины памяти распределение автоматов по стратегиям будет удаляться от партии максимальной цены к

партии Нэша и средний выигрыш автоматов будет падать. Действительно, в нашем примере средний выигрыш автоматов в партии Антоса равен 299,28 руб., а в партии Нэша — 272 руб. На рис. 3.7, 3.8, 3,9 приведены типы зависимости среднего выигрыша от глубины памяти автоматов при различных типах взаимного расположения точек, соответствующих партиям игры,

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

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

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

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

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

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

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

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

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

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

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

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

Типичным примером являются, например, некоторые блоки оптимизации в операционных системах вычислительных машин. Если такой блок за 2 ч работы на 5 % увеличивает пропускную способность вычислительной машины, то даже при ее круглосуточной работе действительная производительность машины не возрастает, а падает на 3 %.

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

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

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

Еще три простые модели

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

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

108

столько, что они начинают испытывать голод. Голодают и плазмиды. Это приводит к тому, что плазмиды, оказавшиеся за граничным значением голодания, начинают вырабатывать не иммунопротеин, безвредный для бактерии-хозяина, а комицин. На рис. 3.19,6 показана такая ситуация, когда одна из плазмид начинает вырабатывать комицин (зачерненные квадратики в теле бактерии). Комицин убивает бактерию и плазмиду. Но комицин, попадая во внешнюю среду, убивает в определенной окрестности все бактерии, не содержащие в своем теле иммунопротеин (рис. 3.19, б), после чего в среде остается уже меньшее число бактерий (рис. 3.19,г), Если их все еще слишком много, то найдется такая плазмида, которая опустится ниже «порога жизни" и начнет срабатывать комицин, что приведет к дальнейшему сокращению популяции бактерий. Плазмиды же делятся вместе с бактериями только тогда, когда пищи становится «слишком много", выше некоторого

109

порога, превышение которого вызывает деление у «чистых» бактерий.

Эту реальную модель саморегулирования численности организмов можно представить и в виде неоднородного коллектива автоматов, живущего в некоторой среде, в которой поддерживается постоянный уровень пищи. Вся пища делится поровну между членами коллектива. Автоматы - плазмидоносители делятся в том случае, когда количество поглощаемой ими пищи превышает некоторый порог Q₁. Остальные автоматы производят деление при более низком пороге Q₂. Когда автомат - плазмидоноситель получает пищи меньше, чем Q₃ < Q₂, то он погибает и уничтожает все обычные автоматы, которые находятся от него на определенном расстоянии (например, на торе в клетках, отстоящих от данной на расстоянии, не превышающем 5-кратного размера клетки). Для того чтобы одновременно не погибли все автоматы - плазмидоносители в модели, случайным образом выбирается один из них. Если после этого уровень пищи все еще не превосходит Q₃, то случайным образом выбирается еще один автомат, способный уменьшить величину популяции. Моделирование такого процесса на ЭВМ показало почти точное совпадение процесса регулирования с тем, что происходит в природе у бактерий.

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

110

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

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

Рассмотрим модель подобного соперничества. Агрессивную и угрожающую стратегии будем обозначать соответственно буквами А и У. Составим таблицу, в которой оценены все возможные комбинации парного соперничества (табл. 3.6).

Таблица 3.6

		Вто	рой
		А	У
Первый	А	(-5, -5)	(+10, 0)
	У	(0, +10)	(+2, +2)

На пересечении строк и столбцов таблицы стоят пары чисел. Это условные оценки выигрышей — проигрышей соперников при выборе той или иной стратегии поведения. Если, например, один из них (первый) выбрал стратегию А, а второй — стратегию У, то первый получает выигрыш, равный 10 условным единицам, а второй остается при «своем интересе». Поясним теперь, как возникли эти оценки. Сначала мы условно оцениваем победу при соперничестве как выигрыш, равный +10, серьезное повреждение или гибель, которые могут произойти при наращивании усилий в стратегиях А, оцениваем как (—20). Поскольку при встрече двух агрессоров исход поединка мы считаем равновероятным, то математические ожидания поощрения — наказания при паре стратегий (А,А) есть 0,5*10+0,5*(—20)= --5. Аналогично для встречи со стратегиями (У,У) это ожидание

111

вычисляется как 0,5*10+(—3)=2. Здесь оценка (—3) есть плата за нервное напряжение в длительном конфликте при стратегии У. Эта стратегия приводит к значительному расходу нервных и других ресурсов животного. Таким образом, таб. 3,6 задает платежную матрицу некоторой игры.

Рассмотрим организм, который может по своему желанию менять свою стратегию в зависимости от обстоятельств. Этот организм можно смоделировать в виде автомата с двумя состояниями, соответствующими стратегиям А и У, использование которых определяется вероятностями Р_A и Ру . При этом, конечно, Р_A+Ру=1. Рассмотрим коллектив, состоящий из подобных автоматов, и предположим, что он неоднороден, причем неоднородность задается различными значениями Р_A. В частности, при Р_A==1 автомат является чистым агрессором. Он во всех случаях жизни придерживается стратегии А. При Р_A==0 автомат всегда придерживается стратегии У.

Как и в предшествующей модели, зададим некоторые пороги Q1 и Q2. Если автомат накапливает выигрыш, превышающий Q1, то он «размножается». Вместо него появляются два автомата с тем же значением Р_A у каждого. Если же накопленное наказание становится по абсолютной величине больше Q2, то автомат «вымирает». Возникает вопрос об оптимальном значении Р_A при случайном парном взаимодействии автоматов в коллективе. При моделировании на ЭВМ было показано, что коллектив из достаточно большого количества описанных автоматов, в котором значения Р_A имели распределение, близкое к равномерному, эволюционирует в сторону однородного коллектива, для которого Р_A приближается к значению 8/13. Из теории игр следует, что смешанная стратегия, при которой стратегии А и У выбираются с вероятностями 8/13 и 5/13, является для игрока в определенном смысле наилучшей. Она обеспечивает игроку максимально возможный гарантированный выигрыш (при самых наихудших для него действиях противника). Интересно было бы получить экспериментальные данные из наблюдений за животными (например, кошками), которые давали бы оценки частоты выбора ими стратегий А и У при встрече с противником, равным по силе. К сожалению, такими данными мы не располагаем.

112

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

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

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

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

113

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

Г л а в а 4 КОГДА "ВСЕ ПО СПРАВЕДЛИВОСТИ"

«Мы холодны душой к нелепым чудесам.

И лишь возможное всегда по вкусу нам».

Буало

Прав ли был Остап Бендер?

«..у окошечка администратора господствовало оживление. Там стояла цветная очередь. Молодые люди, в фасонных пиджаках и брюках того покроя, который провинциалу может только присниться, уверенно размахивали записочками от знакомых режиссеров, артистов, редакций, театрального костюмера, начальника района милиции и прочих, тесно связанных с театром лиц, как то: членов ассоциации теа- и киноработников, общества «Слезы бедных матерей», школьного совета «Мастерской циркового эксперимента» и какого-то «Фортинбраса при УМСЛОПОГАСЕ». Человек восемь стояли с записками от Эспера Эклеровича.

Остап врезался в очередь, растолкал фортинбрасовцев и, крича:—«Мне только справку, вы же видите, что я даже калош не снял!», пробился к окошечку и заглянул внутрь».

Прав ли был герой романа «Двенадцать стульев», когда считал, что с коротким делом можно прорываться без очереди, или великий комбинатор заблуждался? Как должна была вести себя очередь? И как себя должен был вести администратор?

Очередь! Очередь становится таким же спутником нашего быта, как еда, сон, развлечения. Впрочем, как не вспомнить здесь очередь за едой в столовой, очередь за сном в гостинице, очередь за развлечением в театральной кассе. Временами нам кажется, что очередь является порождением чьей-то злой воли, результатом деятельности враждебных сил. Однако в действительности, возникновение очередей — такая же закономерность, как выпадение снега зимой и дождя летом. Плохая, неразумная организация не порождает очередь, а лишь увеличивает ее длину.

116

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

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

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

Весь комплекс обслуживающих средств: место обслуживания, обслуживающий персонал и т. п. в совокупности с правилами обслуживания мы будем называть каналом обслуживания*).

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

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

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

116

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

У внимательного читателя может возникнуть сомнение в логичности наших определений. С одной стороны, мы включаем клиентов в качестве элементов в систему обслуживания, а, с другой стороны, говорим, о том, что клиенты попадают откуда-то в эту систему. Но противоречие это чисто внешнее. Клиенты действительно попадают в систему обслуживания извне, но затем становятся ее элементами. И дрова в отопительной системе могут проиллюстрировать эту мысль.

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

Как клиенты поступают в систему? Самый простой способ — поступление клиентов через равные промежутки времени. Если время обслуживания меньше этого промежутка или равно ему, то очередь возникать не будет. Если же время обслуживания превышает интервал между появлениями клиентов, то очередь будет неограниченно возрастать.

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

117

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

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

Работая над гл. 3, мы в один из дней решили посмотреть кинофильм и начали звонить в ближайший кинотеатр, чтобы узнать репертуар и время начала сеансов. Телефон кинотеатра, как всегда, был непрерывно занят. Непрерывно набирая номер в течение 20 мин, мы наконец услышали:

— «Здравствуйте! Вам отвечает автоответчик кинотеатра «Прометей». Сегодня смотрите в нашем кинотеатре: на детском утреннике в 9 ч утра кинофильм «Внимание, черепаха!». На сеансах 11 и 13 ч новая кинокомедия «Мимино». Новый художественный фильм «Приезжая» на сеансах 15 ч, 16 ч 40 мин, 18 ч 30 мин, 20 ч 20 мин и 22 ч 10 мин. Приглашаем посетить наш кинотеатр. Наш адрес: проспект Просвещения, д. 20». На часах было 16 ч, и нам казалось, что половину сообщения, которое мы прослушали, можно было бы опустить — нас мало интересовало, что показывали в кинотеатре до 16 ч. Нам казалось, что можно было опустить также две первых и предпоследнюю фразы — сокращение времени, необходимого для того, чтобы дозвониться до кинотеатра, с лихвой компенсировало бы некоторое отсутствие избыточной вежливости в ответе. Мы взялись за карандаши.

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

118

pa, потребовалось бы 4 мин вместо 20 мин. Этот выигрыш оправдывает затраты на смену пленки в автоответчике после начала каждого сеанса. Ведь если нам просто не повезло и среднее время, которое необходимо затратить, чтобы дозвониться в справочное бюро кинотеатра, равно не 20, а только 10 мин., то и в этом случае уменьшение вдвое времени обслуживания дает в час экономию около десяти человеко-часов, проведенных у телефона. Трудности ликвидации такого положения заключаются в том, что тысячи человеко-часов в месяц, затрачиваемые у телефонов в бесплодных попытках дозвониться в справочные службы кинотеатров, дополнительные нагрузки на каналы телефонной связи и коммутационное оборудование телефонных станций ни в коей мере не влияют на оценку эффективности функционирования кинотеатров и их справочных служб. Аналогичные выводы, кстати, можно сделать о большинстве телефонных систем обслуживания, куда чрезвычайно сложно дозвониться.

Моральный и материальный ущерб, приносимый очередями людям, очевиден. Но, быть может, он не столь уж важен, если речь идет о неодушевленных предметах? К чему в этом случае сводится ущерб, приносимый очередью?

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

Во-вторых, клиенты, стоящие в очереди, изъяты из употребления. Люди, стоящие в очереди в магазине, в это время не работают, не читают книги, не воспитывают своих детей. Автомобили, стоящие в очереди на ремонт, не перевозят грузы. Стоимость

119

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

Из сказанного ясно, что задача снижения средней длины очереди имеет явный экономический смысл.

Выше мы уже видели на примере, что среднюю длину очереди можно снизить, если уменьшить время обслуживания или, что эквивалентно, увеличить пропускную способность системы. Однако очень часто мы не в состоянии влиять на этот параметр. Можем ли мы вместе с тем уменьшить среднюю длину очереди?

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

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

120

(сбитым), так как он дольше других клиентов (самолетов) будет находиться в зоне обслуживания.

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

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

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

Проблема нескольких арен

Цирк, наверное, самое древнее в мире искусство. Во всяком случае, одно из древнейших. И за тысячелетия своего существования цирк, конечно, изменился. Но со времен появления в нем круглой арены диаметр ее во всех цирках мира стандартен. Все цирковые номера рассчитаны на его величину, изме-

132

нение ее может привести к трагическому исходу опасного номера (а какие номера в цирке не опасны?). Поэтому возникло острое противоречие между размером арены и стремлением сделать помещение цирка более вместительным. Но если арена не может быть увеличена, то как увеличить размер зрительного зала? Сидящим вдали от арены мало удастся увидеть, и уж тем более они не смогут испытать того «эффекта присутствия», которым так славится цирк.

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

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

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

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

133

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

Среди систем вычислительных машин, решающих различные хозяйственные, информационные или научные задачи, можно выделить группу систем с постоянным набором программ, хранящихся в их памяти. Такие системы предназначены для решения конечного набора задач N1, N2, ... , Nk . Число машин, входящих в систему, равно l, и имеет место неравенство l>k. Обозначим программы для решения тех или иных задач через M1, M2, .... Mk; с их помощью решаются нужные потребителям задачи. Заявки на выполнение программ поступают на вход системы в случайном порядке, и система не знает априори никаких характеристик этого потока.

Каждая машина системы может быть настроена на выполнение некоторой определенной программы Mi (i = 1, 2, ..., k). Это означает, что в оперативной памяти машины хранится сама программа для решения задачи Ni и необходимые для этого исходные данные. Подобно арене, приготовленной для выступления определенной группы артистов, такая вычислительная машина подготовлена для выполнения вполне определенной программы. Настройку системы машин будем производить децентрализованно. Для этого придадим каждой ЭВМ автомат, имеющий k состоянии. Пусть p_ij есть вероятность смены состояния с номером i на состояние с номером j (перенастройка ЭВМ с программы Мi на программу Мj). Как всегда Сумма (p_ij)=l. Если автомат Am (т — номер ЭВМ в системе и т=1,2,..,l) настроен на выполнение программы Mi и свободен, а на вход системы поступает заявка на ее выполнение, то Am берет эту заявку на обслуживание и получает сигнал поощрения. Автомат Am есть автомат с переменной структурой, о котором мы рассказывали в гл. 2. Поэтому, получив сигнал поощрения, он увеличивает вероятность р_ii и пропорционально уменьшает остальные вероятности p_ij для i не равное j . Если автомат при поступлении требования на решение задачи Ni был настроен на нее, но уже выполняет другое, ранее

134

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

Пусть автомат Am настроен на выполнение программы Mi и свободен, а вновь пришедшая заявка требует выполнения программы mj при j i; тогда поощрение и наказание Am зависят от той ситуации, которая сложилась в данный момент в вычислительной системе. Если среди свободных автоматов имеются такие, которые настроены на М,, то они берут заявку на обслуживание, а на вход Am никакого сигнала не поступает. Он продолжает ждать «свою законную» заявку. Если же таких автоматов в системе нет, то они отказываются от обслуживания, а все свободные автоматы (в том числе и Am), получают сигнал наказания. Этот сигнал заставляет Am уменьшить значение р_ii и увеличить пропорционально все остальные значения р_ij при i не равном j.

Что может дать такая модель настройки? Нетрудно видеть, что вычислительные машины системы с помощью настраиваемых автоматов будут выбирать из входного потока требований на обслуживание прежде всего те, которые чаще всего в этом потоке встречаются. Вспомнив о парикмахерской, мы можем сказать, что мастера всегда готовы обслужить клиентов, регулярно появляющихся в парикмахерской, а случайный приезжий, как правило, получит у них отказ со ссылкой на то, что часть мастеров заняты, а остальные ждут своих клиентов, которые «вот-вот должны подойти».

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

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

135

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

Разницу в предложенных двух способах адаптации автоматов можно проиллюстрировать на конкретном примере, полученном путем моделирования на вычислительной машине. Будем оценивать качество функционирования системы отношением Н=L*/Lt, где L* —число выполненных заявок за некоторый фиксированный интервал времени, a Lt — число всех поступивших за это время заявок. Пусть вычислительная система состоит из двух ЭВМ, настроенных на выполнение одной из четырех программ M1, М2, М3 и M4 соответственно автоматами А₁ и А₂. На вход системы обслуживания поступает поток требований на выполнение указанных программ. Характеристики этого потока, неизвестные для A1 и A2 в описываемом эксперименте, были заданы следующими вероятностями появления заявки определенного типа: P1=0,15, P2=0,30, Рз=0,45, Р4=0,10. До обучения системы Н=0,5. После обучения по первому способу Н=0,54. Таким образом, первый способ обучения оказывается не слишком эффективным. Если же второй автомат обучается на потоке, остающемся после отбора из него заявок первым автоматом, который так адаптировался, что он настраивается на выполнение только одной программы, то при втором способе обучения Н=0,57 после обучения первого автомата, а после обучения автомата А2. значение Н стало равно 0,63. Если же второй автомат заявок не теряет, то при определенном периоде наблюдения Н= 0,85.

Рассмотренная нами задача о распределении ЭВМ вычислительной системы по заявкам на обслуживание, поступающим случайным и заранее неиз-

136

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

137

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

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

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

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

Можно ли в этой ситуации улучшить качество принимаемых решений? Можно. За счет введения очень простого правила участия в голосовании. Каждый член совета в течение, например, года может голосовать ограниченное число раз. Тогда в каждом

138

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

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

Выше мы же заметили, что процедура голосования не всегда обеспечивает принятие решения. Решение может оказаться невозможным, если для его принятия требуется 2/3 голосов или если решение должно быть принято абсолютным большинством, а число возможных решений превышает два. Известно несколько процедур, устраняющих такие тупиковые ситуации. Голосование проводится в несколько туров. Если в очередном туре не удалось выработать решение, то может быть снижено число решений, участвующих в следующем туре, или отброшены решения, получившие наименьшее число голосов, или, как это имеет место на президентских выборах во Франции, изменено соглашение о принятии решения, и в последнем туре оно принимается относительным большинством. Однако при таком механизме все вынуждены согласиться с принятым решением, но большинство голосовавших с ним не согласно. С другой стороны, наличие права вето, казалось бы, полностью зачеркивает возможность эффективного применения процедуры голосования для принятия решений.

Попытаемся все-таки подумать, каким же образом можно добиваться принятия решений при наличии права вето и явно противоречивых интересах участвующих в голосовании. Для этого обратимся к сформулированной М. Л. Цетлиным «Задаче о жилищной комиссии». В лекции, прочитанной им на заседании секции Физиологического общества в Москве 23 февраля 1965 г., он говорил: «...в нескольких словах я хочу пояснить, в чем состоит трудность распределения жилплощади и какое отношение имеет она к автоматам. Имеется сколько-то квартир, вообще говоря, не очень много, гораздо меньше, чем число нуждающихся. Если бы их было много, то

139

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

Имеется N нуждающихся в квартирах, и имеется т членов комиссии, т не очень большое. Давайте теперь представим себе, как фактически работает комиссия. Каждый человек берет в руки список нуждающихся и смотрит, кто из них нуждается больше всех, кто следующий и т. д., т. е. каждый составляет некоторую очередь из нуждающихся. Вот, например, первый из них пишет так (я буду людей обозначать буквами, если можно):

a₁,a₂,a₃,a₄, ... , a_n

а где-то он еще проведет черту, скажем, после a₃(квартиры кончились). Заметьте, что, составляя список, он будет очень тщательно выбирать тех, кто попадет левее черты. Так же поступит второй член комиссии, третий и т. д. Эти свои мнения они друг другу сообщат. Например, можно считать, что они выпишут их на доске. Ну и дальше, говоря формально, останется только разводить руками. Ничего здесь решить голосованием нельзя и вот почему. Потому, что у нас квартир меньше, чем нуждающихся, и, как правило, эти списки не будут ни у кого совпадать. Но если я составил список и один из моих людей не попал, то я за такое решение голосовать отказываюсь. Поэтому я буду голосовать только за свой список. До тех пор, пока я не буду уверен, что мне удастся провести своих людей, я голосовать «за» не буду. А если буду, то зря меня выбирали в жилищную комиссию. Смотрите, что будет получаться. На доске написаны мнения всех членов комиссии. Если ока-жется, что у большинства эти мнения совпадают, тогда можно решить вопрос голосованием. Давайте разберемся, вероятно ли это? Нет, совершенно невероятно потому, что на самом деле имеется N! разных мнений, где N — число нуждающихся, и вероятность того, что мнения совпадут очень невелика. Поэтому первое, что увидят члены жилищной комиссии: прийти к общему мнению невозможно. Кстати,

140

во всякой разумно устроенной жилищной комиссии решение не принимается голосованием: начинают голосовать лишь тогда, когда есть уверенность, что это решение единогласно. Ясно, почему это делается. Если я остаюсь при своем особом мнении и меня не сумели бы убедить, что решение правильно, то жилищная комиссия заседала бы все это время напрасно. Я пойду в местком, и разбирательство начнется сначала. Как правило, решение жилищной комиссии должен утверждать местком, и если кто-нибудь из членов комиссии обоснованно возражает, то местком ничего не утвердит, а пошлет жилищную комиссию утрясать между собой мнения. Значит, решать при помощи голосования все-таки нельзя. Может быть, здесь стоит сказать, когда можно решать голосованием. Если мы, здесь собравшиеся, будем выбирать председателя из трех возможных кандидатов, то мы вполне можем решить такую задачу голосованием, потому что возможных мнений здесь гораздо меньше, чем число собравшихся, и только в таких случаях и можно решать голосованием. В нашем случае решать голосованием нельзя. Значит, члены комиссии должны прийти к какому-то разумному компромиссу, договариваясь между собой без голосования. Как они могут между собой договариваться? Прежде всего, никому не возбраняется изменять свои мнения. Во-вторых, и мы всегда об этом всерьез думаем (хотя, я думаю, это не очень верно), мы можем пытаться друг друга уговаривать. На самом деле, по любому вопросу, вероятно, здравого человека можно в чем-то как-то убедить... Оказывается, что эта задача может быть сформулирована в терминах игр автоматов...»

М. Л. Цейтлин хорошо представлял себе описанную ситуацию, так как, кроме того, что он был замечательным ученым, в течение многих лет он был членом жилищной комиссии Института прикладной математики АН СССР.

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

141

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

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

В результате обсуждения члены комиссии следующим образом упорядочили кандидатов на три объявленные премии:

1. Иванов	1.	Собакин	1.	Иванов	,	Собакнн	I.	Иванов
2. Петров	2.	Иванов	2.	Мышкин	2.	Сидоров	2.	Кошкин
3. Сидоров	3.	Мышкин	3.	Кошкин	3.	Иванов	3.	Петров
4. Лошадкин	4.	Лошадкин	4.	Лошадкин	4.	Лошадкин	4.	Лошадкин
5. Кошкин 6. Мышкин	5. 6.	Кошкин Сидоров	5. 6.	Сидоров Петров	5. 6.	Петров Мышкин	5. 6.	Сидоров Собакин
7. Собакин	7.	Петров	7.	Собакин	7.	Кошкин	7.	Мышкин

На доске были выписаны следующие голосования:

Фамилия	Сумма мест	Результат	Число голосов за призовое место
Иванов	8	1-я премия	5
Петров	23	6-е место	2
Сидоров Кошкин	21 22	3-я премия 4—5-е место	2 2
Мышкин	24	7-е место	2
Собакин	22	4—5-е место	2
Лошадкин	20	2-я премия	0

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

142

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

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

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

1. Петров	1.	Собакин	I	мышкин	1.	Собакнн	1.	Кошкин
2. Сидоров	2.	Мышкин	2.	Иванов	2.	Сидоров	2.	Петров
3. Иванов	3.	Иванов	3.	Кошкин	3.	Иванов	3.	Иванов
4. Мышкин	4.	Петров	4.	Петров	4.	Мышкин	4.	Мышкин
5. Кошкин	5.	Кошкин	5.	Лошадкин	5.	Петров	5.	Лошадкин
6. Лошадкин	6.	Лошадкин	6.	Сидоров	6.	Лошадкин	6.	Собакин
7. Собакин	7.	Сидоров	7.	Собакнн	7.	Кошкин	7.	Сидоров

Результаты снова были выписаны на доске:

Фамилия	Сумма мест	Результат	Число голосов за призовое место
Иванов	14	1-я премия	5
Петров	16	3-я премия	2
Сидоров	24	6-е место	2
Кошкин	21	4-е место	2
Мышкин	15	2-я премия	2
Собакин	22	5-е место	2
Лошадкин	28	7-е место	0

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

143

того, «темная лошадка» Лошадкин лишился своего случайного преимущества.

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

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

Лет 10 тому назад, на ученом совете Ленинградского Отделения Центрального Экономико-Математического института АН СССР, при подведении итогов конкурса научных работ молодых ученых нами была испробована такая многошаговая процедура оценки. Уже третий тур привел к перемене только восьмого и девятого места, и по общему мнению членов совета оценка результатов конкурса была справедливой.

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

Что такое синхронизация?

Уже довольно давно биологи, которые занимались культурами тканей, т. е. выращиванием живых клеток вне организма, обратили внимание на синхронизацию моментов деления клеток. Явление заключалось в следующем. Клетка делится. Две вновь образовавшиеся клетки некоторое время находятся в состоянии покоя, а затем одновременно делятся. Тот же эффект повторяется для четырех вновь образовавшихся клеток и т. д. Возможны следующие механизмы, обеспечивающие синхронизацию делений. Во-первых, в каждой клетке могут существовать достаточно точные внутренние часы, которые определяют интервалы между делениями клетки. Во-вторых, клетки могут согласовывать друг с другом моменты своих делений. До сих пор ни одна из этих гипотез не нашла точного экспериментального подтверждения. Первая гипотеза достаточно правдоподобна; если такие часы действительно существуют, то механизм синхронизации очевиден. Для обеспечения механизма согласования необходим обмен информацией между клетками. Существует возможность достаточно быстрого обмена сигналами, например при помощи биополя, но наличие такого биополя до сих пор нельзя считать экспериментально доказанным. Скорости же распространения электрохимических процессов, по-видимому, не могут обеспечить наблюдаемой точности синхронизации достаточно больших популяций клеток. Последнее определило интерес биологов только к двум гипотезам, объясняющим механизм синхронизации — наличие биополя и внутренних часов. Существование биополя оставалось под большим сомнением, а внутренние часы могли объяснить только процесс синхронного независимого деления и также требовали рассмотрения механизмов взаимодействия, если включение процесса деления

152

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

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

Имеется цепь стрелков (рис. 5.1), каждый из которых может общаться только с двумя своими не

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

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

153

Существование решения задачи Майхилла было доказано Дж. Мак-Карти и М. Минским, а в 1962 г. Э. Гото опубликовал решение задачи с минимально возможным временем решения, равным 2N —2, где N — число стрелков. При этом алгоритм поведения каждого стрелка представлялся конечным автоматом с несколькими тысячами внутренних состояний. Следующий принципиальный шаг был сделан советским ученым В. И. Левенштейном, опубликовавшим в 1965 г. блестящее решение задачи, в которой используется автомат, имеющий всего девять внутренних состояний. Усилиями последующих исследователей число состояний удалось уменьшить до восьми.

Хотя решение задачи Майхилла давало ответ па принципиальный методологический вопрос и демонстрировало ряд эффектов, которых мы коснемся в следующем параграфе, многие относились к полученным конструкциям скептически: «Зачем городить все эти сложности, если можно протянуть провод между всеми стрелками и одновременно для всех включить лампочку, являющуюся командой стрелять?»

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

Существуют разные подходы к решению этой задачи. Здесь мы остановимся на решении, связанном с задачей Майхилла.

154

Управление стрелками

Сформулируем задачу Майхилла в терминах автоматов, моделирующих поведение стрелков.

Имеется цепь из N автоматов. Каждый автомат имеет п внутренних состояний. Состояние каждого автомата в следующий момент времени зависит от его состояния в текущий момент времени и состояний двух его соседей, правого и левого. В начальный момент все автоматы находятся в некотором начальном состоянии S_о. В начальный момент па один из край-них автоматов цепи подается внешний сигнал, выводящий его из начального состояния. Существует ли такая конструкция автомата (правила смены его состоянии), что после инициации крайнего автомата цепи через некоторое время все автоматы одновременно перейдут в одно и то же состояние S и ни один из них не перейдет в это состояние ни в один из предыдущих моментов, причем сложность каждого автомата п не зависит от длины цепи.

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

линия. Тонкая линия обозначает начальное состояние So автомата. Инициирующий сигнал поступает на крайний автомат цепи А₉ и переводит его в состояние, которое мы будем называть состоянием готовности S₁. Перейдя в это состояние, автомат посылает в цепь два сигнала а₁ и a₃, распространяющиеся по цепи со скоростями 1 и Уз соответственно. Распространение сигнала по цепи со скоростью 1 означает, что автомат, получивший справа сигнал а₁, передает его в том же направлении в следующем такте работы, а при скорости распространения 1/3 задерживает сигнал а₃ на три такта.

155

Сигнал a₁, дойдя до противоположного края цепи, переводит крайний автомат в состояние готовности Si и отражается от края цепи, начиная распространение в обратном направлении (слева направо). Нетрудно понять, что отраженный сигнал а₁ и сигнал а₃ встретятся точно в середине цепи. Находящийся в точке встречи автомат A₅ (или два автомата в случае их четного числа) переходит в состояние готовности Si, которому на рис. 5.2 соответствует жирная черта.

Автомат A₅, перешедший теперь в состояние S₁, посылает в обе стороны по паре сигналов a1 и a3, причем сигнал a1 отражается от первого встреченного им автомата в состоянии S₁. В результате в точках встречи отраженных сигналов с сигналом из (А3 и A7) происходит переход автомата в состояние S₁ и наступает новая генерация сигналов a1 и a3 в обе стороны.

Таким образом, в каждом цикле происходит деление интервала между двумя автоматами, находящимися в состоянии S₁ пополам, и в центре этого интервала автомат тоже переходит в состояние S₁. Такой процесс продолжается до тех пор, пока все автоматы цепи не перейдут в состояние S₁. Обратим внимание на то, что до последнего деления у каждого автомата будет по крайней мере один сосед, который не готов к синхронизации, т. е. находится в состоянии, отличном от S₁. Автомат переходит в состояние синхронизации S, если он сам и оба его соседа находятся в состоянии S₁. Таким образом, задача синхронизации решается и правила поведения каждого автомата не зависят от длины цепи. Время, необходимое для решения задачи деления интервала пополам, равно 3/2 его длины, и, следовательно, общее время синхронизации с точностью до постоянных, зависящих от четности и нечетности интервалов, равно утроенной длине цепи.

Процесс синхронизации можно ускорить, если автомат, перешедший в состояние готовности, посылает еще сигнал а7, распространяющийся со скоростью 1/7, и сигнал а15, распространяющийся со скоростью 1/15 (рис. 5.3). Причины, приводящие к ускорению процесса синхронизации в такой ситуации, очевидны из сравнения рис. 5.2 и 5.3. Хотя и в этом случае правила локального поведения не

156

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

Для того чтобы отдельно взятый автомат мог осуществить задержку сигнала на Т тактов, необходимо, чтобы он имел не менее Т внутренних состояний. Если он одновременно должен задерживать один сигнал на Т1 тактов, а другой сигнал на Т₂тактов, то число его состояний должно быть не меньше, чем T₁T₂. Таким образом, введение дополнительных сигналов, ускоряющих синхронизацию, ведет к существенному росту сложности автоматов. Кроме того, теперь необходимое число сигналов, а следовательно, и сложность автоматов начинает зависеть от длины цепи.

В предыдущем параграфе мы уже упоминали о блестящем решении задачи синхронизации В. И. Левенштейном. Необычайное изящество этого решения состоит в том, что он нашел способ организовать взаимодействие между автоматами так, что в процессе взаимодействия между соседними автоматами осуществляется задержка распространения сигналов на число тактов, равное 1, 3, 7, 15, ..., (2^k—1), причем k зависит не от числа состояний автомата, а от длины цепи. Решающие эту задачу автоматы имели всего девять внутренних состояний. Сейчас известно решение для восьми внутренних состоянии. В этом случае время синхронизации достигает своего минимального значения, равного удвоенной длине цепи, т. е. времени, необходимого для того, чтобы сигнал, распространяющийся со скоростью 1, прошел всю цепь туда и обратно.

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

157

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

Появление решения задачи Майхилла породило несколько дополнительных интересных проблем. Прежде всего была решена задача синхронизации цепи автоматов для случая инициации произвольного автомата цепи. Сложность локального автомата при этом возросла до 10 состояний.

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

Идея алгоритма, осуществляющего синхронизацию с точностью до такта автомата, достаточно проста и состоит в следующем. Инициирующей синхронизацию автомат посылает в канал связи в три последовательных момента времени три сигнала a1, a2 и a3. Приемник отправляет эти сигналы обратно, задержав сигнал а1, на один такт, сигнал a2 на два такта и сигнал a3, на три такта. Одновременный прием одним из участников обмена сигналов a1 и a3 означает выход на синхронный режим, и с этого момента он начинает посылать в канал синхросигнал s. В момент совпадения у одного из участников сигналов a1 и a3 другой участник получает сигнал a2, который отправляет обратно с за-

158

держкой в два такта. После выхода на синхронный режим сигнал a2 не отличим от сигнала s, и если последний возвращается участником с задержкой в два такта, то обмен сигналами s начинает поддерживать взаимную синхронизацию. Для исключения влияния неточности локальных часов, определяющих локальное время на Земле и космическом корабле, обмен сигналами a1 и a2 должен продолжаться и после выхода на синхронный режим.

Теперь рассмотрим ситуацию, в которой майхилловские стрелки не стреляют из ружей, а включают какие-то устройства (рис. 5.4), каждое из которых обладает своим латентным временем, т. е. временем между нажатием пусковой кнопки и началом работы устройства. Например, от момента включения питания радиолокационной станции до момента разогрева радиоламп проходит 1 мин, а от момента запуска двигателя до его прогрева — 5 мин. Каждому «стрелку» известно только латентное время своего собственного устройства. Возникает вопрос о существовании локальных правил поведения автоматов, сложность которых (число состояний) не зависит ни от длины цепи, ни от латентных времен других «стрелков», иными словами, после подачи команды одному из «стрелков» цепи они должны нажать пусковые кнопки так, чтобы все управляемые ими устройства начали работать одновременно.

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

159

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

Гимн однородным структурам

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

Мы думаем, что картина, описанная ниже, знакома всем читателям. В зале заседаний идет собрание. Председательствующий ставит на голосование какой-то проект или решение. «Прошу поднять руку тех, кто «за»,— говорит он. Поднимается лес рук. Подсчет числа голосов весьма трудоемок. Иногда председатель не справляется с ним и требуются специальные помощники — счетчики. «Кто «против»? — снова спрашивает председатель. И опять лес рук. И снова надо считать. Хорошо, когда одно из мнений собирает мизерное число сторонников. Тогда и считать не требуется. Общая картина достаточно красноречива. («Считать не будем? Я думаю, и так все ясно»,— говорит в этих случаях обычно председатель.) Но если «за» и «против» собрали примерно одинаковое число голосов, то публика начинает волноваться и требует перёголосования. Всегда возникает мнение, что счетчики ошиблись. Как избежать этой щекотливой ситуации? Можно ли

164

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

Рассмотрим сначала простейшее голосование, при котором каждый его участник голосует «за» или «против», а окончательное решение принимается по простому большинству голосов. Тогда, очевидно, каждую пару «за—против» можно вычеркнуть из дальнейшего сравнения. Если вычеркнуть все такие пары, то останутся только те, кто проголосовал «за» (если их большинство), или те, кто проголосовал «против». Считать их число не надо. Для простого большинства хватает и одного лишнего голоса. Эту процедуру вычеркивания конкурентных пар легко реализовать на одномерной однородной структуре. Рассмотрим схему, показанную на рис. 5.5. Каждый автомат имеет два состояния, которые мы обозначим через а, b. Состояние а соответствует тому, что данный результат голосования еще не вычеркнут, состояние b — что он вычеркнут. На внешние входы автоматов поступают сигналы х_i от участников голосования. При этом х_i=1 означает, что i-й участник голосования проголосовал «против», a х_i=0 — что он проголосовал «за». Если голосование происходит в специально для этого оборудованном месте, то сигнал от каждого голосующего поступает в наше устройство в результате нажатия им соответствующей кнопки на индивидуальном пульте.

165

Сигналы, передаваемые по горизонтальной шине между автоматами, являются для системы внутренними (рабочими). Работа автоматов в цепи задается табл. 5.1.

Таблица 5.1

	Входной с	игнал, поступив	вший от i-го гол	осующего
Рабочий сигнал	Х_i Состояние	=0 aвтомата Ai	Х_i состояние	=--1 aвтомата Ai
	A	b	А	b
So	S1, b	So, b	S2, b	So, b
S1	S1, а	S1, b	S3,b	S1, b
S2	S3, b	S2, b	S3, a	S2, b
S3	S3, a	S3,b	S3, a	S3, b

Поясним, как устроена эта таблица. В некотором такте работы на автомат Ai поступает входной сигнал Xi , равный 0 или 1, и один из четырех возможных рабочих сигналов. Сам Аi при этом находится в одном из двух возможных состояний (а или b). Значения входного и рабочего сигналов и состояние автомата определяют текущую ситуацию, которая записывается парой символов: значением рабочего сигнала, выдаваемого автоматом Ai в этой текущей ситуации, и новое состоянием, в которое он переходит.

В начале работы системное устройство СУ, показанное на рис. 5.5 в виде кружка, выдает на боковой вход самого левого автомата цепи сигнал So. Все автоматы в начальном такте работы находятся в невычеркнутых состояниях а. Встретив первый автомат в состоянии а (в начальный такт работы это всегда будет крайний левый автомат в цепи), сигнал So переводит его в вычеркнутое состояние b. Если при этом на внешний вход автомата подавался сигнал «за», то далее по цепи будет вправо распространяться сигнал S1. Если же данный автомат имел на входе Xi=1 (т. е. сигнал «против»), то вправо будет распространяться сигнал S2.

Сигналы S1 и S2 осуществляют поиск первого автомата, который мог бы составить вычеркиваемую

166

пару с отмеченным ими автоматом. Если при своем движении вправо сигналы S1 или S2 находят соответствующий автомат, то он переводится в вычеркнутое состояние, а рабочий сигнал становится равным S3. Этот сигнал есть свидетельство вычеркивания одной пары из множества голосующих. Сигнал S3 «проскакивает» через все оставшиеся автоматы цепи, ничего не меняя на своем пути. Его приход в СУ свидетельствует об окончании одного акта вычеркивания. Приход его в СУ заставляет системное устройство выдать на цепочку автоматов новый сигнал So. Окончание процесса вычеркивания произойдет тогда, когда сигнал S1 или сигнал S2 не найдут себе подходящей пары для вычеркивания. В этом случае на вход СУ поступит не сигнал S3, a S1 или S2. Появление сигнала S1 говорит о том, что большинство проголосовало «за», появление S2 — о противоположном результате голосования. Особым случаем является равенство голосов «за» и «против». В этой ситуации наше устройство посылает на боковой вход левого автомата цепи сигнал So, который «проскакивает» неизменным через все вычеркнутые автоматы и приходит на вход СУ. Это и есть сигнал

о равенстве голосов.

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

Мы рассмотрели простейший случай голосования. Но и для более сложных случаев задача об определении результатов голосования оказывается разрешимой с помощью одномерной цепи автоматов, в которой сложность каждого автомата не зависит от того, сколько лиц приняло участие в процедуре голосования, а зависит лишь от вида голосования. Так, например, при голосовании по принципу 2/3 (решение принимается, если за него проголосовало не менее 2/3 голосующих) сложность автоматов не меняется, а лишь увеличивается до шести число различных рабочих сигналов. При одном «сканировании» с помощью сигнала So происходит вычеркивание тройки автоматов, на два из которых поступил сигнал «за», а на один — сигнал «против». Можно рассматривать задачу не с простым голосованием «за» и «против», а с выбором одного из К претендентов

167

по принципу большинства голосов. Это требует уже автоматов с четырьмя состояниями и восьми различных рабочих сигналов. При последовательном голосовании (например, сначала предлагается из трех претендентов B1, В2 и В3 выбрать либо B1, либо группу (В2, В3), и если выбран B1, то голосование заканчивается, а если группа, то на втором туре идет борьба между В2 и В3) требуется уже двумерная однородная структура. Такой же структуры требует и голосование, в котором каждый претендент на «призовое» место оценивается определенным коли-чеством очков.

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

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

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

168

был бы одинаков. Как и при десятичном умножении, он равен 168.

На рис. 5.6 показана однородная матрица, состоящая из трех столбцов, каждая клетка которых представляет собой однотипный автомат, имеющий три состояния D₀, D₁, D. Состояния D₀ и D₁ называются рабочими. Если автомат находится в них, то это означает, что он хранит в данной клетке значение двоичной цифры 0 и 1 соответственно. Состояние D является безразличным (нерабочим). Каждый

автомат имеет связи со всеми своими соседями. Эти входы и выходы мы будем обозначать буквами н, в, л, п (низ, верх, левый, правый). По ним могут передаваться сигналы пяти типов: безразличный (пустой) и B0, B1, Co, C1. Безразличный сигнал мы специально обозначать никак не будем. Сигналы Во и B1 несут информацию о значении цифр в соответствующем разряде множителя. Сигналы Со и С1, выдаваемые автоматами, соответствуют передаче соседу сигналов 0 и 1.

Число строк в матрице зависит от разрядности перемножаемых чисел. При n разрядах число строк в первом столбце равно 2n + 1, во втором и третьем столбцах —2n. Матрица, показанная на нашем рисунке, предназначена для перемножения четырехразрядных двоичных чисел.

Все автоматы, образующие матрицу, функционируют одинаково. Этот принцип проистекает из одно-

169

родности среды. Работа автоматов иллюстрируется табл. 5.2.

Здесь индексы k, p, i могут принимать значения О или 1.

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

Как же происходит умножение? На рис. 5.6, а показано начальное заполнение матрицы. Множитель

Таблица 5.2

		Текущ	ий такт		По	следую	щий	такт
нет команды		вход		состояние		вход		состо	Условие перехода
номер команды	п	л	н	автомата	п	в	л	яние
1			Ck	D				Dk
2			Ck	Dp		Ck		Dp
3	bo			Dp		Bp		D
4			Bk	Dp	Bk	Bk		Dp
5			Bk	D	Bk	Bk		D
6		B1		Dp	Cp	Cp	в»	D
7		Bо		Dp	Co	Cp	Во	D
8		Bl	Ck	Dp	Cp	Cp		Dk
9		Во	Ck	Dp	Co	Cp		Dk
10	Во			D				D
11		Ck	*Cp	Di		C1		D1	k + p + i = 3
		Ck	*Cp	Di		C1		D0	k + p + i = 2
		Ck	*Cp	Di		Co		D1	k + p + i = 1
		Ck	*Cp	Di		Co		Do	k + p + i = 0

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

Процесс начинается с подачи сигнала Во справа на младший разряд множителя. Этот сигнал как бы

170

считывает значение разряда. Появление после этого состояния D означает, что разряд считан (рис. 5.6, б). Далее сигнал Во распространяется вверх по левой колонке и на каждом уровне порождает сигнал Во направо. Эти сигналы сдвигают множимое без прибавления в накопленную сумму правой колонки матрицы. В нашем примере это происходит потому, что на начальном цикле разряд множителя был равен 0. На рис. 5.6, в, г показаны еще два такта работы однородной среды. Появление на рис. 5.6 г сигнала Во, приходящего в левую колонку, соответствует началу работы с очередным разрядом множителя. Таким образом, на четвертом такте завершается микроцикл умножения.

Общая картина распространения сигналов по однородной матрице при умножении двоичных чисел в столбик показана на рис. 5.7. На нем двойная стрелка изображает сигналы Bk, обычная стрелка — сигналы Ck. Светлый кружок означает переход автомата в данном такте в состояние D и выдачу вверх значения, соответствующего его состоянию, темный кружок — переход автомата в состояние Dp, соответствующего значению сигнала, поступившего на данный автомат снизу. Перечеркнутая стрелка означает, что передается либо сигнал Во, либо Со. За 18 тактов, как следует из рис. 5.7, цикл умножения двух четырехразрядных двоичных чисел завершается. Состояния автоматов правой колонки хранят результат умножения. Сигналы, которые на рис. 5.7 как бы выходят за пределы матрицы, пропадают и не оказывают влияния на дальнейшее функционирование матрицы. Читатель, пользуясь табл. 5.2 и рис. 5.7, может самостоятельно завершить умножение 12 на 14 с помощью однородной матрицы.

Общее число тактов, которое нужно затратить на умножение двух n-разрядных двоичных чисел по предложенному методу, равно 8п+2. Если же отказаться от привычной нам логики умножения и перейти на более «изысканные» методы умножения, то однородная матрица позволяет найти произведение всего за 4n—1 такт работы. При этом сложность автоматов, образующих матрицу, даже меньше, чем при умножении в столбик. Правда, при умножении двух n-разрядных чисел потребуется в этом случае

171

n² + 1 автомат, а для рассмотренного нами случая — 6n + 1 автомат.

Кроме умножения, с помощью однородных матриц можно производить и деление. Один из способов

деления на однородной матрице с двумя столбцами требует автоматов той же сложности, что и для умножения в столбик. Число необходимых автоматов равно 2п+3. Однородные среды открывают большие возможности в самых различных областях применения. Например, они оказываются незаменимыми при обработке зрительной информации, отображаемой на

172

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

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

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

Почему йога —не наш путь?»

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

173

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

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

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

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

174

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

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

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

175

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

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

Для того чтобы еще раз подчеркнуть весьма важную для нас мысль о вреде «вытаскивания» специфических функций в централизованную часть системы управления, мы закончим этот параграф одной сценкой, которую можно было наблюдать на международной конференции по проблемам искусственного интеллекта и робототехники. Один из высокопоставленных представителей военно-морского флота США в ответ на жалобы докладчика о том, что весьма

176

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

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

173

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

Эта длинная цитата из повести Станислава Лема «Непобедимый» приведена нами не случайно. На планете «Регис-III» люди столкнулись с необычным явлением. Из примитивных кристалликов, обладающих примитивным поведением, при определенных условиях возникал сверхорганизм— туча. И эта туча обладала почти неисчерпаемыми возможностями по адаптации своего поведения, ибо хранила в огромной памяти, складывающейся из памятей-песчинок отдельных кристаллов, необъятный запас знаний.

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

сообщество рабочих пчел в улье или рабочих муравьев в муравейнике—примеры того же типа.

Но простое скопление однородных подсистем или организмов—это еще не новая система или организм. Множество рабочих пчел, встретившихся на цветущем лугу и относящихся к разным пчелиным

179

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

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

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

Рассмотрим простую модель, иллюстрирующую возможности синтезогенеза. На рис. 6.1 показан тороидальный мир — совокупность клеток, размещенных на внешней поверхности тора (обычная сушка

180

или баранка дают превосходное представление о тороидальной форме). Предположим, что в клетках этого мира может находиться пища, которой могут питаться «организмы», обитающие в них. В качестве таких «организмов» будем рассматривать автоматы с линейной тактикой. Простейшая форма подобного автомата — автомат с одним действием, показанный на рис. 6.2, а. В состоянии 1 при получении сигнала штраф автомат «умирает» (на рисунке это отмечено крестиком). Действие, которое может совершать автомат,— перемещение в некотором фиксированном направлении на одну клетку тора. Обозначим четыре возможных направления перемещения, показанные на рис. 6.1, через А, Б, В, Г. Тогда простейшие автоматы будут делиться на четыре типа — будем обозначать их теми же буквами. Допустим, что автоматы, находящиеся в одной клетке, могут объединяться. Если объединяются два автомата одного типа, то это приводит к увеличению длины лепестка (т. е. глубины памяти для этого действия). При объединении же автоматов различного типа новый автомат имеет уже не один лепесток, а два. На рис. 6.2,6 показан автомат, который возник в результате объединения четырех автоматов, два из которых относятся к

181

типу А, а оставшиеся два — к типу В и Г. Для удобства будем обозначать такой автомат как А²ГВ.

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

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

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

Рассмотрим несколько ситуаций в эволюционном процессе на торе.

На рис. 6.3 показано несколько простейших ситуация на некотором участке тороидальной поверхности. Клетки, в которых имеется пища, отмечены точками. Предполагается, что пища, съеденная в клетках, полностью восстанавливается, как только автомат уйдет из нее. На рис. 6.3, а показаны два простейших автомата. Автомат Л съедает пищу в клетке, где он находится, и идет наверх. Но на этом кольце пищи нигде больше нет. В результате он погибает в клетке, помеченной крестиком. Иная судьба у автомата Г. Если пища имеется на всем кольце,

182

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

На рис. 6.2, б показана еще одна очень простая ситуация. Автоматы А и Г встречаются в клетке с пищей, объединяются и начинают движение. Каким оно будет? Это зависит от того, какое именно состояние окажется начальным. Ели это состояние, соответствующее состоянию 1 автомата А, то объединенный автомат сначала сделает шаг наверх. В этой клетке пищи нет и автомат получит наказание. Это заставит перейти его в состояние 1 бывшего автомата Г и сделать шаг на одну клетку вправо. Там пища есть. Съев ее, автомат сделает еще один шаг вправо. Получив наказание, он, как автомат А, сделает шаг вверх и получит пищу. Далее процесс будет повторяться циклически, если пища размещается на поверхности тора регулярным образом. Автомат будет двигаться по «диагональной линии» и жить вечное Если бы начальным состоянием объединенного автомата было состояние 1 автомата Г, то движение было бы аналогичным. Пунктирные стрелки показывают оба возможных пути автомата АГ.

Усложнение структуры далеко не всегда приводит к улучшению функционирования. Это положение иллюстрируется рис. 6.3, в. В клетке с пищей образуется автомат АБГ. Пусть начальным его состоянием является состояние 1 автомата Г. Сдвинувшись на одну клетку вправо и получив сигнал штраф, автомат переходит (путем равновероятного выбора) в состояние автомата Б. Он сдвигается вниз, но пищи там нет. Опять следует равновероятный переход, и автомат снова попадает в состояние автомата Г. Происходит сдвиг вправо. Но так как пищи в этой клетке нет, объединенный автомат погибает, исчерпав все свои ресурсы. Если бы объединения не произошло, то при том распределении пищи, которое показано на рис. 6.3, в, все три простейших автомата могли бы жить вечно.

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

ных метаморфоз, которые могут развернуться на поверхности тора.

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

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

Выскажем еще раз одну весьма важную мысль, связанную с синтезогенезом. В процессе такого объединения возникает особое явление, сходное (чисто внешне) с полимеризацией в химии. Элементы, вступая в объединение и не меняясь по своей структуре, как бы приобретают новые качественные возможности. И эти новые возможности зависят от механизма объединения. В гл. 4 мы уже столкнулись с этим явлением. Когда два автомата объединялись чисто механически (так, как объединяются автоматы в нашей модели эволюции на горе), число их состояний растет, как п², если каждый из автоматов имел п состояний. Когда же они объединяются за счет случайного парного взаимодействия, то это дает им возможность функционировать как автоматам, обладающим памятью глубины 2ⁿ. В гл. 5 мы также столкнулись с явлением «полимеризации». Автомат всего с восемью состояниями, объединившись в шеренгу стрелков, как бы приобретал возможность работы с памятью всей совокупности автоматов, становился богаче по своим возможностям, не меняя своей структуры. Это явление кажется нам весьма любопытным.

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

Эволюция в городе Едгин

Странное название города есть обратное прочтение слова «нигде». Город этот придумал английский писатель С. Батлер во второй половине XIX века. В английском написании название этого города, совпадающее с названием романа, выглядит как «Erehwon».

Роман С. Батлера утопический. Герой романа, молодой человек по имени Хиггс, путешествуя в горах, попадает в необычный город. Его жители живут по законам, противоречащим нормам морали

191

и юриспруденции, которые господствовали в Европе того времени. Например, болезни и несчастья, которые случаются с жителями Едгина, приравниваются к преступлениям. И за это судят и наказывают. Рождение ребенка также не является радостным событием, и дети, когда они вырастают, вовсе не благодарны своим родителям за то, что те даровали им жизнь. Но зато все жители города Едгин красивы, веселы и жизнерадостны. Хиггса они принимают с распростертыми объятиями, но вскоре сажают в тюрьму,

Причина столь странного поступка — наличие у Хиггса часов. Почему часы испугали местных жителей, Хиггс узнает существенно позже, из рассказа дочери начальника тюрьмы Ирем. И эта причина имеет непосредственное отношение к теме нашей книги.

Но прежде чем говорить об этом, необходимо несколько слов сказать о самом Самуэле Батлере. В его богатой событиями жизни, наполненной разнообразными интересами и пристрастиями, было одно многолетнее увлечение. И это увлечение — попытка понять суть эволюционного процесса. Чарльз Дарвин и его фундаментальная теория происхождения видов сыграли в этом огромную роль. Сначала С. Батлер принял его теорию целиком, но позже наступил период, когда его стали одолевать сомнения. Наиболее сомнительным положением дарвиновской теории для Батлера было то, что течение такого процесса, как биологическая эволюция, возможно только за счет случайного взаимодействия и случайных мутаций. Он был глубоко убежден, что процесс этот должен быть целенаправленным*). Но кем он направляется? С. Батлер был рационалистом, он критически относился к религии, неоднократно высмеивал в своих произведениях церковные порядки и религиозные догмы. Но в своих книгах, посвященных модели эволюции («Жизнь и привычка», 1877, «Старая и новая эволюция», 1879, «Бессознательная память», 1880 и «Случайность или хитрость как главный источник органических изменений», 1886), С. Батлер

*) Идею о направленности эволюции, ее рациональности рбосновывал и академик Л. С, Берг, создавший теорию номогенеза.

выступал против идеи Дарвина о вероятностном характере эволюции. И одним из его аргументов была принятая им концепция технической эволюции. Пожалуй, впервые эта концепция появилась в статье С. Батлера «Дарвин среди машин», опубликованной в 1863 г. Уже в ней он указывает на то, что человек выступает в технической эволюции как звено, привносящее в эволюционный процесс цель и рациональность. В романе «Едгин» эта идея раскрывается во всей своей глубине.

Герой романа постепенно узнает, что раньше в Едгине существовал богатейший техноценоз, созданный учеными и техниками для обслуживания жителей города, облегчения их труда и дальнейшего развития науки и техники. Но, возникнув, техноценоз стал подобен раковой опухоли. Из «Трактата машин», попавшего к нему в руки, Хиггс узнает, что развитие техноценоза шло так быстро, что люди постепенно из хозяев положения стали превращаться в рабов созданной ими машинной цивилизации. С точки зрения машин люди превращаются в насекомых, опыляющих и оплодотворяющих технические устройства, живущие своей независимой жизнью. И, верный своей задаче критики современного ему общества, С. Батлер восклицает: «Сколько людей и теперь живут, как рабы у машин? Сколько людей проводят всю жизнь от колыбели до могилы, служа машинам и днем и ночью?»

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

193

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

Для нас интересно отметить те особенности технических систем, возникших в процессе эволюции по воле человека, которые отмечает С. Батлер. Во-первых, это достижение цели любыми средствами. Логика действий технического устройства отлична от логики действия человека. Во-вторых, развитые технические системы требуют от человека, участвующего в управлении ими, узкой специализации, при которой коллектив управленцев связан между собой только информацией, выдаваемой ему технической системой. Первое положение мы уже обсуждали в гл. 5, когда говорили о трудностях, связанных с созданием общих законов управления, которые могли бы компенсировать логику «машинных рассуждении». Что же касается второго положения, то тут писатель был бы совершенно прав, если бы не возникала возможность заменить человека-управленца соответствующим техническим устройством. А именно эта идея и была обсуждена в гл. 3 и 4 (а отчасти и в гл. 5) книги. Образ рабочего на конвейере, столь ярко сыгранный в бессмертном фильме Чарли Чаплина, показывает, что опасения С. Батлера были небезосновательны.

В чем-то писатель оказался прав. И когда в книге Р. К. Баландина, изданной в 1978 г., мы читаем: «Но даже техника — наше создание, над которым мы безраздельно господствуем,— одновременно имеет над нами значительную власть. Мы сейчас столько же зависим от нее, сколько от остальной природы. Мы употребляем в пищу техногенные (искусственно выведенные и взращенные) виды животных и сорта растений, причем после обязательной кулинарной, техногенной обработки. Мы существуем среди техники и за счет техники. Мы, безусловно, вынуждены обслуживать технику, заботиться о ней, в какой-то степени к ней приспосабливаться, вынуждены учитывать ее возможности и запросы (нередко в ущерб собственным, личным интересам), максимально со-

194

действовать ее прогрессу и постоянной работе в оптимальном режиме...»*, и тень города Едгин витает перед нами.

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

195

Сначала ЭВМ объединялись друг с другом непосредственно, кабелем. Но потом возникла идея вое-пользоваться для этого каналами связи, которые существуют во всемирной сети связи. Такое решение дало качественный скачок. Если раньше человек, который собирался использовать вычислительную машину для решения интересующей его задачи, знал, какая именно ЭВМ ее решает, непосредственно взаимодействовал с ней, то теперь он потерял эту информацию. Задача, введенная в сеть, может решаться на любой ЭВМ, входящей в нее. И зачастую эта ЭВМ находится территориально весьма далеко от пользователя. Пользователь становится как бы обладателем всего ресурса сети, что делает его возможности почти безграничными. Его задача может решаться одной машиной в сети или одновременно несколькими машинами. Возможен и такой режим, при котором задача пользователя решается последовательно по частям на различных ЭВМ сети. А учитывая неоднородность ЭВМ, входящих в сеть, и неоднородность отдельных частей решаемых задач, такая организация решения может привести к существенному повышению эффективности решения.

Первая территориальная сеть обработки данных стала функционировать в 1969 г. в США. Это сеть ARPA, ставшая прообразом многих последующих сетей. В ней имеется подсеть, состоящая из коммутационных процессоров, которая обеспечивает обмен между всеми ЭВМ, входящими в сеть. В отличие от телефонной сети, в которой два абонента связываются друг с другом через коммутацию каналов, в сети обработки данных заявки на связь поступают от ЭВМ в коммутационные процессоры. В заявках указан адресат и абонент. Иногда адресат не указывается, а указываются лишь требования к нему (макисимально допустимое время решения и необходимый объем оперативной памяти для решения задачи). Коммутационный процессор при наличии адресата пересылает заявку либо непосредственно ему (если имеется прямой канал связи между этим коммутационным процессором и адресатом и последний способен принять заказ), либо в другой коммутационный процессор, чье положение на сети обеспечит передачу заявки на решение нужному адресату. Ели же адресат не указан, то коммутационный процессор сам опре-

196

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

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

Сеть ARPA развивалась очень быстро. В короткий срок она охватила всю территорию США, а вскоре через английский и норвежский узлы связи

197

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

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

Другое неожиданное применение сеть получила, когда в США происходила одна из конференций по проблемам искусственного интеллекта. В ней участвовали ученые не только США, но и ряда европейских стран. Необычным было то, что европейские участники при этом находились у себя дома и никуда не выезжали. Да и американские специалисты не покидали своего места жительства. Все доклады, присланные на конференцию, были введены в сеть, каждый участник мог ознакомиться с наиболее интересными для себя сообщениями и выступить в дискуссии или задать докладчику вопросы. Выступления и вопросы просто вводились с терминальных устройств в сеть. Докладчики получали их и вводили в сеть свои ответы на вопросы. Самое приятное заключалось в том, что любой участник конференции мог отдыхать в любое время, не рискуя что-либо упустить. Более того, из-за различий во времени между США и Европой часть участников конференции ак-

193

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

Но мы несколько отвлеклись от основной канвы. Вернемся к анализу процесса эволюции сети обработки данных. Кроме нескольких сетей в США появились общегосударственные территориальные сети в ряде европейских стран. В 1974 г. вступила в строй первая очередь сети CYCLADES во Франции. В 1971 г. был подписан протокол между восемью странами Европы о создании европейской сети обработки данных. В 1976 г. эта сеть начала функционировать в составе пяти узлов коммутации (Лондон, Цюрих, Париж, Милан, Испра). Через Лондон эта сеть соединилась с американскими сетями, возникли узлы в Вене и многих других городах. Некоторые страны Восточной Европы также установили каналы связи с европейской сетью. А сейчас имеется канал, соединивший Москву с несколькими сетями обработки данных в Европе. Ведутся активные работы по созданию территориальной сети СССР. Так происходит эволюция этой новой технической системы, которая сулит человечеству невиданные ранее возможности использования ЭВМ.

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

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

199

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

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

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

«Сильней и глубже век от века Земли и мысли торжество.

Все меньше веры в Божество.

И больше веры в Человека».

ЛИТЕРАТУРА И КОММЕНТАРИЙ

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

1. Цетлин М. Л. Исследования по теории автоматов и моделированию биологических систем.—М.: Наука, 1959, 316 с.

2. Варшавский В. И. Коллективное поведение автоматов.—М.: Наука, 1973. 407 с.

3. Срагович В. Г. Теория адаптивных систем.— M.I Наука, 1976, 319 с.

4. Цыпкин Я. 3. Адаптация и обучение в автоматических системах.—М.: Наука, 1968, 399 с.

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

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

5. Поспелов Д. А. Игры и автоматы.—М.: Л.: Энергия, 1966, 134 с.

6. Поспелов Д. А. Вероятностные автоматы. — М.: Энергия, 1970, 87 с.

7. Буш Р., Мостеллер Ф. Стохастические модели обучаемости. — М.: Физматгиз, 1962, 483 с.

8. фон Нейман Дж. Теория самовоспроизводящихся автоматов.—М.: Мир, 1971, 382 с.

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

При написании гл. 6 мы использовали ряд работ биологов, специалистов в области теории эволюции. Укажем эти источники.

9.Брайнес С. Н., Свечинский В. Б. О соотношении принципов централизации и децентрализации в биологических системах управления.— В сб.: «Бионика», Научный Совет по комплексной проблеме «Кибернетика».—М.: 1973, т. 3, с. 17—19.

10. Завадский К. М. К проблеме прогресса живых и технических систем.—В сб.: «Теоретические вопросы прогрессивного развития живой природы и техники».—Л.: Наука, 1970, с. 3—28.

11.Рашевский Н. Организмические множества: очерк общей теории биологических и социальных организмов. — В сб. «Исследования по общей теории систем».—М.: Прогресс, 1969, с. 442—461.

Трактат о машинной эволюции С. Батлера, о котором мы говорили также в гл. 6, включен в состав его утопического романа «Едгин». Этот роман на русский язык никогда не переводился. Поэтому мы приводим его оригинальные выходные данные, а также указываем современное исследование, специально посвященное сравнительному анализу концепций Батлера и Дарвина по вопросам эволюции.

12. Butler S. Erewhon. — London: Penguin Books, 1970.— 170 p.

13. Wile у В. Darwin Сh., Butler S. Two versions of evolution.—London: Chatto a. Windus, I960.—130 p.

И, наконец, укажем на ряд работ, из которых мы заимствовали те или иные модели и результаты и которые не использовались еще в основных книгах [1—4].

14. Алексеев М. А., Залкинд М. С., Кушнарев В. М. Решение человеком задачи выбора при вероятностном подкреплении двигательных реакций.— В сб.: «Биологические аспекты кибернетики».—М.: Изд-во АН СССР, 1962, с. 198—209. (Результаты использованы в § 2.4 при описании опытов с людьми, производящими альтернативный выбор.)

15. Вайсборд Э. М., Розенштейн Г. Ш. О времени «жизни» стохастических автоматов.—Изв. АН СССР:

Сер. Техн. киберн. 1965, № 4, с. 52—59. (В этой работе приведена точная модель максимизации «жизни» автомата, которая на уровне внешней интерпретации описана нами в § 2.6.)

16. Филоник С. А., Солнцев С. В. Реализация арифметических функций на однородных структурах. — Изв. АН СССР:

Сер. Техн. киберн. 1974, № 4, с. 114—126. (Наш пример умножения в столбик, обсуждавшийся в § 5.4, заимствован из этой работы. Кроме того, в данной работе приведен метод умножения, дающий результат существенно быстрее, а также методы деления на однородных структурах.)

17. Варшавский В. И., Мараховский В. Б. и др. Однородные структуры. Анализ. Синтез. Поведение.—М.: Энергия, 1973, 140 с. (В этой книге читатель найдет многочисленные примеры использования однородных структур для решения самых разнообразных задач.)

Модели голосования, рассмотренные в § 4.6, были исследованы С. Б. Котляр, чьими результатами мы и воспользовались.

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

Автомат 24 и д.

—, адаптация 41

— бесстрастный 105

— вероятностный 24, 34, 38

—, взаимодействия 31 и д.

—,— между автоматами 56, 145, 155

—,— со средой 32, 56

—,— — — динамической 41

—, — — — стационарной 30, 32—36

—, время жизни 53—55

—, выбор действия 30, 31

—, граф смены состояний 42— 55

— детерминированный 24, 38, 86

— —,структура 45

— Кринского 37, 47

— Крылова (осторожный) 39, 45

— оптимист 105

— пессимист 105

—, поведение 31 и д.

—, — целесообразное 31—36

—, ранг рефлексии 95—100

— Роббинса 38

— с линейной тактикой 23, 33, 34, 36, 108

— с переменной структурой 44, 45, 47—50

—,состояния 24 и д.

—степень конформизма 145— 151

— упрямый 144—151 Адаптация 41, 50

Аллогенез 190, 191

Арогенез 190, 191

Биоценоз 5

Вероятность 30 и д.

— выигрыша единичного 61, 71, 75

Вероятность выигрыша суммарного 65

— нештрафа (поощрения) 30— 56

— переходная 47, 54

— смены состояния 45, 46

— штрафа (наказания) 29—56

Взаимодействие 31 и д.

— в коллективе 56, 145

—, граф 92

— ограниченное 91

— парное случайное 86—94

— — — второго типа 89

— — — первого типа 87

— с ограниченным числом соседей 86

— со средой 56

Время жизни автомата 53—55

Глубина памяти автомата 35,

40, 48, 49, 65, 88 и д., 127

Голосование 138—151, 164—168;

Граф смены состояний 52—55

Децентрализация 12 и д.

Дизъюнкция 103

Динамическое равновесие 75

Дисциплина обслуживания 120

Задача Майхилла о цепи стрелков 153—160

Игра 60 и д.

— в размещения 63—69, 84, 95

— в распределения 72—74, 87, 89

Игра Гура 78—80, 88, 89

— Мора

— с общей кассой 66—69, 76, 88, 90

— с ограниченным взаимодействием 92

— эквивалентная 64

Иерархия 137

Йога 173

Каналы обслуживания 116, 121, 128

Касса общая 63 и д.

Качество синхронизации 162

Клиент 116

Коллектив автоматов 30, 39, 55, 66, 100, 104, 108, 112

— — неоднородный 100, 108— 114, 146

— — однородный 100, 164—168

Конвейер 16, 19, 20

Конформизм 145—151

Конъюнкция 101

Лабиринт 27

«Маленькая зверушка» 29 ид.

Матрица платежная 112

— смены состояний 46

Механизм равновероятного выбора 31, 32, 46

Минимизация длины очереди 118, 122

Моделирование форм поведения 29 и д.

Неоднородность в коллективе автоматов 100, 108—114, 146

Нештраф 31 и д.

Обслуживание 116—128

—каналы 116, 121, 128

Обслуживание, качество 117— 121

—,клиенты 116

—,критерии 117

Общая касса 63 и д.

Ограничение 7

Операции на рынке 13, 15, 80

Оптимизм 105

Очередь 115—128

Память магазинная 120

Партия Антоса 76, 77

— максимальной цены 77

— Мора 66, 67, 73, 88, 94

— Нэша 61, 72, 73, 77, 90, 92—94, 145

Переключение 53

— оптимальное 55

Пессимизм 105

Поведение коллективное 30, 80, 96—108, 173

— — автоматов 30, 32, 96, 104, 108

— — потребителей ресурса 83

Подсистема 12

Принятие решений 138

Приоритеты 121—132

Равновесие динамическое 75

Ранги рефлексии 95—100, 180

Ресурс ограниченный 80

Рефлексия 95 и д.

Рефлексы 26

Сегрегациогенез 184, 188, 189

Сеть связи 9, 91, 136

—система управления 10, 22

— ЭВМ 196 и д.

Синтезогенез 179—184, 187, 188

Синхронизация 153—164

—,качество (точность) 162

Синхрофазировка 163

Система 7 и д.

— управления 7 и д.

— — децентрализованная 12, 17, 23 и д.

— —классификация 17

— —.подсистемы 12

—характеристики 17, 20

Система управления, цели локальные 18, 21

— —, — общие 80

— — централизованная 17, 23 и д.

— —, эффективность функционирования 80

Ситуация равновесия по Нэшу 61

Среда 30

— динамическая 40

— переключающаяся 42—52

— стационарная 31—36, 47

— — случайная 36, 47, 65

Стратегия игры 60, 63, 64, 69, 70

Тактика линейная 33—36

Телогенез 191

Теория управления 30 и д.

Техноценоз 5—8, 193—195

Точка Антоса 76, 77

— максимальной игры 77

— Мора 66, 67, 73, 88, 94

— Нэша 61, 72, 73, 77, 90, 92—94, 145

Точность синхронизации 162

Управление 7 и д.

— децентрализованное 12 и д., 23

— иерархическое 137

—,критерий 7, 23

— централизованное 17, 23 и д.

Уравниловка 67

Цена партии Мора 67

— — Нэша 62

Централизация 17, 23 и д.

Цепь стрелков, задача Майхилла 153—160

Штраф 31 и д.

Эволюция 182 и д.

— сети обработки данных 198

— — ЭВМ Эффективность 6, 80

ОГЛАВЛЕНИЕ

Вместо предисловия ................ 3

Глава 1. Как возникает децентрализованное управление? 5

1.1. Искусственный мир .......... 5

1.2. Системы, которые в полном объеме никто не создавал 9

1.3. Несколько поучительных примеров . ...... 13

1.4. Обсуждение примеров ............ 17

1.5. Зачем нужна децентрализация? ......... 21

Глава 2. Просто ли существовать в сложном мире? ... 26

2.1. Парадоксы целесообразности . ........ 26

2.2. «Маленькая зверушка» . . . ........ 29

2.3. Линейная тактика—залог успеха ....... 33

2.4. «Личные» качества автоматов ......... 36

2.5. Как жить в динамическом мире? ........ 40

2.6. «Доживем до понедельника» . ........ 51

2.7. От индивида к коллективу . ......... 55

Глава 3. Согласованность без договоренности . .... 58

3.1. История начиналась в Арбатове ........ 58

3.2. Когда все одинаковые ............ 69

3.3. Распределение ограниченного ресурса . ..... 80

3.4. Что дает случайное взаимодействие ....... 85

3.5. «Он думает, что я думаю...» .......... 94

3.6. Оптимисты и пессимисты в мире автоматов . . . 100

3.7. Еще три простые модели . . ........ 103

Глава 4. Когда «все по справедливости» . ...... 115

4.1. Прав ли был Остап Бендер? . ........ 115

4.2. Дилемма парикмахера и приоритеты . ..... 121

4.3. Как мастер распределяет наряды . ...... 128

4.4. Проблема нескольких арен . ......... 132

4.5. Задача о жилищной комиссии и родственные ей задачи ................... 137

4.6. «Упрямые» автоматы и голосование . ..... 144

Глава 5. Коллектив во времени ........ 152

5.1. Что такое синхронизация? . . . ....... 152

5.2. Управление стрелками . . . . ....... 155

5.3. Синхронизация и асинхронность . ....... 160

5.4. Гимн однородным структурам . . ...... 164

5.5. Почему йога — не наш путь? . ........ 173

Глава 6. Диалектика простого и сложного . ..... 178

6.1. Синтезогенез и интеграция усилий ....... 178

6.2. Сегрегациогепез и его последствия . . .... 184

6.3. Эволюция в городе Едгин ........ 191

6.4. Вместо заключения. Эволюция продолжается . . . 195

Литература и комментарий ....... ..... 201

Предметный указатель .............. 203

Варшавский В. И., Поспелов Д. А.

12 3 4 5 6 7 8 9 10 Следующая ⇒

Последнее изменение этой страницы: 2019-05-06; Просмотров: 217; Нарушение авторского права страницы