جستجوی فاخته

جستجوی فاخته (به انگلیسی: Cuckoo search) یا جستجوی کوکو، یک الگوریتم بهینه‌سازی است که در سال ۲۰۰۹ توسط زین-شی یانگ و سوآش دب ارائه شده است. این الگوریتم الهام گرفته از رفتار انگلی نوعی فاخته است که در آشیانه ی پرندگانی از گونه های دیگر (پرندگان میزبان) تخم گذاری می کند. بعضی از پرندگان میزبان با فاخته‌های مزاحم برخورد می کنند. برای مثال اگر پرنده ی میزبان متوجه شود که تخم‌ها متعلق به خودش نیست، یا تخم‌های بیگانه را دور می‌اندازد و یا به سادگی لانه اش را ترک کرده و در جایی دیگر آشیانه ای جدید می‌سازد. گونه‌هایی از فاخته ها، همچون تخم انگلی های تاپیرا (Tapera)، به نحوی تکامل یافته اند که جفت ماده مهارت خاصی در تقلید رنگ‌ و الگوی تخم‌های میزبان دارد.

جستجوی فاخته این شیوه ی تولید مثلی را ایده آل سازی کرده است و می‌تواند برای انواع مسایل بهینه‌سازی به کار برده شود. همچنین اثبات شده است که جستجوی فاخته حالت خاصی از راهبرد فرگشتی این الگوریتم با استفاده از دو دسته اصلی فاخته‌ها، یعنی فاخته‌های بالغ و تخم‌ها، اقدام به بهینه‌سازی محیط‌های تخم‌گذاری می‌کند. امیدواریم که خصوصیات زیست‌محیطی و مهاجرت فاخته‌ها به سمت همگرایی و یافتن بهترین محیط برای زادوولد و تکثیر هدایت کند. این الگوریتم با یک جمعیت اولیه از فاخته‌ها شروع می‌شود و از روش‌های خاص تخم‌گذاری و تخم‌گذاری استفاده می‌کند تا به محیط‌های بهینه نزدیک‌تر برسد. پس از تبدیل تخم‌ها به فاخته‌های بالغ، جوامعی شکل می‌گیرند و بهترین مکان‌های زیست‌بوم برای آن‌ها مشخص می‌شود. این فاخته‌ها سپس به این بهترین مکان‌ها مهاجرت می‌کنند و تخم‌گذاری در لانه‌های تصادفی داخل محدوده‌های خود را انجام می‌دهند. این فرآیند تا رسیدن به بهترین موقعیت با بیشترین ارزش سود ادامه می‌یابد و جمعیت فاخته‌ها در این مکان تجمع می‌پذیرد.

مفاد

1. جستجوی فاخته
2. راه رفتن اختیاری و اندازه قدم
3. اجرا
4. جستجوی شرح داده شده فاخته
5. جستجوی بلبل چند منظوره
6. ترکیب سازی
7. اجرا
8. مرجع

جستجوی فاخته

جستجوی فاخته از اصول زیر پیروی می‌کند:

هر تخم در هر آشیانه نمایانگر یک راه حل است و تخم فاخته یک راه حل جدید را نشان می‌دهد. هدف آن است که راه حل‌های جدید و احتمالاً بهتر (تخم های فاخته ها) جایگزین راه حل های نه چندان خوبِ موجود در لانه ها شوند. در ساده‌ترین حالت، هر آشیانه یک تخم دارد؛ ولی این الگوریتم می‌تواند به موارد پیچیده‌ تری تعمیم داده شود که در آن هر آشیانه حاوی چندین تخم (یا به عبارتی چندین راه حل) است.

جستجوی فاخته سه قانون ایده آل سازی شده دارد:

