مسائلی که در آنها چند نقطه بهینه وجود دارد و همه این نقاط به راه حل مسئله کمک کند، یک مسئله بهینه سازی چندگانه است. در بهینه سازی چندگانه کاربر دانش بیشتری درباره راه حل های مختلف در فضای جستجو بدست می آورد و این کمک می کند تا در مواقعی که راه حل فعلی مقدور نباشد از راه حل دیگری استفاده نماید.هدف روشهای بهینه سازی حفظ تنوع در جمعیت و تمایز بین گروه جوابها می باشد. همچنین محاسبه نقاط تعادل نش در بازی های چند نفره غیر همکارانه از جمله محاسبات دشوار می باشد. در بازی ها با بیشتر شدن تعداد بازیکنان و استراتژی آنها و همچنین افزایش نقاط تعادل بازی ، الگوریتم های ریاضی با توجه به مشکل شدن محاسبات ، قادر به شناسایی تمام نقاط تعادل در یک زمان نیستند . الگوریتم های تکاملی ابزار جستجوی قدرتمندی برای حل اینگونه مسائل بهینه سازی هستند .یکی از مسائل مهم و پیچیده که جامعه شهروندی با آن رو به روست، تخصیص بهینه منابع برای موارد اورژانسی در صورت وقوع بحران های متعدد در محیط شهری است ، خصوصا هنگامیکه این منابع محدودیت هایی نیز داشته باشد. بنابراین تخصیص واحد های پاسخگویی به روشی مناسب بر اساس اتفاقات و نیاز های دوره بحران بسیار مهم می باشد.الگوریتم پیشنهادی، بهبود الگوریتم رقابت استعماری در پیدا کردن نقاط تعادل نش مسئله مدیریت بحران است. در این الگوریتم، بهینه ها در غالب امپراطوری های جداگانه ای که در حال تکامل هستند جستجو میشوند. برای این کار از یک معیار رشد امپراطوری برای مشخص کردن رشد امپراطوری ها در دهه های تکامل استفاده میشود و بدین شکل امپراطوری متزلزل و در حال رشد مشخص میشود و به این ترتیب امپراطوری که تکامل خود را تا یک آستانه ای انجام دهد به این معنی است که دارای بهینه ای است و باید این بهینه در حافظه خارجی ذخیره گردد و امپراطوری که رشد نکند، متزلزل است و در آن انقلاب رخ میدهد و ازهم پاشیده میشود، بعد از چندین تکرار الگوریتم ، جوابهای ذخیره شده در حافظه تمام بهینه های مسئله را شامل میشوند.در این پایان نامه مسئله مدیریت بحران به عنوان یک چارچوب نظریه بازی ها فرموله می شود به طوریکه حوادث به عنوان بازیکنان مدل شده و مرکز پاسخگویی های فوری و اورژانسی به عنوان موقعیت و مکان منابع که با برنامه ریزی، و تخصیص های محتمل به عنوان استراتژی بازی در نظر گرفته می شود. در این مسئله به هر بحران منابعی را اختصاص میدهیم به صورتی که استراتژیهای تخصیص داده شده به بازیکنان(بحران ها) بهترین ترکیب ممکن باشد و هر ترکیب دیگری وضعیت را به حالت بدتری تغییر دهد که این بهترین ترکیب ها لزوما واحد نیستند ،به این ترکیبات نقطه تعادل نش گوییم و ثابت میکنیم که به ازاء این ترکیب ها تابع لیاپانوف مقدار 0 را برمیگرداند.فهرست مطالب عنوان......................................... صفحهفصل 1مقدمه............. 11-1 مقدمه........................................................................... 11-2 مساله تحقیق.............................................................. 2فصل2مبانی نظری تحقیق............................................................. 62-1 مقدمه........................................................................... 62-2 الگوریتم رقابت استعماری.................................... 62-2-1 شکل دهی امپراطوری های اولیه................... 92-2-2 مدلسازی سیاست جذب....................................... 112-2-3 جابجایی موقعیت مستعمره و استعمارگر.. 142-2-4 قدرت کل یک امپراطوری................................ 152-2-5 رقابت استعماری.............................................. 162-2-6 سقوط امپراطوری ضعیف................................... 192-2-7 همگرایی............................................................. 202-3 نظریه بازی ها........................................................ 212-4 تعادل نش................................................................... 242-4-1 نقطه تعادل نش..................... 242-4-2 الگوریتم تعادل نش................. 262-4-3 بازی غیرهمکارانه و تعادل نش....... 272-5 مسئله مدیریت بحران................. 282-6 فرمولاسیون بازی غیرهمکارانه........................... 30فصل 3مروری بر تحقیقات انجام شده...................................... 333-1 مقدمه......................................................................... 333-2 روش نیچینگ براساس فازی کلاسترینگ................ 333-3 روش پاکسازی بر اساس مفهوم........................... 363-4 روش الگوریتم ژنتیک سلسله مراتبی تطبیقی نیچ383-5 روش الگوریتم ژنتیک نیچینگ جزیره ای......... 393-6 روش دسته جمعی از الگوریتم های نیچینگ..... 423-7 روش سرگردانی.......................................................... 453-8 روش جمعیت نخبگان تطبیقی مبتنی بر الگوریتم ژنتیک 473-9 بهینه سازی گروه ذرات........................................ 503-9-1 روش اتوماتیک نیچینگ بهینه سازی گروه ذرات 533-9-2 روش بهینه سازی گروه ذرات با نسبت فاصله اقلیدسی تابع برازندگی....................................................................... 553-9-3 روش بهینه سازی گروه ذرات مبتنی بر گونه573-9-4 روش بهینه سازی گروه ذرات نیچینگ با جستجوی محلی 573-9-5 روش بهینه سازی گروه ذرات نیچینگ ترتیبی تطبیقی 593-9-6 روش بهینه سازی گروه ذرات نیچینگ بر پایه همسایگی محلی اصلاح شده....................................................................... 613-10 الگوریتم رقابت استعماری ابزاری برای به دست آوردن نقطه تعادل نش633-11 CMS............................................................................ 633-12 معماری رویداد محور برای مدیریت مدیریت بحران توزیع شده 643-13 راه حل بازی تک نفره رویداد محور برای تخصیص منابع در محیط چندبحرانه................................ 653-14 مدیریت بحران چند رویدادی با استفاده از بازی های غیر همکارانه چند مرحله ای......................... 67فصل 4الگوریتم پیشنهادی.......................................................... 684-1 مقدمه......................................................................... 684-2 نگاهی خلاصه به کارهای انجام شده.................. 684-3 الگوریتم پیشنهادی............................................... 774-3-1 تعاریف ............................................................. 794-3-2 مراحل الگوریتم پیشنهادی.......................... 81فصل 5نتایج شبیه سازی.............................................................. 915-1 مقدمه....................................................................... 915-2 تعاریف..................................................................... 925-2-1 نظریه بازی ها.............................................. 925-2-2 نقطه تعادل نش................................................ 945-3 مثالی از تابع لیاپانوف.................................... 955-4 نتایج الگوریتم پیشنهادی در پیدا کردن نقاط تعادل نش 995-5 نتایج الگوریتم پیشنهادی در حل مسئله مدیریت بحران 103فصل 6نتیجه گیری و پیشنهادات............................................. 1366-1 نتیجه گیری............................................................ 1366-2 پیشنهادات.............................................................. 136پیوست 1 کدهای شبیه سازی...................... 145فهرست شكل‌ها عنوان......................................... صفحهشكل شماره 1: فلوچارت الگوريتم رقابت استعماری............ 8شكل شماره 2: اجزاي اجتماعي سياسي تشکيل دهنده يک کشور9شكل شماره 3: چگونگي شکل‌گيري امپراطوري‌هاي اوليه.... 11شكل شماره 4: شماي کلي حرکت مستعمرات به سمت امپرياليست. 12شكل شماره 5: حرکت واقعي مستعمرات به سمت امپرياليست 13شكل شماره 6: تغيير جاي استعمارگر و مستعمره............ 15شكل شماره 7: کل امپراطوري، پس از تغيير موقعيت‌ها. 15شكل شماره 8: امپراطوري‌هاي بزرگ‌تر، با احتمال بيشتري، مستعمرات امپراطوري‌هاي ديگر را تصاحب مي‌کنند......................... 16شكل شماره 9: سقوط امپراطوري ضعيف................................. 20شكل شماره 10: شماي کلي الگوريتم توسعه داده شده.... 21شكل شماره 11: چرخه مدیریت بحران..................................... 29شکل شماره 12: سناریو اتفاقات چندگانه یک بحران... 30شكل شماره 13:ساختار استراتژی GASH-FC........................... 35شكل شماره 14: گام های اصلی در روش پاکسازی بر اساس مفهوم 37شكل شماره 15:الگوریتم ژنتیک جزیره ای- توپولوژی حلقه ای 41شكل شماره 16: الگوریتم ژنتیک جزیره ای- توپولوژی همسایگی 41شكل شماره 17: الگوریتم ژنتیک جزیره ای- توپولوژی شبکه ای 41شكل شماره 18: فلوچارت روش دسته جمعی.............................. 44شكل شماره 19: حالتهای دو جواب نسبت به یکدیگردر حالت کلی 47شكل شماره 20: حالتهای دو جواب نسبت به یکدیگردر حالت فلات 48شكل شماره 21: مثالی از تشخیص حرکت جواب ها................. 49شكل شماره 22: تکرار 5 الگوریتم......................................... 54شكل شماره 23: تکرار 15 الگوریتم....................................... 54شكل شماره 24: ضعف در توانایی تنظیم خوب یک Ibest استاندارد 58شكل شماره 25: الگویی از تابع تپه دره............................ 60شکل شماره 26: Infospheres.......................................................... 65شكل شماره 27: شمای کلی اجرای مراحل الگوریتم پیشنهادی78شكل شماره 28: مثالی از میزان رشد امپراطوری............... 80شكل شماره 29: تقسیم کشورها در بین امپراطوری ها...... 82شكل شماره 30: شمای کلی حرکت کشورهای مستعوره به سمت فرمانروایی83شكل شماره 31: حرکت واقعی مستعمرات به سمت فرمانروایی 83شكل شماره 32: تغییر جای فرمانروایی و مستعمرات........ 85شكل شماره 33: الگویی از تابع تپه دره.......................... 88شكل شماره 34: شمای تصویری ساختار کلی الگوریتم پیشنهادی 90شكل شماره 35:سناریو بحران ها......................................... 104شکل شماره 36:سود بازیکنان در تخصیصات بیمارستان در نرم افزار Gambit..................................................................................... 133شکل شماره 37: نقاط تعادل نش در تخصیصات بیمارستان در نرم افزار Gambit..................................................................................... 134 فهرست جدول‌ها عنوان......................................... صفحهجدول شماره 1: مقایسه پیچیدگی روش های نیچینگ............ 28جدول شماره 2: منابع موردنیاز بحران ها (بازیکنان)31جدول شماره 3: منابع موجود در دسترس.............................. 32جدول شماره 4: درجه اولویت بحران ها.............................. 32جدول شماره 5: زمان رسیدن به بحران ها......................... 32جدول شماره 6: مثال بازی دو نفره.................................... 96جدول شماره 7: نقاط تعادل نش خالص بازی دو نفره...... 96جدول شماره 8: جدول سود بازی1........................................... 99جدول شماره 9: پارامترهای الگوریتم پیشنهادی.......... 100جدول شماره 10: پارامترهای الگوریتم PSO وDE ........ 100جدول شماره 11: تعداد نقاط نش پیدا شده توسط الگوریتم ها در بازی 1............................................................................................... 101جدول شماره 12: تعداد نقاط نش پیدا شده توسط الگوریتم ها در بازی 2............................................................................................... 101جدول شماره 13: تعداد نقاط نش پیدا شده توسط الگوریتم ها در بازی 3............................................................................................... 102جدول شماره 14: تعداد نقاط نش پیدا شده توسط الگوریتم ها در بازی 4............................................................................................... 102جدول شماره 15: منابع موجود .................... 105جدول شماره 16: انواع حوادث و درخواست ها........ 105جدول شماره 17: اولویت حوادث.................... 105جدول شماره 18: سود بازیکنان از تخصیصات مرکز پلیس107-110جدول شماره 19: نقاط تعادل نش مرکز پلیس................... 110جدول شماره 20: حل تابع لیاپانوف برای مرکز پلیس110-113جدول شماره 21: سود بازیکنان از تخصیصات آتش نشانی114-118جدول شماره 22: نقاط تعادل نش آتش نشانی................... 118جدول شماره 23: حل تابع لیاپانوف برای آتش نشانی119-122جدول شماره 24: سود بازیکنان از تخصیصات بیمارستان124-128جدول شماره 25: نقاط تعادل نش بیمارستان................... 128جدول شماره 26: حل تابع لیاپانوف برای بیمارستان128-133جدول شماره 27: نتایج روش پیشنهادی در مقابل نرم افزار Gambit با اجرا در 20 دقیقه............................ 135 1- فصل اول: مقدمه 1-1-مقدمه بدست آوردن بهترین نتیجه ممکن برای یک مساله با توجه به شرایط حاکم بر آن را، بهینه سازی می گویند. در مسائل بهینه سازی در دنیای واقعی، گاهی اوقات فقط یک راه حل بهینه کافی نیست. وقتی چند جواب بهینه برای مساله وجود دارد، تقاضا برای راه حل های مختلف حساسیت بیشتری پیدا میکند. بسیاری از مسائل در دنیای واقعی یک فضای جستجوی راه حل با تعدادی پاسخ های نابرابر دارند که گاهی باعث گمراهی روش های تکاملی می گردد. در چنین مسائلی که چند نقطه بهینه وجود دارد، چنانچه همه این نقاط به راه حل مسئله کمک نمایند با یک مسئله چندگانه [1] مواجه شده ایم که هر کدام از این نقاط یک بهینه محلی[2] نامیده شده و بزرگترین آنها را بهینه سراسری[3] می گویند کهممکن است بهینه های محلی نیز به اندازه بهینه های سراسری در انتخاب راه حل بهتر، مفید باشند. در بهینه سازی چندگانه کاربر دانش بیشتری درباره راه حل های بهینه مختلف در فضای جستجو بدست آورده و این کمک می کند تا در مواقعی که راه حل فعلی بنا بر بعضی ملاحظات( مانند برخی قیود فیزیکی)، مقدور نباشد از راه حل دیگری استفاده نمایدحتی گاهی داشتن چندين راه حل مي تواند خواص پنهان مربوط به فضاي مسئله را روشن نمايد.از بهینه سازی در نظریه بازی ها استفاده میشود؛ نظریه بازی ها یکی از زمینه های ریاضیات است که دارای بیشترین تاثیر در زمینه های اقتصادی و اجتماعی می باشد. دو شاخه اصلی در نظریه بازی وجود دارد: نظریه بازی همکارانه و غیر همکارانه.به طور عمده ، بازیهای ایستا ،بازیهای با حرکت همزمان بازیکنان هستند.در بازیهای ایستا،همه بازیکنان در یک لحظه استراتژیهای خود را اتخاذ میکنند و بنابراین هنگام تصمیم گیری ،هیچ اطلاعی راجع به انتخاب و تصمیم رقبای خود ندارند . بازیهای ایستای غیر همکارانه از تعامل افراد هوشمند با یکدیگر که در تلاش برای دستیابی به اهداف خود هستند ، تشکیل میشود . حل بازی های چند نفره که دارای نقاط تعادل نش متعدد هستند از کارهای دشوار است که مقایسه ای بین روشهای هوشمند در بدست آوردن نقاط تعادل نش انجام شده است. 1-2-مساله تحقیق کارکرد روش های موجود برای بهینه سازی چندگانه به معیاری وابسته است، که این معیار از فاصله دو بهینه از یکدیگر بدست می آید، این معیار در روش های مختلف نام های متفاوتی همچون معیار شباهت، شعاع اشتراک، شعاع پاکسازی، حداقل فاصله مجاز، فاصله گونه و شعاع نیچ دارد که در تمامی این روش ها تخمین این پارامتر، نیاز به اطلاعات قبلی از تابع بهینه سازی همچون تعداد و توزیع بهینه ها در فضای مسئله دارد، در صورتی که این اطلاعات از تابع بهینه سازی وجود نداشته باشد، تخمین نامناسب این پارامتر کارایی روش ها را در پیدا کردن تمام بهینه ها با خطا روبرو میکند.در روش هایی در بهینه سازی چندگانه که خروجی روش، جمعیتی از جوابها است نیاز به مکانیزمی است، تا از روی این جمعیت خروجی، تعداد بهینه های پیدا شده استنباط شود و این مکانیزم علاوه بر نیاز به پردازش بیشتر باز هم وابسته به فاصله دو بهینه از یکدیگر است. همچنین خروجی یک روش به شکل جمعیتی از جوابها، میزان کنترل ما را بروی مراحل اجرای روش، از نظر تعداد بهینه های پیدا شده در حین اجرا، محدود میکند.در این روش ها نياز به نگهداري جمعيت پایدار در اطراف هر بهينه است که در آن باید این جمعیت پایدار تا انتهای روش حفظ شود، این نگهداری از جمعیت پایدار میتواند با تغییر در اپراتور های الگوریتم های تکاملی و یا ذخیره آن در حافظه صورت گیرد.علاوه بر آن در روش هایی که مبتنی بر زیر جمعیت هستند، استفاده از مکانیزم الگوریتم تکاملی که دارای مکانیزم مناسب برای جستجوی فضای مسئله و همچنین دارای نرخ همگرایی سریع است، میتواند باعث جستجوی بهتر و سرعت رسیدن به جوابها در زیر جمعیت ها باشد.در الگوریتم پیشنهادی بهینه ها در غالب امپراطوری های جداگانه پیدا میشوند و بدین طریق از همگرایی زود رس که در نتیجه از دست دادن تنوع گونه ها، ایجاد میشود با زیر جمعیت هایی که بطور جداگانه تکامل پیدا میکنند، اجتناب میشود و در کنار آن، استخراج [4]که روندی رو به همگرایی دارد، را نیز انجام میدهد. برای این کار از یک معیار رشد امپراطوری برای مشخص کردن امپراطوری متزلزل و در حال رشد استفاده میشود که در واقع این معیار از جمع شدن کشورها از یک حد آستانه ای در اطراف بهینه ها جلوگیری میکند و به این ترتیب امپراطوری که تکامل خود را تا یک آستانه ای انجام دهد به این معنی است که دارای بهینه ای است و باید این بهینه در حافظه خارجی ذخیره گردد.در الگوریتم پیشنهادی نياز به نگهداري جمعيت پایدار در اطراف هر بهينه اي كه پيدا مي شود، وجود ندارد زیرا فقط مكان یک جواب که نشان دهنده یک بهینه است، نگهداری میشود و به همین علت که، هر جواب ذخیره شده در حافظه نشان دهنده یک بهینه است، نیاز به مکانیزمی که با استفاده از آن، تعداد بهینه ها از روی زیرجمعیت ها استنباط شود، وجود نخواهد داشت.بنابراین الگوریتم پیشنهادی مبتنی بر زیر جمعیت است و استفاده از مکانیزم الگوریتم تکاملی مانند رقابت استعماری که نشان داده است دارای مکانیزم مناسب برای جستجوی فضای مسئله و همچنین دارای نرخ همگرایی سریع است میتواند باعث جستجوی بهتر و سرعت رسیدن به جوابها در زیر جمعیت ها باشد و همچنین، الگوریتم پیشنهادی در ترکیب با الگوریتم تپه نوردی قرار میگیرد تا بدین صورت بعد از چندین تکرار مشخص، جوابهای ذخیره شده در حافظه با کمترین هزینه محاسباتی به مراکز بهینه ها برسند.