ساخت پايگاه دانش توليد رفتار با استفاده ازالگوريتم تکاملي سيمبايوجنسيس

//ساخت پايگاه دانش توليد رفتار با استفاده ازالگوريتم تکاملي سيمبايوجنسيس

ساخت پايگاه دانش توليد رفتار با استفاده ازالگوريتم تکاملي سيمبايوجنسيس

1-1-  مقدمه

 

همان طور كه تاريخ الگوريتم هاي تکاملي نشان مي دهد، گونه هاي زيادي از الگوريتم‌هاي تكاملي وجود دارند. ولي ايده همه آنها يكي است: با داشتن جمعيتي از گونه‌ها[1]، فشار محيطي باعث انتخاب مي شود (القاء بهترين[2]) و اين افزايش شايستگي[3] جمعيت را نتيجه مي دهد. با داشتن يك تابع كيفيتي كه مي خواهيم بيشينه شود، مي توان مجموعه اي از جواب هاي كانديد را به طور تصادفي توليد كرد و تابع كيفيت را به عنوان معياري براي محاسبه شايستگي به كار برد – (هر چه بيشتر، بهتر) بر اساس اين شايستگي ، بعضي از كانديدهاي بهتر انتخاب مي شوند، تا به عنوان هسته اي براي توليد نسل بعد به كار روند. بر روي اين كانديدها تركيب و يا جهش[4] اعمال مي شود. تركيب بر روي دو يا بيشتر كانديد اعمال مي شود (والدين) و نتيجه آن توليد فرزند (فرزنداني) است.

اعمال تركيب و جهش باعث توليد مجموعه جديدي مي شود كه با مجموعه قبلي (والدين) رقابت مي كنند تا در نهايت برنده ها در نسل بعدي ظاهر شوند. اين كار مي تواند ادامه پيدا كند تا يك كانديد با ويژگي هاي كافي (جواب) به دست بيايد و يا اينكه محدوديت‌هايي كه از قبل براي مسئله تعريف كرده ايم، ارضا شوند.

در اين عمل دو نيروي اصلي وجود دارد كه پايه سيستم تكاملي است:

–        عملگرهاي تغيير (تركيب و جهش) که باعث ايجاد گوناگوني لازم و در نتيجه نوآوري مي شود.

–        انتخاب كه نيرويي است كه كيفيت را به جلو مي برد.

تركيب تغيير و انتخاب باعث بهتر شدن مقادير شايستگي در جمعيت ها مي شود.

با مشاهده روند حركت جمعيت مي توان تكامل به سوي بهينگي را مشاهده كرد.

 تكامل به عنوان فرايند تطبيق بيان مي شود. از اين ديد، شايستگي به عنوان هدف اصلي كه بايد بهينه شود مطرح نيست، بلكه عبارتي است كه نيازمندي كل محيط را بيان مي‌كند، هرچه اين نيازمندي ها بيشتر ارضا شوند، نتيجه در تعداد بيشتري از اعضاي جمعيت خود را نشان مي دهد. عمل تكامل باعث مي شود كه جمعيت با محيط خود بيشتر و بيشتر سازگار شود.

بسياري از اجزاي فرآيند تكامل اتفاقي[5] هستند. اين اجزا در زمان انتخاب موجوداتي كه مناسب تر[6] هستند، احتمال انتخاب بيشتري دارند، هر چند در بيشتر اوقات، موجودات ضعيف تر هم شانس انتخاب شدن و زنده ماندن را دارند. اکثر اوقات موجودات به طور تصادفي براي تركيب از جمعيت خارج مي شوند. اين مطلب در مورد تغييرات نيز صادق است. طرح كلي الگوريتم هاي تكاملي در شکل 1-1 آمده است.

شکل1-1.طرح کلي  الگوريتم تکاملي

همان گونه كه از شبه كد نيز معلوم است، الگوريتم هاي تكاملي جزئي از الگوريتم‌هاي توليد – آزمايش[7] هستند.

–        الگوريتم تكاملي مبتني بر جمعيت است.