1. هر فاخته در هر بار فقط یک تخم می گذارد و تخم خود را در آشیانه ای می اندازد که بصورت تصادفی انتخاب شده است.
2. بهترین آشیانه‌ها با بهترین کیفیت تخم‌ها به نسل بعدی منتقل می‌شوند.
3. تعداد آشیانه‌های میزبان ثابت است و تخم فاخته با احتمال p_a توسط پرنده میزبان کشف می شود. در این صورت، پرنده ی میزبان می تواند یا تخم را بیرون بیندازند و یا آشیانه را ترک کرده و یک آشیانه ی جدید بسازد.

یانگ و دب با کشف عملکرد تعدادی از بهترین اشیانه‌ها و کشف راه حل‌هایی با احتمال (اوه) έ pa کشف کردند که دسته پرندگان لری (lery) جستجوی نحوه راه رفتن اتفاقی را در مقایسه با راه رفتن ساده تصادفی بهتر انجام می‌دهند.

کد

کد ساختگی می‌تواند به شکل زیر خلاصه بندی شود: تابع هدف: f(x) و x=(x1 و x2و …و xd)و

                                                                          :جمعیت اولیه n اشیانه میزبان را ایجاد کنید
                                                                          (توقف ضابطه) یا (بیشترین مقدار تولید> t) در حالیکه

یک بلبل را به‌طور تصادفی انتخاب کنید (بگویید، I) و با اجرای دسته پرندگان لری راه حل آن را جایگزین کنید.

                                           کیفیت و ثبات fi را ارزیابی کنید
                                                              و {(xi)f α.  fi و برای بیشترین)
                                                               و اشیانه‌ای را در بین n (بگویید، j) به‌طور تصادفی انتخاب کنید
                                                                                                  و (fj <fi) اگر

J را جانشین راه حل جدیدی کنید

                                                                                                                    و اگر

یک کسر (pa) از بدترین اشانه‌ها ترک می‌شود و یک اشیانه جدید ساخته می‌شود:

                                            بهترین راهئ حل / اشیانه را انتخاب کنید.
                        راه حل‌ها / اشیانه‌ها را طبقه‌بندی کنید و بهترین نمونه فعلی را پیدا کنید:
                          بهترین راه حل‌های فعلی را به تولید بعدی انتقال دهید.
                                                                                                                   و حال انکه پایان.

برترین امتیاز این الگوریتم سادگی ان است در حقیقت مقایسه با الگوریتم‌های؟ جمعیت محور یا عامل محور همچون بهینه‌سازی انبوه ذرات و جستجوی هماهنگ، در این جا ضرورتاً فقط یک پارامتر pa در cs وجود دارد (جدای تعداد جمعیت n). بنابراین انجام ان کار ساده‌ای است.

راه رفتن تصادفی و تعداد قدم

موضوع مهم اجرای دسته پرندگان لری و راه رفتن تصادفی در معادله کلی برای تنظیم راه حل‌های جدید است.

