• • ایجاد تنوع^[۱۹]­

• • به کارگیری حافظه

• • استفاده از روش چند-جمعیتی بودن^[۲۰]­

نکته­ای که باید به آن اشاره کرد این­ است که هر کدام از این روش­ها خود شامل الگوریتم­های گوناگون ارائه شده در حل مسئله می­باشند. در ادامه به بررسی هر یک از آن­ها می­پردازیم.
۴-۱ ایجاد تنوع
در بهینه­سازی ایستا هم­گرایی افراد جمعیت جزء ملزومات برای پیدا کردن بهترین راه­حل در مناطق امید بخش است. با این وجود در بهینه­سازی پویا هم­گرایی ممکن است اثرات منفی داشته باشد و این به دلیل این­است که جمعیت هم­گرا شده قابلیت دنبال کردن بهینه(ها) پس از تغییرات را ندارد. یک راه­کار برای مقابله با این مسئله، ایجاد تنوع در افراد جمعیت بعد از شناسایی تغییرات محیطی می‌باشد. همان­طورکه در طبیعت نیز تحت شرایط مختلف و تغیرات محیطی، تنوع کمک به بقای افراد جمعیت می­ کند. الگوریتم شکل ۴-۱ نمای کلی ایجاد تنوع بعد از شناسایی تغییرات محیطی را نشان می‌دهد.

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

