دانلود مقاله الگوریتم ژنتیک و محاسبات گرید


Widget not in any sidebars

در این قسمت می خواهیم یک الگوریتم ژنتیک بر پایه زمانبند گرید ارایه کنیم این الگوریتم باید از برخورد متقابل userها و منابع جلوگیری کند.الگوریتم برای jobهای مستقل با محدودیت های مربوطه به taskهای job و فرآیند درجه بندی با زمان محاسباتی مناسب که شامل محدودیت های مربوط به سلسله مراتبی می تواند برای پایین ترین و بالاترین سیستم مدیریتی استفاده شود.
4-5-1 زمانبندی های موجود و مورد استفاده در گرید:
در سال های اخیر سیستم های زمانبند توسعه یافته اند معمولاً با الگوریتم های تعبیه شده برای کشف منابع و تخصیص سیستم که پذیرش و توصیف jobها را برای واسط user تامین می کند.در معماری هر سیستم طراحی شده برای استفاده های متفاوت برای متمرکز سازی و غیر متمرکزسازی،jobها با ویژگی ها و ارتباط و وابستگی و زمان اجرایی مورد انتظار،نقاط بررسی،نظارت بر فرآیندها و بازخوردuserها و سایر موضوعات بررسی می گردد.
4-5-1-1زمانبند جدید توسط الگوریتم ژنتیک:
هر زمانبند گرید طراحی شده برای مدیریت منابع دارای قابلیت حمل با ابزارهای گوناگون توسعه یافته برای تحقیقات گروهی گرید و بخشی برای تخصیص گروهی از منابع سیستم می باشد.این بخش حاضر طراحی شده و پیاده سازی شده از الگوریتم زمانبند ما می باشد.زمانبند برای بهینه سازی زمان بیکاری و زمان محاسباتی در دسترس منابع تلاش می کند و بن بست هایی از userهای خاص ایجاد می شود.
حل فضا برای نگاشت jobها به cluster هایی،نیاز به اعداد کوچکتر از اعداد تخصیص داده شده به گره های محاسباتی دارد،بنابراین ممکن است زمانبندهایclusterها توسعه یافته تنها بر پایه الگوریتم های آگاهانه صورت گیرد.زمانبند گرید نیاز به نگاشت پویا در دسترس و منابع غیر تخصیص یافته برای taskهای مربوط به jobهایی دارد.گره های محاسباتی ممکن است به صورت جغرافیایی توزیع یافته و نیاز به برخورد با انواع jobها داشته باشند.بنابراین حل فضای حالت برای زمانبند گرید در مقیاس بزرگ نیاز زمانبندهای طولانی مدت دارد.
در محیط گرید،اهداف userها و منابع تامین شده می تواند برخورد داشته باشد،اهداف و تلاش ها برای بهبود کارآیی به روابط زیر منجر شده است:
دلالتTst برای زمان پایانی برای آخرین taskزمانبندی می باشد،بدین منظور زمان تاخیر به صورت زیر تعریف می شود:
فرض کنیم Tc(i) زمان بحرانی برای iامینjob باشد.Tc ماکزیمم زمان(Tc(i))برای همه jobهایی که باید زمانبندی شوند باشد و Tst زمان پایانی برای آخرین taskباشد.wدلالت برmakespanدارد:

