مقاله دانشگاهی – بهینه سازی روش تشخیص اهمیت پیوند در پایگاه پیوند و کاربست آن در …

۳-۱۲-۳-۳ جستجوی شبیه سازی حرارت[۱۲۴]
روش SA یکی دیگر از روش های جستجو می باشد که ایده آن از عمـل سرد کردن تدریجی فلـزات برای
استحکام بیشتر آن ها نشأت گرفته است. همانند روش تپه نوردی، در این روش نیز مسئله از یک حالت مانند S در فضای حالت مسئله شروع شده و با گذر از حالتی به حالت دیگر به جواب بهینه مسئله نزدیک می شود. انتخاب حالت شروع هم می تواند به صورت تصادفی انجام پذیرد و هم بر اساس یک قاعده حالت اولیه مسئله انتخاب گردد.
در اینجا نیز تابع Objective میزان بهینگی حالت فعلی را محاسبه کرده و Neighbor نیز یک حالت همسایه برای حالت فعلی تولید می کند. نحوه تولید حالت همسایه از اهمیت به سزایی برخوردار است. روش کلی کار به این صورت است که در هر تکرار، الگوریتم SA حالت همسایه ای مانند ‘ sایجاد می کند و بر اساس یک احتمال، مسئله از حالت s به حالت ‘ sمی رود و یا اینکه در همان حالت s باقی می ماند. این روند تا زمانی تکرار می شود که یک جواب نسبتاً بهینه بدست آید و یا ماکزیمم تعداد تکرار ها انجام شده باشد. در روش کلی الگوریتم بیان شد که قبولی حالت همسایه تولید شده بر اساس یک احتـمال صورت می پذیرد]۳۰[.
تابع (P(e,e’,T تعیین کننده احتمال قبولی حالت همسایه می باشد. e بهینگی حالت فعلی و ‘ eبهینگی حالت
همسایه می باشد. در صورتی که حالت همسایه از حالت فعلی بدتر باشد، مقدار پارامتر T تعیین کننده احتمال قبولی جواب می باشد. در ابتدای امر مقدار پارامتر T را طوری انتخاب می کنیم که اکثر حالت های همسایه را مورد پذیرش قرار دهیم، پارامتر T نشانگر دما بوده و مقدار این پارامتر به تدریج کاهش می یابد. مقدار پارامتر T را طوری انتخاب می کنیم که قبل از انجام گرفتن ماکزیمم تعداد تکرارها، مقدار آن تقریبا صفر گردد.
مستنداتی که برای الگوریتم SA وجود دارد، نشان می دهند که در ابتدای امر مقدار T بهتر است به گونه ای تعیین گردد که در ابتدا ۸۰% جواب ها مورد پذیرش الگوریتم واقع شود]۳۰[. در شکل ۳-۱۵ شبه الگوریتم شبیه سازی حرارت بیان شده است:
Procedure Simulated Annealing
C = Choose an initial solution
T = Choose an initial temperature
REPEAT
S’ = Generate a neighbor of the solution C
ΔE = objective( S’ ) – objective( C )
IF (ΔE > 0 ) THEN // S’ better than C
C = S’
ELSE with probability EXP( ΔE/ T )
C = S’
END IF
T = lower the T using linear/ non-linear techniques
UNTIL meet the stop criteria
End
شکل ۳-۱۵ شبه الگوریتم شبیه سازی حرارت ]۳۰[
۳-۱۲-۳-۴ الگوریتم آستانه پذیرش[۱۲۵]
روش TA نیز همانند روش SA می باشد و تنها تفاوت آن در نحوه قبول کردن جواب های غیر بهینه است. الگوریتم TA جواب هایی را می پذیرد که از جواب قبلی خیلی بدتر نیستند. همانند کاری که دما در الگوریتم SA انجام می دهد. دما در این الگوریتم باید به گونه ای انتخاب شود که بیشتر جواب های غیربهینه در ابتدا توسط الگوریتم پذیرفته شوند. این اصل در مورد روش TA نیز صادق است و در این روش نیـز مقدار آستانه (T) باید به نحـوه انتخاب گـردد که بیشتـر جـواب های غیـربهینه در ابتـدا توسـط
الگوریتم مورد پذیرش واقع شوند]۳۰[. شبه الگوریتم TA در شکل ۳-۱۶ نمایش داده شده است:
Procedure Threhsold Acceptance
C = Choose an initial solution
T = Choose a positive initial threshold
REPEAT
S’ = Generate a neighbor of the solution C
ΔE = objective( S’ ) – objective( C )
IF (ΔE > -T ) THEN // S’ better than C
C = S’
END IF
T = lower the T using linear/ non-linear techniques
UNTIL meet the stop criteria
End
شکل ۳-۱۶ شبه الگوریتم آستانه پذیرش ]۳۰[

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

منبع فایل کامل این پایان نامه این سایت pipaf.ir است