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

word 1 MB 31068 75
1394 مشخص نشده مهندسی کامپیوتر
قیمت: ۹,۷۵۰ تومان
دانلود فایل
  • بخشی از محتوا
  • وضعیت فهرست و منابع
  • چکیده                            

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

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

    کیفیت جواب­ها وکارایی الگوریتم پیشنهادی با کارایی الگوریتمهای دور رابین، کلونی مورچگان و ژنتیک، مقایسه گردید.

     نتایج : نتایج بدست آمده، نشان میدهد که الگوریتم پیشنهادی از نظر کیفیت زمان اجرا از دو الگوریتم کلونی مورچگان و الگوریتم ژنتیک سریعتر عمل می کند. علاوه بر این، الگوریتم پیشنهادی از نظر کیفیت جواب‌ها، از بقیه الگوریتم‌ های مقایسه شده بهتر عمل می کند.

     

     

    مقدمه:

    در سال های اخیر توجهات فزاینده ای به محاسبات ابری شده است. بیشترین استقبالی که از این تکنولوژی صورت گرفته در صنعت چندرسانه ای  و سیستم‌ های آنالیز می‌باشد. در محاسبات ابری برخی از تصمیمات تحت عنوان تصمیمات برنامه‌ریزی شناخته می‌شوند. فرآیند برنامه‌ریزی منابع لازم جهت تولید مجموعه فعالیت‌های مورد نیاز جهت زمانبندی را تعیین می‌کند[Baker00]. زمانبندی  عبارت است از تخصیص منابع محدود به فعالیت‌ها در طول زمان، جهت بهینه سازی یک یا چند تابع هدف [Baker00]. مسئله زمانبندی منابع رایانش ابری ، جزء مهمترین مسائل زمانبندی می‌باشد که توجه بسیاری از محققان را به خود جلب کرده است. مسئله زمانبندی منابع، یک مسئله بسیار سخت در میان مسائل NP-hard محسوب می‌شود [Yu12، Garey76].

    مسئله زمانبندی و تخصیص منابع در یک ابر و یک تور، یک مسئله بسیار سخت می باشد و در نتیجه فضای جستجو ی این مسئله به اندازه ای بزرگ است که اگر یک الگوریتم بخواهد این فضا را به صورت ترتیبی مورد بررسی قرار داده و بهترین جواب را بیابد، نیاز به زمان نمایی خواهد داشت. از جمله الگوریتم های ابتکاری که در حوزه زمانبندی و تخصیص منابع مورد استفاده قرار گرفته اند، می توان به الگوریتم کلونی مورچگان [Zhu12, Chen09]  و الگوریتم ژنتیک [Javier07] اشاره کرد.

    الگوریتم کلونی مورچه ها، نوعی الگوریتم مبتنی بر هوش جمعی است که از مطالعات و مشاهدات روی کلونی مورچه ها الهام گرفته شده است [Diargo96]. در دنیای واقعی، ابتدا مورچه ها به صورت تصادفی به این سو و آن سو می روند تا غذا بیابند. سپس به لانه بر می گردند و ردی از فرومون[1] در مسیر به جای می گذارند. هنگامی که یک مورچه به طور تصادفی و تنها حرکت می کند، با مواجه شدن با مسیری که دارای اثر فرومون  بیشتری است، به احتمال زیاد مسیر فوق را انتخاب می کند و با فرومونی که از خود بر جای می گذارد، آن را در مسیر مذکور تقویت می کند. اگر چه الگوریتم های مبتنی بر کلونی مورچگان ارائه شده [Zhu12, Chen09]، قابلیت زمانبندی موازی مسئله تخصیص منابع در رایانش ابری را فراهم می کند، ولی جهت اجرای کارآمد این الگوریتم نیاز به سخت افزار موازی قدرتمندی می  باشد و اجرای آن بر روی یک سیستم زمانبند نیاز به زمان قابل ملاحظه ای خواهد داشت.

     

    در [Javier07] الگوریتم زمانبندی و تخصیص منابع در رایانش ابری و توری به وسیله الگوریتم ژنتیک مورد بررسی قرار گرفته است. الگوریتم ژنتیک، نوعی الگوریتم ابتکاری است که از تئوری "زنده ماندن شایسته‌ترین"[2]داروین ایده گرفته است [Eiben07]. الگوریتم ژنتیک را می‌توان به عنوان نوعی الگوریتم تکاملی[3] دسته‌بندی کرد که جواب‌های بالقوه یک مسئله خاص را در قالب ساختارهای داده ای شبیه به کروموزوم[4]، کدگذاری کرده و عملگرهای ترکیب مجدد را بر روی این ساختارها اعمال می‌کند تا اطلاعات حیاتی را حفظ کند.

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

    رقابت استعماری

    شکل 2-8 فلوچارت الگوریتم  رقابت استعماری را نشان می‌دهد [Atashpaz07]. همانند دیگر الگوریتم‌های تکاملی، این الگوریتم، نیز با تعدادی جمعیت اولیه تصادفی که هر کدام از آنها یک "کشور" نامیده می‌شوند؛ شروع می‌شود. تعدادی از بهترین عناصر جمعیت (معادل نخبه‌ها در الگوریتم ژنتیک) به عنوان امپریالیست[5]انتخاب می‌شوند. باقیمانده جمعیت نیز به عنوان مستعمره[6]، در نظر گرفته می‌شوند. استعمارگران بسته به قدرتشان، این مستعمرات را با یک روند خاص که در ادامه می‌آید؛ به سمت خود می‌کشند. قدرت کل هر امپراطوری، به هر دو بخش تشکیل دهنده آن یعنی کشور امپریالیست (به عنوان هسته مرکزی) و مستعمرات آن، بستگی دارد. در حالت ریاضی، این وابستگی با تعریف قدرت امپراطوری به صورت مجموع قدرت کشور امپریالیست، به اضافه در صدی از میانگین قدرت مستعمرات آن، مدل شده است.

    با شکل‌گیری امپراطوری‌ های اولیه، رقابت امپریالیستی میان آن‌ها شروع می‌شود. هر امپراطوری‌ای که نتواند در رقابت استعماری، موفق عمل کرده و بر قدرت خود بیفزاید (و یا حداقل از کاهش نفوذش جلوگیری کند)، از صحنه رقابت استعماری، حذف خواهد شد. بنابراین بقای یک امپراطوری، وابسته به قدرت آن در جذب مستعمرات امپراطوری‌های رقیب، و به سیطره در آوردن آنها خواهد بود. در نتیجه، در جریان رقابت‌های امپریالیستی، به تدریج بر قدرت امپراطوری‌های بزرگتر افزوده شده و امپراطوری‌های ضعیف‌تر، حذف خواهند شد. امپراطوری‌ها برای افزایش قدرت خود، مجبور خواهند شد تا مستعمرات خود را نیز پیشرفت دهند. با گذشت زمان، مستعمرات، از لحاظ قدرت به امپراطوری‌ها نزدیک‌تر خواهند شد و شاهد یک نوع همگرایی خواهیم بود. حد نهایی رقابت استعماری، زمانی است که یک امپراطوری واحد در دنیا داشته باشیم، با مستمراتی که از لحاظ موقعیت، به خود کشور امپریالیست، خیلی نزدیک هستند.

     

    کلمات کلیدی:

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

    فصل اول:

    کلیات

    مقدمه

    سیر تکاملی محاسبات به گونه ای است که می‌توان آن را پس از آب، برق، گاز و تلفن به عنوان عنصر اساسی پنجم فرض نمود. در چنین حالتی کاربران سعی می‌کنند بر اساس نیازهایشان و بدون توجه به آن که یک سرویس در کجا قرار دارد و یا چگونه تحول داده می‌شود، به آن دسترسی یابند. نمونه‌های متنوعی از سیستم‌های محاسباتی ارائه شده است که سعی دارند چنین خدماتی را به کاربران ارائه دهند. برخی از این سیستم‌های محاسباتی عبارتند از: محاسبات خوشه ای[1]، محاسبات توری[2]و اخیراً رایانش ابری[3].

    در سالهای اخیر توجهات فزاینده ای به محاسبات ابری شده است. بیشترین استقبالی که از این تکنولوژی صورت گرفته در صنعت چندرسانه ای[4] و سیستم‌های آنالیز می‌باشد سود استفاده از محاسبات ابری در سال 2008، برای کاربردهای تجاری را سه تا چهار برابر سیستم‌های غیر ابری تخمین زده  شده بود[Stanoevska10].فاستر و همکارانش[5][Foster08]محاسبات ابری را به صورت زیر تعریف می‌کند:

    " محاسبات ابری مدلی توزیع شده با مقیاس بزرگ است که مجموعه مقیاس پذیر و مجازی شده از قدرت محاسباتی مدیریت شده،فضای ذخیره سازی و سرویس‌ها را از طریق اینترنت در اختیار مشتریان قرار می‌دهد."

    در محاسبات ابری برخی از تصمیمات تحت عنوان تصمیمات برنامه‌ریزی[6]شناخته می‌شوند. فرآیند برنامه‌ریزی منابع لازم جهت تولید مجموعه فعالیت‌های مورد نیاز جهت زمانبندی را تعیین می‌کند[Baker00]. زمانبندی[7] عبارت است از تخصیص منابع محدود به فعالیت‌ها در طول زمان، جهت بهینه سازی یک یا چند تابع هدف [Baker00]. مسئله زمانبندی منابع رایانش ابری[8]، جزء مهمترین مسائل زمانبندی می‌باشد که توجه بسیاری از محققان را به خود جلب کرده است. مسئله زمانبندی منابع، یک مسئله بسیار سخت در میان مسائل NP-hardمحسوب می‌شود [Yu12، Garey76]. جواب‌های بهینه این مسئله، مطلوب بسیاری از کارخانه‌های تولیدی و نیز شرکت‌های خدماتی می‌باشند. در بخش دوم این فصل مسئله تخصیص و زمانبندی منابع رایانش ابری تعریف می شود. در بخش سوم، خلاصه ای از پیشنه تحقیق بیان شده و توصیفی از روش پیشنهادی آورده شده است. بخش چهارم به مروری بر فصل های مختلف این پایان نامه تخصیص داده شده است.

     

    1-2 بیان مسئله

    ساختار کلی منابع یک ابر در شکل 1-1 آورده شده است.

    بر اساس این شکل، یک ابر از تعدادی سخت افزار (پردازنده، حافظه و ...) تشکیل شده است که این منابع لزوماً دارای ساختار همگنی نیستند. برای دسترسی و استفاده آسان کاربر، این عدم همگنی و پراکندگی منابع باید مخفی بماند. برای این منظور از ماشین های مجازی استفاده می شود. هر ماشین مجازی تعدادی از منابع را مدیریت کرده و آنها را در قالب یک واحد معرفی می کنند. به عنوان مثال ممکن است حافظه ای که یک ماشین مجازی معرفی می کند 1 گیگابایت باشد که 500 مگابایت آن مربوط به یک موبایل و بقیه مربوط به یک دستگاه پردازشی دیگر باشد. در خواست های مشتریان (که شامل طیف وسیعی از درخواست های پردازشی و ذخیره سازی و ... است) از طریق واسط کاربر به هسته ابر معرفی می شوند. هسته ابر برای انجام این کارها، درخواستی مبنی بر زمانبندی کارهای موجود بر روی ماشین های مجازی صادر می کند. وظیفه زمانبند، یافتن تخصیصی از ماشین های مجازی به کارهای ورودی است به گونه ای نیازهای محاسباتی و حافظه ای تمامی کارها، با کمترین هزینه برآورده شود. به عبارت دیگر، فرض کنید مجموعه درخواست ها (کارها) به صورت  از طریق واسط کاربر به هسته معرفی شده باشد. همچنین فرض کنید ماشین های مجازی آزاد به صورت وجود داشته باشند. حال وظیفه زمانبند تخصیص درخواست های ورودی به ماشین های مجازی آزاد است به گونه ای که تابع زیر را حداقل کند [Zhu12,Chen09,Javier07]  :

    (1-1)

    که در آن

    (1-2)

    و این مسئله قیود زیر را دارا می باشد:

    (1-3)

    ( فرمول ها در فایل اصلی موجود است )

    (1-4)

    در فرمول (1-1)،  هزینه تخصیص درخواست (کار)  iام به ماشین jام را مشخص می کند. این هزینه میتواند به طرق مختلفی تعریف شود، ولی مهمترین هزینه ها عبارتند از

    Makespan: زمان اتمام آخرین درخواست

    Mean(flow_time): میانگین زمانهای اجرای درخواستها

    هزینه می تواند ترکیبی از این دو پارامتر نیز باشد.

    1-3 پیشینه تحقیق

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

    همان طور که گفته شد، مسئله زمانبندی و تخصیص منابع در یک ابر و یک تور، یک مسئله بسیار سخت می باشد و در نتیجه فضای جستجوی این مسئله به اندازه ای بزرگ است که اگر یک الگوریتم بخواهد این فضا را به صورت ترتیبی مورد بررسی قرار داده و بهترین جواب را بیابد، نیاز به زمان نمایی خواهد داشت. الگوریتم های ابتکاری هوشمند ، با تکیه بر مکانیسم های سیستم های موفق، سعی در شبیه سازی این مکانیسم ها، جهت حل مسائل مشکل،  می نمایند. از جمله الگوریتم های ابتکاری که در حوزه زمانبندی و تخصیص منابع مورد استفاده قرار گرفته اند، می توان به الگوریتم کلونی مورچگان [Zhu12, Chen09]  و الگوریتم ژنتیک [Javier07] اشاره کرد.

    .  الگوریتم کلونی مورچه ها، نوعی الگوریتم مبتنی بر هوش جمعی است که از مطالعات و مشاهدات روی کلونی مورچه ها الهام گرفته شده است [Diargo96]. در دنیای واقعی، ابتدا مورچه ها به صورت تصادفی به این سو و آن سو می روند تا غذا بیابند. سپس به لانه بر می گردند و ردی از فرومون[9] در مسیر به جای می گذارند. هنگامی که یک مورچه به طور تصادفی و تنها حرکت می کند، با مواجه شدن با مسیری که دارای اثر فرومون  بیشتری است، به احتمال زیاد مسیر فوق را انتخاب می کند و با فرومونی که از خود بر جای می گذارد، آن را در مسیر مذکور تقویت می کند. اگر چه الگوریتم های مبتنی بر کلونی مورچگان ارائه شده [Zhu12, Chen09]، قابلیت زمانبندی موازی مسئله تخصیص منابع در رایانش ابری را فراهم می کند، ولی جهت اجرای کارآمد این الگوریتم نیاز به سخت افزار موازی قدرتمندی می  باشد و اجرای آن بر روی یک سیستم زمانبند نیاز به زمان قابل ملاحظه ای خواهد داشت. بخصوص اگر تعداد درخواست های مشتریان افزایش یابد، این الگوریتم عملاً کارایی خود را از دست داده و قادر به زمانبندی منابع نخواهد بود.

    در [Javier07] الگوریتم زمانبندی و تخصیص منابع در رایانش ابری و توری به وسیله الگوریتم ژنتیک مورد بررسی قرار گرفته است. الگوریتم ژنتیک، نوعی الگوریتم ابتکاری است که از تئوری "زنده ماندن شایسته‌ترین"[10]داروین ایده گرفته است[Eiben07]. الگوریتم ژنتیک را می‌توان به عنوان نوعی الگوریتم تکاملی[11] دسته‌بندی کرد که جواب‌های بالقوه یک مسئله خاص را در قالب ساختارهای داده ای شبیه به کروموزوم[12]، کدگذاری کرده و عملگرهای ترکیب مجدد را بر روی این ساختارها اعمال می‌کند تا اطلاعات حیاتی را حفظ کند.اگر چه الگوریتم ژنتیک الگوریتمی قدرتمند در حل مسائل غیر خطی است، ولی اگر میزان غیر خطی بودن مسئله زیاد باشد، این الگوریتم کارایی خود را از دست می دهد و دچار همگرایی زودرس شده و در بهینه های محلی گرفتار می شود. مسئله زمانبندی از جمله مسائل با اندازه درجه غیرخطی بودن بسیار بالا است و در نتیجه احتمال گرفتار شدن این الگوریتم در بهینه های محلی بسیار بالا است و در نتیجه پاسخ های این الگوریتم قابل اعتماد نخواهند بود.

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

     

    1-4 مروری بر فصل های پایان نامه

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

     

    فصل دوم:

     ادبیات تحقیق

     

    2-1 مقدمه

    سیر تکاملی محاسبات به گونه ای است که می‌توان آن را پس از آب، برق، گاز و تلفن به عنوان عنصر اساسی پنجم فرض نمود. در چنین حالتی کاربران سعی می‌کنند بر اساس نیازهایشان و بدون توجه به آن که یک سرویس در کجا قرار دارد و یا چگونه تحول داده می‌شود، به آن دسترسی یابند. نمونه‌های متنوعی از سیستم‌های محاسباتی ارائه شده است که سعی دارند چنین خدماتی را به کاربران ارائه دهند. برخی از این سیستم‌های محاسباتی عبارتند از: محاسبات خوشه ای[13]، محاسبات توری[14]و اخیراً رایانش ابری[15].

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

    2-2 محاسبات توری

    واژه تور[16] یا محاسبات توری، معانی  مختلفی برای افراد مختلف دارد. معانی که به این واژه نسبت داده شده اند، طیف وسیعی از محاسبات خوشه ای، محاسبات با کارایی بالا[17]، محاسبات مبتنی بر کارکرد[18]، محاسبات نظیر به نظیر[19]گرفته تا نوع جدیدی از محاسبات تحت عنوان محاسبات بدن زیرساخت[20]را شامل می‌شود. ولی منظور ما از تور در این پایان نامه، همان محاسبات توری است که در ادامه به ترسیم ساختار و تعریف آن خواهیم پرداخت. بنابراین این بخش موارد زیر را پوشش می‌دهد:

    تعریف محاسبات توری.

    توصیف معماری محاسبات توری.

    مختصری از مزایا و خطرات محاسبات توری.

    انواع تورها.

     2-2-1 تعریف محاسبات توری

    محاسبات توری پدیده ای پیچیده است که ریشه در دانش الکترونیکی[21] داشته واز توسعه مفاهیم محاسبات موازی[22] و توزیع شده[23] به دست آمده است. ظهور و بروز محاسبات توری مربوط به اوایل 1990 میباشد که کامپیوتر‌هایی با کارایی بالا به ارتباطات داده ای پرسرعت متصل شدند تا بتوانند محاسبات مربوط به کاربردهای علمی و مبتنی بر داده را پاسخ دهند. در آن زمان، محاسبات توری را با نامهایی مانند ابر محاسبات[24]یا فرا محاسبات[25]می‌شناختند و تاکید آن بر روی استفاده از منابع موجود برای کاربردهایی با کارایی بالا بود.

    اولین و پرکاربردترین تعریف برای محاسبات توری تعریفی است که توسط فاستر و کسلمن[26][Foster08] ارائه شده است:

    " یک تور محاسباتی، ساختاری سخت افزاری و نرم افزاری است که یک دسترسی قابل اعتماد[27]، سازگار[28]، فراگیر[29] و ارزان را به قابلیت‌های محاسباتی سطح بالا فراهم آورد. "

    مشکل واقعی مربوط به تور عبارت است از اشتراک منابع و حل مسئله هماهنگ در سازمانهای مجازی که خود از چندین زیرسازمان تشکیل شده اند. اشتراکی که ما به دنبال آن هستم، فقط یک تبادل فایلی ساده نیست بلکه دسترسی مستقیم به کامپیوترها، نرم افزار، داده و منابع دیگر را نیز شامل می‌شود[Stanoevska10].

    منابع اصلی که در یک تور می‌توانند به اشتراک گذاشته شوند، عبارتند از:

    قدرت پردازنده (قدرت محاسباتی).

    فضای ذخیره داده (سیستم فایل شبکه شده).

    ارتباطات و پهنای باند.

    نرم افزار کاربردی.

    2-2-2 معماری محاسبات توری

    یک معماری تور[30] نمایی کلی از اجزای تور را فراهم کرده اهداف و کارکردهای اجزای خود و نیز نحوه تعامل اجزا با یکدیگر را مشخص می‌کند. تمرکز اصلی معماری تور بر روی قابلیت همکاری و پروتکل‌های میان فراهم کنندگان منابع و استفاده کنندگان از این منابع می‌باشد. براساس کار فاستر و کسل‌من[31]، پروتکل‌های مورد نیاز برای تور به صورت شکل 2-1 سازماندهی می‌شوند:

  • فهرست:

    فصل اول: کلیات

    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] K.R. Baker, D. Trietsch, Principles of Sequencing and Scheduling, Wiley, 2000.

    [Yu12] H. Yu, L. Wang, Genetic Algorithm Combined with Simulation for Job Shop Scheduling Problem in Mechanical Engineering, Advances in Mechanical and Electronic Engineering, Vol. 176, pp. 139-144, 2012.

    [Garey76] M. R. Garey, D. S., Johnson, R., Sethi, The complexity of flowshop and jobshop scheduling., Mathematics of operations research, Vol.1, 1976.

    [Atashpaz07] E. Atashpaz-Gargari, C. Lucas, Imperialist competitive algorithm: An algorithm for optimization inspired by imperialistic competition, Evolutionary Computation, 2007. CEC 2007. IEEE Congress on, Singapore,  pp. 4661-4667, 2007.

    [Foster08] I.Foster, Y. Zhao, I.Raicu, S. Lu,Cloud Computing and Grid Computing 360-Degree Compared, Grid Computing Environments Workshop, Austin ,TX , pp. 1-10, 2008.

    [Stanoevska10] K. Stanoevska, T. Wozniak, S. Ristol, Grid and Cloud Computing: A Business Perspective on Technology and Applications, Berlin, Springer-Verlag, 2010.

    [Armbrust09] M.Armbrust,  Above the Clouds – A Berkeley View of Cloud, California , Technical Report UCB/EECS-2009-28.

    [Bourbonnais04] S., Bourbonnais, V. M., Gogate, L. M., Haas, R. W., Horman, S., Malaika, I., Narang, V.,  Raman, Towards an information infrastructure for the grid, IBM Systems Journal, Vol. 43, pp. 665-688, 2004.

    [Foster01] I., Foster, C., Kesselman, The Anatomy of the Grid: Enabling Scalable Virtual Organization, International Journal of High Performance Computing Applications, Vol. 15, pp. 200-222, 2001.

    [Boden04] T., Boden, The Grid Enterprise — Structuring the Agile Business of the Future, Technology Journal, Vol. 21, pp. 107-117, 2004.

    [Goyal05] B., Goyal, S., Lawande, Grid Revolution: An Introduction to Enterprise Grid Computing, McGraw-Hill, 2005.

    [EUCALYPTUS-WEB]  Eucalyptus,http://www.eucalyptus.com.

    [Nurmi09] D. Nurmi, R. Wolski, C. Grzegorczyk, G. Obertelli, S. Soman, L. Youseff, and D. Zagorodnov,  “The Eucalyptus Open-Source Cloud-Computing System”,  In Proceedings of the 2009 9th IEEE/ACM International Symposium on Cluster Computing and the Grid (CCGRID 09), IEEE Computer Society, Washington, DC, USA, pp.124-131, 2009.

    [Zhu12] L. Zhu, Q. Li, L. He, Study on cloud computing resource scheduling strategy based on the ant colony optimization algorithm, International Journal of Computer Science Issues, Vol. 9 (5), pp. 54-58, 2012.

    [Chen09] W.  N. Chen, and J.  Zhang, An ant colony optimization approach to a grid workflow scheduling problem with various QoS requirements, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 39 (1), pp. 29-43.

    [Diargo96] M. Dorigo, V. Maniezzo, and A. Colorni, Ant system: optimization by a colony of cooperating agents, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 26 (1), pp. 29-41, 1996.

    [Le06] L. B. Lee, E. Hossain, and A. S. Alfa, Service

    [Eiben07]A. E., Eiben, J. E.,Smith, Introduction to Evolutionary Computing, Springer, 2007.

    [Larranaga99] P., Larranaga, C.M.H., Kuijpers, R. H., Murga, I., Inza, S., Dizdarevic, Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators. Artificial Intelligence Review, Vol. 13, pp. 129–170, 1999.

    [Sivanandam08] S. N. Sivanandam, S. N. Deepa, Introduction to Genetic Algorithms, New York ,Springer, 2008.

    [Javier07] Javier, C., Fatos, X., Ajith, A.: Genetic Algorithm Based Schedulers For Gird. IEEE, International Journal of innovative Computing, Information and Control 3 (December 2007)

    [Chang10] Y.H. Chang, Adopting co-evolution and constraint-satisfaction concept on genetic algorithms to solve supply chain network design problems, Expert Systems with Applications, vol. 37, pp. 6919–6930, 2010.

    [Michalewicz94] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Program, Spring-Verlag, 1994.

    [Beasley90] J., Beasley, OR-Library: Distributing test problems by electronic mail, Journal of the Operational Research Society, Vol. 41, pp. 1069–1072, 1990.

    [Muth63] J., Muth, G., Thompson, Industrial scheduling, Prentice-Hall, 1963.

    [Lawrence84] S., Lawrence, Resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques (Supplement). Pittsburgh, PA : Carnegie-Mellon University, 1984.

    [Storer92] R. H., Storer, S. D., Wu, R. Vaccari, New search spaces for sequencing problems with application to job shop scheduling, Management Science, Vol. 39, pp. 1495–1509, 1992.

     