–        الگوريتم تكاملي از تركيب استفاده مي كند تا اطلاعات گونه هاي بيشتري را در يك گونه خلاصه كند.

–        الگوريتم تكاملي اتفاقي است.

گونه هاي مختلف الگوريتم هاي تكاملي همگي از طرح كلي كه ارائه شد، پيروي مي‌كنند و فقط در جزئيات تكنيكي متفاوت هستند.[1]

1-2-     علت استفاده از الگوريتم هاي تكاملي

الگوريتم هاي تكاملي در مقايسه با ساير الگوريتم هاي بهينه سازي برتري هايي دارند كه موجب شده است به طور گسترده مورد استفاده قرار بگيرند. به عنوان مثال، اين الگوريتم ها، نياز به معرفي كامل مسئله ندارند و تنها با داشتن اطلاعات چندي در مورد تعريف مسئله مي توانند كار كنند. همچنين محدوديتي درمورد تابع شايستگي ندارند و لزومي ندارد كه اين تابع مثلاً مشتق پذير باشد.

علاوه بر اين موارد، چون الگوريتم هاي تكاملي داراي جمعيتي از موجودات هستند و روي بخش هاي مختلفي از جمعيت به طور موازي كار مي كنند، احتمال كمتري براي قرار گرفتن در بهينه هاي محلي[8] دارند. اين قابليت الگوريتم هاي تكاملي اجازه مي دهد كه كار بهينه سازي را به طور موازي روي چندين بخش جمعيت انجام داد. به عنوان نتيجه اين ويژگي گفته مي شود كه الگوريتم هاي تكاملي روي جمعيت هاي “فضول” خوب عمل مي‌كنند. اين گونه جمعيت ها داراي تعداد زيادي بهينه هاي محلي هستند. الگوريتم هاي تكاملي در اين بهينه هاي محلي گير[9] نمي كنند و معمولاً مي توانند در نهايت به بهينه ترين جواب برسند. [2]

1-3-     انواع الگوريتم هاي تكاملي

همان طور كه در بخش اول گفته شد، گونه هاي مختلفي از الگوريتم هاي تكاملي وجود دارد، گفته مي شود كه اين الگوريتم ها به سه دسته كلي تقسيم مي شوند:

  1. الگوريتم هاي ژنتيكي (GA) ارايه شده توسط Holland [4]و مطالعه شده توسط Goldberg [5]
  2. استراتژي هاي تكاملي (ES) ارايه شده توسط Rechenberg [6]و Schwefel [7]
  3. برنامه ريزي تكاملي (EP) ارائه شده توسط L.J. Fogel et. Al [8]و اصلاح شده توسط D.B. Fogel  [9]

هر كدام سه روش بالا اثبات شده اند كه با داشتن فضاي مسئله پيچيده، پيوسته و چند كيفيتي[10] به جواب تقريباً بهينه مي رسند.

از دسته بندي بالا، گروه اول (الگوريتم هاي ژنتيكي) را به تفسير در فصول بعدي بررسي مي كنيم. در مورد دو دسته ديگر به طور اختصار توضيح مي دهيم.

1-3-1: استراتژي هاي تكاملي

استراتژي هاي تكاملي ارايه شده توسط Rechenberg، Schwefel از لحاظ تاريخي به منظور حل مسائل بهينه سازي پارامترها تعريف شدند. در نتيجه هر گونه در جمعيت به صورت ليستي از اعداد حقيقي تعريف مي شد.[11] علاوه بر اين هر گونه شامل يك سري پارامترهاي استراتژي نيز بود. اين پارامترها براي كنترل رفتار عملگرهاي جهش استفاده مي شدند.

در هر دوره از اجراي الگوريتم،  فرزند توليد مي شوند. اندازه جمعيت  بود و معمولاً  برابر 6 بود عملگر تركيب به ازاي توليد يك فرزند نياز به دو والد داشت. همين دو والد براي توليد هر دو بخش فرزند (پارامترهاي استراتژيك و متغيرهاي شي) مورد استفاده قرار مي گرفتند. انتخاب والدها به صورت تصادفي از جمعيت فعلي بود. گونه هاي مختلفي براي تركيب وجود دارند ولي بهترين جواب براي نوع تركيبي بود كه متغيرهاي شيء فرزند را همه از روي يكي از والدين برداشته و براي پارامترهاي استراتژي نيز ميانگين پارامترهاي استراتژي والدين استفاده شود.

