收益可變泛化定向問題建模及優(yōu)化算法研究

林丕源，張鑫睿，朱澤鵬，吳志輝，黃沛杰

(華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院 廣東 廣州 510642)

0 引言

泛化定向問題(generalized orienteering problem,GOP) 是一類特殊的路徑規(guī)劃問題，最早由Wang等[1]于1996年提出.在該問題中，每個點(diǎn)有多個不同類型的收益，每個類型占有一定的權(quán)重比例，其目標(biāo)是在一定的時間限制下訪問多個點(diǎn)，使求得路徑的收益最大.例如，在災(zāi)后搜救貴重物資時，每個救援點(diǎn)有多種不同類型、不同重要程度的待救物資.GOP是定向問題(orienteering problem,OP)[2]的擴(kuò)展，都是NP-hard問題，現(xiàn)有的研究大多都集中使用啟發(fā)式算法求解[1,3-5].

在搜救、物流運(yùn)輸[5]等泛化定向問題的實(shí)際應(yīng)用場景中，往往還伴隨著收益可變的情況.如在災(zāi)后搜救中的各種待救物資，其價(jià)值會隨著救援時間的延長而面臨被毀的風(fēng)險(xiǎn)；在低溫冷鏈物流運(yùn)輸中，運(yùn)輸?shù)母鞣N物資其新鮮度也會隨著運(yùn)輸時間的積累而降低，需要在有限的時間內(nèi)尋找最優(yōu)運(yùn)輸路線，以降低損失，獲取最大收益.因此有必要研究多類型收益隨時間下降變化的優(yōu)化問題，稱為收益可變泛化定向問題 (generalized orienteering problem with variable profits，GOPVP).本文對GOPVP進(jìn)行建模，并提出了求解該問題的改進(jìn)遺傳算法(genetic algorithm，GA).

遺傳算法受進(jìn)化生物學(xué)的啟發(fā)而發(fā)展，能保證種群的多樣性，具有良好的全局尋優(yōu)能力[6-7]，被廣泛應(yīng)用于各類組合優(yōu)化問題中.GA的改進(jìn)主要在于遺傳算子(選擇、交叉、變異)的設(shè)計(jì)[8].在采用GA求解OP相關(guān)問題方面，Wang等[4]在求解GOP中采用了經(jīng)典的選擇和交叉算子，變異算子則采用了逆轉(zhuǎn)變異.Zabielski等[9]則在求解OP中采用了錦標(biāo)賽的選擇算子，并綜合采用了插入、刪除和逆轉(zhuǎn)的變異算子.由于GOPVP中收益隨時間可變，解序列細(xì)微的變化將使目標(biāo)函數(shù)值產(chǎn)生較大差異，導(dǎo)致難以搜索最優(yōu)解.本文基于小生境[10]的選擇思想，在選擇算子方面，采用分組競爭的遺傳策略，選擇適應(yīng)值較高的個體來保證子代的優(yōu)越性，增加后續(xù)遺傳算子搜尋全局最優(yōu)解的概率.并應(yīng)用和設(shè)計(jì)新的變異算子加強(qiáng)鄰域精確搜索能力，進(jìn)一步提高解的質(zhì)量.實(shí)驗(yàn)結(jié)果表明，相比于研究進(jìn)展方法，改進(jìn)的遺傳算法更具有效性和穩(wěn)定性.

1 問題描述與建模

收益可變泛化定向問題描述如下：在一個無向完全圖中，每個點(diǎn)有多個類型的收益，并隨時間下降變化，各類型占有一定的權(quán)重.目標(biāo)是在限定的時間內(nèi)，求得一條從起點(diǎn)到終點(diǎn)的路徑,且至多經(jīng)過其他點(diǎn)一次，使得所獲收益最大.本文采用文獻(xiàn)[4]中使用的目標(biāo)函數(shù)，結(jié)合可變收益的特點(diǎn)，給出GOPVP的數(shù)學(xué)模型.

引入如下標(biāo)記.

1)xij： 當(dāng)邊(i,j)∈E被訪問時，記xij=1，否則為0.

