Клеточные автоматы

Теорія  кодування є сугубо прикладною наукою і її практичні досягнення достатньо  добре відомі. Однак найбільшого  розповсюдження набули лише, у певному  сенсі, примітивні способи кодування: перевірка на парність, коди Хемінга, циклічні повірки ітд. Це стається як через складність математичного  апарату, так і через недостатній  розробці питань взаємозв’язку кодування і модуляції. Задана надійність кодування досягається лише завдяки надлишковості інформації. Цікавою у цьому плані є концепція кодування і декодування на базі ОС-моделей. В основу цього підходу покладають можливість генерації полігенними однорідними структурами будь-якої наперед заданої скінченної конфігурації із деякої початкової конфігурації. У цьому випадку кодер і декодер, що знаходяться на шляху передачі інформації від джерела до приймача, виконуються на основі деякої ОС-моделі і дозволяють вести кодування і декодування паралельним чином із великою швидкістю. Такий підхід дозволяє скоротити об’єм надлишкової інформації, замінюючи подачу самої інформації алгоритмом, що її породжує. Такий підхід є доволі природнім, оскільки він лежить в основі кодування генетичної інформації в живих системах. В принципі, такий підхід можна використовувати для стискання інформації.   

Сьогодні  важко передбачити в якому  напрямку буде розвиватися обчислювальна  техніка і результати впровадження її в наше життя. Проводяться роботи по фундаментальним проблемам створення  молекулярних ЕОМ, штучних органічних систем, які будуть мати здатність  до самовідтворення. Це дозволяє звести свого роду мости між біологічними і обчислювальними науками, що відкриває широкі можливості для взаємного збагачення і розвитку. Подальший розвиток перспективної паралельної обчислювальної техніки буде ставати все більш тісним із біологічними клітковими системами, навіть до використання окремих біологічних елементів і принципів їхнього функціонування і організації[1].

 

2.3 Використання  кліткових автоматів у фізиці

 

Використання  дискретних ґратчастих систем має довгу  і доволі продуктивну історію  у фізиці. Незважаючи на це, точним решітковим моделям, які підкорюються оборотній  динаміці – із будь-якого стану  динамічної системи можна вивести  її попередній стан, не приділялося  достатньої уваги. Даний вид мікроскопічної оборотності – важлива властивість  всієї мікроскопічної динаміки. Оборотні ґратчасті системи стають навіть і більш фізично реалістичними, якщо ми від них будемо вимагати виконання принципу локальності  взаємодії і строгих законів  збереження. Дійсно, деяка оборотна динаміка, що зберігає імпульс і  в якій дискретне переміщення  частинок між сусідніми вузлами  решітки відбувається в дискретні  моменти часу, дуже точно відтворює  гідродинаміку на макроскопічному  рівні[3]. Вказані ґратчасті динамічні системи можна моделювати клітковими автоматами.

  Так,  автомати ґратчастих газів (Lattice Gas Automata) є спеціальним класом однорідних структур, які широко використовуються, наприклад, для симулювання руху в’язкої рідини і хвильових рівнянь. У наш час дослідження із LGA-тематики являють собою досить добре розроблену область загального дослідження ОС-моделей. Квантові ОС-моделі стають все більш і більш важливими для задач симулювання фізичних систем таких як кантові ґратчасті гази.

Великий розвиток отримало клітково-автоматне  моделювання потоків рідини. Добре  відомий цілий ряд двовимірних  моделей разом із чотирьохвимірною моделлю, що симулює трьохвимірні потоки. Ю. Медвєдєвим була запропонована трьохвимірна ОС-модель (RD-I), яка має набагато меншу складність чим чотирьохвимірна модель. RD-I моделює потоки рідини наступним чином. В клітках знаходяться деякі гіпотетичні частинки. Їхня маса і швидкість одиничні, кількість всіх можливих напрямків вектора швидкості співпадає із числом сусідніх кліток, а правила руху вибираються так, щоб виконувалися закони збереження маси і імпульсу. Кожен такт роботи RD-I розбитий на дві фази: зіткнення і зрушення. На фазі зіткнення відбувається зміни напрямку руху частинок у відповідності до деякого закону зіткнення. Але на фазі зрушення кожна частинка повинна рухатися згідно її вектора швидкості у сусідню клітку. Отримані при цьому результати експериментальних досліджень підтверджують, що визначена таким чином RD-I дійсно досить задовільно моделюють потоки в’язкої рідини (рис. 13).

