رتبه بندی سیستم ها

الگوریتم ژنتیکGA[1]، یک روش اماری و تکنیک جستجو در علم رایانه به منظور یافتن راه‌حل تقریبی برای بهینه‌سازی و مسایل جستجو است، الگوریتم ژنتیک نوع خاصی از الگوریتم­های تکاملی است که از تکنیک­های زیست‌شناسی مانند وراثت و جهش استفاده می‌کند. ویژگی­های خاص این الگوریتم باعث می­شود. الگوریتم‌های ژنتیک اغلب گزینه خوبی برای تکنیک‌های پیش‌بینی هستند. مختصرا گفته می‌شود که الگوریتم ژنتیک یک تکنیک برنامه‌نویسی است که از تکامل ژنتیکی به عنوان یک الگوی حل مساله استفاده می‌کند. مساله‌ای که باید حل شود ورودی است و راه‌حل­ها طبق یک الگو کدگذاری می‌شوند و توسط تابعی که تابع fitness نام دارد، سنجیده می­شود و این تابع هر راه حل کاندید را ارزیابی می‌کند که اکثر ان­ها به صورت تصادفی انتخاب می‌شوند. به طور کلی، این الگوریتم‌ها از بخش­های زیر تشکیل می‌شوند : تابع برازش – نمایش – انتخاب – تغییر.

همچنین مطالب زیر را مطالعه کنید:

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

ویدیوی آموزش پیاده سازی مقاله رتبه بندی سرویس های ابری بصورت الگوریتم چندهدفه

  قانون انتخاب طبیعی بدین صورت است که تنها گونه‌هایی از یک جمعیت ادامه نسل می‌دهند که بهترین خصوصیات را داشته باشند و ان­هایی که این خصوصیات را نداشته باشند، به تدریج و در طی زمان از بین می‌روند. طبیعت با بهره‌گیری از یک روش بسیار ساده (حذف تدریجی گونه‌های نامناسب و در عین حال تکثیر بالاتر گونه‌های بهینه) توانسته است دایما هر نسل را از لحاظ خصوصیات مختلف ارتقا بخشد.

