اتوماتای سلولی چیست؟

اتوماتا (Automata) یک واژه تکنیکی است که در علوم کامپیوتر و ریاضیات برای یک ماشین تئوری مورد استفاده قرار می‌گیرد که حالت‌های داخلی (Internal State) خود را بر اساس ورودی‌ها و نیز حالت‌های قبلی خود تغییر می‌دهد. مجموعه حالت‌ها همیشه به صورت گسسته و متناهی تعریف می‌شوند و این تعریف حالت‌ها موجب غیرخطی شدن دینامیک سیستم می‌شود.  

 اتوماتای سلولی(Cellular Automata) یا CA به یک مجموعه از چنین اتوماتایی اطلاق می‌شود که در راستای یک شبکه فضایی چیده شده‌اند و حالت‌های آن‌ها به صورت همزمان توسط اعمال یکنواخت یک «تابع انتقال حالت (State Transition Function) آپدیت می‌شوند. تابع انتقال حالت معمولا به حالت‌های سلول‌های همسایه اشاره می‌کند.

اتوماتای سلولی

بنا بر آنچه گفته شد، یکی از ویژگی‌های اتوماتای سلولی، آپدیت شدن همزمان آن‌ها است. به این آپدیت شدن همزمان، آپدیت سنکرون (Synchronous Updating) نیز می‌گویند. البته عمل آپدیت شدن می‌تواند به صورت غیر همزمان نیز صورت بگیرد که در این حالت به آن آپدیت آسنکرون (Asynchronous) می‌گویند. ایده اصلی در پس مفهوم اتوماتای سلولی را دانشمندی به نام جان فون نویمان (John von Neumann) و همکارش استنی سواف اولام (Stanisław Ulam) در سال‌های ۱۹۴۰ و ۱۹۵۰ ابداع شد.

در واقع این دو فرد یک «فریم ورک مدلسازی» (Modeling Framework) را ابداع کردند که برای مدل‌سازی سیستم‌های پیچیده  (Complex Systems)  جزو اولین الگوریتم‌ها به شمار می‌آید و به منظور توصیف رفتار «خود مولد  (Self Reproductive) و  قابل تکامل (Evolvable) سیستم‌های زنده مورد استفاده قرار می‌گیرد.

به دلیل این که اتوماتای سلولی توانایی فوق‌العاده‌ای در توصیف دینامیک‌های به شدت غیرخطی فضا زمانی دارند و این کار را با شیوه بسیار ساده و کوتاه انجام می‌دهند، در مدلسازی بسیاری از پدیده‌های متنوع مانند دینامیک‌های مولکولی، هیدرودینامیک‌ها، مشخصه‌های فیزیکی مواد، فرایندهای شیمیایی واکنش انتشار (Reaction Diffusion)، رشد و ریخت‌زایی یک ارگان زنده، تعامل‌های اکولوژیکی و تکامل جمعیت، انتشار گره‌های ترافیکی، دینامیک‌های اقتصادی و اجتماعی و غیره مورد استفاده قرار می‌گیرد.

یکی دیگر از حوزه‌های کاربرد اتوماتای سلولی در علوم محاسباتی مانند پردازش تصویر، تولید اعداد تصادفی و کریپتوگرافی است.

عملکرد اتوماتای سلولی

از لحاظ ریاضی، اتوماتای سلولی به صورت یک سیستم دینامیکی توزیع فضایی در نظر گرفته می‌شوند که هم در زمان و هم در فضا به صورت گسسته هستند. یک مدل اتوماتای سلولی از اتوماتا (سلول یا مکان) یکتایی تشکیل شده است که به صورت یکنواخت روی نقاط یک توری در فضای گسسته D بعدی (D معمولا ۱ یا ۲ یا ۳ است.) توزیع شده‌اند. هر Automaton (جمع اتوماتا) یک متغیر دینامیک است و تغییرات زمانی آن با معادله زیر داده شده است :

st+1(x)=F(st(x+x0),st(x+x1),...,st(x+xn–1)),st+1(x)=F(st(x+x0),st(x+x1),...,st(x+xn–1)),

