ارایه الگوریتم بهینه سازی اصلاح شده چند دسته‌ای فاخته در حل مسائل بهینه‌سازی در محیط پویا

 

پایان‌نامه کارشناسی ارشد رشته مهندسی کامپیوتر

 گرایش هوش مصنوعی

چکیده:

حل مسائل مربوط به محیط­های پویا که به حل مسائل بهینه­سازی پویا معروفند از چند دهه­ی گذشته تا به امروز مطرح بوده­اند. پراهمیت‌ترین چالش در حل این گونه مسائل مربوط به نحوه­ی سازگاری با محیط تغییر یافته­ی جدید می­باشد؛ از اینرو  نیاز به ردیابی و پیروی کردن نقاط بهینه­ی­ جدید در فضای مسأله احساس می گردد. جهت برخورد با این چالش محققان بر آن شدند تا از الگوریتم­های تکاملی که الهام گرفته از فرآیندهای تکاملی­اند و افزودن یکسری ساختار­های خاص بهره­گیرند. چالش دیگری که این مسائل با آن روبرو می­شوند، دستیابی به بهینه‌ها به طور هر چه دقیق­تر می­باشد که جهت این امر بایستی حتی الامکان از الگوریتم­هایی با سرعت هم­گرایی و توانایی جستجوی محلی بالا بکارگیری کرد. الگوریتم بهینه­سازی فاخته یکی از الگوریتم­های تکاملی است که در محیط­های ایستا سرعت هم­گرایی و توانایی جستجوی محلی بالایی از خود نشان داده است. هدف از این پژوهش پویاسازی و ارائه­ی نسخه­ی جدیدی از الگوریتم فاخته می­باشد. جهت تحقق این موضوع ابتدا تغییراتی در ساختار اصلی الگوریتم استاندارد ایجاد خواهد شد و با بهره­گیری از یک ساختار خود-تطبیقی در شعاع تخم‌گذاری فاخته­ها، تلاش در افزایش سرعت هم­گرایی و توانایی جستجوی محلی صورت خواهد گرفت. سپس جهت ردیابی بهینه‌ها بعد از تغییرات محیطی، از یک الگوریتم چند-دسته­ای، ساختار ایجاد دسته­­ی آزاد و نیز ساختار­ انحصار بهره گرفته خواهد شد. همچنین جهت رویارویی با چالش­های مربوط به از دست دادن تنوع و حافظه­­ی­ نامعتبر در دسته­های هم­گرا به بررسی راه‌حل‌های متناسب پرداخته خواهد شد. در دسته­های غیر هم­گرا نیز شایستگی موقعیت فاخته­های آن دسته مجدداً محاسبه خواهد شد. در نتیجه از الگوریتمی به نام MCOA که نسخه­ی بهبود یافته­ای از الگوریتم بهینه­سازی فاخته بود، به عنوان الگوریتم پایه جهت پویاسازی در محیط پویا بکارگیری شد. چرا که در چنین محیط­هایی نیازمند جستجوی هر چه دقیق­تر بهینه‌ها وکاهش تعداد ارزیابی‌ها می­باشیم. در الگوریتم  MCOA از یک ساختار خود-تطبیقی در شعاع تخم­گذاری فاخته­ها بهره گرفته شد تا بتواند باعث افزایش قدرت جستجوی بهینه‌ها در فضای مسئله گردد. این ساختار بر اساس مقدار موفقیت کل فاخته­های موجود در دسته در عملیات تخم­گذاری، عمل می­کند. با بکارگیری از الگوریتم پایه­ی MCOA، الگوریتم پیشنهادی این پایان­نامه به نام MMCOA که قابل بکارگیری جهت حل مسائل بهینه­سازی پویا بود، ارائه شد.

کلمات کلیدی: الگوریتم، بهینه‌سازی، فاخته، محیط پویا

فهرست مطالب

عنوان                                                                                                             صفحه

 

