تحقیق - پایان نامه - مقاله و پروژه

پژ.هش علمی :استفاده از الگوریتم ژنتیک و منطق فازی برای بهینه سازی منابع بازار براساس شبکه بندی- قسمت ۱۴

نگاشت(mapping)ترتیب جدیدی از jobها در محیط گرید با بهره گرفتن از الگوریتم ژنتیک صورت می گیرد.جستجو و طبقه بندی (classfication)در محیط گرید با بهره گرفتن از الگوریتم طبقه بندی فازی(fuzzy classfication)صورت می گیرد.(شکل نه)
الگوریتم پیشنهادی برای تخصیص منابع به jobها در گریدهای اقتصادی:
برای مشاهده قطعه برنامه مربوط به این الگوریتم ارائه شده به زبان مطلب (MATLAB)به قسمت ضمیمه رجوع شود.
۳-۱-۴ روش طبقه بندی فازی منابع برای jobها در محیط گرید:[۲۵][۱۴][۱۵] (fuzzy classfication)
خوشه بندی (clustering)یکی از روش های برای طبقه بندی مجموعه ای از داده ها که بتوانند در طبقه های مختلف بر حسب نوع پارامترهای ورودی طبقه بندی می شوند.در موضوع ما روشی برای خوشه بندی می شود که بتواند jobها با ویژگی های مختلف یا اشیا مشابه را در گروه های مختلف سازماندهی کند یک خوشه (cluster)گروهی از اشیا می باشد که دارای ویژگی های مشابه هستند که اغلب به وسیله فاصله و طول داده در بردارهایی قرار می گیرند.
فرض کنیم مجموعه x={x1,x2,…,xn} مجموعه ای از داده ها یا jobها در موضوع ما می باشد.تابع الگوریتم FCM(Fuzzy Clustering Method)از الگو و روش زیر استفاده می شود.
که در آن mهر عدد حقیقی بزرگتر از یک می باشد.و بردار V به صورت v={v1,v2,…,vc}که مرکز خوشه ها می باشد و U=(µij)N*Cدرجه عضویت بردار x در خوشه (cluster)،jمی باشد.مقادیر ماتریس U باید شرایط زیر را داشته باشند.
µijɛ[۰,۱];i=1,2,…,N ; j=1,2,…,c
یک نرم برای بیان تشابه بین فاصله اندازه گیری شده داده ها و مرکز خوشه ها می باشد که در آن کهبرداری است که از معادله زیر بدست می آید.
بخش بندی فازی یک بهینه سازی تکراری از تابع بالا برای update کردن ماتریس بخش بندی فازی U به صورت زیر تعریف می شود.
این الگوریتم زمانی متوقف می شود که شرط زیر برقرار باشد:
که در آن Qɛ[۰,۱]و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.
فصل چهارم:
متدها و پارامترهای مورد ارزیابی
۴-۱ الگوریتم QoS برای زمانبندی taskهای مستقل در گرید،طبق QoS(Quality of Service)برای منابع محاسباتی در گرید.۲-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 های مستقل در گرید برای بهینه سازی زمانبندی معرفی کرد.
طراحی الگوریتم بهینه سازی پیشنهاد ۲-tier بر اساس الگوریتم min-max و الگوریتم ژنتیک پیشنهاد شده است.
۴-۱-۱ تعریف مساله:
در مجموعه گرید،زمانبندی taskها برای نگاشت task به محاسبات توزیع یافته منابع و زمانبندی با هزینه بهینه و زمان بهینه مورد نظر است.در این قسمت،زمانبندی taskها متمرکز بر کلاس مستقل از task ها با محدودیت های QoS(Quality of Service) می باشد.تعدادی از taskهای متفاوت برای مثال تعدادی از taskها با پهنای باند کمتر از ۱۰۰Gb/s اجرا می شود.پهنای باند تنها محدودیت و هزینه زمانی برای بهینه سازی در این قسمت دارای اهمیت می باشد.هزینه به مجموع توسعه زمان اجرایی همه taskها به metatask ها بر می گردد.در محیط های متفاوت QoS مفاهیم متفاوتی وجود دارد،ممکن است.منظور از هزینه درجه استفاده از منابع باشد.
برای شبکه QoS ممکن است به معنای پهنای باند اضافی باشد.برای cpu ممکن است سرعت پاسخ باشد.در این قسمتQoS مرتبط با پهنای باند شبکه می باشد.تعدادی از taskها نیاز به پهنای باند بالا دارند بنابراین taskها به انواع مختلف تقسیم می شوند.
۱-taskها با نیازمندیهای بالای QoS
۲-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×µ با عناصر ۰و۱ باشد و rj یک باشد یعنی task،Ti توسط ماشین mj اجرا می شود و در غیر اینصورت rj برابر صفر می شود.برای یک مکانیزم با R سطر ماتریس زمانبندی به صورت makespan Z1 و Cost Z2 به صورت زیر تعریف می شود:
فرض Ω ماتریس زمانبندی و S همه فضاهای راه حل زمانبندی باشد ارتباط مجموعه Ω و S نگاشت ۱-۱ می باشد.بنابراین ماتریس t×µ شامل زمانبندی بهینه می شود و مساله بهینه سازی معادل با یافتن زمانبندی Z1وZ2 تحت محدودیت ها می باشد.
در این قسمت ما استراتژی سلسله مراتبی برای بهینه سازی مجموعه زمانبندی که مینیمم Z1 توسط الگوریتم تولید می شود و سپس جستجوی زمانبندی با مینیمم Z2 مجموعه زمانبند کاندید می باشد.
۴-۲ استفاده از الگوریتم ژنتیک برای کاربردهای وسیع در گریدهای همگن برای زمانبندی بهینه منابع[۳]
محیط جغرافیایی توزیع یافته گرید برای تامین و محاسبه منابع گرید در سطح گریدهای سلسله مراتبی و توزیع یافته نیاز به platform محاسباتی قوی دارد.تا بحال بدلیل ارتباطات و سربار زمانبندی بین سایت ها و اجرای موازی مشکلاتی را ایجاد کرده است.در همان زمان بهینه منابع ارائه شده است که یکی از آنها استفاده از الگوریتم ژنتیک می باشد.
مساله نگاشت مجموعه ای از taskهای تکراری به مجموعه ای از منابع محاسباتی همگن یک مساله NP-Complete کامل می باشد.مقایسه الگوریتم آگاهانه زیاد در این زمینه نشان داده است که الگوریتم ژنتیک از سایر الگوریتم ها می تواند کارا باشد،که الگوریتم ژنتیک برای این زمانبندی بهینه نیاز به Clustering(خوشه بندی)و محدود کردن گراف task ها به منظور ارتباطات برای کاهش سربار زمانبندی مناسب است.بخش بندی همچنین می تواند به مدل های همگن بپردازد.نگرش ما تکنیک هایی در این قسمت ما به مزایای مدیریت سلسله مراتبی منابع محیط گرید برای توسعه الگوریتم نگاشت توزیع یافته می پردازیم،گریدهای محاسباتی مانند درخت ها برای خوشه بندی جغرافیایی نشان می دهد.هر cluster(خوشه) در کنترل administrative که دامنه کنترل عاملها نامیده می شود.یک دید از زمانبندی برای خوشه بندی و زمانبندی ارائه می کند که در این قسمت درخت نگاشت توزیع یافته پیشنهاد می شود.گام اول تولید task ها برای خوشه ها و ارتباطات سطح بالا برای گروهی از درخت های متداول می باشد.درخت مورد نظر از task های cluster که dendrogram نامیده می شود،تشکیل شده است.
در گام دوم از الگوریتم ژنتیک برای نگاشت خوشه برای taskهای در دسترس برای منابع cluster استفاده می شود.در گام سوم از یک زمانبند به صورت الگوریتم تکراری برای خاتمه الگوریتم استفاده می شود.

mop