Y@SiN
01-25-2010, 02:39 PM
در الگوریتم تپه نوردی ابتدا یک جواب تصادفی برای مسئله تولید می کردیم و سپس سعی بر آن داشتیم که با تولید حالت های همسایه حالت فعلی و انتخاب بهترین حالت همسایه ، به سمت جواب بهینه حرکت کنیم. همچنین با تغییر کوچکی که بر روی الگوریتم تپه نوردی انجام دادیم ، مشکل قرار گرفتن الگوریتم در بهینگی محلی را حل کردیم ( این روش تنها در مورد مسائل کوچک جوابگو خواهد بود ).
http://pnu-club.com/imported/mising.jpg
روش جستجوی دیگری بر پایه جستجوی تپه نوردی به نام جستجو پرتو محلی نیز وجود دارد که در حل مسائل از قدرت بسیار بیشتری نسبت به جستجوی تپه نوردی برخوردار می باشد. در این روش برخلاف روش تپه نوردی ابتدا 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 اشاره کرد که در مقالات دیگری به بررسی هریک از این روش ها پرداخته ایم.
http://pnu-club.com/imported/mising.jpg
روش جستجوی دیگری بر پایه جستجوی تپه نوردی به نام جستجو پرتو محلی نیز وجود دارد که در حل مسائل از قدرت بسیار بیشتری نسبت به جستجوی تپه نوردی برخوردار می باشد. در این روش برخلاف روش تپه نوردی ابتدا 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 اشاره کرد که در مقالات دیگری به بررسی هریک از این روش ها پرداخته ایم.