آتوماتای سلولی و یادگیر سلولی
درس یادگیری ماشین
مقدمه
آتوماتای سلولی در واقع یک مدل گسسته ریاضی است که در زمینه های مختلفی همچون تئوری محاسبات، ریاضیات، فیزیک و … کاربرد دارد.
آتوماتای سلولی در اواخر دهه 1940 توسط John von Neumann مطرح و پس از او توسط ریاضیدانی بنام Ulam به عنوان مدلی برای بررسی رفتار سیستم های پیچیده پیشنهاد شد.
نامهای دیگر آتوماتای سلولی عبارتند از:
cellular structures
homogeneous structures
tessellation structure
iterative arrays
؟CA چرا
شبیه سازی سیستم های پیچیده نیازمند معادلات پیچیده می باشد.
ارائه معادلات پیچیده نیازمند شناخت قوانین و وجود دانش کامل در مورد سیستم مورد بررسی است.
از معادلات پیچیده برای توصیف یک سیستم پیچیده استفاده نکنید و بجای آن اجازه دهید این پیچیدگی در قالب تعامل بین قوانین ساده بررسی گردد.
ایده : استفاده از تعاملات ساده بین سلولها در آتوماتای سلولی برای شبیه سازی سیستمهای پیچیده
مفاهیم اساسی در یک آتوماتای سلولی
سلول
حالت
شبکه
تغییر و تحول (گسسته از لحاظ زمانی)
همسایگی
قوانین تغییر حالت
وضعیت اولیه
سلول
اصلی ترین مولفه آتوماتای سلولی
سلولها را می توان بعنوان حافظه هایی که وضعیت را ذخیره می کنند در نظر گرفت.
معمولا حالت سلولها بطور همزمان بر اساس قوانین انتقال بروز رسانی می گردد.
حالت
حالات می توانند وضعیت، عدد، رنگ و … باشند.
تعداد حالاتی که یک سلول می تواند داشته باشد متناهی است.
on
off
1
2
3
شبکه
آتوماتای سلولی شامل شبکه ای از سلولها است.
ابعاد شبکه یک مقدار متناهی است (یک بعدی، دو بعدی، سه بعدی و …)
یک بعدی
دو بعدی
سه بعدی
نمای واقعی یک شبکه دو بعدی
همسایگی
کول
همسایه های یک سلول در آتوماتای سلولی بسته به کاربرد سلولهای مختلفی از سلولهای مجاور می باشند.
قوانین تغییر حالت
در آتوماتای سلولی زمان گسسته است و در هر مرحله هر سلول، وضعیت جدید خود را با در نظر گرفتن حالت همسایه های مجاور خود بر اساس یکسری از قوانین بدست می آورد.
قانونها به سه دسته قابل تقسیم می باشند:
1-قانون عمومی: در این قانون مقدار یک سلول در مرحله بعدی، به مقدار تک تک سلولهای همسایه در حالت فعلی وابسته است.
2- قانون totalistic: در این قانون مقدار یک سلول در مرحله بعدی، به تعداد سلولهای همسایه که در حالتهای مختلف می باشند، وابسته است. در این نوع قانون برخلاف قانون عمومی، توجه ای به تک تک سلولها نمی شود.
3- قانون outer totalistic: تنها تفاوتی که این قانون با totalistic دارد در این است که در تعیین حالت بعدی سلول، حالت فعلی نیز موثر است.
قوانین انتقال
مثال: آتوماتای سلولی ابتدائی (یک بعدی)
در این آتوماتا هر سلول دارای دو حالت صفر یا یک می باشد.
همسایه های هر سلول دو سلول کناری آن می باشند.
هر سلول بهمراه دو همسایه کناری آن می توانند هشت مقدار مختلف داشته باشند.
هر سلول با توجه به وضعیت فعلی خود و دو همسایه اش یکی از حالات زیر را خواهد داشت:
مثال: آتوماتای سلولی ابتدائی (یک بعدی)
هر سلول در مرحله بعد می تواند دارای یکی از دو حالت صفر یا یک باشد.
به ازای هشت نوع همسایگی مختلف ما 256 نوع آتوماتای سلولی یک بعدی می توانیم داشته باشیم.
هر کدام از این آتوماتاها دارای قانون خاص خود می باشند.
شماره گذاری قانونها بسته به وضعیتی که در حالات مختلف سلول خواهد داشت انجام می شود. برای مثال قانون زیر به قانون 30 معروف است.
قانون 30
ارائه یک طراحی
هر سلول دارای یکی از چهار حالت زیر می باشد:
حالت Blank
حالت Copper
حالت Head
حالت Tail
Blank
Copper
Head
Tail
قوانین
قوانین بصورت زیر هستند:
یک سلول در حالت Blank همواره در همان حالت باقی می ماند.
حالت بعدی یک سلول که دارای حالت head است، tail می باشد.
حالت بعدی یک سلول که دارای حالت tail است، Copper می باشد.
سلول دارای حالت Copper در همان حال باقی می ماند مگر اینکه یک یا دو همسایه آن در حالت head باشند. در اینصورت حالت آن به head تغییر خواهد کرد.
هر الگو یا قالب معینی را می توان در شبکه سلولی در نظر گرفت و تکامل آنرا با استفاده از قانون های ذکر شده مشاهده نمود.
ارائه الگوهای مناسب
در یک شبکه دو بعدی الگویی را در نظر بگیرید که در آن سلولهای تمام ردیف ها باستثناء یک ردیف در حالت Blank می باشند.
در ردیف مذکور نیز تنها دو سلول مجاور یکی دارای حالت tail و دیگری head میباشد.
بقیه سلولهای ردیف ذکر شده دارای حالت Copper هستند.
گذرگاه سیگنال
یک جفت head-tail را یک الکترون می نامیم.
الکترون در طول مداری که از طریق سلولهای Copper ایجاد گردیده حرکت می کند.
برای انتقال داده از این طریق بروش زیر عمل می کنیم:
مدار را به قسمتهای مساوی به اندازه n تقسیم می کنیم.
اندازه n باید بزرگتر از 2 باشد تا یک الکترون در آن بتواند قرار گیرد.
وجود یک الکترون در یک قسمت بمعنای مقدار یک و عدم وجود آن بمعنای مقدار صفر است.
وجود یک سلول در حالت copper در هر قسمت لازم است لذا n بایستی حداقل سه باشد.
انشعاب گذرگاهها
شبیه سازی دیود
گیت OR
The ROM
با تکرار نوع دوم AND-NOT می توان الگویی ایجاد کرد که یک ROM شکل بگیرد.
هر گیت صفر یا یک را در خود ذخیره میکند.
ذخیره عدد یک: گیت مربوطه ear در قسمت بالا سمت راست ندارد.
ذخیره عدد صفر: گیت مربوطه ear در قسمت بالا سمت راست دارد.
The ROM
flip-flop
فیلپ فلاپ دارای دو حالت set و unset می باشد.
وقتی فیلپ فلاپ در حالت set باشد، در خروجی جریانی از یک ها را تولید خواهد کرد.
ورودی بالا فیلپ فلاپ را reset می کند و خروجی پایین آنرا set می کند.
جمع کننده باینری
در جمع کننده مذکور اعداد در قالب باینری نشان داده می شوند.
بیت ها بصورت سریالی از ورودی ها وارد شده و حاصل جمع آنها در خروجی نیز بصورت سریالی (در قالب باینری) خواهد بود.
نمایش اعداد بصورت ابتدا بیت دارای ارزش کمتر می باشد.
مدار جمع کننده ترکیبی از گیتهای XOR ، AND-NOT ، فیلپ فلاپ و … می باشد.
جمع 011 و 110 (اعداد 3 و 6)
خروجی حاصل از جمع این دو عدد 48 نسل بعد در خروجی خواهد بود.
مجموعه رجیسترها
قابلیتها و نقصهای اتوماتای سلولی
CA مدلی است که از یکسری اجزاء مشابه و ساده تشکیل شده است که قوانین بسیار ساده محلی نیز بر آنها حاکم است. اما در نهایت می تواند سیستمهای پیچیده ای را مدل کند.
یک اشکال عمده CA تعیین فرم قطعی قوانین مورد نیاز برای یک کاربرد خاص است و اینکه CA برای مدل کردن سیستمهای قطعی مناسب می باشد.
پس باید به دنبال روشی باشیم که بدون نیاز به تعیین فرم قطعی قوانین، با گذشت زمان قوانین مناسب استخراج شوند.
هوشمند کردن سلولهای CA و افزودن قابلیت یادگیری به آنها یکی از این روشهاست!
مشکلات اتوماتای سلولی
تعیین فرم قطعی قوانین مورد نیاز برای یک کاربرد خاص
کارا نبودن در مدل سازی سیستم های نویزی و دارای عدم قطعیت
مشکل اتوماتای یادگیر
سادگی بیش از حد به تنهائی قادر به حل بسیاری از مسائل پیچیده نمی باشد
ایده ی اصلی اتوماتای یادگیر سلولی استفاده از عمل انتخاب شده توسط اتوماتای یادگیر به عنوان حالت سلول در اتوماتای سلولی می باشد
ایده ی اولیه
2
LA
CA
یادگیری عمل بهینه بر مبنای پاداش و جریمه
محیط سلولی
همسایگی
قوانین محلی
CLA
معرفی غیرفرمال
اتوماتای یادگیر سلولی
اتوماتای سلولی
یک یا چند اتوماتای یادگیر در هر سلول
حالت بعدی هر سلول بر اساس حالت فعلی سلول و سلول های همسایه تعیین می شود
قانون محلی تعیین می کند که عمل انتخاب شده توسط اتوماتای یادگیر در هر سلول باید پاداش داده شود و یا جریمه شود
3
نحوه ی عملکرد
در هر گام، اتوماتای یادگیر هر سلول یکی از عملهای خود را به صورت تصادفی و بر اساس بردار احتمال عملها انتخاب می کند
قانون محلی حاکم در هر سلول بر اساس عمل انتخابی اتوماتا و عمل انتخابی اتوماتونهای سلول های همسایه، سیگنال تقویتی تولید می کند
سیگنال تقویتی باعث پاداش یا جریمه ی عمل انتخابی هر سلول می شود
گام های فوق تا زمان رسیدن به وضعیت نهائی تکرار می شوند
معرفی فرمال
5
اتوماتای یادگیر سلولی به صورت 5 تائی تعریف میشود
چند مثال
پردازش تصاویر
تصویر: یک توری دو بعدی از نقاط
نگاشت اتوماتای یادگیر سلولی به تصویر
هر نقطه: یک سلول
همسایگی سلولها: وابسته به کاربرد
هر سلول: یک اتوماتای یادگیر
عملهای هر اتوماتای یادگیر: وابسته به کاربرد
قطعهبندی تصاویر
تعیین کلاس هر نقطه از تصویر
قانون محلی: وابسته به کاربرد
مشابهت کلاس تعیین شده با کلاس سلولهای همسایه و نیز سطوح خاکستری
6
حذف نویز
چند مثال
تخصیص کانال در شبکههای موبایل سلولی
هر سلول شبکه: یک سلول از اتوماتای یادگیر سلولی
همسایگی: هر دو سلول همسایه در شبکه
هر سلول: یک یا تعدادی اتوماتای یادگیر
عملهای هر اتوماتای یادگیر
تعیین کانال آزاد سلول
مورد استفاده بودن یا نبودن کانال مربوطه
قانون محلی: همسان نبودن کانالهای انتخاب شده در سلولهای همسایه
7
مساله غذا خوردن فیلسوفان
بررسی رفتاری اتوماتای یادگیر سلولی
اتوماتای یادگیر سلولی
تک بعدی با سه سلول
هر سلول دارای دو عمل (0 یا 1)
نحوه ی نمایش
قانون ها همانند اتوماتای سلولی به فرم ولفرام نمایش داده می شوند
رفتار اتوماتای یادگیر سلولی بر حسب نوع قوانین به 3 کلاس تقسیم بندی می شود
همگرا شونده
پریودیک
نامنظم
9
قانون 54
کلاس همگرا شونده (کلاس 1)
این کلاس به 4 زیرگروه تقسیم می شود
بررسی رفتاری اتوماتای یادگیر سلولی
10
در گروه 1 از این کلاس اتوماتای یادگیر سلولی به سادگی و با پیمودن مسیری تقریبا مستقیم به سمت پیکربندی نهایی خود حرکت می کند و در نهایت در این پیکربندی متوقف می شود
در گروه 2 مسیر پیموده شده در فضای پیکربندی اتوماتای یادگیر سلولی به دو زیر مسیر قابل تقسیم است. زیر مسیر اول از پیکربندی شروع تا یک پیکربندی میانی است که در طول آن اتوماتای یادگیر سلولی مسیر ساده و تقریباً مستقیمی را طی می کند و در قسمت دوم رفتار پیچیده ای در فضای پیکربندی نشان می دهد
در گروه 3 بر خلاف گروه 2، اتوماتای یادگیر سلولی در زیر مسیر اول رفتار پیچیده ای از خود نشان می دهد و سپس در زیر مسیر بعدی به سادگی مسیر نسبتاً مستقیمی را تا پیکربندی نهایی طی می کند
در گروه 4 بر خلاف گروه های 1، 2 و3، اتوماتای یادگیر سلولی در تمام مسیر خود رفتار پیچیده ای از خود نشان می دهد و پس از پیمودن یک مسیر پیچیده سرانجام در پیکربندی نهایی متوقف می شود
کلاس پریودیک (کلاس 2)
در این کلاس تکامل اتوماتای یادگیر سلولی به نحوی صورت می پذیرد که پس از گذر از یک مرحله ی گذرا وارد مرحله ای می شود که در یک زیر فضای محدود به صورت متناوب نوسان کند
بررسی رفتاری اتوماتای یادگیر سلولی
11
کلاس نامنظم (کلاس 3)
در این کلاس هیچ رفتار منظمی در تکامل اتوماتای یادگیر سلولی مشاهده نمی شود. به عبارت دیگر اتوماتای یادگیر سلولی همگرا نمی شود و در عین حال رفتار پریودیک نیز از خود نشان نمی دهد
بررسی رفتاری اتوماتای یادگیر سلولی
12
معیارهای ارزیابی رفتار
آنتروپی
13
معرفی شده توسط Shannonدر سال 1948
معیار عدم قطعیت یک متغیر تصادفی
ویژگیهائی که یک معیار عدم قطعیت باید داشته باشد
پیوستگی
اگر احتمال تمامی حالتهای متغیر تصادفی یکسان باشد، میزان عدم قطعیت باید تابعی صعودی از تعداد حالتها باشد
اگر برخی از حالتها، زیر مجموعه یک حالت کلیتر شوند، میزان عدم قطعیت اولیه باید برابر با مجموع وزندار میزان عدم قطعیتهای جدید باشد
Shannon نشان داد که تنها تابعی که میتواند سه ویژگی فوق را همزمان داشته باشد، تابع آنتروپی است و عبارت است از:
عمل انتخاب شده توسط یک اتوماتای یادگیر، یک متغیر تصادفی است
مفهوم آنتروپی برای تعیین میزان عدم قطعیت یک اتوماتای یادگیر میتواند به کار رود
بردار احتمال عملهای یک اتوماتای یادگیر، وابسته به زمان است
آنتروپی یک اتوماتای یادگیر تابعی از زمان میباشد
یک اتوماتای یادگیر سلولی دارای مجموعهای از اتوماتونهای یادگیر است
آنتروپی اتوماتای یادگیر سلولی، مجموع آنتروپی اتوماتونهای یادگیر آن است
معیارهای ارزیابی رفتار
14
متوسط (پاداش/جریمه) دریافتی توسط اتوماتای یادگیر iام در یک پیکربندی مشخص از اتوماتای یادگیر سلولی
معیارهای ارزیابی رفتار
درجه مصلحتگرائی (Degree of Expediency)
پیکربندی اتوماتای یادگیر سلولی
15
LA1
LA2
LA3
LA4
فضای پیکربندیها
رفتار اتوماتای یادگیر سلولی نگاشت G : K→K است که با اِعمال قانون محلی ایجاد میشود
متوسط (پاداش/جریمه) دریافتی توسط عمل rام اتوماتای یادگیر iام در یک پیکربندی مشخص از اتوماتای یادگیر سلولی
مجموع متوسط (پاداش/جریمه)های دریافتی اتوماتای یادگیر سلولی در یک پیکربندی خاص
معیارهای ارزیابی رفتار
اتوماتای سلولی کاملاً شانسی
اتوماتای سلولی که در هر سلول آن یک اتوماتای کاملاً شانسی وجود داشته باشد
پیکربندی یک اتوماتای سلولی کاملاً شانسی:
مجموع متوسط (جریمه/پاداش)های دریافتی اتوماتای سلولی کاملاً شانسی:
یک اتوماتای یادگیر سلولی مصلحتگراست اگر
16
معیارهای ارزیابی رفتار
درجه مصلحتگرائی
(با فرض اینکه متوسط جریمه باشد)
17
انواع اتوماتای یادگیر سلولی
همگام
تمامی سلول ها با یک ساعت مرکزی همگام هستند
اتوماتونهای یادگیر تمامی سلول ها با هم فعال می شوند، با هم عمل انتخاب می کنند و با هم وضعیت خود را بروز مینمایند
مناسب برای کاربردهای متمرکز یا کاربردهای توزیعشدهای که در آنها اجزاء توزیع شده همگام هستند
نمونه کاربردها
انتشار شایعه
پردازش تصاویر
بازیابی تصاویر
قطعهبندی تصاویر
جایابی مدارهای مجتمع متراکم
18
انواع اتوماتای یادگیر سلولی
ناهمگام
در اغلب کاربردهای توزیع شده به دلیل عدم امکان همگام سازی تمامی سلول ها با یکدیگر، کاربرد بیشتری نسبت به حالت همگام دارد
آخرین حالت هر همسایه به عنوان ورودی قانون محلی مورد استفاده قرار می گیرد
Step Driven
ترتیب فعال سازی به یکی از حالات زیر و یا هر حالت قابل تصور دیگری انجام می شود
ترتیب ثابت
ترتیب تصادفی
ترتیب جدید تصادفی
ترتیب یکنواخت
Time Driven
هر سلول یک ساعت داخلی دارد که آن سلول را در زمان های خاصی فعال می کند
فعال شدن هر سلول کاملاً مستقل از فعال شدن سایر سلول ها صورت می پذیرد
در بسیاری از کاربردهای توزیع شده ی واقعی، به دلیل عدم وجود یک مرکز تعیین ترتیب، گزینه ی مناسب تری می باشد
نمونهها
تشخیص لبه در تصاویر
پیمایش موضوعی وب
اختصاص کانال پویا
19
انواع اتوماتای یادگیر سلولی
بسته
در اتوماتای یادگیر سلولی بسته، سیگنال تقویتی تنها تابعی از عمل انتخابی هر سلول و عمل های انتخابی سلول های همسایه (محیط محلی) می باشد
باز
در اتوماتای یادگیر سلولی باز، سیگنال تقویتی تابعی از محیط محلی و محیط سراسری می باشد
20
نمونهها
لبهیابی تصاویر
بهینهسازی (مبتنی بر ترکیب اتوماتای یادگیر سلولی باز و بهینهسازی گروه ذرات PSO)
انواع اتوماتای یادگیر سلولی
شعاع همسایگی متغیر
در اتوماتای یادگیر سلولی استاندارد شعاع همسایگی عددی از پیش تعیین شده و در طول اجرا ثابت است
در برخی کاربردها لازم است تا شعاع همسایگی در طول زمان تغییر یابد. به طور مثال در ابتدا همه ی سلول ها در همسایگی هم در نظر گرفته شوند و در طول محاسبه شعاع همسایگی کاهش یابد و تاثیرات محلی تر در نظر گرفته شود
نمونه
جایابی مدارهای مجتمع متراکم
21
انواع اتوماتای یادگیر سلولی
چند اتوماتون یادگیر در هر سلول
در برخی کاربردها لازم است که در هر سلول بیش از یک اتوماتون یادگیر قرار داشته باشد
یادگیری پارامترهای مختلف در یک سلول
اختصاص کانال پویا در شبکههای سلولی سیار
تعیین هر زیربخش از حالت سلول توسط یک اتوماتون
مدل ترکیبی CLA-EC
22
کاربردها
شبیه سازی مدل انتشار شایعه
تنظیم بار در گریدهای محاسباتی
تخصیص کانال در شبکه های سلولی
جایابی مدارات مجتمع متراکم
شبیه سازی تکامل ماقبل حیات
مدل سازی شبکه های تجاری
پردازش تصاویر
قطعه بندی
تشخیص لبه
رفع نویز
واضح سازی تصویر
خوشه بندی شبکه های حسگر بی سیم
28
مراجع
[1] محمدرضا میبدی, حمید بیگی و مسعود طاهرخانی, « اتوماتای یادگیر سلولی», در مجموعه مقالات ششمین کنفرانس انجمن کامپیوتر ایران, ص 163-153, 1379.
[2] Beigy, H., and Meybodi, M. R., “A Mathematical Framework for Cellular Learning Automata”, Advanced in Complex Systems, to appear.
[3] Beigy, H., and Meybodi, M. R., “A Mathematical Framework for Cellular Learning Automata”, Advanced in Complex Systems, to appear.
[4] رضا رستگار و محمد رضا میبدی, «یک طبقه بندی برای اتوماتاهای یادگیر سلولی», در مجموعه مقالات دومین کنفرانس فناوری اطلاعات و دانش, 1384
[5] M. R. Kharazmi, and M. R. Meybodi, “Application of Cellular Learning Automata to Image Segmentation”, Proceedings of Tenth Conference on Electrical Engineering (10th ICEE), University of Tabriz, Vol 1, pp. 298-306, May 2002.
[6] M. R. Kharazmi, and M. R. Meybodi, “An Algorithm Based on Cellular Learning Automata for Image Restoration”, Proceedings of The First Iranian Conference on Machine Vision & Image Processing, University of Birjand, pp. 244 –254, March 2001.
[7] F. Marchini and M. R. Meybodi, “Application of Cellular Learning Automata to Image Processing: Finding Skeleton” ,Proceedings of The Third Conference on Machine Vision, Image Processing and Applications (MVIP 2005) University of Tehran, Tehran, Iran, pp. 271-280, Feb. 2005.
[8] H. Beigy and M. R. Meybodi, “A Self-Organizing Channel Assignment Algorithm: A Cellular Leaning Automata Approach”, Vol. 2690 of Springer-Verlag Lecture Notes in Computer Science, PP. 119-126, Springer-Verlag, 2003.
[9] H. Beigy and M. R. Meybodi, “A Dynamic Channel Assignment Algorithm: A Cellular Learning Automata Approach", Proceedings of The 2nd Workshop on Information Technology & It's Disciplines, pp. 218-231, Kish Island, Iran, February 24-26, 2004.
45
مراجع
46
[10] M. R. Meybodi and M. R. Khojaste, “Application of Cellular Learning Automata in Modeling of Commerce Networks”, in Proceedings of 6th Annual International Computer Society of Iran Computer Conference CSICC2001, Isfahan, Iran, PP. 284-295, 2001.
[11] M. R. Meybodi and F. Mehdipour, “VLSI Placement Using Cellular Learning Automata”, Journal of Modares, University of Tarbeit Modares, Vol. 16, pp. 81-95, summer 2004.
[12] M. R. Meybodi and M. Taherkhani, ”Application of Cellular Learning Automata to Modeling of Rumor Diffusion”, in Proceedings of 9th Conference on Electrical Engineering, Power and Water institute of Technology, Tehran, Iran, PP. 102-110, May 2001
[13] R. Ghanbari and M. R. Meybodi, "Load Balancing in Grid Computing Using Cellular Learning automata”, Technical Report, Computer Engineering Department, Amirkabir University, Tehran, Iran, 2004.
[14] Beigy, H. and Meybodi, M. R.., “Asynchronous Cellular Learning Automata” ,Proceedings of 10th Annual CSI Computer Conference o Iran, Telecommunication Research Center, Tehran, Iran, pp. 271-280, Feb. 2005.
[15] Beigy, H. and Meybodi, M. R., “Open Synchronous Cellular Learning Automata”, Proceedings of the 8th world Multi-conference on Systemics, Cybernetics and Informatics(SCI2004), pp. 9-15, Orlando, Florida, USA. July 18-21, 2004.
[16]R. Rastegar and M. R. Meybodi, “A New Evolutionary Computing Model based on Cellular Learning Automata”, to appear in proceedings of IEEE conference on Cybernetics and Intelligent Systems 2004 (CIS2004), Singapore, December 2004.
?
با تشکر