عملگر اصلي در ES، جهش است و روي هر دو بخش گونه اعمال مي شود. عملگر جهش ابتدا روي بخش پارامترهاي استراتژي اعمال مي شود. بعد از آن متغيرهاي شيء با استفاده از نتايجي كه از اعمال جهش روي پارامترهاي استراتژي حاصل شده است، جهش مي كنند. اين نوع جهش به ES اين قابليت را مي دهد كه خود را تطبيق دهد و سعي كند بهترين پارامترهاي استراتژي را بدست آورد.

انتخاب در ES به طور قطعي انجام مي شود. بهترين  گونه از بين  فرزند انتخاب مي شوند. (انتخاب ) يا بهترين  گونه از اجتماع دو جمعيت انتخاب مي شوند (انتخاب ()) همانند برخي ديگر از الگوريتم هاي تكاملي ES تا زماني كه يكي از شروط خاتمه مسئله برقرار شود، اجرا مي شود. در شكل1-2 شبه كدي از ES ارائه شده است.

شکل1-2: شبه کد استراتژي تکاملي

1-3-2: برنامه ريزي تكاملي

برنامه ريزي تكاملي ارائه شده توسط L.J. Fogel et al اولين بار براي تكامل ماشين‌هاي حالت با استفاده از تعداد محدودي كد كردن الفباها تعريف شد. بعد از آن EP D. B Fogel را براي بهينه سازي متغيرها گسترش داد. همانند ES، گونه ها در EP به صورت رشته اي از اعداد حقيقي تعريف مي شوند. تفاوت EP با ES اين است كه در EP عملگر تركيب وجود ندارد. تكامل به طور كامل به عملگر جهش وابسته است. عملگر جهش از توزيع احتمال گووس براي تغيير هر متغير استفاده مي كند.

انحراف معيار استاندارد از روي ريشه تبديل خطي شايستگي والدين به دست مي آيد (اين تبديل را بايد پارامتري كنيم) براي جلوگيري از كار زياد با پارامترهاmeta-EP, Fogel را ارائه كرده است. در meta- EP هر گونه شامل متغيرهاي شي و واريانس (يك واريانس به ازاي هر متغير شي) است. از اين واريانس ها براي كنترل عملگر جهش گووسي استفاده مي شود.

عملگر انتخاب با استفاده از tranment-select انجام مي شوند. گونه خاصي به نام q-tournament selection استفاده مي شود. الگوريتم به اين صورت است كه u را اجتماع جمعيت فرزندان و والدين مي گيريم. به ازاي هر عضو m از u،q حريف از u به صورت تصادفي انتخاب مي شوند. تعداد حريف هايي كه مقدار شايستگي آنها از m بدتر است حساب مي شود.[12]  گونه اي كه تعداد حريف هاي ضعيف آنها از همه بيشتر هستند و وارد جمعيت مي شوند. هرچه q افزايش پيدا مي كند، الگوريتم انتخاب قطعي تر مي شود. در نتيجه بهترين گونه هميشه در جمعيت جديد حضور دارد. شبه كد EP در شکل 1-3 ارائه شده است. [3]

10

شکل1-3: شبه کد برنامه ريزي تکاملي

 

 

 

 

فصل دوم: الگوريتم ژنتيك

زندگي در طبيعت دائماً در حال تكامل است. الگوريتم هاي ژنتيكي، الگوريتم هاي محاسباتي هستند كه با توجه به تكامل ايجاد شده اند. به نظر مي آيد الگوريتم هاي ژنتيكي براي جستحو فضاهاي بزرگ كه به طور ضعيف توصيف شده اند، به كار مي‌روند.

2-1: ژنتيك در طبيعت

