پایان‌نامه ارشد کامپیوتر برنامه ریزی منابع ابررایانه الگوریتم رقابت استعماری

۱۰۰ هزار تومان ۶۰ هزار تومان
افزودن به سبد خرید

جهت خرید و دانلود پایان‌نامه ارشد کامپیوتر برنامه ريزي منابع ابررايانه الگوريتم رقابت استعماري روی خرید محصول کلیک و یا با ایمیل زیر در ارتباط باشید

sellthesis@gmail.com


پایان ‌نامه کارشناسی ارشد کامپیوتر روش برنامه ريزي منابع ابر رايانه براساس الگوريتم رقابت استعماري


خرید محصول پایان‌نامه ارشد کامپیوتر برنامه ريزي منابع ابررايانه الگوريتم رقابت استعماري


چکیده:

سیر تکاملی محاسبات به گونه ای است که می‌توان آن را پس از آب، برق، گاز و تلفن به عنوان عنصر اساسی پنجم فرض نمود. در سالهای اخیر توجهات فزاینده ای به محاسبات ابری شده است. محاسبات ابری مدلی توزیع شده با مقیاس بزرگ است که مجموعه مقیاس پذیر و مجازی شده از قدرت محاسباتی مدیریت شده، فضای ذخیره سازی و سرویس‌ها را از طریق اینترنت در اختیار مشتریان قرار می‌دهد.
مسئله تخصیص منابع در رایانش ابری و زمانبندی هر یک از کارهای کاربر بر روی ماشین های مجازی موجود، يک مسئلهNP-Completeمي باشد که تاکنون الگوريتم‌هاي بسياري جهت حل آن ارائه گرديده است. ولی هیچ یک از این الگوریتم ها قادر به برآورده ساختن نیازمندیهای مرتبط با سرعت و دقت در محیطهای رایایش ابری نیستند. در اين پژوهش، روشی ترکیبی از الگوریتم رقابت استعماری و جستجوی محلی، برای حل این مسئله پيشنهاد گردیده است. این الگوریتم با ایجاد یک امپراتوری اولیه سعی در بهبود سازی پاسخ های ممکن، از طریق اعمال مراحل الگوریتم رقابت استعماری دارد. جهت جلوگیری از همگرایی زودرس، الگوریتم رقابت استعماری با یک الگوریتم جستجوی محلی ترکیب شده است. الگوریتم ترکیبی پیشنهادی از یک مکانیسم تشخیص همگرایی مبتنی بر ضریب شباهت استفاده کرده و در زمانهایی که روش رقابت استعماری دچار همگرایی زودرس می شود، روش جستجوی محلی را اجرا می کند.
کيفيت جواب¬ها وکارايي الگوریتم پیشنهادی با کارايي الگوريتمهای دور رابین، کلونی مورچگان و ژنتیک، مقايسه گرديد.
نتایج : نتایج بدست آمده، نشان میدهد که الگوريتم پيشنهادي از نظر کيفيت زمان اجرا از دو الگوریتم کلونی مورچگان و الگوریتم ژنتیک سریعتر عمل می کند. علاوه بر این، الگوریتم پیشنهادی از نظر کیفیت جواب‌ها، از بقيه الگوريتم‌هاي مقايسه شده بهتر عمل می کند.

کلمات کلیدی: تخصیص منابع، رایانش ابری، الگوریتم رقابت استعماری، جستجوی محلی، NP-Complete.


فهرست مطالب
عنوان صفحه

فصل اول: کلیات 1
1-1: مقدمه 2
1-2: بیان مسئله 3
1-3 : پیشینه تحقیق 5
1-4: مروری بر فصل های پایان نامه 7

