1 Local Search 局部搜索算法介紹
??局部搜索是解決最優(yōu)化問題的一種啟發(fā)式算法。因為對于很多復(fù)雜的問題恭取，求解最優(yōu)解的時間可能是極其長的泰偿。因此誕生了各種啟發(fā)式算法來退而求其次尋找次優(yōu)解或近似最優(yōu)解熄守，局部搜索就是其中一種。它是一種近似算法（Approximate algorithms）耗跛。
??局部搜索算法是從爬山法改進而來的裕照。簡單來說，局部搜索算法是一種簡單的貪心搜索算法调塌，該算法每次從當前解的鄰域解空間中選擇一個最好鄰居作為下次迭代的當前解晋南，直到達到一個局部最優(yōu)解(local optimal solution)。局部搜索從一個初始解出發(fā)羔砾，然后搜索解的鄰域负间，如有更優(yōu)的解則移動至該解并繼續(xù)執(zhí)行搜索，否則就停止算法獲得局部最優(yōu)解姜凄。
??爬山算法是一種簡單的貪心搜索算法政溃，也可以被稱為局部搜索算法（local search algorithm），該算法每次從當前解的臨近解空間中選擇一個最優(yōu)解作為當前解态秧，直到達到一個局部最優(yōu)解董虱。這種算法思想很單純，但是也存在一個很大的缺陷。在搜索選擇的過程中有可能會陷入局部最優(yōu)解愤诱，而這個局部最優(yōu)解不一定是全局最優(yōu)解云头。比如下面這個問題：
??假設(shè)A是當前解，爬山算法往前繼續(xù)搜索淫半，當搜索到B這個局部最優(yōu)解時就會停止搜索了溃槐。因為此時在B點無論是往哪邊走都不會得到更優(yōu)的解了。但是科吭，聰明的同學已經(jīng)發(fā)現(xiàn)了竿痰，全局最優(yōu)解在C點。
2 Local Search 思想
??局部搜索會先從一個初始解開始砌溺，通過鄰域動作影涉。產(chǎn)生初始解的鄰居解，然后根據(jù)某種策略選擇鄰居解规伐。一直重復(fù)以上過程蟹倾，直到達到終止條件。
??不同局部搜索算法的區(qū)別就在于：鄰域動作的定義以及選擇鄰居解的策略猖闪。這也是決定算法好壞的關(guān)鍵之處鲜棠。
2.1 鄰域動作
??其實鄰域動作就是一個函數(shù)。那么培慌，通過這個函數(shù)豁陆，針對當前解s，產(chǎn)生s對應(yīng)的鄰居解的一個集合吵护。比如：對于一個bool型問題盒音，其當前解為：s = 1001，當將鄰域動作定義為翻轉(zhuǎn)其中一個bit時馅而，得到的鄰居解的集合N(s)={0001,1101,1011,1000}祥诽，其中N(s) ∈ S。同理瓮恭，當將鄰域動作定義為互換相鄰bit時雄坪，得到的鄰居解的集合N(s)={0101,1001,1010}.
??Local Search中鄰域的選擇包括：
??1. Best improvement (steepest descent)
??2. First improvement
??3. Random selection
2.2 Local Search 偽代碼
2.1 Local Search 中鄰域的選擇
3 Local Search 優(yōu)缺點
3.1 Local Search 的缺點
1、對初始值十分敏感屯蹦。（The LS is very sensitive to the initial solution.）
2维哈、需要執(zhí)行的迭代次數(shù)可能未知。（The number of iterations performed may not be known in advance.）
3登澜、即使LS運行得非忱樱快，其最壞情況下的復(fù)雜度也是指數(shù)級的帖渠。（Even if the LS runs very quickly, its worst case complexity is exponential.）
3.2 Local Search 的優(yōu)點
1谒亦、若沒有很多局部最優(yōu)解的時候，Local Search會運行的很好。
