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

۱۲۰۰ بازدید
آخرین به‌روزرسانی: ۲۴ اردیبهشت ۱۴۰۲
زمان مطالعه: ۸ دقیقه
اتوماتای سلولی چیست؟ — راهنمای جامع

«اتوماتا» (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 (جمع اتوماتا) یک متغیر دینامیک است و تغییرات زمانی آن با معادله زیر داده شده است:

$$ 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 به وسیله ۱)، بر اساس یکسری قوانین ثابت (عموماً یک تابع ریاضی) تولید می‌شود که وضعیت جدید برای هر سلول را بر اساس وضعیت جاری آن سلول و وضعیت‌های سلول‌های همسایه آن مشخص می‌کند. به‌ صورت معمول، قوانین به روزرسانی وضعیت سلول‌ها برای هر سلول مشابه است و در طول زمان تغییر نمی‌کند و به کل شبکه به صورت همزمان اعمال خواهد شد. البته استثناهایی مانند اتوماتای سلولی تصادفی و اتوماتای سلولی ناهمگام نیز وجود دارند.

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

^^

بر اساس رای ۷ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
libretexts
۱ دیدگاه برای «اتوماتای سلولی چیست؟ — راهنمای جامع»

این حیطه از علوم کامپیوتر در ایران بسیار ناشناخته مونده و من تقریبا در این حوزه ندیدم کاری انجام شده باشه در حالی که به سرعت در حال رشد در تمام ابعاد حتی در شیمی و زیست شناسی هست بنابراین پیشنهاد می کنم در این خصوص دوره ای ترتیب بدید البته مخاطبانی احتمالا از ده نفر در ابتدا تجاوز نکنه ولی به سرعت فراگیر خواهد شد

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *