نتایج آزمایشها بهکارگیری RASA در زمانبندی وظایف مستقل حاکی از این است که قابلیت اجرای RASA در به دست آوردن زمانبندی با مدتزمان اجرای کمتر بهطور قیاسی خوب است و نسبت به الگوریتمهای موجود در سیستمهای توزیعشده مقیاس بزرگ، قدم را فراتر نهاده است.
۲-۹-۱۳ الگوریتم ژنتیک جلو رونده (LAGA[38])
LAGA از اعتبار RD[39]، برای بهینهسازی زمان اجرا و قابلیت اطمینان برنامه کاربردی گردشکاری استفاده میکند. اعتبار RD، اعتباری مبتنی بر قابلیت اطمینان و وابسته به زمان است که میتواند بهطور مؤثری جهت ارزیابی قابلیت اطمینان منبع در سیستمهای توزیعشده، استفاده شود.
( اینجا فقط تکه ای از متن فایل پایان نامه درج شده است. برای خرید متن کامل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. )
GA میتواند چندین راهحل رضایتبخش را برای زمانبندی ارائه دهد. تعداد خیلی کمی از GA های پیشنهادی قادرند همزمان اجرا و هم قابلیت اطمینان برنامه کاربردی گردشکاری را بهینه کنند. این به علت مشکل بودن نگهداری وابستگی بین وظایف است. BGA[40] تنها موردی است که در این رابطه میشناسیم، اما BGA ممکن است راه حل هایی را ارائه دهد که وابستگی بین وظایف را نقص میکند. LAGA قادر است از مسئله راه حل های نامعتبری که BGA پیش میآید جلوگیری کند.BGA، تنها GA موجودی است که همزمان اجرا و هم قابلیت اطمینان را برای برنامههای کاربردی گردش کاری بهینه میکند. بااینحال ممکن است، BGA راه حل های نامعتبری را ارائه دهد که وابستگی بین وظایف را نقص میکند.
LAGA دارای دو ویژگی است:
۱-الگوریتم ژنتیک را توسط یک عملگر جهشی جدید بر اساس ابتکار اولویت منبع پیشنهادشده بهینه میکند.
۲- از یک مکانیزم ارزیابی و اکتشافی جدید استفاده میکند.
جهت داشتن زمانبندی مطمئن، دو موضوع مهم باید بررسی شود:
چگونه قابلیت اطمینان یک منبع را ارزیابی کنیم؟
چگونه زمانبندی مطمئن را بر اساس اطلاعات قابلیت اطمینان منابع اجرا کنیم؟
در کارهای قبلی بهمنظور ارزیابی قابلیت اطمینان منابع، از سیستمهای اعتبار قدیمی برای نگهداری قابلیت اطمینان منابع در زمانبندیهایشان استفاده میکردند که این کار دو مشکل داشت: اول اینکه از دید منبع، اغلب مدلهای اعتباری فقط اعتبار یک منبع را بر اساس نرخی که وظایف با موفقیت کامل میشوند ارزیابی میکند، آنها تأثیر حالت و مدتزمان اجرا (سایز) وظیفه را بررسی نمیکردند (مثلاً بین A و B)،A نرخ شکست بالاتری دارد اما چون تعداد وظایف بیشتری که سایز زمان اجرای کمتری دارند را تکمیل میکند، A اعتبار بیشتری را دارد که این غلط است و دوم اینکه، از دید وظیفه، مدلهای اعتباری موجود قابلیت اطمینان یکسانی را به تمام وظایف روی یک منبع بر اساس اعتبار آن منبع اختصاص میدهند، درصورتیکه یک وظیفه طولانیتر که روی یک منبع غیرمطمئن اجرا میشود، احتمال موفقیت کمتری را باید داشته باشد. قابلیت اطمینان منبع میتواند توسط اعتباری نظارت شود که میتواند به عنوان احتمالی که منبع قادر است بهرهبرداری مورد انتظار سرویس را ارائه دهد، تعریف شود.
در LAGA، اعتبار RD، سایز وظایف در زمان اجرا را با بهره گرفتن از نرخ شکست وظیفه (شکستهای وظیفه در واحد زمان) بررسی میکند تا مقدار اعتبار RD را مشخص کند، همچنین یک اعتبار بلادرنگ را نیز فراهم میکند که میتواند آن را برای ارزیابی قابلیت اطمینان هر وظیفه بهطور مستقیم با بهره گرفتن از مدل شکستنمایی، به کار برد.
اعتبار RD وابسته به زمان است و الگوریتم محاسبه اعتبار RD قادر است نرخ شکست بلادرنگ را برای یک منبع ارزیابی کند.
LAGA اجرای وظایف را به عنوان یکراه حل مناسب با بهره گرفتن از استراتژی Max-Min (ماکزیمم کردن قابلیت اطمینان- مینیمم کردن زمان اجرای برنامه کاربردی) ضمانت میدهد. الگوریتم راه حل های متناقض را نمیرود، درواقع یک مکانیسم ارزیابی جدیدی را ارائه میدهد که قادر است بهطور هوشمندانهتر روند کاری را سرعت بخشد، برای ماکزیمم کردن قابلیت اطمینان باید فاکتور شکست را مینیمم شود.
LAGA میزان شکست یک منبع را پیشبینی میکند و تأثیر زمان را در نظر میگیرد، ازاینرو یک اعتبار وابسته به زمان مبتنی بر قابلیت اطمینان را تعریف میکند که مستقیماً به نرخ شکست مربوط میشود. LAGA شامل مراحل رمزگذاری، تقاطع، جهش، ارزیابی، انتخاب کردن است. اجرای وظیفه در مرحله ارزیابی انجام میشود، درحالیکه در GA ها معمولاً در مراحل تقاطع و جهش انجام میشود. این الگوریتم، GA معمولی را توسط یک عملگر جهش جدید که بر اساس اکتشاف اولویت منبع پیشنهادشده میباشد، بهینه میکند.LAGA از یک مکانیسم ارزیابی و تحول جدیدی استفاده میکند، اجرای وظیفه در مرحله ارزیابی کردن با بهره گرفتن از استراتژی Max-Min، بر اساس اکتشاف اولویت وظیفه تعریفشده انجام میشود. LAGA از مکانیسم ارزیابی و تحول جدیدی استفاده میکند که:
عملگرهای تحول نگاشت دادن وظیفه- منبع یکراه حل زمانبندی را استنتاج میکنند.
مرحله ارزیابی وظیفه را به عنوان دستهای از راه حل ها با بهره گرفتن از استراتژی Max-Min پیشنهادشده اما تعیین میکند که استراتژی دوفازی است که میتواند با GA ها کار کند.
درواقع LAGA مسئله زمانبندی مبتنی بر قابلیت اطمینان در محیطهای محاسباتی توزیعشده (مثل ابرها) را، توسط مطرح کردن اعتبار RD که وابسته به زمان است و برای ارزیابی قابلیت اطمینان منبع به کار میرود بررسی میکند. اعتبار RD از نرخ شکست استفاده میکند تا اعتبار منبع را مشخص کند، بنابراین میتواند برای ارزیابی قابلیت اطمینان یک وظیفه بهطور مستقیم با بهره گرفتن از مدل شکست نمایی استفاده شود.الگوریتم محاسبه اعتبار RD میتواند تغییرات بلادرنگ اعتبار را بهطور پویا نظارت کند. بر اساس این اعتبار RD، الگوریتم LAGA پیشنهاد شد تا زمان اجرا و قابلیت اطمینان برنامههای کاربردی گردشکاری را بهطور هوشمندانه بهینه کند.نتایج نشان میدهد که اعتبار RD قابلیت اطمینان یک برنامه کاربردی را با اعتبارات دقیقتر بهبود میبخشد، درحالیکه LAGA راه حل های بهتری را نسبت به لیست اکتشافات موجود فراهم میکند و راه حل های بهتر را سریعتر از GA قدیمی استنتاج میکند.اعتبار RD از نرخ شکست استفاده میکند تا اعتبار منبعی را تعریف کند که میتواند برای ارزیابی قابلیت اطمینان یک وظیفه با مدل شکست نمایی استفاده شود. الگوریتم محاسبه اعتبار RD میتواند تغییرات بلادرنگ اعتبار را بهطور پویا نظارت کند. سپس بر اساس اعتبار RD، الگوریتم LAGA را برای بهینهسازی مدتزمان اجرا و قابلیت اطمینان برنامههای کاربردی را بهطور هوشمندانه پیشنهاددهیم.
فصل سوم
روش اجرای تحقیق
در این فصل الگوریتمهای تکاملی ژنتیک، ازدحام ذرات و رقابت استعماری و مزایا و معایب آنها موردبحث قرار میگیرند. همچنین روشی برای ترکیب آنها بر پایه الگوریتم رقابت استعماری ارائه میشود.
۳- ۱ الگوریتم ژنتیک
۳-۱-۱ مقدمه
از الگوریتم ژنتیک در روشهای بهینهسازی و حل مسائل استفاده میشود. الگوریتم ژنتیک زیرمجموعهای از محاسبات تکاملیافته (هوش مصنوعی) است که از قوانین تکامل بیولوژیک طبیعی تقلید میکند. الگوریتم ژنتیک، قانون بقای بهترین را اعمال میکند. در هر نسل به کمک فرایند انتخابی متناسب باارزش جوابها و تولیدمثل جوابهای انتخابشده (با کمک گرفتن از عملگرهایی که از ژنتیک طبیعی تقلید میکنند), تقریبهای بهتری از جواب نهایی به دست میآید. این فرایند سازگاری نسلهای جدید با شرایط مسئله را ممکن میسازد.
۳-۱-۲ تاریخچه
برای اولین بار تحقیقی درباره استراتژی تکامل توسط ریچنبرگ در سال ۱۹۶۰ ارائه شد و چندین سال نظریه او توسط پژوهشگران متعددی موردبررسی قرار گرفت و سرانجام آقای جان هولاند در سال ۱۹۷۵ الگوریتم ژنتیک را ارائه داد.
آقای جان کوزا، برای روند الگوریتم ژنتیک (GA) یکزبان برنامهنویسی ابداع کرد که همان برنامهنویسی ژنتیک (GP) میباشد و نرمافزاری که توسط او ابداع شد نرمافزار LISP مینامند.
۳-۱-۳ تاریخچه بیولوژیکی
بدن هر موجود زنده از سلول، هر سلول از کروموزوم و کروموزوم نیز از رشتههای DNA تشکیلشده است. کروموزوم نیز از ژن تشکیل یافته است. به هرکدام از بلوکهای DNA یک ژن میگویند و به مجموعهی ژنها نیز یک ژنوم (Genome) میگویند.
۳-۲ ساختار و اجزای الگوریتم ژنتیک
الگوریتمهای ژنتیک دارای اجزای ذیل میباشند:
۳-۲-۱ کروموزوم[۴۱]
در الگوریتمهای ژنتیک، کروموزومها نشاندهندهی یک نقطه در فضایی که جستجو در آن انجام میگیرد و همچنین یکراه حل برای مسئله میباشند. کروموزومها یا همان (راه حل ها), از تعداد ثابتی ژن[۴۲] که (متغیرهای موردنظر) تشکیل میشوند. برای نمایش دادن کروموزومها، عموماً از کدگذاری دودویی (رشته بیتی) استفاده میشود.
۳-۲-۲ جمعیت[۴۳]
در استفاده از این الگوریتم مجموعهای از کروموزومها، تشکیلدهندهی یک جمعیت میباشند که با تأثیر عملگرهای ژنتیکی روی هر جمعیتی، جمعیت جدید (با همان تعداد کروموزوم) تشکیل میشود.
۳-۲-۳ تابع برازندگی[۴۴]
برای حل هر مسئلهای با کمک از الگوریتم ژنتیک، اول یک تابع برازندگی تولید میگردد که برای هر کروموزوم، این تابع یک عدد غیر منفی را بازمیگرداند و این عدد بیانگر شایستگی آن کروموزوم است.
۳-۳ عملگرهای الگوریتم ژنتیک
عملگرهای ژنتیکی که شامل عملگر انتخاب[۴۵], آمیزش[۴۶] و جهش[۴۷] میباشند بهطورمعمول بیشترین کاربرد را در الگوریتم ژنتیک دارند. با تأثیر این عملگرها بر روی یک جمعیت، نسل[۴۸] بعدی آن جمعیت تولید میشود.
۳-۳-۱ عملگر انتخاب (Selection):
از بین کروموزومهایی که در یک جمعیت قراردادند کروموزومهای برازندهتری که شانس بیشتری برای تولیدمثل دارند انتخاب میکند.
روشهای انتخاب:
انتخاب نخبگان ((Elitist Selection:
با بهره گرفتن از مقدار شایستگی که از طریق تابع ارزیاب دریافت شده است مناسبترین و بهترین عضو هر اجتماعی را انتخاب میکند.
نمونهبرداری با بهره گرفتن از روش چرخ رولت:
به هر فرد در جمعیت موردنظر، یک قطعهای از چرخ را تخصیص میدهیم که اندازه آن متناسب با شایستگی فرد میباشد. چرخ N (تعداد افراد در جمعیت) بار چرخیده میشود و در هر بار چرخیدن آن، فرد زیر نشانگر چرخ انتخاب میشود و به عنوان والدین نسل بعدی در مخزن قرار داده میشود. پیادهسازی آن بهصورت ذیل میباشد:
ابتدا نرخ انتظار کل افرادی که در جمعیت قرار دارند را جمع نمایید و سپس جواب آن را T نامگذاری نمایید.
مراحل ذیل را به تعداد N بار تکرار نمایید:
ابتدا یک عدد تصادفی ® بین ۰ و T انتخاب نمایید سپس در بین افراد یک جمعیت نرخهای انتظار (مقدار شایستگی) را باهم جمع کنید تا زمانی که مجموع آن بزرگتر مساوی با R گردد آنگاه، فردی که نرخ انتظارش سبب بیشتر شدن جمع از حد موزد نظر میشود، به عنوان فرد برگزیده انتخاب میکنیم.
شکل ۳-۱ چرخ رولت و روش ارزیابی در آن [۱۳]