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

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

0 引言

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

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

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

1 問題描述與建模

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

引入如下標記.

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

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

GOPVP的數(shù)學模型為

(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)

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

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

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

2 算法求解

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

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

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

(8)

2.2 初始化種群

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

2.3 遺傳算子

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

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

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

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

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

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

d) 輪轉(zhuǎ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中點的收益可變，染色體基因的序列直接影響到個體的目標函數(shù)值.輪轉(zhuǎn)操作更詳細的例子如圖5所示.每個點有兩個類型的收益，且隨時間線性下降，如圖中f所示，最大時間限制Tmax為10.圖中菱形表示起止點，圓形表示待訪問點.假設(shè)目標函數(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ù)目標函數(shù)公式(1)計算，其總收益為46.5.圖5(b)中可行解為source-a-b-c-d-destination，其總收益為59.5.通過輪轉(zhuǎn)操作，可進一步提高解的質(zhì)量.

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

3.1 實驗設(shè)置

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

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

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

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

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

1) nGA算法.Zabielski等[9]基于GA的OP求解算法，采用了錦標賽的選擇算子，并綜合采用了插入、刪除和逆轉(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組，交叉操作隨機選擇15對父代進行操作，變異操作中隨機個體數(shù)占種群大小的10%，其中插入和刪除變異概率都為0.5.

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

3.2 實驗結(jié)果及分析

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

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

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

表1 setW 算例實驗結(jié)果Tab.1 Result of setW

表2 setC實驗結(jié)果Tab.2 Result of setC

表3 setT實驗結(jié)果Tab.3 Result of setT

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

表4 setT實驗結(jié)果Tab.4 Result of setT

表5 setT實驗結(jié)果Tab.5 Result of setT

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

4 結(jié)論

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

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

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