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

سمینار برای دریافت درجه کارشناسی ارشد M.Sc مهندسی برق - کنترل با عنوان بررسی سیستم های چند عامله با استفاده از تئوری بازی ها

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

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

سیستم های چند عامله

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

- دانش کافی و لازم برای حل مسئله در یک عامل وجود ندارد.

- کنترل سیستم توزیع شده است (یک سیستم کنترلی کلی وجود ندارد)

- داده ها توزیع شده (غیر متمرکز) می باشند.

- محاسبات بصورت غیر همزمان صورت می گیرند.

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

تئوری بازی ها و کاربردهای آن ها درسیستم های چند عامله

مقدمه : همه آثار و ابعاد علوم اثر خود را در زندگی مردم نشان داده اند و تا حدود زیادی هر فرد جایگاه و ثمرات هر علم را با نگاهی به اطراف خود به خوبی می تواند درک و مشاهده کند.

علوم مختلف از جمله علوم اجتماعی، علوم پزشکی ، علوم مهندسی و......هر یک اهمیت خود را در بخشهای مختلف زندگی انسانها نشان داده اند.

حال سوال اساسی این است که نظریه بازیها چه کمکی می تواند بکند و اساسا چرا نظریه بازیها بایستی مطالعه شود.

انسان در هر لحظه در شرایط بازی قرار دارد.مانند بازی فرزندان با والدین، فرد با دوستان، فرد با دشمنان،و......

در مواجه با این تعاملات روزانه با دیگران است که هر فرد به صورت شهودی و شعوری، تجربه و تخصص در انجام بازی را می آموزد.

امروزه برای موفقیت بیشتر در روابط دیپلماسی، تجارت، جنگ و صلح و....مجبور به فراگیری نظری بازیها هستیم.

نظریه بازی ها چیست؟

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

فهرست مطالب پایان نامه

چکیده

مقدمه

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

مقدمه

هوش مصنوعی توزیع شده

حوزه های کاری هوش مصنوعی توزیع شده

دلایل گرایش به هوش مصنوعی توزیع شده

پایه تکنولوژیکی

توزیع ذاتی

مزایای طراحی و پیاده سازی

دلایل معرفت شناسی

بنیاد اجتماعی

همجوشی (کلاس های جدید از مسائل)

مسائل مطرح در هوش مصنوعی توزیع شده

تعریف عامل و عامل های هوشمند

تعریف عامل

عامل به عنوان یک سیستم نرم افزاری

مفهوم عامل از دیدگاه عام

مروری برخصوصیات عامل

ویژگی های دیگر عامل ها

طبقه بندی عاملها

مقایسه عامل با شیء

تفاوت های سیستم مبتنی بر عامل و سیستم های خبره

انواع محیط عامل

قابل دستیابی / غیر قابل دستیابی

محیط قطعی یا غیر قطعی

محیط مقطعی یا غیر مقطعی

محیط ایستا / پویا

محیط گسسته یا پیوسته

سیستم های چند عامله

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

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

نیاز برخی دامنه ها به سیستم های چندعامله:

افزایش سرعت عمل با موازی سازی

قابلیت اطمینان

توسعه پذیری

آسانتر شدن برنامه سازی

آزمون نظریه های سایر رشته های علمی

معماری های ارایه شده برای سیستم های چندعامله

مدل OMG

استاندارد FIPA

استاندارد KAOS

مدل General Magic

سازماندهی سیستم های چندعامله

ساختار سلسله مراتبی

ساختار مسطح

ساختار جزء به کل

ساختار پیمانه ای

پارامترهای مطرح در ارزیابی سیستمهای چندعامله

سیستمهای مقیاس وسیع(Large Scale systems):

کنترل غیر متمرکز : (Decentralized Control)

نتیجه گیری

تئوری بازی ها و کاربردهای آن ها درسیستم های چند عامله

مقدمه

نظریه بازی ها چیست؟

تفاوت میان تصمیم گیری و بازی

طبقه بندی نظریه بازی ها

برخی مفاهیم و اصطلاحات

موارد استفاده از نظریه بازی ها

فرض های اساسی در نظریه بازیها

شاخه های اصلی نظریه بازی ها

بازی های ایستا

نمایش بازی در فرم استراتژیک یا نرمال

فرم ماتریسی بازی

پیدا کردن جواب در بازیهای ایستا

بازیهای رقابتی

بازیهای تصادفی

بازیهای پویا

بازی پویا در فرم بسط یافته

درخت بازی

عناصر فرم بسط یافته:

پیشینه بازی:

مجموعه اطلاعاتی:

استراتژی

پیدا کردن جواب در بازیهای پویا

بررسی روش های یادگیری

یادگیری تقویتی

خط مشی

تابع پاداش

تابع مقدار

مدل برگرفته شده از محیط

اجزای یادگیری تقویتی

اهدافوپاداش

Q-Learning

خاصیتمارکوف

فرآیندتصمیمگیریمارکوف

روش های حل فرآیندهای تصمیم گیری مارکوف

تابعارزش

تابع ارزش بهینه:

فرایند تحلیل سلسله مراتبی (AHP)

ویژگیهای فرایند تحلیل سلسله مراتبی

ساختار سلسله مراتبی

اصول فرایند تحلیل سلسله مراتبی

محاسبه وزن

روشهای محاسبه وزن

روش حداقل مربعات (least squares method)

روش حداقل مربعات لگاریتمی (logarithmic least squares method)

روش بردار ویژه (Eigenvector Method)

روش های تقریبی (Approximation Method)

سازگاری سیستم و ماتریس سازگار

محاسبه نرخ ناسازگاری

نتیجه گیری

مراجع