هدف اصلی روش‌های هوشمند به کار گرفته شده در هوش مصنوعی، یافتن پاسخ بهینه مسایل مهندسی است. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک، مقدار ماکزیمم تابع را بیابیم. مثلا از نقطه 1 شروع کنیم و تابع را ماکزیمم کنیم. بدیهی است اگر از نقطه 1 شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از ان متوقف خواهد شد. اما در روش‌های هوشمند مخصوصا الگوریتم ژنتیک، به دلیل خصلت تصادفی ان­ها، حتی اگر هم از نقطه 1 شروع کنیم باز ممکن است در میان راه، نقطه Aبه صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی[2]را خواهیم داشت]21[. برای شناخت الگوریتم ژنتیک، لازم است تعاریف زیر انجام شود:

  • شخص:[3]یک جواب کاندید برای مساله که معمولا به صورت رشته بیتی نمایش داده می­شود.
  • ژن[4]: هر بیت در شخص است و واحدپایه ژنتیک است.
  • فرم[5]: حالت­های مختلف هر ژن را می­گویند، اگر رشته بیتی باشد دارای مقادیر 0یا 1می­باشد.
  • لوکاس[6]: موقعیت هر ژن بر روی کروموزوم را گویند.
  • جمعیت[7]: مجموعه­ای از اشخاص که سایز ان معمولا ثابت است.
  • کروموزوم[8]: به گروهی از ژن­ها اطلاق می­شود.

الگوریتم ژنتیک، الگوریتمی اتفاقی است که از تکامل طبیعی تقلید می­کند. جنبه­ای که این الگوریتم را مجزا می­کند، این است که مجموعه­ای از جواب­ها را که اشخاص یا کروموزوم نامیده می­شود، در یک جمعیت نگه می­دارد. همانند تکامل زیستی، دارای مکانیزمی است که بهترین و مناسب­ترین کروموزوم را در هر نسل انتخاب می­کند. به منظور شبیه­سازی فرایند تکامل، کروموزوم­های انتخاب شده تحت تاثیر عملگر­های ژنتیک همانند ترکیب  و  جهش قرار می­گیرند [17]. الگوریتم ژنتیک دارای پنج مرحله می­باشد که بدین ترتیب است:

کدینگ برای این منظور استفاده می­شود که قسمتی از یک جواب به صورت یک کروموزوم کد ­شود. الگوریتم ژنتیک به جای این که بر روی پارامتر­ها یا متغیر­های مساله کار کند، با شکل کد شده ان­ها سروکار دارد. در طبیعت، بقای یک نسل یکی از مهمترین فاکتورها است و تنها عملگر ممکن برای این امر امیزش است. در الگوریتم­های ژنتیکی به طبع، طبیعت امیزش وجود دارد. امیزش با تعویض ژن­ها بین دو کروموزوم انجام می­گیرد و هر کدام از کروموزوم­ها خصوصیاتی از خود را به فرزندان انتقال می­دهند. بدیهی است کروموزوم­هایی که دارای برازندگی بیشتری باشند، شانس بیشتری برای امیزش دارند. مهمترین عملگر در الگوریتم ژنتیک، عملگر ترکیب است. ترکیب، فرایندی است که در ان نسل قدیمی کروموزوم­ها با یکدیگر مخلوط و ترکیب می­شوند تا نسل تازه­ای از کروموزوم­ها به وجود بیاید. جفت­هایی به عنوان والد، ژن­هایشان را با هم مبادله می­کنند و اعضایی جدید به وجود می­اورند. ترکیب در الگوریتم ژنتیک باعث از بین رفتن پراکندگی یا تنوع ژنتیکی جمعیت می­شود، زیرا اجازه می­دهد ژن­های خوب یکدیگر را بیابند.

ترکیب، دو کروموزوم را با انتخاب تصادفی موقعیتی مانند P ترکیب می­کند که  Pمقداری کمتر یا مساوی طول کروموزوم­ها است. اگر تعداد (طول) ژن­ها در کروموزوم­ها Nباشد، از دو کروموزوم والد، دو فرزند به صورت زیر به وجود می­اید. یک فرزند با کپی کردن ژن­های 1,…,(P-1)از کروموزوم والد اول و ژن­های P,…,Nاز کروموزوم والد دوم ساخته می­شود. فرزند دیگر به طور مشابه، این بار با کپی کردن ژن­های 1,…,(P-1)از کروموزوم والد دوم و ژن­های P,…,Nاز کروموزوم والد اول به وجود می­اید. در این ترکیب از دو والد، دو فرزند به وجود می­اید.

جهش نیز عملگر دیگری است که جواب­های ممکن دیگری را متولد می­کند. در الگوریتم ژنتیک بعد از این که یک عضو در جمعیت جدید به وجود امد، هر ژن ان با احتمال جهش، جهش می­یابد. در جهش ممکن است ژنی از مجموعه ژن­های جمعیت حذف شود یا ژنی که تا به حال در جمعیت وجود نداشته است، به ان اضافه شود. جهش یک ژن به معنای تغییر ان ژن است و بسته به نوع کدگذاری، روش­های متفاوت جهش استفاده می­شود. می­توان استنباط کرد که مهم­ترین وظیفه جهش، اجتناب از همگرایی به بهینه محلی است. در الگوریتم ژنتیک با کدگذاری باینری، این عمل با تولید تصادفی یکی از اعداد 0یا 1و جایگزینی ان به جای بیت موردنظر صورت می­گیرد. اما در برخی کاربردهای ژننتیک، عمل جهش دودویی در یک بیت با متمم ساختن ان بیت انجام می­گیرد که این روش مناسب­تر است. رمزگشایی، عکس عمل Encoding(رمزگذاری) است. در این مرحله بعد از این که الگوریتم بهترین جواب را برای مساله ارایه کرد، لازم است عکس عمل رمزگذاری روی جواب­ها اعمال شود.

عملیات الگوریتم ژنتیک
GA
Genetic Algorithm
عملیات الگوریتم ژنتیک

[1] Genetic Algorithm

[2] Global Optimal

[3] Individual

[4] Gene

[5] allele

[6] Locus

[7] Population

[8] chromosome

[9] Encoding

[10] Evaluation

[11] Crossover

[12] Mutation

[13] Decoding

روش های انتخاب و رتبه بندی
الگوریتم چندهدفه غیرغالب یکی از روشهای انتخاب و رتبه بندی است که دارای مراحل زیر است:
۱- ساخت جمعیت اولیه: مجموعه ای از کروموزم ها در کنار هم جمعیت اولیه را می سازند. هر کروموزم دارای ویژگی های مجموعه داده است.
۲- محاسبه برازندگی: بر طبق فرمول های معیارهای عملکرد برازندگی برای هر جمعیت محاسبه می شود.
۳- مرتب سازی غیرغالب اعضای جمعیت: مرتب سازی کروموزم ها به علت اینکه چند تابع هدف وجود دارد امکان پذیر نیست بنابراین به کمک مرتب سازی غیرغالب تمامی حالات مورد مقایسه قرار گرفته می شوند و سپس رتبه‌بندی می شوند. کروموزوم هایی با کمترین جبهه ی پارتو در رتبه ی بالاتری نسبت به سایر سرویس ها قرار می گیرند و در سرویس هایی که در یک جبهه ی پارتو قرار دارند یکسان هستند و هیچ اولویتی نسبت به هم ندارند. در الگوریتم مرتب سازی غیرغالب با فرض 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| رایانش ابری| آموزش ویدیویی|بررسی رتبه‌بندی سرویس­های ابری با اعمال رویکردی برای حل مسائل چندهدفه

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