Simulated annealing الگوریتم جستجوی

  • شماره مطلب : 24
  • دسته بندی : هوش مصنوعی
  • عنوان :  الگوریتم جستجوی Simulated annealing
  • نویسنده : NetBoss
  • پیش نیاز : الگوریتم جستجوی تپه نوردی
  • پروژه عملی :

شرح الگوریتم Simulated annealing

اگر در مورد الگوریتم جستجوی تپه نوردی مطالعه کرده باشید متوجه خواهید شد که این الگوریتم هیچ گاه حرکاتی به سمت پایین دره انجام نخواهد داد. تفسیر جمله فوق این است که در واقع این الگوریتم هیچ گاه وضعیت هایی با هزینه ای بیشتر از هزینه وضعیت فعلی را انتخاب نخواهد نمود. چنین استراتژی باعث خواهد شد که الگوریتم جستجوی تپه نوردی کامل نباشد، زیرا همیشه احتمال گیر افتادن در یک local Maximum محتمل است. بطور عکس، انتخاب یکنواخت یکی از وضعیت های ایجاد شده بطور رندوم جستجویی کامل ولی بسیار ناکارآمد است. برای همین منطقی بنظر میرسد تا با ترکیب جستجوی تپه نوردی با یک نوع حرکت رندوم هم کارآمدی هم کامل بودن را بدست آورد. به الگوریتم با چنین خاصیتی Simulated annealing میگویند.

بد نیست بدانید که در علم متالوژی Simulated annealing  روشی است که با آن ابتدا فلزات را حرارت داده و سپس به تدریج آنها را سر میکنند. نتیجتا با استفاده از این تکنیک استحکام فلزات افزایش پیدا خواهد کرد. نام الگوریتم فوق هم از همین پروسه گرفته شده است. دلیل انتخاب این اسم برای این الگوریتم در کتاب راسل توضیح داده شده است. با این حال برای جلوگیری از سوء برداشت از توضیح آن در این مطلب خودداری شده است.

حلقه داخلی این الگوریتم بسیار شبیه به الگوریتم جستجوی تپه نوردی میباشد. با این حال این الگوریتم بجای انتخاب بهترین  وضعیت از میان وضعیت های ایجاد شده، بصورت رندوم یکی از آنها را انتخاب مینماید. این بدین معناست که با این کار حرکت به سمت دره (وضعیت هایی با هزینه بیشتر) محتمل خواهد شد. اگر حرکت انتخاب شده وضعیت حل مسئله را بهبود ببخشد، این وضعیت همیشه توسط الگوریتم تایید میشود. در غیر این صورت، از این پس الگوریتم این وضعیت را با احتمالی کمتر از 1 انتخاب مینماید. این احتمال با توجه به بد بودن وضعیت مورد نظر بطور نمایی کاهش میابد. همچنین، این احتمال با کاهش المان T  کاهش میابد. در واقع با بالا بودن T انتخاب وضعیت های اشتباه در ابتدای کار الگوریتم زیاد است ولی با کاهش مقدار T انتخاب آنها غیر محتمل تر خواهد شد. اگر Scheduler مقدار T  را به اندازه کافی کاهش دهد، الگوریتم میتواند در نهایت یک Global optimum با احتمال نزدیک به 1 را بیابد.

در اوایل دهه 80 بطور گسترده ای از این الگوریتم برای حل مسائل مرتبط با VLSI Layout problems استفاده شده است.

function SIMULATED-ANNEALING(problem, schedule) returns a solution state
inputs: problem, a problem
schedule , a mapping from time to “temperature”
current ←MAKE-NODE(problem.INITIAL-STATE)
for t = 1 to∞do
T ←schedule(t )
if T = 0 then return current
next←a randomly selected successor of current
ΔE ←next.Heuristic – current.Heuristic
if ΔE < 0 then current ←next
else current ←next only with probability e^(ΔE/T)

الگوریتم جستجوی محلی

Add a Comment

Your email address will not be published. Required fields are marked *

Copy Protected by Chetan's WP-Copyprotect.