نوع فایل: word
قابل ویرایش 106 صفحه
مقدمه:
1-1- اتوماتای سلولی
علم در مورد مدلهایی که بشکل برده از خواستهای ما تبعیت می‌کنند،کاربرد کمی دارد.مدلهایی مطلوب ما هستند که با ما صحبت کنند، مدلهایی که ایده‌های خودشان را داشته باشند. ما همیشه می‌خواهیم بیش از آنچه در مدل قرار داده‌ایم، از آن استخراج کنیم، همچنین درعلوم مختلف همیشه سعی بر این بوده است تا با شکستن سیستمها به اجزای کوچکتر، آنها را تجزیه و تحلیل نماییم. اما در علم اتوماتای سلولی روش دیگری در پیش‌گرفته می‌شود و آن قرار دادن اجزای ساده در کنار هم به منظور ایجاد یک سیستم پیچیده می‌باشد.
اتوماتای سلولی در اواخر دهه 1940 توسط John von Neumann مطرح و پس از او توسط ریاضیدانی بنام Stanisla Ulam به عنوان مدلی برای بررسی رفتار سیستم‌های پیچیده پیشنهاد شد . اتوماتای سلولی، جهان‌هایی هستند تعریف شده با قوانین ساده که شباهت بسیاری به صفحه بازی دارند. می‌توان آنها را بطور واقعی ساخت و مراحل تکاملشان را مشاهده نمود. البته همیشه نباید در اولین آزمایش انتظار نتایج جالب توجه را داشت ضمن آنکه از دیدگاههای مختلف تعریف نتایج جالب توجه با هم تفاوت دارد. در هر حال، پس از ساختن چند تا از آنها، قادر خواهیم بود که یک اتوماتای سلولی برای هدف خاص خود طراحی و پیاده‌سازی کنیم.
اتوماتای سلولی در حقیقت سیستم‌های دینامیکی گسسته‌ای هستند که رفتارشان کاملاً بر اساس ارتباط محلی استوار است. در اتوماتای سلولی، فضا بصورت یک شبکه تعریف می‌گردد که به هر خانه آن یک سلول گفته می‌شود. زمان بصورت گسسته پیش می‌رود و قوانین آن بصورت سرتاسری است که از طریق آن در هر مرحله هر سلول، وضعیت جدید خود را با در نظر گرفتن همسایه‌های مجاور خود بدست می‌آورد. اتوماتای سلولی را می‌توان به عنوان سیستم‌های محاسباتی نیز در نظر گرفت که اطلاعات کد شده در خودشان را پردازش می‌کنند. همچنین یک اتوماتای سلولی بهمراه واحد کنترل آنرا می‌توان بعنوان یک ماشین SIMD تعبیر نمود.
اتوماتای سلولی چندین بار و هر بار تحت نام مختلفی نسبت به سایرین ابداع شده است. نامهایی نظیر cellular structures, homogeneous structures, tessellation automata tessellation structures و iteration arrays از جمله نامهایی هستند که اتوماتای سلولی با آنها معرفی شده است . از دیدگاه ریاضیات محض آنها را می‌توان شاخه‌ای از دینامیک توپولوژیکی (Topological Dynamics) از دیدگاه مهندسی برق آرایه‌های تکرار شونده (Iterative Arrays) و از دیدگاه کودکان دبستانی نوعی بازی کامپیوتری دانست .
در نوشتن قوانین اتوماتای سلولی، مشخص می‌کنیم که هر سلول چگونه از برخی از سلولهای همسایه خود اثر می‌پذیرد. یک سلول را همسایه سلول دیگر گوئیم هر گاه که قادر باشد آنرا در یک مرحله و براساس قانون تحت تاثیر قرار دهد. برای سلولهای واقع در مرزها می‌توان سلولهای واقع در مرز(های) مقابل را بعنوان همسایه در نظرگرفت. در صورتیکه همسایگی را بدین صورت در نظر گیریم، آنرا wrap around و در غیر اینصورت bounded گوئیم. در بدست آوردن وضعیت کنونی سلول علاوه بر وضعیت قبلی سلولهای همسایه، می‌توان وضعیت قبلی خود سلول را نیز دخالت داد. معمولاً قوانین اتوماتای سلولی بطور دستی طراحی می‌شوند. البته برای جستجو در فضای قوانین، راه‌حلهایی بر مبنای الگوریتمهای ژنتیک نیز ارائه شده است .
نکته‌ای که در مورد جدول قوانین وجود دارد، تعداد حالات ممکن پرکردن جدول می‌باشد. برای مثال، اگر تنها چهار همسایه شمالی، جنوبی، شرقی، غربی و نیز خود سلول را در نظر گیریم، تعداد حالات ممکن 25=32 می‌شود که چنانچه دو حالت برای هر سلول در نظر بگیریم، 232 حالت برای پرکردن جدول وجود خواهد داشت که حدود چهار میلیارد می‌گردد. حال اگر همسایه‌های شمال غربی، شمال شرقی، جنوب غربی و جنوب شرقی را نیز در نظر گیریم، تعداد حالات پرکردن جدولمی‌گردد که توان دوم تعداد تخمینی ذرات بنیادی جهان می‌باشد! راه حلی که در این زمینه وجود دارد، استفاده از یک زبان برای بیان قوانین و مکانیزمی برای تفسیر آن است.
فهرست مطالب:
فصل اول
1- مقدمه
1-1- اتوماتای سلولی
1-1-1- پیدایش اتوماتای سلولی
1-1-2- تعریف رسمی اتوماتای سلولی
1-1-3- ویژگی‌های اتوماتای سلولی
1-1-4- سیستم‌های دینامیکی
1-1-5- بازی زندگی Game of Life
1-1-6- کاربردهای اتوماتای سلولی
1-2- اتوماتای یادگیرنده
1-2-1- اتوماتون یادگیرنده
1-2-2- محیط
1-2-3- اتوماتای احتمالی با ساختار ثابت (Fixed Structure)
1-2-4- اتوماتای احتمالی با ساختار متغیر (Variable Structure)
1ـ2ـ5ـ اتوماتای متصل به هم ( Interconncted Automata )
1ـ2ـ6ـ کاربردهای اتوماتای یاد گیرنده
1ـ3ـ تئوری اطلاعات
1ـ3ـ1ـ آنتروپی
1ـ3ـ2ـ پیچیدگی و اطلاعات
فصل دوم
2- اتوماتای یادگیرنده سلول
2-1- لزوم ایجاد مدل جدید
2-1-1- آیا اتوماتای سلولی شرایط مورد نیاز برای یادگیری تقویتی را تأمین می کند؟
2-1-2- آیا سلولها در یادگیری خود همکاری دارند؟
2-2- تعریف جدید مدل اتوماتای یادگیرسلولی
2-3- تعریف رسمی اتوماتای یادگیرسلولی
2-4- نحوه پاداش دهی به سلولها
2-4-1- خبرگی
2-5- آیا مدل جدید یک سیستم چند عامله است؟
2-6- آیا می‌توان با افزودن هوشمندی به سلولهای اتوماتای سلولی انتظار همگراشدن سیستم را داشته باشیم؟
فصل سوم
3 -کاربردهایى از اتوماتاى سلولی و یادگیر
3-1-یک الگوریتم مرتب سازی موازی برای اتوماتای سلولی خطی
3-2-حل مسئله بزرگترین برش در گراف با استفاده از اتوماتای یادگیر سلولی
منابع و مراجع
منابع و مأخذ:
[1] طاهرخانی، مسعود. "طرح و بررسی اتوماتای یادگیرنده سلولی به عنوان ابزاری جهت مدلسازی سیستمها". دانشگاه صنعتی امیرکبیر. زمستان 1378.
[2] Adami, C., “Introduction to Artificial Life”, Springer Verlag, New York, Inc., 1998.
[3] Sutton, R., Barto A., “Reinforcement Learning: An Introduction”, MIT Press, 1998.
[4] Narendra, K.S. and Thathachar, M.A.L., “Learning Automata: An Introduction”, Prentice Hall, Inc., 1989.
[5] Wolfram, S., “Statistical Mechanics of Cellular Automata”, Review of Modern Physics.
[6] Wolfram, S., “Universality and Complexity in Cellular Automata”, Physica D. 10. pp. 1-35. 1984a.
[7] Wolfram, S., “Computation Theory of Cellular Automata”, Communications in Mathematical Physics, 96, pp. 15-57, 1984b.
[8] Wolfram, S., “Random Sequence Generation by Cellular Automata”, Advances in Applied Mathematics, 7, pp. 123-169, 1986b.
[9] F.Barahona, M.Grotschel, M.Junger and G.Reinelt,"An Application of Combinatorial Optimaization to Statistical Physics and Circuit Layout Design",Oper.Res., Vol.36, pp.493-513, 1988.
[10] R.Karp,"Reducibility among combinatorial problems",Complexity of computer computations, pp.85-104, 1972.
[11] S.Sahni and T.Gonzalez,"P-Complete Approximation Problems",Journal of ACM, vol.23, No.3, pp.555-565, 1976.
[12] T.Hofmeister and H.Lefmann,"A Combinatorial Design Approach to MAXCUT",Procedings of the 13th Symposium on Theoretical Aspects of Computer Science, pp.441-452, 1996.
[13] M.X.Goemans and D.P.Wiliamson,"Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Proggraming",Journal of ACM,Vol.42. No.6, pp.1115-1145, 1995.
[14] P.M.Vitanyi,"How Well Can a Graph is n-Colored?",Disc.Math, Vol.34, pp.69-80,1981.
[15] S.Poljak and D.Turzik, "A Polynomial Algorithm for Constructing a Large Bipartite Subgraph with an Application to a Satisfiability Problem",Can.J.Math, Vol.34, PP.519-524,1982.
[16] D.J.Haglin and S.M.Venkatesan,"Approxiation and Intractability Results for the Maximum Cut Problem and its Variants",IEEE Trans. Comput., Vol.40, PP.110-113, 1991.
پروژه رشته کامپیوتر با عنوان اتوماتای سلولی. doc