الگوریتم بهینه سازی فاخته – از صفر تا صد

۳۱۶۱ بازدید
آخرین به‌روزرسانی: ۲۱ تیر ۱۴۰۲
زمان مطالعه: ۲۰ دقیقه
الگوریتم بهینه سازی فاخته – از صفر تا صد

الگوریتم بهینه سازی فاخته (Cuckoo Optimization Algorithm) یکی از الگوریتم‌های توسعه داده شده برای حل «مسائل بهینه‌سازی غیرخطی» (Non-Linear Optimization Problems) و «مسائل بهینه‌سازی پیوسته» (Continuous Optimization Problems) محسوب می‌شود. این الگوریتم، از زندگی خانواده‌ای از پرندگان به نام «فاخته» (Cuckoo) الهام گرفته شده است. الگوریتم بهینه سازی فاخته براساس شیوه زندگی بهینه و ویژگی‌های جالب این گونه، نظیر تخم‌گذاری و تولید مثل آن‌ها ساخته شده است.

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

فاخته‌های بالغ تحت تأثیر ویژگی‌های محیطی و به امید یافتن محیط بهینه برای زندگی و تولید مثل، به صورت گروهی مهاجرت می‌کنند. در این الگوریتم، محیط بهینه همان «بهینه سراسری» (Global Optimum) در تابع هدف مسأله بهینه‌سازی خواهد بود. این الگوریتم تاکنون در سناریوهای بهینه‌سازی مختلف و کاربردهای جهان واقعی، عملکرد خوبی از خود نشان داده است.

در ادامه معرفی مختصری از «الگوریتم‌های تکاملی» (Evolutionary Algorithms) ارائه خواهد شد؛ سپس الگوریتم بهینه سازی فاخته و بخش‌های مختلف آن توضیح داده می‌شود. در نهایت، برخی از کاربردهای این الگوریتم در حل مسائل بهینه‌سازی مورد بررسی قرار می‌گیرد.

مقدمه‌ای از الگوریتم‌های تکاملی

به فرآیند تغییر و دستکاری ورودی‌ها و یا خصوصیات یک دستگاه، عملیات ریاضی یا یک آزمایش علمی که در جهت رسیدن به یک خروجی با جواب بهینه انجام می‌شود، بهینه‌سازی گفته می‌شود. در فرآیند بهینه‌سازی، ورودی‌، متغیرهای مسأله هستند.

خروجی این فرآیند، «برازندگی» (Fitness) نامیده می‌شود و فرآیند یا تابعی که قرار است بهینه شود، «تابع هدف» (Objective Function) نام دارد.

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

روش‌های متفاوتی برای حل یک مسأله بهینه‌سازی وجود دارد. دسته‌ای از این روش‌ها، روش‌های «بهینه‌سازی ریاضیاتی» (Mathematical Optimization) هستند که بر پایه فرآیندهای «قطعی» (Deterministic) ریاضی بنا نهاده شده‌اند. به این دسته فرآیندهای بهینه‌سازی، «برنامه‌نویسی ریاضی» (Mathematical Programming) نیز گفته می‌شود.

دسته دیگر، روش‌هایی هستند که از فرآیندهای طبیعی الهام گرفته شده‌اند. این دسته روش‌های بهینه‌سازی، مبتنی بر فرآیندهای تصادفی و روش‌های «مولد اعداد تصادفی» (Random Number Generator) هستند. چنین روش‌هایی معمولا کار خود را با مجموعه‌ای از متغیرهای اولیه شروع می‌کنند. این متغیرها به شکل تصادفی (یا شبه تصادفی) مقداردهی اولیه می‌شوند. روش‌های بهینه‌سازی الهام گرفته شده از طبیعت سعی دارند تا در یک فرآیند تکاملی، همگرایی جمعیت اولیه تولید شده از متغیرها را به بهینه سراسری تضمین و از این طریق، جواب بهینه را برای مسأله بهینه‌سازی تولید کنند.

یکی از معروف‌ترین و پر کاربرد‌ترین الگوریتم‌های بهینه‌سازی تکاملی،  «الگوریتم ژنتیک» (Genetic Algorithm) است. این الگوریتم از عملگرهایی برای تکامل جمعیت اولیه استفاده می‌کند که از تغییرات ژنتیکی طبیعی در موجودات زنده و اصل «انتخاب طبیعی» (Natural Selection) الهام گرفته شده‌اند. از جمله دیگر الگوریتم‌های تکاملی می‌توان به الگوریتم «بهینه‌سازی ازدحام ذرات» (Particles Swarm Optimization) اشاره کرد. این الگوریتم از رفتارهای اجتماعی پرواز پرندگان برای یافتن غذا یا حرکت گروهی و در جهت یکسان ماهی‌ها الهام گرفته شده است.

نمونه موفق دیگری از شبیه‌سازی فرآیندهای طبیعی برای حل مسائل بهینه‌‎سازی، الگوریتم «بهینه‌سازی کلونی مورچگان» (Ants Colony Optimization) است. این الگوریتم از رفتارهای اجتماعی مورچگان برای یافتن منابع غذایی الهام گرفته شده است؛ رفتار اجتماعی بهینه‌ای که از طریق باقی گذاشتن رد «فرومون» (Pheromone) در محیط حاصل می‌شود. رد فرومون به جا گذاشته شده از مورچگان در محیط، مسیر بهینه از کلونی تا منبع غذایی یافت شده را نشان می‌دهد.

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