2)ui： 表示點(diǎn)vi在路徑中的位置.

GOPVP的數(shù)學(xué)模型為

(1)

(2)

(3)

(4)

2≤ui≤n,i≠1，

(5)

ui-uj+1≤(n-1)(1-xij),i,j≠1.

(6)

xij∈{0,1},i,j∈V，

(7)

其中：目標(biāo)函數(shù)(1)表示最大化路徑總收益；約束(2)保證路徑的長度不超過最大時間約束Tmax；約束(3)保證從起點(diǎn)v1出發(fā)并到達(dá)終點(diǎn)vn；約束(4)確保結(jié)點(diǎn)至多被訪問一次；約束(5)和(6)確保路徑中沒有子環(huán)，稱之為Miller-Tucker-Zemlin (MTZ)[11].

圖1 GOPVP的一個示例解Fig.1 An example of solution of the GOPVP

圖1展示了GOPVP的一個可行解示例.圖中菱形表示起止點(diǎn)，圓形表示待訪問點(diǎn).最大時間約束Tmax為15，每個點(diǎn)有兩個類型的收益，f表示結(jié)點(diǎn)的收益變化函數(shù)，邊權(quán)表示兩點(diǎn)之間的耗時(圖中僅展示了部分結(jié)點(diǎn)間的時間花費(fèi)).假設(shè)目標(biāo)函數(shù)中指數(shù)k為1，兩個類型權(quán)重均為0.5，點(diǎn)的收益隨時間線性下降，具體如圖所示.圖1所示的路徑中，為了保證在指定時限內(nèi)到達(dá)目的點(diǎn)，有4個點(diǎn)未訪問，路徑為source-a-b-c-d-destination，路徑總耗時為14，滿足最大時間約束.根據(jù)目標(biāo)函數(shù)公式(1)，路徑總收益為56.5.

2 算法求解

本文提出改進(jìn)的遺傳算法來求解GOPVP.首先隨機(jī)初始化種群，隨后通過分組競爭從父代中選擇較優(yōu)的個體形成較優(yōu)的子代，交叉算子選取適當(dāng)?shù)母复M(jìn)行交叉.變異算子除了基于GA求解OP相關(guān)問題的研究進(jìn)展方法[4,9]中采用的插入、刪除和逆轉(zhuǎn)等變異算子之外，基于優(yōu)化局部搜索策略[12-13]的考慮，增加了替換和交換兩個變異算子，并針對收益變化的特點(diǎn)新增一個輪轉(zhuǎn)變異算子，來進(jìn)一步改善解的質(zhì)量，以此形成更優(yōu)種群.當(dāng)進(jìn)化次數(shù)達(dá)到設(shè)定的閾值或最優(yōu)解多次沒有提升時終止計(jì)算，否則重啟算法.

2.1 染色體編碼及適應(yīng)值計(jì)算

本文采用自然數(shù)編碼的方式，將完全圖中的各點(diǎn)標(biāo)序.當(dāng)染色體為1-8-2-9-3-7-6-n時，表示求解路徑從序號為1的點(diǎn)出發(fā)，依次經(jīng)過中間各結(jié)點(diǎn)，到達(dá)終點(diǎn)n.本文使用目標(biāo)函數(shù)值來表示個體的適應(yīng)值，

(8)

2.2 初始化種群

本算法采用隨機(jī)生成方式初始化種群.首先固定起止點(diǎn)，形成僅有兩個基因的染色體，接著向染色體中插入新的基因，同時判斷插入后的新染色體是否違反條件約束，若違反，則終止插入新的基因，否則選擇下一個基因順序插入.

2.3 遺傳算子

1) 選擇算子.本文采用分組競爭的方式來選擇個體.將種群大小Psize分為num組(num

2) 交叉算子.本文采用單點(diǎn)交叉的方式.首先隨機(jī)兩個個體作為父代，然后確定父代的共同基因(不包含起止基因)為交叉點(diǎn)集.若交叉點(diǎn)集不空，則以所有基因?yàn)榻徊纥c(diǎn)進(jìn)行交叉，并將適應(yīng)值比父代大且可行的子代個體保存下來，否則不進(jìn)行交叉操作.