در رابطه فوق، st(x)st(x) حالت اتوماتای واقع در موقعیت x و در زمان t است. همچنین F برابر با تابع انتقال حالت و N=x0,x1,...,xn−1N=x0,x1,...,xn−1 همسایگی‌های سلول در نظر گرفته می‌شود. مهم‌ترین مشخصه و فرض در اتوماتای سلولی این است که یک تابع انتقال حالت و همسایگی یکسان به صورت یکنواخت به تمام موقعیت‌های فضایی اعمال می‌شود. زمانی که نیومان اولین بار این فریم ورک را برای مدل‌سازی سیستم‌ها ابداع کرد، محققان معمولا داده‌های صریح تجربی درباره این‌که چگونه اجزا در سیستم‌های پیچیده دنیای واقعی به یکدیگر متصل می‌شوند، در اختیار نداشتند.

بنابراین یک گام ابتدایی و منطقی این بود که  قواعد فضایی  (Spatial Regularity) و  همگنی  (Homogeneity) فرض شوند. البته این فرض‌ها بعدا در مدل‌های شبکه گسترش یافتند. stst یک تابع است که موقعیت‌های مکانی را به حالت‌ها نگاشت می‌کند. به این کار پیکربندی اتوماتای سلولی در زمان t می‌گویند. یک پیکربندی به صورت شهودی به معنی الگوهای فضایی است که اتوماتای سلولی در زمان معینی نمایش می‌دهند. در تصویر زیر یک نمایش شماتیک از نحوه کار اتوماتای سلولی نشان داده شده است.

شماتیک کار اتوماتای سلولی

همسایگی N همیشه به نحوی تنظیم می‌شود که حول سلول کانونی آپدیت شده (x0=0x0=0) متمرکز شود و محل قرارگیری فضایی آن به صورتی باشد که برای (i=1,2,...,n−1)(i=1,2,...,n−1) شرط |xi−x0|≤r|xi−x0|≤r صحیح باشد. در این رابطه بهr، شعاع N می‌گویند. به عبارت دیگر، حالت بعدی یک سلول به صورت محلی بر اساس حالت کنونی آن سلول و حالت کنونی سلول‌های همسایگی آن تعیین می‌شود. به یک چیدمان مشخص از حالت‌ها در یک همسایگی  موقعیت  (Situation) می‌گویند. در تصویر زیر مثال‌هایی متداول از همسایگی‌ها نشان داده شده است که معمولا برای اتوماتای سلولی دو بعدی مورد استفاده قرار می‌گیرد. تصویر زیر مربوط به همسایگی نیومان در اتوماتای سلولی است.

همسایگی نیومان در اتوماتای سلولی

در اتوماتای سلولی با همسایگی نیومان، که در تصویر بالا مشاهده می‌شود، هر سلول حالت خود را بر اساس حالت‌های سلول‌های همسایگی‌های بالا، پایین، چپ و راست و نیز خود سلول تغییر می‌دهد. اما در همسایگی مور (Moore Neighborhood) چهار سلول قطری نیز به همسایگی‌ها افزوده شده‌اند. تابع انتقال حالت به صورت یکنواخت و همزمان به تمام سلول‌های فضا اعمال می‌شود. تابع را می‌توان به شکل یک جدول جست‌و‌جو  (Look-up Table) یا فرمول‌های ریاضی و یا یک زبان الگوریتم سطح بالا توصیف کرد. تصویر زیر نیز نشان دهنده همسایگی مور در اتوماتای سلولی است.

همسایگی مور در اتوماتای سلولی

انواع تقارن در اتوماتای سلولی

اگر یک تابع انتقال حالت برای تمام موقعیت‌هایی که هنگام چرخش با یکدیگر مشابه هستند، همیشه یک حالت یکسان را تولید کند، آن‌گاه مدل اتوماتای سلولی دارای تقارن چرخشی (Rotational Symmetry) است. این چنین تقارنی همیشه در اتوماتای سلولی با هدف مدلسازی پدیده‌های فیزیکی مورد استفاده قرار می‌گیرد. یک تقارن چرخشی را قوی می‌گوییم، اگر تمام حالت‌های اتوماتای سلولی گرایش آزاد (Orientation Free) باشند و نیز اگر چرخش یک موقعیت شامل هیچ چرخشی در خود حالت‌ها نشود. مفهوم تقارن چرخشی قوی در اتوماتای سلولی در تصویر زیر نشان داده شده است.

