پروژه آتاماتون سلولی ، آتاماتون یادگیر ، و کاربرد آن ها

پروژه کارشناسی کامپیوتر

فصل اول

مقدمه 

-1-مقدمه

بدون  شک گسترش روز افزون علم چه در تئوری و چه در کاربرد، انسانها را موظف کرده زمینه های مختلف علوم را چه در سطح و چه در عمق گسترش دهند. در مورد آتاماتون سلولی و نیز آتاماتون یادگیر و کاربردهای آنها در متون آکادمیک سخن بسیار گفته شده و در این مجموعه ناچیز سعی شده با معرفی آنها و چند نمونه از کاربردهایشان، کلید ورود به این زمینه بی انتها بدست آورده شود. آتاماتون سلولی مدلی است گسسته که در تئوری شمارش پذیری، ریاضیات و علوم نظری کاربردهای زیادی دارد. شاید در سال 1940 که STANISLAW ULAM در حال تحقیق در ازمایشگاه ملی LOS ALAMOS بود هرگز تصور نمی کرد که روزگاری، مطالعه او روی شبکه هایی منظم با  عناصری تاثیر پذیر از یکدیگر تا حد بی حد گسترش یابد. چنانچه از این مباحث بگذریم، نخستین چیزی که چارچوب آتاماتون سلولی را شکل میدهد عناصری سلولی شکل هستند که رفتار هر یک از این سلولها متاثر از وضعیت فعلی خود و همسایگانش می باشد. اتاماتون سلولی میتوان چندین بعد داشته باشد و هر سلول می تواند پذیرای چندین حالت باشد. در فصل 2 این مجموعه سعی شده ضمن تعریف آتاماتون سلولی تعدادی اندک از انواع آنها و نیز کاربردهایشان ذکر شود.

در فصل 3 نیز سعی شده ضمن تعریف آتاماتون یادگیر، چند نوع از آنها ونیز نمونه هایی از یکی از انواع ان معرفی شود. در واقع اتاماتون یادگیر یک ماشین حالتی است که برای حل مسائل پیچیده و بهینه سازی و کنترل کردن مسائل قطعی، تصادفی و یاسیستمهای نا مشخص بکار می رود. برای یادگیری آتاماتون محیط نقش اساسی در پاسخ دهی و مطلع کردن آتاماتون دارد. در فصل 4 مدل مخفی مارکوف به تفصیل مورد بررسی قرار گرفته است. دلیل این امر شباهت بسیار بین مدل مخفی مارکوف و آتاماتون سلولی می باشد.

در فصل پنجم در مورد کاربرد آتاماتون یادگیر در تناظر گرافها سخن گفته شده است. اهمیت این کاربرد هنگامی بر ما مشخص می شود که بدانیم طبق روشهای کلاسیک BACK TRACKING ، تعیین تناظر بین دو گراف دارای پیچیدگی زمانی O(n!) خواهد بود!  و در نهایت در فصل ششم، 10 برنامه کاربردی که آتاماتونهای سلولی مختلفی راشبیه سازی کرده اند به همراه کد منبعشان معرفی شده اند تا ضمن درک بهتر آتاماتون سلولی و نحوه عمل ان بتوان از نمونه کوچکی از کاربردهای آن آگاه شد. در نهایت و در ضمیمه، اصل منابع اینترنتی این مجموع آورده شده است. تا چنانچه با گذر زمان آدرس آنها تغییر کند، بتوان برای یافتن مطالبی بیشتر به این مراجع دسترسی داشت. لازم به ذکر است در این مجموعه در موقعیتهایی به این منابع ارجاع شده که مطالب تنها جنبه تعریفی داشته و این تعریفها بین مراجع مختلف استاندارد می باشند . انتخاب این منابع از سایتهای اینترنتی تنها به دلیل جمع و جور  بودن و نیز نگارش ساده و در عین حال مختصر و مفید آنها می باشد.

فصل دوم

آتاماتون سلولی

2-1- مقدمه*

آتاماتون سلولی مدلی است گسسته که در تئوری شمارش پذیری ، ریاضیات و علوم نظری کاربردهای زیادی دارد. درواقع آتاماتون سلولی شامل تعدادی نامتناهی از سلولهای منظم و توری شکل می باشد که هر یک از سلولها می توانند تعداد محدودی از مقادیر را بپذیرند. توری مورد نظر می تواند چند بعدی نیز باشد. زمان هم متغیری گسسته به شمار می آید و وضعیت هر سلول در لحظه t ام تابعی است از وضعیت تعدادی از سلولهای دیگر (که همسایه آن سلول نامیده می شوند) در لحظه (t-1) ام . در واقع همسایگان هر سلول مجموعه ای از سلولهای وابسته به آن سلول بوده و تغییر نخواهند کرد. سلولها برای بروز شدن قوانین یکسانی دارند که این قوانین روی مقادیر همسایه هر سلول عمل می کنند. در هر لظحه که قوانین برای کل شبکه بکار می روند محصول جدیدی تولید خواهد شد. یک مثال از آتاماتون سلولی می تواند صفحه شطرنجی شکلی باشد که هر مربع یک سلول بوده و هر سلول دو حالتی است (که می تواند سیاه یا سفید باشد)، و همسایگان هر سلول هشت مربعی هستند که آنرا احاطه کرده اند. بنابراین 512 =9 2 الگوی ممکن برای هر سلول و همسایگانش می تواند وجود داشته باشد.