Рисунок 13

Неважко впевнитися, ОС-моделі безпосередньо  володіють рядом основних рис  фізичної моделі світу – однорідністю і локальністю. Тоді як їхня властивість  оборотності в загальному випадку  не має місця апріорі і її потрібно завчасно запрограмувати у тій чи іншій ОС-моделі. Більше того, в загальному випадку проблема визначення оборотності динаміки класичних ОС-моделей алгоритмічно нерозв’язна. З іншого боку, є можливість заздалегідь конструювати оборотні ОС-моделі, можливо, спрощені в сенсі окремих характеристик, але більш адекватні фундаментальним аспектам фізичних процесів. На основі оборотних ОС-моделей були побудовані і дослідженні моделі дифузії, турбулентності, рівноваги, гідродинаміки, газодинаміки і хвильової оптики. Найпопулярнішими із таких моделей є моделі Айзинга.

При моделюванні  процесів і феноменів із перерахованих  розділів фізики використовувалась  одна фундаментальна властивість ОС-моделі – проста поведінка великого числа  одиничних достатньо простих  автоматів ОС-моделі визначає скільки  завгодно складну поведінку всієї  моделі в цілому. Саме ця властивість  лежить в основі багатьох фізичних процесів і явищ. Наприклад, молекули газу, підкоряючись дуже простим законам, породжують досить складну колективну поведінку: звукові хвилі, вихри  і турбулентність[2].

 

2.4 Однорідні  структури і диференційні рівняння

 

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

Одним із основних методів для чисельного рішення диференційних рівнянь  є метод скінченних різниць, у  випадку рішення крайових задач  він називається сітковим. Як правило, рішення крайових задач виконують  на ЕОМ. Однак, враховуючи послідовний  принцип обчислень більшості  сучасних ЕОМ, даний підхід потребує значних часових затрат. Тому, для  вирішення таких задач пробують створити супер-ЕОМ або ЕОМ із спеціальною архітектурою. Ідея сіткового  методу найкращим чином відповідає концепції обчислювальних ОС-моделей, в яких глобальна поведінка, що описується диференційними рівняннями, повністю визначається локальними взаємодіями  одиничних автоматів. Тому використання ОС-моделей дозволяє застосовувати  нові методи рішення рівнянь в  часткових похідних, різницевих, а  також інтегро-диференційних. Наприклад, такі підходи інтенсивно використовуються для рішення рівнянь Нав’є-Стокса. В деякому сенсі можна говорити про однорідні структури, як про модельний аналог диференційних рівнянь.

Загальний принцип, який лежить в основі таких  підходів – це побудова обчислювальної ОС-моделі, чия динаміка відображує поведінку рішення шуканого диференційного рівняння. Такі підходи є досить перспективними для вирішення крайових задач зі складною геометрією границь  чи граничними умовами, що залежать від  часу. Наприклад, дуже зручними для  дослідження диференційних рівнянь  є згадані вище CAM-машини. Також ОС-моделі дозволяють створювати дуже точні моделі динаміки рідин, які витримують конкуренцію навіть в обчислювальних аспектах із традиційними методами. Більш прямий підхід до використання обчислювальних ОС-моделей для рішення крайових задач і різницевих рівнянь базується на прямій аналогії різницевих операторів і локальних функцій переходу. Саме такий підхід дуже тісно зв’язаний із ідеєю Е. Бенкса відносно використання загальної ОС-концепції для моделювання неперервних фізичних просторів[2].

2.5 Використання  однорідних структур у соціології 

 

Дуже  широко ОС-концепція використовується також для дослідження різного  типу автоматних моделей колективної  поведінки. В багатьох задачах моделювання  соціальних явищ на сьогодні використовують класичні математичні методи, наприклад, описання динаміки деякого процесу  диференційними рівняннями, але появилися  і перші досить цікаві моделі соціальних явищ, що базуються на основі ОС-концепції. Ця концепція використовується для  створення моделей рику, моделювання  електоральних процесів, процесів глобалізації, є цікаві спроби застосування однорідних структур для моделювання поширення  слухів чи епідемій. Пропонується дати математичний опис таким процесам як самоорганізація населення, освіта і ріст міст чи навіть країн, що дуже важко формалізувати, на базі ОС-моделювання.

