基于LocalSearch的算法賞析

1、前言：很久沒有寫博文了，兩個字“窮忙”，這一段時間里收到了很多老師、學(xué)生和業(yè)界人員的問題，有些回答的稍顯草率，請諒解，其中的一些問題（比如QCQP中的semidefinite的相關(guān)問題及討論）很想寫寫，但一想到寫這些東西需要認(rèn)真捋清思路、小心措辭、輔助作圖等，又想到自己research進(jìn)展跟狗屎一樣，就實在沒有心情寫了。其實，青年教師的科研壓力不比在讀博士生小，老師們應(yīng)該都能理解，所以請學(xué)生們和業(yè)界人員原諒我這一段時間問題回答上的草率。今天選擇Local Search（LS）這個話題，一來是最近看到很多Papers在使用這些方法，二來是看到最近優(yōu)化軟件LocalSolver(官網(wǎng)，中國代理商)

2、火爆的不行。LocalSolver是基于local search方法（而非Branch and Cut方法和Constraint Programming方法）求解Mathematical Programming模型的，所以非線性算子（floor, ceil, log, exp, pow, cos, sin, tan）就完全不在話下了，當(dāng)您的model有大量非線性和非凸性的時候，您就別再一邊又一邊給杜老師發(fā)Email了（杜老師，我用Gurobi和CPLEX怎么都不行？），也別苦逼地去嘗試IBM ILOG CP Opitimizer了，因為CP雖然也能處理這些，但畢竟設(shè)計的初衷不是為了求Mathe

3、matical Model的，所以這時候大膽嘗試一下LocalSolver吧。我以后再也不會說：你的Model非線性和非凸性都很強，有點沒治；我會說：Pls Try LocalSolver（對學(xué)術(shù)界免費開放）。Local Search詳細(xì)的基本知識我就不說了，說實在的，我掌握的也不是很系統(tǒng)，不過LocalSolver團(tuán)隊提供了供課堂教學(xué)用的資料，讓老師教學(xué)生系統(tǒng)學(xué)習(xí)LS技術(shù)（我在內(nèi)蒙古大學(xué)還沒有資格給研究生上課，所以暫時不會把LS技術(shù)系統(tǒng)地帶入課堂,這一點也令我有些沮喪)，有需要教學(xué)的老師可向LocalSolver開發(fā)團(tuán)隊協(xié)商索要教學(xué)資料。下面我簡單地把跟Local Search緊密相關(guān)的一些

4、算法（這里，我無意全面地介紹跟LS相關(guān)的各種算法）介紹給大家，讓大家對LS技術(shù)有個相對直觀和略顯高級的理解，也能大致洞察清楚優(yōu)化軟件LocalSolver后面的東東，主要包括：Variable Neighborhood Descent(VND),Iterated Local Search (ILS)，Variable Neighborhood Search (VNS)，Variable Neighborhood Decompostion Search (VNDS)，Large Neighborhood Search (LNS)等。算法詳細(xì)的細(xì)節(jié)我不再披露，請大家google里找相應(yīng)的Paper

5、s閱讀，我只簡單給出算法的主要偽代碼（主要的來源是Thomas Stutzle在2003年一個暑期學(xué)校上的講義即Blum在Applied Soft Computing上寫的一篇綜述論文），并著重分析各算法的核心思想以及各算法的區(qū)別。-博主2013年8月31日注：開始-Local Search也是一種順序化的搜索方法，搜索路徑形成一個軌跡，針對當(dāng)前點（解），從其鄰域中試圖找到一個更好的解來代替當(dāng)前解（找不到時當(dāng)然要停止搜索）。問題一：基本的Local Search常常能到達(dá)局部最優(yōu)，若算法不再配備克服局部極優(yōu)的機(jī)制，常常稱這種Local Search為Hill Climbing（爬山法）；若配備

6、了克服局部極優(yōu)的機(jī)制，就形成更為復(fù)雜的算法，如利用iteration機(jī)制的Iterated Local Search算法，利用memory(記憶)機(jī)制的reactive search optimization算法，利用memory-less stochastic modification機(jī)制的Simulated Annealing算法。我們這里提到的Local Search主要指的是Hill Climbing。問題二：若定義鄰居（鄰域）的方法是最多不超過k個Solution Component發(fā)生改變（其余n-k個component不變），這種Local Search成為k-OPT。例子：求解

7、TSP的2-OPT即是一種Local Search。在這一算法中，常常把定義鄰居的交換兩條弧的操作成為2-OPT Swap,可用函數(shù)2OptSwap(route,i,k)。如對于解A-B-C-D-E-F-G-H-A，指定i=3,k=6，即針對弧C-D和G-H進(jìn)行交換，交換為C-G和D-H,即(A-B-C)和（H-A）片段不變（也即H-A-B-C不變），片段（D-E-F-G）元素也不變，只是兩個片段原來靠弧C-D和G-H連接，現(xiàn)在靠弧C-G和D-H連接（兩個片段連接的首尾交換了一下），考慮到這里是有方向的，故將片段（D-E-F-G）在元素連接方式不變的情況下方向變一下，即為（G-F-E-D），這

