جستجوی پرتو محلی
در الگوریتم تپه نوردی ابتدا یک جواب تصادفی برای مسئله تولید می کردیم و سپس سعی
بر آن داشتیم که با تولید حالت های همسایه حالت فعلی و انتخاب بهترین حالت همسایه ،
به سمت جواب بهینه حرکت کنیم. همچنین با تغییر کوچکی که بر روی الگوریتم تپه نوردی
انجام دادیم ، مشکل قرار گرفتن الگوریتم در بهینگی محلی را حل کردیم ( این روش تنها
در مورد مسائل کوچک جوابگو خواهد بود ).
|
|
روش جستجوی دیگری بر پایه جستجوی تپه نوردی به نام جستجو پرتو محلی نیز وجود دارد
که در حل مسائل از قدرت بسیار بیشتری نسبت به جستجوی تپه نوردی برخوردار می باشد.
در این روش برخلاف روش تپه نوردی ابتدا 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
|
|
هرچند که الگوریتم جستجوی پرتو محلی در مقایسه با الگوریتم تپه نوردی از کارآیی
بیشتری برخوردار است، با این حال هر دو این روش ها از قرار گرفتن در بهینگی های
محلی مصون نیستند. از اینرو نیاز به روش های دیگری داریم که بتوانند از بهینگی های
محلی گذر کرده و به سمت بهینگی سراسری حرکت کنند. از جمله این روش ها می توان
به روش Simulated Annealing ، Tabu Search و Threshold Acceptance اشاره کرد که در
مقالات دیگری به بررسی هریک از این روش ها پرداخته ایم.
|