Цікаві  ОС-моделі пропонуються для дифузії  інформації. Наприклад, була описана  цікава система кліткових автоматів, яка відображає процес розповсюдження і публікації новин серед окремих  інформаційних джерел. При цьому, отримані на ній результати відносно дифузії новин на веб-сайтах відповідає реальному стану речей.

Окремо  варто виділити спроби застосування ОС-концепції до моделювання електорального процесу. В циклі робіт Т. Брауна розглядаються цілий ряд контекстуальних  моделей електорального процесу. Він  вважає, що навіть класичні однорідні  структури можуть бути застосовані  для даних цілей, коли виборчі  переваги особи визначаються установками  його найближчого оточення. Так, одна із таких моделей припускає, що індивід  приймає рішення голосувати за «демократів» чи «республіканців» згідно правила  простої більшості. Враховуються тільки погляди самої особи і її чотирьох сусідів ( індекс сусідства фон Неймана) . Коли із п’яти людей три або  більше підтримують демократів, то особа також голосує за демократів. Коли ж більшість його сусідів віддають перевагу республіканцям, то особа приймає точку зору більшості.

                                                      Рисунок 14

При початковому  розподілі одиниць у двовимірному масиві (нехай 1 буде відповідати республіканцям) із щільністю після 50 (більше ітерацій робити не було змісту, бо процес стабілізувався) ітерацій результат можна побачити на рис. 14.

В наш  час на стадії становлення знаходиться  комп’ютерна соціологія, яка базується  на використанні можливостей комп’ютерів  для вирішення соціологічних  як теоретичних, так і емпіричних, і практичних задач. Цей напрямок виник  як засіб розробки і повірки  соціологічних теорій, виміру соціальних явищ, визначення принципів і закономірностей  будови і функціонування соціальних процесів. Основним теоретичним поняттям комп’ютерної соціології є поняття  штучного суспільства – реально  функціонуючої комп’ютерної системи, яка складається із однієї чи декількох  комп’ютерних моделей для проведення імітаційного моделювання. Таким чином, на відміну від традиційних соціологічних теорій, які існують в текстовій формі чи математичних формул, в комп’ютерній соціології теорія – це реально функціонуюча система, яка може базуватися і на ОС-концепції[2,10,11].

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

МОДЕЛЬ  ПОШИРЕННЯ ІНФЕКЦІЇ НА БАЗІ КЛІТИНИХ АВТОМАТІВ

 

В цьому  розділі розглядається проста епідеміологічна  модель,  яка, я надіюсь, допоможе дослідженню поширення інфекцій і розробці ефективних стратегій  боротьби з ними. Моделі, які використовують таку ж саму концепцію застосовувалися  для боротьби із хворобою Шагаса в  Центральній Америці[6].  Для реалізації моделі я розробив нескладну програму на мові Delphi (текст в додатку А), алгоритм не є найефективнішим, але повністю підходить для поставлених задач.

 

3.1 Концепція  поширення властивості в просторі 

 

В статті[6] було розглянуто концепцію моделювання поширення у просторі областей, що задовольняють деякій властивості із початкової області . Класичні підходи розв’язку таких проблем є достатньо складними і вони, в основному, моделюють тільки лінійне поширення, чого часто буває не достатньо. Тому пропонується підхід на базі кліткових автоматів.

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

Алфавіт ділиться на дві підмножини -  і , - це множина станів, що задовольняють деякій властивості   , а доповнення    відносно алфавіту . Для визначення чи стан задовольняє вводиться індикаторна функція .

 

Тоді  буде визначатися через як  .

Вводиться відображення , що характеризує поведінку клітки після поширення на неї властивості  

Поширення властивості  залежить від впливу навколишнього середовища (тобто на скільки сусідніх кліток вже поширилася в момент часу ),  для цього введемо міру цього впливу:

 ,

де , а .

Тепер можна  ввести відображення , що визначає чи пошириться властивість на клітку с в момент часу .

 

Підсумувавши  все запишемо правило локального переходу, що визначає динаміку системи:

,

де  і – це відповідно і , і – деякі відображення.

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

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