در زيست شناسي، ژن واحد اصلي ذخيره سازي در ژنتيك است[10]. درون سلول ها، ژن ها براي توليد كروموزوم به هم متصل شده اند. ساده ترين نوع توليد جنسي بين ارگان هاي يك موجود تك سلولي است. دو سلول براي توليد يك سلول جديد با دو دسته كروموزوم تركيب مي شوند. اين سلول جديد “دولا”[13] نام دارد. اين سلول بلافاصله دچار تقسيم سلولي[14] مي شود. در تقسيم سلولي هر كدام از كروموزوم هاي سلول diploid يك كپي از خود مي سازد. بعد گروه كروموزوم ها (جديد و اصلي) با هم تركيب مي شوند. بعد كروموزوم ها دو بار از هم جدا مي شوند و چهار سلول diploid توليد مي كنند. جهش مي تواند در هر مرحله انجام شود. هر تغييري در كروموزوم به فرزندان به ارث مي رسد.

جهش براي تكامل لازم است. سه نوع جهش در الگوريتم هاي ژنتيكي وجود دارد:

  1. جهش نقطه­اي: كه در آن يك ژن تغيير مي كند.
  1. جهش كروموزوم: كه در آن تعدادي از ژن هاي رشته كروموزوم به طور كامل از بين مي روند.
  2. جابجايي: كه در آن بخشي از كروموزوم دچار تغيير مي شود.

2-2: الگوريتم ژنتيك استاندارد:

الگوريتم ژنتيك استاندارد از مدل توليد جنسي haploid استفاده مي كند. در GA استاندارد جمعيت مجموعه اي از گونه هاي عددي باينري مثل 1101011 هستند. هر گونه يك رشته كروموزوم را نشان مي دهد. تعدادي تابع وجود دارند كه نشان مي دهند كه هر individual به چه ميزاني مناسب است. تابع ديگري وجود دارد كه individual ها را براي توليد مثل از جمعيت انتخاب مي كند.

دو كروموزوم انتخاب شده با هم crossover مي كنند و مجدد تقسيم مي شوند. بعد از آن، دو individual جديد جهش مي كنند. اين كار به تعداد دفعات مشخصي تكرار مي‌شود.

هر كدام از عملگرهاي بالا را  معرفي مي كنيم:

  • شايستگي: معياري از خوب بودن كروموزوم است. يعني چقدر اين رشته كروموزوم مناسب فضاي فعلي مسئله است و آن را حل مي كند. براي الگوريتم ژنتيك استاندارد، شايستگي ، تابع f است از مجموعه كروموزوم هاي موجود به مجموعه اعداد حقيقي.

  • انتخاب: عمل انتخاب يك زوج است براي عمل توليد مثل. تابع انتخاب مي تواند هر تابع صعودي باشد. يكي از توابع موجود انتخاب fitness-proportionate است كه تابع انتخاب آن تابع احتمال  روي جمعيت {x1,..,xn} مي‌باشد.
  • Cross over: عمل جابجا كردن ژن بين دو individual در حال توليد است. گونه هاي زيادي از crossover وجود دارد ولي ما crossover يك نقطه اي را بررسي مي كنيم. عدد تصادفي i بين يك و n انتخاب مي شود. اين عدد نقطه اي از رشته كروموزوم است كه crossover با احتمال Pc، انجام مي شود. اگر crossover انجام شود. در آن صورت بخش­­هاي دو رشته كروموزوم تا نقطه i با هم جابجا مي شوند. به عنوان مثال 11111111 وقتي با رشته 00101010 در i=4، crossover مي كنند، دو رشته 00101111 و 11111010 را توليد مي كنند.

  • جهش: عمل تغيير كروموزوم به صورت تصادفي است. pm احتمالي است كه بيت iام تغيير كند. كه در آن i بين 1 تا n است. براي هر i عدد تصادفي بين صفر و يك انتخاب مي شود. اگر عدد بدست آمده از pm كمتر بود، در آن صورت، آن بيت تغيير مي كند.

