کتاب کلونی زنبورعسل و ژنتیک در تخصیص درجه دوم

فهرست
عنوان صفحه
مقدمه 11
فصـل اول 15
الگوریتم ABC 19
مطالعات 21
فصـل دوم 29
روش مطالعه 29
جستجوی تابو 33
تنظیم اندازه لیست تابو و مقدار تنفس 34
ارزیابی سریع راه حل های همسایه 36
الگوریتم ABC موازی برای QAP 39
فصـل سوم 45
نتایج ارزیابی عملکرد الگوریتم های پیشنهادی 45
تأثیر افزایش تعداد پردازنده ها 46
تنظیم تعداد اکتشافات 48
نتایج اجرای مسائل نمونه در QAPLIB 50
تحلیل نظری الگوریتمهای پیشنهادی 57
فصـل چهارم 59
نتیجه گیری و کارهای آینده 59
منـابع و مآخـذ 63

الگوریتم کلونی زنبور عسل

مساله تخصيص درجه دوم (QAP) يكي از مسائل بهينه سازي تركيباتي متعلق به كلاس مسائل NP-hard بوده كه داراي كاربردي وسيع در جايابي تجهيزات طراحي مدارهاي VLSI، طراحي صفحه كليد، طراحي بردهاي كنترلي و ساير علوم مهندسي است. تاكنون تلاش هاي بسياري براي حل مساله تخصيص درجه دوم صورت پذيرفته و الگورتيم هاي بسياري براي دست يابي به جواب هاي بهينه و نزديك به آن توسعه داده شده است كه الگوریتم زنبور عسل نيز يكي از آنهاست. اين تحقيق تلاشي جامع تر در حل مساله QAP با استفاده از الگوریتم زنبور عسل ضمن لحاظ نمودن توسعه هاي اخير آن با هوش مصنوعی است.

بهينه سازي كلوني زنبور^[1] (يا به اختصار BCO) به طور كلي به مجموعه اي از الگوريتم هاي فرامكاشفه اي مبتني بر هوش دست جمعي اطلاق مي شود كه با الهام گيري از زندگي اجتماعي زنبورها براي حل دسته ي خاصي از مسائل بهينه سازي ابداع شده اند. همانند بهينه سازي كلوني مورچه، بهينه سازي كلوني زنبور نيز اساساً يك روش بهينه سازي مبتني بر احتمالات است. امروزه از بهينه سازي كلوني زنبور در حل مسائل بهينه سازي پيوسته از قبيل آموزش شبكه هاي عصبي، طراحي بهينه ي اجزاي مكانيكي و الكترونيكي و نيز در حل مسائل بهينه سازي تركيبي از جمله بهينه سازي سرورهاي اينترنت و مساله فروشنده ي دوره گرد استفاده مي شود.

طي دهه­ي گذشته الگوريتم هاي مختلفي با الهام گيري از الگوي رفتاري زنبورها براي حل انواع مختلفي از مسائل بهينه سازي شده ابداع شده اند كه از ميان آنها مي توان به سيستم زنبور^[2] (يا به اختصار BS)، الگوريتم BCO، الگوريتم ABC، MBO، الگوريتم زنبورها^[3]، الگوريتم HMBO، زنبور كندو^[4]، كلوني مصنوعي زنبور^[5] و الگوريتم VBA اشاره كرد. وجود الگوريتم هاي بسيار متنوع براي بهينه سازي كلوني زنبور اصلي ترين مشكل در پيش روي افرادي است كه قصد آشنايي با اين روش بهينه سازي را دارند. يكي از دلايل بروز اين مشكل اين است كه بر خلااف ساير الگوريتم كه در آن الگوريتم اصلي توسط يك فرد با يك تيم از پژوهشگران ابداع و سپس توسط ديگران توسعه داده شده است، ايده ي استفاده از زندگي اجتماعي زنبورها براي حل مسائل بهينه سازي توسط چند تيم مستقل از پژوهشگران به فواصل زماني كوتاه ولي به شكل هاي مختلف ارائه شده است. در نتيجه، اين روش بعدها نيز توسط محققان مختلف در مسيرهاي متفاوتي توسعه يافته اند كه همين امر باعث شده تا نتوان اكنون آنها را در غالب يك الگوريتم واحد ارائه كرد. يكي از اهداف اصلي اين فصل ارائه يك بحث منسجم و دقيق از دو الگوريتم پر كاربرد و مهم در زمينه ي بهينه سازي كلوني زنبور است.