Xt+1 = xt+ sEt در حالیکه Et از نمودار معمول استاندارد همراه با میانگین صفر و انحراف معیار واحد برای راه رفتن تصادفی است یا برای دسته پرندگان لوی از نمودار لوی برداشت می‌شود. بدیهی است، راه رفتن تصادفی می‌توان به شباهت بین تخم بلبل و تخم میزبان ارتباط داده شود که می‌تواند در عمل سخت و مشکل باشد. در این جا اندازه قدم s تعیین می‌کند راه پیمای تصادفی چگونه بیشتر می‌تواند برای تعداد ثابتی iteration راه رود. ایجاد اندازه قدم لوی اغلب سخت و دشوار است و یک الگوریتم مناسب، الگوریتم مانتیگ نا است. اگر خیلی بزرگ باشد، سپس راه حل جدید ایجاد شده خیلی متفاوت از راه حل قدیم خواهد بود (یا حتی به لبه نوارها می‌پرد). سپس، چنین حرکتی بعید است که پذیزفته شود. اگر s خیلی کوچک باشد، تغییرات آنقدر اندک و ناچیز است که چشمگیر و قابل ملاحظه باشد و بنابراین چنین جستجویی مؤثر نیست. زیرا اندازه صحیح گام لازم است تا مقدار جستجو را تا حد کافی کار آمد و مؤثر حفظ کند. بر اساس یک مثال، برای گام برداشتن تصادفی ایزوتروپیک ساده، ما می‌دانیم میانگین فاصله r که به فضای d – بعدی حرکت می‌کند معادل رابطه زیر است: r2 = 2dDt در حالیکه d=22/2J ضریب مناسب انتشار است. در این جا s اندازه قدم یا فاصله طی شده در هر پرش است و J زمان صرف شده برای هر پرش است. معادله بالا اشاره بر ان دارد: S2=τr2/td برای L مقیاس طول نمونه از بعد مورد نظر، جستجوی محلی به‌طور نمونه در منطقه r=L/10 محدود می‌شود. برای ۱=τ و ۱۰۰۰ تا ۱۰۰=t، ما L01/0= s را برای d=۱ و L001 /0 =s را برای d=۱۰ داریم؛ بنابراین ما می‌توانیم برای اغلب مسایل از ۰۱/۰ تا ۰۰۱/۰ = s/L استفاده کنیم. اگر چه انحراف واقعی ممکن است به تجزیه و تحلیل دقیق رفتار دسته پرندگان لوی داشته باشد.

تحلیل و بررسی الگوریتم و همگرایی سودمند خواهد بود، زیرا مسایل باز زیادی در رابطه با متاهریستیک وجود دارد. اجرا: کد ساختگی به شکل ترتیبی داده شد، اما یانگ و دب به شکل برداری اجرا کردند که روش بسیار مؤثر و کارامدی است. در دنیای واقعی، اگر تخم بلبل مشابه تخم میزبان باشد، سپس این تخم بلبل کمتر احتمال دارد که کشف شود، بنابراین قابلیت باید تفاوت در راه حل‌ها ارتباط داشته باشد؛ بنابراین خوب است تا با مقداری از اندازه‌های گام تصادفی، به روش از پیش داوری شده، راه رفتن تصادفی را انجام دهیم. برای اجرای مطلب (matLab)، این راه رفتن از پیش داوری شده تصادفی می‌تواند تا حدی به وسیله رابطه زیر بدست آید: Stepsize= rand (nest (randperm(n)و)-nest(randperm(n)و))و New- nest= nest+stepsize. *k؛ در حالیکه k=rand(size(nest))> pa و pa سرعت کشف کردن است. یک مطلب cs استاندارد می‌تواند در این جا تعریف شود. نرم افراز شی- تنظیم شده اجرای جستجوی بلبل را با سانین طراحی کرد. به عبارت دیگر، الگوریتم تشریحی بلبل همچنین می‌تواند برای مسایل بهینه‌سازی غیرضروری انجام شود. اجرای منبع باز جستجوی بلبل شرح داده شده می‌تواند در این سایت http://code.google.com/p/modified-cs پیدا شود.

جستجوی بلبل شرح داده شده:

والتون و همکارانش با هدف سرعت بخشیدن به همگرایی، جستجوی بلبل استاندارد را توصیف کردند: توصیف شامل گام اضافی اطلاعاتی می‌شود که در بین تخم‌های بالایی مبادله می‌شود. نشان داده شده‌است که جستجوی بلبل شرح داده شده (mcs)، در اصطلاح سرعت‌های همگرایی، هنگام اجرای یک سری از توابع هدف benchmark بهینه‌سازی استاندارد، جستجوی بلبل استاندارد و الگوریتم‌های دیگر را اجرا می‌کند.

سپس، جستجوی بلبل شرح داده شده اجرا شده‌است تا شبکه بدون شکل و ساختاری را اصلاح کند که از هزینه محاسباتی به طرز قابل ملاحظه‌ای بکاهد. علاوه بر این، بهینه‌سازی دیگر جستجوی بلبل به اصطلاح جستجوی بلبل مقدار معینی با نتایج متقاعدکننده‌است.

