بخشی از مقاله
به کارگيري مدلي ترکيبي از بازي اقليت و اتوماتاي يادگير براي ايجاد
هماهنگي در سيستم هاي چند عامله
چکيده
ايجاد هماهنگي يکي ازمسائل مهم واساسي در سيستمهاي چندعامله است که توسط محققين بسياري مورد مطالعه قرار گرفته است . بدون وجود هماهنگي ميان عاملها، ممکن است سيستم دچار هرج و مرج شده و از رسيدن به هدف نهايي بازبماند. بـازي اقليت مدل ساده اي از سيستمهاي چند عامله رقابتي هست که براي مطالعه همکاري و رقابت ميان عاملهـا در سيسـتمهاي بـا منابع محدود به کار مي رود. هدف اصلي اين مقاله ارائه روشي مبتني بر يک مدل ترکيبي از بازي اقليت و اتوماتاي يادگير براي ايجاد هماهنگي در سيستم هاي چند عامله است . در روش پيشنهادي با کمک اتوماتاي يادگير مدل بهتري براي هماهنگي عاملها پيشنهاد گرديده است. براي بررسي و ارزيابي روش پيشنهادي از محيطي بنام DynaGrid استفاده شده است.شبيه سازي هاي انجام گرفته نشان دهنده بهبود فرآيند هماهنگي و يادگيري در مدل پيشنهادي نسبت به روش هاي قبلي است .
کلمات کليدي :سيستم هاي چند عامله، هماهنگي، بازي اقليت،اتوماتاي يادگير.
١- مقدمه
يک سيستم چند عامله دربرگيرنده جامعه ايي از عامل هاست کـه در يک محيط در کنار يکديگر در حال انجام فعـاليتي بـوده و سـعي در انجام کار خاصي دارند. فرآيند هماهنگي در سيستم هاي چند عامله به دو صورت همکاري و رقابت مطرح مي شود. در يک محيط رقابتي مبتني بر تيم عامل هاي موجود در قالب چند تيم براي دستيابي بـه هدفشان با هم همکاري مي کنند در چنين محيطي عامل بايد نسبت به تغيير محيط واکنش مطلوبي را نشان دهد و همواره بايد تصميمي مناسب را بر اساس باز خوردهـاي دريـافتي از محـيط اتخـاذ نمايـد. کوشش در اين مقاله اين است که با کمک بازي اقليت و ويژگي هاي خاصي که در آن وجود دارد عامل ها را درجهـت شـناخت محـيط و اخذ تصميمات مناسب ياري نمايد.از طرفي اتوماتاي يـادگير نيزيـک شانزدهمين کنفرانس ملي سالا دانشکده مهندسي کامپيوتر ، دانشگاه صنعتي مدل انتزاعي است که بطور تصادفي يک عمـل از مجموعـه متنـاهي عمل را انتخاب کرده و بر محيط اعمال مي کند محيط عمل انتخاب شده توسط اتوماتا را ارزيابي کرده و نتيجه را توسـط سـيگنال هـاي تقويتي در قالب پاداش يا جريمه به اتوماتا اعلام مي کند[٢].ما تصور مي کنيم که مدل ترکيبي بازي اقليـت و اتوماتـاي يـادگير ويژگـي هاي لازم را براي ايجاد هماهنگي عامل ها در محيط مـد نظرمـان را فراهم مي کند. برهمين اسـاس از ايـن مـدلي ترکيبـي در محيطـي رقابتي بنام DynaGrid که يک محيط مشبک و شبيه سازي شـده براي بازي شکار و شکارچي است استفاده شده است . با بهره گيري از اين مدل تلاش شده عامل هاي موجود درجهت رسيدن به هماهنگي ياري گردند. در ادامه مقاله ابتدا به بررسي و معرفـي بـازي اقليـت و اتوماتاي يادگير پرداخته و سپس محيط مساله و بازي معرفي شـده است، سپس تـلاش شـده نتـايج و تجربيـات از بکـار گيـري مـدل پيشنهادي وسايرروش هاي يادگيري در چنين محيطي در جهـت آموزش عامل هاي موجود در بـازي بررسـي شـود. در بخـش پايـاني مقاله خلاصه ايي از مقاله ارائه گرديده است .
٢- بازي اقليت
بازي اقليت ، مدل ساده اي از سيستمهاي چند عامله رقابتي است که ديناميک پيچيده اي را در بر مي گيرد که براي مطالعـه همکـاري و رقابت عاملها در سيستمهاي با منابع محدود بـه کـار مـي رو .بـازي اقليت جزء بازيهاي تکرار پذيربا N (عددي فرد) بازيکن (عامل ) اسـت که هريک از عاملها بايستي يکي از دو انتخاب موجودشـان را در هـر مرحله انتخاب کنند. عامل ها بطور مسـتقيم بـا يکـديگر در تعامـل نبوده و از طريق مکانيزم بـه اشـتراک گذاشـتن اطلاعـات بـه رفتـار جمعي صريح دست پيدا مي کنند[١٤]. بواقع بازي اقليت مدل ساده ايي است که در آن بازيکنان بدون امکان هيچگونه ارتباط مستقيمي با يکديگر هماهنگ مي شوند. در اين بازي ما عامل هـايي بـا ميـزان محدوديتي از عقلانيت روبرو هستيم . در هر گـام از بـازي عامـل هـا يکي از دو سمت ٠ يا1(A يا B ) را انتخاب مي نمايند و در هر گام از بازي عامل هاي که در سمتي باتعداد عامل هاي کمتر قرار مي گيرند برنده آن گام مي باشند. بـازي اقليـت شـامل سـه پـارامتر اساسـي حافظه (m)، تعدادي بازيکن (N ) و در نهايت تعدادي استراتژي(S ) مي باشد. در هر گام از بازي هر بازيکن بر اسـاس يکـي از اسـتراتژي هايي که در اختيارش است و با توجه به مقدار m يکي ازدو سـوي ٠ يا ١ را انتخاب مي نمايد. بازيکناني که در گوشه اقليت هستند برنده آن گام از بازي هستند. و تمامي استراتژي هايي که گوشه ي اقليـت (برنده) را به طور صحيح پيش بيني نمودند پاداشـي را دريافـت مـي کنند و متعاقب آن پيش بيني اشتباه توسط يک اسـتراتژي برابـر بـا تنبيه آن استراتژي است .نتـايج مراحـل مختلـف از بـازي مـي توانـد توسط يک عدد باينري ارائه گردد که اين همـان مقـداري اسـت کـه بعنوان تاريخچه در حافظه (m) قرار مي گيرد.[١٣]
٣- اتوماتاي يادگير
اتوماتاي يادگير يک مدل انتزاعي است که بطور تصادفي يک عمل از مجموعه متناهي عمل را انتخاب کرده و بر محـيط اعمـال مـي کند محيط عمل انتخاب شـده توسـط اتوماتـا را ارزيـابي کـرده و نتيجه را توسط سيگنال هاي تقويتي در قالب پاداش يا جريمه بـه اتوماتا اعلام مي کند. اتوماتا نيز وضعيت داخلي خود را تغيير داده و عمــل بعــدي را انتخــاب مــي کنــد.محــيط توســط ســه تــايي نشان داده مي شود. که α مجموعـه ورودي ها β مجموعه خروجي هـا و Cمجموعـه احتمـال هـاي جريمـه ياپاداش است .[١]
٤- معرفي مساله و آشنايي با محيط بازي
آنچه که ما در اين مقاله در پي آن هستيم شامل موارد زير است :
• چگونه مـي تـوانيم از بـازي اقليـت در فرآينـد يـادگيري استفاده نمائيم ؟
• چگونه مي توانيم نگاشتي مناسب بين نحوه رفتار عامل ها در محيط DynaGridکه محيطي شبيه سازي شده براي بازي شکار و شکارچي است و ويژگي هاي اساسـي بـازي اقليت برقرار نماييم ؟
• چگونه مي تـوانيم بـا ارائـه يـک مـدل ترکيبـي نگاشـتي مناسب ميان بازي اقليت و اتوماتاي يادگير برقرار نماييم ؟
• آيا مدل پيشنهادي مي توانـد مـا را در ايجـاد همـاهنگي ميان عامل ها ياري نمايد و آيا ايـن مـدل کـاراتر از روش هاي پيشين مي باشد؟
٤-١- شکار و شکارچي
دســـته ايـــي از بـــازي هـــاي تعقيبـــي بـــراي نخســـتين بـــار در [٦]توسط Benda مطرح گشت . در تمامي بازي ها تلاش بر اين بود که از هوش مصنوعي توزيع شده براي ايجاد هماهنگي ميان عامل ها بهره برداري شود. در[١١] يک راه حل حريصـانه بـراي ايـن مسـاله مطرح گشت ، در [١٢]تلاش شد از نسخه ي اصلي بازي اقليـت بـراي ايجاد هماهنگي ميان عامل ها بهره گيري شود. در[١] عامـل هـا بـا استفاده از يادگيري تقويتي در جهت رسيدن به هدفشان هماهنـگ مي شوند.در [١٠],[٩],[٨]نحوه ارتباط ميان عامل ها و ويژگي هاي رقابتي که ممکن است ميان عامل ها اتفاق ميافتد مورد بررسي قرار گرفت . در[١٠]سياست هاي متفاوتي براي هماهنگي عامل ها و نحوه حرکت عامل هاي شکارچي مطرح شده است . همچنين مدل هايي از اين بازي ارائه شد که در آن هيچ ارتباطي ميان عامل هاي شـکارچي وجود نداشت که عملا راه حل مناسبي براي اين مساله نبود چون در خيلي موارد عامل ها راه همديگر را در رسيدن به عامـل هـدف سـد مي کردند[٩]. تلاش ما در اين مقاله اين است که با ايجاد تغييراتي در نسخه ي اصلي بازي اقليت و استفاده از ساير مدل هاي آن به راه حلي کارآمد براي اين مساله در محيط DynaGrid برسيم .در واقـع الگوريتم پيشنهادي ما مبتني بر ايجاد تغييراتي در بازي اقليت اسـت تا از اين راه هم حجم تبادل اطلاعات را ميان عامل ها کـم نمـوده و هم عامل ها را در جهت انجام رفتارهايي هماهنگ تر ياري نمايد.
٤-٢- محيط DynaGrid
از ابتداي معرفي بازي شکار و شکارچي محيط هاي متفاوتي براي آن مطرح گشته است ، يکي از اين محيط ها محـيط DynaGrid اسـت همان طور که در شکل ١ ديده مـي شـود محـي DynaGridيـک محيط مشبک است که در آن عامـل هـاي دو تـيم متفـاوت (آبـي و قرمز) براي دستيابي به يک عامل هدف(مشکي ) بـا هـم رقابـت مـي نمايند.
• هر خانه در اين شبکه داراي يک مقدار مطلوبيت است که مقدار آن برابر Umax-d مي باشـد. (Umax در ايـن مقالـه برابر ١٠٠٠ مي باشدو d برابر است بـا فاصـله آن خانـه از خانه ايي است که عامل هدف در آن قرار دارد.)
• هر عامل در هر گام از بازي مي تواند بـه يکـي از هشـت خانه ي خالي مجاور خويش حرکت نمايد.
• نحوه ي حرکت عامل هدف براساس سياست اعمـال شـده در بازي مي تواند بـه صـورت تصـادف [٩] يـا خطـي يـا منحني [٧] باشد.
شکل (١) : تصوير يک لحظه از محيط DynaGrid
٥- روش پيشنهادي
روش هاي متفاوتي براي حل مسأله شـکار و شـکارچي ارائـه گشـته است . نويسندگان[١٠]تلاش نمودند ساختارهاي متفـاوت حرکتـي و ميانگين گام هاي لازم براي رسيدن شکارچيان به شـکار را محاسـبه نمايند. در[١١]يک روش حريصانه را براي حل اين مسأله پيشـنهاد شد.در [١٢] تلاش شد از نسخه ي اصـلي بـازي اقليـت بـراي ايجـاد هماهنگي ميان عامل هاي يک تيم استفاده شود. آنچـه کـه در ايـن مقاله دنبال مي شود اين است که تلاش مي نماييم مدل ترکيبـي از بازي اقليت و اتوماتاي يادگير را ارائـه نمـاييم در نهايـت روش هـاي پيشنهادي را با روش هاي قبلي مقايسـه مـي نمـاييم . بواقـع مـا از راهبرد بازي اقليت در مسـأله شـکار و شـکارچي در هـر گـام بـدين ترتيب استفاده مي نمائيم :
١- تمامي عامل هاي موجود در يک تيم در هر گام, در بـازي اقليـت شرکت مي نمايند.
٢- عامل هايي که در بازي اقليت برنده شده انـد حرکـت واکنشـي و عامل هايي که در گوشه ي اکثريت واقع شده اند و بازنـده شـده انـد حرکت هماهنگي را انجام مي دهند. حرکت واکنشي : در اين حرکت عامل از بين خانه هاي اطراف خانه ايي را که بيشترين مقدار ارزش را دارد انتخاب مي کند و بدان خانه مي رود. حرکت هماهنگي : عاملي که اين حرکت را انتخاب مي نمايد تلاش مي نمايد به خانه ايي کوچ نمايد که کمترين مقدار ارزشي را داشته باشد ولي اگر عاملي از تيم مخالف را در همسايگي خويش ببيند به جاي حرکت هماهنگي همان حرکت واکنشي را انجام داده و به خانه ايي با مقدار ارزشي بالاتر مي رود تا از اين طريق سدي در مقابل حرکت عامل تيم مقابل به سمت عامل هدف باشد. شکل ٢ الگوريتم پيشنهادي ما در قالب شبه کد نمايش مي دهد.
[RND-MG]بواقع ما در الگوريتم پيشنهادي خويش با بهره گيري از [١٠]تلاش نموديم در هر مرحله به جاي يک حافظه واقعي از يک حافظه تصادفي استفاده نماييم و آن را به طور يکسان در اختيار تمامي عامل ها قرار دهيم . و چون در عمل لازم نيست که در هر مرحله تمامي اطلاعات مراحل قبلي از تمامي عامل ها را جمع آوري نماييم حجم اطلاعات مبادله شده کاهش يافته و همچنين زمان لازم براي شروع گام بعدي بازي و ايجاد هماهنگي ميان عامل ها کم مي شود که اين پارامتر در شبکه هاي سنسوري که طول عمر باتري هاي سنسورها ارتباط مستقيم با مدت زمان روشن ماندن و ميزان ارتباطات آنها دارد مي تواند مورد توجه قرار گيرد.
٥-١- استفاده از مدل ترکيبي بازي اقليـت و اتوماتـاي يادگير براي ايجاد هماهنگي
همان طور که پيش از اين بيان شد در بازي اقليت هر عامـل در هـر گام از بازي يکي از استراتژي هاي در دسترس را انتخـاب کـرده وبـر همان اساس حرکت خويش را انجام مي دهد. پس از پايـان آن گـام اگرآن استراتژي پيش بيني صحيح را داشت و توانست گوشه ي اقليت را درست پيش بيني نمايد پـاداش ودر غيـر اينصـورت جريمـه مـي گيرد. حرکت هر عامل هم در محيط DynaGridبر همـين اسـاس انجام مي گيرد. در مدل پيشنهادي β دو عضوي و معادل پـاداش و جريمه مي باشد همچنين مجموعه همان مجموعه استراتژي هـا مي باشد که عامل بايد يکي از آنها را انتخاب نمايد. شکل زير تعامـل بيان بازي اقليت و اتوماتاي يادگير را نشان ميدهد.
شکل (٢) : الگوريتم RND_MG
شکل (٣) : تعامل بازي اقليت و اتوماتاي يادگير
در اين مدل ما از الگوريتم يادگيري خطي بـراي پـاداش يـا جريمـه استفاده مي نماييم .هر گاه استفاده از يک استراتژي باعث قرار گرفتن عامل در گوشه ي اقليت شود آن استراتژي و استراتژي ها مشـابه آن پاداش دريافت مي کنند و احتمال انتخاب آن در دفعات بعـد بيشـتر مي شود و هر گاه استفاده از آن استراتژي باعث عملکرد بدتري شود آن استراتژي و استراتژي هاي مشابه اش جريمه دريافت مي کننـد و احتمال انتخاب آن در دفعات بعد کمتـر مـي شـود. مسـاله انتخـاب استراتژي بر اساس مـدل ترکيبـي بـازي اقليـت و اتوماتـاي يـادگير منطبق بر الگوريتم زير است .