قانون بکار رفته برای آتاماتون سلولی نیز میتواند بصورت جدولی باشد. این مثال، مثالی از آتاماتون سلولی دو بعدی بود.

( تصاویر در فایل اصلی قابل مشاهده است )

آتاماتون های سلولی اغلب بصورت متناهی شبیه سازی می شوند و نه بصورت نامتناهی مثلاً در مثال قبلی و در آتاماتون سلولی دو بعدی صفحه اصلی مستطیل شکل و متناهی می باشد. بنابراین این سئوال پیش خواهد آمد: سلولهایی که در لبه ها قرار دارند چگونه پردازش شوند؟

یکی از روشهای ممکن برای حل این مساله این است که سلولهای غیر موجود در همسایه آن را ثابت در نظر بگیریم . راه حل دیگر این است که همسایگان این سلولها متفاوت از همسایگان سلولهای دیگر در نظر گرفته شوند. در این حالت این شبکه به صورت حلقوی در نظر گرفته می شود که در شکل 2-1 نمونه آن دیده می شود. این عمل برای حل مشکل مسأله مرزی همسایگان صورت می گیرد.

2-2- تاریخچه آتاماتون سلولی

تاریخچه آتاماتون سلولی برای اولین باربه Stanislaw ulamبرمی گردد.  وی در سال 1940 در آزمیشگاه ملی los Alamos در حال مطالعه گروهی از کریستال هایی بود که به شکل شبکه توری منظم بودند و در همان زمان John von Neumann که همکار ulam بود در همان آزمایشگاه مشغول کار کردن روی مسأله سیستم های خود تکراری بود . او می خواست روبوتی بسازد که بتواند تولید مثل کند. سپس ulam پیشنهاد کرد با هم همکاری کرده و تمرکز خود را به سمت ریاضیات سوق دهند. به این ترتیب اولین نسل آتاماتون سلولی بنا شد. در سال 1970 آتاماتونی سلولی، دو حالتی و دو بعدی بنام Geame of life بسیار مشهور شد. مخترع این سیستم John Conway بود اما محبوب شدن آنرا به Martin Gardner نسبت می دهند. در سال 1969 ، konrad zuse در کتابی به نام فضای محاسباتی، پیشنهاد تطبیق قوانین فیزیکی طبیعی را با آتاماتون سلول مطرح کرد.

در سال 1983، Stephen wolfram نخستین مجموعه از مقالات خود را بستن بر کلاسهایی ناشناخته و اساسی آتاماتون سلولی به ثبت رسانید.

او در سال 2002، نتایج مطالعات چندین ساله خود را در 1280 صفحه تحت عنوان نوع جدیدی از علم چاپ نمود.

2-3- ساده ترین آتاماتون سلولی

ساده ترین آتاماتون سلولی باید یک بعدی بوده و علاوه بر آن هر سلول باید تنها دو حالت را پذیرا باشد. ضمن آنکه سلولهای همسایه هر سلول را باید دو سلول همسایه آن تعریف کنیم. بنابراین میتوان نتیجه گرفت هر سلول و دو همسایه آن می توانند 23=8 امکان برای الگوی کار،  پذیرا باشند و این یعنی 28=256 قانون می تواند تعریف شود. این 256 آتاماتون سلولی عموماً از نامهای استاندارد متعارفی استفاده
می کنند که نخستین بار توسط wolfram معرفی شده اند. نام یک آتاماتون سلولی یک عدد دهدهی است که شکل دودویی آن نمایانگر قانون مورد نظر در جدول قوانین می باشد، با هشت همسایه ممکن که بطورمعکوس در جدول لیست شده اند. مثلاً همانطور که در شکلهای 2-2 و 2-3 نشان داده شده است دو جدول، قوانین 30 و نیز 110 را معرفی کرده اند. شکل گرافیکی نیز از مرکز هر تصویر و با شماره1 آغاز شده است.

هر جدول بطور کامل قانون آتاماتون سلولی را مشخص می کند. مثلاً قانون 30 در جدول می گوید اگر سه همسایه سلول در آتاماتون سلولی الگوی 100 را داشته باشند سپس سلول مرکزی یک خواهد بود (البته در قدم بعدی) و نیز قانون 110 آتاماتون سلولی خلاف این را می گوید.

2-4- آتاماتون سلولی معکوس پذیر