جستجوی بلبل چند منظوره (mocs):

روش جستجوی بلبل چند منظوره (mocs) فرمول‌سازی شده‌است تا با مسایل بهینه‌سازی چند معیاری روبرو شود. این روش از وزن‌های تصادفی استفاده می‌کند تا اهداف چند گانه را با یک هدف تکی ترکیب کند. همچنین وزن‌ها به‌طور تصادفی متفاوت هستند. حوزه‌های پاریتو می‌توانند پیدا شوند بنابراین نقاط می‌توانند به‌طور معکوس در سراسر حوزه‌ها پراکنده شوند.

ترکیب‌سازی

اگر چه جستجوی بلبل یک الگوریتم بر پایه انبوه هوش است، اما هنوز می‌تواند با الگوریتم‌های دیگر بر پایه انبوه همچونpso ترکیب شود. برای مثال به نظر می‌رسد الگوریتم ترکیبی cs-pso نقص pso را اصلاح می‌کند. موارد استفاده: موارد استفاده جستجوی بلبل در مسایل بهینه‌سازی مهندسی در بازده پیش‌بینی شده آن نشان داده شده‌است. برای مثال، هم برای طرح پزیدن و هم برای مسایل طرح پرتوهای یکی شده، cs در مقایسه با راه حل‌های مقاله، راه حل‌های بهتری کسب کرد. الگوریتم جستجوی بلبل گسسته پیش‌بینی شده به تازگی طراحی می‌شود تا مسئله زمان‌بندی پرستاری را حل کند. روش محاسباتی مؤثر بر پایه جستجوی بلبل که برای انتشار اطلاعات در شبکه‌های حس‌گیری سیم فرض شده‌است. جستجوی بلبل بر پایه مقدار معین انجام شد تا مسایل کی تاپ سک (knapsack) را حل کند که تأثیر ان را نشان دهد. از جستجوی بلبل همچنین می‌توان استفاده کرد تا مسیرهای آزمایشی مستقل را برای آزمایش نرم‌افزار ساختاری و برای ایجاد اطلاعات آزمایشی به وجود آورد.

مقایسه مفهومی جستجوی بلبل با pso, dE, abc نشان می‌دهد که الگوریتم‌های cs و dE در مقایسه با pso و abc دقیق تری ارائه می‌دهند. مطالعه دقیق گسترده بر روی انواع مسایل بهینه‌سازی ساختاری نشان می‌دهد جستجوی بلبل در مقایسه با الگوریتم‌های دیگر نتایج بهتری به دست می‌دهد. علاوه بر این، رروش آزمایش نرم‌افزار جدید بر اساس جستجوی بلبل شکل گرفته‌است. علاوه بر این جستجوی بلبل به خصوص برای حل مسایل بزرگ مقیاس مناسب است. همان‌طور که در مطالعه اخیر نشان داده شده‌است جستجوی بلبل اجرا شده‌استتا شبکه‌های عصبی با عملکرد اصلاح شده‌ای پرورش یابند. علاوه بر این cs به شکل موفقیت‌آمیز اجرا می‌شود تا الگوهای عصبی spiking شکل گیرند. همچنین از جستجوی بلبل استفاده می‌شود تا فرایند ترکیب خدماتا و طراحی گراف‌ها بهینه‌سازی شود. جستجوی بلبل روش مطمئنی برای طرح سیستم کار گذاشته و بهینه‌سازی طرح از جمله مناسب‌ترین طرح ساختارهای فولادسازی است. مطالعات جدیدتر نشان می‌دهد که جستجوی بلبل می‌تواند در الگوریتم‌های دیگر در استفاده‌های نورد سازی، ساخت برنامه زمان‌بندی و موارد دیگر اجرا شود. یک استفاده جالب از جستجوی بلبل حل مسایل محدوده ارزش است.