3) 變異算子.本文應(yīng)用和設(shè)計(jì)了6種變異算子.簡單的插入和刪除變異算子在隨機(jī)選擇的個體上執(zhí)行，維持進(jìn)化過程中種群的多樣性，防止早熟；其他4種變異算子在多個分組競爭中優(yōu)勝的個體上執(zhí)行，加強(qiáng)優(yōu)良個體的局部搜索能力，進(jìn)一步改善解的質(zhì)量.其中分組競爭的方式和選擇算子操作一致.變異算子具體過程如下.

a) 替換變異.用新基因替換染色體上的基因，并用替換后收益最高且可行的子代來更新父代.

b) 逆轉(zhuǎn)變異.逆序所有的基因片段，以減少個體長度[13]，以便插入更多的基因片段，增加個體收益，如圖2所示.

c) 交換變異.調(diào)換任意兩個基因的位置，并用操作后長度最短的個體來更新原染色體，如圖3所示.

d) 輪轉(zhuǎn)變異.針對收益可變的問題特點(diǎn)，循環(huán)移動基因片段，對產(chǎn)生的所有新子代，保留可行且收益最佳的子代以更新父代，具體如圖4所示.

圖2 逆轉(zhuǎn)操作Fig.2 Operation of reverse

圖3 交換操作Fig.3 Operation of swap

圖4 輪轉(zhuǎn)操作Fig.4 Operation of turn

與GOP不同，GOPVP中點(diǎn)的收益可變，染色體基因的序列直接影響到個體的目標(biāo)函數(shù)值.輪轉(zhuǎn)操作更詳細(xì)的例子如圖5所示.每個點(diǎn)有兩個類型的收益，且隨時間線性下降，如圖中f所示，最大時間限制Tmax為10.圖中菱形表示起止點(diǎn)，圓形表示待訪問點(diǎn).假設(shè)目標(biāo)函數(shù)中指數(shù)k為1，兩個類型權(quán)重均為0.5.

圖5 輪轉(zhuǎn)操作例子Fig.5 Example of turn operator

在圖5的示例中，圖5(a)中可行解為source-d-a-b-c-destination，根據(jù)目標(biāo)函數(shù)公式(1)計(jì)算，其總收益為46.5.圖5(b)中可行解為source-a-b-c-d-destination，其總收益為59.5.通過輪轉(zhuǎn)操作，可進(jìn)一步提高解的質(zhì)量.

3 實(shí)驗(yàn)設(shè)置及結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)置

3.1.1實(shí)驗(yàn)數(shù)據(jù) 本文采用3個經(jīng)典算例集來驗(yàn)證算法的有效性，分別為Wang等[1]提出的GOP算例和Tsiligirides[14]、Chao等[15]提出的OP算例，將它們擴(kuò)展成GOPVP實(shí)例，并分別命名為setW、setT和setC.

setW算例(起止點(diǎn)相同)為中國東部27個城市，其位置坐標(biāo)為城市對應(yīng)的經(jīng)緯度，每個城市間的距離根據(jù)經(jīng)緯度計(jì)算.算例中，城市具有4個不同類型的評分.在現(xiàn)實(shí)應(yīng)用中，不同的類型可以表示旅游規(guī)劃中城市的各種旅游特色，也可以表示低溫冷鏈物流中各種物資類別.

setT和setC是兩個經(jīng)典的OP算例，其原始數(shù)據(jù)及改造數(shù)據(jù)被研究者們廣泛應(yīng)用.setT包含3個不同的點(diǎn)集，個數(shù)分別為21、32、33.setC算例包含兩個不同的點(diǎn)集，個數(shù)分別為64、66.每個點(diǎn)集都有多個不同的Tmax.在setT和setC中，路徑的起止點(diǎn)不同，點(diǎn)之間的距離采用歐氏距離.由于算例中每個點(diǎn)僅有一個類型的收益，因此本文擴(kuò)展這兩個數(shù)據(jù)：隨機(jī)打亂點(diǎn)集收益值，形成新的收益序列.重復(fù)3次，構(gòu)造多類型數(shù)據(jù).

