الگوریتم جستجوی گرانشی

انجام پایان نامه  کامپیوتر

 الگوریتم جستجوی گرانشی

 

 

مقدمه

 الگوریتم جستجوی گرانشی

 

 

 

 الگوریتم 

 

فناوری رایانش ابری، به عنوان مدل و رهیافتی برای حل مسائل پیچیده و بزرگ در علوم مهندسی، صنعت و تجارت مطرح شده است و هر روز بر تعداد برنامه های کاربردی متفاوتی که از زیر ساخت ابری به منظور تامین نیازهای محاسباتی، ذخیره­سازی اطلاعات و سایر موارد بهره­ برداری می­کنند، افزوده می­شود.

بنابراین در چنین محیط پیچیده­ای زمانبندی و مدیریت منابع، چالش بزرگی را ایجاد می­کند و ارائه یک روش زمانبندی مناسب، بسیار مهم و ضروری می­باشد.

ر محیط ابری رسیدگی به پارامترهای تأثیرگذار به صورت توأمان حائز اهمیت می­باشد، در تحقیق جاری این نکته مورد توجه قرار گرفته و پارامترهای حائز اهمیت نیز قابلیت اطمینان، انرژی و makespan خواهد بود.

 

حل بسیاری از مسائل در زمینه­های مهندسی و سایر علوم، مستلزم استفاده از منابع محاسباتی قدرتمند است. محیط­های رایانش ابری، بستری مناسب، برای حل مسائلی است که نیاز به محاسبات سنگین و طولانی دارند.

منابع، از لحاظ جغرافیایی در این محیط، توزیع شده­اند، اما از نظر منطقی به صورت یک منبع واحد دیده می­شوند. رایانش ابری یک زیربنای سخت ­افزاری و نرم ­افزاری می­باشد که دسترسی قابل اعتماد، پایدار، فراگیر و ارزان را به منابع محلی دیگران فراهم می­کند.

آنها، این قابلیت را به وجود می­آورند که بتوانند بنگاه­های مجازی را به منظور اشتراک و یکپارچه­سازی میلیون­ها منبع که از نظر جغرافیایی در سطح سازمان­ها و حوزه­های مدیریتی پراکنده­اند ایجاد کنند.

ابریها از یکسری منابع ناهمگون، سیستم­های مدیریت، سیاست­ها و برنامه ­های کاربردی با نیازمندی­های مختلف، تشکیل شده ­اند.

 

 

 

 

 

بیان مساله

 الگوریتم جستجوی گرانشی

 

  کاربرد محاسبات ابری در حوزه انرژی تأثیرات محیطی فعالیت‌های حوزه انرژی را بهبود می‌بخشد.

فعالان صنعت از فناوری‌های ابری در مسیر بهبود سرعت و مسئولیت‌پذیری در مدیریت سیستم‌های اصلی عملیات‌های مهندسی استفاده می‌کنند.

این تعهد اغلب شامل استفاده از ترکیبی از ابر با تکنولوژی‌های موبایلی برای کمک به بهبود کارکرد تجهیزات از راه دور و مدیریت بهتر دارایی‌های سازمانی و کاهش اتلاف منابع می‌شود.

 

در کنار تمامی مزایای مذکور محاسبات ابری شرکت‌های انرژی را در محدود کردن اثرات زیست‌محیطی و کاهش میزان مصرف انرژی یاری می‌رساند.

پاین تلاش‌ها شامل تحقق مجازی‌سازی و تحکیم زیرساخت‌ها و ارائه برنامه‌های کاربردی و فرآیندها در قالب سرویس‌های مختلف به‌منظور کاهش مصرف انرژی، هزینه‌ها و افزایش فرصت‌های شغلی است.

رایانش ابری یک سیستم توزیعی و موازی شامل مجموعه­ای از کامپیوترهای درون ارتباطی و واقعی است.

کامپیوترها به­طور دینامیکی ایجاد شده و به عنوان یکی از منابع هماهنگ براساس توافقات سطح سرویس ارائه می­شوند، که با مذاکره بین سرویس ­دهنده و مشتری به ­وجود می­آیند.

 

دلیل تشبیه این تکنولوژی به ابر این است که مانند ابر جزئیات فنی­اش را از کاربران مخفی می­سازد و لایه­ای از انتزاع را بین جزئیات فنی و کاربران به ­وجود می­آورد

آنچه سیستم محاسبات ابری ارائه می­کند برنامه ­های کاربردی تجاری برخط است که از طریق مرورگر وب یا نرم­افزارهای دیگر به کاربران ارائه می­شود.

 

اطلاعات و نرم­افزارهای کاربردی بر روی سرورها ذخیره شده و براساس تقاضا در اختیار کاربران قرار می­گیرد.

