حل مسائل گسسته توسط الگوریتم بهینه سازی فاخته

با توجه به اين که الگوريتم بهينه سازي فاخته يک الگوريتم جامع و بسيار سريع مي باشد لذا بايد قادر باشد تا انواع مسائل بهينه سازي را حل نمايد. يکي از انواع مسائل گسسته اي که با استفاده از اين الگوريتم حل شده است، مسئله رنگ آميزي گراف است. در نظريه گراف، رنگ آميزي گراف يکي از حالت‌هاي خاص مساله‌هاي برچسب گذاري گراف است. رويکرد کلي آن استفاده از نظير کردن رنگ‌هايي به يال‌ها يا راس‌ها است که اين رنگ آميزي محدوديت خاصي را رعايت نمايد. در ساده ترين حالت، رنگ آميزي مورد نظر است که در آن هيچ دو راس مجاوري هم رنگ نباشند (رنگ آميزي راس‌ها). علاوه بر آن رنگ آميزي يال‌ها نيز به همين صورت تعريف مي شود. رنگ آميزي گراف کاربردهاي زيادي در زمينه‌هاي عملي و تئوري گوناگون دارد. با وجود اين که اين مساله از نظر علمي هنوز در حال رشد و بررسي بيشتر مي باشد، با ظهور جدول سودوکو در بين عموم مردم شناخته و مشهور شده است.

براي حل مسائل بهينه سازي گسسته با الگوريتم بهينه سازي فاخته لازم است تا موقعيت‌هاي سکونت فاخته‌ها از حالت پيوسته به گسسته تبديل شود. ساده ترين روش انجام چنين کاري round گيري از habitat (محل سکونت)‌هاي فاخته‌ها است. سپس با تعريف مناسب تابع هزينه مي توان از الگوريتم بهينه سازي فاخته انتظار داست که کمترين تعداد رنگ‌ها را چنان به راس‌هاي هر گراف دلخواه اختصاص دهد که هيچ گره مجاوري که با يالي بهم وصل هستند داراي رنگ يکساني نباشند. براي اين کار کافيست دو مورد را در تابع هزينه لحاظ کنيم:

  1. در هر تکرار الگوريتم بهينه سازي فاخته به ازاي هر عضو از جمعيت که جواب کانديدي براي حل مساله است، در صورتي که مقدار عددي رنگ اختصاص داده شده به راس‌هاي مجاور يکسان باشد مقدار هزينه اين جواب بايد افزايش داشته باشد. براي اين کار مي توان شمارنده اي در نظر گرفت که به ازاي هر بار نقض اين شرط يک واحد به آن افزوده شود.
  2. با قيد فوق فقط راس‌هاي مجاور که با يالي بهم وصل شده اند داراي رنگ يکساني نخواهند بود ولي شرط استفاده از مينيمم رنگ برآورده نخواهد شد. براي برآورده شدن اين شرط بايد جمله ديگري به تابع هزينه اضافه کينم. اين جمله بدين صورت است که اگر دو راس در گراف داراي رنگ‌هاي يکساني نباشند و بين آن‌ها يالي موجود نباشد آن گاه مقدار تابع هزينه باز هم افزايش خواهد داشت. براي اين کار هم مي توان از شمارنده ي ديگري استفاده کرد.

در نهايت مي توان مقدار دو پارامتر جريمه فوق را با ضرايبي جمع کرده و بعنوان تابع هزينه با الگوريتم بهينه سازي فاخته جهت کمينه سازي ارائه کرد.

پیام بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

46 − forty four =