本文目前的實(shí)驗(yàn)中假設(shè)了各類型收益均隨時間呈線性下降，其函數(shù)形式為fig(ti)=sig(0)-αti,i∈V,g=1,2,…,m，且fi1(ti)=fi2(ti)=…=fim(ti)，其中：α=sig(0)/Tmax；sig(0)為點(diǎn)i在第g個類型上的初始收益.更一般性的收益下降函數(shù)有待進(jìn)一步研究.

3.1.2對比方法 在3個不同的算例上，與本文提出的改進(jìn)的遺傳算法(improved genetic algorithm，IGA)對比的研究進(jìn)展算法為nGA算法和2PIA算法.

1) nGA算法.Zabielski等[9]基于GA的OP求解算法，采用了錦標(biāo)賽的選擇算子，并綜合采用了插入、刪除和逆轉(zhuǎn)的變異算子.

2) 2PIA算法.Silberholz等[5]提出的兩參數(shù)迭代算法，采用了逆轉(zhuǎn)、插入和刪除的局部搜索操作.

3.1.3參數(shù)設(shè)置 對比方法采用原文參數(shù)設(shè)置.IGA的相關(guān)參數(shù)設(shè)置如下：迭代次數(shù)T為50，沒有改善的迭代次數(shù)限制為5，種群大小Psize為50，選擇操作中分組個數(shù)num為5組，交叉操作隨機(jī)選擇15對父代進(jìn)行操作，變異操作中隨機(jī)個體數(shù)占種群大小的10%，其中插入和刪除變異概率都為0.5.

此外，本文以單位時間間隔分割最大時間限制Tmax(由于距離和時間轉(zhuǎn)換簡單，本文對測試實(shí)例中的邊權(quán)耗費(fèi)不做區(qū)分)，并預(yù)先存儲各結(jié)點(diǎn)在不同時刻的收益，以加速計(jì)算.為了消除各算法隨機(jī)性帶來的影響，本文將每個算法在各個數(shù)據(jù)上分別進(jìn)行10次獨(dú)立重復(fù)實(shí)驗(yàn)，取10次運(yùn)行結(jié)果的最大值和均值進(jìn)行比較，同時比較各算法求得結(jié)果的標(biāo)準(zhǔn)差，驗(yàn)證本算法的穩(wěn)定性.

3.2 實(shí)驗(yàn)結(jié)果及分析

3.2.1setW 類似于文獻(xiàn)[5]，本文測試目標(biāo)函數(shù)中5個不同的目標(biāo)函數(shù)指數(shù)k分別為1，3，4，5，10，對不同的k值分別考慮5個不同的類型權(quán)重wv(0:[0.25,0.25,0.25,0.25]，1:[1,0,0,0]，2:[0,1,0,0]，3:[0,0,1,0]，4:[0,0,0,1])，Tmax均為5 000.

在25組測試實(shí)驗(yàn)中，本文分別比較了3個算法求得的目標(biāo)函數(shù)均值和最大值，結(jié)果如表1所示.從表中可以看出，在最大值和均值上，文本的IGA算法全部都達(dá)到了最優(yōu)值.setW的仿真實(shí)驗(yàn)表明，相比對比方法，在不同目標(biāo)函數(shù)指數(shù)和類型屬性權(quán)重組合下，仍能夠保持較好的尋優(yōu)求解優(yōu)勢，體現(xiàn)了較強(qiáng)的尋優(yōu)能力.

3.2.2setT、setC 由于測試實(shí)例過多，對setT和setC，本文僅實(shí)驗(yàn)指數(shù)k為2，類型權(quán)重為(0.25,0.25,0.25,0.25)的目標(biāo)函數(shù).setT算例共有49組不同的實(shí)驗(yàn)，setC算例共有40組不同的實(shí)驗(yàn).3種算法的求解結(jié)果比較分別如表2和表3～5所示，表中n為算例中點(diǎn)的個數(shù)，Tmax為最大時間限制.在數(shù)據(jù)集setT和setC上，同樣比較各算法求解目標(biāo)值的均值和最大值.

