موازی سازی الگوریتم ژنتیک - تابو برای حل مسئله رنگ آمیزی در گراف

در این مقاله بررسی یک مسئله بهینه سازی ترکیبی خاص (COP) یعنی مسئله رنگ آمیزی گراف (GCP) مد نظر است. برای حل این مسئله ما یک روش موازی برگرفته از یک استراتژی موثر ارائه می دهیم. یک بررسی مختصر در مورد روش های شناخته شده برای حل این مسئله مارا قادر می سازد تا روش خود را که مبتنی بر یک متد ترکیبی است توجیه کنیم. ابتدا مجموعه ای از راه حل های اولیه که به اصطلاح روش رنگ آمیزی RLF نامیده می شود را بررسی می کنیم. سپس دو الگوریتم ژنتیک و جستجوی tabu را ترکیب و پس از آن یک استراتژی موازی سازی بر روی آن اعمال می کنیم. عملکرد روش ما به وسیله یک سری آزمایشات انجام شده بر روی چند پردازنده IBM SP۲ مورد ارزیابی قرار گرفته است. گراف های پردازش شده از دو مجموعه معیار انتخاب شده اند که مجموعه نخست برگرفته از اینترنت و شامل گراف هایی است که اعداد رنگی آنها مشخص است و مجموعه دیگر شامل گراف های تصادفی است تجزیه و تحلیل نتایج ثابت می کند که روش ما اثر بخشی بهتری دارد.کلمات

Keywords:

موازی سازی , رنگ آمیزی گراف , روش ترکیبی , ژنتیک