زمان بیکاری برای هر گره به دلیل غیر استفاده بودن شکاف ها(gap) باید محدودیت های taskها و job برای رویه ها فرآهم کند.
فرض کنید m تعداد task در jامین گره و فرض کنید n تعداد گره های محاسباتی باشد.فرض کنیدTgs(j,k) زمان شروع kامین task و jامین گره و Tge(j,k)زمان پایان kامین task باشد بنابراین:
Tgen نرمال شده زمان بیکاری برای همه گره ها باشد.
چهار مورد می تواند با وزن های αوβووبرای تابع بازخورد F به صورت زیر باشد:
چهار پارامتر استفاده شده برای jobها برای تامین منابع در این سیستم نیاز به تطابق با userها دارند.
بعد از تابع بازخورد برای هر job جمعیت اولیه محاسبه می شود میانگین تابع بازخورد و استاندارد deviation(SD) محاسبه می شود.اگرSD کمتر از مقدار آستانه باشد برای حل قابل قبول است.الگوریتم ژنتیک همگرایی آن را بیان می کند.همگرایی الگوریتم برای حل تولید جمعیت جدید از نیازها به صورت تصادفی تولید می شود.البته این حل بدون برای تولید جمعیت جدید روش elitismمورد استفاده قرار می گیرد.
ابتدا مجموعه ای از تابع های برخورد ساخته می شوند،اعداد تصادفی می توانند ساخته شوند.این اعداد خارج از جمعیت موجود کاندیدها برای تولید جمعیت جدید می توانند باشند.الگوریتم ژنتیک بر پایه جستجومی توانند نزدیک به بهینه در زمان معقول عمل کند هر گاه فضای حل مساله خیلی بزرگ باشد.زمانبندی گرید یک مساله بهینه می باشد،وزن ها می توانند برای تغییر رفتار زمانبند به کار روند.الگوریتم ژنتیک برای زمانبندیمی تواند به آسانی برای تغییرات فضای مساله به کار رود.الگوریتم ژنتیک برای زمانبند و کاربردهای گرید برای تخخصیص منابع به سیستم مورد استفاده قرار می گیرد.
به طور عمومی هر job با یک گراف بیان می شود،که taskهای زیادی در چند سطح بیان می شوند.تابع بازخورد برای اندازه گیری کیفیت زمانبندی تعریف می شود،بنابراین user برای حداقل کردن زمان گردش و پذیرش user زمانی که منابع تامین شده برای تکمیل زمان و حداقل کردن زمان بیکاری هر گره محاسباتی به کار می رود.
RASسعی می کند زمانبندی برای jobها را برای پردازش و گره های محاسباتی بهتر کند.زمانی که زمانبند ممکن استtaskها را برای jobها با زمان گپ های بیکار در نظر نگیرد برای اعمال این زمان از رابطه زیر استفاده می شود.
مقدار نرمال برای زمان گردش از رابطه زیر بدست می آید:
فرض کنیم Tjobdline(i)زمان iامین job و فرض کنیم Tdt(i) زمان تاخیر برای ملاقات iامین jobباشد.
4-6 زمانبندی jobها با استفاده از الگوریتم ژنتیک با quality of service QoSدر گریدهای اقتصادی
محاسبات گرید برای همپوشانی و استفاده از منابع توزیع یافته،بیکار (idle)و منابع گسترده جهانی در اینترنت برای حل مسایل پیچیده که نیاز به به داده های محاسباتی دارند بکار می روند.مساله تقسیم به زیر مسایلی می شود که job نامیده می شود و این مسایل از نظر زمان اجرایی مسایل NPکامل هستند که نیاز به زمانبندی و استراتژی خوب برای استفاده از گریدهای توزیع یافته دارد.به منظور حل مسایل بسیاری از نگرش ها و روش های آگاهانه پیشنهاد شده است که نتایج نزدیک به بهینه دارند.ارزیابی الگوریتم ژنتیک برای (Quality of Service)QoSوابسته به taskهای همگن می باشد.تمرکز اصلی کار ما حداقل کردن makespanو انتخاب منابعمی باشد.نتایج با الگوریتم های موجود قبلی مقایسه می شوند.
محاسبات گرید ادغام تکنیک های محاسباتی و گسترده برای ارتباطات در محیط های توزیع یافته می باشند.رشد اینترنت در سده اخیر گریدهای محاسباتی را قادر ساخته است که منابع را در شبکه به اشتراک بگذارند که استفاده از این منابع نیاز به مسایل پیچیده دارد.قابلیت محاسباتی بالای گرید برای منابع توزیع یافته موجب تکمیل سریع تر و اجرای مستقل taskهای کوچکترمی شود.به اشتراک گذاری این منابع نیاز به مدیریت چندگانه دارد.که آنها در super computer های مجازی اجرا می شوند.
مردم بسیاری از موسسات که برای حل مساله عمومی با همکاری می کنند از یک سازمان مجازی مانند گرید کمک می گیرند.علومی که نیاز به حل مسایل محاسباتی با حجم بالا دارند مهندسی،حسابداری علوم فضایی و سایر علومی که نیاز به حجم بالایی از داده ها دارند از تکنولوژی گرید استفاده می کنند.
در محیط های گرید نیاز به نظارت شبکه و منابع می باشد.اگر شبکه یا منابع شبکه پایدار نباشند اجرای jobها نیاز به زمان بالا دارد و با شکست مواجه می شود.الگوریتم های کلاسیک و سنتی مانند (First Come First Service)FCFS و (Shortest Job First)SJF در محیط گرید کارا و موثر نیستند.
این غیر ممکن است که صدها منبع برای زمانبندی jobها بتوانند از این الگوریتم ها استفاده کنند چون نگهدار ی و ذخیره این منابع نیاز به ترافلاپس کارآیی(performance)دارد.نرم افزار های open sourceبرای الگوریتم های زمانبندی آگاهانه مانند(Minimum Completion Time)MCT و (Minimum Excution Time)MET پیشنهاد می شود.