پژوهش دانشگاهی – تغییر الگوریتم بهینه سازی فاخته جهت استفاده در محیط های پویا- قسمت ۲۴

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

برای دانلود متن کامل پایان نامه به سایت  fotka.ir  مراجعه نمایید.

۵-۲-۱ بررسی همگرایی دستهها

برای تعیین همگرایی یک دسته، فاصلهی اقلیدسی تمام فاختههای یک دسته از یکدیگر محاسبه شده و در صورتیکه فاصلهی دورترین فاختههای دسته کوچکتر از مقدار پارامتر rconv (که بر اساس آزمایشات برابر ۱۰ است) باشد، یعنی دسته همگرا گردیده است. فاصلهی اقلیدسی از رابطهی زیر به دست میآید:

(۵‑۴)

که در آن تعداد فاختههای هر دسته میباشند.

شکل ۵-۲: کارنمای الگوریتم MCOA

۵-۲-۲ مکانیزم انحصار

چالش دیگری که در بهینهسازی محیط پویا وجود دارد همگرایی دو دسته به یک قله میباشد. در این حالت وجود یکی از این دو دسته غیر مفید و حتی مضر میباشد. زیرا دستهی اضافی با مصرف منابع محاسباتی و ارزیابی شایستگی، موجب کند شدن الگوریتم میگردد. برای این منظور از مکانیزم انحصار استفاده میشود. در این مکانیزم، فاصلهی اقلیدسی دو موقعیت بهترین فاختهی تمام دستههای موجود در فضای مسئله از یکدیگر محاسبه شده و اگر فاصلهی بهترین فاختهی دو دسته کمتر از یک مقدار مشخص rexcl [19] باشد، دستهای که بهترین فاختهی آن از موقعیت بدتری نسبت به موقعیت بهترین
فاختهی دستهی دیگر برخوردار باشد، به طور کلی از بین میرود. فاصلهی انحصاری از رابطهی زیر به دست میآید:

(۵‑۵)

در آن تعداد قلهها و تعداد ابعاد مسئلهاند.

۵-۲-۳ کشف تغییرات محیط

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

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

پس از کشف تغییر در محیط، دستهها با دو چالش مهم برخورد میکنند که اولی حافظهی نامعتبر و دومی تنوع از دست رفته در دسته میباشد. چالش اول از آن جا بوجود میآید که مقادیر ذخیره شده در حافظه به عنوان مقدار شایستگی هر فاخته، در محیط جدید تغییر کرده و باید بروز شوند. همچنین مشکل دوم یعنی از دست دادن تنوع در دسته از آنجا ناشی میشود که ذات الگوریتمهای فرامکاشفهای، همگرا شدن به سمت یک هدف است. در واقع با کاهش گستردگی دسته و جمع شدن فاختهها در اطراف هدف، تنوع در دسته کاهش یافته و این امر باعث افزایش توانایی جستجوی محلی و رسیدن به
موقعیتهای بهتر میگردد. با این وجود پس از تغییر محیط، هدف جا به جا شده و دسته با توجه به کاهش شدید تنوع در پیش از تغییر محیط، توانایی حرکت به سمت موقعیت جدید هدف را از دست داده و یا اینکه حرکت به سمت آن بسیار کند انجام میشود.

برای مقابله با این دو چالش، در الگوریتم پیشنهادی پس از کشف تغییر در محیط ابتدا موقعیت بهترین فاختهی تمام دستههایی که همگرا شدهاند (قلههایی را تحت پوشش دارند) تعیین میگردد. سپس تمام فاختههای دسته در شعاعی در اطراف این موقعیت به صورت تصادفی پخش میشوند. اندازهی این شعاع برابر رابطهی زیر است:

(۵‑۶)