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

یکی از مسایل پرکاربرد در بهینه سازی ترکیبیاتی، مساله رنگ آمیزی گراف می باشد. رنگ آمیزی گراف بدون جهت G(V,E) عبارت است از اختصاص رنگ به ریوس G طوری که ریوس مجاور همرنگ نباشد. در واقع می خواهیم مجموعه ی V را به K بخش افراز کنیم طوری که هر دو راس مجاور در یک بخش نباشد. K را عدد رنگی گراف می نامیم اگر حداقل مقدار ممکن را داشته باشد . یافتن این رنگ آمیزی برای گراف G به مسیله ی رنگ آمیزی گراف معروف است. که در رده ی مسایل Np-hard قرار دارد. در این پژوهش، برای حل مسیله مذکور،یک الگوریتم تکاملی دوجانبه ارایه شده است. این الگوریتم را می توان به طور کلی، ترکیبی از الگوریتم ژنتیک با یک روش جستجوی ممنوع ، در نظر گرفت. حجم محاسبات مربوط به حل مسیله با روش توسعه یافته در این پژوهش و نتایج بدست آمده، نشان می دهد که روش توسعه یافته، دارای مزیت چشمگیری نسبت به روشهای متعارف میباشد و میتوان از آن در حل مسایل بهینه سازی پیچیده، استفاده نمود.