مقاله نرم افزار Fault Tolerance با استفاده از Simulated Annealing

توجه : به همراه فایل word این محصول فایل پاورپوینت (PowerPoint) و اسلاید های آن به صورت هدیه ارائه خواهد شد

  مقاله نرم افزار Fault Tolerance با استفاده از Simulated Annealing دارای ۲۱ صفحه می باشد و دارای تنظیمات در microsoft word می باشد و آماده پرینت یا چاپ است

فایل ورد مقاله نرم افزار Fault Tolerance با استفاده از Simulated Annealing  کاملا فرمت بندی و تنظیم شده در استاندارد دانشگاه  و مراکز دولتی می باشد.

توجه : در صورت  مشاهده  بهم ریختگی احتمالی در متون زیر ،دلیل ان کپی کردن این مطالب از داخل فایل ورد می باشد و در فایل اصلی مقاله نرم افزار Fault Tolerance با استفاده از Simulated Annealing،به هیچ وجه بهم ریختگی وجود ندارد

بخشی از متن مقاله نرم افزار Fault Tolerance با استفاده از Simulated Annealing :

نرم افزار Fault Tolerance با استفاده از Simulated Annealing

چکیده :
در این مقاله سعی می کنیم بهترین مینیمم را برای تابع زیر بدست بیاوریم :

برای این منظور از روش simulated Annealing (SA) استفاده می کنیم .
SA یکی از روشهای بهینه سازی حل مسئله است که در واقع الهام گرفته شده از فرایند ذوب و دوباره سرد کردن مواد می باشد و به همین دلیل به شبیه سازی حرارتی شهرت یافته است .
پس از حل مسئله با روش SA سعی می کنیم آنرا در یک نرم افزار تحمل خطا به کار ببریم برای داشتن یک نرم افزار تحمل خطا تکنیکهای مختلفی وجود دارد که ما در این مقاله با استفاده از تکنیک های انزرنگی و تنوع طراحی از روش Acceptance Voting (AV) بهره برده ایم .

۱- مقدمه :

۱-۱- Fault: باعث errorدر سیستم می شود که به آنbug هم گفته می شود .
Error : حالتی از سیستم است که منتج به خرابی می شود .
Failure : حالتی است که سیستم از سرویس مورد نظر منحرف شود .
۲-۱ تحمل خطا (Fault Tolerance):

تحمل خطا یک پروسه یعنی مجموعه ای از فعالیت هاست که هدف آن حذف خطا است یا اگر نتوانست خطا را حذف کند ، لااقل تاثیراتش را کم کند .
۳-۱ سیستم تحمل پذیر خطا (System Fault Tolerance ) :
سیتم تحمل پذیر خطا معادل با سیستم قابل اعتماد ( Dependable ) می باشد که باید ویژگی های (قابلیت دسترسی ، قابلیت اعتماد ، ایمنی و قابلیت نگهداری را داشته باشد .
۴-۱ افزونگی ( Redundancy):
یکی از روشهای تحمل خطا در سیستم های نرم افزاری افزونگی است . افزونگی قابلیتی است در تحمل خطا بطوریکه می توان با افزایش سخت افزار و یا کپی برداری از تمام نرم افزار و یا قسمتی از نرم افزار و یا کپی برداری از data تحل خطا را در سیستم تضمین کرد .
۵-۱ تنوع طراحی (Design Diversity) :
برای تولید یک سیستم تحمل پذیر خطا می توان یک نرم افزار را به شرکت های مختلف برنامه نویسی داد تا برنامه را بنویسد و برای تولید نتیجه نهایی نیز می توان از الگوریتم voting استفاده کرد پس باید از این نرم افزار طراحی های مختلف داشته باشیم . روشهایی که از تکنیک تنوع طراحی استفاده می کنند عبارتند از:
RCB-NVP-NSCP-CRB-AV

۲- Simulated Annealing

۱-۲ . SA چیست؟

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

جستجوگرهای هوشمند کاملاً متداول گردیده است. یکی از این روش‌ها SA است. SA شباهت دارد با حرارت دادن جامدات. این ایده ابتدا توسط شخصی که در صنعت نشر فعالیت داشت به نام متروپلیس در سال ۱۹۵۳ بیان شد.[۱۰] وی تشبیه کرد کاغذ را به ماده‌ای که از سرد کردن مواد بعد از حرارت دادن آنها بدست می‌آید. اگر یک جامد را حرارت دهیم و دمای آن را به نقطه ذوب برسانیم سپس آن را سرد کنیم جزئیات ساختمانی آن به روش و نحوه سرد کردن آن وابسته می‌شود. اگر آن جامد را به آرامی سرد کنیم کریستال‌های بزرگی خواهیم داشت که می‌توانند آن طور که ما می‌خواهیم فرم بگیرند ولی اگر سریع سرد کنیم آنچه که می‌خواهیم بدست نمی‌آید.

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

P:احتمال پذیرش نقطه بعدی
C: یک پارامتر کنترلی
تغییر هزینه

پارامتر کنترل در شبیه‌سازی آب دادن فولاد، همان نقش دما را در پدیده فیزیکی ایفا می‌کند. ابتدا ذره (که نمایش دهنده نقطه فعلی در فضای جستجو است) با مقدار انرژی بسیار زیادی (که نشان دهنده مقدار بالای پارامتر کنترلی C است) نشان داده شده است. این انرژی زیاد به ذره اجازه فرار از یک کمینه محلی را می‌دهد. همچنانکه جستجو ادامه می‌یابد، انرژی ذره کاهش می‌یابد (C کم می‌شود) و در نهایت جستجو به کمینه کلی میل خواهد نمود. البته باید توجه داشت که در دمای پایین امکان فرار الگوریتم از کمینه محلی کاهش می‌یابد، به همین دلیل هر چه انرژی آغازین بالاتر، امکان رسیدن به کمینه کلی هم بیشتر است .[۱۰]

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

نقطه‌ای در فضای جستجو است که جستجو را از آنجا آغاز می‌کنیم. این نقطه معمولاً به صورت تصادفی انتخاب می شود .

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

۳ برنامه سرد کردن :
پارامترهایی که نحوه سرد کردن الگوریتم را مشخص می‌کنند. بدین ترتیب که دما چند وقت به چند وقت و به چه میزان کاهش یابد و دماهای شروع و پایان چقدر باشند. در سال ۱۹۸۲ کرک پاتریک ایده متروپلیس را برای حل مسائل به کار برد. در سال ۱۹۸۳ کرک پاتریک و تعدادی از همکارانش از SA برای حل مسئله فروشنده دوره‌گرد یا TSP استفاده کردند. [۸]
‍‍‍‌‌‌ روش بهینه‌سازی SA یک روش عددی با ساختار تصادفی هوشمند است. قابلیت انعطاف در کوچک گرفتن طول گام‌های تصادفی در الگوریتمSA مانع از بروز هرگونه ناپایداری و ناهمگرایی در ترکیب با مدل می‌شود. علاوه بر آن توانایی SA در خروج از بهینه‌های محلی و همگرایی به سوی بهینه‌ی سراسری از جنبه‌ی نظری و در کاربردهای عملی به اثبات رسیده است. به

طور مثال روش SA در بهینه‌سازی بهره‌برداری کانال‌های آبیاری در کشاورزی از الگوریتم ژنتیک مدل بهینه‌تری را می‌دهد. بهینه‌سازی توابع غیرصریح و مسائل Non-Complete با روش‌های کلاسیک بهینه‌سازی دشوار و گاهی غیرممکن است و بایستی از روش‌های عددی بهینه‌سازی استفاده کرد. برای حل مسئله به روش SA ابتدا مدل‌سازی ریاضی صورت می‌گیرد. [۵]

– معیار پذیرش (یک حرکت)
در الگوریتم‌های بهینه‌سازی محلی، جواب جدید تنها در صورت بهبود تابع هدف پذیرفته می‌شود. این در حالیست که در SA نه تنها جوابی که باعث بهبود تابع هدف می‌شود پذیرفته می‌شود بلکه جواب‌های نامناسب نیز بطور احتمالی پذیرفته می‌شوند. یک قانون ترمودینامیک، راجع به رابطه‌ی درجه حرارت (t) توضیح می‌دهد و احتمال افزایش اندازه‌ی انرژی ( )‌، این قانون بصورت زیر است:

(۱)

که در آن K مقداری ثابت است که به آن ثابت بولتزمان گفته می‌شود. با استفاده از این قانون ترمودینامیک، احتمال پذیرفته شدن حرکت بد توسط رابطه‌ی زیر محاسبه می‌شود:

(۲)

که در اینجا:
: تغییر در تابع ارزیابی
t: درجه حرارت
r: یک عدد تصادفی بین صفر و یک
p: احتمال حرکت به جواب جدید

حرکت به جواب جدید در صورتی که جواب جدید از جواب فعلی بهتر باشد و یا مقدار تابع احتمال حرکت از یک عدد تصادفی از دامنه [۰,۱) بزرگ‌تر باشد انجام خواهد یافت. در غیر اینصورت جستجوگر جواب جدید دیگری را تولید و ارزیابی خواهد نمود. این حرکت گام به گام تا رسیدن به شرط توقف الگوریتم ادامه می‌یابد. یک مسئله‌ی مهم در الگوریتم پیشنهادی SA بررسی شرط تعادل و شرط توقف الگوریتم پیشنهادی است.

شرط تعادل:
بطور کلی در روش SA، تعداد جواب پذیرفته شده و یا تعداد کل جواب تولید شده در هر درجه حرارت به عنوان مبنایی برای بررسی شرط تعادل در آن درجه حرارت منظور می‌شود. به تعداد تعویض‌ها در هر درجه حرارت جهت بررسی شرط تعادل، “دوره” گغته می‌شود. این تعداد به عنوان پارامتر الگوی SA است که باید تعیین گردد.

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

– برنامه سرد کردن :
قسمت های تشکیل دهنده برنامه سرد کردن عبارتند از:
۱ درجه حرارت آغازی
۲ درجه حرارت پایانی
۳ کاهش درجه حرارت در هر مرحله
۴ تکرار در هر درجه حرارت

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

پیشنهاد شده (rayward_smith) شروع کنیم با یک درجه حرارت زیاد و گرم کنیم آن را به سرعت تا زمانی که ۶۰% از راه‌حل‌های بد پذیرفته شوند و بعد خیلی آهسته سرد کنیم. در این روش درجه حرارت آغازین واقعی بدست می‌آید.[۱۳]

یک ایده ی مشابه، پیشنهاد شده (Dowsland)، هست به سرعت گرم کردن سیستم تا زمانی که نسبت دقیقی از راه‌حل‌های بد پذیرفته شوند و بعد سرد کردن آهسته می‌تواند شروع شود.[۵] این مشابه آنچه در حرارت فیزیکی انجام می‌شود است، یعنی مواد گرم می‌شوند تا زمانی که مایع (ذوب) شوند و بعد سرد می‌شوند. باید توجه کرد زمانی که مواد مایع شدند گرما دادن بیشتر بیهوده است.

درجه حرارت پایانی:
معمولاً اجازه داده می‌شود درجه حرارت کاهش یابد تا زمانی که به صفر برسد. همچنین معیار توقف می‌تواند یک درجه حرارت پایین مناسب باشد.

کاهش درجه حرارت در هر مرحله:
معمولاً می‌توان با یک رابطه خطی ساده (یک تناوب هندسی) کاهش دما را بدست آورد:

تجربه نشان می دهد با ید بین ۰۸ تا ۰۹۹ باشد تا بهترین نتیجه بدست آید و الگوریتم طولانی نشود.

تکرار در هر دما:
رابطه ای که استفاده می شود عبارت است از :

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

تابع هزینه :
ره‌آورد حل یک مسئله باید روشهایی برای اندازه گیری کیفیت آن روش باشد. تابع هزینه معمولاً پیچیده است و با نمایش داده می‌شود:
: ارزیابی تفاوت بین راه‌حل جاری و راه‌حل مجاور
همسایگی :
وقتی راجع به یک مسئله فکر می‌کنید ، ابتدا به دنبال این هستید که چگونه از یک حالت می‌توان به حالت دیگر رفت. اگر هر حالت را یک NODE از یک گراف فرض کنیم همسایگی‌های مشخصی خواهیم داشت. در SA باید همسایگی‌ها را طوری انتخاب کرد که تا حد ممکن همگرایی مسئله برای رسیدن به جواب حفظ شود.
روش‌های جابجایی در همسایگی:
۱جابجایی جهت‌دار(DIS):
اگر همسایگی ها را به صورت یک آرایه فرض کنیم،اولین و آخرین خانه‌ی آرایه با مجاورش تعویض می‌شود و اگر از خانه های میانی باشد با هر کدام از دو خانه ی مجاورش که مناسب‌تر است.
۲جابجایی تصادفی(RIS):
دو خانه از آرایه بطور تصادفی انتخاب و باهم تعویض می‌شوند.
۳جابجایی مجاور(AIS):
مشابه DIS است با این تفاوت که از دو خانه مجاور،به صورت تصادفی یکی انتخاب می‌شود.

۲-۲ اجرای تابع با استفاده از SA:
برای بدست آوردن بهترین مینیمم تابع از روش sa استفاده میکنیم . ابتدا الگوریتم را با حلقه ۱۰۰۰ اجرا می کنیم یعنی ۱۰۰۰ بار ورودی را تغییر می دهیم تا بهترین خروجی را بدست آوریم در این مرحله خروجی برابر با ۰۲۵- می شود . بار دیگر الگوریتم را با حلقه ۲۰۰۰ اجرا می کنیم که خروجی مجددا برابر با ۰۲۵- می شود ابته وقتی الگوریتم با حلقه ۲۰۰۰ را ۱۰ بار اجرا کردیم خروجی هر بار ۰۲۵- می شود ولی برای الگوریتم با حلقه ۱۰۰۰ چنین نیست . بنابر این می توان گفت الگوریتم فوق تا حدود زیادی قابل اعتماد است اما نه به طور کامل .

*خروجی ۵۰ بار اجرای الگوریتم با حلقه ۱۰۰۰ و T=T*0/9 و با تغییر یک متغیر به طور تصادفی:

*خروجی اجرای الگوریتم با حلقه ۱۰۰۰ و T=T*0.9 و با تغییر ۵ متغیر بطور تصادفی در هر اجرای حلقه :

• خروجی ۵۰ بار اجرای الگوریتم با حلقه ۱۰۰۰ و T=T*0.98 و با تغییر یک متغیر به طور تصادفی در هر اجرای حلقه :

• خروجی ۵۰ بار اجرای الگوریتم با حلقه ۱۰۰۰ و T=T*0.5 و با تغییر دو متغییر بطور تصادفی در هر اجرای حلقه :
*خروجی ۵۰ بار اجرای الگوریتم با حلقه ۱۰۰۰ و T = 1 و با تغییر دو متغییر بطور تصادفی در هر اجرای حلقه :

۳- رسم تابع :

اگر بخواهیم این تابع را در matlab رسم کنیم به دلیل اینکه تابع ۱۰ بعدی می شود نمی توان به راحتی آن را رسم کرد بنابراین کاری که انجام دادیم این بود که از روش ساده سازی و تغییر و متغیر استفاده کردیم و در نهایت به یک تابع سهمی درجه ۲ رسیدیم که رسم این تابع در matlab بسیار ساده است :