اتوماتای سلولی چیست؟ – راهنمای جامع

«اتوماتا» (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 معمولا ۱ یا ۲ یا ۳ است.) توزیع شده‌اند.

فیلم آموزش شبکه های پیچیده پویا Complex Dynamical Networks در فرادرس

کلیک کنید

هر Automaton (جمع اتوماتا) یک متغیر دینامیک است و تغییرات زمانی آن با معادله زیر داده شده است:

$$s _ { t + 1 } ( x ) = F ( s _ { t } ( x + x _ { 0 } ) , s _ { t } ( x + x _ { 1 } ) , .. . , s _ { t } (x + x _ { n - 1 } ) ), \label { ( 1 1 . 1 ) }$$

در رابطه فوق، $$s _ { t } ( x )$$ حالت اتوماتای واقع در موقعیت x و در زمان t است. همچنین F برابر با تابع انتقال حالت و $$N = { x _ 0 , x _ 1 , . . . , x _ { n − 1 } }$$ همسایگی‌های سلول در نظر گرفته می‌شود. مهم‌ترین مشخصه و فرض در اتوماتای سلولی این است که یک تابع انتقال حالت و همسایگی یکسان به صورت یکنواخت به تمام موقعیت‌های فضایی اعمال می‌شود. زمانی که نیومان اولین بار این فریم ورک را برای مدلسازی سیستم‌ها ابداع کرد، محققان معمولا داده‌های صریح تجربی درباره اینکه چگونه اجزا در سیستم‌های پیچیده دنیای واقعی به یکدیگر متصل می‌شوند، در اختیار نداشتند.

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

همسایگی N همیشه به نحوی تنظیم می‌شود که حول سلول کانونی آپدیت شده ($$x _ 0 = 0$$) متمرکز شود و محل قرارگیری فضایی آن به صورتی باشد که برای $$( i = 1 , 2 , . . . , n − 1 )$$ شرط $$| x _ i − x _ 0 | ≤ 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): این شرط فرض می‌کند که سلول‌ها در لبه یک فضای متناهی حالت‌های ثابتی داشته باشند که هیچ وقت تغییر نکند. معمولا این شرایط آسان‌ترین انتخاب است، مخصوصا زمانی که در حال پیاده‌سازی یک کد شبیه‌سازی از یک مدل اتوماتای سلولی باشید.

تمرین ۱: اتوماتای سلولی یک بعدی

در تصویر زیر نمایی از یک اتوماتای سلولی یک بعدی نشان داده شده است. این مدل اتوماتای سلولی از نوع متقارن چرخشی جامع با شعاع یک محسوب می‌شود که شرایط مرزی پریودیک دارد. در این تصویر، رنگ سفید به معنی صفر و رنگ خاکستری به معنی عدد یک در نظر گرفته می‌شود. هر سلول در هر گام زمانی به $$round(S/3)$$ (گرد کردن حاصل تقسیم S بر عدد سه) تغییر می‌یابد. در این رابطه، S برابر با جمع محلی حالت‌ها در همسایگی‌های آن است. به عنوان تمرین می‌توانید تکامل زمانی اتوماتای سلولی زیر را به دست آورید.

تمرین ۲: اتوماتای سلولی دو بعدی

در تصویر زیر نمونه‌ای از یک مدل اتوماتای سلولی دو بعدی نشان داده شده است. این مدل اتوماتای سلولی جامع و با همسایگی نیومان با شریط بدون مرز (فضای بی‌نهایت) در نظر گرفته شده است. رنگ سفید نشان دهنده صفر یا حالت خاموش و رنگ خاکستری نشان دهنده یک یا حالت روشن است. هر سلول در هر مرحله زمانی بر اساس $$round(S/5)$$ تغییر می‌یابد. در این رابطه S برابر با مجموع محلی حالت‌ها در هر همسایگی است. در این مدل اتوماتای سلولی، تکامل زمانی مربوطه را محاسبه کنید.

خلاصه

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

یک اتوماتای سلولی شامل یک شبکه منظم از سلول‌ها است که هر کدام از آن‌ها در یکی از حالت‌های مجموعه حالات متناهی امکان‌پذیر مانند On و Off، قرار دارند. شبکه می‌تواند هر بعد متناهی داشته باشد. برای هر سلول، یک مجموعه از سلول‌ها که همسایهٔ آن نامیده می‌شود، نسبت به آن سلول مشخص تعریف شده‌ است. یک حالت آغازین (زمان t = ۰) با تخصیص دادن یک وضعیت به هر سلول انتخاب می‌شود.

یک نسل جدید یا تکامل (توسعه t به وسیله ۱)، بر اساس یکسری قوانین ثابت (عموماً یک تابع ریاضی) تولید می‌شود که وضعیت جدید برای هر سلول را بر اساس وضعیت جاری آن سلول و وضعیت‌های سلول‌های همسایه آن مشخص می‌کند. به‌ صورت معمول، قوانین به روزرسانی وضعیت سلول‌ها برای هر سلول مشابه است و در طول زمان تغییر نمی‌کند و به کل شبکه به صورت همزمان اعمال خواهد شد. البته استثناهایی مانند اتوماتای سلولی تصادفی و اتوماتای سلولی ناهمگام نیز وجود دارند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌های دروس علوم و مهندسی کامپیوتر
• آموزش شبکه های پیچیده پویا (Complex Dynamical Networks)
• مجموعه آموزش‌‌های مهندسی مخابرات
• آموزش تئوری کدینگ
• الگوریتم هافمن (Huffman Coding) — به زبان ساده
• کدگذاری هافمن (Huffman Coding) برای ورودی های مرتب — راهنمای
• مخابرات دیجیتال چیست؟ — از صفر تا صد

^^