چند رنگ آمیزی پهنای باند در گراف مبتنی بر اتاماتای یادگیر سلولی

در این مقاله، الگوریتمی مبتنی بر اتاماتای یادگیر سلولی نامنظم برای حل مسائل رنگ آمیزی پهنای باند گراف و چند رنگ آمیزی پهنای باند گراف پیشنهاد می گردد. در الگوریتم پیشنهادی ابتدا گراف ورودی تبدیل به گراف پایه می گردد و سپس به هر یک از رئوس گراف، یک سلول متناظر می شود و همچنین به هر سلول، یک اتاماتای یادگیر اختصاص می یابد. هر یک از اتاماتای یادگیر، یک عمل از مجموعه اعمال خود را با توجه به بردار احتمال مربوطه انتخاب می کند. اگر قدر مطلق تفاضل عمل انتخابی یک سلول نسبت به تمامی همسایگانش بزرگتر یا مساوی وزن یال مرتبط بین آن دو باشد، در این صورت به عمل انتخابی این سلول پاداش داده می شود و در غیر این صورت سلول جریمه می شود. الگوریتم تا زمانی ادامه می یابد که تمام سلول ها پاداش بگیرند. الگوریتم پیشنهادی، با الگوریتم موجود همچون لیم، پرستویچ و مالاگوتی مقایسه شده و طبق نتایج بدست آمده بر روی گراف های نمونه نشان داده می شود که الگوریتم پیشنهادی نتایج به مراتب بهتری را تولید می کند.

کلیدواژه ها:

مساله چند رنگ آمیری گراف ، مساله رنگ آمیزی پهنای باند گراف ، اتاماتای یادگیر سلولی