فصل اول: کلیات تحقیق

۱-۱ مقدمه. ۲

۱-۲ بیان مسأله. ۳

۱-۳ اهمیت و ضرورت تحقیق.. ۵

۱-۴ اهداف تحقیق.. ۵

۱-۵ سؤالات تحقیق.. ۵

۱-۶ فرضیات تحقیق.. ۶

۱-۷ جنبه جدید بودن و نوآوری در تحقیق.. ۶

۱-۸ چارچوب تحقیق.. ۷

فصل دوم: مبانی نظری و پیشینه تحقیق

۲-۱ مقدمه. ۹

۲-۲ مبانی نظری تحقیق.. ۱۰

۲-۲-۱ محیط‌های پویا و مسائل بهینه‌سازی پویا ۱۰

۲-۲-۲ تغییرات پیوسته و ناپیوسته. ۱۰

۲-۲-۳ تغییرات سراسری و منطقه‌ای.. ۱۱

۲-۲-۴ الگوریتم بهینه‌سازی فاخته. ۱۱

۲-۲-۵ روش زندگی و تخمگذاری فاختهها ۱۱

۲-۲-۶ جزئیات الگوریتم بهینهسازی فاخته. ۱۳

۲-۲-۷ تلبع محک قلعه‌های متحرک… ۱۶

۲-۲-۸ معیار کارایی.. ۱۸

۲-۳ پیشینه تحقیقات.. ۱۹

۲-۳-۱ پیشینه تحقیقات داخلی.. ۱۹

۲-۳-۲ پیشینه تحقیقات خارجی.. ۲۱

۲-۴ خلاصه و جمع‌بندی فصل.. ۲۲

فصل سوم: مواد و روش تحقیق

۳-۱ مقدمه. ۲۴

عنوان                                                                                                             صفحه

 

۳-۲ روش تحقیق.. ۲۵

۳-۳ متغیرهای تحقیق.. ۲۶

۳-۴ روش و ابزار تجزیهوتحلیل داده‌ها ۲۸

۳-۵ روش انجام تحقیق.. ۲۸

۳-۵-۱ ایجاد تنوع. ۲۸

۳-۵-۱-۱ اعمال مهاجران تصادفی، مهاجران بر پایه نخبه و ابر جهش به راه‌اندازی شده در الگوریتم ژنتیک در محیط پویا ۲۹

۳-۵-۱-۲ بکارگیری الگوریتم ممتیک بر اساس جستجوی محلی تپهنوردی در محیط پویا ۳۱

۳-۵-۱-۳ بکارگیری از الگوریتم ایمنی مصنوعی بر پایهی خودکار یادگیرنده در محیط پویا ۳۳

۳-۵-۱-۴ اعمال ساختار خود-سازگار در مقدار جابجایی روی الگوریتمهای تکاملی در محیط پویا ۳۵

۳-۵-۱-۵ چگونگی بکارگیری خودکار سلولی در الگوریتمهای تکاملی در محیطهای پویا ۳۷

۳-۵-۲ بکارگیری حافظه. ۳۹

۳-۵-۲-۱ حافظهی ضمنی.. ۴۰

۳-۵-۲-۲ حافظهی صریح.. ۴۰

۳-۵-۳ روش چندجمعیتی بودن.. ۴۴

۳-۵-۳-۱ بکارگیری الگوریتم بهینهسازی چند-جمعیتی ذرات سریع در محیط پویا ۴۵

۳-۵-۳-۲ الگوریتم بهینهسازی تجمعی ذرات با رویکرد افزودن گروه فرزند در محیط پویا ۴۷

۳-۵-۳-۳ بکارگیری الگوریتم بهینهسازی تجمعی ذرات با رویکرد وزن تطبیقی و خوشهبندی فازی در محیط پویا ۴۸

۳-۵-۳-۴ بکارگیری الگوریتم گروه ماهی‌های مصنوعی با رویکرد چندجمعیتی در محیط پویا ۵۱