فصل دوم: ادبیات تحقیق 8
2-1: مقدمه 9
2-2: محاسبات توری 9
2-2-1: تعریف محاسبات توری 10
2-2-2: معماری محاسبات توری 11
2-2-3: مزایا و خطرات بالقوه محاسبات توری 13
2-2-4: انواع تورها 15
2-2-4-1: تورهای خوشه ای 15
2-2-4-2: تورهای سازمانی 17
2-2-4-3: تورهای سودمندی 18
2-2-4-4: تورهای انجمنی 19
2-3: محاسبات ابری 21
2-3-1: تعاریف محاسبات ابری 21
2-3-2: لایه های سه گانه ابر 25
2-3-2-1: زیرساخت به عنوان سرویس (IaaS) 26
2-3-2-2: بستر به عنوان سرویس (PaaS) 27
2-3-2-2: نرم افزار به عنوان سرویس (SaaS) 27
2-4 الگوریتم رقابت استعماری (ICA) 28
2-4-1 نگاهی به تاریخچه استعمار 28
2-4-2 بهینه سازی بر اساس رقابت استعماری 29

فصل سوم: پیشینه تحقیق 31
3-1 مقدمه 32
3-2 سیستم مدیریت منابع اکالیپتوس 33
3-3 تخصیص منابع با استفاده از کلونی مورچه ها 36
3-4 تخصیص منابع با استفاده از الگوریتم ژنتیک 38

فصل چهارم: روش پیشنهادی 43
4-1 مقدمه 44
4-2 ساختار الگوریتم رقابت استعماری پیشنهادی 45
4-2-1: کدگذاری 46
4-2-2: شکل دهی امپراتوری های اولیه 47
4-2-3: مدل سیاست جذب: حرکت مستعمره ها به سمت امپریالیست 49
4-2-4: جابجایی موقعیت مستعمره و امپرالیست 52
4-3: جستجوی محلی 53
4-3-1: مکانیسم کنترل جستجوی محلی 54

فصل پنجم: پیاده سازی و ارزیابی نتایج 56
5-1 مقدمه 57
5-2: محک های استفاده شده 57
5-3 بررسی پارامترهای مختلف الگوریتم پیشنهادی 58
5-4 مقایسه الگوریتم پیشنهادی با الگوریتم های دیگر 61
5-4-1 مقایسه زمان های اجرا 61
5-4-2 مقایسه کیفیت پاسخها 62

فصل ششم: نتیجه گیری و کارهای آتی 64
6-1: مطالعات آتی 65
منابع 66


مقدمه:

