الگوریتم چندهدفه غیرغالب|multi objective non-dominant

روش های انتخاب و رتبه بندی
الگوریتم چندهدفه غیرغالب یکی از روشهای انتخاب و رتبه بندی است که دارای مراحل زیر است:
۱- ساخت جمعیت اولیه: مجموعه ای از کروموزم ها در کنار هم جمعیت اولیه را می سازند. هر کروموزم دارای ویژگی های مجموعه داده است.
۲- محاسبه برازندگی: بر طبق فرمول های معیارهای عملکرد برازندگی برای هر جمعیت محاسبه می شود.
۳- مرتب سازی غیرغالب اعضای جمعیت: مرتب سازی کروموزم ها به علت اینکه چند تابع هدف وجود دارد امکان پذیر نیست بنابراین به کمک مرتب سازی غیرغالب تمامی حالات مورد مقایسه قرار گرفته می شوند و سپس رتبه‌بندی می شوند. کروموزوم هایی با کمترین جبهه ی پارتو در رتبه ی بالاتری نسبت به سایر سرویس ها قرار می گیرند و در سرویس هایی که در یک جبهه ی پارتو قرار دارند یکسان هستند و هیچ اولویتی نسبت به هم ندارند. در الگوریتم مرتب سازی غیرغالب با فرض p و q به عنوان عضوی از جمعیت و Sp مجموعه ی اعضایی از جمعیت که توسط p مغلوب می شوند. همچنین np تعداد دفعاتی که p توسط سایرین مغلوب می شود، می باشد. برای هر عضو از جمعیت مانند p و به ازای هر عضو از جمعیت مانند q اگر p بر q غلبه کند، q به Sp اضافه می شود و اگر q بر p غلبه کند یک واحد به np اضافه می شود. سپس تمام اعضای جمعیت که np=0 باشد، به F1 اضافه می شود. اکنون بر طبق F1 جبهه ی F2 ساخته می شود. برای این کار اگر شمارنده جبهه ها را K در نظر بگیریم برای جبهه Fk+1 ابتدا هر عضو از Fk مانند p که به ازای هر عضو از Sp مانند q یک واحد از nq کسر می شود و اگر nq=0 شود q در Fk+1 قرار می گیرد این عمل تا جایی ادامه می یابد که عضوی برای رتبه بندی وجود نداشته باشد. در غیر اینصورت یک واحد به K اضافه می شود و مراحل تکرار می-شوند.
۴- محاسبه¬ی فاصله ی ازدحامی: معمولاً پس از محاسبه ی رتبه بندی غیرغالب باید از فاصله ی ازدحامی استفاد شود. پس از تعیین جبهه ی پارتو به عنوان جبهه ای که از سایر جبهه ها کمتر است به کمک فاصله ی ازدحامی به انتخاب سرویس های بهتر در جبهه پارتو پرداخته می شود. فاصله ازدحامی به بی نظمی اشاره می کند و چگالی را در جبهه پارتو مورد بررسی قرار می دهد. که هر چه فاصله بین کروموزوم ها در جبهه پارتو بیشتر باشد شانس کروموزوم برای دریافت رتبه ی بالاتر بیشتر است. شکل زیر این مطلب را نشان می دهد(۱).

نمایش جبهه پارتو در الگوریتم چندهدفه

همانطور که مشاهده میشود در شکل a کروموزم ها نسبت به دو تابع هدف محاسبه شده اند و قرار گرفته اند. سپس در شکل b جبهه های پارتو ساخته می شوند که همانطور که در شکل مشاهده می شود در 4 سطح جبهه های پارتو شناسایی شده اند. در شکل c به محاسبه ی فاصله ی ازدحامی پرداخته می شود(۱).
۵- ترکیب : انتخاب دو والد و ترکیب آنها برای تولید دو فرزند به عنوان کروموزوم¬های جدید در این مرحله انجام می شود که فرزندان ممکن است جزء سرویس های واقعی نباشند.
۶- جهش : درصدی از کروموزم ها مطابق نرخ جهش با مقادیر تصادفی جایگزین می شوند تا واقعیت در الگوریتم ژنتیک برقرار باشد.
۷- مرتب سازی و جایگزینی: پس از مراحل فوق اعضای جمعیت مرتب می شوند تا برای تکرارهای بعدی مورد استفاده قرار بگیرند اعضای کمتر از حداکثر جمعیت تعیین شده حذف می شوند.
۸- شرط پایان تکرار الگوریتم: می توان از دو روش استفاده کرد:
• تعیین تعداد تکرار
• تعیین جواب بهینه برای همگرایی به آن
• جواب را به وضوح در دست داشته باشیم(۱).

همچنین مطالب زیر را مطالعه کنید:
سمینار کارشناسی ارشد| رایانش ابری| فایل لاتک|بررسی رتبه‌بندی سرویس­های ابری با اعمال رویکردی برای حل مسائل چندهدفه

پیاده سازی مقاله ISI| رایانش ابری| آموزش ویدیویی|بررسی رتبه‌بندی سرویس­های ابری با اعمال رویکردی برای حل مسائل چندهدفه

(۱) مقاله اصلی را از اینجا می توانید دانلود کنید.