ناب لرنینگ |
بزرگترین بانک اطلاعاتی پروژه های دانشجویی زمانبندی وظایف در رایانش ابری
جهت تخصیص منابع و حفظ تعادل بار بین ماشین های مجازی در رایانش ابری روشهای مختلفی مطرح شده است. برخی از این روشها عبارتند از الگوریتم ژنتیک، الگوریتم کلونی زنبور عسل، الگوریتم کلونی مورچگان، جهش قورباغه، الگوریتم وال، سنجاقک، الگوریتم قطره های آب و غیره. از این رور هر کدام از این روشها دارای مشکلاتی در زمینه ایجاد تعادل بار و تخصیص منابع هستند. اصلی ترین چالشی که این الگوریتم ها با آن مواجه هستند، ایجاد تعادل بار بین ماشین های مجازی به منظور تخصیص منابع در دیتاسنترهای رایانش ابری است.
اگر بخواهیم به صورت هسته شناسی چالش تعادل بار در این الگوریتم ها را مورد بررسی قرار دهیم، باید به این صورت مطرح نمود که این الگوریتم ها به خوبه نمی توانند تعادل بار را در ماشین های مجازی موجود در دیتاسنترها فراهم نموده و سربار داده بین ماشین های مجازی به مراتب زیاد شده و تعداد وظایف زیادی مجبور به مهاجرت به ماشین های مجازی دیگر هستند. این چالش و مشکل زمان اجرا و زمان پاسخ را تحت تاثیر قرار داده و منجر به افت سیستم و افزایش مصرف انرژی در دیتاسنترهای رایانش ابر می گردد.
الگوریتم های زمانبندی وظایف در رایانش ابری
در این بخش به معرفی برخی از مهمترین الگوریتم های زمانبندی وظایف در رایانش ابری پرداخته خواهد شد.
الگوریتم های زمانبندی بر اساس PSO
پديده PSO، براي اولين بار توسط کندي و ابرهارت در سال ۱۹۹۵ مطرح شد. PSO يک الگوريتم محاسبه اي تکاملي الهام گرفته از طبيعت و براساس تکرار مي‌باشد. منبع الهام اين الگوريتم، رفتار اجتماعي حيوانات، همانند حرکت دسته جمعي پرندگان و ماهي‌ها بود. از اين جهت که PSO نيز با يک ماتريس جمعيت تصادفي اوليه، شروع مي‌شود، شبيه بسیاری دیگر از الگوریتم های تکاملی همچون الگوريتم ژنتيک پيوسته است.
برخلاف الگوریتم ژنتیک ، PSO هيچ عملگر تکاملي همانند جهش و تزويج ندارد. هر عنصر جمعيت، يک ذره ناميده مي‌شود (که همان معادل کروموزوم در GA) است. در واقع الگوريتم PSO از تعداد مشخصي از ذرات تشکيل مي شود که به طور تصادفي، مقدار اوليه مي گيرند. براي هر ذره دو مقدار وضعيت و سرعت، تعريف مي شود که به ترتيب با يک بردار مکان و يک بردار سرعت، مدل مي‌شوند.
الگوریتم ژنتیک
الگوریتم ژنتیک برای اولین بار در سال ۱۹۷۵ توسط Holland و برپایه ی اصل تکامل که در طبیعت مشاهده می گردد بنا نهاده شده است. در الگوریتم ژنتیک هر کروموزوم بیانگر یک راه حل ممکن برای مسئله می باشد و متشکل رشته ای از ژن ها است. در ابتدا جعیت به صورت تصادفی برای ایجاد نقطه ی شروع الگوریتم انتخاب می شوند. یک تابع برازش برای بررسی تناسب کروموزوم و محیط تعریف می شود. تابع برازش می تواند بر اساس make span, Flow time و یا هزینه ی اجرایی بنا نهاده شده باشد.
بر اساس مقدار برازش، کروموزوم ها انتخاب شده و عملگر های تزویج و جهش بر آنها اِعمال شده و نسل جدید جمعیت تولید می شوند. کیفیت هر نسل بوسیله ی تابع برازش ارزیابی می شود. این فرایند تا تولید نسل دلخواه ادامه می یابد.
الگوریتم های بر پایه ی کلونی مورچگان
این الگوریتم ها از رفتار واقعی مورچه ها در یافتن کوتاهترین مسیر بین کلونی و منابع غذا، الهام گرفته شده است. این روش نوین در سال ۱۹۹۲ توسط Dorigo به عنوان رساله ی دکترای وی معرفی شد و در اصل سیستم مورچه نامیده می شد. مورچه ها در مسیر طی شده ردپایی با استفاده از ماده شیمیایی خاصی به نام فرومون برجای می گذارند. با گذشت زمان و عبور سایر مورچه ها، درمسیرهای بهینه غلظت فرومون بیشتر شده و مورچه های بعدی مسیر بهتر را تشخیصص می دهند.
روش ACO برای حل مسائل بهینه سازی گسسته که نیازمند یافتن یک مسیر به هدف می باشند، مفید است. مسائل مختلفی از قبیل مسئله ی کوله پشتی چند بُعدی، زمانبندی کارها در محیط Grid ، و بسیاری دیگر با استفاده از این روش با موفقیت حل شده است.
الگوریتم LCA
این الگوریتم که اخیرا توسط دکتر علی حسین زاده کاشان برای بهینه سازی های سراسری و بر پایه ی تقلید فرایند قهرمانی در رقابت های ورزشی ارائه شده است. روش LCA می تواند به صورت زیر بیان گردد:
یک تعداد نقش های مجزا به عنوان تیم های ورزشی در یک لیگ مصنوعی برای چندین هفته با هم به رقابت می پردازند. براساس زمانبندی هفتگی لیگ، تیم ها دو به دو بازی می کنند و خروجی بازی آنها به صورت برد، باخت و یا مساوی تعیین می گردد. هر تیم دارای ترکیب و چینش خاصی بوده که دارای مقدار برازش بخصوصی به خود می گیرد. با ثبت و نگهداری مسیر وقایع هفته ی گذشته، هر تیم برای تغییرات مورد نیاز در چینش و نحوه ی بازی خود برای بازی هفته آینده تصمیم می گیرد و مسابقات پس از تعدادی فصل ( شرط توقف ) پایان می پذیرد.
LCA الگوریتمی بر مبنای جمعیت می باشد که در آن تیم ها همانند ذرات در PSO با تفاوت اندک در نحوه ی انجام جستجوی آنها هستند. روشی که برای ایجاد راه حل های جدید در LCA استفاده می شود، بسیار شبیه فرایند آنالیز بازی است که توسط مربیان تیم برای طراحی ترکیب مناسب برای بازی آینده بکار می رود. به عنوان نمونه در یک انالیز بازیف مربیی تیم چینش تیم خود را بر اساس تجربه خود از مسابقه و همچنین سبک بازی تیم حریف اصلاح می کند. الگوریتم LCA الگوریتمی بر مبنای جمعیت و چارچوبی برای بهینه سازی سراسری در فضای جستجوی پیوسته می باشد.
الگوریتم سنجاقک
الگوریتم سنجاقک با توجه به دیدگاه رینولدز، رفتار ذرات شامل سه اصل مهم می باشد که عبارتند از: ۱٫ جدایی: این عملگر اشاره به عدم تماس دو یا چند فرد یا ذره در یک فضا دارد.۲٫ ترازبندی: عدم تجاوز سرعت ذرات یا اشیا نسبت به سایر همسایه ها در یک فضای واحد.۳٫ انسجام: این عملگر نیز به این اشاره دارد که افراد به سمت به هدف واحد یا مرکز مورد نظر سوق پیدا کنند.هدف اصلی هر ذره در سناریو فوق زنده ماندن است. بنابراین همه افراد یا ذرات باید به سمت منبع غذایی جهش پیدا کرده و از وابستگی به موارد دیگر خود داری نمایند. با توجه به این دو رفتار ذرات، ۵ عامل اصلی در بروز رسانی موقعیت ذرات وجود دارد که در شکل زیر نشان داده شده است.
