دانلود مقاله رایگان

پژوهش: پایان نامه ارشد فناوری اطلاعات: بهبود الگوریتم رقابت استعماری در پیدا کردن نقاط تعادل نش مسئله مدیریت بحران

پایان نامه مقطع کارشناسی ارشد رشته فناوری اطلاعات

دانشگاه شیراز

دانشکده آموزش های الکترونیکی

پایان نامه کارشناسی ارشد در رشته مهندسی فناوری اطلاعات (طراحی و تولید نرم افزار)

عنوان:

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

استاد راهنما:

آقای دکتر مصطفی فخراحمد

برای رعایت حریم خصوصی نام نگارنده درج نمی گردد

تکه هایی از متن به عنوان نمونه :

فهرست مطالب:

فصل 1   مقدمه………………………………………………………………………. 1

1-1  مقدمه……………………………………………………………………. 1

1-2  مساله پژوهش…………………………………………………………….. 2

فصل2  مبانی نظری پژوهش……………………………………………………… 6

2-1 مقدمه…………………………………………………………………….. 6

2-2  الگوریتم رقابت استعماری………………………………………………… 6

2-2-1 شکل دهی امپراطوری های اولیه…………………………………… 9

2-2-2 مدلسازی سیاست جذب…………………………………………. 11

2-2-3  جابجایی موقعیت مستعمره و استعمارگر…………………………. 14

2-2-4  قدرت کل یک امپراطوری………………………………………… 15

2-2-5  رقابت استعماری…………………………………………………. 16

2-2-6  سقوط امپراطوری ضعیف………………………………………… 19

2-2-7 همگرایی…………………………………………………………. 20

2-3  نظریه بازی ها…………………………………………………………… 21

2-4  تعادل نش………………………………………………………………. 24

2-4-1  نقطه تعادل نش………………………………………………. 24

2-4-2  الگوریتم تعادل نش…………………………………………………….. 26

2-4-3  بازی غیرهمکارانه و تعادل نش……………………………………… 27

2-5  مسئله مدیریت بحران……………………………………………….. 28

2-6  فرمولاسیون بازی غیرهمکارانه………………………………………….. 30

فصل 3  مروری بر تحقیقات انجام شده…………………………………. 33

3-1  مقدمه…………………………………………………………………… 33

3-2 روش نیچینگ براساس فازی کلاسترینگ……………………………….. 33

3-3  روش پاکسازی بر اساس مفهوم…………………………………………. 36

3-4  روش الگوریتم ژنتیک سلسله مراتبی تطبیقی نیچ………………………. 38

3-5  روش الگوریتم ژنتیک نیچینگ جزیره ای……………………………….. 39

3-6 روش دسته جمعی از الگوریتم های نیچینگ……………………………. 42

3-7 روش سرگردانی…………………………………………………………. 45

3-8 روش جمعیت نخبگان تطبیقی مبتنی بر الگوریتم ژنتیک……………….. 47

3-9 بهینه سازی گروه ذرات…………………………………………………. 50

3-9-1  روش خودکار نیچینگ بهینه سازی گروه ذرات…………………. 53

3-9-2  روش بهینه سازی گروه ذرات با نسبت فاصله اقلیدسی تابع برازندگی 55

3-9-3  روش بهینه سازی گروه ذرات مبتنی بر گونه…………………….. 57

3-9-4 روش بهینه سازی گروه ذرات نیچینگ با جستجوی محلی……….. 57

3-9-5  روش بهینه سازی گروه ذرات نیچینگ ترتیبی تطبیقی…………… 59

3-9-6  روش بهینه سازی گروه ذرات نیچینگ بر پایه همسایگی محلی اصلاح شده…..61

3-10 الگوریتم رقابت استعماری ابزاری برای به دست آوردن نقطه تعادل نش…….. 63

3-11   CMS…………………………………………………………………..

3-12 معماری رویداد محور برای مدیریت مدیریت بحران توزیع شده………………….. 64

3-13 راه حل بازی تک نفره رویداد محور برای تخصیص منابع در محیط چندبحرانه… 65

3-14 مدیریت بحران چند رویدادی با بهره گیری از بازی های غیر همکارانه چند مرحله ای…. 67

فصل 4  الگوریتم پیشنهادی……………………………………………………………. 68

4-1 مقدمه…………………………………………………………………… 68

4-2 نگاهی اختصار به کارهای انجام شده…………………………………….. 68

