بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
به کارگيري الگوريتم ژنتيک براي حل مسأله پوشش مجموعه
مسأله پوشش مجموعه يا مسأله پوشــش سـطرهاي يـک مـاتريس بـه وسـيله زيرمجموعه اي از ستون ها با کمترين هزينه ، يک مسأله NP-Complete اســت .
همين امر محققين را بر آن داشته است تا تمام تــلاش خـود را بـراي طراحـي الگوريتم هاي ابتکاري بــه کار گـيرند. الگوريتـم ژنتيک بـه عنـوان يـک روش ابتکاري که سعي دارد تا فرايند تکامل تدريجــي حيـات انسـان را تقليـد کنـد، رويکرد مناسبي است براي مواجهه با مسأله پوشش مجموعه که متأسفانه کمـتر بدان توجه شده است . در اين کار تحقيقي سعي شــده اسـت تـا بـا اسـتفاده از مفاهيم الگوريتم ژنتيک يک رويــه مؤثـر بـراي حـل مسـأله پوشـش مجموعـه طراحي گردد. نتايج حاصله از اجراي الگوريتم بر روي مسائلي که بـه صـورت تصادفي توليد شده اند، مؤيد کارايي آن مي باشد.
۱- مقدمه
مسأله پوشش مجموعه که کاربردهاي فراواني در مسائل روزمـره دارد، يـک مـدل برنامـه ريزي خطي صفر و يک است . مسأله پوشش مجموعه کاربردهاي بسيار متنوعي دارد کــه در مقـالات گوناگون به آنها اشــاره شـده اسـت . جـالب ترين ايـن کاربردهـا مکان يـابي تسـهيلات [١,٢]، زمان بندي رانندگان اتوبوس [٣]، زمان بندي کارکنان خطوط هوايــي [٤] و حتـي متعادل سـازي خط مونتاژ [٥] مي باشد. در اين مقاله سعي شده است تا با استفاده از مفـهوم الگوريتـم ژنتيـک که يک روش ابتکاري مؤثر در حل مسائل دشوار بهينه سازي است ، رويه جديدي براي مواجهه با مسأله پوشش مجموعه معرفي گردد.
اين مقاله بدين صورت سازماندهي شده است که ابتدا مســأله پوشـش مجموعـه تشـريح مي شود، سپس توضيح کوتاهي در رابطه با الگوريتم ژنتيک ارائه مي گردد و آنگــاه بررسـي هاي انجام شده بر روي گزينش عملگر جهشي ، مکانيســم انتخـاب و نـرخ تقـاطعي مناسـب بـراي طراحي يک الگوريتم مؤثـر تبييـن مي شـود و در نـهايت بـا اسـتفاده از نتـايج حاصلـه از ايـن بررسي ها الگوريتم پيشنهادي معرفي و تعدادي مسأله که به صورت تصادفي توليد شــده اند بـه وسيله آن حل مي گردد.
۲- مسأله پوشش مجموعه
مسأله پوشش مجموعه که هيراگو [٦] آن را يک نــوع مسـأله مکان يـابي ـ تخصيـص ۳ معرفـي مي کند، يک مدل برنامه ريزي خطي صفر و يک است . اين مسأله هنگــامي مطـرح مي شـود کـه لازم باشد تعدادي مشتري هر يک به وسيله حداقل يک تسهيل خدمت داده شوند به طوري کــه اين خدمت دهي با حداقل هزينه ممکن انجام گردد. اگر فرض کنيــم کـه مشـتريان در m گـره مستقر باشند و تسهيلات نيز بتوانند در n گره مستقر شوند، مدل رياضي ذيل ارائه مي شود:
در مدل فوق c j هزينه تخصيص يک تسهيل به گره j است . xj که متغيير تصميم مسأله مي باشد، در صورتي يک است که تسهيلي در گره j مستقر شود و در غير ايــن صـورت صفـر خواهد بود. aij نيز با توجه به فاصله بين دو گره محاسبه مي شود. اگر فاصله بين گره i و گره j از فاصله پوشش ۴ مجاز که پيشتر تعريف شده است کوچکتر باشد aij يک خواهد بود، يعني اگر تسهيلي در گره i مستقر شود مي تواند به مشتري موجود در گــره j خدمت دهـي کنـد. (در اين حالت اصطلاحاً گفته مي شود که گره j توسط گـره i پوشـش يافتـه اسـت .) در غـير ايـن صورت aij صفر منظور مي شود.
با توجه به NP-Complete بودن مسأله پوشش مجموعه ، استفاده از روش هــاي متـداول حل مدل هاي برنامه ريزي عدد صحيح همچون شاخه و کران ، برش کسري و الگوريتم جمعــي براي حل آن بسيار وقت گير خواهد بود. البته روش هاي ديگــري هـم بـراي حـل دقيـق مـدل پيشنهاد شده است که الگوريتم ارائه شده توســط بـيزلي [٧]، روش ابتکـاري همـزاد فيشـر و کديــا،االگوريتــــم ارائــــه شــــده .... ان ها هسـتند. ايـن روش هـا جملگـــي دقيــق و البتــه بســيار وقــت گــير هستند. روش هاي ديگري نيز براي حل مسأله پوشش مجموعه توسط محققين بيان شده اسـت .
مهمترين اين روش ها عبارتند از: روش ارائــه شـده توسـط بـيزلي موسـوم بـه روش ابتکـاري لاگرانژي ۶ [١١]، الگوريتم لوپز و لورنا موسوم به روش ابتکاري جانشين ۷ [١٢]، حالت توســعه يافته الگوريتم لوپز و لورنا که توسط آلمينانا و پاستور ارائه شده است [١٣] و دو روش واسکو و ويلسون به نام هاي SCHEURI و SCFUNCTO١٧ [١٤,١٥].
۳- الگوريتم ژنتيک
مفهوم الگوريتم ژنتيک اولين بار توسط جان هالند ارائه شده است . الگوريتم ژنتيک تنها مربوط به حيات انسان نيست بلکه تکامل طبيعــت را شبيه سـازي مي کنـد [١٦] و بـه گمـان محققيـن رويکرد بسيار مناسبي براي مواجهه با مسائل بهينه سازي مي باشد[١٧]. سـاختار کلـي الگوريتـم ژنتيک که يک تکنيک جستجوي احتمالي است را مي توان اين چنين تشريح کرد:
هر جواب مسأله از طريق يک سيستم کدينگ ۸ به رمز درآورده مي شـود. ايـن رمزهـا کـه عموماً به صورت رشته هستند را اصطلاحاً کروموزوم ۹ و اجزاي تشکيل دهنده آنها را نـيز ژن ۱۰ مي نـامند. هـر الگوريتـم ژنتيـک بـا مجموعـه اي از کروموزوم هـا کـه درحقيقـت مجموعــه اي ازجواب هاي مسأله هستند آغاز مي گردد. اين مجموعه که يا به صورت تصادفي توليد مي شــود يا از طريق الگوريتم هاي ابتکاري ديگر ايجاد مي گردد، جمعيت اوليه ۱۱ خوانده مي شــود. بـراي انجام فرايند جفت گيري تعدادي از کروموزوم هاي موجود در جمعيت برگزيده مي شوند (يا بــه طريق تصادفي يا از طريق يکي از مکانيسم هاي شــناخته شـده انتخـاب ) تـا از طريـق عملگـر تقاطعي ۱۲ تعدادي فرزند توليد نمايند. همچنين براي ايجاد تنوع در جمعيت جديدي کــه قـرار اسـت تشـکيل شـود از عملگـر ديگـري بـه نـام عملگـر جهشـي ۱۳ اسـتفاده مـي گـردد. کليـه کروموزوم هاي جمعيت اوليه و فرزندان توليد شده از طريق عملگرهاي تقاطعي و جهشــي ، بـر اساس مقدار برازندگي ۱۴ آنها (که در مورد مسائل بهينه سازي معمولاً همان تــابع هـدف مسـأله است ) ارزيابي شده و سعي مي شود تا مناسب ترين کروموزوم ها به جمعيت بعدي راه يابند. اين عمل بر اساس يک مکانيسم انتخاب ۱۵ انجام مي شود. بعد از چند تکرار (نسل ۱۶)، الگوريتـم بـه سمت جواب بهينه يا جوابي که بسيار به آن نزديک است همگرا مي شــود. البتـه آنچـه در ايـن قسمت ذکر شد ساختار کلـي الگوريتـم ژنتيـک اسـت ، ليکـن تنـوع نسـبتاً قـابل توجـهي کـه درچگونگي به کارگيري عملگرهاي تقاطعي و جهشي ، نــوع عملگرهـاي تقـاطعي و جهشـي و مکانيسم انتخاب مورد استفاده ، نحوه ايجاد جمعيت اوليــه ، چگونگـي مواجهـه بـا جواب هـاي غيرموجه (البته در مسائل بهينه سازي محدود) و چگونگي گزينش والديــن بـراي انجـام عمـل جفت گيري وجود دارد، دست محققين را براي طراحي الگوريتم هاي ژنتيک متنــوع کـاملاً بـاز مي گذارد.
۴- فعاليت هاي آغازين براي طراحي يک الگوريتم کارا
۴-۱- الگوريتم طراحي شده اوليه
در اين بخش الگوريتم طراحي شده به صورت گام به گام تشريح مي شود:
گام صفر: در اين مرحله اندازه جمعيــت اوليـه ، تعـداد نسـل ها، نـرخ تقـاطعي ۱۷ و نـرخ جهشي ۱۸ تعيين مي گردد. در اين مرحله بايد توجـه داشـت کـه بـزرگـتر فـرض کـردن انـدازه جمعيت اوليه ، تعداد نسل ها و نرخ تقــاطعي مي توانـد بـه بسـط فضـاي جسـتجو و در نتيجـه همگرايي سريعتر الگوريتم منتــج گـردد. همچنيـن از آنجـا کـه عملگـر جهشـي يـک عملگـر حاشيه اي است بهتر است با پايين فرض نمودن آن از ايجاد يک رويه صرفاً تصادفي جلوگـيري نمود[١٦].
گام اول : در اين گام جمعيت اوليه به تعدادي کــه در گـام صفـر تعييـن شـده اسـت بـه صورت تصادفي توليد مي شود. در اين مجموعه هيچ گونه کروموزوم تکراري وجود ندارد.
گام دوم : در اين مرحله با استفاده از عملگر تقاطعي دونقطه برش ۱۹، فرايند جفـت گـيري صورت مي گيرد. البته در اين مرحله امکان استفاده از عملگر تکنقطــه بـرش نـيز وجـود دارد، ليکن بنا به توصيه اغلب محققين مبني بر ترجيح استفاده از عملگرهاي دو يا چند نقطه برش از عملگر تقاطعي دو نقطه برش استفاده مي شود[١٨].
چگونگي اجراي عملگر بدين شکل است که براي هــر دو کروموزومـي کـه قـرار اسـت نقش والدين را بازي کنند دو نقطه به صورت تصـادفي انتخـاب مي شـود. کروموزوم هـا از آن نقاط ، برش خورده و سپس قسمت هاي مابين نقاط برش بيـن دو کرومـوزوم مبادلـه مـي گـردد.
نحوه انتخاب والدين نيز بدين صورت است که به تعداد کروموزوم هــاي موجـود در جمعيـت عدد تصادفي توليد مي شود. هر يک از آنها کوچکتر از نرخ تقاطعي باشند، کرومـوزوم مربوطـه به عنوان يکي از والدين انتخاب مي شود. اگر تعداد کروموزوم هــاي گزينـش شـده فـرد باشـد آخرين کروموزوم انتخاب شده ، حذف مي گردد. در اين مرحله تعدادي بچه توليد مي شــود کـه همگي از نظر موجه بودن تست مي شوند و کروموزوم هاي غيرموجه معــدوم مـي گردنـد. البتـه براي مواجهه با کروموزوم هاي غيرموجه امکان استفاده از رويکردهــاي ديگـر نظـير اسـتراتژي جريمه اي و اصلاحي نــيز وجـود دارد؛ ليکـن بـراي حـل مسـائلي کـه داراي فضـاي جـواب غيرمحدب هستند بهتر است از روش مبتني بر رد کروموزوم هاي غيرموجه استفاده شود[١٦].
گام سوم : در اين مرحله با استفاده از عملگر جهشي سعي مي شود تا تنوعي در جمعيــت ايجاد شود. در اين گام دو نوع عملگر تعريف شده است که عملکرد آنها مقايسه خواهــد شـد.
اولين عملگر، عملگر جهشي يکنواخت ۲۰ است . چگونگي اجراي عملگر بدين شکل است کــه تعدادي ژن از جمعيت برگزيده مي شوند، اگــر ژنـي صفـر باشـد بـه يـک تبديـل مي شـود و بالعکس . نحوه انتخاب والدين نيز بدين صورت است که به تعداد ژن هاي موجود در جمعيـت (حـاصلضرب تعـداد کروموزوم هـاي موجــود در جمعيــت و تعــداد ژن هــاي موجــود در کروموزوم ها) عدد تصادفي توليد مي شود. هر يک از اين اعداد کوچکتر از نرخ جهشي باشــند، ژن مربوطه تغيير مي کند.
رويکرد ديگري که در اين فاز امتحان شده اسـت ، عملگـر جهشـي معاوضـه ۲۱ مي باشـد.
چگونگي اجراي عملگر بدين شکل است که تعدادي کروموزوم از جمعيت برگزيده مي شـوند، هر يک به صورت تصادفي از يک نقطه برش داده شده و جاي دو قسمت حاصله بــا يکديگـر تعويض مي شود. نحوه انتخاب والدين نيز بدين صـورت اسـت کـه بـه تعـداد کروموزوم هـاي موجود در جمعيت عدد تصادفي توليد مي شود. هر يک از آنها کوچکتر از نرخ جهشي باشــند، کروموزوم مربوطه به عنوان نيا انتخاب مي شود. در اين مرحلــه (از هـر عملگـري کـه اسـتفاده شود) تعدادي بچه توليد مي گردد که همگي از نظر موجه بودن تست مي شوند و کروموزوم هاي غيرموجه از گردونه خارج گشته و معدوم مي گردند.
گام چهارم : در اين مرحله نيز که نوبت اجراي فاز انتخاب اسـت دو رويکـرد تعريـف و در نهايت مقايسه شده است . رويکرد اول ، استفاده از مکانيسم انتخاب ( +μ ) اسـت . در ايـن روش کليه کروموزوم هاي جمعيت قبل و کليه فرزندان توليدشده توسط دو عملگــر تقـاطعي و جهشي در يک مکان جمع شده و بر اساس مقدار برازنــدگي شـان منظـم مي شـوند و از بـالاي فهرست به تعداد اندازه جمعيت کروموزوم انتخاب مي شود. رويکرد ديگر، استفاده از مکانيسـم انتخاب مسابقه ۲۲ است . در اين روش نيز ابتدا کليه کروموزوم هاي جمعيت قبل و کليه فرزنـدان توليدشده توسط دو عملگر تقاطعي و جهشي در يک مکان جمع مي شوند. ســپس بـه صـورت تصادفي دو کروموزوم از اين مکان انتخاب شده ، کروموزومــي کـه داراي مقـدار تناسـب بـهتر است به نسل بعد منتقل مي شود. اين کار تا جايي ادامه مي يابد که تعداد کروموزوم هاي انتخاب شده مساوي با اندازه جمعيت باشد. ماحصل اجراي اين گــام (از هـر مکانيسـمي کـه اسـتفاده شود) تشکيل جمعيت جديد است . بديهي است کليه کروموزوم هاي موجود در جمعيت جديـد موجه اند.
گام پنجم : اگر تعداد تکرارها (نسل ها) به تعدادي که از پيش تعييـن شـده اسـت رسـيده باشد، الگوريتم متوقف مي شود. در غير اين صورت الگوريتم به گام دوم باز مي گردد.
۴-۲- بررسي هاي اوليه
پيش از ارائه بررسي هاي انجام شده بايد به ذکر نکته مهمي که در رابطه بــا مسـأله آزمون هـاي شبيه سازي شده وجود دارد پرداخت . براي توليد ضرايب تابع هدف از روش هم نهشتي خطــي با پيمون ۱۰۰ استفاده و اعداد تصادفي بيـن ۰ و ۹۹ توليـد شـده اسـت . بـراي توليـد مـاتريس محدوديت ها نيز از يک مولد خطي تکرارپذير در پايه دو استفاده شده است . توزيع يکنواخــت و استقلال کليه اعداد توليد شده به وسيله آزمون هاي مربع کاي و افراز بررسي و تـأييد گرديـده است .
۴-۲-۱- تعيين مؤثرترين عملگرها
همان طور که پيشتر ذکر شد تعريف رويکردهاي گوناگون در مورد عملگر جهشي و مکانيســم انتخاب باعث مي شود تا الگوريتم چهار حالت مختلف بيان شده در جدول ۱ را به خود بگيرد.
براي بررسي چهار حالت فوق الذکر يک مسأله به ابعاد ۲۰×۲۰ (با جــواب بهينـه ۳۷) بـا نسبت (تعـداد يکهـاي موجـود در مـاتريس محدوديت هـا) ۰.۵۲ شبيه سـازي شـده اسـت .
الگوريتم در هر يک از حالات فوق ۱۰ بار در شرايط زير بر روي مسأله اجرا شده است : اندازه جمعيت = ۵۰، تعداد نسل ها = ۲۰، نرخ تقاطعي = ۰.۹۰، نرخ جهشي = ۰.۱۰ نتايج حاصله از ۱۰ بار اجراي هر حالت الگوريتــم بـر روي مسـأله مذکـور بـه صـورت ميانگين متوسط مقدار برازش کروموزموم هاي هر نســل در ۱۰ اجـرا در شـکل ۱ رسـم شـده است . همچنين متوسط فاصله جواب هاي حاصله در هر يک از ۱۰ اجرا نسبت به جواب بهينــه نيز در جدول ۲ ارائه شده است .
