بخشی از مقاله


نرم افزار 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 ) می باشد که باید ویژگی های (قابلیت دسترسی ، قابلیت اعتماد ، ایمنی و قابلیت نگهداری را داشته باشد :
- قابلیت دسترسی: سيستم در هر لحظه آماده استفاده باشد .
- قابلیت اعتماد: سيستم پيوسته و بدون عيب کار کند .
- ایمنی: وقتي سيستم fail مي شود اتفاق فاجعه آميزي رخ ندهد .
- قابلیت نگهداری: سيستم شدهfail به راحتي قابل ترميم باشد.


4-1- افزونگی ( Redundancy):
یکی از روشهای تحمل خطا در سیستم های نرم افزاری افزونگی است . افزونگی ، قابلیتی است در تحمل خطا به طوری که می توان با افزایش سخت افزار و یا کپی برداری از تمام نرم افزار و یا قسمتی از نرم افزار و یا کپی برداری از data تحل خطا را در سیستم تضمین کرد .
5-1- تنوع طراحی (Design Diversity) :
برای تولید یک سیستم تحمل پذیر خطا می توان یک نرم افزار را به شرکت های مختلف برنامه نویسی داد تا برنامه را بنویسد و برای تولید نتیجه نهایی نیز می توان از الگوریتم voting استفاده کرد پس باید از يك نرم افزار طراحی های مختلف داشته باشیم .


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

1-5-1- Recovery Blocks(RCB)
یک تکنیک تحمل خطای نرم افزاری تنوع طراحی است. یک روش دینامیک است و ازیک AT(Acceptanc test) استفاده می کند. از افزونگی نرم افزاری استفاده میکند یعنی در اینجا ما از نرم افزار چندین گپی داریم از AT برای تست شرط استفاده می کند که آیا شرط برقرار شده است یا نه، اگربرقرار بود که خروجی تولید می شود و گرنهback ward Recovery انجام می دهد و Alternate بعدی کار را انجام می دهد و اگر هیچ یک از نتایج Alternate ها پاس نشد یک خطا اتفاق می افتد.


2-5-1- N- version programming(NVP):
از تکینیک های اصلی تنوع طراحی نرم افزاری است یک روش استاتیک است یعنی تمامtask هایی که قرار است به عنوان variant ها عمل کند تا خروجی تولید شود مشخص اند. از روش Forward Recoveryاستفاده می کند. پایه عملیات آن به این صورت است که n تا نسخه همزمان اجرا می شود و یک مکانیزم تصمیم گیری روی نتایج ورژن ها اعمال می کنیم اگر توانستیم به تصمیم جامعی برسیم که نتیجه برگردانده می شود و گرنه یک exception اتفاق می افتد.

3-5-1- : N self– Checking programming(NSCP)
با استفاده از NSCP با داشتن افزونگی نرم افزاری می خواهیم رفتار برنامه ها را که همزمان می شوند را چک کنیم ،در این روش از یک مقایسه کنند. که نقش اساسی در تصمیم گیری داردیعنی وظیفه اش این است که نتایج variant ویک الگوریتم مقایسه ای یکAT برای هرحقیقت سخت افزار تشکیل می شود که با افزایش سخت افزارها این موارد نیز افزایش
می یابند.
N در NSCP همیشه زوج است و نشان دهنده تعداد variant هاست جفت ها همزمان اجرا می شوند. درNSCP زمانی خطا اتفاقی می افتد که یا نتایج جفت ها با هم موافق نباشد ویا نتایج تولید شده بوسیله جفت های موافق باهم متفاوت باشند.


4-5-1-روش (Consen sus Recovery Block (CRB
این تکنیک ترکیبی از RCB , NVP است . این روش باعث می شود تا اهمیتATدرRB را کم کند. در این روش n ورژن از برنامه را با اولویت گذاری دادیم که این اولویت ها براساس سرویسشان و میزان قابلیت اعتمادشان است .دراین تکنیک ابتدا n تا ورژن به روش NVP همزمان اجرا می شوند و نتیجه شان بوسیله voter بررسی می شود. اگرvoter نتیجه نهایی را بتواند تولید کند کار تمام می شود و گرنه نتیجه variantها بر اساس بیشترین اولویت به AT فرستاده می شود .

run Ranked Variant 1, Ranked Variant 2, ..., Ranked Variant n
if (Decision Mechanism (Result 1, Result 2, ..., Result n) )
return Result else
ensure Acceptance Test
by Ranked Variant 1 [Result]
else by Ranked Variant 2 [Result]
else by Ranked Variant n [Result]
else raise failure exception return Result



5-5-1- Acceptance voting (AV) :

AV یکی از روشهای مهم از تکنیک تنوع طراحی می باشد . در این روش ما می توانیم از یک نرم افزار ، نسخه های مختلفی داشته باشیم که به هر یک از آنها یک variant گفته
می شود .
این روش هم از (Acceptance Test) AT و هم از voting استفاده می کند .
در اینجا ابتدا تمام variant ها به صورت موازی اجرا می شود خروجی هر یک از آنها وارد یک AT می شود . ATخروجی را بررسی می کند تا آن را به voterپاس دهد .
voterدر این روش یک voter کاملا دینامیک است ؛ یعنی voter از یک الگوریتم رای گیری دینامیک استفاده می کند ؛ یعنی اگر تعداد خروجی هايی که توسط AT به آن پاس داده می شود کمتر از N (تعداد variant ها ) باشد نیز میتواند جواب نهایی را تولید کند یعنیvoter تعداد خروجی های پاس داده شده به وسیله AT به voter می تواند K باشد که N 1≤K < است . به این ترتیب اگر یکی از variant ها نیز نتوانست پاسخ درست را تولید کند ، الگوریتم با استفاده از خروجی بقیه variant ها می تواند خروجی صحیح را تولید کند . در این تکنیک زمانی سیستم Fail می شود که هیچ خروجی به voter پاس داده نشود و یا voter دینامیک نتواند یک خروجی صحیح را انتخاب کند .

run Variant 1, Variant 2, ..., Variant n
ensure Acceptance Test 1 by Variant 1 ensure Acceptance Test 2 by Variant 2
ensure Acceptance Test n by Variant n [Result i, Result j, ..., Result m pass the AT] if (Decision Mechanism (Result i, Result j, ..., Result m) )
return Result else
return failure exception


6-1- Error Recovery:
1-6-1- BACK Ward Recovery:
یعنی ترمیم بازگشت به عقب است . یعنی ترمیمی که به حالت درست قبلی بر می گردد. یعنی در backward ، state قبلی save می شود و هرچه را که save می کنیم در اصل یک check point می گذاریم یعنی علامت میگذاریم که اینجا یک state صحیح قبلی است و این هیچ گاه منجر به خرابی نمی شود پس هنگامی که یک خطا کشف شد آخرین stateدرست قبلی را پیدا می کند و در آنجا قرار می گیرد.
2-6-1- recovery forward :
وقتی خطایی اتفاق می افتد به دنبال یک حالت صحیح نزدیک می گردد.state ی که سیستم بتواند در آن به کارش ادامه دهد. در این روش از error ها گذر می شود. یعنی از error ها سعی می کند به یک حالت صحیح برسد.
7-1-: Data Diversity
هدف این است که یک ورودی بدهیم ویک خروجی صحیح بگیریم ما ورودی هایی را می شناسیم و تست می کنیم ولی یکسری ورودی هایی را نمی شناسیم مخصوصا در سیستم های کنترلی که گاهی نویز محیط خیلی زیاد است بنابراین ما روی ورودی یک مکانیزم یا الگوریتمی سوار می کنیم که این ورودی را به شکل دیگر ی تبدیل می کنیم که آیا داده تغییر یافته را به نرم افزار بدهیم خروجی در دامنه valid است یا invalid و تاچه میزان تاثیرات ورودی بر روی خروجی ظاهر می شود.[1]

2- Simulated Annealing :

1-2 - SA چيست؟

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

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


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


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


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


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

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

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

- معيار پذيرش (يك حركت)


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

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

(2)


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

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

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

در متن اصلی مقاله به هم ریختگی وجود ندارد. برای مطالعه بیشتر مقاله آن را خریداری کنید