پروژه درس الگوریتم های فراابتکاری: مساله افرازبندی گراف (Graph Partitioning Problem)

مقدمه

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

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

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

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

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

فهرست مطالب

1. مقدمه

1-1. تاریخچه و اهمیت مساله ی افرازبندی گراف

1-2. کاربردهای عملی مساله ی افرازبندی گراف

1. تعریف مساله ی افرازبندی گراف و اصطلاحات مرتبط با آن
2. بررسی درجه ی سختی مساله ی افرازبندی گراف
3. توابع هدف مطرح در مساله ی افرازبندی گراف
4. الگوریتم حل مساله ی افرازبندی گراف

5-1. الگوریتم های حل دقیق

5-1-1. مدل برنامه ریزی عدد صحیح

5-2. الگوریتم تقریبی

5-3. الگوریتم حریصانه

5-3-1. الگوریتم حریصانه ی K-Greedy برای مساله ی افرازبندی گراف

5-4. الگوریتم جستجوی محلی

5-5. الگوریتم فراابتکاری جستجوی ممنوعه

1. به کارگیری یک الگوریتم فراابتکاری؛ از طراحی تا اجرا

6-1. مساله ی MBCP

6-2. پیاده سازی الگوریتم جستجوی محلی

6-3. تجزیه و تحلیل دورنمای فضای مساله

6-4. پیاده سازی الگوریتم منتخب (الگوریتم ژنتیک)

الگوریتم فراابتکاری الگوریتم ابتکاری الگوریتم هیوریستیک افراز بندی گراف پروژه الگوریتم فرا ابتکاری گراف

سجاد یکشنبه 12 اردیبهشت 1395 ساعت 05:52