مهم‌ترین مزایای استفاده از الگوریتم‌های تکاملی برای حل مسائل بهینه‌سازی عبارتند از:

  • این دسته از الگوریتم‌های بهینه‌سازی معمولا در برابر تغییرات پویای محیط عملیاتی بسیار مقاوم هستند. یکی از نقاط ضعف روش‌های سنتی بهینه‌سازی (نظیر بهینه‌سازی‌های ریاضی) این است که کوچک‌ترین تغییر ایجاد شده در محیط، جواب‌های بهینه از پیش یافته شده برای مسأله مورد نظر را عملا منسوخ می‌کند. در چنین حالتی، اجرای دوباره روش بهینه‌سازی برای تولید جواب‌های بهینه و متناسب با شرایط محیطی جدید الزامی است. در نقطه مقابل، الگوریتم‌های محاسبات تکاملی برای تطابق جواب‌های بهینه با شرایط محیطی در حال تغییر، بسیار مناسب هستند.
  • روش‌های بهینه‌سازی تکاملی در طیف وسیعی از کاربردها (خصوصا کاربردهای جهان واقعی) قابل استفاده هستند. از الگوریتم‌های تکاملی می‌توان برای حل تمامی مسائلی استفاده کرد که در قالب مسائل «بهینه‌سازی تابعی» (Function Optimization) قابل تعریف باشند.
  • الگوریتم‌های تکاملی را می‌توان با دیگر روش‌های بهینه‌سازی سنتی ترکیب کرد.
  • الگوریتم‌های تکاملی می‌توانند برای حل مسائلی استفاده شوند که برای آن‌ها جوابی وجود ندارد. یکی از مزیت‌های مهم الگوریتم‌های تکاملی قابلیت به‌کارگیری آن‌ها در دامنه کاربردهایی است که خبره انسانی (دانشی که برای عملکرد صحیح سیستم مورد نیاز است) در آن‌ها وجود ندارد. این قابلیت الگوریتم‌های تکاملی در «روال‌های حل مسأله خودکار» (Automated Problem-Solving Routines) بیشتر خودنمایی می‌کند. محققان به این نتیجه رسیده‌اند که استفاده از خبره انسانی در چنین سناریوهایی لزوما منجر به تولید نتایج بهتر نخواهد شد؛ اگرچه در صورت وجود خبره یا نیاز به قرارگیری یک خبره در کنار سیستم خودکار طراحی شده، حتما باید از مزایای دانش انسانی برای حل مسأله استفاده کرد.

با در نظر گرفتن چنین ویژگی‌هایی، الگوریتم‌های تکاملی برای دامنه وسیعی از کاربردها قابل استفاده خواهند بود. مهم‌ترین این کاربردها عبارتند از:

  • عملیات و کنترل سیستم‌های نیرو (کنترل بهینه سیستم‌های برق و قدرت، زمان‌بندی مولدهای جریان برق و سایر موارد).
  • مسائل ترکیبی با پیچیدگی «ان‌پی سخت» (NP-Hard).
  • بهینه‌سازی استراتژی‌های زمان‌بندی کارها.
  • فرآیندهای شیمیایی (تشخیص ساختارهای شیمیایی، پیش‌بینی ساختار کریستال‌ها، طراحی داروها و سایر موارد).
  • مسیریابی خودروها.
  • مسائل بهینه‌سازی چند هدفه (Multi-Objective Optimization Problems).
  • مدل‌سازی پارامترهای بهینه.
  • مسائل «پردازش تصویر» (Image Processing) و «شناسایی الگو» (Pattern Recognition).

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

فاخته‌ها و شیوه زندگی منحصر به فرد این گونه برای تولید مثل

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

در این میان، گونه خاصی از پرندگان وجود دارند که برای مراقبت از تخم‌های خود و بزرگ کردن آن‌ها به حیله‌گری متوسل می‌شوند. این دسته پرندگان، «انگل‌های جوجه‌گذاری» (Brood Parasite) نامیده می‌شوند. فاخته‌ها شناخته شده‌ترین گونه از این دسته پرندگان هستند. در ابتدا، فاخته ماده لانه‌ای برای مراقبت از تخم‌هایش پیدا می‌کند. سپس یکی از تخم‌های موجود در لانه پرنده میزبان را با یکی از تخم‌های خود جا به جا می‌کند و با تخم پرنده میزبان از آن منطقه فرار می‌کند؛ فرآیندی که بیش از ده ثانیه به طول نخواهد انجامید.

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

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

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

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

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

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

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

فاخته‌ها شرایط محیط زندگی را برای بقا ارزیابی می‌کنند. محیطی که بیشترین تعداد تخم‌های فاخته در آن رشد کنند و به فاخته بالغ تبدیل شوند، بیشترین «سود» (Profit) را به ارمغان خواهد آورد. به عبارت دیگر، فاخته در محیطی تخم‌گذاری می‌کند که نرخ بقای تخم‌ها بیشینه باشد. تخم‌هایی که زنده می‌مانند و به فاخته بالغ تبدیل می‌شوند، در محل زندگی خود جوامعی متشکل از تعدادی فاخته تشکیل می‌دهند. هر جامعه متشکل از فاخته‌ها در یک زیستگاه خاص از محیط زندگی می‌کنند.

