پایان نامه بررسی سیستم‌های چند عامله با استفاده از تئوری بازی‌ها

اختصاصی از یارا فایل پایان نامه بررسی سیستم‌های چند عامله با استفاده از تئوری بازی‌ها دانلود با لینک مستقیم و پرسرعت .

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

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

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

فهرست مطالب:
چکیده    1
مقدمه    2
1-    عامل و سیستم‌های چند عامله    4
1-1- مقدمه    4
1-2- هوش مصنوعی توزیع شده    4
1-3- حوزه‌های کاری هوش مصنوعی توزیع شده    6
1-4- دلایل گرایش به هوش مصنوعی توزیع شده    9
1-4-1- پایه تکنولوژیکی    9
1-4-2- توزیع ذاتی    10
1-4-3- مزایای طراحی و پیاده‌سازی    12
1-4-4- دلایل معرفت شناسی    13
1-4-5- بنیاد اجتماعی    14
1-4-6- همجوشی (کلاس‌های جدید از مسائل)    14
1-5- مسائل مطرح در هوش مصنوعی توزیع شده    14
1-6- تعریف عامل و عامل‌های هوشمند    17
1-6-1- تعریف عامل    18
1-7- عامل به عنوان یک سیستم نرم‌افزاری    19
1-8- مفهوم عامل از دیدگاه عام    20
1-9- مروری برخصوصیات عامل    20
1-10- ویژگی‌های دیگر عامل‌ها    25
1-11- طبقه بندی عاملها    29
1-12- مقایسه عامل با شیء    33
1-13- تفاوت‌های سیستم مبتنی بر عامل و سیستم‌های خبره    35
1-14- انواع محیط عامل    35
1-14-1- قابل دستیابی / غیر قابل دستیابی    36
1-14-2- محیط قطعی یا غیر قطعی    37
1-14-3- محیط مقطعی یا غیر مقطعی    38
1-14-4- محیط ایستا / پویا    38
1-14-5- محیط گسسته یا پیوسته    38
1-15- سیستم‌های چند عامله    39
1-16- خصوصیات سیستم‌های چند عاملی:    46
1-17- دلایل استفاده از سیستم‌های چندعامله    47
1-17-1- نیاز برخی دامنه‌ها به سیستم‌های چندعامله:    47
1-17-2- افزایش سرعت عمل با موازی سازی    48
1-17-3- قابلیت اطمینان    48
1-17-4- توسعه پذیری    48
1-17-5- آسانتر شدن برنامه‌سازی    49
1-18- آزمون نظریه‌های سایر رشته‌های علمی    49
1-19- معماری‌های ارایه شده برای سیستم‌های چندعامله    49
1-19-1- مدل OMG     50
1-19-2- استاندارد FIPA     50
1-19-3- استاندارد KAOS    50
1-19-4- مدل General Magic    51
1-20- سازماندهی سیستم‌های چندعامله    51
1-20-1- ساختار سلسله مراتبی    51
1-20-2- ساختار مسطح    52
1-20-3- ساختار جزء به کل    53
1-20-4- ساختار پیمانه‌ای    53
1-21- پارامترهای مطرح در ارزیابی سیستمهای چندعامله    54
1-22- سیستمهای مقیاس وسیع(Large Scale systems):    55
1-23- کنترل غیر متمرکز : (Decentralized Control)    56
1-24- نتیجه‌گیری    57
2-    تئوری بازی‌ها و کاربردهای آن‌ها درسیستم‌های چند عامله    60
2-1- مقدمه    60
2-2- نظریه بازی ‌ها چیست؟    60
2-3- تفاوت میان تصمیم‌گیری و بازی    62
2-4- طبقه‌بندی نظریه بازی‌ها    63
2-5- برخی مفاهیم و اصطلاحات    68
2-6- موارد استفاده از نظریه بازی‌ها    74
2-7- فرض های اساسی در نظریه بازیها    75
2-8- شاخه‌های اصلی نظریه بازی‌ها    75
2-9- بازی‌های ایستا    77
2-10- نمایش بازی در فرم استراتژیک یا نرمال    79
2-11- فرم ماتریسی بازی    82
2-12- پیدا کردن جواب در بازیهای ایستا    82
2-13- بازیهای رقابتی    83
2-14- بازیهای تصادفی    84
2-15- بازیهای پویا    85
2-16- بازی پویا در فرم بسط یافته    85
2-17- درخت‌ بازی    87
2-18- عناصر فرم بسط یافته:    88
2-19- پیشینه بازی:    88
2-20- مجموعه اطلاعاتی:    89
2-21- استراتژی    90
2-22- پیدا کردن جواب در بازیهای پویا    91
3-    بررسی روش‌های یادگیری    93
3-1- یادگیری تقویتی    93
3-1-1- خط مشی    94
3-1-2- تابع پاداش    94
3-1-3- تابع مقدار    94
3-1-4- مدل برگرفته شده از محیط    95
3-2- اجزای یادگیری تقویتی    97
3-3- اهداف و پاداش    98
3-4- Q-Learning    99
3-5- خاصیت مارکوف    100
3-6- فرآیند تصمیم گیری مارکوف    101
3-7- روشهای حل فرآیندهای تصمیم گیری مارکوف    103
3-8- تابع ارزش    104
3-9- تابع ارزش بهینه:    105
3-10- فرایند تحلیل سلسله مراتبی (AHP)    106
3-11- ویژگیهای فرایند تحلیل سلسله مراتبی    106
3-12- ساختار سلسله مراتبی    107
3-13- اصول فرایند تحلیل سلسله مراتبی    108
3-14- محاسبه وزن    108
3-15- روشهای محاسبه وزن    109
3-15-1- روش حداقل مربعات ( least squares method )    109
3-15-2- روش حداقل مربعات لگاریتمی (logarithmic least squares method)    110
3-15-3- روش بردار ویژه ( Eigenvector Method ):    111
3-15-4- روش های تقریبی(Approximation Method)    112
3-16- سازگاری سیستم و ماتریس سازگار    112
3-17- محاسبه نرخ ناسازگاری    113
4-    نتیجه‌گیری    116
5-    مراجع    118
6-    ABSTRACT    121



 
چکیده

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


  مقدمه

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

