الگوریتم ژنتیک با جهش آشوبی هوشمند و ترکیب چند‌نقطه‌ای مکاشفه‌ای برای حل مسئله رنگ‌آمیزی گراف

تخصیص مقدار رنگی را به هر یک از گره های گراف، به گونه ای که هیچ دو گره مجاوری دارای رنگ یکسانی نباشد و کمترین مقدار رنگی استفاده شود، مسئله رنگ آمیزی گراف گویند. این مسئله به عنوان یکی از مسائل nphard شناخته می شود که کاربردهای مختلفی در زمینه تخصیص پهنای باند، اختصاص حافظه به برنامه ها و همچنین، طراحی مدارهای مجتمع دارد. در مقاله حاضر، از الگوریتم ژنتیک و پدیده آَشوب برای حل این مسئله استفاده شده است. در روش پیشنهادی حاضر، عمل گر ترکیب چند نقطه ای مکاشفه ای به نام cmhn معرفی شده است. این عمل گر، با انتخاب چند نقطه برش در والدین و معتبر کردن یکی از زیر بخش های والدین (دومین زیربخش هر والد می تواند معتبر یا غیر معتبر باشد) آنها را با هم، با استفاده از روشی ابتکاری ترکیب می کند. برای اینکه بتوان از بهینه محلی فرار کرد و همچنین، برای یافتن فضای جستجوی جدید، از عمل گر جهش استفاده می شود. در این مقاله، عمل گر جهش آشوبی هوشمند معرفی شده است که با استفاده از فرمولی گره هایی را که برای جهش مناسب ترند، انتخاب و بر روی آنها جهش را اعمال می کند. همچنین، نیمی از جمعیت اولیه با استفاده از روش ابتکاری و نیمی از آن با روش تصادفی تولید شده است. به منظور ارزیابی الگوریتم پیشنهادی از نمونه گراف های dimacs و queen استفاده شده است. نتایج به دست آمده نشان می دهد که روش پیشنهادی در بیش تر گراف ها، به خصوص گراف های بسیار بزرگ (wap) و گراف های queen جواب بهتری نسبت به تحقیقات مشابه ارائه می دهد.