N-車(chē)探險(xiǎn)問(wèn)題是一類(lèi)NP-hard離散優(yōu)化問(wèn)題,針對(duì)該問(wèn)題,提出一種融合局部搜索的離散水波優(yōu)化算法。結(jié)合該問(wèn)題等價(jià)于置換排序的特性,設(shè)計(jì)基于置換序列的編碼方式;利用反轉(zhuǎn)、移動(dòng)、交換等操作重新定義傳播、折射和碎浪算子;開(kāi)發(fā)基于插入鄰域的局部搜索策略,以增強(qiáng)水波優(yōu)化算法的局部搜索能力。最后,利用實(shí)驗(yàn)設(shè)計(jì)探討關(guān)鍵參數(shù)對(duì)算法性能的影響。基于14個(gè)標(biāo)準(zhǔn)問(wèn)題的測(cè)試結(jié)果表明:所提方法的尋優(yōu)精度、穩(wěn)定性等整體優(yōu)于標(biāo)準(zhǔn)水波優(yōu)化算法、粒子群算法、煙花算法和啟發(fā)式算法H1～H4;與離散水波優(yōu)化算法相比,基于禁忌搜索的變鄰域搜索算法用至少66.6倍的計(jì)算時(shí)間得到了最大相對(duì)偏差比為0.017的尋優(yōu)精度。結(jié)果表明,離散水波優(yōu)化算法能在較短時(shí)間內(nèi)獲得較滿(mǎn)意的解。

【文章頁(yè)數(shù)】：9 頁(yè)

【部分圖文】：

圖2反轉(zhuǎn)操作

(1）隨機(jī)選取πi的兩個(gè)位置i、j，反轉(zhuǎn)i,i+1，…，j-1,j得到π′i;3.3折射

圖1車(chē)輛行駛序列圖[17-18]

定義π=（π1，π2，…，πn）為車(chē)輛的行駛序列，前面的車(chē)給后面的車(chē)供油，是車(chē)輛πi的行駛距離，如圖1所示。車(chē)輛πi的行駛距離滿(mǎn)足[17]:

圖3移動(dòng)操作

如圖3所示，在π*和πi之間移動(dòng)[4,2,6]的操作步驟為：(1)π*（4)=4，分別找到πi(1)=4，πi(4)=5，交換πi的4和5;(2)π*（5)=2，分別找到πi(3)=2，πi(5)=1，交換πi的2和1;(3)π*（6)=6，分別找到πi(2)=6，πi(6)=3....

圖4交換操作

(2）如果f（π*）>f（πi），則更新πi=π*；如果min（βf（πi）/f（π*），1)<u，則更新πi=π*，否則保留πi。其中，u為[0,1]上的均勻隨機(jī)數(shù)。3.5基于插入鄰域的局部搜索

本文編號(hào)：3971916