۴-۱-۱ اعمال مهاجران تصادفی، مهاجران بر پایه­ نخبه و ابر جهش به راه اندازی شده در الگوریتم ژنتیک در محیط پویا
در سال ۱۹۹۳ کاب^[۲۱] و گرفنستت^[۲۲] [۷] به مقایسه­ سه استراتژی افزایش تنوع بر روی الگوریتم ژنتیک پرداختند. این استراتژی­ها شامل به کارگیری عملگر جهش با نرخ ثابت، استفاده از مهاجران تصادفی^[۲۳] و استفاده از ابر جهش به راه اندازی شده^[۲۴] بودند. سپس این سه استراتژی بر روی چندین نوع محیط با
تغییرات مختلف، آزمایش شدند. محیط­ها عبارتند از: محیط با انتقال خطی نقطه­ی بهینه، محیط با
شکل۴-۱: شبه کد ایجاد تنوع در الگوریتم تکاملی [۶]
جابجایی تصادفی نقطه­ی بهینه و نوسان بین دو فضای جستجوی متفاوت.
در مهاجران تصادفی از نرخ جابجایی^[۲۵] استفاده شد که مشخص کننده­ درصدی از جمعیت است که باید با این افراد تصادفی ایجاد شده در جمعیت جابجا شوند. به این ترتیب درصدی از جمعیت براساس نرخ جهش بالا، عمل می‌کنند. در حالی­که بقیه­ی جمعیت با نرخ جهش پایین (۰۰۱/۰) در طول اجرا به کار گرفته می­شوند. قسمت جابجا شده جمعیت یا بدترین افراد در جمعیت­اند یا به طور تصادفی انتخاب شده و سپس با مهاجران تصادفی جایگزین می­شوند.
مکانیزم ابر جهش به راه اندازی شده به عنوان یک مکانیزم سازگار یاد می­ شود. به دلیل این­که
زمانی­که کارآیی الگوریتم کاهش می­یابد با نرخ جهش بالا وارد عمل می­ شود ولی در بقیه‌ی حالت­ها از یک جهش یکنواخت (۰۰۱/۰) در افراد جمعیت استفاده می­ کند. در این­جا کارآیی را با متوسط بهترین اعضای جمعیت اندازه می­گیرند.
نتایج به­ دست آمده حاکی از آن بود که الگوریتم ژنتیک استاندارد با نرخ جهش ثابت برای
محیط­هایی که تغییرات به طور پیوسته و خطی­اند مفید واقع می­ شود. ولی زمانی­که نرخ جهش افزایش یابد متوسط کارآیی دچار کاهش می­ شود. بنابراین باید نرخ جهش را با میزان تغییرات، تنظیم کرد که این باعث عدم کارآیی این مکانیزم برای زمانی­که میزان تغییرات نامشخص است، می­گردد.
مکانیزم ابر جهش به راه اندازی شده به طور تطبیقی بوده که این ویژگی مهمی به شمار می ­آید. اما این مکانیزم برای زمانی­که تغییرات به تندی انجام می­ شود کارآیی چندانی ندارد. به طور کلی این مکانیزم در دنبال کردن تغییرات به طور پیوسته دچار واریانس زیاد می­ شود.
استراتژی مهاجران تصادفی برای محیط­هایی که تغییرات ناگهانی وجود دارد موثر واقع می­ شود. با این حال در محیط­های بدون تغییر این استراتژی خوب عمل نمی­کند. چرا که باعث از دست دادن اطلاعات می­گردد. همچنین در محیط­هایی با تغییرات کم این مسئله صادق است و باعث عدم کارآیی این استراتژی می­ شود.
یانگ^[۲۶] در سال ۲۰۰۷ نسخه­ بهبود یافته­ای از به کارگیری مهاجران در الگوریتم ژنتیک را ارائه کرد که در آن از مهاجران ایجاد شده بر پایه­ بهترین فرد نسل قبلی برای ایجاد تنوع استفاده کرد تا بتواند بر مشکلات حاصل از اعمال مهاجران تصادفی فائق آید [۸]. الگوریتم حاصل به نام
EIGA^[27]می­باشد.
در این الگوریتم پس از آن­که اپراتورهای ژنتیکی بر افراد جمعیت اعمال می­شوند، در هر نسل، بهترین فرد نسل قبلی انتخاب و براساس آن به تعداد n× تا مهاجر تولید می­گردند. نسبت تعداد مهاجران تولید شده به اندازه­ جمعیت و n اندازه­ جمعیت می­باشد. این مهاجران براساس اعمال عملگر جهش بیتی^[۲۸] با احتمال بر روی بهترین فرد نسل قبلی ایجاد شده و سپس افراد تولید شده به جای
n× تا از بدترین افراد جمعیت جاری قرار می­گیرند. بنابراین در الگوریتم پیشنهادی این مقاله از ترکیبی از نخبه­کشی و مهاجران تصادفی استفاده شده است.
همچنین برای زمانی­که تغییرات محیطی زیاد است، همانند قبل از رویکرد اعمال مهاجران تصادفی بهره گرفته شده و در نهایت از الگوریتم ترکیبی جدید به نام HIGA[29] نتایج خوبی حاصل گردید.
۴-۱-۲ به کارگیری الگوریتم ممتیک بر اساس جستجوی محلی تپه­نوردی در محیط پویا
استفاده از الگوریتم ممتیک به دلیل به کارگیری جستجوی محلی در الگوریتم تکاملی بسیار حائز اهمیت است. در سال ۲۰۰۹، وانگ^[۳۰] و یانگ [۹] الگوریتم ممتیکی ارائه دادند که در آن از مفهوم تپه­نوردی جهت جستجوی محلی قوی‌تر استفاده شده است. همچنین از دو متد ایجاد تنوع برای حل مشکل هم­گرایی در مسائل بهینه­سازی پویا، بهره گرفته شد.
چهارچوب الگوریتم ممتیک براساس الگوریتم ژنتیک به این­صورت است که جمعیتی از افراد تولید و ارزیابی می­شوند. سپس بهترین فرد جمعیت انتخاب و توسط متدهای به کار گرفته شده برای جستجوی محلی، بهبود می­یابد. در نهایت جمعیت جدید از بهترین افراد بین والدها و فرزندان ایجاد شده و سپس بهترین فرد ارزیابی و توسط جستجوی محلی بهبود می­یابد.
همچنین در الگوریتم ممتیک عملگرهای جستجوی محلی نقش مهمی در استخراج بهینه در فرایند تکامل به عهده می­گیرند. یکی از متدهای جستجوی محلی تپه­نوردی است که در آن فرایند جستجو از فرد جاری به فرد کاندید در صورت بهتر بودن فرد کاندید انتقال می­یابد. در این مقاله از دو استراتژی برای تپه­نوردی استفاده شده است:

1. 1. تپه­نوردی بر پایه­ جفت­گیری حریصانه (GCHC^[31])

1. 1. تپه­نوردی براساس جهش تند (SMHC^[32])