در شكل 2-1 شبه كدي از 7 مرحله الگوريتم ژنتيكي ارائه شده است. [11]

10

شکل2-1: شبه کد الگوريتم ژنتيکي

فصل سوم: الگوريتم تكاملي سيمبيوتيك[15] (SEA)

در اين فصل به معرفي نوع جديدي از الگوريتم هاي تكاملي ارايه شده در مقاله اي در  CEC2007 مي پردازيم.

3-1: علت معرفي SEA

مي دانيم در الگوريتم ژنتيكي عملگر تركيب اين وظيفه را دارد كه ويژگي هاي شخصيتي والدين را از كروموزوم هاي آنها استخراج نموده و آنها را تحت تركيب جديدي در فرزندان قرار دهد به اميد اينكه فرزندان ويژگي هاي خوب والدين خود را داشته باشند. انجام اين عمل مستلزم داشتن شكل كروموزوم و عمل تركيب مناسب است.

مي دانيم كه در تركيب دو رشته كرموزوم، عمل انتخاب ژن ها از والدين براي توليد فرزند، بسيار مهم است. يك تركيب مناسب آن است كه ژن هاي “خوب” را در والدين انتخاب نماييم. ولي ما از كجا مي توانيم تشخيص دهيم در يك رشته كروموزوم كدام ژن ها خوب هستند و كدام مناسب نيستند؟ علاوه بر اين، مشكل ديگر اين است كه اگر براي يك موقعيت در كروموزوم هر دو والدين ژن خوب وجود داشته باشند، از كجا مي توانيم تشخيص دهيم كه كدام كروموزوم را براي مقداردهي به اين موقعيت بايد انتخاب كنيم؟ روشهاي مختلفي براي حل اين مشكلات ارائه شده است. يكي از اين راه حل ها استفاده از ايده داشتن كروموزوم هاي ناقص است. همانند آنچه در MGA [16][14] بيان شده است.

SEA نيز از اين ايده براي رفع مشكل استفاده مي كند. قبل از بيان الگوريتم SEA لازم است كه نوعي عملگر تركيب كه در اين الگوريتم استفاده مي شود را معرفي كنيم.

3-2: عملگر تركيب سيمبيوتيك:

عملگر symbiotic بر اساس عمل symbiogenesis طراحي شده است. در طبيعت symbiogenesis عمل توليد گونه جديد از انضمام[17] ژنتيكي يك ارگان به نام symbionts مي­باشد. اين انضمام ژنتيكي با عملگر توليد مثل كه باعث انتقال ويژگي هاي ژنتيكي مي‌شود، متفاوت است. در عملگر تركيب معمولي، توليد مثل بين دو والد از يك گونه انجام مي شود. عمل انتقال ژن به فرزند به طور كاملاً اختصاصي انجام مي شود. يعني براي يک موقعيت خاص اگر يك والد در آنجا ژنوم را داشته باشد،آن ژن از والد ديگر به ارث برده نمي­شود. برعكس در تركيب symbiotic، تركيب مي­تواند بين گونه هاي والد مختلف انجام شود، اين عملگر مي تواند باعث يكپارچگي كامل يك ژنوم شود، تركيب حاصل از اين ادغام شدن مي تواند ژن هاي يكي از والد را داشته باشد و درعين حال هر تعداد ژني كه بخواهد از والد ديگر بخواهد. [15]

بنابراين عملگر تركيب symbiotic به اين صورت عمل مي كند كه دو كروموزوم كه به طور ناقص تعريف شده اند را با هم تركيب كرده و فرزندي با تركيب ويژگي هاي دو كروموزوم اوليه ايجاد مي كند. در شكل3-1 نمونه اي از اين نوع تركيب ارايه شده است.

10

شکل3-1: نمونه اي از ترکيب Symbiotic

3-3: ايده كلي SEA:

 