تقارن چرخشی قوی در اتوماتای سلولی

در غیر این صورت به چرخش متقارن، ضعیف می‌گویند. در یک اتوماتای سلولی با تقارن چرخشی ضعیف، برخی از حالت‌ها جهت‌دار هستند و چرخش یک موقعیت، به تنظیمات چرخشی آن حالت‌ها نیز نیاز دارد. در مدل اتوماتای سلولی نیومان تقارن چرخشی ضعیف اتخاذ شده بود. تقارن چرخشی ضعیف در اتوماتای سلولی در تصویر زیر نشان داده شده است.

تقارن چرخشی ضعیف در اتوماتای سلولی

اگر یک تابع انتقال حالت فقط به مجموع حالت‌های سلول‌ها در همسایگی بستگی داشته باشد، آن‌گاه اتوماتای سلولی را جامع   (Totalistic) می‌گویند. بر اساس تعریف، چنین توابع انتقال حالتی متقارن چرخشی هم هستند. فرض جامع بودن، طراحی مدل‌های اتومات سلولی را بسیار ساده‌تر می‌کند، اما با این حال، هنوز هم می‌توانند گستره وسیعی از دینامیک‌های پیچیده را تولید کنند.

حالت‌ها و شرایط مرزی در اتوماتای سلولی

حالت‌ها در اتوماتای سلولی همیشه بر حسب خاموش  (Quiescent) و روشن (Non-Quiescent) طبقه بندی می‌شوند. یک سلول در حالت خاموش، در همان حالت خود باقی می‌ماند اگر تمام همسایه‌های آن نیز در همان حالت خاموش باشند. بسیاری از مدل‌های اتوماتای سلولی حداقل یک حالت خاموش دارند که با صفر یا  پوچن (Blank) نشان داده می‌شود. این نماد یک خلا در فضای اتوماتای سلولی را نشان می‌دهد.

حالت‌های روشن را گاهی حالت‌های فعال  (Active States) نیز می‌گویند؛ زیرا این حالت‌ها می‌توانند به صورت دینامیکی تغییر کنند و با حالت‌های نزدیک تعامل داشته باشند. این چنین حالت‌هایی در تولید رفتارهای پیچیده با اتوماتای سلولی نقش بسیار مهمی را ایفا می‌کنند. به دلیل اینکه مدل‌های اتوماتای سلولی دارای بسط فضایی همراه با بسط زمانی هستند، در نتیجه برای مطالعه رفتار آن‌ها نیاز است که شرایط مرزی فضایی را علاوه بر شرایط اولیه مشخص کرد. در حالت کلی چندین شرایط مرزی متداول وجود دارند که عبارتند از:

شرایط بدون مرز (NO BOUNDARIES) : این شرط فرض می‌کند که فضا بی‌نهایت باشد و کاملا با حالت‌های خاموش پر شده باشد.

شرایط مرزی متناوب (PERIODIC BOUNDARIES) : این شرط فرض می‌کند که فضا حول هر محور فضایی (Spatial Axis) پیچیده شده باشد. به عبارت دیگر، سلول‌ها در یک لبه از فضای متناهی، به سلول‌ها در لبه مخالف متصل هستند.

شرایط مرزی قطع (CUT-OFF BOUNDARIES) : این شرط فرض می‌کند که سلول‌ها در لبه یک فضای متناهی، هیچ همسایگی فراتر از مرزها ندارند. این شرط اجبارا منجر به تعداد همسایگی‌های کمتر می‌شود. همچنین نکته دیگری که در این شرایط باید به آن توجه کرد این است که تابع انتقال حالت باید به صورتی طراحی شود که بتواند این موارد را مدیریت کند.

شرایط مرزی ثابت (FIXED BOUNDARIES) : این شرط فرض می‌کند که سلول‌ها در لبه یک فضای متناهی حالت‌های ثابتی داشته باشند که هیچ وقت تغییر نکند. معمولا این شرایط آسان‌ترین انتخاب است، مخصوصا زمانی که در حال پیاده‌سازی یک کد شبیه‌سازی از یک مدل اتوماتای سلولی باشید.