Клітинний автомат (КА) - набір клітин, що утворюють деяку періодичну решітку із заданими правилами переходу, що визначають стан клітини в наступний момент часу через стан клітин, що знаходяться від неї на відстані не більше деякого, в поточний момент часу. Як правило, розглядаються автомати, де стан визначається самою клітиною і найближчими сусідами. Як грати зазвичай розглядається кубічна решітка. Один з найцікавіших прикладів клітинного автомата - гра «Життя».
визначення
Клітинний автомат складається з набору об'єктів (осередків), зазвичай утворюють регулярну решітку. Стан окремо взятого i-го об'єкта (або осередку) в момент часу n характеризується деякою змінною, яка може бути цілим, дійсним або комплексним числом, або являти собою набір з декількох чисел. Розглянуті стану осередків змінюються синхронним чином через дискретні інтервали часу відповідно до локальних ймовірносними правилами, які можуть залежати від стану змінних в найближчих сусідніх вузлах. Ці правила не змінюються з часом.
Клітинний автомат є дискретною динамічною системою, поведінка якої повністю визначається в термінах локальних залежностей. Назвемо дискретним простором простір над дискретною безліччю елементів. Примірник простору цього класу будемо називати гратами клітинного автомата, а кожен його елемент - кліткою. Кожна клітина характеризується певним значенням з деякого безлічі. Про клітці кажуть, що вона містить або має відповідне значення, або знаходиться або перебуває в стані, кодируемом даними значенням ain. Воно можемо бути булевим, цілим, числом з плаваючою точкою, безліччю або іншим об'єктом, в залежності від потреб завдання. Сукупність станів всіх клітин решітки називається станом решітки. Стан решітки змінюється відповідно до деякого законом, який називається правилами клітинного автомата. Кожна зміна стану решітки називається итерацией. Час в розглянутій моделі дискретно і кожна ітерація відповідає нікому моменту часу. Правила визначають, яке значення має міститися в клітці в наступний момент часу, в залежності від значень в деяких інших клітинах в поточний момент, а також, можливо, від значення, що міститься в ній самій в поточний момент. Якщо новий стан клітини залежить від поточного її стану, то про відповідному клітинному автоматі кажуть, що він є автоматом з клітинами з пам'яттю, інакше - автоматом з клітинами без пам'яті. Безліч клітин, що впливають на значення даної, за винятком її самої, називається околицею клітини. Околиця клітини зручніше задавати, якщо на решітці ввести метрику, тому далі, для зручності, будемо говорити про решітці, як про дискретно метричному просторі. Одне з головних відмінностей клітинної системи від всіх інших обчислювальних систем полягає в тому, що у всіх інших системах присутні дві принципово різні частини: архітектурна, яка фіксована і активна (тобто виконує деякі операції) і дані, які змінні і пасивні (тобто самі по собі вони нічого зробити не можуть). У клітинних автоматів і та, і інша частини складаються з принципово ізоморфних, не відрізняються один від одного елементів. Таким чином, обчислювальна система може оперувати своєю матеріальною частиною, модифікувати, розширювати себе і будувати собі подібних [1]. Хоча системи цього класу і були придумані Джоном фон Нейманом, така паралельна архітектура отримала назву «Не-фон-неймановской», так як послідовну архітектуру він створив раніше. Якщо порівнювати клітинні автомати і звичайні диференціальні рівняння (ОДУ), то одне з основних відмінностей перших від других полягає в локальності правил, за допомогою яких описується динаміка системи. У разі застосування ОДУ ми користуємося деякими правилами зміни усереднених по всій системі величин - середніх (наприклад, концентрацій). При цьому спочатку вважають, що такі правила існують. У разі КА існування таких узагальнених правил необов'язково. Досить знати закони розвитку системи на мікро- або мезоуровне в невеликих просторових областях (осередках), з яких складається макросистема. Важливо лише, що ці локальні правила однакові для всіх осередків. Іншою відмінністю КА від диференціальних рівнянь (ДУ) є використання не тільки дискретних, але і, як правило, цілочисельних змінних. Дискретність змінних дозволяє розглядати великий клас розривних недіфференціруемих функцій. Слід зазначити, що дискретні властивості КА помітно зменшуються при роботі з великими значеннями змінних, але ніколи не зникають. Завжди існує мінімальний дискретний крок зміни змінної. У разі ж чисельного рішення ОДУ або ДУ в приватних похідних можна зменшувати крок дискретності до як завгодно малих величин.
Відзначимо основні властивості класичної моделі клітинних автоматів.
• Локальність правил. На новий стан клітини можуть впливати тільки елементи її околиці і, можливо, вона сама;
• Однорідність системи. Жодна область решітки не може бути розпізнана від іншої з яких-небудь особливостей правил і т. П. Однак на практиці решітка виявляється кінцевим безліччю клітин (адже неможливо виділити необмежений обсяг даних). В результаті можуть мати місце крайові ефекти. клітини стоять на кордоні решітки будуть відмінні від інших за кількістю сусідів. Щоб уникнути цього можна ввести періодичні крайові умови
• Безліч можливих станів клітини - звичайно. Це умова необхідна, щоб для отримання нового стану клітини потрібно кінцеве число операцій. Відзначимо, що воно не заважає використовувати клітини для зберігання чисел з плаваючою точкою при вирішенні прикладних задач.
• Значення у всіх клітинах змінюються одноразово, в кінці ітерації, а не в міру обчислення. В іншому випадку порядок перебору клітин решітки, при здійсненні ітерації, суттєво впливав би на результат. Необхідно відзначити, що на практиці, при вирішенні певних завдань, виникає потреба в тому, щоб відмовитися від останніх трьох властивостей.
Основний напрямок дослідження клітинних автоматів - алгоритмічна розв'язність тих чи інших проблем. Також розглядаються питання побудови початкових станів, при яких клітинний автомат буде вирішувати задану задачу.
Класифікація клітинних автоматів
КА можна розділити на детерміновані і імовірнісні. рухомі та нерухомі. однорідні і неоднорідні. прості абстрактні і складні, точно описують реальні системи.
Рухомі та нерухомі КА
Рухливі КА характеризуються можливістю зміни положення клітини в решітці під час еволюції системи. У нерухомих КА положення клітини під час еволюції залишається постійним.
Детерміновані і імовірнісні КА
детерміновані КА
У детермінованих КА стан осередку ain + 1 в наступний момент часу однозначно визначається станом цього осередку і її найближчих сусідів в попередній момент часу. У цьому випадку стан даного елемента в момент часу n + 1 є однозначною функцією F від двох змінних - стану цього елемента і суми станів його найближчих сусідів в попередній момент часу n. При такому визначенні клітинний автомат не має пам'ять. Клітинні автомати з пам'яттю можна отримати, припустивши, що функція F залежить, наприклад, також від стану елемента в ще більш ранній момент часу.
імовірнісні КА
КА, в яких стану осередків в наступний момент часу визначаються на основі деяких ймовірностей, називаються імовірнісними КА (ВКА). У класичних ВКА правила переходів мають абстрактний характер і не пов'язані однозначно з реальними процесами, що відбуваються в моделюється системі. У таких автоматах при моделюванні процесу для кожного осередку датчиком випадкових чисел генерується випадкове число Q (0 Для вирішення найбільш важких завдань типу "реакція - дифузія - конвекція" з урахуванням флуктуацій був розроблений метод імовірнісного клітинного автомата з застосуванням процедури Монте-Карло (ВКА-МК або просто ВКА). Клітинний автомат являє собою регулярну решітку, що складається з N2 = N0 елементарних осередків. Форма решітки може бути не тільки квадратної, але і прямокутної з сильно витягнутими осередками. Кожна осередок характеризується набором цілих чисел: числом молекул відповідного сорту в даній комірці (наприклад, nA, nB, nC в разі трьох сортів молекул A, B і C) і своїми цілочисельними координатами (наприклад, i і j). Осередку приписується також певний обсяг Vm і лінійний розмір l = (Vm) 1/3. Обсяг Vm використовується при завданні ймовірностей протікання хімічних реакцій в осередках. Всі осередки вважаються однорідними. Іноді використовуються правила, записані в вигляді звичайних диференціальних рівнянь (клас КА-ОДУ). В цьому випадку стану осередків задаються набором змінних, значення яких здатні приймати будь-які дійсні числа. Для таких автоматів диференціальні рівняння вирішуються для кожного осередку окремо протягом фіксованого відрізка часу, при цьому кожна клітинка може мати різні початкові умови. Цей клас КА дуже щільно прилягає до ДУ в приватних похідних. Моделі типу КА-ОДУ займають проміжне стан між КА і ВКА, а також між простими КА і ДУ в приватних похідних. Основною ідеєю КА-ОДУ є розбиття моделюється області на рівновеликі осередки і рішення системи ОДУ незалежно в кожному осередку з різними початковими умовами. У деяких моделях просторове розташування осередків несуттєво, а в інших кількість сусідніх осередків і розмірність простору відіграють вирішальну роль (випадки розповсюдження хвиль або освіти стаціонарних просторових структур в неперемешіваемий середовищі). У моделях КА-ОДУ передбачається, що клітина містить дуже велике число часток, що дозволяє застосовувати ОДУ і безперервні функції. Ця обставина залишає тільки один спосіб для моделювання дифузії, а саме просте усереднення концентрації по сусідніх осередків. 2. ВКА досить часто використовується для моделювання фізико-хімічних процесів в нанорозмірних системах, що пов'язано зі складністю застосування Класичний методів заснованих на вирішенні ДУ
Схожі статті