دانلود شبیه سازی مقاله الگوریتم تکاملی برای رنگ آمیزی گراف

الگوریتم پیشرفته برای حل مشکل رنگ آمیزی در گراف

یک گراف غیرقابل هدایت G با یک مجموعه V از رأس ها و مجموعه ای از لبه ها، دارای مشکل رنگ آمیزی گراف  است. این مشکل شامل پارتیشن بندی تمام رأس ها به k مجموعه مستقل و تعداد رنگ های مورد استفاده است که به حداقل تعداد ممکن برسد.

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

در این مقاله الگوریتم پیشرفته  برای حل مسئله رنگ آمیزی گراف ارائه شده است. الگوریتم پیشنهادی MACOL چندین ویژگی برجسته مانند یک اپراتور متقابل چند پدر و مادر (AMPaX) و یک معیار جایگزینی مبتنی بر فاصله و کیفیت برای به روز رسانی را با یکدیگر ادغام می کند.

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

شبیه سازی مقاله در نرم افزار متلب صورت گرفته است.

رنگ آمیزی گراف