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

رنگآمیزی گراف یکی از مسائل Np-Complete به شمار میرود. یکی از کاربردهای این مسئله رنگآمیزی نقشهها است. با وجود اینکه این مسأله از نظرعلمی هنوز در حال رشد و بررسی بیشتر میباشد، با ظهور جدول سودوکو در بین عموم مردم شناخته و مشهور شده است. میتوان عمده روشهایی که برایمسأله رنگآمیزی گراف مطرح شدهاند را در یکی از دستههای زیر قرار دهیم:الف روشهای حریصانه -ب روشهای جستجوی محلی -ج روشهای مبتنی بر تبدیل به مسأله بزرگترین مجموعه مستقل –د روشهای تکاملی -تکنیکهای محاسبات تکاملی، برخلاف الگوریتمهای جستجوی متداول، روی یک مجموعه از جوابها در فضای جستجو عمل میکنند و با استفاده از همکاری ورقابتی که بین جوابها ایجاد میکنند، میتوانند خیلی سریع جواب بهینه را برای مسائل بهینهسازی پیچیده پیدا کنند. این تکنیکها به طور عمده از فرایندتکامل در طبیعت الهام گرفته شدهاند که چهار مورد مشهور آن به صورت زیر میباشد: الگوریتم ژنتیک برنامه نویسی تکاملی استراتژ یهای تکاملی برنامه نویسی ژنتیکیسوای این تکنیکهای محاسبات تکاملی الهام گرفته از فرآیند تکامل در طبیعت، یک سری تکنیکهای محاسباتی جدید ابداع شدهاند که رفتار اجتماعی راشبیه سازی کردهاند، نظیر: اجتماع مورچگانPSO عمده دلیلی که میتوان برای رفتار اجتماعی موجودات زنده آورد، بهینگی آن میباشد. به این ترتیب منطقی به نظر میرسد که برای حل مسائل بهینهسازیمهندسی، این رفتارهای اجتماعی را شبیهسازی کنیم. در این مقاله مراحل یادگیری آتوماتا را با تعداد نسل در الگوریتم ژنتیک در یک الگوریتم جدید براساس آتوماتای یادگیر مورد بررسی قرار خواهیم داد

کلیدواژه ها:

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