در این معماری، اکثر داده­های ابر بر روی سرورهای موجود در بستر اینترنت قرار گرفته و برنامه­ های کاربردی علاوه بر سرورهای ابری بر روی مرورگرهای کاربران نیز اجرا می شود.

عموماً مصرف ­کننده ­های سیستم­های محاسبات ابری، مالک زیرساخت فیزیکی ابر نیستند، بلکه برای عدم پرداخت هزینه آن، از عرضه­کنندگان شخص ثالث اجاره می­کنند. آنها منابع را در قالب سرویس استفاده می­کنند و صرفاً بهای منابع به کار برده شده، می­پردازند.

بسیاری از سرویس­ذدهندگان محاسبات ابری، با به­ کارگیری مدل محاسبات کاربردی امکان کاهش مصرف انرژی  انجام کارها را به ­گونه ­ای مشابه با صنایع همگانی(مانند برق) فراهم می­سازند.

 

این در حالی است که سایر عرضه­ کنندگان سرویس­های خود را به صورت اشتراکی عرضه می­کنند.

به اشتراک ­گذاری قدرت محاسباتی میان چند درخواست ­کننده می­تواند باعث بهبود نرخ بهره ­وری شود زیرا با این شیوه دیگر سرورها بدون دلیل بیکار نمی ­مانند که باعث کاهش قابل توجه هزینه ها علاوه بر افزایش سرعت تولید و توسعه برنامه کاربردی می شود.

 

تأثیر دیگر این شیوه نیز این است که منابع به میزان بیشتری مورد استفاده قرار می­گیرند، زیرا مشتریان محاسبات ابری نیازی به محاسبه و تعیین بیشترین مقدار برای بار حداکثر خود دارند.

 

منابع کامپیوتری می­تواند به­

طور دینامیکی به شرایط و اولویت­ های کاربر اختصاص یابد. در محیط رایانش ابری هر کاربر برای اجرای هر کار، ممکن است با صدها منابع مجازی روبرو شود.

رایان ش ابری کاملا به مجازی­سازی وابسته است. سیستم زمان­بندی، وظایف مختلفی را در ابر جهت افزایش نرخ تکمیل کار و افزایش بهره­وری از منابع و در نتیجه افزایش توان محاسباتی، برعهده دارد.

در واقع مفهوم زمان­بندی به معنای اختصاص منابع به کارها است. از این جهت مساله زمان­بندی یک مساله مهم در مدیریت منابع موجود در ابر است، چراکه با وجود درخواست­های زیاد امکان انجام زمان­بندی به ­طور دستی در مرکز داده وجود ندارد.

در چارچوب زمان­بندی باید پارامترهای ورودی­های کاربر مانند زمان اجرای سرویس، منابع موردنیاز، تعداد آن و… در نظرگرفته شود.

 

مجازی­سازی به­ طور وسیعی در رایانش ابری استفاده می­شود. با این حال به­دلیل همگنی دینامیکی منابع بر پایگاه رایانش ابری، دستگاه­های مجازی باید با محیط مجازی رایانش ابری انطباق یابند تا بهترین عملکرد را با استفاده کامل از سرویس و منابع آن به­دست بیاورند

 

. اما برای بهبود استفاده از منابع، منابع بایستی به­درستی اختصاص یابند.

سرویس­های کاربر در محیط ابر به­صورت مستقل و یا وابسته است.

 

در سرویس­های مستقل هر سرویس و منابع مورد نیاز آن مشخص است اما در سرویس­های وابسته تقدم و تأخیر اجرای سرویس­ها بایستی در زمان­بندی مشخص درنظرگرفته شود.

 

در این حالت اگر اجرای سرویس i مقدم بر اجرای سرویس j باشد در این حالت بایستی ابتدا سرویس i اجراشده و سپس سرویس j اجرا شود، همچنین هر یک از سرویس­ها فقط زمانی اجرا می­شوند که منابع لازم در دسترس باشد.

 

 

در این پژوهش قصد داریم با انتخاب الگوریتم بهینه­ سازی چندهدفه کارآمد  به زمان­بندی سرویس­های وابسته از طریق تخصیص منابع بپردازیم بطوریکه زمان تکمیل سرویس­ها و هزینه پرداختی به سرویس­ دهنده کمینه شود.

 

 

 

الگوریتم‌های مختلفی برای زمان­بندی و کاهش مصرف انرژی  انجام کارها و تخصیص منابع ارائه شده است.

اما مرتبه زمانی این الگوریتم‌ها بالا و زمان یافتن پاسخ بهینه طولانی است.

 