تحقیق در مورد پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, مقاله در مورد پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, پروژه دانشجویی در مورد پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, پروپوزال در مورد پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, تز دکترا در مورد پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, تحقیقات دانشجویی درباره پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, مقالات دانشجویی درباره پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, پروژه درباره پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, گزارش سمینار در مورد پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, پروژه دانشجویی در مورد پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, تحقیق دانش آموزی در مورد پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, مقاله دانش آموزی در مورد پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری, رساله دکترا در مورد پایان نامه روش برنامه ریزی منابع ابر رایانه براساس الگوریتم رقابت استعماری

پایان نامه کارشناسی ارشد رشته مهندسی کامپیوتر چکیده: در سال های اخیر با توجه به رشد روز افزون درخواستها و پیوستن مشتریان جدید به دنیای محاسبات، سیستم های محاسباتی نیز باید تغییر کنند و قدرتمندتر وانعطاف پذیرتر از قبل عمل نمایند. در این میان محاسبات ابری به عنوان مدلی فراتر از یک سیستم ارائه شد که در حال حاضر توانایی پاسخگویی به اکثر درخواست ها و نیازمندی ها را دارد. راه حل های ...

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

پایان نامه جهت اخذ درجه کارشناسی ارشد رشته مهندسی کامپیوتر گرایش نرم افزار چکیده الگوریتم زمان بندی کار، که یک مسئله NP-کامل است، نقش کلیدی در سیستم ابرهای محاسباتی ایفا می کند. الگوریتم رقابت استعماری یکی از جدیدترین الگوریتم های بهینه سازی تکاملی است. همانگونه که از نام آن بر می آید، این الگوریتم بر مبنای مدل سازی فرایند اجتماعی- سیاسی پدیده استعمار بنا نهاده شده است. در این ...