بهترین زیستگاه، یا زیستگاهی که بیشترین منابع غذایی و شانس زنده ماندن برای فاخته‌ها را داشته باشد، به عنوان مقصد مهاجرتی دیگر جوامع انتخاب می‌شود. جوامع مهاجرت کننده، نزدیک بهترین زیستگاه سکنی می‌گزینند. با توجه به تعداد تخم‌های هر فاخته و فاصله فاخته تا بهترین زیستگاه، یک «شعاع تخم‌گذاری» (Egg Laying Area) برای هر فاخته تعیین می‌شود. سپس، هر کدام از فاخته‌ها به طور تصادفی در لانه‌های موجود درون این شعاع، تخم‌گذاری می‌کنند. این کار تا زمانی ادامه پیدا می‌کند که بهترین نقطه با بیشترین سود (بیشترین منابع غذایی و بالاترین شانس زنده ماندن) شناسایی شود؛ بیشتر فاخته‌ها اطراف این نقطه همگرا می‌شوند. در ادامه، مراحل الگوریتم بهینه سازی فاخته توضیح داده خواهند شد.

تولید زیستگاه‌های اولیه فاخته‌ها

برای حل یک مسأله بهینه‌سازی، در مرحله اول باید مقادیر متغیرهای مسأله را در قالب یک آرایه نمایش داد. در الگوریتم بهینه سازی فاخته، به آرایه نمایش دهنده مقادیر متغیرهای مسأله، «زیستگاه» (Habitat) گفته می‌شود. هر زیستگاه، یک نمونه یا یک جواب کاندید برای مسأله بهینه‌سازی مدنظر خواهد بود.

جواب‌های کاندید طی یک فرایند تکاملی به جواب بهینه سراسری همگرا می‌شوند. در یک مسأله بهینه‌سازی NVar بُعدی، زیستگاه، آرایه‌ای به ابعاد $$1\times(N_{var})$$ است. این آرایه مکان کنونی فاخته در محیط را نشان می‌‌دهد. آرایه مذکور به شکل زیر تعریف می‌شود:

$$habitat=\left[x_{1}, x_{2}, x_{3}, .....x_{N_{var}}\right]$$

مقادیر متغیرهای $$\left(x_{1}, x_{2}, x_{3}, .....x_{N_{var}}\right)$$ اعشاری هستند. میزان سود یک زیستگاه، از طریق ارزیابی تابع سود $$f_{p}$$ در زیستگاه متشکل از مقادیر $$\left(x_{1}, x_{2}, x_{3}, .....x_{N_{var}}\right)$$ مشخص می‌شود. بنابراین تابع سود برای یک مسأله بهینه‌سازی داده شده به شکل زیر تعریف می‌شود.

$$Profit=f_{p}\left(habitat\right)=f_{p}\left(x_{1}, x_{2}, x_{3}, .....x_{N_{var}}\right)$$

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

$$Profit=-Cost\left(habitat\right)=-f_{c}\left(x_{1}, x_{2}, x_{3}, .....x_{N_{var}}\right)$$

فرآیند تکاملی الگوریتم بهینه سازی فاخته به این صورت است که در ابتدا یک ماتریس با اندازه $$N_{Population}\times N_{Var}$$ از زیستگاه‌های کاندید تولید می‌شود. سپس برای هر زیستگاه تولید شده، تعدادی تصادفی تخم فاخته در نظر گرفته می‌‌شود. در طبیعت، هر فاخته به طور میانگین بین 5 تا 20 عدد تخم می‌گذارد. این اعداد، مقادیر کمینه و بیشینه (حد بالا و پایین) تعداد تخم‌های مجاز (مقادیر متغیرها) در هر زیستگاه را تشکیل می‌دهند.

عادت دیگر فاخته‌ها در جهان واقعی این است که معمولا در فاصله بیشینه از زیستگاه واقعی زندگی خود تخم‌گذاری می‌کنند. در الگوریتم فاخته، به این فاصله بیشینه، شعاع تخم‌گذاری گفته می‌شود. در یک مسأله بهینه‌سازی، شعاع تخم‌گذاری برای هر فاخته متناسب با تعداد کلی تخم‌ها، حد پایین ($$Var_{High}$$) و حد بالای ($$Var_{Low}$$) مقادیر متغیرها محاسبه می‌شود. بنابراین، شعاع تخم‌گذاری به شکل زیر تعریف می‌شود:

$$ELR=\alpha \times \frac{No. of. Current. Cuckoo's. Eggs }{Total. Number. of. Eggs.} \times(Var_{High} - Var_{Low})$$

در این رابطه، پارامتر $$\alpha$$ عددی صحیح است که مقدار بیشینه شعاع تخم‌گذاری را کنترل می‌کند.

با توجه به بکارگیری الگوریتم‌های فراابتکاری در مباحثی همچون یادگیری ماشین، مهندسی کنترل و ...، «فرادرس» اقدام به انتشار فیلم آموزش الگوریتم بهینه سازی فاخته و پیاده سازی آن در MATLAB کرده که در ادامه متن به آن اشاره شده است.

  • برای دیدن فیلم آموزش الگوریتم بهینه سازی فاخته و پیاده سازی آن در MATLAB + اینجا کلیک کنید.

روش تخم‌گذاری فاخته‌ها

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

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

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

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

مهاجرت فاخته‌ها

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

از آنجا که فاخته‌های بالغ در زیستگاه و محیط زندگی خود پراکنده شده‌اند، به سختی می‌توان تشخیص داد که هر فاخته به کدام جامعه فاخته‌ای تعلق دارد. برای حل این مشکل، جمعیت فاخته‌ای موجود در محیط، توسط الگوریتم خوشه‌بندی K-means گروه‌بندی می‌شوند (در شبیه‌سازی‌های انجام شده، مناسب‌ترین مقدار پارامتر k برای الگوریتم K-means، بین 3 تا 5 است). پس از گروه‌بندی جمعیت فاخته‌ای، «سود میانگین» (Mean Profit) گروه‌های فاخته‌ای ایجاد شده محاسبه می‌شود. بهترین زیستگاه موجود در گروه فاخته‌ای که بیشترین سود میانگین را دارد، به عنوان زیستگاه هدف و مقصد مهاجرتی دیگر گروه‌های فاخته‌ای انتخاب می‌شود. فاخته‌ها، تمام مسیر را به سمت زیستگاه مقصد پرواز نمی‌کنند. بلکه بخشی از مسیر را با درجه انحراف خاصی از مقصد حرکت می‌کنند. نحوه حرکت فاخته‌ها به سمت زیستگاه مقصد در شکل زیر آمده است.

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

همانطور که در شکل بالا مشهود است، هر فاخته تنها $$\%\lambda$$ از مسیر را با درجه انحراف $$\phi$$ رادیان پرواز می‌کنند. پارامترهای $$\lambda$$ و $$\phi$$ به فاخته‌ها کمک می‌کنند تا مناطق بیشتری را برای یافتن زیستگاه بهینه با بیشترین منابع غذایی و بهترین شرایط زندگی جستجو کنند. برای هر فاخته، مقادیر $$\lambda$$ و $$\phi$$ به شکل زیر تعریف می‌شوند.

$$\lambda \sim U(0, 1)$$

$$\phi \sim U(-\omega, \omega)$$

در این رابطه، پارامتر $$\lambda$$ یک عدد تصادفی بین 0 و 1 است که از توزیع یکنواخت تبعیت می‌کند. پارامتر $$\omega$$ نیز مقدار درجه انحراف از زیستگاه هدف را مشخص می‌کند (برای هم‌گرایی بهینه جمعیت فاخته‌ها به بهینه سراسری، مقدار $$\frac{\pi}{6}$$ برای پارامتر $$\omega$$ مناسب است).

تعادل جمعیت فاخته‌ها در محیط

با توجه به اینکه همیشه باید تعادل در جمعیت فاخته‌ها حفظ شود، پارامتر کنترلی به نام $$N_{Max}$$ تعریف می‌شود. این پارامتر وظیفه دارد تا تعداد فاخته‌های موجود در محیط را کنترل و محدود کند. به دلیل کمبود منابع غذایی در محیط، از بین رفتن فاخته‌ها به دست شکارچیان و بعضا نبود لانه مناسب برای رشد جوجه‌ها، وجود پارامتر کنترلی $$N_{Max}$$ برای کنترل جمعیت فاخته در الگوریتم بهینه سازی فاخته ضروری است. در الگوریتم بهینه سازی فاخته، تنها تعداد $$N_{Max}$$ فاخته (که بیشترین مقدار سود را تولید می‌کنند) در محیط زنده می‌مانند.

همگرایی به جواب بهینه

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

شبه کد الگوریتم بهینه سازی فاخته

  1. جمعیت فاخته‌ها از طریق مقداردهی تصادفی به متغیرهای تابع هدف مسأله بهینه‌سازی مورد نظر مقدار دهی اولیه می‌شود.
  2. تعدادی تخم فاخته به هرکدام از فاخته‌ها اختصاص داده می‌شود.
  3. برای هر فاخته، شعاع تخم‌گذاری مشخص می‌شود.
  4. هر فاخته در محدوده شعاع تخم‌گذاری مشخص شده اقدام به تخم‌گذاری می‌کند.
  5. تخم‌های فاخته‌ای که توسط پرنده میزبان شناسایی شوند (رنگ و الگوی این تخم‌ها با تخم‌های پرنده میزبان تفاوت دارد) از بین می‌روند.
  6. تخم‌های فاخته باقی مانده، سر از تخم بیرون می‌آورند و رشد می‌کنند (بالغ می‌شوند).
  7. زیستگاه هر کدام از فاخته‌های بالغ ارزیابی می‌شود (میزان سود مشخص می‌شود).
  8. با توجه به پارامتر $$N_{Max}$$، جمعیت فاخته‌ای موجود در محیط کنترل می‌شود و فاخته‌هایی که در بدترین زیستگاه‌ها زندگی می‌کنند از بین می‌روند.
  9. جمعیت فاخته‌ای خوشه‌بندی، سود میانگین گروه‌های فاخته‌ای محاسبه و بهترین زیستگاه به عنوان مقصد مهاجرتی دیگر گروه‌ها انتخاب می‌شود.
  10. جمعیت فاخته‌ای به سمت زیستگاه بهینه انتخاب شده مهاجرت می‌کنند.
  11. در صورتی که جمعیت فاخته‌ها به نقطه بهینه سراسری همگرا و یا بیش از 95 درصد جمعیت فاخته‌ها به یک زیستگاه خاص همگرا شوند، اجرای الگوریتم متوقف می‌شود؛ در غیر این صورت، اجرای الگوریتم به گام 2 منتقل شده و الگوریتم دوباره اجرا می‌شود.

ویژگی مهم الگوریتم بهینه سازی فاخته، طبیعت تصادفی و احتمالی آن است. نقطه قوت الگوریتم‌های بهینه‌سازی تصادفی در طبیعت احتمالی آن‌ها نهفته است. ویژگی مذکور سبب می‌شود که این دسته الگوریتم‌ها کمتر در دام «بهینه محلی» (Local Optimum) قرار بگیرند. همچنین، برخلاف دیگر الگوریتم‌های بهینه‌سازی (خصوصا ریاضی)، داشتن اطلاعات اضافی در مورد مشتق تابع هدف الزامی نیست.

ارزیابی عملکرد الگوریتم بهینه سازی فاخته روی توابع هدف معیار

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

در ادامه توابع هدف معیار استفاده شده در این آزمایش تعریف می‌شوند. در تمامی حالات ارزیابی الگوریتم بهینه سازی فاخته، تعداد متغیرهای مسأله برابر 100 در نظر گرفته شده است. حد بالا و پایین برای مقادیر ممکن متغیرهای مسأله، به ترتیب برابر با 5 و 5- است. تعداد اولیه فاخته‌ها برابر با 20 در نظر گرفته شده است. در هر تکرار از الگوریتم بهینه سازی فاخته، هر فاخته می‌تواند بین 5 تا 10 عدد تخم بگذارد.

تابع هدف اول

مشخصات و قیدهای عددی تابع هدف اول به شرح زیر است:

$$f=x+\sin(4x)+1.1y+ \sin(2y)$$

$$0<x, y<0, min: f(9.039, 8.668)=-8.5547$$

نمایش سه‌بُعدی تابع هدف اول در شکل زیر آمده است.

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

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

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

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

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

تابع هدف دوم

تابع هدف دوم، یک تابع هدف n-بُعدی است که با هدف کمینه‌سازی طراحی شده است و به آن تابع هدف Rastrigin گفته می‌شود.

مشخصات و قیدهای عددی تابع هدف Rastrigin به شرح زیر است:

$$f= 10n+ \sum_{i=1}^{n} (x_i^2 - 10 \cos (2\pi x_{i})), n=9$$

$$-5.12\leq x_{i} \leq 5.12, f(0,0,....,0)=0$$

نمایش سه‌بُعدی تابع هدف دوم در شکل زیر آمده است.

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

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

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

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

نتایج نشان داده شده از ارزیابی الگوریتم بهینه سازی فاخته روی توابع هدف معیار، نشان دهنده عملکرد بالای الگوریتم در همگرایی به جواب بهینه سراسری است. همچنین، این الگوریتم در تعداد تکرارهای معدود قادر است تا تقریب بسیار خوبی از جواب بهینه واقعی ارائه دهد. کد الگوریتم بهینه سازی فاخته و توابع هدف معیار در زبان برنامه‌نویسی «متلب» (MATLAB) در ادامه آمده است.

پیاده‌سازی الگوریتم بهینه سازی فاخته در متلب

1% -----------------------------------------------------------------
2% Cuckoo Optimization Algorithm (COA) by Ramin Rajabioun          %
3% Programmed by Ramin Rajabioun                                   %
4% -----------------------------------------------------------------
5% Paper: R. Rajabioun. Cuckoo Optimization Algorithm, Applied Soft
6% Computing 11 (2011) 5508�5518
7% ----------------------------------------------------------------%
8% This program implements a standard version of Cuckoo            %
9% Optimization Algorithm (COA) which minimizes any Cost Function  %
10% --------------------------------------------------------------- %
11% Email: r.rajabioun@ece.ut.ac.ir                                 %
12% Website: www.coasite.info                                       %
13% --------------------------------------------------------------- %
14%
15% To use the code easily prepare your cost function and type its  %
16% name in: costFunction = 'YourCostFunctionName', then set number %
17% of optimization parameters in "npar" and set the upper and lower%
18% bands of the problem                                            %
19% --------------------------------------------------------------- %
20clc, clear, close all
21%% Set problem parameters
22% select your cost function:
23costFunction = 'rastrigin';           % F6 +/-5.12
24npar  = 100;          % number of optimization variables
25varLo = -5;         % Lower  band of parameter
26varHi =  5;         % Higher band of parameter
27%% Set COA parameters
28numCuckooS = 5;             % number of initial population
29minNumberOfEggs = 2;        % minimum number of eggs for each cuckoo
30maxNumberOfEggs = 4;        % maximum number of eggs for each cuckoo
31maxIter = 100;              % maximum iterations of the Cuckoo Algorithm
32knnClusterNum = 1;          % number of clusters that we want to make
33motionCoeff = 9;            % Lambda variable in COA paper, default=2
34accuracy = -inf;           % How much accuracy in answer is needed
35maxNumOfCuckoos = 10;      % maximum number of cuckoos that can live at the same time
36radiusCoeff = 5;           % Control parameter of egg laying
37cuckooPopVariance = 1e-13;   % population variance that cuts the optimization
38%% initialize population:
39cuckooPop = cell(numCuckooS,1);
40% initialize egg laying center for each cuckoo
41for cuckooNumber = 1:numCuckooS    
42    cuckooPop{cuckooNumber}.center = ( varHi-varLo )*rand(1,npar) + varLo;
43end
44%% initialize COA cost minimization plot
45figure(1)
46hold on
47xlabel 'Cuckoo iteration'
48ylabel 'Cost Value'
49%% Start Cuckoo Optimization Algorithm
50iteration = 0;
51maxProfit = -1e20;        % Let initial value be negative number
52goalPoint = (varHi - varLo)*rand(1,npar) + varLo; % a random goalpoint to start COA
53globalBestCuckoo = goalPoint;
54globalMaxProfit = maxProfit;
55profitVector = [];
56while ( (iteration <= maxIter) && (-maxProfit > accuracy) )
57    
58    iteration = iteration + 1
59    
60    % initialize number of eggs for each cuckoo
61    for cuckooNumber = 1:numCuckooS        
62        cuckooPop{cuckooNumber}.numberOfEggs = floor( (maxNumberOfEggs - minNumberOfEggs) * rand + minNumberOfEggs );
63    end
64    % get total number of available eggs between all cuckooS
65    summ = 0;
66    for cuckooNumber = 1:numCuckooS
67        summ = summ + cuckooPop{cuckooNumber}.numberOfEggs;
68    end
69    % calculate egg laying radius for each Cuckoo, considering problem
70    % limitations and ratio of each cuckoo's eggs
71    for cuckooNumber = 1:numCuckooS
72        cuckooPop{cuckooNumber}.eggLayingRadius = cuckooPop{cuckooNumber}.numberOfEggs/summ * ( radiusCoeff * (varHi-varLo) );
73    end
74    % To lay eggs, we produced some radius values less than egg laying
75    % radius of each cuckoo
76    for cuckooNumber = 1:numCuckooS
77        cuckooPop{cuckooNumber}.eggLayingRadiuses = cuckooPop{cuckooNumber}.eggLayingRadius * rand(cuckooPop{cuckooNumber}.numberOfEggs,1);
78    end
79    
80    for cuckooNumber = 1:numCuckooS
81        params = cuckooPop{cuckooNumber}.center;        % get center values
82        tmpRadiuses = cuckooPop{cuckooNumber}.eggLayingRadiuses;
83        numRadiuses = numel(tmpRadiuses);
84        % divide a (hyper)circle to 'numRadiuses' segments
85        % This is to search all over the current habitat
86        angles = linspace(0,2*pi,numRadiuses);    % in Radians
87        newParams = [];
88        for cnt = 1:numRadiuses
89            addingValue = zeros(1,npar);
90            for iii = 1:npar
91                randNum = floor(2*rand)+1;
92                addingValue(iii) = (-1)^randNum * tmpRadiuses(cnt)*cos(angles(cnt)) + tmpRadiuses(cnt)*sin(angles(cnt));
93            end
94            newParams = [newParams; params +  addingValue ];
95        end
96        
97        
98        % check for variable limits
99        newParams(find(newParams>varHi)) = varHi;
100        newParams(find(newParams<varLo)) = varLo;
101        cuckooPop{cuckooNumber}.newPosition4Egg = newParams;
102    end
103    
104    % Now egg laying is done
105    
106    % Now that egg positions are found, they are laid, and so its time to
107    % remove the eggs on the same positions (because each egg only can go to one nest)
108    for cuckooNumber = 1:numCuckooS
109        tmpPopulation = cuckooPop{cuckooNumber}.newPosition4Egg;
110        tmpPopulation = floor(tmpPopulation * 1e20)/1e20;
111        ii = 2;
112        cntt = 1;
113        while ii <= size(tmpPopulation,1) || cntt <= size(tmpPopulation,1)
114            if all((tmpPopulation(cntt,:) == tmpPopulation(ii,:)))
115                tmpPopulation(ii,:) = [];
116            end
117            ii = ii + 1;
118            if ii > size(tmpPopulation,1) && cntt <= size(tmpPopulation,1)
119                cntt = cntt + 1;
120                ii = cntt + 1;
121                if ii > size(tmpPopulation,1)
122                    break
123                end
124            end
125        end
126        cuckooPop{cuckooNumber}.newPosition4Egg = tmpPopulation;
127    end    
128    
129     
130    % Now we evalute egg positions
131    for cuckooNumber = 1:numCuckooS
132        cuckooPop{cuckooNumber}.profitValues = -feval(costFunction,[cuckooPop{cuckooNumber}.center ; cuckooPop{cuckooNumber}.newPosition4Egg]);        
133    end
134    
135    % Now we check to see if cuckoo population is more than maxNumOfCuckoos
136    % this case we should keep 1st maxNumOfCuckoos cuckoos and kill the others
137    allPositions = [];
138    whichCuckooPopTheEggBelongs = [];
139    tmpProfits = [];
140    if numCuckooS > maxNumOfCuckoos
141        for cuckooNumber = 1:numCuckooS
142            tmpProfits = [tmpProfits; cuckooPop{cuckooNumber}.profitValues];
143            allPositions = [allPositions; [cuckooPop{cuckooNumber}.center; cuckooPop{cuckooNumber}.newPosition4Egg(:,1:npar)]];
144            whichCuckooPopTheEggBelongs = [whichCuckooPopTheEggBelongs; cuckooNumber*ones(size(cuckooPop{cuckooNumber}.newPosition4Egg(:,1:npar),1),1) ];
145        end
146        % now we sort cuckoo profits
147        [sortedProfits, sortingIndex] = sort(tmpProfits,'descend');
148        % Get best cuckoo to be copied to next generation
149        bestCuckooCenter = allPositions(sortingIndex(1),1:npar);
150        
151        sortedProfits = sortedProfits(1:maxNumOfCuckoos);
152        allPositions = allPositions(sortingIndex(1:maxNumOfCuckoos),:);
153        clear cuckooPop
154        for ii = 1:maxNumOfCuckoos
155            cuckooPop{ii}.newPosition4Egg = allPositions(ii,:);
156            cuckooPop{ii}.center = allPositions(ii,:);
157            cuckooPop{ii}.profitValues = sortedProfits(ii);
158        end
159        numCuckooS = maxNumOfCuckoos;
160    else
161        for cuckooNumber = 1:numCuckooS
162            tmpProfits = [tmpProfits; cuckooPop{cuckooNumber}.profitValues];
163            allPositions = [allPositions; [cuckooPop{cuckooNumber}.center; cuckooPop{cuckooNumber}.newPosition4Egg(:,1:npar)] ];
164            whichCuckooPopTheEggBelongs = [whichCuckooPopTheEggBelongs; cuckooNumber*ones(size(cuckooPop{cuckooNumber}.newPosition4Egg(:,1:npar),1),1) ];
165        end
166        [sortedProfits, sortingIndex] = sort(tmpProfits,'descend');
167        % Get best cuckoo to be copied to next generation
168        bestCuckooCenter = allPositions(sortingIndex(1),1:npar);
169    end
170    
171    maxProfit  = sortedProfits(1);
172    currentBestCuckoo = bestCuckooCenter;
173    currentMaxProfit = -feval(costFunction,currentBestCuckoo);
174    if currentMaxProfit > globalMaxProfit
175        globalBestCuckoo = currentBestCuckoo;
176        globalMaxProfit = currentMaxProfit;
177    end
178    
179    % Update cost minimization plot
180    plot(iteration, -globalMaxProfit,'ks','linewidth',2,'MarkerEdgeColor','k','MarkerFaceColor','g','MarkerSize',10)
181    title([ 'Curent Cost = ' num2str(-globalMaxProfit) ' , at Iteration = ' num2str(iteration) ])
182    pause(0.01)
183    
184    profitVector = [profitVector globalMaxProfit];
185    
186    % ======== now we have some eggs that are safe and will grow up ==========
187    %========= mating: =============
188    % first we put all egg positions under each other
189    allPositions = [];
190    whichCuckooPopTheEggBelongs = [];
191    for cuckooNumber = 1:numCuckooS
192        allPositions = [allPositions; cuckooPop{cuckooNumber}.newPosition4Egg(:,1:npar)];
193        whichCuckooPopTheEggBelongs = [whichCuckooPopTheEggBelongs; cuckooNumber*ones(size(cuckooPop{cuckooNumber}.newPosition4Egg(:,1:npar),1),1) ];
194    end
195    if sum(var(allPositions)) < cuckooPopVariance
196        break
197    else
198        [clusterNumbers, clusterCenters] = kmeans(allPositions,knnClusterNum);
199    end
200    % make newly made clusters
201    cluster = cell(knnClusterNum,1);
202    for ii = 1:knnClusterNum
203        cluster{ii}.positions = [];
204        cluster{ii}.profits = [];
205    end
206    
207    pointer = zeros(numel(cuckooPop),1);
208    for tmpCounter = 1:numel(cuckooPop)
209        nEggs = size(cuckooPop{tmpCounter}.newPosition4Egg,1);
210        pointer(tmpCounter) = nEggs;
211    end
212    for cnt = 1:length(clusterNumbers)
213        cluster{clusterNumbers(cnt)}.positions = [cluster{clusterNumbers(cnt)}.positions; cuckooPop{whichCuckooPopTheEggBelongs(cnt)}.newPosition4Egg(end-pointer(whichCuckooPopTheEggBelongs(cnt))+1,1:npar)];
214        cluster{clusterNumbers(cnt)}.profits   = [cluster{clusterNumbers(cnt)}.profits; cuckooPop{whichCuckooPopTheEggBelongs(cnt)}.profitValues(end-pointer(whichCuckooPopTheEggBelongs(cnt))+1)];
215        pointer(whichCuckooPopTheEggBelongs(cnt)) = pointer(whichCuckooPopTheEggBelongs(cnt)) - 1;
216    end
217    
218    % Determine the best cluster
219    f_mean = zeros(knnClusterNum,1);
220    for cnt = 1:knnClusterNum
221        f_mean(cnt) = mean(cluster{cnt}.profits);
222    end
223    [sorted_f_mean, sortingIndex_f_mean] = sort(f_mean,'descend');
224    maxFmean = sorted_f_mean(1);   indexOfBestCluster = sortingIndex_f_mean(1);
225    
226    % now that we know group with number 'indexOfBestCluster' is the best we 
227    % should select their best point az Goal Point of other groups
228    [maxProfitInBestCluster, indexOfBestEggPosition] = max(cluster{indexOfBestCluster}.profits);
229    goalPoint  = cluster{indexOfBestCluster}.positions(indexOfBestEggPosition,1:npar);
230    
231    % now all other mature Cuckoos must go toward this goal point for laying
232    % their eggs
233    numNewCuckooS = 0;
234    for cntClstr = 1:size(cluster,1)
235        tmpCluster = cluster{cntClstr};
236        tmpPositions = tmpCluster.positions;
237        for cntPosition = 1:size(tmpPositions,1)
238            tmpPositions(cntPosition,:) = tmpPositions(cntPosition,:) + ...
239                                          motionCoeff * rand(1,npar) .*  (goalPoint  - tmpPositions(cntPosition,:));
240        end
241        % check if variables are in range
242        tmpPositions(find( tmpPositions>varHi )) = varHi;
243        tmpPositions(find( tmpPositions<varLo )) = varLo;
244        % update cluster positions
245        cluster{cntClstr}.positions = tmpPositions;
246        cluster{cntClstr}.center = mean(tmpPositions);
247        % update number of cuckoos: numCuckooS
248        numNewCuckooS = numNewCuckooS + size(cluster{cntClstr}.positions,1);
249    end
250    numCuckooS = numNewCuckooS;
251    % update cuckooPop
252    clear cuckooPop
253    cuckooPop = cell(numCuckooS,1);
254    cntNumCuckooS = 1;
255    for cnt = 1:size(cluster,1)
256        tmpCluster = cluster{cnt};
257        tmpPositions = tmpCluster.positions;
258        for cntPosition = 1:size(tmpPositions,1)
259            cuckooPop{cntNumCuckooS}.center = cluster{cnt}.positions(cntPosition,1:npar);
260            cntNumCuckooS = cntNumCuckooS + 1;
261        end
262    end
263    % Copy the Best cuckoo and its randomized form of this population to go 
264    % to the next generation
265    currentBestCuckoo = bestCuckooCenter;
266    currentMaxProfit = -feval(costFunction,currentBestCuckoo);
267    if currentMaxProfit > globalMaxProfit
268        globalBestCuckoo = currentBestCuckoo;
269        globalMaxProfit = currentMaxProfit;
270    end
271    cuckooPop{end}.center = globalBestCuckoo; % This is because the best cuckoo will live longer and won't die right after egg laying
272    cuckooPop{end}.profitValues = -feval(costFunction,cuckooPop{end}.center);
273    tmp = rand(1,npar).*globalBestCuckoo;
274    tmp(find( tmp>varHi )) = varHi;
275    tmp(find( tmp<varLo )) = varLo;
276    cuckooPop{end-1}.center = tmp;
277    cuckooPop{end-1}.profitValues = -feval(costFunction,cuckooPop{end-1}.center);
278    
279end     % end of while
280%% Now Algorithm has stopped
281disp('Best Params = ')
282disp(globalBestCuckoo')
283fprintf('\n')
284disp('Cost = ')
285disp(-globalMaxProfit)
286% profit history is in:  profitVector
287costVector = - profitVector;
288figure
289plot(costVector,'-ks','linewidth',3,'MarkerEdgeColor','k','MarkerFaceColor','g','MarkerSize',15)
290xlabel 'Cuckoo Iteration'
291ylabel 'Cost Value'
292title(['Current Cost = ' num2str(costVector(end)) ', at iteration = ' num2str(iteration) ])

پیاده‌سازی تابع هدف Rastrigin در متلب

1function y = rastrigin(x)
2y = 10.0 * size(x,2) + sum(x .^2 - 10.0 * cos(2 * pi .* x),2);

جمع‌بندی

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

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

فیلم آموزش الگوریتم بهینه سازی فاخته و پیاده سازی آن در MATLAB

در صورتی که به موضوع الگوریتم بهینه‌سازی فاخته علاقه‌مند هستید، می‌توانید دوره ویدیویی آموزش این الگوریتم و پیاده‌سازی آن در متلب را در وب سایت فرادرس مشاهده کنید. در این دوره آموزشی، ابتدا با مقدمه‌‌ای از مبحث بهینه‌سازی، دسته‌بندی الگوریتم‌های بهینه‌سازی و ساز و کار آن‌ها آشنا خواهید شد. سپس، با مبانی تئوری الگوریتم بهینه‌سازی فاخته آشنا می‌شوید. در ادامه، نحوه پیاده‌سازی این الگوریتم در متلب آموزش داده می‌شود. در انتها، عملکرد الگوریتم بهینه‌سازی فاخته برای بهینه‌سازی چندین تابع معیار مهم مورد ارزیابی قرار می‌گیرد. مدرس این دوره آموزشی مهندس منوچهر بابایی و مدت زمان آن 3 ساعت و 36 دقیقه است.

  • برای دیدن فیلم آموزش الگوریتم بهینه سازی فاخته و پیاده سازی آن در MATLAB + اینجا کلیک کنید.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

^^

بر اساس رای ۲۱ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
منابع:
ScienceDirectMathWorksمجله فرادرس
۶ دیدگاه برای «الگوریتم بهینه سازی فاخته – از صفر تا صد»

سلام و وقت بخیر
یک سوال داشتم در مورد الگوریتم فاخته

فرض کنید می خواهیم یک مدل برنامه ریزی خطی را با الگوریتم فاخته حل کنیم.
در کجای الگوریتم محدودیت های مدل برنامه ریزی خطی اعمال می شود؟
آیا در تعیین شعاع تخم گذاری تاثیرگذار است؟

سلام
این الگوریتم فاخته مربوط به چه گرایش کامپویتر می شود،
و آیا با نرم افزار دیگری هم بغیر از مطلب قابل پیاده سازی است ،
چه نرم افزاری؟
ممنون

با سلام؛

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

شاد و پیروز باشید.

سلام
فوق العاده بود.
مرسی

با سلام
ضمن تشکر از به اشتراک گذاشتن مطالب علمی.
برای بهتر شدن این کار شاید اگر رفرنس های مطلب و همچنین راه ارتباطی با نویسنده مطلب برای تبادل نظر نوشته شود، خیلی بهتر خواهد شد.
با احترام

خیلی ممنون.
مطلب بسیار جالبی بود.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *