طراحی یک آتوماتای یادگیر جدید برای رنگآمیزی گراف

مسئله رنگآمیزی گراف 1 ، یکی از مسائل ارضاء محدودیت موجود در ادبیات هوشمصنوعی میباشد. رنگآمیزی رأسی عبارت است از تخصیص رنگهایی به رأسهای گراف به قسمی که هیچ دو رأس مجاور، همرنگ نباشد. کمینه عددی )تعداد رنگها( که به این گراف برای رنگآمیزی اختصاص میدهیم را عدد رنگیمینامند، این مسأله از رده مسائل بسیار دشوار 2 است. باتوجه به اهمیت مسأله رنگ آمیزی گراف و کاربردهای فراوان آن، الگوریتمهای فراوانی برای یافتن یکرنگآمیزی مجاز در گراف، پیشنهاد شده است؛ از جمله میتوان به الگوریتمهای دقیق، الگوریتمهای توزیع شده، الگوریتم های موازی، الگوریتمهای تقریبی والگوریتمهای اکتشافی و غیره اشاره کرد. مفهوم آتوماتای یادگیر نخستین بار توسط تستلین 3 مطرح شد. وی به مدلسازی رفتارهای سیستمهای بیولوژیکی علاقمند بود و یک آتوماتای قطعی که در محیطی تصادفی فعالیت میکرد را بعنوان مدلی برای یادگیری معرفی نمود. یکی از کاربردهای آتوماتا در رنگآمیزیگراف میباشد که در این تحقیق از این کاربرد استفاده کردیم.در این تحقیق یک الگوریتم جدید براساس آتوماتای یادگیر ارائه شده تا بتواند با دقت و سرعت بالاتر و همچنین قابلیت یادگیری رئوس گراف را رنگآمیزی کند.روش پیشنهادی نیز دارای نمودار انتقال و عملکرد مجزایی بوده و این روش بر روی گراف با رئوس کم، رئوس زیاد و تعداد رئوس متوسط بررسی شد و در انتها تعداد مراحل انجام کار و مجموع رنگهای مورد استفاده برای رنگآمیزی گراف مشخص با الگوریتمهای بهینهسازی مورد مقایسه قرار گرفت. نتایج ارزیابی نشان دهنده دقت و سرعت عملکرد بهتر روش پیشنهادی نسبت به دیگر روشهای بهینهسازی میباشد.

Keywords:

آتوماتای یادگیر , پاداش , جریمه , رنگآمیزی گراف , نمودار انتقال