8、就構(gòu)造除了新的鄰居A-B-C-G-F-E-D-H-A。所以每次給定一個i、k的具體值，2OptSwap(route,i,k)就會給出一個具體的鄰居。這就有了下面的問題三。問題三：對于當(dāng)前解S，有很多鄰居（對于上面的2-OPT，每個不同的組合都將是一個鄰居），也即它的鄰域中有很多解，如何搜索它的鄰域？也即，如何在鄰域中找到更好的解？一種簡單粗暴的思路是“系統(tǒng)化的搜索”，利用兩次for循環(huán)來枚舉不同的組合，當(dāng)在某個找到更好解時，替代當(dāng)前解S，否則繼續(xù)枚舉,見下面的代碼；另一種策略常常用到，即“隨機(jī)化的搜索”方法，每次隨機(jī)地選取S的一個鄰居（即），找到更好的解時替代當(dāng)前解，否則繼續(xù)隨機(jī)選取S的一個鄰

9、居，當(dāng)在給定隨機(jī)嘗試次數(shù)內(nèi)找不到更好解時，算法停止。-博主2013年8月31日注：結(jié)束-1.Variable Neighborhood Descent(VND)每次在一個鄰域N_k中找不到一個更好的解時，就仍然從當(dāng)前解s出發(fā)，換一個領(lǐng)域結(jié)構(gòu)（常常是在一個更大的領(lǐng)域中）搜索，看是否能找到更好的解；當(dāng)找到一個更好的解s時，從這一新的解出發(fā)，重新返回第一個領(lǐng)域結(jié)構(gòu)開始搜索。這里變換鄰域結(jié)構(gòu)時的初衷是當(dāng)前鄰域結(jié)構(gòu)找不到更好的解，而變換（常常為擴(kuò)大）鄰域結(jié)構(gòu)能帶來找到更優(yōu)解的希望，但變換鄰域結(jié)構(gòu)時，要保持搜索的初始解（當(dāng)前解）不變。但值得注意的是：對不同領(lǐng)域結(jié)構(gòu)嘗試搜索的算法可能不一樣。2. Itera

10、ted Local Search (ILS)Local Search是在一個領(lǐng)域結(jié)構(gòu)（通常較小，如TSP問題的2-OPT，3-OPT鄰域，并行機(jī)調(diào)度問題的insert鄰域）中從一個最優(yōu)解出發(fā)試圖找到最好的解，local search的搜索往往是從一個點到另一個點的順序化搜索，一點點改進(jìn)（模擬退火在每個溫度上的搜索不也是一種local search么？只是加入了以一定概率接受差解的機(jī)制）。因此local search的出發(fā)點（初始解）就很重要，對出發(fā)點的搜索，往往是在一個更大的領(lǐng)域結(jié)構(gòu)內(nèi)（如TSP問題的4-OPT鄰域，并行機(jī)調(diào)度的swap鄰域）隨機(jī)地選取一點，這種在更大領(lǐng)域內(nèi)隨機(jī)選一點的操作稱為

11、Perturbation。值得注意的是：Simulated Annealing (SA), Tabu Search (TS)等也是為了增強local search而設(shè)計的Metaheuristics，它們的整個搜索過程都是一條trajectory，而ILS的搜索過程中由于用了Perturbation來跳出局部最優(yōu)，所以其搜索過程不再是一條trajectory，這也是ILS與SA、TS的主要不同之處。博主2013年10月2日注：如果這里Perturbation跟s*沒有關(guān)系，是純隨機(jī)地產(chǎn)生一個解，那么就不是Iterated Local Search了，就變成了Multi-start Local

12、Search了。3.Variable Neighborhood Search (VNS)不考慮對解的接受規(guī)則（因為AcceptenceCriterion本身可以靈活選用），VNS與ILS的區(qū)別僅僅在于：在對local search初始點搜索(即perturbation)時，VNS并不是僅限于一種領(lǐng)域結(jié)構(gòu)，而是按一定順序（size從大到小還是從小到大？可有多種不同版本）嘗試預(yù)先設(shè)計好的多個領(lǐng)域結(jié)構(gòu)從一個領(lǐng)域結(jié)構(gòu)N_k中的一點出發(fā)，local search找不到更好解就從第N_(k+1)個鄰域結(jié)構(gòu)的一點出發(fā)；一旦找到更好解，下次perturbation時就仍然從第一個鄰域結(jié)構(gòu)N_1開始嘗試(注意：

13、local search操作僅僅在N_1領(lǐng)域結(jié)構(gòu)中展開)。VNS與VND的差別在于變換領(lǐng)域的初衷：VND變換領(lǐng)域時local search的出發(fā)點不變，即不是為了Perturbation,只是為了改變（擴(kuò)大）鄰域結(jié)構(gòu)能找到更好的解；而VNS變換領(lǐng)域結(jié)構(gòu)目的是perturbation，從幾何上看，是從當(dāng)前搜索的局部區(qū)域中跳出來讓local search在另一個局部區(qū)域中展開。4. Variable Neighborhood Decompostion Search (VNDS)VNS的一個常用變種是VNDS（變鄰域分解搜索），VNDS與VNS的唯一不同在于：local search是針對一個縮小后

14、的問題（子問題）進(jìn)行搜索的。每次perturbation得到一個初始解后，不是馬上進(jìn)行l(wèi)ocal search，而通過“保留這個初始解的k個解元素不變，另外n-k個解元素是可變的”定義一個子問題，讓local search搜索這n-k個自由的解元素（從上圖看出，實際是一個縮小的問題）。5. Large Neighborhood Search (LNS)那有的小同學(xué)又問問題了：杜老師，Large Neighborhood Search (LNS)又是什么？答：請看下面LNS的Procedure，觀察一下差異。看出跟ILS的差異了么？（1）ILS中的Local Search往往鄰域較小，所以采用一般的Local Search即可，而LNS的鄰域較大，往往需要其它搜索技術(shù)，如