مقدمهدر حوزه ی بهینه سازی ترکیباتی با مسائل بسیار مهم و کاربردی آشنا می شویم که هر یک با توجه به درجه ی سختی، در رده ی خاصی از مسائل قرار می گیرند. از جمله ی این مسائل، مساله ی افراز بندی در گراف است که جزو مسائل سخت است و به طور خاص در رده ی مسائل NP-Complete قرار داده می شود و در حالت کلی الگوریتم حلی وجود ندارد که بتواند این مساله را در زمان چندجمله ای حل نماید.از طرف دیگر گرافها معمولا توسط محققان به عنوان یک ابزار کمک کننده در مدلسازی یک مساله و برنامه ی کاربردی استفاده می شوند. بریدن و ساده تر کردن یک گراف به بخشه ای کوچکتر یکی از ترفندهای اساسی در عملگرهای الگوریتم های حل است. تقسیم بندی و یا افرازبندی گراف های بزرگ اغلب به عنوان یک زیرمساله ی مهم در برخی از مسائل کاربردی مطرح می شود. شبیه سازی علمی، شبکه های اجتماعی، شبکه های راه ها و کنترل ترافیک هوایی نمونه هایی از این کاربردهاست.در حالت کلی یک مساله ی افرازبندی در گراف به این صورت است؛ فرض کنید گراف داده شده باشد. هدف تقسیم کردن راس های به زیرمجموعه ی جدا از هم، با اندازه های مساوی است، به طوری که تعداد یال های عبوری بین هر مجموعه ی جدا از هم، کمترین باشد. در شکل نمونه هایی از افرازبندی گراف نشان داده شده است. با توجه به اهیمت مساله ی افرازبندی گراف، طبیعتا روشها و رویکردهای گستردهای برای حل و برخورد با آن وجود دارد. این روش ها، گسترهای از الگوریتم های سادهای همچون الگوریتم جستجوی عرضی تا روشهای پیچیدهای همچون بهینه سازی ترکیبی را شامل می شوند. در این گزارش قصد داریم تا ضمن ارائه ی تعریفی دقیق از مساله ی افرازبندی گراف و بیان تاریخچه و کاربردهای آن به بررسی برخی از الگوریتم های حل این مساله بپردازیم و یک روش حل فراابتکاری را برای حل مساله پیاده سازی نماییم. فرمت فایل: ورد (قابل ویرایش) تعداد صفحات: 40 فهرست مطالب 1-1. تاریخچه و اهمیت مساله ی افرازبندی گراف 1-2. کاربردهای عملی مساله ی افرازبندی گراف 5-1. الگوریتم های حل دقیق 5-1-1. مدل برنامه ریزی عدد صحیح 5-2. الگوریتم تقریبی 5-3. الگوریتم حریصانه 5-3-1. الگوریتم حریصانه ی K-Greedy برای مساله ی افرازبندی گراف 5-4. الگوریتم جستجوی محلی 5-5. الگوریتم فراابتکاری جستجوی ممنوعه 6-1. مساله ی MBCP 6-2. پیاده سازی الگوریتم جستجوی محلی 6-3. تجزیه و تحلیل دورنمای فضای مساله 6-4. پیاده سازی الگوریتم منتخب (الگوریتم ژنتیک)