پایان­ نامه کارشناسی ارشد در رشته­ مهندسی کامپیوتر (هوش مصنوعی) چکیده استخراج طبقه­ بند­های عام[1] و قابل فهم از داده، نقش مهمی در بسیاری از حوزه ­ها و مسائل است. تاکنون روش­های متعددی برای طبقه­بندی[2] و تشخیص الگو[3] معرفی شده ­است. یکی از شیوه­های موفق و منحصربه­فرد در حوزه طبقه­بندی و تشخیص الگوی داده­های ورودی، استفاده از تکنیک ­های فازی برای تقسیم­بندی نرم فضای ویژگی و ...

پايان نامه دوره کارشناسي ارشد در رشته علوم اقتصادي بهمن 1393 چکيده پيش­بيني از ابزارها و راهکارهاي مؤثر به منظور برنامه­ريزي و تدوين روش­هاي مالي است. دقت پيش­بيني از مهم­

دریافت درجه‌ی کارشناسی ارشد در رشته مهندسی برق گرایش الکترونیک چکیده مکانیزه کردن ادوات، یکی از مهم ترین و گسترده‌ترین زمینه‌هایی است که در فرآیندهای تولید استفاده می‌شود. با توجه به پیچیدگی و عدم اطمینان از فرآیندهای ماشین‌کاری، اخیراً تکنیک‌های محاسبات نرم[1] مبتنی بر مدل‌های فیزیکی برای پیش‌بینی عملکرد ماشینکاری فرآیندها و بهینه سازی آنها به روش‌های متداول ترجیح داده شده‌اند. ...

