الگوریتم بهینه سازی مبتنی بر جغرافیای زیستی (BBO)

الگوریتم بهینه سازی مبتنی بر جغرافیایی زیستی

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

تئوري الگوريتم BBO اينگونه بيان مي شود كه با فرض جزاير مختلف به عنوان زيستگاه‌‌هاي سكونت پذير، زيستگاه‌‌هايي كه براي اسكان گونه‌‌هاي جغرافيايي مطلوب مي باشند داراي شاخص صلاحيت (HSI) بالا هستند. خصوصيات تعيين كننده مطلوبيت زيستگاه‌‌ها با عنوان SIV معرفي شده و شامل فاكتورهايي مانند بارندگي، تنوع گياهي، ويژگي‌‌هاي نقشه برداري، خاك منطقه و دما مي باشد. زيستگاه‌‌هاي با HSI بالا تنوع بهتري از گونه‌‌ها را در خود دارند. در مقابل، زيستگاه‌‌هاي نامطلوب تعداد كمتري از گونه‌‌ها را شامل مي شوند. از اين روي، پديده ي مهاجرت گونه‌‌ها بين زيستگاه‌‌هاي همسايه نيز اين گونه توصيف مي شود كه بنا بر پر شدن زيستگاه‌‌هاي مطلوب، اين زيستگاه‌‌ها نرخ مهاجرت پذيري پاييني براي گونه‌‌هاي جديد دارند، بنابراين در توزيع گونه‌‌هاي خود نسبت به زيستگاه‌‌هاي با HSI پايين، ايستاتر هستند. از طرف ديگر، نرخ مهاجرت به بيرون بالايي هم به زيستگاه‌‌هاي همسايه به موجب فرصت‌‌هاي بسيار آنها براي مهاجرت دارند (نه به اين معني كه گونه ي مهاجرت كننده از زيستگاه خود محو شود بلكه نماينده اي از آن گونه‌‌ها به زيستگاه‌‌هاي با HSI كمتر مهاجرت داده مي شود و به طور همزمان در زيستگاه همسايه نيز ظاهر مي شود). از سوي ديگر، زيستگاه‌‌هاي با HSI پايين به موجب خلوت بودن آنها از گونه‌‌هاي زيستي، امكان مهاجرت پذيري بيشتري دارند كه اين باعث افزايش مطلوبيت آن زيستگاه مي شود چراكه كه مطلوبيت هر زيستگاه متناسب با تنوع گونه‌‌هاي جغرافيايي آن مي باشد. با اين حال اگر مطلوبيت يك زيستگاه پايين باقي بماند، آنگاه امكان انقراض گونه‌‌هاي ساكن وجود دارد كه اين خود راه را بيشتر براي مهاجرت پذيري باز مي كند. به همين دليل، اين زيستگاه‌‌ها در توزيع گونه‌‌هاي خود نسبت به زيستگاه‌‌هاي مطلوب تر، پوياتر هستند.

حال در مسئله بهينه سازي انتخاب ويژگي، به منظور اكتشاف زيرمجموعه ويژگي بهينه (به عنوان بهترين زيستگاه در اكوسيستم) كه حاوي مهمترين ويژگي‌‌هاي پيش بيني كننده (به عنوان بهترين تنوع گونه‌‌هاي جغرافيايي در زيستگاه) مي باشد، مسئله انتخاب ويژگي در BBO اينگونه نگاشت مي شود: يك اكوسيستم جمعيتي از راه حل‌‌هاي كانديد (زيرمجموعه‌‌هاي ويژگي كانديد) به عنوان زيستگاه‌‌ها در فضاي مسئله مي باشد و هر ويژگي در هر راه حل كانديد نيز به عنوان يك SIV شناخته مي شود. يك زيرمجموعه ويژگي خوب مشابه يك زيستگاه با HSI بالا مي باشد و يك زيرمجموعه ي ويژگي ضعيف مشابه يك زيستگاه با HSI پايين مي باشد. راهحل‌‌هاي باHSI بالا در مقابل تغييرات نسبت به راهحل‌‌هاي باHSI پايين مقاومتر هستند. بر همين اساس، راهحل‌‌هاي با HSI بالاتمايل به اشتراك گذاري ويژگيهاي خود با راه حل‌‌هاي با HSI پايين دارند (بنابراين جريان اطلاعاتي تقريباً از راه حل‌‌هاي خوب به راه حل‌‌هاي با تناسب ضعيف است)؛ و راه حل‌‌هاي ضعيف تنوعي از ويژگي‌‌هاي جديد را از راه حل‌‌هاي خوب مي پذيرند كه اين باعث افزايش كيفيت راه حل‌‌هاي ضعيف و همچنين اكتشاف فضاهاي جديد جستجو مي شود. HSI هر زيستگاه در مسئله انتخاب ويژگي نيز متناسب با تابع برازش هر زيرمجموعه ويژگي مي باشد.

