انواع پروژه ها و آموزشهای تخصصی مهندسی صنایع و مدیریت, فیلم های آموزشی مباحث مهندسی صنایع و مدیریت
دسته بندی محصولات
کلیک کنید

اطلاعیه فروشگاه

تمامی مطالب و پروژه های موجود در این فروشگاه به صورت کاملا اختصاصی تهیه شده اند، به طوریکه نمونه این پروژه ها به صورت رایگان در محیط اینترنت یافت نمی شود و یا اگر یافت هم شوند به قیمت بیشتر به فروش می رسند. جهت دانلود رایگان آموزش های نرم افزاری مهندسی صنایع و مدیریت به کانال تلگرام ما مراجعه کنید. https://telegram.me/ieproject

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

پروژه درس الگوریتم های فراابتکاری: مساله افرازبندی گراف (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. پیاده سازی الگوریتم منتخب (الگوریتم ژنتیک)


اشتراک بگذارید:


پرداخت اینترنتی - دانلود سریع - اطمینان از خرید

پرداخت هزینه و دریافت فایل

مبلغ قابل پرداخت 15,000 تومان
کدتخفیف:

درصورتیکه برای خرید اینترنتی نیاز به راهنمایی دارید اینجا کلیک کنید


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

نام فایلحجم فایل
Graph-Partitioning-Problem_195712_8468.zip972.7k





پرفروش ترین محصولات