پایان نامه اتوماتاي يادگير سلولي
فهرست محتوا
فهرست
1-1-1- پيدايش اتوماتاي سلولي.. 3
1-1-2- تعريف رسمي اتوماتاي سلولي.. 8
1-1-3- ويژگيهاي اتوماتاي سلولي.. 9
1-1-4- سيستمهاي ديناميكي.. 18
1-1-5- بازي زندگي Game of Life. 21
1-1-6- كاربردهاي اتوماتاي سلولي.. 24
1-2-3- اتوماتاي احتمالي با ساختار ثابت (Fixed Structure) 36
1-2-4- اتوماتاي احتمالي با ساختار متغير (Variable Structure) 44
1ـ2ـ5ـ اتوماتاي متصل به هم ( Interconncted Automata ) 52
1ـ2ـ6ـ كاربردهاي اتوماتاي ياد گيرنده. 55
2- اتوماتاي يادگيرنده سلولي. 63
2-1-1- آيا اتوماتاي سلولي شرايط مورد نياز براي يادگيري تقويتي را تأمين مي كند؟ 65
2-1-2- آيا سلولها در يادگيري خود همكاري دارند؟. 66
2-2- تعريف جديد مدل اتوماتای يادگيرسلولي.. 66
2-3- تعريف رسمي اتوماتای يادگيرسلولي.. 67
2-4- نحوه پاداش دهي به سلولها 69
2-5- آيا مدل جديد يك سيستم چند عامله است؟. 74
3-1-2- كلاس CGeneralNeighboreState. 79
3-1-3- كلاس CtotalisticNeighborState. 81
3-1-4- كلاس CTNeighborGroup. 82
3-1-8- كلاس CCellularAutomata. 97
3-1-9- كلاس CNeighborsStates. 103
3-1-13- كلاس CLearningAutomata. 113
3-1-14- كلاس CFixedStructureSLA.. 114
3-1-22- كلاس CVariableStructureSLA.. 122
3-1-23- كلاس CLinearRewardPenalty. 126
3-1-24- كلاس CLinearRewardEpsilonPenalty. 126
3-1-25- كلاس CLinearRewardInaction. 127
3-2- انواع داده های برنامه. 133
1- مقدمه
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- پيدايش اتوماتاي سلولي
تئوري اتوماتاي جهاني Turing باعث شد تا von Neumann در مورد اتوماتاي سلولي كه توانايي self-reproduction داشته باشد، فكر كند. پرسشي كه او از خود نمود اين بود كه چه نوع ساختار منطقي ميتواند به اتوماتون اين امكان را دهد كه مانند خود را ايجاد كند؟
يك ساختار با ويژگي self-reproduction مجموعهاي از سلولهاي فعال است كه هر كدام بيانگر بخشي از يك ماشين ميباشد. در هر مرحله هر اتوماتون از مجموعهاي از قوانين بشكل تابعي از وضعيت كنوني خود و وضعيت همسايههاي مجاورش استفاده ميكند تا وضعيت بعدي خود را بدست آورد. براساس چنين تاثير متقابل محلي، يك ساختار اوليه پس از طي چندين مرحله، يك نسخه از خودش را ميسازد.
ماشين Turing يك اتوماتون انتزاعي است كه ميتواند در يكي از n حالت قرار داشته باشد و قادر به خواندن و نوشتن برروي نواري بطول بينهايت ميباشد. با چنين ماشين سادهاي Turing توانست ادعا كند كه ميتوان هر مسالهاي را كه با قلم و كاغذ قابل حل است، با اين ماشين نيز حل نمود و در نهايت ماشين جهاني خود را معرفي كرد. پس هر ماشين محاسباتي پيچيده در حقيقت معادل ماشين Turing است..
von Neumann دريافت كه چنين ايدهاي را ميتوان با افزايش تعداد عمليات ماشين Turing بسط داد. ايده شبيه سازي يك كامپيوتر توسط كامپيوتر ديگر (با دادن اطلاعات كافي در مورد آن كامپيوتر، مثلاً مجموعه قوانين) باعث شد تا von Neumann خواستههاي يك اتوماتون را جهت ساختن اتوماتون ديگر فرموله كند. درقياس با Turing، او تعريفي از قسمتهاي بنيادي جهت ساختن اتوماتون ارائه كرد (تحت عنوان كاتالوگ اجزاء ماشين). اتوماتون سازنده در مجموعه نامحدودي از اين اجزا شناور است و هنگاميكه توصيف اتوماتون خاصي را دريافت ميدارد، آن را ميسازد. به چنين اتوماتوني، اتوماتون سازنده جهاني (Universal Constructive Automaton) گويند كه آنرا A ميناميم.
در شكل 1-1- نمودار شماتيك اتوماتون self-replicative يا Mc نشان داده شده است. Mc شامل دو بخش است. يكي بخش سازنده (Constructing Unit) كه اتوماتون جديد را ميسازد و ديگري بخش نوار ميباشد كه اطلاعات لازم براي ساختن اتوماتون جديد را ميتواند بخواند و بنويسد.
شكل 1-1) نمودار شماتيك اتوماتون self-replicarive
بخش نوار شامل يك كنترلگر نوار و يك نوار است. نوار بصورت يك آرايه خطي از سلولهايي است كه شامل اطلاعاتي در مورد M يعني اتوماتوني كه بايد ساخته شود، هستند. اطلاعات روي نوار از چپ به راست شامل موارد زير ميباشد:
مختصات x و y گوشه سمت چپ و پايين (x0,y0) مستطيلي كه در آن بايد اتوماتا ساخته شود.
ب – طول و عرض اين مستطيل
پ – وضعيت سلولها بترتيب معكوس
ت – يك علامت ستاره كه نشان دهنده پايان نوار ميباشد.
ايجاد اتوماتون جديد با فرستادن سيگنال (از طريق انتشار وضعيتهاي سلولها) بين بخش نوار و واحد سازنده انجام ميشود. واحد سازنده شامل يك واحد كنترل و يك بازوي سازنده ميباشد. بازوي سازنده يك آرايه از وضعيتهاي سلولها است. كه از طريق آن وضعيتهاي سلولها ميتواند از واحد كنترل به محل مورد نظر در محدوده ساخت منتقل گردد.
I را توصيف يك اتوماتون خاص (مشابه نوار اطلاعات در ماشين Turing) در نظر ميگيريم. در حالت خاص، به A ميتوان توصيف خودش را داد كه در آنصورت به آن Self-replicate گوئيم. حال اتوماتون B را در نظر ميگيريم كه دستورالعملهاي I را دريافت كرده تا يك كپي از آن بسازد (B مثل يك ماشين كپي ميباشد). C نيز يك مكانيزم كنترل است.
ابتدا C به A دستور ميدهد تا اتوماتوني را كه توسط I توصيف شده بسازد. سپس C باعث ميگردد كه B يك كپي از I ساخته و آن را در اتوماتون تازه ساخته شده قرار دهد. در نهايت اتوماتون ساخته شده از A و B جدا ميشود. پس داريم:
D= (A,B,C)
واضح است كه D زماني ميتواند عمل كند كه دستورالعملهاي I براي آن فراهم شده باشد. حال دستورالعملهاي ID را در نظر ميگيريم كه D را توصيف ميكنند (بجاي آنكه A يا B را توصيف كنند) لذا خواهيم داشت:
E= (D, ID)
كه يك اتوماتون self-replicate جهاني ميباشد.
لازم است در اينجا به اين نكته اشاره كنيم كه بين اتوماتون و توصيف آن اختلاف وجود دارد. طبق نظر Von Neumann اين دو مفاهيمي در سطوح مختلف ميباشند. يكي از دلايل اين امر در مشاهدات او بود كه اتوماتا قادر است اتوماتاي با پيچيدگي بالاتري نسبت به خودش را بسازد (نظير ماشينهايي كه ابزار دقيق ميسازند). تنها بحثي كه باقي مانده بود، آن بود كه اين اطلاعات اضافي از كجا فراهم ميگردد. او ادعا كرد كه سطحي از پيچيدگي بالاتر از آنچه كه پيچيدگي ميتواند به آن برسد وجود دارد (در نسلهاي بعد). براي تصحيح ايده von Neumann با دانستن ساختار كد ژنتيك، بايد گفت كه اين افزايش اطلاعات (دستورالعملهاي پيچيدهتر) است كه عامل افزايش پيچيدگي ارگانيزم ميگردد. اطلاعات در ID بوسله موتاسيون تصادفي (Random Mutation) نوشته ميشود كه von Neumann آنها را با genome در اتوماتي طبيعي مطرح كرد. اين اطلاعات لزوماً نبايد در ابتدا در ID باشد. بنابراين سيستم داراي قوه تكثير (Reproductive) كامل ايد شامل محيطي باشد كه به آن وفق داده ميشود.
1-1-2- تعريف رسمي اتوماتاي سلولي
اتوماتاي سلولي شبكهاي است از سايتها كه هر كدام ميتواند k حالت (وضعيت) داشته باشد. در هر سايت يك اتوماتون با حالات محدود (Finite State Automaton) قرار دارد. در حالت يك بعدي، هر سايت دو همسايه نزديك به خود دارد. در اين حالت، وضعيت سايت I در زمان t+1 يعني مطابق فرمول زير بدست ميآيد:
تابع را قانون اتوماتاي سلولي ميناميم. ايده همسايگي در اتوماتاي سلولي يك بعدي را ميتوان بسط داد بگونهاي كه دو همسايه ديگر و يا بيشتر را نيز شامل شود. يعني ميتوان شعاع r را براي همسايگي در نظر گرفت. البته معمولاً نزديكترين همسايهها را در نظر ميگيريم، يعني r=1 همچنين سايتها در اتوماتاي سلولي ميتوانند در شبكهاي با هر ابعادي قرار گيرند. دو نوع همسايگي مهم در اتوماتاي سلولي دو بعدي عبارتند از همسايگي Moore و همسايگي von Neumann . در همسايگي Moore براي هر سلولي مركزي هشت سلولي همسايه و در همسايگي von Neumann چهار سلولي همسايه در نظر گرفته ميشود:
نقد و بررسیها
هنوز بررسیای ثبت نشده است.