پایان نامه محاسبه نقطه تعادل نش در روشهای یادگیری تقویتی چندعاملی

اختصاصی از یارا فایل پایان نامه محاسبه نقطه تعادل نش در روشهای یادگیری تقویتی چندعاملی دانلود با لینک مستقیم و پرسرعت .

فرمت فایل : WORD (قابل ویرایش)

تعداد صفحات:130

پایان نامه برای دریافت درجه کارشناسی ارشد”M.Sc”
مهندسی  برق – کنترل

فهرست مطالب:
چکیده    1
مقدمه    3
1-    کلیات    5
1-1-    سئوالات کلیدی پروژه    8
1-2-    مفروضات پروژه    9
1-3-    روش کار و تحقیق    10
1-4-    ساختاربندی پروژه    10
2-    تئوری بازی    13
2-1-    رقابت در عامل‌ها    15
2-1-1-    بازیهای بدیهی    15
2-1-2-    بازیهای بدون رقابت    15
2-1-3-    بازیهای کاملاً رقابتی    16
2-1-4-    بازیهای با تضاد جزئی    16
2-2-    ساختار بازیها    17
2-2-1-    بازیهای نرمال    17
2-2-2-    بازیهای پویا    18
2-3-    مفهوم غلبه    20
2-3-1-    غلبه اکید در استراتژی محض    20
2-3-2-    غلبه ضعیف    21
2-3-3-    غلبه اکید در استراتژیهای مرکب    22
2-4-    نقطه تعادل نش    22
2-5-    نقطه تعادل کامل زیربازی    24
2-6-    بهینگی پارتو    24
2-7-    مفاهیم بسط یافته تعادل نش    25
2-7-1-    نقطه تعادل هم بسته    25
2-7-2-    نقطه تعادل ε    27
2-7-3-    نقطه تعادل کامل دست لرزان    27
2-7-4-    نقطه تعادل صحیح    30
2-7-5-    نقطه تعادل پاسخ دو جانبه‌ای (QRE)    31
2-7-6-    نقطه تعادل شبه کامل    33
2-7-7-    نقطه تعادل سلطه‌جو    33
2-7-8-    نقطه تعادل متوالی    35
3-    روشهای کلاسیک محاسبه نقطه تعادل نش    38
3-1-    محاسبه نقطه تعادل نش در بازیهای نرمال    38
3-1-1-    Lamke-hawson method    38
3-1-2-    Simple search method    47
3-2-    محاسبه نقطه تعادل نش در بازیهای پویا    51
3-2-1-    الگوریتم استقراء معکوس    51
4-    یادگیری تقویتی    55
4-1-    مبانی اولیه    56
4-2-    خاصیت مارکوف    57
4-3-    فرآیند تصمیم گیری مارکوف    58
4-3-1-    تابع ارزش    60
4-3-2-    تابع ارزش بهینه    62
4-3-3-    روش‌های حل فرآیندهای تصمیم گیری مارکوف    63
4-3-4-    برنامه ریزی پویا    63
4-3-5-    روش مونت کارلو    64
4-3-6-    روش تفاضل زمانی    65
4-4-    روش‌های یادگیری تک عاملی    67
4-4-1-    الگوریتم Sarsa    68
4-4-2-    الگوریتم Q-Learning    68
4-4-3-    الگوریتم Dyna_Q    70
5-    یادگیری تقویتی چندعاملی    73
5-1-    تاریخچه    73
5-1-1-    یادگیری Nash-Q    73
5-1-2-    یادگیری Friend or Foe    74
5-1-3-    یادگیری Asymmetric-Q    75
5-1-4-    Minimax    76
5-1-5-    Infinitesimal Gradient Ascent (IGA)    77
5-1-6-    Wolf-IGA    79
5-1-7-    (Policy dynamic wolf) PD-Wolf    80
5-2-    فرآیند بازی مارکوف    81
6-    محاسبه نقطه تعادل نش در یادگیری تقویتی n-عامله    86
6-1-    بازیهای مارکوف نرمال n-عامله    87
6-1-1-    استفاده از الگوریتم ژنتیک در محاسبه نقطه تعادل نش    89
6-2-    بازیهای مارکوف پویا n-عامله    91
6-2-1-    استفاده از روش استقراء معکوس تعمیم یافته در محاسبه نقطه تعادل نش    92
7-    شبیه سازی    95
7-1-    شبیه‌سازی در محیط مشبک    95
7-1-1-    استفاده از Q-Learning در محیط‌های چندعاملی    95
7-1-2-    مقایسه الگوریتم Nash-Q و Q-Learning    97
7-1-3-    محاسبه نقطه تعادل نش در یادگیری تقویتی چندعاملی    98
7-2-    شبیه سازی بازار برق    100
7-2-1-    مطالعه موردی    104
8-    نتیجه‌گیری    111
مراجع    114
ABSTRACT    123



 
چکیده

