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

بخشی از مقاله

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

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

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

1- مقدمه :

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

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

2- Simulated Annealing

1-2 . SA چيست؟

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

جستجوگرهاي هوشمند كاملاً متداول گرديده است. يكي از اين روش‌ها SA است. SA شباهت دارد با حرارت دادن جامدات. اين ايده ابتدا توسط شخصي كه در صنعت نشر فعاليت داشت به نام متروپليس در سال 1953 بيان شد.[10] وي تشبيه كرد كاغذ را به ماده‌اي كه از سرد كردن مواد بعد از حرارت دادن آنها بدست مي‌آيد. اگر يك جامد را حرارت دهيم و دماي آن را به نقطه ذوب برسانيم سپس آن را سرد كنيم جزئيات ساختماني آن به روش و نحوه سرد كردن آن وابسته مي‌شود. اگر آن جامد را به آرامي سرد كنيم كريستال‌هاي بزرگي خواهيم داشت كه مي‌توانند آن طور كه ما مي‌خواهيم فرم بگيرند ولي اگر سريع سرد كنيم آنچه كه مي‌خواهيم بدست نمي‌آيد.

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

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

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

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

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

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

3. برنامه سرد كردن :
پارامترهايي كه نحوه سرد كردن الگوريتم را مشخص مي‌كنند. بدين ترتيب كه دما چند وقت به چند وقت و به چه ميزان كاهش يابد و دماهاي شروع و پايان چقدر باشند. در سال 1982 كرك پاتريك ايده متروپليس را براي حل مسائل به كار برد. در سال 1983 كرك پاتريك و تعدادي از همكارانش از SA براي حل مسئله فروشنده دوره‌گرد يا TSP استفاده كردند. [8]
‍‍‍‌‌‌ روش بهينه‌سازي SA يك روش عددي با ساختار تصادفي هوشمند است. قابليت انعطاف در كوچك گرفتن طول گام‌هاي تصادفي در الگوريتمSA مانع از بروز هرگونه ناپايداري و ناهمگرايي در تركيب با مدل مي‌شود. علاوه بر آن توانايي SA در خروج از بهينه‌هاي محلي و همگرايي به سوي بهينه‌ي سراسري از جنبه‌ي نظري و در كاربردهاي عملي به اثبات رسيده است. به

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

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

(1)

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

(2)

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

حركت به جواب جديد در صورتي كه جواب جديد از جواب فعلي بهتر باشد و يا مقدار تابع احتمال حركت از يك عدد تصادفي از دامنه [0,1) بزرگ‌تر باشد انجام خواهد يافت. در غير اينصورت جستجوگر جواب جديد ديگري را توليد و ارزيابي خواهد نمود. اين حركت گام به گام تا رسيدن به شرط توقف الگوريتم ادامه مي‌يابد. يك مسئله‌ي مهم در الگوريتم پيشنهادي SA بررسي شرط تعادل و شرط توقف الگوريتم پيشنهادي است.

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

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

- برنامه سرد كردن :
قسمت هاي تشكيل دهنده برنامه سرد كردن عبارتند از:
1. درجه حرارت آغازي
2. درجه حرارت پاياني
3. كاهش درجه حرارت در هر مرحله
4. تكرار در هر درجه حرارت

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

پيشنهاد شده (rayward_smith) شروع كنيم با يك درجه حرارت زياد و گرم كنيم آن را به سرعت تا زماني كه 60% از راه‌حل‌هاي بد پذيرفته شوند و بعد خيلي آهسته سرد كنيم. در اين روش درجه حرارت آغازين واقعي بدست مي‌آيد.[13]

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

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

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

تجربه نشان مي دهد با يد بين 0.8 تا 0.99 باشد تا بهترين نتيجه بدست آيد و الگوريتم طولاني نشود.

تكرار در هر دما:
رابطه اي كه استفاده مي شود عبارت است از :

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

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

2-2 اجرای تابع با استفاده از SA:
برای بدست آوردن بهترین مینیمم تابع از روش sa استفاده میکنیم . ابتدا الگوریتم را با حلقه 1000 اجرا می کنیم یعنی 1000 بار ورودی را تغییر می دهیم تا بهترین خروجی را بدست آوریم در این مرحله خروجی برابر با 0.25- می شود . بار دیگر الگوریتم را با حلقه 2000 اجرا می کنیم که خروجی مجددا برابر با 0.25- می شود ابته وقتی الگوریتم با حلقه 2000 را 10 بار اجرا کردیم خروجی هر بار 0.25- می شود ولی برای الگوریتم با حلقه 1000 چنین نیست . بنابر این می توان گفت الگوریتم فوق تا حدود زیادی قابل اعتماد است اما نه به طور کامل .

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

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

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

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

3- رسم تابع :

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