یک آتاماتون سلولی را معکوس پذیر گویند هر گاه هر پیکربندی جاری آتاماتون سلولی بتواند پیکربندی قبلی را نشان دهد. اگر هر آتاماتون سلولی بتواند بطور معکوس عمل نگاشت پیکربندی به پیکربندی را انجام دهد، تابع عملگر را bijective می نامند.

مثلاً برای آتاماتون سلولی یک بعدی الگوریتمهایی برای یافتن تصاویر قبلی وجود دارد و هر قانون یک بعدی می تواند معکوس پذیر یا معکوس ناپذیر باشد.

آتاماتون سلولی معکوس پذیر می تواند در شبیه سازی گاز و سیالات دینامیک، در علم ترمودینامیک کاربرد گسترده ای داشته باشد.

برای آتاماتونهای سلولی متناهی که معکوس پذیر نباشند ، قطعاً الگوهای آنها قادر به شناسایی وضعیتهای قبلی نیستند. تکنیکهای زیادی برای ساخت آتاماتونهای سلولی معکوس پذیر وجود دارد که دو تا از معروف ترین آنها عبارتند از تکنیک second order و تکنیک partitioning ، که هر دوی آنها شامل راههایی برای اصلاح آتاماتون سلولی می باشند. اگر چه که این آتاماتونها تعریف اصلی مورد نظر ما را ارضاء نمی کنند اما می توانند با آتاماتونهای متعارف (که دارای همسایه ها و حالتهای مختلف می باشند) به خوبی رقابت کرده و در نتیجه در زیر مجموعه آتاماتونهای سلولی متعارف قرار بگیرند.

2-5- آتاماتون سلولی Totalistic

آتاماتونهای سلولی Totalistic کلاس خاصی از آتاماتونهای سلولی به شمار می روند . در این نوع آتاماتون وضعیت هر سلول با یک عدد بازنمایی می شود و مقدار هر سلول در لحظه t بستگی دارد به مجموع مقادیر همسایه ها در لحظه (t-1) . اگر وضعیت سلولها در زمان t به مقدار همان سلول در لحظه (t-1) وابسته باشد سپس، آتاماتون مورد نظر outer toralistic نامیده می شود. مسأله Game of life مربوط به Conway مثالی است از آتاماتون سلولی outer totalistic با مقادیر سلولی O و I.

2-6- استفاده از آتاماتون سلولی در علوم پنهان شناسی

قانون شماره 30 یک قانون پیشنهادی برای امکان جریان محاسباتی در علوم پنهان شناسی مطرح می باشد.

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

2-7- آتاماتونهای وابسته

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

علاوه بر موارد فوق ممکن است همسایه ها و یا قوانین در طی بازه های زمانی تغییر یابند. مثلا ممکن است در یک مرحله سلولهای افقی بعنوان همسایه در نظر گرفته شود اما در مرحله بعد، همسایه سلول، سلولهای عمودی باشند.

در اینجا لازم به ذکر است که در آتاماتون سلولی وضعیت جدید هر سلول از وضعیت جدید سلولهای همسایه تأثیر نمی پذیرد و این وضعیتهای قبلی همسایه ها هستند که وضعیت جدید هر سلول را مشخص می کنند.

علاوه بر آتاماتونهای گسسته که به تفصیل در مورد آنها بحث شد میتوان آتاماتون پیوسته را نیز تعریف کرد. این آتاماتونها مشابه آتاماتون سلولی totalistic می باشند، با این تفاوت که قوانین پیوسته بوده و وضعتهای ممکن نیز پیوسته می باشند (مثلاً در بازه [0,1] ).

علاوه بر این میتوان نوع دیگری از آتاماتون سلولی پیوسته را نیز تعریف کرده که وضعیت هر سلول میتواند تعدادی متناهی از اعداد واقعی باشد و زمان متغیری پیوسته بوده و وضعیت هر سلول وابسته به معادلاتی متفاوت باشد.

در صورتیکه این تقریبها با آتاماتون سلولی به وجود آیند، می توان آتاماتون سلولی را یک الگوی موثر نام برد.

2-8- آتاماتون سلولی در طبیعت

میتوان ادعا کرد الگوهای مشخص و زیبای بکار رفته در صدفهای حلزونی شکل دریایی ، نمونه ای از آتاماتون سلولی در طبیعت می باشد. همانطور که در شکل 2-4 دیده می شود رنگدانه های سلولهای مستقر در نوار باریک لبه صدف نمونه ای طبیعی از آتاماتون سلولی می باشد.

در واقع در این نوع صدف هر سلول رنگدانه هایی را بر اساس تابعی از سلولهای فعال و سلولهای بازدارنده همسایه خود تراوش می کند. (همانند یک نسخه طبیعی از قوانین ریاضیات!!)

در واقع همگام با رشد این موجود دریایی الگوی رنگی و نواری لبه صدف تغییر می نماید . مشابه با همین وضعیت گیاهان نیز در جذب و دفع گازهای طبیعی الگویی مشابه آتاماتون سلولی بکار می برند.

2-9- خلاصه

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