ايده كلي SEA در شكل 3-1 نشان داده شده است. هر موقعيت ژني با شكل مجزايي بيان شده است. و هر مقدار، با يك شكل خاص[18] براي پر كردن اين موقعيت ها نمايش داده شده است. هر كروموزوم كامل بايد فقط و تنها فقط يك نمونه از اشكال موجود براي موقعيت ها را داشته باشد و هر كدام از اين موقعيت ها تنها بايد با يك شكل خاص پر شده باشند.

در الگوريتم كلي، هر كروموزوم با يك موقعيت (يك بيت) تعريف شده شروع به كار مي كند (قدم 1) در آغاز هر دوره با استفاده از عملگر تركيب symbiotic از روي كروموزوم ها، تركيبات مختلفي ساخته مي شوند. (قدم 2) هر كدام از تركيبات نشان دهنده يك كروموزوم كامل است و در نتيجه اين كروموزوم ها را مي توان سنجيد (قدم 3) بعد از اين كه تركيبات سنجيده شدند، آن اعضايي كه خوب نبودند ازجمع كروموزم‌ها خارج مي شوند (قدم 4) بعد از اين مرحله براي زياد كردن شانس انتخاب مجدد كروموزوم خوب، از آن كپي هايي ساخته مي شود (قدم 5). در حين كار كپي كردن، بخشهايي از كروموزوم خوب به هم متصل مي شوند تا كروموزوم ها به طور دقيق تر مشخص شوند. همچنين هر بخش از اين كروموزوم هم مي تواند با احتمالي جهش كند و كروموزوم جديد بسازد (قدم 6)

10

شکل3-2: نمونه اي از الگوريتم جستجو symbiotic-هر موقعيت با يک شکل و هر مقدار ممکن ژن نيز با شکلي رنک شده نشان داده شده است

بعد از اين مرحله تمام كروموزم هايي كه كپي شدند، جهش پيدا كرده اند و همچنين آن كروموزم هايي كه در مرحله قبل شركت نداشته اند، تحت عنوان جمعيت جديد براي دوره بعد اجراي الگوريتم انتخاب مي شوند، دوره جديدي از الگوريتم از قدم 2 شروع مي شود. شبه کد اين الگوريتم در شکل 3-3 آمده است. [12]

            THE SYMBIOTUIC EVOLUTIONARY ALGORITHM:

            1. Initialize population with all single-bit chromosomes with all possible values. Create an empty Tabu list.

            2. Repeat until stopping conditions are met:

            2.1. Create a number of assemblies using ASSEMBLY-GENERATION-FUCNTION. If any of the assemblies is already in the Tabu list, remove it and create another one instead.

            2.2. Compute the fitness of all assemblies.

            2.3. Choose the best assembly and add it to the Tabu list. If Tabu list exceeds its pre-specified size, remove the oldest member.

            2.4. For each symbiont of the best assembly,

            2.4.1. With MutationRate probability, create a mutated copy of the chromosome and add it to the pool.

            2.5. For all pairs of symbionts of the best assembly,

            2.5.1. Combine the pair and create an offspring. If the offspring has less specified genes than the number specified by CoolingFunction, add it to the pool. Otherwise, randomly break it into some chromosomes (with random sizes) and add them to the pool.

            2.6. Remove all symbionts of the bottom 25% assemblies from the pool, except those that have taken part in the top 25% assemblies as well.

2.7. If there is more than one copy of any chromosome in the pool, remove it.

            THE ASSEBLY GENERATION FUNCTION:

            1. Pick the first symbiont of the assembly, randomly from chromosome pool.

            2. While the assembly is not complete,

            2.1. Randomly pick Selection_Rate × Population chromosomes from the pool so that none have any conflict with the assembly.

            2.2. If a partial evaluation function exists, run 2.2.1, otherwise 2.2.2.

            2.2.1. Compute the fitness of the symbiotic combination of each of them with the assembly and pick the best.

            2.2.2. Randomly pick one.

2.3. Add the chosen chromosome to the assembly.

شکل3-3: شبه کد الگوريتمSEA

 

 

 

 

 