پایان نامه کارشناسی ارشد در رشته مهندسی اتوماسیون و ابزار دقیق چکیده ارائه روشی جدید در خوشه­بندی اطلاعات با استفاده ازترکیب الگوریتم خفاش و Fuzzy c-means خوشه­بندی قرار دادن داده­ها در گروه­هایی است که اعضای هر گروه از زاویه خاصی به هم شباهت دارند . شباهت بین داده­های درون هر خوشه حداکثر و شباهت بین داده­­های درون خوشه­های متفاوت حداقل می­باشد. Fuzzy c-means نیز یک تکنیک ...

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

پایان نامه جهت اخذ درجه کارشناسی ارشد M.Sc رشته سنجش از دور و سیستم اطلاعات جغرافیایی- منابع آب و خاک چکیده ازجمله مسائل مهم در مدیریت بحران حوادث غیرمترقبه طبیعی به ویژه زلزله، مکان یابی بهینه به منظور اسکان شهروندان در هنگام و یا پس از بروز حادثه می‌باشد. یکی از مشکلات بزرگ سازمان‌های درگیر در مدیریت بحران شهری، فقدان یک مدل مکانی جامع به منظور اعمال مدیریت واحد در انتقال ...

پایان نامه برای دریافت درجه کارشناسی ارشد(M.A) گرایش: ”استراتژیک" مقدمه امروزه لزوم برنامه ریزی مناسب به منظور برآورد صحیح از زمان و هزینه انجام پروژه و میزان منابع مورد نیاز در یک پروژه که تاثیر مستقیم بر اجرا، اداره و بهره برداری مناسب از پروژه هایی همانند احداث سد و ساختمان دارند، روشن است. در مجموع، مدیریت و برنامه ریزی فعالیت ها و منابع مورد نیاز در یک پروژه، نیازمندانجام ...

ثبت سفارش