دانلود مقاله الگوریتم و رای


Widget not in any sidebars

این الگوریتم زمانی متوقف می شود که شرط زیر برقرار باشد:
که در آن Qɛ[0,1]وK گامهای تکرار الگوریتم می باشد.همه معادلات بالا برای الگوریتم FCM(Fuzzy Classfication Method) به صورت زیر خلاصه می شود:
Algorithm:Fuzzy C-Means
Step 1:Generate an initial U and V
Step 2:At k-step:calculate the centers vectors C(k)=[vj]with U(k):
Step3:Update U(k),U(k+1)
Step 4:If ||U(k+1)-U(k)||<Øthen STOP;
Otherwise return to step 2.
فصل چهارم:
متدها و پارامترهای مورد ارزیابی
4-1 الگوریتم QoS برای زمانبندی taskهای مستقل در گرید،طبق QoS(Quality of Service)برای منابع محاسباتی در گرید.2-tier الگوریتم ترکیبی مستقل از زمانبندی برای حداقل کردن هزینه زمانی در گرید معرفی کرد.QGMM(QoS Guided Min-Min)[2]
گرید یک حالت سرکشی به منابع محاسباتی می باشد که یک سری محاسبات مجتمع و یکپارچه و منابع محیط گرید،ایجاد می گند.
محاسبات گرید الگویی برای حل مسایل می باشد،زمانبندی taskها یکی از مسایل است که باید در محیط گرید انجام شود.taskهای مستقل و زمانبندی آنها در این قسمت مورد بررسی قرار می گیرد که حداقل سازی و بهینه سازی زمانبندی برای LTS در نظر گرفته می شود.هر دو مورد بارکاری و تعادل و هزینه در این مورد بررسی قرار می گیرد.مساله بهینه سازی زمانبندی گروه های مختلف و توزیع ها در محیط همگن گرید یک مساله از نوع NP-Complete می باشد و در حال حاضر یک مساله ای می باشد که نیاز به جستجوی آگاهانه دارد که توسط الگوریتم هایی مانند max-min،شبیه سازی آنلاین و الگوریتم ژنتیک صورت می گیرد.
حالت در نظر گرفته برای LTS می تواند به صورت خلاصه توسط الگوریتم های ایستای آگاهانه مانند max-min،A*و الگوریتم ژنتیک انجام شود.نتایج تجربی از الگوریتم های ژنتیک و max-min نشان داده است که الگوریتم ژنتیکی بهترین عملکرد را دارد.
ولی اگر زمان اجرایی نگاشت اتفاق افتاده باشد الگوریتم min-max می تواند عملکرد عالی برای زمان های اجرایی کوتاه داشته باشد.Buyya الگوریتم خود را برای بهینه سازی هزینه و زمان در گرید معرفی کرد.علاوه بر این Literature الگوریتم min-max آگاهانه را برای task های مستقل در گرید برای بهینه سازی زمانبندی معرفی کرد.
طراحی الگوریتم بهینه سازی پیشنهاد 2-tier بر اساس الگوریتم min-max و الگوریتم ژنتیک پیشنهاد شده است.
4-1-1 تعریف مساله:
در مجموعه گرید،زمانبندی taskها برای نگاشت task به محاسبات توزیع یافته منابع و زمانبندی با هزینه بهینه و زمان بهینه مورد نظر است.در این قسمت،زمانبندی taskها متمرکز بر کلاس مستقل از task ها با محدودیت های QoS(Quality of Service) می باشد.تعدادی از taskهای متفاوت برای مثال تعدادی از taskها با پهنای باند کمتر از 100Gb/s اجرا می شود.پهنای باند تنها محدودیت و هزینه زمانی برای بهینه سازی در این قسمت دارای اهمیت می باشد.هزینه به مجموع توسعه زمان اجرایی همه taskها به metatask ها بر می گردد.در محیط های متفاوت QoS مفاهیم متفاوتی وجود دارد،ممکن است.منظور از هزینه درجه استفاده از منابع باشد.
برای شبکه QoS ممکن است به معنای پهنای باند اضافی باشد.برای cpu ممکن است سرعت پاسخ باشد.در این قسمتQoS مرتبط با پهنای باند شبکه می باشد.تعدادی از taskها نیاز به پهنای باند بالا دارند بنابراین taskها به انواع مختلف تقسیم می شوند.
1-taskها با نیازمندیهای بالای QoS
2-taskها با نیازمندیهای پایین.در گرید taskها با QoS و نیازمندیها،taskها بدون نیازمندیها می توانند با QoS بالا و یا QoS پایین اجرا شوند.زمانی که taskها با QoS بالا اجرا می شوند نیاز به تامین منابع با QoS بالا دارند.بنابراین یک سناریو می تواند شامل منابع با Qos بالا یا منابع با QoS پایین باشد.
Taskها با QoS بالا به حالت بلوکه در می آیند و taskها با Qos پایین به صورت idle یا بیکار در می آیند.بنابراین تکمیل زمان اجرایی metatask ها ممکن است با تاخیر مواجه شود.بنابراین کارآیی و قابلیت استفاده منابع می تواند بهبود یابد.
علاوه بر این هزینه پایین و کارآیی بالا و سرویس های امن برای استفاده کننده ها مطلوب است.منابع در گرید به صورت همگن در سازمانهای مختلف،استراتژی های مدیریت منابع مختلف دارند بنابراین هزینه ها برای منابع متفاوت از قوانین متفاوت تبعیت می کند.عموماً بحث درباره هزینه وابسته به زمان اجرایی می باشد.
منابع با زمان اجرایی کوتاهتر نیاز به صرف هزینه بالایی دارند.در metataskها هر task مکانیزم های دستیابی به منابع متفاوت دارد و هزینه ها تحت مکانیزمهای متفاوت یکسان نیست.بنابراین در این قسمت تمرکز بر روی چگونگی نگاشت می باشد.
زمانی که Ti بر روی ماشین mj اجرا می شود،فرض کنیمETC(Ti,mj) زمان محاسباتی باشد و CoST(Ti,mj) هزینه باشد.و R یک ماتریس t×µ با عناصر 0و1 باشد و rj یک باشد یعنی task،Ti توسط ماشین mj اجرا می شود و در غیر اینصورت rj برابر صفر می شود.برای یک مکانیزم با R سطر ماتریس زمانبندی به صورت makespan Z1 و Cost Z2 به صورت زیر تعریف می شود:
فرض Ω ماتریس زمانبندی و S همه فضاهای راه حل زمانبندی باشد ارتباط مجموعه Ω و S نگاشت 1-1 می باشد.بنابراین ماتریس t×µ شامل زمانبندی بهینه می شود و مساله بهینه سازی معادل با یافتن زمانبندی Z1وZ2 تحت محدودیت ها می باشد.
در این قسمت ما استراتژی سلسله مراتبی برای بهینه سازی مجموعه زمانبندی که مینیمم Z1 توسط الگوریتم تولید می شود و سپس جستجوی زمانبندی با مینیمم Z2 مجموعه زمانبند کاندید می باشد.