فصل چهارم: توصيف فضاي مسئله

          بازي Pac-Man يک بازي کامپيوتري معروف است که در اصل توسط Toru Iwanati براي شرکت Namco در سال 1981 طراحي شد. مدل معمول اين بازي شامل يک بازيکن است که توسط انسان در زمين شطرنجي بازي حرکت داده مي­شود. بازيکن تلاش مي­کند که از چهار “روحي” که در زمين بازي در حال حرکت هستند فرار کند و در عين حال از زمين “دانه” هايي که در اول بازي در زمين پخش شده اند را جمع کند. اگر Pac-Man با روحي برخورد کند، يکي از 3 “جاني” که دارد را از دست مي­دهد. بعد از آن بازي ادامه پيدا مي­کند و روح ها به مکان اوليه خود باز گردانده مي­شوند. در برخي از بازي ها در 4 گوشه زمين نيز دانه هايي وجود دارد که اگر Pac-Man از آن دانه ها بخورد تا مدت زماني معين مي­تواند روح ها را بخورد. بازي در صورتي که Pac-Man هر 3 جانش را از دست داده باشد به پايان مي­رسد. شکل4-1 تصويري از وضعيت اوليه شروع بازي را نشان مي­دهد

10

شکل4-1: نقطه آغاز يک بازي Pac-Man

Pac-Man يک بازي زمان حقيقي است که حول دنبال کردن يک موجود در يک محيط نيمه ساختيافته، جمع کردن دانه، دفاع کردن و در شرايطي حمله کردن مي چرخد. اين بازي ها نيازمند کنترل ديناميک بازيگر بازي توسط يک نيروي انساني است و کارهايي مثل اولويت دهي، برنامه ريزي و بررسي خطر ها را شامل مي­شود.

يادگيري اين قواعد براي انسان ساده است در حالي که براي Pac-Man بازي، جنبه هاي سختي دارد که نيازمند مطرح کردن استراتژي­هاي جديدي است.

در اين فصل ابتدا ايده کلي قرار دادن يک agent به جاي نيروي انساني براي بازي کردن را مطرح مي­کنيم. براي انجام اين کار قواعد بازي را تا حد خوبي ساده کرده­ايم. در اين جا تنها يک روح، يک Pac-Man و تعدادي دانه در صفحه بازي داريم. به صورت يک ماشين حالت، تعدادي قانون و احتمال حرکت ها بسته به هر قانون، مطرح شده است. در پايان اين قواعد را معرفي مي­کنيم.

هدف ما اين است agent اي را پيدا کنيم که بتواند بازي کردن را تنها بر اساس اطلاعاتي که در اختيار بازيگر انساني که Pac-Man را بازي مي کند، ياد بگيرد. به طور کلي agent نبايد اطلاعات خاصي در مورد جريان داخلي بازي داشته باشد. (مثلاً اينکه رفتار روح چگونه پياده شده است) علاوه براين بايد قواعد کلي خوب بازي کردن را ياد بگيرد و اين يادگيري نبايد بر مبناي يک زمين بازي خاص باشد. يادگيري بايد استراتژي هاي بازي کردن خوب Pac-Man باشد.

4-1: agent

در اين بخش به معرفي agent مسئله (Pac-Man) مي­پردازيم و مي­خواهيم که agent ما بتواند در شرايط که ذکر شد بازي را انجام دهد.

agent را به صورت ساده و شفاف در نظر مي­گيريم. يک پياده سازي خوب بايد اين ويژگي را داشته باشد که بتواند بستر مناسبي ايجاد کند که بتوان روش­هاي تکاملي را براي يادگيري روي آن آزمايش کرد. اين ملاحظات باعث مي­شود که  agentرا به صورت يک ماشين حالت متناهي با دو وضعيت[19] به همراه مجموعه­اي از احتمالات براي هر وضعيت در نظر بگيريم. اين احتمالات براي کنترل حرکت agent به کار مي­رود.  در هر زمان وضعيت با فاصله­اي که agent نسبت به روح دارد، تعيين مي­شود. اگر اين فاصله از مقدار مشخصي بيشتر باشد، agent در وضعيت  Exploreاست و اگر از آن مقدار مشخص کمتر باشد در وضعيت Retreat است.

