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


الگوریتم بهینه سازی فاخته (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 بُعدی، زیستگاه، آرایهای به ابعاد است. این آرایه مکان کنونی فاخته در محیط را نشان میدهد. آرایه مذکور به شکل زیر تعریف میشود:
مقادیر متغیرهای اعشاری هستند. میزان سود یک زیستگاه، از طریق ارزیابی تابع سود در زیستگاه متشکل از مقادیر مشخص میشود. بنابراین تابع سود برای یک مسأله بهینهسازی داده شده به شکل زیر تعریف میشود.
چنانکه در رابطه بالا مشهود است، الگوریتم فاخته تابع سود را بیشینه میکند. در صورتی که هدف کمینهسازی یک تابع هزینه باشد، به راحتی میتوان از طریق بیشینهسازی تابع سود زیر، تابع هزینه را کمینه کرد:
فرآیند تکاملی الگوریتم بهینه سازی فاخته به این صورت است که در ابتدا یک ماتریس با اندازه از زیستگاههای کاندید تولید میشود. سپس برای هر زیستگاه تولید شده، تعدادی تصادفی تخم فاخته در نظر گرفته میشود. در طبیعت، هر فاخته به طور میانگین بین 5 تا 20 عدد تخم میگذارد. این اعداد، مقادیر کمینه و بیشینه (حد بالا و پایین) تعداد تخمهای مجاز (مقادیر متغیرها) در هر زیستگاه را تشکیل میدهند.
عادت دیگر فاختهها در جهان واقعی این است که معمولا در فاصله بیشینه از زیستگاه واقعی زندگی خود تخمگذاری میکنند. در الگوریتم فاخته، به این فاصله بیشینه، شعاع تخمگذاری گفته میشود. در یک مسأله بهینهسازی، شعاع تخمگذاری برای هر فاخته متناسب با تعداد کلی تخمها، حد پایین () و حد بالای () مقادیر متغیرها محاسبه میشود. بنابراین، شعاع تخمگذاری به شکل زیر تعریف میشود:
در این رابطه، پارامتر عددی صحیح است که مقدار بیشینه شعاع تخمگذاری را کنترل میکند.
با توجه به بکارگیری الگوریتمهای فراابتکاری در مباحثی همچون یادگیری ماشین، مهندسی کنترل و ...، «فرادرس» اقدام به انتشار فیلم آموزش الگوریتم بهینه سازی فاخته و پیاده سازی آن در MATLAB کرده که در ادامه متن به آن اشاره شده است.
- برای دیدن فیلم آموزش الگوریتم بهینه سازی فاخته و پیاده سازی آن در MATLAB + اینجا کلیک کنید.
روش تخمگذاری فاختهها
در مرحله بعد، هر فاخته در شعاع تخمگذاری خود و بهطور تصادفی، در لانه پرندههای میزبان تخمگذاری میکند. فرآیند تخمگذاری فاختهها در شکل زیر نمایش داده شده است.
پس از پایان فرآیند تخمگذاری، تخمهایی که شباهت کمتری به تخمهای پرنده میزبان دارند، توسط پرنده میزبان شناسایی شده و دور انداخته میشوند. بنابراین، پس از هر فرایند تخمگذاری از تخمهای فاخته از بین میروند. این مقدار معمولا برابر ده درصد تخمهای گذاشته شده است و تخمهایی را شامل میشود که در محیطهای حاوی منابع غذایی کم قرار دارند و در نتیجه توانایی همگرایی به جواب بهینه را ندارند. سایر تخمها در لانه پرنده میزبان رشد کرده، سر از تخم بیرون آورده و توسط پرنده میزبان تغذیه میشوند.
نکته بسیار جالب دیگر در مورد تخمگذاری و رشد فاختهها این است که تنها یک تخم در لانه پرنده میزبان رشد میکند. وقتی که جوجه فاخته زودتر از جوجههای پرنده میزبان سر از تخم بیرون میآورد، تخمهای پرنده میزبان را از لانه بیرون میاندازد. شایان توجه است که جوجه فاخته سه برابر بزرگتر از جوجههای پرنده میزبان است. بنابراین، حتی در حالتی که جوجههای پرنده میزبان زودتر از جوجه فاخته سر از تخم بیرون آورند، جوجه فاخته پس از تولد بیشتر منابع غذایی را مصرف میکند. در نتیجه، پس از چند روز جوجههای پرنده میزبان از گرسنگی تلف میشوند.
مهاجرت فاختهها
جوجههای فاخته پس از رشد کردن و بالغ شدن، تا مدتی در زیستگاه و جامعه خود به زندگی ادامه میدهند. با این حال، زمانی که دوره تخمگذاری آنها آغاز میشود به مناطقی مهاجرت میکنند که از یک سو منابع غذایی بیشتری در آنجا وجود داشته باشد و از سوی دیگر رنگ و الگوی تخمهای آنها شباهت زیادی به تخمهای پرنده میزبان در آن منطقه داشته باشد. جامعه فاختهای که بیشترین سود (بیشترین منابع غذایی و بهترین شرایط محیطی برای زندگی) را داشته باشد، به عنوان مقصد مهاجرت فاختهها در دیگر جوامع انتخاب میشود.
از آنجا که فاختههای بالغ در زیستگاه و محیط زندگی خود پراکنده شدهاند، به سختی میتوان تشخیص داد که هر فاخته به کدام جامعه فاختهای تعلق دارد. برای حل این مشکل، جمعیت فاختهای موجود در محیط، توسط الگوریتم خوشهبندی K-means گروهبندی میشوند (در شبیهسازیهای انجام شده، مناسبترین مقدار پارامتر k برای الگوریتم K-means، بین 3 تا 5 است). پس از گروهبندی جمعیت فاختهای، «سود میانگین» (Mean Profit) گروههای فاختهای ایجاد شده محاسبه میشود. بهترین زیستگاه موجود در گروه فاختهای که بیشترین سود میانگین را دارد، به عنوان زیستگاه هدف و مقصد مهاجرتی دیگر گروههای فاختهای انتخاب میشود. فاختهها، تمام مسیر را به سمت زیستگاه مقصد پرواز نمیکنند. بلکه بخشی از مسیر را با درجه انحراف خاصی از مقصد حرکت میکنند. نحوه حرکت فاختهها به سمت زیستگاه مقصد در شکل زیر آمده است.
همانطور که در شکل بالا مشهود است، هر فاخته تنها از مسیر را با درجه انحراف رادیان پرواز میکنند. پارامترهای و به فاختهها کمک میکنند تا مناطق بیشتری را برای یافتن زیستگاه بهینه با بیشترین منابع غذایی و بهترین شرایط زندگی جستجو کنند. برای هر فاخته، مقادیر و به شکل زیر تعریف میشوند.
در این رابطه، پارامتر یک عدد تصادفی بین 0 و 1 است که از توزیع یکنواخت تبعیت میکند. پارامتر نیز مقدار درجه انحراف از زیستگاه هدف را مشخص میکند (برای همگرایی بهینه جمعیت فاختهها به بهینه سراسری، مقدار برای پارامتر مناسب است).
تعادل جمعیت فاختهها در محیط
با توجه به اینکه همیشه باید تعادل در جمعیت فاختهها حفظ شود، پارامتر کنترلی به نام تعریف میشود. این پارامتر وظیفه دارد تا تعداد فاختههای موجود در محیط را کنترل و محدود کند. به دلیل کمبود منابع غذایی در محیط، از بین رفتن فاختهها به دست شکارچیان و بعضا نبود لانه مناسب برای رشد جوجهها، وجود پارامتر کنترلی برای کنترل جمعیت فاخته در الگوریتم بهینه سازی فاخته ضروری است. در الگوریتم بهینه سازی فاخته، تنها تعداد فاخته (که بیشترین مقدار سود را تولید میکنند) در محیط زنده میمانند.
همگرایی به جواب بهینه
بعد از تعدادی تکرار در الگوریتم بهینه سازی فاخته، تمامی جمعیت فاختهای به بهترین زیستگاه موجود در محیط همگرا میشوند. در این زیستگاه، تخمهای فاخته بیشترین شباهت را به تخم پرندگان میزبان خواهند داشت و بیشترین منابع غذایی محیط در این ناحیه یافت خواهند شد. به عبارت دیگر، زیستگاه بهینه، بیشترین مقدار سود را تولید خواهد کرد. وقتی که بیش از 95 درصد جمعیت فاختهها به یک زیستگاه همگرا شوند، فرآیند عملیاتی الگوریتم بهینه سازی فاخته به پایان خواهد رسید. در ادامه، شبه کد الگوریتم بهینه سازی فاخته نمایش داده شده است.
شبه کد الگوریتم بهینه سازی فاخته
- جمعیت فاختهها از طریق مقداردهی تصادفی به متغیرهای تابع هدف مسأله بهینهسازی مورد نظر مقدار دهی اولیه میشود.
- تعدادی تخم فاخته به هرکدام از فاختهها اختصاص داده میشود.
- برای هر فاخته، شعاع تخمگذاری مشخص میشود.
- هر فاخته در محدوده شعاع تخمگذاری مشخص شده اقدام به تخمگذاری میکند.
- تخمهای فاختهای که توسط پرنده میزبان شناسایی شوند (رنگ و الگوی این تخمها با تخمهای پرنده میزبان تفاوت دارد) از بین میروند.
- تخمهای فاخته باقی مانده، سر از تخم بیرون میآورند و رشد میکنند (بالغ میشوند).
- زیستگاه هر کدام از فاختههای بالغ ارزیابی میشود (میزان سود مشخص میشود).
- با توجه به پارامتر ، جمعیت فاختهای موجود در محیط کنترل میشود و فاختههایی که در بدترین زیستگاهها زندگی میکنند از بین میروند.
- جمعیت فاختهای خوشهبندی، سود میانگین گروههای فاختهای محاسبه و بهترین زیستگاه به عنوان مقصد مهاجرتی دیگر گروهها انتخاب میشود.
- جمعیت فاختهای به سمت زیستگاه بهینه انتخاب شده مهاجرت میکنند.
- در صورتی که جمعیت فاختهها به نقطه بهینه سراسری همگرا و یا بیش از 95 درصد جمعیت فاختهها به یک زیستگاه خاص همگرا شوند، اجرای الگوریتم متوقف میشود؛ در غیر این صورت، اجرای الگوریتم به گام 2 منتقل شده و الگوریتم دوباره اجرا میشود.
ویژگی مهم الگوریتم بهینه سازی فاخته، طبیعت تصادفی و احتمالی آن است. نقطه قوت الگوریتمهای بهینهسازی تصادفی در طبیعت احتمالی آنها نهفته است. ویژگی مذکور سبب میشود که این دسته الگوریتمها کمتر در دام «بهینه محلی» (Local Optimum) قرار بگیرند. همچنین، برخلاف دیگر الگوریتمهای بهینهسازی (خصوصا ریاضی)، داشتن اطلاعات اضافی در مورد مشتق تابع هدف الزامی نیست.
ارزیابی عملکرد الگوریتم بهینه سازی فاخته روی توابع هدف معیار
در این بخش، الگوریتم بهینه سازی فاخته روی دو تابع هدف معیار ارزیابی میشود. هدف از این آزمایش، ارزیابی عملکرد این الگوریتم در همگرایی به جواب بهینه سراسری و همچنین مشخص کردن تعداد تکرارهای لازم برای رسیدن به جواب بهینه سراسری است. توابع هدف استفاده شده با هدف ارزیابی عملکرد الگوریتمهای بهینهسازی در پیدا کردن مقادیر بهینه متغیرها جهت کمینهسازی طراحی شدهاند.
در ادامه توابع هدف معیار استفاده شده در این آزمایش تعریف میشوند. در تمامی حالات ارزیابی الگوریتم بهینه سازی فاخته، تعداد متغیرهای مسأله برابر 100 در نظر گرفته شده است. حد بالا و پایین برای مقادیر ممکن متغیرهای مسأله، به ترتیب برابر با 5 و 5- است. تعداد اولیه فاختهها برابر با 20 در نظر گرفته شده است. در هر تکرار از الگوریتم بهینه سازی فاخته، هر فاخته میتواند بین 5 تا 10 عدد تخم بگذارد.
تابع هدف اول
مشخصات و قیدهای عددی تابع هدف اول به شرح زیر است:
نمایش سهبُعدی تابع هدف اول در شکل زیر آمده است.
شکلهای زیر، نتیجه اجرای الگوریتم بهینهساری فاخته برای بهینهسازی تابع هدف اول را نشان میدهد. همانطور که در شکل مشهود است، همگرایی تنها طی 7 تکرار حاصل شده است. تمامی فاختهها به جواب بهینه سراسری همگرا شدهاند. در تکرارهای ابتدایی الگوریتم، جمعیت فاختهها به سمت زیستگاه حاوی جواب بهینه سراسری مهاجرت میکنند. سپس در تکرارهای آتی، فاختهها هر چه بیشتر به زیستگاه حاوی جواب بهینه سراسری نزدیک و نزدیکتر میشوند. در نهایت، در تکرار هفتم، تقریبا تمام فاختهها به جواب بهینه سراسری همگرا میشوند. در چنین حالتی، الگوریتم به شرط توقف مشخص شده میرسد و به کار خود پایان میدهد. شکل اول، پراکندگی جمعیت ابتدایی فاختهها در محیط را نشان میدهد. شکل دوم، نزدیک شدن جمعیت فاختهها به جواب بهینه سراسری پس از 3 تکرار را نشان میدهد. شکل سوم، همگرایی کامل جمعیت فاختهها را به جواب بهینه سراسری پس از 7 تکرار نشان میدهد.
تابع هدف دوم
تابع هدف دوم، یک تابع هدف n-بُعدی است که با هدف کمینهسازی طراحی شده است و به آن تابع هدف Rastrigin گفته میشود.
مشخصات و قیدهای عددی تابع هدف Rastrigin به شرح زیر است:
نمایش سهبُعدی تابع هدف دوم در شکل زیر آمده است.
همانطور که در شکل مشاهده میشود، تابع هدف Rastrigin یکی از چالشبرانگیزترین توابع هدف برای مقاصد بهینهسازی است. این تابع، تعداد زیادی بهینه محلی دارد و احتمال قرار گرفتن الگوریتم بهینهسازی در یکی از بهینههای محلی بسیار زیاد است. بنابراین، رسیدن به بهینه سراسری برای بسیاری از الگوریتمهای بهینهسازی بسیار سخت خواهد بود.
شکل زیر نحوه همگرایی الگوریتم بهینه سازی فاخته روی تابع هدف دوم را نشان میدهد. همانطور که در شکل مشهود است، در چند تکرار اول، جمعیت فاخته به بهترین زیستگاه موجود در محیط نزدیک میشوند. چنین پدیدهای، قدرت و سرعت بالای الگوریتم بهینه سازی فاخته در همگرایی به ناحیه حاوی جواب بهینه سراسری را نشان میدهد. در نهایت، در تکرار 101اُم، الگوریتم بهینه سازی فاخته به جواب بهینه سراسری (مقدار هزینه صفر) همگرا میشود.
نتایج نشان داده شده از ارزیابی الگوریتم بهینه سازی فاخته روی توابع هدف معیار، نشان دهنده عملکرد بالای الگوریتم در همگرایی به جواب بهینه سراسری است. همچنین، این الگوریتم در تعداد تکرارهای معدود قادر است تا تقریب بسیار خوبی از جواب بهینه واقعی ارائه دهد. کد الگوریتم بهینه سازی فاخته و توابع هدف معیار در زبان برنامهنویسی «متلب» (MATLAB) در ادامه آمده است.
پیادهسازی الگوریتم بهینه سازی فاخته در متلب
پیادهسازی تابع هدف Rastrigin در متلب
جمعبندی
الگوریتم بهینه سازی فاخته، الگوریتمی برای حل مسائل بهینهسازی پیوسته و غیر خطی است. این الگوریتم از رفتار گونه خاصی از پرندگان به نام فاخته الهام گرفته شده است. به طور خاص، از ویژگیهای منحصر به فرد این پرنده در تخمگذاری و تولید مثل برای پیادهسازی الگوریتم بهینه سازی فاخته استفاده شده است. هر فاخته، زیستگاهی برای زندگی دارد. فاختهها در زیستگاه خود شروع به تخمگذاری میکنند. تخمهایی که از بین نمیروند، رشد کرده و بالغ میشوند. فاخته برای تولید مثل به مناطقی مهاجرت میکند که بیشترین منابع غذایی و بهترین شرایط زندگی را داشته باشد. فاختهها در اطراف زیستگاه بهینه یافت شده اقدام به تخمگذاری میکنند.
این رویه سبب میشود تا محیط بیشتری از زیستگاه بهینه برای یافتن جواب بهینه سراسری جستجو شود. پس از تعدادی چرخه مهاجرتی، بیشتر جمعیت فاختهها به جواب بهینه سراسری مسأله بهینهسازی همگرا میشوند. نتایج ارزیابی نشان میدهد که این الگوریتم، سرعت و دقت بالایی در همگرایی به جواب بهینه توابع هدف معیار دارد. حتی در مواردی که تابع هدف تعداد زیادی جواب بهینه محلی دارد، این الگوریتم قادر است در تعداد کمی تکرار، به تقریب نزدیکی از جواب بهینه سراسری همگرا شود. الگوریتم بهینه سازی فاخته را میتوان به عنوان پیادهسازی موفق از فرآیند الهام گرفته شده از طبیعت در نظر گرفت.
فیلم آموزش الگوریتم بهینه سازی فاخته و پیاده سازی آن در MATLAB
در صورتی که به موضوع الگوریتم بهینهسازی فاخته علاقهمند هستید، میتوانید دوره ویدیویی آموزش این الگوریتم و پیادهسازی آن در متلب را در وب سایت فرادرس مشاهده کنید. در این دوره آموزشی، ابتدا با مقدمهای از مبحث بهینهسازی، دستهبندی الگوریتمهای بهینهسازی و ساز و کار آنها آشنا خواهید شد. سپس، با مبانی تئوری الگوریتم بهینهسازی فاخته آشنا میشوید. در ادامه، نحوه پیادهسازی این الگوریتم در متلب آموزش داده میشود. در انتها، عملکرد الگوریتم بهینهسازی فاخته برای بهینهسازی چندین تابع معیار مهم مورد ارزیابی قرار میگیرد. مدرس این دوره آموزشی مهندس منوچهر بابایی و مدت زمان آن 3 ساعت و 36 دقیقه است.
- برای دیدن فیلم آموزش الگوریتم بهینه سازی فاخته و پیاده سازی آن در MATLAB + اینجا کلیک کنید.
اگر نوشته بالا برای شما مفید بوده است، آموزشهای زیر نیز به شما پیشنهاد میشوند:
- مجموعه آموزشهای الگوریتمهای بهینهسازی هوشمند
- آموزش الگوریتم بهینهسازی ازدحام ذرات— شامل مباحث تئوری و عملی
- مجموعه آموزشهای هوش مصنوعی
- رویکرد هوش ازدحامی با استفاده از کلونی زنبور عسل مصنوعی برای حل مسائل بهینهسازی
- شبیهسازی تبرید (Simulated Annealing) — به زبان ساده
- الگوریتم تپه نوردی – مبانی و مفاهیم
^^
سلام و وقت بخیر
یک سوال داشتم در مورد الگوریتم فاخته
فرض کنید می خواهیم یک مدل برنامه ریزی خطی را با الگوریتم فاخته حل کنیم.
در کجای الگوریتم محدودیت های مدل برنامه ریزی خطی اعمال می شود؟
آیا در تعیین شعاع تخم گذاری تاثیرگذار است؟
سلام
این الگوریتم فاخته مربوط به چه گرایش کامپویتر می شود،
و آیا با نرم افزار دیگری هم بغیر از مطلب قابل پیاده سازی است ،
چه نرم افزاری؟
ممنون
با سلام؛
از همراهی شما با مجله فرادرس سپاسگزارم. الگوریتمهای بهینهسازی از جمله روشهای مورد استفاده در بهینهسازی ریاضیاتی هستند که در حوزه هوش مصنوعی و یادگیری ماشین به طور گستردهای مورد استفاده قرار میگیرند. شایان توجه است که مباحث بهینهسازی در کلیه زمینههای فنی و مهندسی و دیگر علوم، کاربرد دارند. امکان پیادهسازی هر الگوریتمی (فاخته یا دیگر الگوریتمهای بهینهسازی) در زبانهای برنامهنویسی گوناگون از جمله پایتون، جاوا، گو و دیگر زبانها نیز وجود دارد.
شاد و پیروز باشید.
سلام
فوق العاده بود.
مرسی
با سلام
ضمن تشکر از به اشتراک گذاشتن مطالب علمی.
برای بهتر شدن این کار شاید اگر رفرنس های مطلب و همچنین راه ارتباطی با نویسنده مطلب برای تبادل نظر نوشته شود، خیلی بهتر خواهد شد.
با احترام
خیلی ممنون.
مطلب بسیار جالبی بود.