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

در این مقاله، به منظور حل مساله رنگ آمیزی گراف، روشی فرا ابتکاری برپایه الکوریتم ژنتیک ارائه شده است. کد گذاری مورد استفاده در این مقاله از نوع جهشی می باشد. کروموزوم ارایه شده، آرایه ای به طول تعداد رئوس گراف و هر خانه آن ( که یک ژن می باشد) متناظر با یکی از رئوس گراف است. در این مقاله از یک روش جدید، برای تولید یک نسل اولیه نسبتاً بهینه و یافتن حداقل تعداد رنگ مورد استفاده برای رنگ آمیزی گراف و یک روش نخبه گرا برای حفظ راه حل های بهینه هر نسل استفاده شده است. از ویژگی های الگوریتم ارایه شده می توان به یافتن کوچک ترین عدد رنگی گراف، یافتن حداکثر تعداد پاسخ های بهینه غیر تکراری و عدم وابستگی نسبت به تغییرات گراف ها اشاره کرد.

کلیدواژه ها:

رنگ آمیزی گراف ، الگوریتم ژنتیک ، ژن ، کروموزوم ، نخبه گرایی