وقتي انسان با Pac-Man بازي مي­کند، مي تواند تمام زمين را در حين بازي ببيند. ولي به طور اتوماتيک توجه اوليه اش به منطقه است که الان Pac-Man در آن قرار دارد. برنامه ريزي يک سري پشت سرهم از حرکات براي انسان مشکل نيست ولي کارموثري نيز نيست چون اين بازي ديناميک است و پيش بيني حرکات کار بيهوده­اي است.

بنابراين ايده اوليه ما براي يک agent براي Pac-Man اين است که بازي را به عنوان تعداد کمي حالات گردش[20]  و يک سري اطلاعات کلي مثل موقعيت و نوع حرکت روح، ببينيم. شکل 4-2 تمام حالات مختلف گردش در صفحه بازي نشان مي­دهد. (نقشه­اي از زمين بازي)

10

شکل4-2:نقشه زمين بازي Pac-Man به همراه تمام حالات گردش

در هر لحظه از بازي، در يکي از حالات گردش قرار دارد و بسته به اين موقعيت بايد خروجي مناسب را توليد کند تا موقعيت و جهت جديد خود را تعيين کند. به ازاي حالات مختلف گردش در موقعيت فعلي(راهرو[21]، گردشL[22]، تقاطعT شکل[23] و چهارراه[24]) حالات ممکن گردش وجود دارد. در وضعيت Explore انتخابات احتمالي با توجه به شکل حالت گردش انجام مي­شود. در نتيجه Pac-Man فضاي بازي را به صورت شبه تصادفي مي­گردد. Explore کردن براي پيدا کردن خروجي حرکتيagent  از هيچ اطلاع ديگري استفاده نمي­کند. در حالت retreat، علاوه بر ملاحظات بالا، agent براي پيدا کردن خروجي حرکتي به موقعيت روح نيز توجه مي­کند. يعني بايد حالات مختلف گردش و موقعيت را تواماً براي پيدا کردن خروجي حرکتي در نظر گرفت.

موقعيت­هاي مختلف روح را به  8 دسته­ي “روبرو، پشت،چپ، راست، روبرو و چپ، روبرو و راست، پشت و چپ و پشت و راست” نسبت به موقعيت Pac-Man تقسيم مي­کنيم. بايد در نظر داشت که 4 وضعيت اول فقط براي حالات يک بعدي در نظر گرفته مي­شوند يعني اگر به عنوان مثال Pac-Man رو به سمت بالا باشد، در آن صورت روح در دسته “پشت” است اگر مقدار  y از مقدار y فعلي Pac-Man کمتر باشد. براي اصلاح کردن اين وضعيت 4 دسته ديگر موقعيت را براي روح در نظر مي­گيريم. براي همان مثال، موقعيت روح به صورتي که در جدول 4-1 نشان داده شده است، دسته­بندي مي­شود.



[1] individual

[2] Survival of the fittest

[3] fitness

[4] mutation

[5] stochastic

[6] Fitter

[7] Generate-and-test

[8] Local optima

[9] trap

[10] Multi modal

[11]  به اين بخش از گونه متغيرهاي شي (object variables) مي گويند.

[12] Count

[13] diploid

[14] meiosis

[15] Symbiotic Evolutionary

[16] Messy Genetic Algorithms

[17] Integration

[18]pattern

[19] state

[20] Turn type

[21] corridor

[22] L-Turn

[23] T-Junction

[24] Intersection

۱۳۹۲-۸-۵ ۰۱:۰۴:۰۰ +۰۳:۳۰آبان ۵ام, ۱۳۹۲|هوش مصنوعی دسته بندی ها|برچسب ها:٪ s |بدون ديدگاه

ثبت ديدگاه

پرداخت

1-پرداخت آنلاین
برای پرداخت آنلاین از لینک زیر استفاده کنید
پرداخت آنلاین
2- پرداخت آفلاین
برای پرداخت آفلاین مبلغ مورد نظر را به یکی از شماره کارت
6037997245888723بانک ملی