الگوريتم نوين جهت رنگ آميزي گراف با استفاده از آتوماتاي يادگير
الگوريتم نوين جهت رنگ آميزي گراف با استفاده از آتوماتاي يادگير
خلاصه مقاله:
رنگ آميزي گراف يكي از مسائل Np-Comlete به شمار مي رود. يكي از كاربردهاي اين مسئله رنگ اميزي نقشه ها است. در اين مقاله يك الگوريتم جديد براي رنگ آميزي گراف با استفاده از آتوماتاي يادگير پيشنهاد ميشود. فرآيند يادگيري با تعدادي از آتوماتاهاي تصادفي شروع ميشود. هر آتوماتا به تنهايي نمايش دهنده يك رنگ آميزي تصادفي ميباشد. با تكرار فرآيند يادگيري رنگ آميزي بهبود مييابد. در مقايسه با الگوريتمهاي ژنتيك، الگوريتم پيشنهادي سريعتر به جواب نزديك به بهينه ميرسد. دليل آن اين است كه الگوريتمهاي ژنتيك به دنبال كروموزوم بهينه از ميان جمعيتها هستند و به جايگاه ژنها در كروموزومها اهميت داده نميشود ولي در الگوريتم پيشنهادي سعي ميشود تا با استفاده از آتوماتاي مهاجرت اشياء جايگاه بهينه ژنها مشخص شود. الگوريتم پيشنهادي در تعداد مراحل تكراريادگيري كمتري در مقابل تعداد نسل الگوريتم ژنتيك به جواب بهينه نزديك ميشود. نتايج شبيهسازي حاصل از الگوريتم پيشنهادي بر روي گرافهاي مطرح با الگوريتم ژنتيك مورد مقايسه قرار گرفته است.
كلمات كليدي:
آتوماتاي يادگير، آتوماتاي مهاجرت اشيا، رنگ آميزي گراف.
|