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

مسئله رنگآمیزی گراف، عبارت است از رنگآمیزی یک گراف بدون جهت، با استفاده از حداقل K رنگ مختلف ، به طوری که هیچ دو راس مجاوری همرنگ نباشند و یکی از قدیمیترین و مشهورترین مسائل در تئوری گراف است که امروزه کاربردهای متعددی در مسائل مختلف دارد. مسئله رنگآمیزی به عنوان یک مسئله NP-Hard است، بنابراین استفاده از روشهای قطعی جهت پیدا کردن جواب قابل قبول برای آن، مناسب نمیباشند. لذا، روشهای هوش مصنوعی و پردازش تکاملی، برای پیدا کردن جواب قابل قبول مورد استفاده قرار میگیرد. در این مقاله یک روش جدید مبتنی بر هوش ازدحامی به نام الگوریتم کلونی زنبور (ABCGC) برای مسئلهی رنگآمیزی گراف ارائه شده است. یکی از الگوریتمهای موجود ارائه شده برای رنگ آمیزی گراف، استفاده از الگوریتم مبتنی بر مورچه (ABAC) برای رنگآمیزی می باشد. از این رو در این مقاله برای ارزیابی الگوریتم پیشنهادی، آن را با الگوریتم مبتنی بر مورچه (ABAC) مقایسه کردیم و نتایج محاسباتی بر روی نمونههای آزمایشی بیانگر بهبود این الگوریتم نسبت به الگوریتم ABAC برای مسئله رنگآمیزی گراف میباشد.

کلیدواژه ها:

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