اولين مورد استفاده از الگوي غذايابي زنبور عسل براي حل مسائل مرتبط با بهينه سازي به سال 1997 باز مي گردد كه در آن ساتو^[6] و هاگيوارا^[7] سيستم زنبور (BS) را براي بهبود كارايي الگوريتم ژنتيك پيشنهاد دادند. مهمترين رخداد پس از معرفي BS معرفي الگوريتم BCO در سال 2001 توسط لوسيچ^[8] و تئودورويج^[9] بود كه در آن از الگوي غذايابي زنبورهاي عسل براي حل مساله ي فروشنده ي دوره گرد و متعاقباً براي مدلسازي و حل مسائل مرتبط با مهندسي ترافيك استفاده كردند. اتفاق مهم بعدي در تاريخ بهينه سازي كلوني زنبور معرفي الگوريتم  زنبورها توسط پم^[10] و ديگران در سال 2006 و ABC توسط بس تورك^[11] و كارابوگا^[12] عددي توابع استفاده مي شد. از آن زمان تا كنون مرتباً نمونه هاي كارآمدتري از الگوريتم هاي بهينه سازي كلوني زنبور توسط محققان مختلف و به منظور حل مسائل گوناگون بهينه سازي شده پيشنهاد شده است كه اين رويه همچنان نيز ادامه دارد.

با توجه به توضیحات فوق الگوریتم BCO به صورت زیر بیان می شود.

1- مقداردهی اولیه: به هر یک از زنبورها  یک جواب تهی نسبت دهید.

2- برای هر یک از زنبورهای کندو، گذر پیشرو را به صورت زیر انجام دهید:

2-1 قرار دهید

2-2 تمام حرکت های ممکن برای ادامه ی مسیر فعلی ساخته شده توسط زنیور را شناسایی و امتیازدهی کنید (امتیازدهی به گونه ای انجام می شود که جواب های بهینه تر امتیاز بیشتری به دست آورند.)

2-3 با توجه به امتیازدهی انجام شده در بند قبل، یکی از حرکت های ممکن برای ادامه ی مسیر را به طور تصادفی با استفاده از چرخ رولت انتخاب کنید (بدین ترتیب احتمال انتخاب هر یک از حرکت ها به کیفیت آن بستگی خواهد داشت).

2-4 قرار دهید   و اگر  آنگاه به مرحله ی 2-2 بروید.

3- تمام زنبورها را به کندو بازگردانید.

4- زنبورها را بر اساس مقدار تابع هزینه شان مرتب سازی کنید.

5- هر زنبوری را با یک احتمال معین تصمیم می گیرد که آیا به تکمیل حل نیمه کاره ی خود ادامه داده و سایر زنبورها را نیز به پیروی از خود ترغیب کند و یا اینکه به یک زنبور پیرو تبدیل گردد (بدیهیست که در مسائل کمینه سازی، زنبورهایی که مقدار تابع هزینه شان عدد کوچکتری باشد از شانس بیشتری برای ادامه ی حل نیمه کاره ی قبلی و تکمیل آن برخوردار خواهند بود و بالعکس)

6- یرس هر يک از زنبورهای پیرو یکی از زنبورهای پیشاهنگ را به طور تصادفی با استفاده از چرخ رولت انتخاب کنید.

7- در صورتی که شرط پایان اجرای الگوریتم هنوز فراهم نشده است به قدم دوم بروید.

8- بهترین نتیجه را اعلام كنید.

الگوریتم ABC

همانند الگوريتم BCO در الگوريتم ABC نيز زنبورهاي مصنوعي، كه هر يك از آنها در واقع عامل محاسباتي ساده است. با تقليد رفتار زنبورهاي عسل در طبيعت به حل مساله ي بهينه سازي مورد نظر مي­پردازند. در الگوريتم ABC زنبورهاي مصنوعي موجود در كلوني به سه دسته تقسيم مي شوند: زنبورهاي مشغول به كار ^[13] كه يك منبع غذايي را كشف كرده و از آن غذا مي آورند، زنبورهاي تماشاگر^[14] كه درون كندو بوده و به رقص زنبورهاي مشغول به كار نگاه مي كنند تا با استفاده از آن از موقعيت منبع غذا آگاه شوند و زنبورهاي پيشاهنگ[15] كه به طور تصادفي در محيط پيرامون كندو به دنبال غذا مي گردند. زنبورهاي پيشاهنگ و تماشاگر را گاهي زنبورهاي بيكار^[16] نيز مي نامند. دليل اين نامگذاري آن است كه در موقع اجراي برنامه فقط زنبورهاي مشغول به كار به جستجو براي يافتن جوابهاي بهينه مي پردازند. همانطور كه در ادامه نيز خواهيم ديد، زنبورهاي تماشاگر وجود خارجي ندارند و زنبورهاي پيشاهنگ نيز فقط هنگامي كه نياز به انتخاب تعدادي نقطه به طور تصادفي از دامنه ي مساله داشته باشيم ظاهر مي شوند. تنها دليل استفاده  از اين زنبورها كمك به توضيح نحوه ي عملكرد الگوريتم ABC و ايجاد امكاني براي مقايسه ي آن با عملكرد زنبورهاي عسل در طبيعت است. در ادامه ي بحث بيشتر در اين مورد صحبت خواهيم كرد. همچنين توجه داشته باشيد كه نحوه ي تعريف و نوع عملكرد زنبورهاي پيشاهنگ در الگوريتم ABC تا حدي متفاوت از الگوريتم BCO است.

