Local beam search الگوریتم جستجوی

  • شماره مطلب : 25
  • دسته بندی : هوش مصنوعی
  • عنوان :  الگوریتم جستجوی local beam search
  • نویسنده : NetBoss
  • پیش نیاز : الگوریتم جستجوی تپه نوردی
  • پروژه عملی :

شرح الگوریتم local beam search

اگر الگوریتم جستجوی تپه نوردی را مطالعه کرده باشید به یاد خواهید آورد که در این الگوریتم تنها یک وضعیت را در حافظه نگهداری خواهیم نمود. حال بر خلاف الگوریتم جستجوی تپه نوردی، در الگوریتم local beam search جستجو را برای تعداد K وضعیت را ادامه خواهیم داد. با شروع کار این الگوریتم تعداد K وضعیت رندم در حافظه نگهداری میشوند. سپس در هر محرله وضعیت های ناشی از این K وضعیت تولید میشوند. اگر هر کدام از وضعیت های تولید شده برابر با وضعیت هدف بود، کار الگوریتم به پاین رسیده و وضعیت هدف توسط الگوریتم Return  خواهد شد. در غیر این صورت، از میان تمام وضعیت های تولید شده الگوریتم K تا از بهترین ها را انتخاب نموده و مراحل حل مسئله را ادامه خواهد داد. در نگاه اول ممکن است که این روش با الگوریتم Random Restart که برای K وضعیت بطور همزمان کار میکند اشتباه گرفته شود. این در حالی است که این دو روش بسیار متفاوت میباشند. در روش Random Restart پراسس های جستجو از یکدیگر مستقل هستند. این در حالیست که در Local beam search اطلاعات مفید جستجو در حال Share شدن میان ترد های عملیات جستجو میباشند. نتیجتا با این روش الگوریتم از جستجو های بیهوده جلوگیری کرده و منابع خود را طوری تخصیص میدهد که بهترین نتایج حاضل میشوند. 

مشکل local beam search

ساده ترین ورژن این الگوریتم که در بالا توضیح داده شد از عدم وجود گوناگونی در میان K وضعیت رنج میبرد. در واقع این احتمال وجود دارد که در طول انجام مراحل این K وضعیت شبیه بهم باشند که این امر باعث میشود که الگوریتم فوق مقدار اندکی  از الگوریتم تپه نوردی هزینه بیشتری داشته باشد. برای حل مشکل فوق از ورژن خاصی از این الگوریتم به نام الگوریتم Stochastic beam search  استفاده میشود.

شرح Stochastic beam search

در این روش به جای انتخاب K تا از بهترین وضعیت های ایجاد شده به تعداد K وضعیت را به صورت رندم انتخاب مینماییم. این کار با این امید انجام میشود که وضعیت های انتخاب شده علیرغم احتمال حرکت به سمت دره، در ادامه باعث بهبود عملکرد روال جستجو شوند.

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

Add a Comment

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

Copy Protected by Chetan's WP-Copyprotect.