در نوع اول تپه­نوردی بهترین فرد به عنوان یک والد در عملگر جفت­گیری و والد دوم از طریق انتخاب به روش چرخ رولت از بین جمعیت انتخاب می‌شوند. سپس بر روی این دو جفت­گیری یکنواخت انجام شده تا یک فرزند تولید شود. در صورتی­که فرزند بهتر از بهترین فرد در جمعیت قبلی باشد، جایگزین بهترین فرد می‌شود. در این­جا از پارامتری به نام استفاده شده که احتمال انجام
جفت­گیری در جستجوی محلی است. هر چقدر این پارامتر کوچک‌تر باشد، ناحیه­ای حول و حوش بهترین فرد مورد جستجو قرار می­گیرد. یعنی در فضای کوچک‌تری اطراف بهترین فرد به دنبال راه­حل بهتر هستیم.
در نوع دوم چندین بیت در کروموزوم بهترین فرد تغییر می­یابد. این بیت‌ها به طور تصادفی و به تعداد انتخاب می­شوند. اگر فرد جدید تولید شده بهتر از بهترین فرد در جمعیت باشد، در
آن­صورت جایگزین بهترین فرد خواهد شد. در این­جا هر چقدر بزرگ‌تر باشد، در فضای بزرگ‌تری اطراف بهترین فرد جستجوی محلی ادامه خواهد یافت.
در نهایت هر کدام از دو نوع تپه­نوردی بر اساس میزان رشد الگوریتم تعیین می­شوند. سپس برای ایجاد تنوع در جمعیت از دو متد نگاشت دوگان سازگار^[۳۳] و مهاجران تصادفی به راه اندازی شده^[۳۴] استفاده می­گردد.
در متد نگاشت دوگان سازگار که از دوگان کروموزوم در DNA الهام گرفته شده است، دوگان هر فرد به صورت و در نظر گرفته می­ شود. بنابراین قبل از این­که جستجوی محلی بر روی بهترین فرد انجام شود دوگان آن محاسبه شده تا درصورت بهتر بودن آن، جستجوی محلی بر روی دوگان انجام گیرد.
در مهاجران تصادفی به راه اندازی شده تنها زمانی افراد مهاجر وارد جمعیت شده که هم­گرایی جمعیت از یک حد آستانه­ای کمتر شود.
در بخش آزمایشات نیز نتایج خوب ارائه شده از این الگوریتم، قدرت متدهای به کار گرفته شده و به دنبال آن کارآیی الگوریتم را نشان داد.
۴-۱-۳ استفاده از الگوریتم ایمنی مصنوعی بر پایه­ خودکار یادگیرنده در محیط پویا
رضوانیان و میبدی در سال ۲۰۱۰ [۱۰] بر اساس خودکار یادگیرنده و ترکیب با الگوریتم ایمنی مصنوعی الگوریتمی ارائه دارند تا در رویکرد افزایش تنوع جمعیتی گام دیگری در محیط­های پویا بردارند.
الگوریتم­ ایمنی یک الگوریتم الهام گرفته شده از سیستم ایمنی بدن می‌باشد. از نظر تئوریک سیستم ایمنی بدن می ­تواند تغییرات محیطی را به خوبی مدیریت کند و در مقابل آن واکنش نشان دهد. با این وجود الگوریتم­های ایمنی مصنوعی قادر به دنبال کردن تغییرات در محیط­های پویا نمی­باشند. بنابراین نیازمند تعدادی مکانیزم برای شناسایی و پاسخ به تغییرات هستند.
خودکار یادگیرنده از مجموعه­ محدودی «عمل»^[۳۵] درست شده که در هر مرحله یکی از این اعمال انتخاب شده و بر روی محیط اثر می­گذارند. انتخاب هر عمل براساس یک «بردار احتمال عمل»^[۳۶] در هر وضعیت^[۳۷] می­باشد. پس از این­که عمل بر روی محیط اثرگذاشت، محیط به دنبال آن سیگنالی با توزیع احتمال نامشخص به خودکار یادگیرنده بر می­گرداند. سپس براساس آن سیگنال و با بهره گرفتن از الگوریتم یادگیری، خودکار بردار احتمال عمل را به روز رسانی می­ کند.
در این الگوریتم سعی شده تا با سازگاری پارامترها با محیط­های پویا، به ایجاد نوعی تنوع در جمعیت کمک کند. در الگوریتم ایمنی عملگر جهش تنها عملگر به کار برده شده بوده که توسط پارامتری به نام احتمال نرخ جهش ، به کارگیری یا عدم به کارگیری این عملگر بر روی سلول­های ایمنی مشخص
می­ شود. در نهایت سلول جهش یافته () توسط
توزیع گوسین به صورت زیر محاسبه می‌گردد: