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

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