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

مسأله رنگ آمیزی گراف عبارت است از انتساب یک رنگ به هر یک از رئوس گراف به طوریکه به هر دو رأس مجاور دلخواه از گراف، رنگ های متفاوتی اختصاص داده شود. مسأله رنگ آمیزی گراف از شناخته شده ترین مسائل NP-hard می باشد و به همین دلیل از الگوریتمهای تکاملی جهت حل این مسأله استفاده می شود. در این مقاله از الگوریتم جستجوی الکترومغناطیس نما که مکانیزم تئوری جذب – دفع الکترومغناطیس را تقلید و شبیه سازی می کند، برای حل مسأله رنگ آمیزی گراف استفاده شده است. الگوریتم جستجوی الکترومغناطیس نمای راهبری شده، می تواند از دام بهینه محلی که یکی از مشکلات اساسی الگوریتم جستجوی الکترومغناطیس نما است، بگریزد و موجب حصول پاسخ های بهتر در زمان مناسب تر شود. در انتها نتایج اجرای پیاده سازی الگوریتم جستجوی الکترومغناطیس نمای راهبری شده، با الگوریتم پایه آن مقایسه شده و کارایی بهتر آن مشخص می شود.

Keywords:

رنگ آمیزی گراف , الگوریتم جستجوی شبیه سازی الکترومغناطیس نما