4-3  الگوریتم پیشنهادی……………………………………………………… 77

4-3-1  تعاریف ………………………………………………………….. 79

4-3-2   مراحل الگوریتم پیشنهادی……………………………………….. 81

فصل 5  نتایج شبیه سازی………………………………………………………… 91

5-1 مقدمه………………………………………………………………….. 91

5-2  تعاریف…………………………………………………………………. 92

شما می توانید مطالب مشابه این مطلب را با جستجو در همین سایت بخوانید                     

5-2-1  نظریه بازی ها…………………………………………………… 92

5-2-2 نقطه تعادل نش………………………………………………….. 94

5-3 مثالی از تابع لیاپانوف……………………………………………………. 95

5-4 نتایج الگوریتم پیشنهادی در یافتن نقاط تعادل نش………………… 99

5-5 نتایج الگوریتم پیشنهادی در حل مسئله مدیریت بحران………………. 103

فصل 6  نتیجه گیری و پیشنهادات……………………………………………………. 136

6-1  نتیجه گیری…………………………………………………………… 136

6-2 پیشنهادات…………………………………………………………….. 136

پیوست 1   کدهای شبیه سازی…………………………………………………… 145

چکیده:

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

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

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

در این پایان نامه مسئله مدیریت بحران به عنوان یک چارچوب نظریه بازی ها فرموله می گردد به طوریکه حوادث به عنوان بازیکنان مدل شده و مرکز پاسخگویی های فوری و اورژانسی به عنوان موقعیت و مکان منابع که با برنامه ریزی، و تخصیص های محتمل به عنوان استراتژی بازی در نظر گرفته می گردد. در این مسئله به هر بحران منابعی را اختصاص میدهیم به صورتی که استراتژیهای تخصیص داده شده به بازیکنان(بحران ها) بهترین ترکیب ممکن باشد و هر ترکیب دیگری وضعیت را به حالت بدتری تغییر دهد که این بهترین ترکیب ها لزوما واحد نیستند ،به این ترکیبات نقطه تعادل نش گوییم و ثابت میکنیم که به ازاء این ترکیب ها تابع لیاپانوف مقدار 0 را برمیگرداند.

فصل اول: مقدمه

1-1- مقدمه

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

از بهینه سازی در نظریه بازی ها بهره گیری میشود؛ نظریه بازی ها یکی از زمینه های ریاضیات می باشد که دارای بیشترین تاثیر در زمینه های اقتصادی و اجتماعی می باشد. دو شاخه اصلی در نظریه بازی هست: نظریه بازی همکارانه و غیر همکارانه.

شما می توانید تکه های دیگری از این مطلب را در شماره بندی انتهای صفحه بخوانید              

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

2-1- مساله پژوهش

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

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

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

در الگوریتم پیشنهادی بهینه ها در غالب امپراطوری های جداگانه پیدا میشوند و بدین طریق از همگرایی زود رس که در نتیجه از دست دادن تنوع گونه ها، ایجاد میشود با زیر جمعیت هایی که بطور جداگانه تکامل پیدا میکنند، اجتناب میشود و در کنار آن، استخراج [4] که روندی رو به همگرایی دارد، را نیز انجام میدهد. برای این کار از یک معیار رشد امپراطوری برای مشخص کردن امپراطوری متزلزل و در حال رشد بهره گیری میشود که در واقع این معیار از جمع شدن کشورها از یک حد آستانه ای در اطراف بهینه ها جلوگیری می ‌کند و به این ترتیب امپراطوری که تکامل خود را تا یک آستانه ای انجام دهد به این معنی می باشد که دارای بهینه ای می باشد و بایستی این بهینه در حافظه خارجی ذخیره گردد.

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

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

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

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

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

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

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

[1] Multi modal

[2] Local Optima

[3] Global Optima

[4] exploit

***ممکن می باشد هنگام انتقال از فایل اصلی به داخل سایت بعضی متون به هم بریزد یا بعضی نمادها و اشکال درج نشود اما در فایل دانلودی همه چیز مرتب و کامل و با فرمت ورد موجود می باشد***

متن کامل را می توانید دانلود نمائید

زیرا فقط تکه هایی از متن پایان نامه در این صفحه درج شده (به گونه نمونه)

اما در فایل دانلودی متن کامل پایان نامه

 با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود می باشد

تعداد صفحه : 176

قیمت : چهارده هزار و هفتصد تومان

 

Comments are closed.