Самоорганизация вычислительных сетей

САМООРГАНИЗАЦИЯ ВЫЧИСЛИТЕЛЬНЫХ СЕТЕЙ

Постановка задачи

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

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

Рис.1.2 Схема компьютерной системы, в которой отдельные ЭВМ подчинены управляющему компьютеру.

Введение

1) Понятие самоорганизации

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

При самоорганизации в системах возникают разнообразные состояния: солитоны, автоколебания или автоволны, диссипативные структуры.

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

- структуры, возникающие при притоке энергии в систему и

существующие за счёт постоянного рассеивания поступающей энергии.

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

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

2) Примеры явления самоорганизации.

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

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

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

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

Явление самоорганизации наблюдается в самых разных областях науки, таких как

- физика

- химия

- биология

- кибернетика:

-искусственный интеллект

- психология

- социология

- экономика

- антропология

Традиционный физический пример самоорганизации - эффект Бенара

Явление заключается в возникновение в подогреваемом снизу слое жидкости структуры из шестигранных призматических ячеек (ячейки Бенара рис.2).

В опыте Бенара рассматривается тонкий слой масла, налитого на плоскую пластину.

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

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

Рис.2 Ячейки Бенара

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

Рассмотрим пример образования макроскопических структур в химии (химических системах).

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

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

Рис.3 Некоторые конфигурации, возникающие при реакции Белоусова--Жаботинского в тонком слое в чашке Петри.

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

Нейрон

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

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

Вычислительная сеть

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

Рис.3. Схема вычислительной сети.

Каждый примитивный компьютер обменивается информацией с соседями по сети.

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

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

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

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

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

Зададим сеть из элементов.

Пусть имеем набор из N элементов, пронумерованных последовательно числами j = 1,...,N.

Укажем связи между элементами: для каждого j-го элемента зададим группу элементов, являющихся его соседями.

O(j) - множество ближайших соседей элемента j.

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

Определим правила перехода между состояниями.

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

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

Правило перехода имеет вид:

, где

F - функция от 2-х переменных: состояния элемента и суммы состояний его ближайших соседей в текущий момент времени n .

Если функция F зависит от , то клеточный автомат обладает памятью.

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

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

Тогда вместо функции F необходимо задать набор вероятностей переходов:

,

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

Рассмотрим регулярные сети, элементы которых занимают узлы правильной решётки (квадратная, гексагональная плоская решётка).

Динамика рассматриваемых детерминированных клеточных автоматов с конечным числом состояний является необратимой. По конечному состоянию всей сети невозможно однозначно восстановить её исходное состояние.

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

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

Клеточные автоматы класса II генерируют локализованные простые структуры. Эти простые структуры могут быть стационарными или периодическими по времени.

Клеточные автоматы классов III и IV обладают более сложной динамикой. В пределе различные картины активности сменяют друг друга, никогда не повторяясь. Локальное возмущение порождает процесс изменения активности, который захватывает с течением времени всё большую часть сети. По прошествии большого числа шагов свойства процесса теряют зависимость от начальных условий. Автоматы класса III обладают “эргодическим” или “турбулентным ” поведением.

Динамика клеточных автоматов класса IV существенно зависит от начальной картины активности сети. Подбирая определённые начальные условия, можно генерировать самые различные последовательности сменяющих друг друга картин. Клеточные автоматы 4 класса могут осуществлять универсальные вычисления, подобно “Машине Тьюринга”.

Примером автомата класса IV является игра “Жизнь”.

Игру "Жизнь" изобрел американский математик Дж.Х.Конвей. "Жизнь" категории игр, имитирует процессы живой природы.

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

У каждой позиции бесконечного поля имеется ровно 8 соседей - четыре по вертикали и горизонтали, четыре по обеим диагоналям.

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

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

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

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

- полностью исчезают;

- переходят в устойчивую конфигурацию (перестают изменяться);

- выходят на "колебательный режим".

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

"Законы жизни" Конвея:

1. ВЫЖИВАНИЕ. Каждая клетка с двумя или тремя соседями, выживает и переходит в следующее поколение.

2. ГИБЕЛЬ. Каждая клетка, у которой имеется более трех соседей гибнет от перенаселенности. Каждая клетка, у которой менее двух соседей, гибнет от одиночества.

3.РОЖДЕНИЕ. В пустой позиции, с которой соседствуют ровно три клетки, на следующем ходе зарождается клетка.

Гибель и рождение происходят одновременно.

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

Примером может служить сеть, способная выделять движущиеся объекты на фоне шума.

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

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

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

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

В мире клеточных автоматов имеется класиификация (S. Wolfram, 1983), согласно которой все автоматы делятся на четыре класса, в зависимости от типа динамики изменяющихся состояний. Автоматы первого класса по истечении конечного времени достигают однородного состояния, в котором значения всех элементов одинаковы и не меняются со временем. Ко второму классу автоматов относятся системы, приводящие к локализованным структурам стационарных или периодических во времени состояний элементов. Третий класс составляют “блуждающие” автоматы, которые с течением времени посещают произвольным (непериодическим) образом все возможные состояния элементов, не задерживаясь ни в одном из них. И, наконец, четвертый класс составляют “странные” автоматы, характер динамики которых зависит от особенностей начального состояния элементов. Некоторые начальные состояния приводят к однородному вырождению автомата, другие - к возникновению циклической последовательности состояний, третьи - к непрерывно меняющимся (как “по системе”, так и без видимой системы) картинам активности элементов.

К автоматам четвертого типа относится знаменитая игра “Жизнь” Дж. Конвея. Каждый элемент (организм) колонии “Жизни” может находиться в состоянии покоя или активности. Ближайшими к данному элементу объявляются четыре его соседа на квадратной решетке. Покоящийся элемент может возродиться к активности, если рядом с ним находится ровно три активных соседа. Активный элемент сохраняет “жизнеспособность” при двух активных соседях. Если соседей больше чем два, то элемент гибнет от тесноты, а если их меньше, чем два, то гибель наступает от скуки. Хотя наблюдение за сложной эволюцией начального состояния “Жизни” может дать определенную пищу для мыслительной исследовательской деятельности, в целом этот автомат остается не более чем математическим курьезом.

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

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

Литература

1. Г. Хакен “Синергетика: иерархии неустойчивостей в самоорганизующихся системах и устройствах.”

2. А.Ю. Лоскутов, А.С. Михайлов “Введение в синергетику”

3. С.П. Курдюмов “Самоорганизация сложных систем”

4. М.И. Рабинович, Д.И. Трубецков “Введение в теорию колебаний и волн”