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

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

Keywords:

ا لگوریتم های ژنتیک , رنگ آمیزی گراف , ژن , کروموزوم , گراف