در این رساله، روش مناسبی جهت محاسبه نقطه تعادل نش در الگوریتم‌های یادگیری تقویتی چندعاملی با تعداد زیاد عامل‌ها مطرح شده‌است، که قادراست با ادغام محاسبات مربوط به نقطه تعادل نش و ایجاد مصالحه بین اکتشاف- استخراج، محاسبات را به صورت بهینه کاهش دهند. ترکیب یادگیری تقویتی تک- عاملی و تئوری بازی ایده اصلی اکثر روشهای یادگیری چندعاملی است. این روش‌ها سعی دارند تا کل فرآیند یادگیری را به تعدادی متناهی از حالت‌های تصمیم‌گیری چندعاملی با خاصیت مارکوف تقسیم کرده و با انتخاب نقطه تعادل نش در هر کدام از این مراحل به تدبیر بهینه برای هر عامل همگرا شوند. بنابراین محاسبه نقطه تعادل نش مسئله مهمی است که در حال حاضر مشکلاتی شامل پیچیدگی محاسبات در روشهای شناخته شده محاسبه نقطه تعادل نش، چندگانگی نقطه تعادل نش، و مختلط بودن نقطه تعادل نش باعث شده که اکثر روشهای پیشنهادی یادگیری تقویتی چندعاملی جایگاه مناسبی در حل مسائل دنیای واقعی پیدا نکنند. ناگفته نماند که تقریباً تمام روشهای یادگیری تقویتی چندعاملی مطرح شده، مبتنی بر روشهای off-policy بوده‌اند که نیازی به در نظر گرفتن مسئله رویه انتخاب عمل و اکتشاف در اثبات همگرایی ندارند. بنابراین در رویه‌های اجرایی پیشنهاد داده‌اند که ابتدا نقطه تعادل نش محاسبه شده و سپس با روش ϵ-greedy مصالحه بین اکتشاف و استخراج برقرار شود.
محاسبه نقطه تعادل ϵ-نش در بازی‌های نرمال در این رساله به صورت یک مسئله مینیمم‌سازی تعریف شده که جواب آن توسط الگوریتم‌های ژنتیک بدست آمده‌است. علاوه بر کاهش پیچیدگی روش محاسبه نقطه تعادل نش، با اضافه کردن جمله مناسب در محاسبه تابع برازندگی، هر عامل قادر است نقطه تعادل نش پارتو را محاسبه کند که مسئله چندگانگی نقاط تعادل نش را نیز مرتفع می‌سازد.
در پایان، روشهای پیشنهادی در حل مسئله بازار برق مورد استفاده قرار گرفته‌است. این مسئله که در سال‌های اخیر توجه زیادی را به خود جلب کرده در این رساله به سه قسمت تقسیم شده‌است. در قسمت اول شرکت برق با هدف کاهش هزینه‌ها یک مسئله برنامه‌ریزی مقید را با کمک برنامه‌ریزی خطی حل می‌کند. قید‌های این مسئله شامل لزوم تأمین نیازهای مصرف‌کنندگان و افت توان در خطوط انتقال انرژی می‌باشد. در قسمت دوم، هر ژنراتور با توجه به اطلاعات کسب شده مراحل قبلی اقدام به انتخاب قیمت‌گذاری جدید در ابتدای روز بعد می‌کند. این اطلاعات  شامل قیمت‌هایی که خودش و دیگران به شرکت برق ارائه کرده‌اند و تصمیم شرکت برق (که منجر به پاداش (سود) برای خودش و دیگران شده) می‌باشد. این قسمت توسط الگوریتم‌های ژنتیک حل شده است. در قسمت سوم، از همان اطلاعات ذکر شده در قسمت قبل به منظور اصلاح دیدگاهش برای روز گذشته استفاده می‌کند. الگوریتم یادگیری چندعاملی Nash-Q در این قسمت استفاده شده است. در حالت کلی، انرژی مورد نیاز شبکه و توپولوژی آن هر دو متغیر هستند. ولی در این رساله توپولوژی شبکه ثابت فرض شده است. شبیه‌سازی‌های انجام شده نشان می‌دهد که روش ارائه شده به خوبی قادر به حل مسئله یادگیری تقویتی چندعاملی در مسائل کاربردی با تعداد عامل بیشتر از دو است.
 

مقدمه

محاسبه نقطه تعادل ϵ-نش در بازی‌های نرمال در این رساله به صورت یک مسئله مینیمم‌سازی تعریف شده که جواب آن توسط الگوریتم‌های ژنتیک بدست آمده‌است. علاوه بر کاهش پیچیدگی روش محاسبه نقطه تعادل نش، با اضافه کردن جمله مناسب در محاسبه تابع برازندگی، هر عامل قادر است نقطه تعادل نش پارتو را محاسبه کند که مسئله چندگانگی نقاط تعادل نش را نیز مرتفع می‌سازد.
در پایان، روشهای پیشنهادی در حل مسئله بازار برق مورد استفاده قرار گرفته‌است. در ابتدای هر روز، شرکت برق با هدف کاهش هزینه و در عین حال تأمین نیازهای مصرفی با توجه به توپولوژی شبکه، به کمک برنامه‌ریزی خطی میزان خرید برق از هر ژنراتور را با توجه به قیمت‌های پیشنهادی آنها اعلام می‌کند. علاوه بر آن در پایان هر ماه با توجه به تناسب قیمت‌های پیشنهادی، مبلغی را به عنوان پاداش به هر ژنراتور می‌دهد. ژنراتورها با توجه به میزان سودی که از فروش برق بدست می‌آورند، پارامترهای مربوط به جدول ارزش‌های خود در آن روز را اصلاح می‌کنند. این جدول‌ها منعکس کننده مسئله تعیین قیمت با توجه به خواسته‌های شرکت برق و نحوه قیمت‌گذاری سایر ژنراتورها است. ژنراتور‌ها در ابتدای هر روز با توجه به این جدول به دنبال پیدا کردن بهترین پیشنهاد به شرکت برق هستند که در واقع همان مسئله تعیین نقطه تعادل نش است. با کمک یادگیری تقویتی چندعاملی، ارزش‌های این جدول‌ها به مرور اصلاح شده و عامل‌ها قادر به جمع‌آوری سود بیشتری در طول یک ماه خواهند بود. شبیه‌سازیهای انجام شده روند صعودی افزایش میزان سود را نشان می‌دهند.