由表2和表3～5可知，本算法能適應(yīng)不同點(diǎn)集大小和時間限制的組合，在大部分組合中，IGA求得的目標(biāo)最大值和均值都取得了明顯的優(yōu)勢.在均值比較上，當(dāng)n=32時，2PIA取得了和本文算法相當(dāng)?shù)男Ч?，且均?yōu)于nGA.在整個setT數(shù)據(jù)集的49個算例上，本文取得了39次最優(yōu)結(jié)果，并且在setC上全部取得最優(yōu)，遠(yuǎn)遠(yuǎn)超過2PIA和nGA.在最大值比較上，2PIA和nGA在setT仿真實(shí)驗(yàn)上都僅取得6個最優(yōu)解，在setC上都僅取得5個最優(yōu)解，而本文的IGA算法則全部達(dá)到了最優(yōu)，進(jìn)一步證明了改進(jìn)算法的優(yōu)越性.

表1 setW 算例實(shí)驗(yàn)結(jié)果Tab.1 Result of setW

表2 setC實(shí)驗(yàn)結(jié)果Tab.2 Result of setC

表3 setT實(shí)驗(yàn)結(jié)果Tab.3 Result of setT

3.2.3穩(wěn)定性分析 為了驗(yàn)證IGA算法的穩(wěn)定性，本文采用標(biāo)準(zhǔn)差作為評價(jià)指標(biāo)進(jìn)行比較，如表6所示，其中n為算例中點(diǎn)的個數(shù).表中的結(jié)果為算法在該算例集不同實(shí)驗(yàn)方案標(biāo)準(zhǔn)差的平均值.從表中可以看出，在setW、setT和setC 3個算例集上，IGA求解結(jié)果的標(biāo)準(zhǔn)差都比較小，且均顯著優(yōu)于其他算法.在setW和setT上，IGA求解結(jié)果的標(biāo)準(zhǔn)差接近0，表明算法每次獨(dú)立實(shí)驗(yàn)幾乎都能找到最優(yōu)解.從實(shí)驗(yàn)結(jié)果可知，與2PIA和nGA相比，IGA具有更好的穩(wěn)定性.

表4 setT實(shí)驗(yàn)結(jié)果Tab.4 Result of setT

表5 setT實(shí)驗(yàn)結(jié)果Tab.5 Result of setT

表6 不同算法的標(biāo)準(zhǔn)差對比結(jié)果Tab.6 Comparison of standard deviation for different algorithms

4 結(jié)論

考慮帶有多類型和收益(價(jià)值等)隨時間變化特點(diǎn)的實(shí)際應(yīng)用場景，本文提出了一類收益可變泛化定向問題，并建立了相應(yīng)的數(shù)學(xué)模型.設(shè)計(jì)了一種改進(jìn)的遺傳算法來解決該模型，采用分組競爭機(jī)制在全體種群中搜索優(yōu)勝解，不僅保持了解的多樣性，同時保持了解的優(yōu)良性.再通過基于收益可變特點(diǎn)的變異算子，進(jìn)一步加強(qiáng)了解的質(zhì)量.

為了評估提出算法的有效性和穩(wěn)定性，在3個擴(kuò)展的數(shù)據(jù)集上進(jìn)行測試.由仿真實(shí)驗(yàn)可知，提出的算法，相比于研究進(jìn)展方法，能找到更優(yōu)的可行解.同時由標(biāo)準(zhǔn)差分析可知，本算法具有更好的穩(wěn)定性.

更多實(shí)際特征是接下來考慮的因素之一，如時間窗[12]和時間依賴[16]等.此外，對于大規(guī)模應(yīng)用場景，進(jìn)一步改進(jìn)算法，快速求得高質(zhì)量的可行解是下一步的研究工作.