BBO يك الگوريتم تكاملي بر پايه جمعيت است كه از پديده مهاجرت حيوانات و پرندگان بين جزاير الهام گرفته شده است. در واقع جغرافياي زيستي مطالعه توزيع جغرافيايي گونه‌‌هاي زيستي مي باشد. جزايري كه مكان مناسبي براي گونه‌‌هاي جغرافيايي جهت اسكان هستند داراي شاخص ميزان مطلوبيت HIS بالا هستند. در BBO هر منطقه زيستي به عنوان يك عضو منفرد شناخته مي شود و داراي شاخص ميزان مطلوبيت يا HSI مخصوص به خود است در اين الگوريتم جواب يا منطقه زيستي با HSI بالاتر نشان دهنده جواب خوب مي باشد. البته اين روال در الگوريتم‌‌هايي همچون ژنتيك در قالب كروموزوم به عنوان عضوي منفرد مطرح شده بود و ميزان برازندگي نيز برآوردي از عملكرد الگوريتم به حساب مي آمد كه طبيعتاً جواب با برازندگي بيشتر بهتر بود . در BBO معمولاً خواص از منطقه ي جواب‌‌هاي با HSI بالاتر به منطقه‌‌هايي با HSI پايين تر حركت مي كند به عبارت ديگر منطقه‌‌هاي با HSI پايين تر با گرفتن خواص از منطقه‌‌هاي با HS بالا خود را شبيه به آنها مي كنند. متغييرهاي هر ناحيه SIV ناميده مي شود كه بيانگر خواص هر ناحيه است و در مهاجرت‌‌هاي خروجي وجود دارد مهاجرت خروجي غالباً براي آن جوابي مطرح مي شود كه HSI بالايي دارد و خواص خود را به اشتراك مي گذارد قابل ذكر است هر كدام از اين دو نوع مهاجرت نرخ خاص خود را دارد كه با نام‌‌هاي نرخ ورود و نرخ خروج شناخته مي شوند. حال الگوريتم BBO با استفاده از اين دو عملگر در اپراتور تقاطع و همچنين با استفاده از اپراتور جهش به دنبال آن است تا جواب‌‌هايي ايجاد كند كه HSI را حداكثر نمايند. نرخ مهاجرت از مكاني مشخص و نرخ مهاجرت به مكاني خاص از مقداري ثابت شروع مي شود و به نسبت جمعيت ساكن تغيير مي كند. در الگوريتم BBO تعداد مناطق درگير در اين روال ثابت است و نرخ رخ دادن فرآيند‌‌هاي آني با اپراتور جهش مشخص مي شود نيز ثابت باقي مي ماند؛ يعني هر چند كه فرايند عموماً به طور تصادفي پياده سازي مي شود اما مواردي در شرايط گوناگون ثابت هستند.

معرفي الگوريتم بهينه سازي مبتني بر جغرافياي زيستي

همانطور كه پيشتر گفته شد، اين الگوريتم بر اساس علم جغرافياي زيستي شكل گرفته شده است. BBO يك الگوريتم بهينه سازي بر اساس جمعيت است كه در آن توليد مثل نسل كودكان مورد بحث قرار نمي گيرد. اصولاً در جغرافياي زيستي رقابت بر سر بقا و منابع صورت مي گيرد، جانوران و حيوانات تلاش مي كنند به صورت انحصاري به منابع دستيابي كنند؛ اما ازآنجايي كه در مناطق خلوت منابع به صورت زيادي وجود دارد جانوران براي مهاجرت به اين مناطق تلاش مي كنند. دو فاكتور تعيين كننده در اين الگوريتم مقدار شاخص شايستگي زيستگاه كه HSI ناميده مي شود و متغيرهاي شاخص شايستگي كه SIV نام دارد. لذا جزايري كه مكان مناسبي براي گونه‌‌هاي جغرافيايي جهت اسكان هستند داراي شاخص صلاحيت HSI بالا هستند و فاكتورهاي تعيين كننده HSI از قبيل بارندگي، تنوع گياهي، دما شاخص شايستگي زيستگاه هستند. جزاير با HSI داراي گونه‌‌هاي زيادي هستند، در حالت كلي جزاير با HIS بالا داراي نرخ مهاجرت به داخل پايين و جزاير باHSI پايين داراي نرخ مهاجرت به داخل بالايي هستند، دلايل اين دو مورد مي تواند اين باشد كه در مورد اول جزيره قبلاً توسط گونه‌‌هاي ديگر پر شده است و نمي تواند پذيراي گونه‌‌هاي جديدي باشد و مورد دوم به علت جمعيت خلوت اين جزيره است؛ اما در مسائل بهينه سازي اگر هدف بيشينه سازي باشد، سكونتگ اهي كه HIS بيشتري دارد، براي سكونت بهتر است و بالعكس، اگر هدف كمينه سازي باشد، سكونت گاهي كه HSI كمتري دارد، سكونت گاه بهتري خواهد بود.

