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