Astaraki

جزئيات الگوريتم COA:
در شكل زير فلوچارت الگوريتم بهينه سازي فاخته (COA) را مشاهده مي كنيد. همانند ساير الگوريتمهاي تكاملي COAهم با يك جمعيت اوليه كار خود را شروع مي كند. جمعيتي متشكل از فاخته ها (Cuckoos). اين جمعيت از فاخته ها تعدادي تخم دارند كه آنها را در لانه تعدادي پرنده ي ميزبان خواهند گذاشت. تعدادي از اين تخم ها كه شباهت بيشتري به تخم هاي پرنده ميزبان دارند شانس بيشتري براي رشد و تبديل شدن به فاخته بالغ خواهند داشت. ساير تخم ها توسط پرنده ميزبان شناسايي شده و از بين مي روند. ميزان تخم هاي رشد كرده مناسب بودن لانه هاي آن منطقه را نشان مي دهند. هرچه تخمهاي بيشتري در يك ناحيه قادر به زيست باشند و نجات يابند به همان اندازه سود (تمايل) بيشتري به آن منطقه اختصاص مي يابد. بنابراين موقعيتي كه در آن بيشترين تعداد تخمها نجات يابند پارامتري خواهد بود كه COAقصد بهينه سازي آنرا دارد.



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

توليد محلهاي سكونت اوليه فاخته ها (جمعيت اوليه جوابهاي كانديد):
براي حل يك مساله بهينه سازي لازم است تا مقادير متغيرهاي مساله بفرم يك آرايه شكل گيرند. در GAو PSOاين آرايه ها با نامهاي "كروموزوم" و "موقعيت ذرات" مشخص مي شوند. ولي در الگوريتم بهنيه سازي فاخته (COA) به اين آرايه habitatيا "محل سكونت" مي گوييم.
در يك مساله بهينه سازي Nvarبعدي يك habitat يك آرايه 1xNvarخواهد بود كه موقعيت فعلي زندگي فاخته ها را نشان مي دهد. اين آرايه به شكل زير تعريف مي شود:
Habitat = [x1,x2,…,xNvar]
ميزان مناسب بودن (يا مقدار سود) در habitatفعلي با ارزيابي تابع سود (fp) در habitatبدست مي آيد. پس:
Profit = fp(habitat) = fp(x1,x2,…,xNvar)
همانطور كه ديده مي شود COAالگوريتمي است كه تابع سود را ماكزيمم مي كند. براي استفاده از COAبراي حل مسايل كمينه سازي كافي است يك علامت منفي در تابع هزينه ضرب كنيم.
براي شروع الگوريتم بهينه سازي يك ماتريس habitatبه سايز Npop*Nvarتوليد مي شود. سپس براي هر كدام از اين habitatها تعدادي تصادفي تخم تخصيص مي يابد. در طبيعت هر فاخته بين 5 تا 20 تخم مي گذارد. اين اعداد به عنوان حد بالا و پايين تخصيص تخم به هر فاخته در تكرارهاي مختلف استفاده مي شود. ديگر عادت هر فاخته حقيقي اين است كه آنها در يك دامنه مشخص تخم هاي خود را مي گذارند.
از اين به بعد حداكثر دامنه تخمگذاري را Egg Laying Radius (ELR)مي ناميم.
در يك مساله بهينه سازي به حد بالاي متغيرهاي varhiو حد پايين varlowهر فاخته داراي ELRي خواهد بود كه متناسب است با تعداد كل تخمها، تعداد تخم هاي فعلي فاخته و همچنين حد بالا و پايين متغيرهاي مساله.
بنابراين ELRبصورت زير تعريف مي شود:


آلفا متغيري است كه حداكثر مقدار ELR را با آن تنظيم ميكنيم.

روش فاخته ها براي تخمگذاري:
هر فاخته بصورت تصادفي تخمهايي را در لانه پرندگان ميزبان كه در ELR خود قرار دارد، مي گذارد.

وقتي تمام فاخته ها تخمهاي خود را گذاشتند برخي از تخم ها كه كمتر شبيه تخم هاي پرنده ميزبان هستند شناسايي شده و از لانه بيرون انداخته مي شوند. بنابراين بعد از هر تخمگذاري p%از تمام تخمها (معمولا 10%) كه مقدار تابع سود آنها كمتر است نابود مي شوند. بقيه جوجه ها در لانه هاي ميزبان تغديه شده و رشد مي كنند.
نكته جالب ديگر در مورد جوجه فاخته ها اين است كه فقط يك تخم در هر لانه امكان رشد دارد. چرا كه وقتي جوجه ها ي فاخته از تخم در مي آيند تخمهاي خود پرنده ميزبان را از لانه بيرون پرت مي كنند و اگر جوجه هاي پرنده ميزبان زودتر از تخم خارج شده باشند جوجه فاخته بيشترين مقدار غذا را كه پرنده ميزبان مي آورد خورده (بدن 3 برابر بزرگتري كه دارد بقيه جوجه ها را كنار مي زند) و پس از چند روز جوجه هاي خود پرنده ميزبان از گرسنگي مي ميرند و فقط جوجه فاخته زنده مي ماند.

مهاجرت فاخته ها:
وقتي جوجه فاخته ها رشد كردند و بالغ شدند مدتي در محيط ها و گروه هاي خودشان زندگي مي كنند ولي وقتي زمان تخمگذاري نزديك مي شودبه habitatهاي بهتر كه در آنجا شانس زنده ماندن تخمها بيشتر است مهاجرت مي كنند. پس از تشكيل گروه هاي فاخته در مناطق مختلف زيست كلي (فضاي جستجوي مساله) گروه داراي بهترين موقعيت به عنوان نقطه هدف براي ساير فاخته ها جهت مهاجرت انتخاب مي شود.
وقتي فاخته هاي بالغ در اقصي نقاط محيط زيست زندگي مي كنند تشخيص اينكه هر فاخته به كدام گروه تعلق دارد كار سختي است. براي حل اين مشكل، گروه بندي فاخته ها توسط روش كلاس بندي K-meansانجام مي شود (يك k بين 3 تا 5 معمولا كفايت مي كند).
حال كه گروه هاي فاخته تشكيل شدند سود ميانگين گروه محاسبه مي شود تا بهينگي نسبي محل زيست آن گروه بدست آيد. سپس گروهي كه داراي بيشترين مقدار متوسط سود (بهينگي) مي باشد، به عنوان گروه هدف انتخاب شده و گروه هاي ديگر به سمت آن مهاجرت مي كنند.
هنگام مهاجرت به سمت نقطه هدف فاخته ها تمام مسير را به سمت محل هدف طي نمي كنند. آنها فقط قسمتي از مسير را طي كرده و در آن مسير هم انحرافي دارند. اين نحوه حركت را در شكل زير بوضوح مشاهده مي كنيد.


همانطور كه از شكل فوق معلوم است هر فاخته فقط λ%از كل مسير را به سمت هدف ايده آل فعلي طي مي كند و يك انحراف φراديان نيز دارد. اين دو پارامتر به فاخته ها كمك مي كند تا محيط بيشتري را جستجو كنند. λعددي تصادفي بين 0 و 1 است و φعددي بين π/6و π/6- مي باشد.
وقتي تمام فاخته ها به سمت نقطه هدف مهاجرت كردند و نقاط سكونت جديد هركدام مشخص شد، هر فاخته صاحب تعدادي تخم مي شود. با توجه به تعداد تخم هر فاخته يك ELRبراي آن مشخص مي شود و سپس تخمگذاري شروع مي گردد.

از بين بردن فاخته هاي قرار گرفته در مناطق نا مناسب:
با توجه به اين واقعيت كه هميشه تعادلي بين جمعيت پرندگان در طبيعت وجود دارد عددي مثل Nmaxحداكثر تعداد فاخته هايي را كه مي توانند در يك محيط زندگي كنند كنترل و محدود مي كند. اين تعادل بدليل محدوديت هاي غذايي، شكار شدن توسط شكارچيان و نيز عدم امكان پيدا كردن لانه هاي مناسب براي تخم ها وجود دارد.

همگرايي الگوريتم:
پس از جند تكرار تمام جمعيت فاخته ها به يك نقطه بهينه با حداكثر شباهت تخم ها به تخم هاي پرنده گان ميزبان و همچنين به محل بيشترين منابع غذايي مي رسند. اين محل بيشترين سود كلي را خواهد داشت و در آن كمترين تعداد تخم ها از بين خواهند رفت. همگرايي بيش از 95% تمام فاخته ها به سمت يك نقطه، الگوريتم بهينه سازي فاخته (COA) را به انتهاي خود مي رساند.
گامهاي اصلي COAدر شكل زير نمايش داده شده است:


منبع

__________________

تعرفه ارزان تبلیغات در اولین و بزرگترین سایت هوش مصنوعی ایران !
با بیش از صد و چهل هزار کاربر!

satiakiamehr

با سلام و احترام
درمورد کاربرد الگوریتم cao می خواستم بدونم که میشه برای پیدا کردن ماکزیمم جریان و کوتاهترین مسیر در شبکه ها از اون استفاده کرد؟امکان داره که بیشتر توضیح بدید؟

satiakiamehr

با سلام و احترام
درمورد کاربرد الگوریتم cao می خواستم بدونم که میشه برای پیدا کردن ماکزیمم جریان و کوتاهترین مسیر در شبکه ها از اون استفاده کرد؟امکان داره که بیشتر توضیح بدید؟