۱۳

۷

۶

۱۲

۲

۵

۹

۴

۱۱

۳

۱

۱۰

۸

شکل ۴-۱۱ نحوه عملکرد عملگر جهش در الگوریتم ژنتیک
۴-۳-۳ الگوریتم جستجوی فاخته
بعد از معرفی شدن روش های بهینه سازی تکاملی اولیه مثل الگوریتم ژنتیک، الگوریتم تبرید تدریج^[۱۲۰]، تحقیقات زیادی روی روش های تکاملی بهینه سازی که از طبیعت الهام گرفته شده بودند انجام گرفت، که می توان به الگوریتم جستجوی فاخته^[۱۲۱]، الگوریتم ازدحام ذرات (PSO)، کلونی مورچگان (ACO)، الگوریتم زنبور عسل (ABC) و الگوریتم ماهی­های مصنوعی^[۱۲۲] اشاره کرد. که کاربردهای بسیاری در حل مسائل بهینه سازی دارند. در بین این الگوریتم ها الگوریتم بهینه سازی فاخته یکی از جدیدترین و قویترین روش های بهینه سازی تکاملی می باشد که تاکنون معرفی شده اند. الگوریتم فاخته با الهام از روش زندگی پرنده ای به نام فاخته است که در سال ۲۰۰۹ توسط شین او یانگ و دب ساوش، توسعه یافته است. الگوریتم فاخته بر اساس زندگی گونه ای از فاخته است. این الگوریتم توسط پرواز لووی^[۱۲۳] به جای پیاده روی ایزوتروپتیک تصادفی ساده توسعه یافته است.
فاخته پرنده­ایست که برای خود لانه نمی سازد و تخم‌های خود را در لانه‌ی دیگر پرندگان می‌گذارد. فاخته در هنگام تخم­گذاری در لانه پرنده­های دیگر(میزبان) ممکن است برخی تخم‌های پرنده‌ی میزبان را از بین ببرد. با اینکار فاخته پرندگان میزبان را وادار به همکاری در ادامه ی نسل خود می کند. فاخته لانه‌ای با تخم‌های تازه انتخاب می­ کند. معمولا تخم فاخته در رنگ و طرح شبیه تخم پرندگان میزبان است ولی در اندازه اندکی بزرگ‌تر است تا جوجه فاخته‌ها زودتر از از تخم بیرون بیایند. مهارت گذاشتن تخم‌هایی شبیه به تخم یک پرنده‌ی خاص به طور تکاملی در فاخته‌های ماده بهبود می‌یابد. در این میان احتمال لو رفتن تخم فاخته توسط پرنده میزبان نیز وجود دارد. ممکن است پرنده ی میزبان متوجه چیزی شود. در این زمان پرنده میزبان یکی از تخم‌ها را تصادفی از لانه بیرون می‌اندازند که ممکن است این تخم یکی از تخم‌های خودش باشد. برخی اوقات پرنده میزبان لانه را ترک می‌کند و لانه‌ی دیگری برای خود می‌سازد. تکامل در شباهت برای مقابله با این وضعیت است.

( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )

جوجه­های فاخته شباهت زیادی با جوجه‌های میزبان دارند رفتار غذاخواهی آن ها را تقلید می‌کنند. جوجه­های فاخته حتی ممکن است تخم‌ها یا جوجه‌های پرنده‌ی میزبان را از لانه بیرون ‌اندازد. یا طی چند روز اول آنقدر غذا می‌خورد که بقیه از گرسنگی بمیرند. جوجه فاخته معمولا تنها جوجه باقیمانده در لانه می‌شود. الگوریتم جستجوی فاخته با در نظر گرفتن خصوصیت اخلاقی فاخته و توزیع رفتار پرواز پرندگان در فضای جواب به جستجو می ­پردازد.
قوانین جستجوی فاخته
هر فاخته در هر زمان یک تخم می‌گذارد.
آن را در یک لانه‌ی تصادفی قرار می‌دهد.
بهترین لانه‌ها با کیفیت بالای تخم، نسل بعدی را تشکیل می‌دهند.
تعداد لانه‌های میزبان ثابت است.
تخمی که توسط فاخته گذاشته شده است، با یک احتمال p_a [۰, ۱] توسط پرنده‌ی میزبان کشف می‌شود.
در این حالت پرنده‌ی میزبان می‌تواند تخم را دور بیاندازد یا لانه را ترک کند و یک لانه‌ی کاملا جدید برای خود بسازد.
کسر P_a از n تعداد لانه‌ها.
این لانه‌ها با لانه‌های جدید (با راه حل‌های جدید) جایگزین می شوند.
هر تخم در هر لانه نمایش دهنده یک راه حل کاندیدا است. یک تخم فاخته که از طریق پرواز لووی به وجود می آید، نمایش دهنده ی یک راه حل جدید است n لانه‌ی میزبان به طور تصادفی در زیستگاه ایجاد می‌شود. هر کدام از این لانه‌ها متعلق به یک فاخته است. هر کدام دارای یک تخم (راه حل کاندیدا) هستند. این فاخته‌ها جمعیت اولیه را تشکیل می‌دهند. برای هر یک میزان برازندگی محاسبه می‌شود.
شبه­کد
شبه­کد الگوریتم جستجوی فاخته طراحی­شده برای حل مساله بهینه­سازی فوق در ادامه آورده شده­است:
پارامترهای مدل بهینه سازی را بخوان
پارامترهای الگوریتم (از جمله تعداد لانه­ها، تعداد فاخته­های مزاحم، پارامترهای α و p_a) را مقدار دهی کن
جمعیت اولیه را بساز.
لانه­های (جواب­های) فوق را برازش کن.
حلقه زیر را تا پیش از برقراری شرط توقف اجرا کن (حلقه اصلی الگوریتم)
فاخته­های مزاحم را مشخص کن (i).
لانه­ای را به تصادف اتخاب کن (j).
به کمک پرواز لووی، مکان جدیدی را برای فاخته­ مزاحم (i) تعیین کن.
به کمک فرایند موجه­سازی، جواب­ حاصله را موجه کن.
لانه­ فوق را برازش کن.
در صورتی که مقدار تابع هدف آن بهتر از مقدار تابع هدف لانه (j) باشد، آن را جایگزین کن.
تعدادی از بدترین لانه­ها (p_a) را انتخاب کرده و به کمک پرواز لووی، مکان جدیدی را برایشان تعیین کن.
به کمک فرایند موجه­سازی، جواب­های فوق را موجه کن.
جواب­های فوق را برازش کن.
نتایج نهایی را نمایش داده و ذخیره کن.
شکل ۴-۱۲ شبه کد ارائه شده در برای الگوریتم جستجوی فاخته
پرواز لووی:
برای پیاده­سازی پرواز لووی از رابطه زیر استفاده کن.