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

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

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

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

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

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

۴-۵-۱-روش (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

۵-۵-۱- Acceptance voting (AV) :

AV یکی از روشهای مهم از تکنیک تنوع طراحی می باشد . در این روش ما می توانیم از یک نرم افزار ، نسخه های مختلفی داشته باشیم که به هر یک از آنها یک variant گفته
می شود .
این روش هم از (Acceptance Test) AT و هم از voting استفاده می کند .
در اینجا ابتدا تمام variant ها به صورت موازی اجرا می شود خروجی هر یک از آنها وارد یک AT می شود . ATخروجی را بررسی می کند تا آن را به voterپاس دهد .
voterدر این روش یک voter کاملا دینامیک است ؛ یعنی voter از یک الگوریتم رای گیری دینامیک استفاده می کند ؛ یعنی اگر تعداد خروجی هایی که توسط AT به آن پاس داده می شود کمتر از N (تعداد variant ها ) باشد نیز میتواند جواب نهایی را تولید کند یعنیvoter تعداد خروجی های پاس داده شده به وسیله AT به voter می تواند K باشد که N 1K < است . به این ترتیب اگر یکی از 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

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

۲- 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 است که باید تعیین گردد.