چکیدهمحیطهای پویا محیطهایی هستند که قابلیت تغییرات در طول زمان را به خود اختصاص میدهند. این تغییرات میتواند به طرق مختلف از جمله تغییر در پارامترها، توابع هدف یا محدودیتهای مسئله اتفاق افتد. در این راستا حوزهی وسیعی از علوم مختلف مانند مدیریت، اقتصاد، رایانه، ریاضیات و غیره با این تغییرات روبرو بوده که هم در بخش تئوری و هم به صورت عملی در جهان واقعی مطرح میشوند. به همین دلیل حل مسائل مربوط به محیطهای پویا که به حل مسائل بهینهسازی پویا معروفند از چند دههی گذشته تا به امروز مطرح بودهاند. مهمترین چالش در حل این گونه مسائل مربوط به نحوهی سازگاری با محیط تغییر یافتهی جدید میباشد. بنابراین نیاز به ردیابی و دنبال کردن نقطهی (نقاط) بهینهی جدید در فضای مسئله احساس میشود. برای برخورد با این چالش محققان بر آن شدند تا از الگوریتمهای تکاملی که الهام گرفته از فرآیندهای تکاملیاند و افزودن یکسری مکانیزمهای خاص بهرهگیرند. چالش دیگری که این مسائل با آن روبرو میشوند، یافتن بهینه(ها) به طور هر چه دقیقتر میباشد که برای این امر بایستی حتی الامکان از الگوریتمهایی با سرعت همگرایی و توانایی جستجوی محلی بالا استفاده کرد. الگوریتم بهینهسازی فاخته یکی از الگوریتمهای تکاملی است که در محیطهای ایستا سرعت همگرایی و توانایی جستجوی محلی بالایی از خود نشان داده است. از سویی پویاسازی این الگوریتم تاکنون بررسی نشده است. لذا هدف از این پژوهش پویاسازی و ارائهی نسخهی جدیدی از این الگوریتم میباشد. برای تحقق این موضوع ابتدا تغییراتی در ساختار اصلی الگوریتم استاندارد ایجاد شده و با بهرهگیری از یک مکانیزم خود-تطبیقی در شعاع تخمگذاری فاختهها، تلاش در افزایش سرعت همگرایی و توانایی جستجوی محلی صورت گرفته است. سپس جهت ردیابی بهینه(ها) بعد از تغییرات محیطی، از یک الگوریتم چند-دستهای، مکانیزم ایجاد دستهی آزادو نیز مکانیزم انحصار بهره گرفته میشود. همچنین جهت رویارویی با چالشهای مربوط به از دست دادن تنوع و حافظهی نامعتبر در دستههای همگرا شده، فاختههای هر دسته در شعاعی (که بر اساس طول گام حرکتی قلهها تعیین میگردد) اطراف بهترین فاختهی آن دسته پخش و مورد ارزیابی قرار میگیرند. در دستههای غیر همگرا نیز تنها شایستگی موقعیت فاختههای آن دسته مجدداًمحاسبه میشود. مکانیزم غیرفعالسازی از دیگر مکانیزمهایی است که جهت افزایش کارآیی الگوریتم در محیطهای پویا مطرح شده است. در نهایت بر اساس نتایج به دست آمده، الگوریتم پیشنهادی در مقایسه با اکثر الگوریتمها کارآیی بهتری از خود نشان داده است.واژههای كلیدی:مسائل بهینه سازی پویا، الگوریتمهای تکاملی و الگوریتم بهینه سازی فاخته فهرست مطالبعنوانصفحهفصل اول: مقدمه1فصل دوم: شرح مسئله42-1 محیطهای پویا و مسائل بهینهسازی پویا52-2 تغییرات پیوسته و ناپیوسته52-3 تغییرات سراسری و مقطعی62-4 اهدف62-5 خلاصهی فصل6فصل سوم: مفاهیم پایهای73-1 الگوریتم بهینهسازی فاخته83-1-1 روش زندگی و تخمگذاری فاختهها83-1-2 جزئیات الگوریتم بهینهسازی فاخته93-2 تابع محک قلههای متحرک123-3 معیار کارآیی133-4 خلاصهی فصل14فصل چهارم: راهکارهای پیشین154-1 ایجاد تنوع164-1-1 اعمال مهاجران تصادفی، مهاجران بر پایهی نخبه و ابر جهش به راه اندازی شده در الگوریتم ژنتیک در محیط پویا164-1-2 به کارگیری الگوریتم ممتیک بر اساس جستجوی محلی تپهنوردی در محیط پویا184-1-3 استفاده از الگوریتم ایمنی مصنوعی بر پایهی خودکار یادگیرنده در محیط پویا194-1-4 اعمال مکانیزم خود-سازگار در نرخ جابجایی روی الگوریتمهای تکاملی در محیط پویا214-1-5 چگونگی به کارگیری خودکار سلولی در الگوریتمهای تکاملی در محیطهای پویا224-2 به کارگیری حافظه244-2-1 حافظهی ضمنی244-2-2 حافظهی صریح244-3 روش چند-جمعیتی بودن274-3-1 به کارگیری الگوریتم بهینهسازی چند-جمعیتی ذرات سریع درمحیط پویا28فهرست مطالبعنوانصفحه4-3-2 الگوریتم بهینهسازی تجمعی ذرات با رویکرد افزودن گروه فرزند در محیط پویا304-3-3 به کارگیری الگوریتم بهینهسازی تجمعی ذرات با رویکرد وزن تطبیقی و خوشهبندی فازی در محیط پویا314-3-4 به کارگیری الگوریتم گروه ماهیهای مصنوعی با رویکرد چند-جمعیتی در محیط پویا324-3-5 به کارگیری الگوریتم کرم شبتاب با رویکرد ایجاد گروه در محیط پویا364-4 خلاصهی فصل40فصل پنجم: راهکار پیشنهادی و ارزیابی نتایج425-1 الگوریتم MCOA435-1-1 مکانیزم خود-تطبیقی شعاع تخمگذاری445-2 الگوریتم پیشنهادی MMCOAجهت بهینهسازی در محیطهای پویا465-2-1 بررسی همگرایی دستهها465-2-2 مکانیزم انحصار475-2-3 کشف تغییرات محیط485-2-4 رفع مشکل حافظهی نامعتبر و تنوع از دست رفته485-2-5 مکانیزم غیرفعالسازی495-3 تحلیل و ارزیابی نتایج505-3-1 تحلیل نتایج الگوریتم MMCOAدر فرکانس تغییرات و تعداد قلههای مختلف و مقایسه با دیگر الگوریتمها505-3-2 تحلیل نتایج الگوریتم MMCOAدر طول گام حرکتی مختلف قلهها و مقایسه با دیگر الگوریتمها755-3-3 تحلیل نتایج الگوریتم MMCOAبا تعداد ابعاد مختلف مسئله و مقایسه با دیگر الگوریتمها775-4 جمعبندی نتایج795-5 خلاصهی فصل80فصل ششم: نتیجهگیری و راهکارهای آتی826-1 نتیجهگیری836-2 راهکارهای آتی84مراجع85واژهنامه89 فهرست شکلهاعنوانصفحهشکل3‑1: نمایش نحوهی تخمگذاری در محدودهی ELR[4]10شکل3-2: نمایش نحوهی مهاجرت فاختهها به سمت موقعیت هدف [4]11شکل3-3: شبه کد الگوریتم بهینهسازی فاخته [4]11شکل4-1: شبه کد ایجاد تنوع در الگوریتم تکاملی [6]17شکل4-2: ساختار خودکار یادگیرنده[10]21شکل4-3: شبه کد بهینهسازی پویا با حافظهی صریح[6]25شکل4-4: شبه کد دستاورد چند-جمعیتی بودن[6]28شکل4-5: شبه کد الگوریتمDMAFSA [22]37شکل4-6: شبه کد الگوریتم SFA[23]39شکل 5-1: شبه کد الگوریتمMCOA45شکل 5-2: کارنمای الگوریتمMCOA47شکل 5-3: شبه کد الگوریتمMMCOA50شکل 5-4: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 1 قله بر اساس تعداد ارزیابیها54شکل 5-5: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 1 قله بر اساس ...54شکل 5-6: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 5 قله بر اساس تعداد ارزیابیها55شکل 5-7: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 5 قله بر اساس ...55شکل 5-8: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 10 قله بر اساس تعداد ارزیابیها55شکل 5-9: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 10 قله بر اساس ...55شکل 5-10: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 20 قله بر اساس تعداد ارزیابیها56شکل 5-11: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 20 قله بر اساس ...56شکل 5-12: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 30 قله بر اساس تعداد ارزیابیها56شکل 5-13: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 30 قله بر اساس ...56شکل 5-14: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 50 قله بر اساس تعداد ارزیابیها57شکل 5-15: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 50 قله بر اساس ...57شکل 5-16: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 100 قله بر اساس تعداد ارزیابیها57شکل 5-17: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 100 قله بر اساس ...57شکل 5-18: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 200 قله بر اساس تعداد ارزیابیها58فهرست شکلهاعنوانصفحهشکل 5-19: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 200 قله بر اساس ...58شکل 5-20: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 1 قله بر اساس تعداد ارزیابیها58شکل 5-21: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 1 قله بر اساس ...58شکل 5-22: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 5 قله بر اساس تعداد ارزیابیها59شکل 5-23: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 5 قله بر اساس ...59شکل 5-24: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 10 قله بر اساس تعداد ارزیابیها59شکل 5-25: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 10 قله بر اساس ...59شکل 5-26: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 20 قله بر اساس تعداد ارزیابیها60شکل 5-27: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 20 قله بر اساس ...60شکل 5-28: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 30 قله بر اساس تعداد ارزیابیها60شکل 5-29: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 30 قله بر اساس ...60شکل 5-30: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 50 قله بر اساس تعداد ارزیابیها61شکل 5-31: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 50 قله بر اساس ...61شکل 5-32: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 100 قله بر اساس تعداد ...61شکل 5-33: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 100 قله بر اساس ...61شکل 5-34: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 200 قله بر اساس تعداد ...62شکل 5-35: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 200 قله بر اساس ..62شکل 5-36: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 1 قله بر اساس تعداد ارزیابیها62شکل 5-37: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 1 قله بر اساس ...62شکل 5-38: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 5 قله بر اساس تعداد ارزیابیها63شکل 5-39: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 5 قله بر اساس ...63شکل 5-40: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 10 قله بر اساس تعداد ارزیابیها63شکل 5-41: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 10 قله بر اساس ...63شکل 5-42: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 20 قله بر اساس تعداد ارزیابیها64شکل 5-43: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 20 قله بر اساس ...64شکل 5-44: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 30 قله بر اساس تعداد ارزیابیها64شکل 5-45: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 30 قله بر اساس ...64فهرست شکلهاعنوانصفحهشکل 5-46: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 50 قله بر اساس تعداد ...65شکل 5-47: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 50 قله بر اساس ...65شکل 5-48: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 100 قله بر اساس تعداد ...65شکل 5-49: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 100 قله بر اساس ...65شکل 5-50: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 200 قله بر اساس تعداد ...66شکل 5-51: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 200 قله بر اساس ...66شکل 5-52: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 1 قله بر اساس تعداد ارزیابیها66شکل 5-53: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 1 قله بر اساس ...66شکل 5-54: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 5 قله بر اساس تعداد ارزیابیها67شکل 5-55: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 5 قله بر اساس ...67شکل 5-56: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 10 قله بر اساس تعداد ارزیابیها67شکل 5-57: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 10 قله بر اساس ...67شکل 5-58: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 20 قله بر اساس تعداد ارزیابیها68شکل 5-59: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 20 قله بر اساس ...68شکل 5-60: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 30 قله بر اساس تعداد ارزیابیها68شکل 5-61: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 30 قله بر اساس ...68شکل 5-62: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 50 قله بر اساس تعداد ارزیابیها69شکل 5-63: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 50 قله بر اساس ...69شکل 5-64: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 100 قله بر اساس تعداد ...69شکل 5-65: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 100 قله بر اساس ...69شکل 5-66: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 200 قله بر اساس تعداد ارزیابیها70شکل 5-67: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 200 قله بر اساس ...70شکل 5-68: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 1 قله بر اساس تعداد ارزیابیها70شکل 5-69: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 1 قله بر اساس ...70شکل 5-70: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 5 قله بر اساس تعداد ارزیابیها71شکل 5-71: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 5 قله بر اساس ...71شکل 5-72: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 10 قله بر اساس تعداد ...71فهرست شکلهاعنوانصفحهشکل 5-73: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 10 قله بر اساس ...71شکل 5-74: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 20 قله بر اساس تعداد ...72شکل 5-75: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 20 قله بر اساس ...72شکل 5-76: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 30 قله بر اساس تعداد ...72شکل 5-77: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 30 قله بر اساس ...72شکل 5-78: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 50 قله بر اساس تعداد ...73شکل 5-79: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 50 قله بر اساس ...73شکل 5-80: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 100 قله بر اساس تعداد ...73شکل 5-81: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 100 قله بر اساس ...73شکل 5-82: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 200 قله بر اساس تعداد ...74شکل 5-83: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 200 قله بر اساس ...74شکل 5-84: نمودار پایداری الگوریتم MMCOAدر سناریوی دو تابع محک قلههای متحرک74شکل 5-85: گراف خطای جاری الگوریتم MMCOAبا طول گام حرکتی 2 در قلهها بر اساس تعداد ارزیابیها76شکل 5-86: نمودار میلهای خطای جاری الگوریتم MMCOAبا طول گام حرکتی 2 در قلهها بر اساس تعداد تغییر ...76شکل 5-87: گراف خطای جاری الگوریتم MMCOAبا طول گام حرکتی 3 در قلهها بر اساس تعداد ارزیابیها77شکل 5-88: نمودار میلهای خطای جاری الگوریتم MMCOAبا طول گام حرکتی 2 در قلهها بر اساس تعداد تغییر ...77شکل 5-89: گراف خطای جاری الگوریتم MMCOAبا تعداد ابعاد 2 بر اساس تعداد ارزیابیها78شکل 5-90: نمودار میلهای خطای جاری الگوریتم MMCOAبا تعداد ابعاد 2 بر اساس تعداد تغییر محیطی78شکل 5-91: گراف خطای جاری الگوریتم MMCOAبا تعداد ابعاد 3 بر اساس تعداد ارزیابیها79شکل 5-92: نمودار میلهای خطای جاری الگوریتم MMCOAبا تعداد ابعاد 3 بر اساس تعداد تغییر محیطی79شکل 5-93: گراف خطای جاری الگوریتم MMCOAبا تعداد ابعاد 4 بر اساس تعداد ارزیابیها79شکل 5-94: نمودار میلهای خطای جاری الگوریتم MMCOAبا تعداد ابعاد 4 بر اساس تعداد تغییر محیطی79 فهرست جدولها عنوانصفحهجدول 5-1: مقادیر پارامترهای الگوریتم MMCOA51جدول 5-2: مقادیر پارامترهای MPB51جدول 5-3: مقایسهی خطای برونخطى (خطای استاندارد) الگوریتمها بر روی MPBبا S=1، فرکانسهای تغییر ...52جدول 5-4: مقایسهی خطای برونخطى (خطای استاندارد) الگوریتمها بر روی MPBبا f=5000، S=1 و تعداد قلههای ...54جدول 5-5: مقایسهی خطای برونخطى (خطای استاندارد) الگوریتمها بر روی MPBبا f=5000، M=10و طول گام ...75جدول 5-6: مقایسهی خطای برونخطى (خطای استاندارد) الگوریتمها بر روی MPBبا f=5000، M=10، S=1 و ابعاد ...77جدول 5-7: موارد کاربرد الگوریتم MMCOA80 فصل اول: مقدمهبهینهسازی، فرآیندی جهت پیداکردن مناسبترین مقدار از فعالیت(های) مورد نظر در حوزهی داده شده با توجه به منابع و محدودیتهای موجود میباشد. بر همین اساس این فرآیند میتواند طیف وسیعی از حوزههای علمی در شاخههای مختلف از جمله ریاضیات، آمار، علوم کامپیوتر، علوم مدیریتی و غیره و حتی مسائل روزمره را پوشش دهد. بنابراین پرداختن به مسائل مربوط به بهینهسازی از اهمیت خاصی برخوردار بوده و به عنوان یکی از اصلیترین رویههای تحقیقاتی برای محققان به شمار میآید.در مسائل مطرح شده در حوزهی بهینهسازی طبقهبندیهای مختلفی بسته به حوزهی کاربردی وجود دارد. یکی از این طبقهبندیها بر اساس تغییرپذیری یا عدم تغییرپذیری محیط اطراف تعیین میشود. به این ترتیب در صورتیکه محیط شاهد عدم تغییرات در خود باشد مسائل مربوطه تحت عنوان مسائل بهینهسازی ایستا مطرح شده و در صورت تغییرات محیطی، با مسائل بهینهسازی پویا روبرو میگردد. در مسائل نوع اول هدف اصلی یافتن و یا تخمین هر چه بهتر نقطهی (نقاط) بهینه میباشد. این در حالی است که در مسائل نوع دوم نه تنها باید هدف اصلی در حالت ایستا ارضا شود بلکه بایستی بتوان هر چه سریعتر نقطهی (نقاط) بهینه را دنبال کرد. این امر از آنجا ناشی میشود که در محیطهای پویا به دلیل تغییرپذیری محیطی امکان تغییر نقطهی (نقاط) بهینه به منطقهی دیگری از فضای جستجو وجود دارد. بنابراین چنین مسائلی با چالشهای بیشتری نسبت به حالت ایستا مواجه میشوند. از این رو محققان بر آن شدند که از الگوریتمهایی بهرهگیرند که بتوانند خود را با شرایط متغیر محیطی وفق دهند. به این ترتیب توجه آنها به سمت الگوریتمهای تکاملی معطوف گردید. چرا که این الگوریتمها از تکامل طبیعی الهام گرفته و تکامل طبیعی نیز فرآیندی پیوسته از سازگاری با محیط میباشد.در پژوهشهای انجام شده تاکنون از سه روش اصلی در الگوریتمهای تکاملی برای حل مسائل بهینهسازی پویا استفاده شده است: (1) ایجاد تنوع، (2) به کارگیری حافظه و (3) رویکرد چند-جمعیتی. به دلیل امکان ایجاد تغییرات در فضایی که هیچ عضوی در آن حضور ندارد و یا امکان همگرایی اعضا در آن منطقه، از رویکرد ایجاد تنوع استفاده میشود. جهت تحقق این امر در الگوریتمهایی چون الگوریتم ژنتیک، از مهاجران تصادفی و گاهی از مکانیزم خود-تطبیقی در نرخ جابجایی مهاجران وارد شده به جمعیت بهره گرفته شده است. در الگوریتمهای کلونی مورچگان و کلونی زنبورهای مصنوعی از خودکار سلولی و در یک نمونه نیز از الگوریتم ایمنی مصنوعی بر پایهی خودکار یادگیرنده، استفاده شده است. همچنین محققان سعی کردند تا با به کارگیری حافظه و استفاده از بهترین اعضای جمعیت بتوانند الگوریتم ژنتیک را با محیطهایی که در معرض تغییرات کم قرار میگیرند تا حدی سازگار نمایند. در نمونههای دیگر از الگوریتمهایی چون الگوریتم بهینهسازی تجمعی ذرات[1]، الگوریتم گروه ماهیهای مصنوعی[2] و الگوریتم کرم شبتاب[3] از رویکرد چند-جمعیتی استفاده شدهکه در آنها از چندین جمعیت در فضای جستجو برای ایجاد تعادل بین اکتشاف[4] و استخراج[5] نقطهی (نقاط) بهینه و ردیابی هر چه بهتر آن(ها) بهره گرفته شده است.دراينپاياننامه يکيازجديدترينالگوريتمهايتکاملي،الگوريتمبهينهسازيفاخته[6]، برای حل مسائل بهینهسازی پویا ارائه میگردد. اينالگوريتمهمانطورکهازنامشپيداستازنحوهی زندگی پرندهای موسوم به فاخته الهام گرفته شده است. مسئلهای که در این جا وجود دارد اینست که الگوریتم فاخته برای حل مسائل بهینهسازی ایستا به کار رفته و نتایج خوبی را گزارش داده است. حال آنکه برای استفاده از این الگوریتم در حل مسائل بهینهسازی پویا یکسری مکانیزمهایی جهت ردیابی بهینه در زمان تغییرات و نیز برقراری نوعی تعادل در عملیات اکتشاف و استخراج، افزوده میشوند.در ادامه، در فصل دوم به شرح کلی مسئله، پیشفرضها و اهداف بهینهسازی در محیطهای پویا پرداخته و در فصل سوم جهت درک بهتر موضوع، مفاهیم پایهای و ابزارهای مورد استفاده برای حل مسائل مربوطه مطرح میگردد. در فصل چهارم نمونههایی از راهکارهای گذشته در زمینهی مسائل بهینهسازی پویا، مورد مطالعه قرار گرفته و در فصل پنجم راهکار پیشنهادی این تحقیق، نتایج ارزیابی و آزمایشات آورده میشود. در نهایت در فصل ششم نتیجهگیری کلی و راهکارهای آتی ارائه خواهد شد.در این فصل به شناخت محیطهای پویا و به تبع آن مسائل بهینهسازی پویا به عنوان مسئلهی اصلی این پژوهش، تغییرات به کار گرفته شده در فضای مسئله که در این پایاننامه به عنوان پیش فرض مورد استفاده قرار میگیرد و هدف مورد نظر برای حل این گونه مسائل پرداخته خواهد شد.محیطهای پویا، که به نام مسائل پویا[7]یا مسائل وابسته به زمان[8] شناخته میشوند، محیطهایی هستند که در طول زمان میتوانند شاهد تغییرات پیوسته یا گسسته در خود باشند. این تغییرات میتواند در حوزهی وسیعی اتفاق بیافتد. از جمله اینکه تعداد، ابعاد، دامنهی پارامترهای محیطی و یا دیگر ویژگیها میتواند تغییر کند. از دیگر مواردی که ممکن است اتفاق بیافتد، تغییر مقدار پارامترها با توجه به زمان است. در نهایت در کلیهی تغییرات ایجاد شده، محیط با تغییر نقطه یا نقاط بهینهی سراسری و محلی روبرو میگردد. مسایلی که در این حوزه تعریف میشوند هم در بخش آزمایشگاهی و هم در دنیای واقعی به این محیطها عینیت میبخشند. از جملهی آنها، مسائل بهینهسازی پویا[9]بوده که در آنها مقدار تابع برازندگی مرتب تغییر میکند. به طور دقیقتر در تعریف ریاضی این گونه مسائل خواهیم داشت
تغییر الگوریتم بهینه سازی فاخته جهت استفاده در محیط های پویا word
چکیدهمحیطهای پویا محیطهایی هستند که قابلیت تغییرات در طول زمان را به خود اختصاص میدهند. این تغییرات میتواند به طرق مختلف از جمله تغییر در پارامترها، توابع هدف یا محدودیتهای مسئله اتفاق افتد. در این راستا حوزهی وسیعی از علوم مختلف مانند مدیریت، اقتصاد، رایانه، ریاضیات و غیره با این تغییرات روبرو بوده که هم در بخش تئوری و هم به صورت عملی در جهان واقعی مطرح میشوند. به همین دلیل حل مسائل مربوط به محیطهای پویا که به حل مسائل بهینهسازی پویا معروفند از چند دههی گذشته تا به امروز مطرح بودهاند. مهمترین چالش در حل این گونه مسائل مربوط به نحوهی سازگاری با محیط تغییر یافتهی جدید میباشد. بنابراین نیاز به ردیابی و دنبال کردن نقطهی (نقاط) بهینهی جدید در فضای مسئله احساس میشود. برای برخورد با این چالش محققان بر آن شدند تا از الگوریتمهای تکاملی که الهام گرفته از فرآیندهای تکاملیاند و افزودن یکسری مکانیزمهای خاص بهرهگیرند. چالش دیگری که این مسائل با آن روبرو میشوند، یافتن بهینه(ها) به طور هر چه دقیقتر میباشد که برای این امر بایستی حتی الامکان از الگوریتمهایی با سرعت همگرایی و توانایی جستجوی محلی بالا استفاده کرد. الگوریتم بهینهسازی فاخته یکی از الگوریتمهای تکاملی است که در محیطهای ایستا سرعت همگرایی و توانایی جستجوی محلی بالایی از خود نشان داده است. از سویی پویاسازی این الگوریتم تاکنون بررسی نشده است. لذا هدف از این پژوهش پویاسازی و ارائهی نسخهی جدیدی از این الگوریتم میباشد. برای تحقق این موضوع ابتدا تغییراتی در ساختار اصلی الگوریتم استاندارد ایجاد شده و با بهرهگیری از یک مکانیزم خود-تطبیقی در شعاع تخمگذاری فاختهها، تلاش در افزایش سرعت همگرایی و توانایی جستجوی محلی صورت گرفته است. سپس جهت ردیابی بهینه(ها) بعد از تغییرات محیطی، از یک الگوریتم چند-دستهای، مکانیزم ایجاد دستهی آزادو نیز مکانیزم انحصار بهره گرفته میشود. همچنین جهت رویارویی با چالشهای مربوط به از دست دادن تنوع و حافظهی نامعتبر در دستههای همگرا شده، فاختههای هر دسته در شعاعی (که بر اساس طول گام حرکتی قلهها تعیین میگردد) اطراف بهترین فاختهی آن دسته پخش و مورد ارزیابی قرار میگیرند. در دستههای غیر همگرا نیز تنها شایستگی موقعیت فاختههای آن دسته مجدداًمحاسبه میشود. مکانیزم غیرفعالسازی از دیگر مکانیزمهایی است که جهت افزایش کارآیی الگوریتم در محیطهای پویا مطرح شده است. در نهایت بر اساس نتایج به دست آمده، الگوریتم پیشنهادی در مقایسه با اکثر الگوریتمها کارآیی بهتری از خود نشان داده است.واژههای كلیدی:مسائل بهینه سازی پویا، الگوریتمهای تکاملی و الگوریتم بهینه سازی فاخته فهرست مطالبعنوانصفحهفصل اول: مقدمه1فصل دوم: شرح مسئله42-1 محیطهای پویا و مسائل بهینهسازی پویا52-2 تغییرات پیوسته و ناپیوسته52-3 تغییرات سراسری و مقطعی62-4 اهدف62-5 خلاصهی فصل6فصل سوم: مفاهیم پایهای73-1 الگوریتم بهینهسازی فاخته83-1-1 روش زندگی و تخمگذاری فاختهها83-1-2 جزئیات الگوریتم بهینهسازی فاخته93-2 تابع محک قلههای متحرک123-3 معیار کارآیی133-4 خلاصهی فصل14فصل چهارم: راهکارهای پیشین154-1 ایجاد تنوع164-1-1 اعمال مهاجران تصادفی، مهاجران بر پایهی نخبه و ابر جهش به راه اندازی شده در الگوریتم ژنتیک در محیط پویا164-1-2 به کارگیری الگوریتم ممتیک بر اساس جستجوی محلی تپهنوردی در محیط پویا184-1-3 استفاده از الگوریتم ایمنی مصنوعی بر پایهی خودکار یادگیرنده در محیط پویا194-1-4 اعمال مکانیزم خود-سازگار در نرخ جابجایی روی الگوریتمهای تکاملی در محیط پویا214-1-5 چگونگی به کارگیری خودکار سلولی در الگوریتمهای تکاملی در محیطهای پویا224-2 به کارگیری حافظه244-2-1 حافظهی ضمنی244-2-2 حافظهی صریح244-3 روش چند-جمعیتی بودن274-3-1 به کارگیری الگوریتم بهینهسازی چند-جمعیتی ذرات سریع درمحیط پویا28فهرست مطالبعنوانصفحه4-3-2 الگوریتم بهینهسازی تجمعی ذرات با رویکرد افزودن گروه فرزند در محیط پویا304-3-3 به کارگیری الگوریتم بهینهسازی تجمعی ذرات با رویکرد وزن تطبیقی و خوشهبندی فازی در محیط پویا314-3-4 به کارگیری الگوریتم گروه ماهیهای مصنوعی با رویکرد چند-جمعیتی در محیط پویا324-3-5 به کارگیری الگوریتم کرم شبتاب با رویکرد ایجاد گروه در محیط پویا364-4 خلاصهی فصل40فصل پنجم: راهکار پیشنهادی و ارزیابی نتایج425-1 الگوریتم MCOA435-1-1 مکانیزم خود-تطبیقی شعاع تخمگذاری445-2 الگوریتم پیشنهادی MMCOAجهت بهینهسازی در محیطهای پویا465-2-1 بررسی همگرایی دستهها465-2-2 مکانیزم انحصار475-2-3 کشف تغییرات محیط485-2-4 رفع مشکل حافظهی نامعتبر و تنوع از دست رفته485-2-5 مکانیزم غیرفعالسازی495-3 تحلیل و ارزیابی نتایج505-3-1 تحلیل نتایج الگوریتم MMCOAدر فرکانس تغییرات و تعداد قلههای مختلف و مقایسه با دیگر الگوریتمها505-3-2 تحلیل نتایج الگوریتم MMCOAدر طول گام حرکتی مختلف قلهها و مقایسه با دیگر الگوریتمها755-3-3 تحلیل نتایج الگوریتم MMCOAبا تعداد ابعاد مختلف مسئله و مقایسه با دیگر الگوریتمها775-4 جمعبندی نتایج795-5 خلاصهی فصل80فصل ششم: نتیجهگیری و راهکارهای آتی826-1 نتیجهگیری836-2 راهکارهای آتی84مراجع85واژهنامه89 فهرست شکلهاعنوانصفحهشکل3‑1: نمایش نحوهی تخمگذاری در محدودهی ELR[4]10شکل3-2: نمایش نحوهی مهاجرت فاختهها به سمت موقعیت هدف [4]11شکل3-3: شبه کد الگوریتم بهینهسازی فاخته [4]11شکل4-1: شبه کد ایجاد تنوع در الگوریتم تکاملی [6]17شکل4-2: ساختار خودکار یادگیرنده[10]21شکل4-3: شبه کد بهینهسازی پویا با حافظهی صریح[6]25شکل4-4: شبه کد دستاورد چند-جمعیتی بودن[6]28شکل4-5: شبه کد الگوریتمDMAFSA [22]37شکل4-6: شبه کد الگوریتم SFA[23]39شکل 5-1: شبه کد الگوریتمMCOA45شکل 5-2: کارنمای الگوریتمMCOA47شکل 5-3: شبه کد الگوریتمMMCOA50شکل 5-4: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 1 قله بر اساس تعداد ارزیابیها54شکل 5-5: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 1 قله بر اساس ...54شکل 5-6: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 5 قله بر اساس تعداد ارزیابیها55شکل 5-7: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 5 قله بر اساس ...55شکل 5-8: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 10 قله بر اساس تعداد ارزیابیها55شکل 5-9: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 10 قله بر اساس ...55شکل 5-10: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 20 قله بر اساس تعداد ارزیابیها56شکل 5-11: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 20 قله بر اساس ...56شکل 5-12: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 30 قله بر اساس تعداد ارزیابیها56شکل 5-13: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 30 قله بر اساس ...56شکل 5-14: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 50 قله بر اساس تعداد ارزیابیها57شکل 5-15: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 50 قله بر اساس ...57شکل 5-16: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 100 قله بر اساس تعداد ارزیابیها57شکل 5-17: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 100 قله بر اساس ...57شکل 5-18: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 200 قله بر اساس تعداد ارزیابیها58فهرست شکلهاعنوانصفحهشکل 5-19: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 500 و تعداد 200 قله بر اساس ...58شکل 5-20: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 1 قله بر اساس تعداد ارزیابیها58شکل 5-21: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 1 قله بر اساس ...58شکل 5-22: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 5 قله بر اساس تعداد ارزیابیها59شکل 5-23: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 5 قله بر اساس ...59شکل 5-24: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 10 قله بر اساس تعداد ارزیابیها59شکل 5-25: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 10 قله بر اساس ...59شکل 5-26: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 20 قله بر اساس تعداد ارزیابیها60شکل 5-27: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 20 قله بر اساس ...60شکل 5-28: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 30 قله بر اساس تعداد ارزیابیها60شکل 5-29: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 30 قله بر اساس ...60شکل 5-30: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 50 قله بر اساس تعداد ارزیابیها61شکل 5-31: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 50 قله بر اساس ...61شکل 5-32: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 100 قله بر اساس تعداد ...61شکل 5-33: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 100 قله بر اساس ...61شکل 5-34: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 200 قله بر اساس تعداد ...62شکل 5-35: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 1000 و تعداد 200 قله بر اساس ..62شکل 5-36: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 1 قله بر اساس تعداد ارزیابیها62شکل 5-37: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 1 قله بر اساس ...62شکل 5-38: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 5 قله بر اساس تعداد ارزیابیها63شکل 5-39: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 5 قله بر اساس ...63شکل 5-40: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 10 قله بر اساس تعداد ارزیابیها63شکل 5-41: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 10 قله بر اساس ...63شکل 5-42: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 20 قله بر اساس تعداد ارزیابیها64شکل 5-43: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 20 قله بر اساس ...64شکل 5-44: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 30 قله بر اساس تعداد ارزیابیها64شکل 5-45: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 30 قله بر اساس ...64فهرست شکلهاعنوانصفحهشکل 5-46: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 50 قله بر اساس تعداد ...65شکل 5-47: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 50 قله بر اساس ...65شکل 5-48: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 100 قله بر اساس تعداد ...65شکل 5-49: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 100 قله بر اساس ...65شکل 5-50: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 200 قله بر اساس تعداد ...66شکل 5-51: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 2500 و تعداد 200 قله بر اساس ...66شکل 5-52: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 1 قله بر اساس تعداد ارزیابیها66شکل 5-53: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 1 قله بر اساس ...66شکل 5-54: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 5 قله بر اساس تعداد ارزیابیها67شکل 5-55: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 5 قله بر اساس ...67شکل 5-56: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 10 قله بر اساس تعداد ارزیابیها67شکل 5-57: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 10 قله بر اساس ...67شکل 5-58: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 20 قله بر اساس تعداد ارزیابیها68شکل 5-59: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 20 قله بر اساس ...68شکل 5-60: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 30 قله بر اساس تعداد ارزیابیها68شکل 5-61: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 30 قله بر اساس ...68شکل 5-62: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 50 قله بر اساس تعداد ارزیابیها69شکل 5-63: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 50 قله بر اساس ...69شکل 5-64: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 100 قله بر اساس تعداد ...69شکل 5-65: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 100 قله بر اساس ...69شکل 5-66: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 200 قله بر اساس تعداد ارزیابیها70شکل 5-67: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 5000 و تعداد 200 قله بر اساس ...70شکل 5-68: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 1 قله بر اساس تعداد ارزیابیها70شکل 5-69: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 1 قله بر اساس ...70شکل 5-70: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 5 قله بر اساس تعداد ارزیابیها71شکل 5-71: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 5 قله بر اساس ...71شکل 5-72: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 10 قله بر اساس تعداد ...71فهرست شکلهاعنوانصفحهشکل 5-73: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 10 قله بر اساس ...71شکل 5-74: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 20 قله بر اساس تعداد ...72شکل 5-75: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 20 قله بر اساس ...72شکل 5-76: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 30 قله بر اساس تعداد ...72شکل 5-77: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 30 قله بر اساس ...72شکل 5-78: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 50 قله بر اساس تعداد ...73شکل 5-79: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 50 قله بر اساس ...73شکل 5-80: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 100 قله بر اساس تعداد ...73شکل 5-81: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 100 قله بر اساس ...73شکل 5-82: گراف خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 200 قله بر اساس تعداد ...74شکل 5-83: نمودار میلهای خطای جاری الگوریتم MMCOAدر فرکانس تغییرات 10000 و تعداد 200 قله بر اساس ...74شکل 5-84: نمودار پایداری الگوریتم MMCOAدر سناریوی دو تابع محک قلههای متحرک74شکل 5-85: گراف خطای جاری الگوریتم MMCOAبا طول گام حرکتی 2 در قلهها بر اساس تعداد ارزیابیها76شکل 5-86: نمودار میلهای خطای جاری الگوریتم MMCOAبا طول گام حرکتی 2 در قلهها بر اساس تعداد تغییر ...76شکل 5-87: گراف خطای جاری الگوریتم MMCOAبا طول گام حرکتی 3 در قلهها بر اساس تعداد ارزیابیها77شکل 5-88: نمودار میلهای خطای جاری الگوریتم MMCOAبا طول گام حرکتی 2 در قلهها بر اساس تعداد تغییر ...77شکل 5-89: گراف خطای جاری الگوریتم MMCOAبا تعداد ابعاد 2 بر اساس تعداد ارزیابیها78شکل 5-90: نمودار میلهای خطای جاری الگوریتم MMCOAبا تعداد ابعاد 2 بر اساس تعداد تغییر محیطی78شکل 5-91: گراف خطای جاری الگوریتم MMCOAبا تعداد ابعاد 3 بر اساس تعداد ارزیابیها79شکل 5-92: نمودار میلهای خطای جاری الگوریتم MMCOAبا تعداد ابعاد 3 بر اساس تعداد تغییر محیطی79شکل 5-93: گراف خطای جاری الگوریتم MMCOAبا تعداد ابعاد 4 بر اساس تعداد ارزیابیها79شکل 5-94: نمودار میلهای خطای جاری الگوریتم MMCOAبا تعداد ابعاد 4 بر اساس تعداد تغییر محیطی79 فهرست جدولها عنوانصفحهجدول 5-1: مقادیر پارامترهای الگوریتم MMCOA51جدول 5-2: مقادیر پارامترهای MPB51جدول 5-3: مقایسهی خطای برونخطى (خطای استاندارد) الگوریتمها بر روی MPBبا S=1، فرکانسهای تغییر ...52جدول 5-4: مقایسهی خطای برونخطى (خطای استاندارد) الگوریتمها بر روی MPBبا f=5000، S=1 و تعداد قلههای ...54جدول 5-5: مقایسهی خطای برونخطى (خطای استاندارد) الگوریتمها بر روی MPBبا f=5000، M=10و طول گام ...75جدول 5-6: مقایسهی خطای برونخطى (خطای استاندارد) الگوریتمها بر روی MPBبا f=5000، M=10، S=1 و ابعاد ...77جدول 5-7: موارد کاربرد الگوریتم MMCOA80 فصل اول: مقدمهبهینهسازی، فرآیندی جهت پیداکردن مناسبترین مقدار از فعالیت(های) مورد نظر در حوزهی داده شده با توجه به منابع و محدودیتهای موجود میباشد. بر همین اساس این فرآیند میتواند طیف وسیعی از حوزههای علمی در شاخههای مختلف از جمله ریاضیات، آمار، علوم کامپیوتر، علوم مدیریتی و غیره و حتی مسائل روزمره را پوشش دهد. بنابراین پرداختن به مسائل مربوط به بهینهسازی از اهمیت خاصی برخوردار بوده و به عنوان یکی از اصلیترین رویههای تحقیقاتی برای محققان به شمار میآید.در مسائل مطرح شده در حوزهی بهینهسازی طبقهبندیهای مختلفی بسته به حوزهی کاربردی وجود دارد. یکی از این طبقهبندیها بر اساس تغییرپذیری یا عدم تغییرپذیری محیط اطراف تعیین میشود. به این ترتیب در صورتیکه محیط شاهد عدم تغییرات در خود باشد مسائل مربوطه تحت عنوان مسائل بهینهسازی ایستا مطرح شده و در صورت تغییرات محیطی، با مسائل بهینهسازی پویا روبرو میگردد. در مسائل نوع اول هدف اصلی یافتن و یا تخمین هر چه بهتر نقطهی (نقاط) بهینه میباشد. این در حالی است که در مسائل نوع دوم نه تنها باید هدف اصلی در حالت ایستا ارضا شود بلکه بایستی بتوان هر چه سریعتر نقطهی (نقاط) بهینه را دنبال کرد. این امر از آنجا ناشی میشود که در محیطهای پویا به دلیل تغییرپذیری محیطی امکان تغییر نقطهی (نقاط) بهینه به منطقهی دیگری از فضای جستجو وجود دارد. بنابراین چنین مسائلی با چالشهای بیشتری نسبت به حالت ایستا مواجه میشوند. از این رو محققان بر آن شدند که از الگوریتمهایی بهرهگیرند که بتوانند خود را با شرایط متغیر محیطی وفق دهند. به این ترتیب توجه آنها به سمت الگوریتمهای تکاملی معطوف گردید. چرا که این الگوریتمها از تکامل طبیعی الهام گرفته و تکامل طبیعی نیز فرآیندی پیوسته از سازگاری با محیط میباشد.در پژوهشهای انجام شده تاکنون از سه روش اصلی در الگوریتمهای تکاملی برای حل مسائل بهینهسازی پویا استفاده شده است: (1) ایجاد تنوع، (2) به کارگیری حافظه و (3) رویکرد چند-جمعیتی. به دلیل امکان ایجاد تغییرات در فضایی که هیچ عضوی در آن حضور ندارد و یا امکان همگرایی اعضا در آن منطقه، از رویکرد ایجاد تنوع استفاده میشود. جهت تحقق این امر در الگوریتمهایی چون الگوریتم ژنتیک، از مهاجران تصادفی و گاهی از مکانیزم خود-تطبیقی در نرخ جابجایی مهاجران وارد شده به جمعیت بهره گرفته شده است. در الگوریتمهای کلونی مورچگان و کلونی زنبورهای مصنوعی از خودکار سلولی و در یک نمونه نیز از الگوریتم ایمنی مصنوعی بر پایهی خودکار یادگیرنده، استفاده شده است. همچنین محققان سعی کردند تا با به کارگیری حافظه و استفاده از بهترین اعضای جمعیت بتوانند الگوریتم ژنتیک را با محیطهایی که در معرض تغییرات کم قرار میگیرند تا حدی سازگار نمایند. در نمونههای دیگر از الگوریتمهایی چون الگوریتم بهینهسازی تجمعی ذرات[1]، الگوریتم گروه ماهیهای مصنوعی[2] و الگوریتم کرم شبتاب[3] از رویکرد چند-جمعیتی استفاده شدهکه در آنها از چندین جمعیت در فضای جستجو برای ایجاد تعادل بین اکتشاف[4] و استخراج[5] نقطهی (نقاط) بهینه و ردیابی هر چه بهتر آن(ها) بهره گرفته شده است.دراينپاياننامه يکيازجديدترينالگوريتمهايتکاملي،الگوريتمبهينهسازيفاخته[6]، برای حل مسائل بهینهسازی پویا ارائه میگردد. اينالگوريتمهمانطورکهازنامشپيداستازنحوهی زندگی پرندهای موسوم به فاخته الهام گرفته شده است. مسئلهای که در این جا وجود دارد اینست که الگوریتم فاخته برای حل مسائل بهینهسازی ایستا به کار رفته و نتایج خوبی را گزارش داده است. حال آنکه برای استفاده از این الگوریتم در حل مسائل بهینهسازی پویا یکسری مکانیزمهایی جهت ردیابی بهینه در زمان تغییرات و نیز برقراری نوعی تعادل در عملیات اکتشاف و استخراج، افزوده میشوند.در ادامه، در فصل دوم به شرح کلی مسئله، پیشفرضها و اهداف بهینهسازی در محیطهای پویا پرداخته و در فصل سوم جهت درک بهتر موضوع، مفاهیم پایهای و ابزارهای مورد استفاده برای حل مسائل مربوطه مطرح میگردد. در فصل چهارم نمونههایی از راهکارهای گذشته در زمینهی مسائل بهینهسازی پویا، مورد مطالعه قرار گرفته و در فصل پنجم راهکار پیشنهادی این تحقیق، نتایج ارزیابی و آزمایشات آورده میشود. در نهایت در فصل ششم نتیجهگیری کلی و راهکارهای آتی ارائه خواهد شد.در این فصل به شناخت محیطهای پویا و به تبع آن مسائل بهینهسازی پویا به عنوان مسئلهی اصلی این پژوهش، تغییرات به کار گرفته شده در فضای مسئله که در این پایاننامه به عنوان پیش فرض مورد استفاده قرار میگیرد و هدف مورد نظر برای حل این گونه مسائل پرداخته خواهد شد.محیطهای پویا، که به نام مسائل پویا[7]یا مسائل وابسته به زمان[8] شناخته میشوند، محیطهایی هستند که در طول زمان میتوانند شاهد تغییرات پیوسته یا گسسته در خود باشند. این تغییرات میتواند در حوزهی وسیعی اتفاق بیافتد. از جمله اینکه تعداد، ابعاد، دامنهی پارامترهای محیطی و یا دیگر ویژگیها میتواند تغییر کند. از دیگر مواردی که ممکن است اتفاق بیافتد، تغییر مقدار پارامترها با توجه به زمان است. در نهایت در کلیهی تغییرات ایجاد شده، محیط با تغییر نقطه یا نقاط بهینهی سراسری و محلی روبرو میگردد. مسایلی که در این حوزه تعریف میشوند هم در بخش آزمایشگاهی و هم در دنیای واقعی به این محیطها عینیت میبخشند. از جملهی آنها، مسائل بهینهسازی پویا[9]بوده که در آنها مقدار تابع برازندگی مرتب تغییر میکند. به طور دقیقتر در تعریف ریاضی این گونه مسائل خواهیم داشت