Procedure HillClimbing
Generate a solution )S’ )
Best = S’
Loop
S = Best
S’ = Neighbors)S(
Best = SelectBest )S’ )
Until stop criterion satisfied
End
شکل ۳-۱۳ شبه کد جستجوی تپه نوردی ]۳۰[
۳-۱۲-۳-۲ جستجوی پرتو محلی^[۱۲۳]
روش جستجـوی دیگری بر پایه جستجوی تپه نوردی به نام جستجو پرتو محـلی نیز وجـود دارد که در حل مسـائل از قـدرت بسیار بیشتری نسبت به جستجوی تپه نوردی برخوردار می باشد. در این روش برخلاف روش تپه نوردی ابتدا k جواب برای مساله تولید می شود. سپس برای هریک از این K حالت همسایه های آن ها را تولید کرده و از میان همه همسایه ها K تا از بهترین همسایه ها انتخاب می گردد که این فرایند تا رسیدن به شرط توقف ادامه می یابد. انتخاب K پاسخ بهینه‌تر از بین تمام پاسخ های همسایه تولید شده، از شبیه شدن پاسخ ها به یکدیگر جلوگیـری می‌کند]۳۶[. شبه الگوریتم پرتو محلـی در شکل ۳-۱۴ نمایش داده شده است:

Procedure LoacBeamSearch
Generate K solution
Do
For each solution generate its neighbors
Select K best solution from whole neighbors
Replace current solutions by selected solutions
Loop until stop criterion satisfied
End
شکل ۳-۱۴ شبه الگوریتم پرتومحلی]۳۶[
۳-۱۲-۳-۳ جستجوی شبیه سازی حرارت^[۱۲۴]
روش 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 در شکل ۳-۱۶ نمایش داده شده است: