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

[آبجی]

در الگوریتم تپه نوردی ابتدا یک جواب تصادفی برای مسئله تولید می کردیم و سپس سعی بر آن داشتیم که با تولید حالت های همسایه حالت فعلی و انتخاب بهترین حالت همسایه ، به سمت جواب بهینه حرکت کنیم. همچنین با تغییر کوچکی که بر روی الگوریتم تپه نوردی انجام دادیم ، مشکل قرار گرفتن الگوریتم در بهینگی محلی را حل کردیم ( این روش تنها در مورد مسائل کوچک جوابگو خواهد بود ).

روش جستجوی دیگری بر پایه جستجوی تپه نوردی به نام جستجو پرتو محلی نیز وجود دارد که در حل مسائل از قدرت بسیار بیشتری نسبت به جستجوی تپه نوردی برخوردار می باشد. در این روش برخلاف روش تپه نوردی ابتدا 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 اشاره کرد که در مقالات دیگری به بررسی هریک از این روش ها پرداخته ایم.