فصل اول
عامل و سیستم های چند عامله

1-    عامل و سیستم‌های چند عامله

1-1-  مقدمه
یکی از مهمترین مقوله هایی که انتظار می رود در باره  یک حوزه علمی جدید، مشخص شود، آشنایی با ماهیت آن حوزه است. بدین معنی که این حوزه چیست، چگونه و چرا به وجود آمده است، سعی دارد چه مسائلی را حل کند، برای حل چه مسائلی کاربرد دارد و قلمروی آن تا کجاست؟
در دو دهه اخیر، با افزایش توجه به محاسبات توزیع شده و علاقه به استفاده از تکنیک‌های هوش مصنوعی در این نوع محاسبات، شاخه جدیدی از هوش مصنوعی به نام هوش مصنوعی توزیع شده  شکل گرفته است. "هوش مصنوعی توزیع شده" عبارتی است که پژوهشگران در اولین گردهمایی رسمی، کارگاهی آموزشی در سال 1980 در دانشگاه ام آی تی در آمریکا پیشنهاد کردند.
در این حوزه جدید، به حل مسائل به صورت توزیع شده، توسط گروهی از موجودیت‌های خودمختار  حل کننده مسئله به نام عامل  پرداخته می‌شود. در اجتماع عامل‌ها، هر عامل خودمختار دارای اهداف، باورها، قابلیت‌ها و ویژگی‌های خاصی می‌باشد.
1-2-   هوش مصنوعی توزیع شده
در اولین تعاریف ارائه شده برای هوش مصنوعی توزیع شده بیان شده است که این حوزه، زیر مجموعه‌ای از هوش مصنوعی است که به مدل‌های دانش و تکنیک‌های ارتباط و استدلال مورد نیاز عامل‌های محاسباتی هوشمند برای مشارکت در اجتماعی از عامل‌ها می‌پردازد.]11[. در تعاریف دیگر آمده است که هوش مصنوعی توزیع شده، مطالعه، ساخت و بکارگیری سیستم‌هایی است که در آنها چندین عامل در حال تعامل با یکدیگر، مجموعه‌ای از اهداف را دنبال می‌کنند و مجموعه‌ای از وظایف را انجام می‌دهند. ]14[.
در سال 1980 هوش مصنوعی توزیع شده متوجه آن دسته از مسائلی گردید که برای آنها یک حل کننده مسئله و یا یک واحد محاسباتی کافی نیست، بلکه نیاز به همکاری بین موجودیتهای مستقل حل مسائل (عامل‌ها) برای حل اینگونه مسائل می‌باشد. ]12[. این تعریف مورد تغییر و بحث‌‌های بسیاری قرار گرفت که از جمله احتمال وجود چندین وظیفه برای سیستم مطرح شد. در حالی که عامل‌ها ممکن است دارای اهداف ناسازگار نیز باشد. در سال 1981 هوش مصنوعی توزیع شده متوجه وضعیت‌های حل مسئله‌ای گردید که در آنها چندین عامل برای رسیدن به مجموعه‌ای مشترک از اهداف همکاری می‌کنند.
در سال 1983، یک سیستم همکاری حل مسئله به صورت شبکه‌ای توزیع شده از اجتماع عامل‌های نیمه خودمختار معرفی شد که هر کدام قادر به حل مسئله می‌باشند و برای حل یک مسئله با یکدیگر همکاری می‌کنند. ]2[. بر این اساس سیستم هوش مصنوعی توزیع شده، شبکه‌ای از سیستم‌های مجزا و هوشمند است که با یکدیگر همکاری دارند. ]5[. در تعاریف سال‌های اخیر سیستم هوش مصنوعی توزیع شده از تعداد زیادی عامل تشکیل شده است که هر عامل توانایی محدودی در حل مسائل داشته و هوش کلی سیستم نیز نتیجه تعامل‌های بین این عامل‌های با توانایی محدود در نتیجه‌گیری است. البته به نظر می‌رسد که محققین علاقه‌مند به عدم توزیع (به صورت پیوند گرا) بیشتر از این تعریف پیروی می‌کنند و به نظر می‌رسد که همان تعریف اولیه نزدیکی بیشتری با اکثر تعاریف در این زمینه داشته باشد.
در سال 1985 هوش مصنوعی توزیع شده متوجه راه‌حل نتیجه شده از مشارکت مجموعه‌ای از منابع دانش غیر متمرکز و ارتباط بین آنها شد که هر کدام در پردازنده‌ای جدا از هم قرار گرفته‌اند ]13[ . این ارتباط الزاماً یک ارتباط از پیش تعریف شده نمی‌باشد. یکسال بعد، در تعریفی جدید حداقل هوش و نتیجه‌گیری در هوش مصنوعی توزیع شده بدین صورت بیان گردید که سیستم هوش مصنوعی توزیع شده باید حداقل شامل دو عامل باشد. این عامل‌ها دارای درجه‌ای از اطلاعات و خودمختاری در راستای دستیابی به هدف خود بوده و از دیدگاه هوش مصنوعی مهارتهایی نظیر قابلیت استنتاج، برنامه‌ریزی و غیره را از خود بروز می‌دهند.
در سال 1987 هوش مصنوعی توزیع شده، در رابطه با اجتماع، همکاری و تعامل بین عامل‌های هوشمند مستقل برای حل مسائل پیچیده و کلی تعریف گردید. ]10[. در مسائل فرض شد ]6[. در سال 1988 بحث همزمانی در سیستم‌های هوشمند عنوان گردید. ]1[. در جدول 1-1 خلاصه‌ای از تعاریف ارائه شده برای هوش مصنوعی توزیع شده و معیارهایی که در هر تعریف اهمیت داشته‌اند، دیده می‌شوند.
با توجه به تعاریف مطرح شده دیده می‌شود که در اکثر تعاریف هوش مصنوعی توزیع شده به وجود چندین عامل یا موجودیت حل کننده مسئله ارائه شده است که به شکل توزیع شده به منظور خاصی با یکدیگر تعامل دارند. منظور یا مقصود این تعامل می‌تواند حل یک مسئله، انجام یک یا چند وظیفه یا دستیابی به یک یا چند هدف تأیین شده برای اجتماع عامل‌ها باشد. این تعامل نیز می‌تواند به شکل همکاری یا هماهنگی یا یک ارتباط ساده باشد. در رابطه با میزان پیچیدگی عامل‌ها یا موجودیت‌های حل مسئله نیز نظراتی ارائه شده است. بعضی از محققین اعتقاد دارند که عامل‌ها هوشمند بوده و دارای قابلیت‌هایی مانند استدلال و برنامه‌ریزی می‌باشند.