تغییر الگوریتم بهینه سازی فاخته جهت استفاده در محیط های پویا

 

 

 

 

 

پایان‌نامه برای دریافت درجه کارشناسی ارشد

رشته مهندسی کامپیوتر گرایش هوش مصنوعی

 

 

چکیده

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

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

 

فهرست مطالب
عنوان صفحه
فصل اول: مقدمه ۱
فصل دوم: شرح مسئله ۴
  ۲-۱ محیط­های پویا و مسائل بهینه­سازی پویا ۵
  ۲-۲ تغییرات پیوسته و ناپیوسته ۵
  ۲-۳ تغییرات سراسری و مقطعی ۶
  ۲-۴ اهدف ۶
  ۲-۵ خلاصه­ی فصل ۶
فصل سوم: مفاهیم پایه‌ای ۷
  ۳-۱ الگوریتم بهینه­سازی فاخته ۸
    ۳-۱-۱ روش زندگی و تخم­گذاری فاخته­ها ۸
    ۳-۱-۲ جزئیات الگوریتم بهینه­سازی فاخته ۹
  ۳-۲ تابع محک قله­های متحرک ۱۲
  ۳-۳ معیار کارآیی ۱۳
  ۳-۴ خلاصه­ی فصل ۱۴
فصل چهارم: راه‌کارهای پیشین ۱۵
  ۴-۱ ایجاد تنوع ۱۶
    ۴-۱-۱ اعمال مهاجران تصادفی، مهاجران بر پایه­ی نخبه و ابر جهش به راه اندازی شده در الگوریتم ژنتیک در محیط پویا ۱۶
    ۴-۱-۲ به کارگیری الگوریتم ممتیک بر اساس جستجوی محلی تپه­نوردی در محیط پویا ۱۸
    ۴-۱-۳ استفاده از الگوریتم ایمنی مصنوعی بر پایه­ی خودکار یادگیرنده در محیط پویا ۱۹
    ۴-۱-۴ اعمال مکانیزم خود-سازگار در نرخ جابجایی روی الگوریتم­های تکاملی در محیط پویا ۲۱
    ۴-۱-۵ چگونگی به کارگیری خودکار سلولی در الگوریتم­های تکاملی در محیط­های پویا ۲۲
  ۴-۲ به کارگیری حافظه ۲۴
    ۴-۲-۱ حافظه­ی ضمنی ۲۴
    ۴-۲-۲ حافظه­ی صریح ۲۴
  ۴-۳ روش چند-جمعیتی بودن ۲۷
    ۴-۳-۱ به کارگیری الگوریتم بهینه­سازی چند-جمعیتی ذرات سریع درمحیط پویا ۲۸
فهرست مطالب
عنوان صفحه
    ۴-۳-۲ الگوریتم بهینه­سازی تجمعی ذرات با رویکرد افزودن گروه فرزند در محیط پویا ۳۰
    ۴-۳-۳ به کارگیری الگوریتم بهینه­سازی تجمعی ذرات با رویکرد وزن تطبیقی و خوشه­بندی  فازی در محیط پویا ۳۱
    ۴-۳-۴ به کارگیری الگوریتم گروه ماهی‌های مصنوعی با رویکرد چند-جمعیتی در محیط پویا ۳۲
    ۴-۳-۵ به کارگیری الگوریتم کرم شب­تاب با رویکرد ایجاد گروه در محیط پویا ۳۶
  ۴-۴ خلاصه­ی فصل ۴۰
فصل پنجم: راه­کار پیشنهادی و ارزیابی نتایج ۴۲
  ۵-۱ الگوریتم MCOA ۴۳
    ۵-۱-۱ مکانیزم خود-تطبیقی شعاع تخم­گذاری ۴۴
  ۵-۲ الگوریتم پیشنهادی MMCOA جهت بهینه­سازی در محیط­های پویا ۴۶
    ۵-۲-۱ بررسی هم­گرایی دسته­ها ۴۶
    ۵-۲-۲ مکانیزم انحصار ۴۷
    ۵-۲-۳ کشف تغییرات محیط ۴۸
    ۵-۲-۴ رفع مشکل حافظه­ی نامعتبر و تنوع از دست رفته ۴۸
    ۵-۲-۵ مکانیزم غیرفعال­سازی ۴۹
  ۵-۳ تحلیل و ارزیابی نتایج ۵۰
    ۵-۳-۱ تحلیل نتایج الگوریتم MMCOA در فرکانس تغییرات و تعداد قله­های مختلف و مقایسه با دیگر الگوریتم­ها ۵۰
    ۵-۳-۲ تحلیل نتایج الگوریتم MMCOA در طول گام حرکتی مختلف قله­ها و مقایسه با دیگر الگوریتم­ها ۷۵
    ۵-۳-۳ تحلیل نتایج الگوریتم MMCOA با تعداد ابعاد مختلف مسئله و مقایسه با دیگر الگوریتم­ها ۷۷
  ۵-۴ جمع­بندی نتایج ۷۹
  ۵-۵ خلاصه­ی فصل ۸۰
فصل ششم: نتیجه‌گیری و راه­کارهای آتی ۸۲
  ۶-۱ نتیجه‌گیری ۸۳
  ۶-۲ راه‌کارهای آتی ۸۴

Sorry, the comment form is closed at this time.