در شكل بالا منحني‌‌هاي نرخ‌‌هاي مهاجرت و مهاجرت پذيري هم براي نسخه اصلي BBO برحسب تغييرات تعداد گونه‌‌ها و هم در مسئله انتخاب ويژگي برحسب تغييرات رتبه ي راه حل‌‌ها متناسب با تابع برازش نشان داده شده است. مطابق شكل، زيستگاه در نقطه ، داراي حداكثر تعداد گونه‌‌هاي اسكان يافته مي باشد، كه مطابق آن نرخ مهاجرت پذيري گونه ي جديد در اين زيستگاه حداقل(به علت اشباع شدن زيستگاه توسط گونه‌‌هاي قبلي) و نرخ مهاجرت از آن به زيستگاه‌‌هاي همسايه نيز حداكثر مي باشد(به علت فرصت‌‌هاي مناسب آنها براي مهاجرت). در نقطه مبدأ مختصات نمودار نيز به علت خالي بودن زيستگاه از سكنه نرخ مهاجرت پذيري از زيستگاه‌‌هاي با HSI بالا به منظور توسعه اكتشاف فضاي مسئله حداكثر مي باشد و متقابلاً نرخ مهاجرت از آن به زيستگاه‌‌هاي همسايه نيز به علت برازش پايين آن حداقل مي باشد. در مسئله انتخاب ويژگي نيز نقطه ي kmax زيرمجموعه ي ويژگي با بهترين رتبه برحسب مقدار برازش را نشان مي دهد كه به اشتراك گذاري ويژگي‌‌هاي خوب با زيرمجموعه‌‌هاي ضعيف تر اشاره دارد. مبدأ مختصات نيز زيرمجموعه ي ويژگي با پايين ترين رتبه ي برازش را نشان مي دهد كه مطابق آن حداكثر نرخ پذيرش اطلاعات از راه حل‌‌هاي متناسب تر و حداقل نرخ اشتراك گذاري اطلاعات با راه حل‌‌هاي ديگر را دارد.

براي منحني‌‌هاي خط مستقيم در شكل بالا روابط زیر برقرار است:

مهاجرت: تغييرمان از يك زيستگاه به زيستگاه ديگراست، در الگوريتم BBO يك جمعيت به عنوان يك راه حل در نظر گرفته مي شود، از مهاجرت براي ايجاد تغيير در راه حل استفاده مي شود مهاجرت در BBO يك فرآيند تطبيقي است كه براي تغيير در زيستگاه‌‌هاي موجود استفاده مي شود. ما از نرخ مهاجرت هر راه حل براي تعيين احتمال تبادل اطلاعات ما بين زيستگاه‌‌ها استفاده مي كنيم؛ كه با احتمال محاسبه مي شود. مي توان با استفاده از نخبه گرايي باعث جلوگيري از حذف راه حل‌‌هاي بهتر شد.
جهش: عملگر جهش بيشتر در پردازش‌‌هاي تكاملي انجام مي گيرد. شايد هميشه تمام جواب‌‌هايي كه توسط الگوريتم BBO به دست آمده باشد بهينه نباشد، يا ممكن است ما را از هدف اصلي كه رسيدن به جواب بهينه است دور كند بدين منظور در اين الگوريتم بعد از عمل مهاجرت بايد عملگر جهش روي راه حل‌‌ها اتفاق بيافتد، از جهش براي ايجاد تغيير در راه حل‌‌ها استفاده خواهيم كرد، هدف كلي جهش ايجاد تنوع در راه حل‌‌ها يا افزايش زيست گاه‌‌ها در ميان جمعيت است.

1236 بازدید