بخشی از مقاله
چکیده
مسئله رنگآمیزی گراف یک مسئله مشهور ان پی سخت است، که به یافتن تعداد کمینه k رنگ برای رنگآمیزی رأسهای یک گراف اشاره دارد، بطوریکه هر دو رأس متصل شده بوسیله یک یال رنگهای مختلفی داشته باشند. در این مقاله از اتوماتای یادگیر سلولی نامنظم و منطق فازی جهت یافتن عدد رنگی استفاده شده است. الگوریتم تقریبی پیشنهادی با الگوریتمهای تقریبی بلام، کارگر، هالپرین و اتوماتای یادگیر سلولی مقایسه شده است. طبق آزمایشهای انجام گرفته الگوریتم پیشنهادی نتایج بهتری را در مقایسه با الگوریتمهای فوق تولید میکند، بطوریکه عدد رنگی گراف تولید شده با استفاده از این الگوریتم نسبت به دیگر الگوریتمها کمتر است، که نشان از کارآمدی روش پیشنهادی دارد.
واژگان کلیدی: اتوماتای یادگیر سلولی، رنگآمیزی گراف، منطق فازی، سیستم استنتاج فازی
مقدمه
یک -kرنگآمیزی یک گراف، تخصیصی از یکی رنگهای متمایز k به هر یک از رئوس در گراف است، بطوریکه هیچ دو رأس همسایه رنگ یکسانی نداشته باشند. عدد رنگی یک گراف، کوچکترین k است، بطوریکه گراف بتواند -k رنگآمیز باشد. مسئله رنگآمیزی گراف مجموعهای از مسائل زمانبندی را مدلسازی میکند. رنگآمیزی گراف همچنین مرتبط با مسئلههای ترکیبی دیگر از قبیل یافتن مجموعه مستقل بیشینه در یک گراف است. متأسفانه از نقطه نظر الگوریتمی، مسئله رنگآمیزی یک گراف با تعداد کمینه رنگها ان پی سخت است - Karp, 1972 - ، حتی به گراف-هایی با عدد رنگی ثابت کمتر از 3 محدود میشود.
با توجه به اینکه در اکثر کاربردهای رنگآمیزی گراف، یافتن یک راهحل نزدیک به بهینه نیز کافی است، الگوریتمهای تقریبی فراوانی برای رنگآمیزی گراف از جمله الگوریتمهای ویگدرسون - Wigderson, 1983 - ، برگر - Berger - and Rompel, 1990، بلام - Blum, 1991 - ، کارگر - Karger et al, 1998 - و هالپرین - Halperin et al, - 2001 ارائه شده است. در - Enayatzare and Meybodi, 2009 - الگوریتمی بر اساس اتوماتای یادگیر سلولی برای مسئله رنگ آمیزی گراف پیشنهاد گردید که نتایج آن در مقایسه با الگوریتمهای موجود قابل قبول بود. در این مقاله با اقتباس از - Enayatzare and Meybodi, 2009 - الگوریتمی بر اساس اتوماتای یادگیر سلولی نامنظم و منطق فازی برای حل مسأله رنگآمیزی گراف پیشنهاد میگردد. الگوریتم پیشنهادی با الگوریتمهای تقریبی بلام, کارگر، هالپرین و اتوماتای یادگیر سلولی مقایسه میگردد. نتایج آزمایشها نشان میدهد که الگوریتم پیشنهادی در مقایسه با سایر الگوریتمها، نتیجه بهتری حاصل میکند.
اتوماتای سلولی
اتوماتای سلولی - Wolfram, 1983 - در اواخر دهه 1940 توسط ون نیومن مطرح و پس از او توسط ریاضیدانی بنام اولام به عنوان مدلی برای بررسی رفتار سیستمهای پیچیده پیشنهاد شد. اتوماتای سلولی در حقیقت سیستمهای دینامیکی گسستهای هستند که رفتارشان کاملأ بر اساس ارتباط محلی استوار است. در اتوماتای سلولی، فضا بصورت یک شبکه تعریف میگردد که به هر خانه آن یک سلول گفته میشود. زمان بصورت گسسته پیش میرود و قوانین آن بصورت سرتاسری است که از طریق آن در هر مرحله هر سلول، وضعیت جدید خود را با در نظر گرفتن همسایههای مجاور خود بدست میآورد. قوانین اتوماتای سلولی، نحوه تأثیر پذیرفتن سلول از سلولهای همسایه خود را مشخص میکند. یک سلول را همسایه سلول دیگر گوئیم هرگاه بتواند آن را در یک مرحله و بر اساس قانون حاکم تحت تأثیر قرار دهد.
در بدست آوردن وضعیت کنونی سلول علاوه بر وضعیت قبلی سلولهای همسایه، میتوان وضعیت قبلی خود سلول را نیز دخالت داد. در مدلسازی سیستمهای فیزیکی و بیولوژیکی بهوسیله اتوماتای سلولی، گاهی لازم است که قوانین را بصورت احتمالی در نظر بگیریم. رفتار احتمالی را میتوان به عنوان نویز در سیستم تعبیر نمود. یکی از اشکالات اتوماتای سلولی، تعیین فرم قطعی قوانین مورد نیاز برای یک کاربرد خاص است. راهحلهای متفاوتی در برخورد با این مشکلات به نظر میرسد. یکی از این راهحلها حرکت بهسمتی است که به نحوی خود ابزار با گذشت زمان بتواند قوانین مناسب را استخراج کند.
اتوماتای یادگیر
اتوماتای یادگیر - Narendra and Thathachar, 1989 - ، ماشینی است که میتواند تعدادی متناهی عمل را انجام دهد. هر عمل انتخاب شده توسط یک محیط احتمالی ارزیابی میشود و نتیجه ارزیابی در قالب پاسخی مثبت یا منفی به اتوماتا داده میشود و اتوماتا از این پاسخ در انتخاب عمل بعدی تاثیر میگیرد. هدف نهایی این است که اتوماتا یاد بگیرد تا از بین اعمال خود بهترین عمل را انتخاب کند. بهترین عمل، عملی است که احتمال دریافت پاداش از محیط را به حداکثر برساند. اتوماتای یادگیر با ساختار متغیر را میتوان توسط چهارتایی - α, β, p, T - نشان داد که α = {α1' …' α r} مجموعه عملهای اتوماتا، β = { β1' …' βm} مجموعه ورودیهای اتوماتا، p = {p1' …' pr} بردار احتمال انتخاب هر یک از عملها و p - n+1 - = T[α - n - , β - n - , p - n - ] الگوریتم یادگیری میباشد. الگوریتم زیر یک نمونه از الگوریتمهای یادگیری خطی است. فرض کنید عمل αi در مرحله nام انتخاب شود.در روابط فوق، a پارامتر پاداش و b پارامتر جریمه میباشند. با توجه به مقادیر a و b سه حالت زیر را میتوان در نظر گرفت. زمانیکه a و b با هم برابر باشند، الگوریتم را LRP مینامیم، زمانیکه b از a خیلی کوچکتر باشد، الگوریتم را LRεP مینامیم و زمانیکه b مساوی صفر باشد الگوریتم را LRI مینامیم . - Thathachar and Sastry, 2002 -
اتوماتای یادگیر سلولی
بسیاری از مسائل را نمیتوان با استفاده از یک اتوماتای یادگیر تنها حل کرد، بلکه قدرت اصلی اتوماتای یادگیر زمانی آشکار میشود که آنها به صورت دسته جمعی بکار روند. با توجه به این مسأله و ضعفهای عنوان شده برای اتوماتای سلولی، با ترکیب دو مدل اتوماتای سلولی و اتوماتای یادگیر، مدل جدیدی با نام اتوماتای یادگیر سلولی ایجاد گردید . - Meybodi et al, 2003 - در واقع یک اتوماتای یادگیر سلولی، یک اتوماتای سلولی است که هر سلول آن به یک یا چند اتوماتای یادگیر مجهز شده است. تعریف رسمی اتوماتای یادگیر سلولی در - Beigy and Meybodi, 2004 - آمده است. عملکرد اتوماتای یادگیر سلولی را میتوان به شرح زیر بیان کرد. در هر لحظه هر اتوماتای یادگیر در اتوماتای یادگیر سلولی یک عمل از مجموعه اعمال خود را انتخاب میکند. این عمل میتواند بر اساس مشاهدات قبلی و یا به صورت