پيش از الگوريتم ABC به هر مساله ي بهينه سازي پيوسته (اعم از تحت قيد يا بدون قيد) ابتدا بايد آن را به يك مساله ي كمينه سازي (بدون قيد) تبديل نماييم. با توجه به اينكه نحوه ي انجام اين كار به تفصيل در فصول گذشته توضيح داده شده است دوباره وارد آن نمي شويم. الگوريتم ABC با ايجاد جمعيت اوليه اي از بردارهاي تصادفي شروع به كار مي كند. در اين مرحله، زنبورهايي كه مسئول يافتن تعدادي نقطه به طور تصادفي از دامنه ي مساله هستند را زنبورهاي پيشاهنگ مي ناميم. نحوه ي ادامه كار بدين صورت است كه در هر تكرار از الگوريتم، زنبورهاي مصنوعي (كه اين بار زنبورهاي مشغول به كار ناميده مي شوند) با انجام جستجوهاي تصادفي در اطراف جواب هاي به دست آمده در تكرار قبل به يافتن جواب هاي جديد مي پردازند. بديهيست كه اين جواب هاي جديد لزوماً همگي بهتر از جواب هاي بدست آمده در تكرار قبل نخواهند بود. پس از آنكه هر يك از زنبورهاي مصنوعي مشغول به كار يك جواب جديد پيدا كردند همه ي آنها دوباره به كندو بازگردانده مي شوند و براي انتخاب مسير حركتشان در تكرار بعدي تصميم گيري مي كنند. اين همان مرحله ي زنبورهاي تماشاگر است كه قبلاً نيز به آن اشاره كرده بوديم. همانطور كه مي بينيم  در الگوريتم ABC واقعاً هيچ زنبور مصنوعي تماشاگري در كار  نيست، بلكه همان زنبورهايي كه هر كدامشان يك جواب جديد از دامنه ي مساله پيدا كرده اند جوابهايشان را در اين مرحله با يكديگر به اشتراك مي گذارند براي اين منظور ميزان بهينگي (يا در واقع تناسب[17]) جواب هاي به دست آمده توسط زنبورها محاسبه شده و سپس هر يك از زنبورها با استفاده از چرخ رولت يكي از جوابهاي به دست آمده توسط زنبورهاي تكرار فعلي را به عنوان مسير جستجو در تكرار بعدي انتخاب مي كند. بدين ترتيب بديهيست كه اولاً نواحي اطراف جواب هاي بهينه تر توسط تعداد زنبورهاي بيشتري در تكرار بعدي مورد جستجو قرار مي گيرد و ثانياً امكان انجام جستجوي جديد در اطراف جواب هاي غير بهينه ي به دست آمده در تكرار قبلي نيز فراهم مي­گردد. برايند عمليات فوق جستجوي موثر تمام دامنه ي مساله است. مراحل فوق تا زمان تامين شرط مورد نياز براي خاتمه ي اجراي برنامه (يعني مثلاً اجراي تعداد از پيش تعيين شده اي از تكرارها) انجام مي گيرد در الگوريتم ABC براي افزايش كارآيي فرايند فوق، در صورتي كه پس از انجام تعداد از پيش تعيين شده اي از تكرارها هيچ جواب بهتري پيدا نشود، تعدادي از زنبورها (يا همگي آنها) حل‌هاي خود را كنار گذاشته و با تبديل شدن به زنبورهاي پيشاهنگ مجدداً به جستجوي تصادفي در دامنه ي مساله مي پردازند. به تجربه ديده شده كه انجام اين كار مي توانند به نحو قابل ملاحظه اي شانس يافتن جواب بهينه ي سراسري را افزايش دهد. بهترين جواب بدست آمده ‌در طول تمام تكرارها را نيز مي توان برابر با جواب مساله  بهينه سازي در نظر گرفت. با توجه به توضيحات فوق واضح است كه الگوريتم ABC از برخي جهات شبيه به كلوني زنبورهاي واقعي و از برخي جهات متفاوت با آن عمل مي كند.