۳-۵-۳-۵ بکارگیری الگوریتم کرم شبتاب با رویکرد ایجاد گروه در محیط پویا ۵۷

۳-۶ خلاصه و جمع‌بندی فصل.. ۶۱

فصل چهارم: بحث و نتایج

۴-۱مقدمه. ۶۴

۴-۲ الگوریتم MCOA.. 65

۴-۳ ساختار خود- تطبیقی شعاع تخمگذاری.. ۶۷

۴-۴ الگوریتم پیشنهادی MMCOA جهت بهینهسازی در محیطهای پویا ۶۸

عنوان                                                                                                             صفحه

 

۴-۴-۱ بررسی همگرایی دستهها ۶۹

۴-۴-۲ ساختار انحصار. ۷۰

۴-۴-۳ کشف تغییرات محیط.. ۷۱

۴-۴-۴ رفع مشکل حافظهی نامعتبر و تنوع از دست رفته. ۷۱

۴-۴-۵ ساختار غیرفعالسازی.. ۷۲

۴-۵ تحلیل و ارزیابی نتایج.. ۷۴

۴-۵-۱ تحلیل نتایج الگوریتم MMCOA در فرکانس تغییرات و تعداد قلههای گوناگون و مقایسه با دیگر الگوریتمها ۷۴

۴-۵-۱-۱ گراف نادرست جاری و نمایش نمودار میله‌ای آن در فرکانس تغییرات ۵۰۰٫ ۸۰

۴-۵-۱-۲ گراف نادرست جاری و نمایش نمودار میله‌ای آن در فرکانس تغیرات ۱۰۰۰٫ ۸۵

۴-۵-۱-۳ گراف نادرست جاری و نمایش نمودار میله‌ای آن در فرکانس تغیرات ۲۵۰۰٫ ۹۱

۴-۵-۱-۴ گراف نادرست جاری و نمایش نمودار میله‌ای آن در فرکانس تغیرات ۵۰۰۰٫ ۹۶

۴-۵-۱-۵ گراف نادرست جاری و نمایش نمودار میله‌ای آن در فرکانس تغییرات ۱۰۰۰۰٫ ۱۰۲

۴-۵-۱-۶ نمودار پایداری سناریوی دو تابع محک قلههای متحرک… ۱۰۷

۴-۵-۲ تحلیل نتایج الگوریتم MMCOA در طول گام حرکتی گوناگون قلهها و مقایسه با دیگر الگوریتمها ۱۰۸

۴-۵-۲-۱ گراف نادرست جاری و نمایش نمودار میله‌ای آن با طول گام حرکتی ۲ در قله‌ها ۱۱۰

۴-۵-۲-۲ گراف نادرست جاری و نمایش نمودار میله‌ای آن با طول گام حرکتی ۳ در قله‌ها ۱۱۰

۴-۵-۳ تحلیل نتایج الگوریتم MMCOA با تعداد ابعاد گوناگون مسئله و مقایسه با دیگر الگوریتمها ۱۱۱

۴-۵-۳-۱ گراف نادرست جاری و نمایش نمودار میله‌ای آن با تعداد ابعاد ۲٫ ۱۱۲

۴-۵-۳-۲ گراف نادرست جاری و نمایش نمودار میله‌ای آن با تعداد ابعاد ۳٫ ۱۱۳

۴-۵-۳-۳ گراف نادرست جاری و نمایش نمودار میله‌ای آن با تعداد ابعاد ۴٫ ۱۱۴

۴-۶ جمع‌بندی و خلاصه فصل.. ۱۱۵

فصل پنجم: نتیجه‌گیری و پیشنهادات

۵-۱ مقدمه. ۱۱۹

۵-۲ نتیجه‌گیری.. ۱۲۰

۵-۳ پیشنهادات.. ۱۲۱

منابع و مآخذ

 

Sorry, the comment form is closed at this time.