بخشی از مقاله
چکیده:
مسئله رنگآمیزی گراف1، یکی از مسائل ارضاء محدودیت موجود در ادبیات هوشمصنوعی میباشد. رنگآمیزی رأسی عبارت است از تخصیص رنگهایی به رأسهای گراف به قسمی که هیچ دو رأس مجاور، همرنگ نباشد. کمینه عددی (تعداد رنگها) که به این گراف برای رنگآمیزی اختصاص میدهیم را عدد رنگی مینامند، این مسأله از رده مسائل بسیار دشوار2 است. باتوجه به اهمیت مسأله رنگآمیزی گراف و کاربردهای فراوان آن، الگوریتمهای فراوانی برای یافتن یک رنگآمیزی مجاز در گراف، پیشنهاد شده است؛ از جمله میتوان به الگوریتمهای دقیق، الگوریتمهای توزیع شده، الگوریتمهای موازی، الگوریتمهای تقریبی و الگوریتمهای اکتشافی و غیره اشاره کرد. مفهوم آتوماتای یادگیر نخستین بار توسط تستلین3 مطرح شد. وی به مدلسازی رفتارهای سیستمهای بیولوژیکی علاقمند بود و یک آتوماتای قطعی که در محیطی تصادفی فعالیت میکرد را بعنوان مدلی برای یادگیری معرفی نمود. یکی از کاربردهای آتوماتا در رنگآمیزی گراف میباشد که در این تحقیق از این کاربرد استفاده کردیم.
در این تحقیق یک الگوریتم جدید براساس آتوماتای یادگیر ارائه شده تا بتواند با دقت و سرعت بالاتر و همچنین قابلیت یادگیری رئوس گراف را رنگآمیزی کند. روش پیشنهادی نیز دارای نمودار انتقال و عملکرد مجزایی بوده و این روش بر روی گراف با رئوس کم، رئوس زیاد و تعداد رئوس متوسط بررسی شد و در انتها تعداد مراحل انجام کار و مجموع رنگهای مورد استفاده برای رنگآمیزی گراف مشخص با الگوریتمهای بهینهسازی مورد مقایسه قرار گرفت. نتایج ارزیابی نشان دهنده دقت و سرعت عملکرد بهتر روش پیشنهادی نسبت به دیگر روشهای بهینهسازی میباشد.
کلمات کلیدی: آتوماتای یادگیر، پاداش، جریمه، رنگآمیزی گراف، نمودار انتقال.
-1 مقدمه
در نظریه گراف، رنگآمیزی گراف یکی از حالتهای خاص مسألههای برچسبگذاری گراف است. رویکرد کلی آن استفاده از نظیر کردن رنگهایی به رأسهاست که این رنگآمیزی محدودیت خاصی را رعایت میکند. در سادهترین حالت، رنگآمیزیای مورد نظر است که در آن هیچ دو رأس مجاوری همرنگ نباشند (رنگآمیزی رأسها) که در این حالت یک جواب قابل قبول محسوب میشود و برای رسیدن به این هدف الگوریتمهای مختلفی وجود دارد. تعریف ریاضی یک
Graph Coloring Problem NP-Complete Tsetlin
1
1
2
3
گراف بصورت زوج مرتب که در آن V مجموعه رئوس و مجموعه یالهای گراف G میباشد که دارای n رأس و m یال میباشد و ماکسیمم درجه رئوس آنرا با نشان میدهیم. مینیمم عددی (تعداد رنگها) که به این گراف برای رنگآمیزی اختصاص میدهیم را عدد رنگی یالی مینامند و با نمایش میدهیم .[1] مسئله رنگآمیزی گراف میتواند معادل مسئله رنگآمیزی یک نقشه با حداقل تعداد رنگ میباشد، بطوری که هیچ دو شهر مجاور نقشه، دارای رنگ یکسان نباشند. از آنجا که جغرافیای یک نقشه را میتوان به شکل یک گراف معادل، در نظر گرفت، درحالات خاص، میتوان روشهای موجود در تئوری گرافها را برای آن، گسترش داد. در عین حال، بسیاری از روشهای سنتی موجود در هوش مصنوعی، برای حل این مسئله، بکار گرفته شده است.[2]
-2 بررسی کارهای گذشته
کاربردهای عملی مسئله رنگآمیزی گراف شامل موارد زیر میشود البته محدود به موارد فوق نمیباشد:
➢ نقشه رنگآمیزی [4]
➢ زمانبندی [5]
➢ تخصیص فرکانس رادیویی [6]
➢ تخصیص رجیستر [7]
➢ تطبیق الگو و سودوکو (جدول اعداد)
روشهای زیادی در گذشته به مسئله رنگآمیزی گراف پرداختند که یکی از مقالاتی که میتوان بدان اشاره کرد به صورت زیر شرح داده میشود:
4 الگوریتم تقریبی هوشمند مبتنی بر آتوماتای یادگیر برای رنگآمیزی گراف با حداقل تعداد رنگ در [8] پیشنهاد شده است. در هر الگوریتم، شبکهای از آتوماتای یادگیر همریخت به گراف داریم که در ابتدا با تخصیص یک آتوماتای یادگیر به رئوس گراف آغاز به کار میکنیم. بعنوان مثال یک شبکه از آتوماتای یادگیر میتواند توسط یک 2 جزئی توصیف شود، که در آن نشان دهنده مجموعهای از آتوماتای یادگیر میباشند و نشان دهنده مجموعهای از اقدامات که در آن مجموعهای از اقدامات که میتوانند بوسیله آتوماتای Ai یاد بگیرند را شرح میدهد، برای هر . مجموعهای از رنگها که به هر رأس Vi میتواند اختصاص داده شود از مجموعه اقدامات آتوماتای یادگیر میتواند گرفته شود. هریک از الگوریتمهای پیشنهاد شده شامل مراحلی میباشد و در هرمرحله، هر آتوماتای یادگیر بصورت تصادفی یکی از رنگها را انتخاب میکند و به رأس متناظر با آن اختصاص میدهد. بنابراین، رنگآمیزی در هر مرحله ایجاد میشود. مجموعهای از رنگها در هر مرحله از مجموعه رنگها انتخاب میشوند سپس، الگوریتم تصمیم میگیرد که آیا رنگآمیزی مجاز هست یا خیر (به جز الگوریتم .(4 در هر مرحله k، کاردینالیتی از حداقل مجموعه رنگها که هنوز یافت نشده است توسط مقدار آستانه دینامیک TK نشان داده میشود. کاردینالیتی از رنگ مجموعه از رنگآمیزی اصلی آورده شده است و سپس با مقدار آستانه دینامیک TK مقایسه میشود. اگر تعداد رنگ گرافهایی با تعداد کمتری از مجموعه رنگهای رنگآمیزی شده بود، سپس توسط محیط پاداش میگیرد و در غیر اینصورت جریمه میشود. رنگهایاصلی مختلف هستند که مکرراً تولید میشوند و بردار احتمال عملگرها به روزرسانی میشود تا زمانی که یک راهحل نزدیک به بهینه پیدا شود و مسئله حداقل رنگها با یک احتمال نزدیک به هدف برسد.