در سالهای اخیر توجهات فزاینده ای به محاسبات ابری شده است. بیشترین استقبالی که از این تکنولوژی صورت گرفته در صنعت چندرسانه ای و سیستم‌های آنالیز می‌باشد. در محاسبات ابری برخی از تصمیمات تحت عنوان تصمیمات برنامه‌ریزی شناخته می‌شوند. فرآیند برنامه‌ریزی منابع لازم جهت تولید مجموعه فعالیت‌های مورد نیاز جهت زمانبندی را تعیین می‌کند[Baker00]. زمانبندی عبارت است از تخصیص منابع محدود به فعالیت‌ها در طول زمان، جهت بهینه سازی یک یا چند تابع هدف [Baker00]. مسئله زمانبندی منابع رایانش ابری ، جزء مهمترین مسائل زمانبندی می‌باشد که توجه بسیاری از محققان را به خود جلب کرده است. مسئله زمانبندی منابع، یک مسئله بسیار سخت در میان مسائل NP-hard محسوب می‌شود [Yu12، Garey76].
مسئله زمانبندی و تخصیص منابع در یک ابر و یک تور، یک مسئله بسیار سخت می باشد و در نتیجه فضای جستجوی این مسئله به اندازه ای بزرگ است که اگر یک الگوریتم بخواهد این فضا را به صورت ترتیبی مورد بررسی قرار داده و بهترین جواب را بیابد، نیاز به زمان نمایی خواهد داشت. از جمله الگوریتم های ابتکاری که در حوزه زمانبندی و تخصیص منابع مورد استفاده قرار گرفته اند، می توان به الگوریتم کلونی مورچگان [Zhu12, Chen09] و الگوریتم ژنتیک [Javier07] اشاره کرد.
الگوریتم کلونی مورچه ها، نوعی الگوریتم مبتنی بر هوش جمعی است که از مطالعات و مشاهدات روی کلونی مورچه ها الهام گرفته شده است [Diargo96]. در دنیای واقعی، ابتدا مورچه ها به صورت تصادفی به این سو و آن سو می روند تا غذا بیابند. سپس به لانه بر می گردند و ردی از فرومون در مسیر به جای می گذارند. هنگامی که یک مورچه به طور تصادفی و تنها حرکت می کند، با مواجه شدن با مسیری که دارای اثر فرومون بیشتری است، به احتمال زیاد مسیر فوق را انتخاب می کند و با فرومونی که از خود بر جای می گذارد، آن را در مسیر مذکور تقویت می کند. اگر چه الگوریتم های مبتنی بر کلونی مورچگان ارائه شده [Zhu12, Chen09]، قابلیت زمانبندی موازی مسئله تخصیص منابع در رایانش ابری را فراهم می کند، ولی جهت اجرای کارآمد این الگوریتم نیاز به سخت افزار موازی قدرتمندی می باشد و اجرای آن بر روی یک سیستم زمانبند نیاز به زمان قابل ملاحظه ای خواهد داشت.
در [Javier07] الگوریتم زمانبندی و تخصیص منابع در رایانش ابری و توری به وسیله الگوریتم ژنتیک مورد بررسی قرار گرفته است. الگوریتم ژنتیک، نوعی الگوریتم ابتکاری است که از تئوری “زنده ماندن شایسته‌ترین” داروین ایده گرفته است [Eiben07]. الگوریتم ژنتیک را می‌توان به عنوان نوعی الگوریتم تکاملی دسته‌بندی کرد که جواب‌های بالقوه یک مسئله خاص را در قالب ساختارهای داده ای شبیه به کروموزوم ، کدگذاری کرده و عملگرهای ترکیب مجدد را بر روی این ساختارها اعمال می‌کند تا اطلاعات حیاتی را حفظ کند.
بر این اساس، در این مقاله، روشی مبتنی بر الگوریتم رقابت استعماری [Atashpaz07] جهت حل مسئله زمانبندی کار ارائه می شود. این الگوریتم در کلاس الگوریتم های ابتکاری مبتنی بر جمعیت طبقه بندی می شود و در نتیجه مشکلات روشهای سیستماتیک سنتی را ندارد. علاوه بر این، در روش پیشنهادی، از جستجوی محلی جهت جلوگیری از گرفتار شدن الگوریتم در بهینه های محلی استفاده شده است و به همین دلیل ، این الگوریتم در شرایط بهینه های محلی، رفتار هوشمندانه تری را نسبت به الگوریتم ژنتیک از خود نشان می دهد. علاوه بر این، الگوریتم پیشنهادی نیاز به سخت افزار خاصی جهت اجرا شدن ندارد و از نظر زمانی می تواند بسیار بهتر از الگوریتم کلونی مورچگان عمل کند.


محاسبات توری

واژه تور یا محاسبات توری، معانی مختلفی برای افراد مختلف دارد. معانی که به این واژه نسبت داده شده اند، طیف وسیعی از محاسبات خوشه ای، محاسبات با کارایی بالا ، محاسبات مبتنی بر کارکرد ، محاسبات نظیر به نظیر گرفته تا نوع جدیدی از محاسبات تحت عنوان محاسبات بدن زیرساخت را شامل می‌شود. ولی منظور ما از تور در این پایان نامه، همان محاسبات توری است که در ادامه به ترسیم ساختار و تعریف آن خواهیم پرداخت. بنابراین این بخش موارد زیر را پوشش می‌دهد:
• تعریف محاسبات توری.
• توصیف معماری محاسبات توری.
• مختصری از مزایا و خطرات محاسبات توری.
• انواع تورها.

مرور

هیچ دیدگاهی برای این محصول نوشته نشده است.