پارامتر های کیفیت خدمات : این پارامتر می تواند بخش های مختلفی را شامل شود نظیر هزینه های کاربر یا ایجاد ضرب الاجل برای کار یا زمان اجرا می تواند در نظر گرفته شود.
الگوریتم ژنتیک
محدوده کاری الگوریتم ژنتیک بسیار وسیع می باشد و هر روز با پیشرفت روزافزون علوم و تکنولوژی استفاده از این روش در بهینه سازی و حل مسائل بسیار گسترش یافته است. الگوریتم ژنتیک یکی از زیر مجموعه های محاسبات تکامل یافته می باشد که رابطه مستقیمی با مبحث هوش مصنوعی دارد در واقع الگوریتم ژنتیک یکی از زیر مجموعه های هوش مصنوعی می باشد. الگوریتم ژنتیک را می توان یک روش جستجوی کلی نامید که از قوانین تکامل بیولوژیک طبیعی تقلید می کند .الگوریتم ژنتیک برروی یکسری از جواب های مساله به امید بدست آوردن جوابهای بهتر قانون بقای بهترین را اعمال می کند. درهر نسل به کمک فرایند انتخابی متناسب با ارزش جواب ها و تولید مثل جواب های انتخاب شده به کمک عملگرهایی که از ژنتیک طبیعی تقلید شده اند ، تقریب های بهتری از جواب نهایی بدست می آید. این فرایند باعث می شود که نسلهای جدید با شرایط مساله سازگارتر باشد. حساب تکاملی ,برای اولین بار در سال ۱۹۶۰ توسط آقای ریچنبرگ ارائه شد که تحقیق وی در مورد استراتژی تکامل بود.بعدها نظریه او توسط محققان زیادی مورد بررسی قرار گرفت تا اینکه الگوریتم ژنتیک (GA ) توسط جان هولند(John Holland ) و در سال ۱۹۷۵ در دانشگاه میشیگان ارائه شد.
در سال ۱۹۹۲ نیز جان کوزا (John Koza ) از الگوریتم ژنتیک (GA ) برای حل و بهینه سازی مسائل مهندسی پیشرفته استفاده کرد و توانست برای اولین بار روند الگوریتم ژنتیک (GA ) را به زبان کامپیوتر در آورد و برای آن یک زبان برنامه نویسی ابداع کندکه به این روش برنامه نویسی ,برنامه نویسی ژنتیک (GP ) گویندو نرم افزاری که توسط وی ابداع گردید به نرم افزار LISP مشهور است که هم اکنون نیز این نرم افزار کاربرد زیادی در حل و بهینه سازی مسائل مهندسی پیدا کرده است .به طور کلی الگوریتمهای ژنتیکی از اجزاء زیر تشکیل میشوند:
کروموزوم
در الگوریتمهای ژنتیکی, هر کروموزوم نشان دهنده یک نقطه در فضای جستجو و یک راهحل ممکن برای مسئله مورد نظر است. خود کروموزومها (راه حلها) از تعداد ثابتی ژن (متغیر) تشکیل میشوند. برای نمایش کروموزومها, معمولاً از کدگذاریهای دودویی (رشتههای بیتی) استفاده میشود ولی اگر تعداد عناصر برای حضور در کرموزوم زیاد باشد برای جلوگیری از افزایش فضای اشغالی توسط هر کروموزوم عدد مورد نظر را در داخل کروموزوم قرار می دهیم.
جمعیت
مجموعهای از کروموزومها یک جمعیت را تشکیل میدهند. با تاثیر عملگرهای ژنتیکی بر روی هر جمعیت, جمعیت جدیدی با همان تعداد کروموزوم تشکیل میشود.
تابع برازندگی
به منظور حل هر مسئله با بهره گرفتن از الگوریتمهای ژنتیکی ، ابتدا باید یک تابع برازندگی برای آن مسئله ابداع شود. برای هر کروموزوم ، این تابع عددی غیر منفی را برمیگرداند که نشان دهنده شایستگی یا توانایی فردی آن کروموزوم است.
در الگوریتمهای ژنتیکی ، در طی مرحله تولید مثل ازعملگرهای ژنتیکی استفاده میشود. با تاثیر این عملگرها بر روی یک جمعیت ، نسل بعدی آن جمعیت تولید میشود. عملگرهای انتخاب و آمیزش و جهش معمولاً بیشترین کاربرد را در الگوریتمهای ژنتیکی دارند.
عملگر انتخاب
این عملگر از بین کروموزومهای موجود در یک جمعیت ، تعدادی کروموزوم را برای تولید مثل انتخاب میکند. کروموزومهای برازندهتر شانس بیشتری دارند تا برای تولید مثل انتخاب شوند.
انتخاب نخبگان : مناسبترین عضو هر اجتماع انتخاب میشود. با توجه به مقدار شایستگی که از تابع ارزیاب دریافت کرده است.
عملگر آمیزش
در جریان عمل تلفیق به صورت اتفاقی بخشهایی از کروموزوم ها با یکدیگر تعویض می شوند. این موضوع باعث می شود که فرزندان ترکیبی از خصوصیات والدین خود را به همراه داشته باشند و دقیقاً مشابه یکی از والدین نباشند.هدف ، تولید فرزند جدید می باشد به این امید که خصوصیات خوب دو موجود در فرزندشان جمع شده و یک موجود بهتری را تولید کند.روش کار به صورت زیر است:
بصورت تصادفی یک نقطه از کروموزوم را انتخاب می کنیم .ژن های مابعد آن نقطه از کروموزوم ها را جابجا می کنیم.اگر عملیات تلفیق را در یک نقطه انجام دهیم به آن تلفیق تک نقطه ای می گویند. تلفیق بدین صورت انجام می گیرد که حاصل ترکیب کروموزومهای پدر و مادر می باشد.روش تولید مثل نیز بدین صورت است که ابتدا بصورت تصادفی ,نقطه ای که قرار است تولید مثل از آنجا آغاز گردد ، انتخاب می گردد.سپس اعداد بعد از آن به ترتیب از بیت های کروموزومهای پدر و مادر قرار می گیرد که در شکل ۶ نیز نشان داده شده است.
شکل ۶ - عملگر تلفیق
همان طور که در شکل ۶ می بینید یک نقطه از هر کدام از والدین انتخاب شده و جابجایی در بین والدین ایجاد شده و فرزند ساخته می شود.
روش ادغام دو نقطه ای((Two-point CrossOver : همانطور که در شکل ۷ می بینید در این روش دو مکان را به صورت تصادفی انتخاب کرده و مقادیر بین این دو نقطه را جابجا می کنیم.
شکل ۷- تلفیق دو نقطه ای
می توانیم این عملیات را در چند نقطه انجام دهیم ، که به آن بازترکیبی چند نقطه ای می گویند.
عملگر جهش
پس از اتمام عمل آمیزش, عملگر جهش بر روی کروموزومها اثر داده میشود. این عملگر یک ژن از یک کروموزوم را به طور تصادفی انتخاب نموده و سپس محتوای آن ژن را تغییر میدهد. اگر ژن از جنس اعداد دودویی باشد, آن را به وارونش تبدیل میکند و چنانچه متعلق به یک مجموعه باشد, مقدار یا عنصر دیگری از آن مجموعه را به جای آن ژن قرار میدهد. در شکل ۸ چگونگی جهش یافتن سومین ژن یک کروموزوم نشان داده شده است.پس از اتمام عمل جهش ، کروموزومهای تولید شده به عنوان نسل جدید شناخته شده و برای دور بعد اجرای الگوریتم ارسال میشوند.
شکل ۸- عملگر جهش
در شکل ۹ گردش کار الگوریتم ژنتیک ارائه شده است ابتدا جمعیت اولیه از کرموزوم ها تولید می شود حال برای تک تک کروموزوم ها تابع شایستگی محاسبه و تعیین می شود در این مرحله اگر کروموزمی به میزان شایستگی مورد نظر ما رسیده باشد الگوریتم متوقف شده و جواب برگردانده میشود در غیر این صورت با بهره گرفتن از انتخاب به روش نخبه سالار کروموزوم هایی که دارای مقدار مناسب تری باشند انتخاب شده و فرزندان بوجود می آیند و جهش در آنها رخ می دهد حال دوباره مقدار شایستگی محاسبه می شود در صورت مناسب بودن به اتمام کار میرسم وگرنه به ساخت فرزندان جدید می پردازیم و در نهایت اگر شایستگی هیچ کروموزوم به مقدار مورد نظر ما نرسد با توجه به تعداد تکرارهایی که برای الگوریتم در نظر گرفته ایم به اتمام الگوریتم می رسیم.
جمعیت اولیه
ارزیابی جوابها
آیا جواب مورد نظر حاصل شده؟
انتخاب
تلفیق
بله
جهش
T=T+1
T=0
خیر
شکل ۹-گردش کار الگوریتم ژنتیک
شبکه عصبی
شبکه های عصبی مصنوعی (Artificial Neural Network) الگویی برای پردازش اطلاعات می باشند که با تقلید از شبکه های عصبی بیولوژیکی مثل مغز انسان ساخته شده اند.عنصر کلیدی این الگو ساختار جدید سیستم پردازش اطلاعات آن می باشد و از تعداد زیادی عناصر (نرون) با ارتباطات قوی داخلی که هماهنگ با هم برای حل مسائل مخصوص کار می کنند ، تشکیل شده اند. شبکه های عصبی مصنوعی با پردازش روی داده های تجربی، دانش یا قانون نهفته در ورای داده ها را به ساختار شبکه منتقل می کند که به این عمل یادگیری می گویند. اصولاً توانایی یادگیری مهمترین ویژگی یک سیستم هوشمند است. سیستمی که بتواند یاد بگیرد منعطف تر است وساده تر برنامه ریزی میشود، بنابراین بهتر میتواند در مورد مسایل و معادلات جدید پاسخگو باشد. انسانها از زمان های بسیار دور سعی بر آن داشتند که بیوفیزیولوژی مغز را دریابند چون همواره مسئله هوشمندی انسان و قابلیت یادگیری ،تعمیم،خلاقیت،انعطاف پذیری و پردازش موازی در مغز برای بشر جالب بوده و بکارگیری این قابلیتها در ماشینها بسیار مطلوب می نمود.روش های الگوریتمیک برای پیاده سازی این خصایص در ماشینها مناسب نمی باشند در نتیجه می بایست روشها مبتنی بر همان مدلهای بیولوژیکی باشد.ANN درست مثل انسانها با بهره گرفتن از مثالها آموزش می بیند ; همانطور که یک بچه با دیدن انواع مختلف از یک حیوان قادر به تشخیص آن می باشد. از ویژگی های شبکه عصبی می توان به موارد زیر اشاره کرد:
قابلیت یادگیری و تطبیق پذیری : این ویژگی باعث آن شده است که از شبکه عصبی با یک بار آموزش بتوان بارها استفاده کرد.
قابلیت تعمیم پذیری: شبکه عصبی این قابلیت را دارد که گسترش دارد و این کار بدین شکل انجام میگیرد که باید شبکه را با مقیاس جدید آموزش بدهیم
پردازش موازی : قابلیت موازی سازی از ویژگی های کلیدی شبکه عصبی می باشد که باعث افزایش سرعت اجرای شبکه چه در بخش تمرین و چه در بخش آزمایش می شود.
مقاوم بودن: از این شبکه حتی با وجود داده های نویز دار میتوان انتظار نتیجه مطلوب را داشت و این ویژگی با توجه به داده ها در دنیای واقعی بسیار مورد استفاده قرار میگیرد.
پیشینه تحقیق
در این بخش به بررسی کارهای مرتبط در زمینه زمانبندی و اختصاص منابع در محیط های محاسبات ابری می پردازیم.