زمان‌بربودن این الگوریتم­ها باعث می‌شود کارایی مناسبی در حل این مساله نداشته باشند.

 

بنابراین نیاز به استفاده از الگوریتم‌های دیگری است که در زمان قابل قبول با هزینه مناسب، پاسخ مناسبی برای این مساله به دست آوردند.

از جمله این الگوریتم‌های مناسب، الگوریتم‌های بهین ه­سازی هوشمند هستند. معروف­ترین الگوریتم­های بهینه­سازی چندهدفه عبارتند از الگوریتم چندهدفه بهینه­سازی ازدحام ذرات(MOPSO)، الگوریتم ژنتیک نسخه دوم با مرتب­سازی نامغلوب(NSGA-II)، الگوریتم تکاملی چندهدفه مبتنی بر تجزیه(MOEAD)[1].

در این پژوهش قصد داریم با الگوریتم جستجوی گرانشی و ازدحام ذرات به زمان­بندی سرویس­های وابسته از طریق تخصیص منابع بپردازیم بطوریکه انرژی اجرای کارها، زمان تکمیل سرویس­ها و هزینه پرداختی به سرویس­دهنده کمینه شود.

 

 

انجام پایان نامه  هوش مصنوعی

 

 نتیجه ­گیری

 الگوریتم جستجوی گرانشی

 

در این تحقیق یک چارچوب برای بهینه سازی پارامترهای زمانبندی وظایف با استفاده از الگوریتم بهینه سازی ازدحام ذرات و ماتریس جستجوی گرانشی ارائه شد.

تلاش روش پیشنهادي براین بود تا یک زمانبندی وظایف بهینه را پیدا کند که از میزان شایستگی خوبی برخوردار باشد. همچنین الگوریتم پیشنهادي با پارامترهاي مختلف پیاده­سازي شد و نمودارهاي مربوط به آن مشاهده شد.

استفاده از الگوریتم بهینه ­سازی ازدحام ذرات زمان لازم براي پارامترهای زمانبندی وظایف را تا حدي کاهش می­دهد، هر چند که جواب قطعی را به ما نمی­دهد و جوابی نزدیک به بهینه را خواهد داد.

براي نشان دادن عملکرد هر الگوریتم، مقایسه آن با الگوریتم­هاي قبلی امري ضروري است. بنابراین نتایج حاصل از کار، با الگوریتم­ ژنتیک مقایسه گردید.

با مقایسه الگوریتم، به این نتیجه رسیدیم که زمان پاسخ الگوریتم بهینه­سازی ازدحام ذرات در مقایسه با الگوریتم ژنتیک و بهینه سازی ازدحام ذرات کمتر است و همچنین الگوریتم بهینه­سازی ازدحام ذرات از پایداري خوبی برخوردار است به طوري­که جواب حاصل از روش پیشنهادی نزدیک به جواب بهینه خواهد بود.

 

با توجه به نمودارهاي همگرایی، مشاهده کردید که الگوریتمPSO با رویکرد جستجوی گرانشی از همگرایی خوبی برخوردار است.

همچنین با توجه به نمودارهاي میزان پایداري، براي الگوریتمPSO با رویکرد جستجوی گرانشی به از اين تعداد وظایف مختلف، آزمایش جواب واحدي به دست داده است، بنابراین پایداري الگوریتم ازدحام ذرات با رویکرد جستجوی گرانشی خوب بوده و می­توان نتیجه گرفت که جواب به دست آمده از الگوریتم پیشنهادی، جواب بهینه می­تواند باشد.

 

 

 الگوریتم جستجوی گرانشی

 

 

 

 

 پیشنهادات

 الگوریتم جستجوی گرانشی

 

با توجه به نتایج و مطالب ارائه شده در این تحقیق پیشنهاد برای کارهای آتی این است که با به کار گیری جستجوی گرانشی در الگوریتم های تکاملی دیگر مانند ژنتیک و رقابت استعماری، کلونی مورچه و غیره به مقایسه این الگوریتم­ها پرداخته شود.

 

همچنین پیشنهاد می شود که روش پیشنهادی بر روی مجموعه داده های مختلف مورد بررسی و ارزیابی قرار گرفته شود و یا با تعریف چندین تابع هدف میزان کارایی روش پیشنهادی سنجیده شود.

در نهایت پیشنهاد می شود روش پیشنهادی بر روی پارامترهای دیگری مانند انرژی تعریف شود و با الگوریتم های فرااکتشافی جدید مانند ملخ، پروانه –اتش  و… مقایسه شود

 

برای مشاهده مطالب بیشتر به سایت www.farzdon.ir مراجعه  نماید.

 

 

 

 

 الگوریتم جستجوی گرانشی