融合盈虧拿取策略的改進遺傳算法求解TTP

關鍵詞：旅行商問題；背包問題；旅行小偷問題；改進遺傳算法；盈虧拿取策略中圖分類號：TP301.6 文獻標志碼：A 文章編號：1001-3695（2025）08-021-2408-08doi：10.19734/j. issn.1001-3695.2024.12.0489

Improved genetic algorithm incorporating profit-loss picking strategy for solving TTP

Jiang Xiaojua，b，c，TanDailuna，b，c?，Feng Shiqianga，b，c （aSchoolofthaicamp;foatonCsamp;UesiKboatofOiAsie ofNonlinear Analysis amp; Applications，China WestNormal University，Nanchong Sichuan 637o09，China）

Abstract：TTPisanew typeofcombinatorialoptimizationproblem，which iscomposedof TSPandKP.Itsoptimizationmodelcovers theconstraintsofthetwokindsofproblemsandalsoinheritsthecomputationaldifiultyof thetwo kindsof problems.To solvetheTTP，thispaper proposedanimprovedgeneticalgorithm incorporating profit-losspicking strategy.Forthe listof itemsontheroadofanytraveler，itdefinedthevalueitemsandadoptedthe must-takestrategy，definedtheloss items fortheremaining itemsandeliminated them，introducedthedoublescorecalculation formulafortheeliminatedremaining items，andconductedcomprehensivesortingaccording tothemixed sorting strategy，andthenselected themintothebackpack inorder.Thewhole procesingproessconstitutedtheprofit-loss takingstrategyForthegeneticalgorithm，thispaper designedthestrategyofpopulation initializationbasedonnarestneighborsearchandtruncationexchange to improvethequalityoftheinitialpopulation.Itusedthestochasticuniversalsamplingselectionoperator，thepartialmatchingcrossoveroperator andthesecondarymutationoperatortostrengthensurvivalofthefitestandmaintainthediversityofthepopulation.Itadded reinsertionoperatorsto keep thepopulation stable.Thesimulationresultsshow thattheimprovedstrategycanobviously improvetheperformanceof thealgorithm，andtheresultof theexamplereachestheexpectation.Theimprovedalgorithmhas good optimization ability and stability.

Key words：traveling salesman problem（TSP）;knapsack problem（KP）；travel thief problem（TTP）;improved genetic algorithm；profit-loss picking strategy

0 引言

旅行小偷問題（TTP）是組合優化領域一個有趣且具有挑戰性的問題。該問題結合了旅行商問題（TSP）和背包問題（KP）的特點，要求小偷訪問一系列地點，并在每個地點選擇性偷取一些物品裝進租來的背包，使得總價值最大且不超過背包的容量限制。TTP不僅可以作為理論研究的對象，探討各種優化算法在解決復雜組合優化問題上的性能和實用性，還可以在實際應用中發揮重要作用，例如在垃圾清運[1]、車輛調度[2]供應鏈管理[3]等問題上提供一些參考和啟示。

2013年，Bonyadi等人4發現組合優化中存在多個子問題相互依賴的現象，為了研究此類問題的復雜性，引入了TTP并舉出一個包含四個城市和五個物品的實例，形象地揭示了TTP中兩個子問題之間緊密且復雜的關聯關系。此后，很多學者對其進行了大量的研究。由于TTP的計算復雜度高，難以運用精確算法求解，主要采用啟發式算法和智能優化算法求解。Polyako-vskiy等人[5]基于分步求解TTP子問題的思路，提出了簡單啟發式算法和兩種迭代啟發式算法：隨機局部搜索和（1+1） 進化算法。Bonyadi等人[6提出了一種協同進化方法，使TSP與KP子問題在求解的過程中相互影響，以此獲得TTP的最優解。Mei等人[7]也提出了一種協同進化算法，其在處理子問題時不考慮子問題之間的相互作用。之后，Mei等人還提出了一種基于兩階段局部搜索的模因算法，用于求解規模較大的TTP實例。Faulkner等人[9]提出了單一解啟發式算法，首先利用鏈式LK啟發式規則處理TSP，再利用迭代貪婪策略求解 KP，最后將兩個子問題的解復合得到TTP的解。Wagner[10]把對TTP的研究重點放在了行走路徑的改進上，提出了基于蟻群優化的群智能算法來求解TTP。EIYafrani等人[11]針對TTP，提出了兩種啟發式算法：a）結合了2-opt局部搜索算子和基于模擬退火的打包啟發式算子；b）結合了2-opt局部搜索算子和位翻轉局部搜索算子。Maity等人[12]提出了混合局部搜索啟發式算法，先借助鏈式LK算法優化TSP路徑，然后在固定路徑上采用物品拿取啟發式規則來求解KP子問題。從整體求解TTP的思路出發，Mei等人提出了模因算法，在求解效果上，模因算法要比協同進化算法更優。Alharbi等人[13]引入了一種改進人工蜂群算法，該算法以相互依賴的機制求解TTP。Vieira等人[14]采用了多分量遺傳算法求解TTP，每個部分都被編碼，應用基本的交叉算子和變異算子進行遺傳進化。Wu 等人[15]對固定路徑下背包租金對TTP求解難度進行了理論研究。此外，馬梅等人[16]針對物品分布信息不明確的情況，構建了一個優化物品概率分布的新的TTP模型，并提出了一種混合遺傳算法作為解決方案。朱志翔[17基于物品分布提出了求解雙目標TTP的粒子群算法。Xiang等人[18]提出了一種基于多策略融合的多目標五元循環優化算法來解決雙目標TTP。Herring等人[19]研究了雙目標動態TTP，并提出了一種解決該問題的響應式種群播種算法。

總體上，現有文獻中，采用啟發式算法時需要依賴所構造的啟發式規則，通用性和靈活性不高；采用智能優化算法時，主要側重于對TSP子問題作路徑優化，對KP子問題的背包物品拿取策略及其路徑的協同方面探討較少。對此，本文選取通用性高、魯棒性強、具有并行搜索能力的遺傳算法進行改進，著重設計了近鄰域搜索和截斷交換策略來改進種群初始化，采用隨機遍歷抽樣作為選擇算子；同時針對KP子問題，定義了與當前TSP路徑協同的動態變化的“超值物品”與“虧本物品”，旨在評估不同物品對總收益的貢獻度，盡可能地把超值物品全部拿完，同時把虧本物品排除在外，以此構成背包物品的盈虧拿取策略。在仿真實驗中，選取了10個TTP算例，進行了改進策略的消融實驗和算法整體的迭代尋優計算，求解結果達到預期，算法改進提升效果明顯。

1TTP與數學模型

一般地，TTP可以描述為：一個小偷攜帶一個租賃的有容量限制的背包，計劃遍歷若干個城市（城市之間的距離已知），每個城市過且只過一次;除起點城市外，其余每個城市都放有數量不等的物品（物品的價值和重量已知），小偷經過某個城市時可以拿取一定數量的物品裝入背包，也可以不拿；初始時，小偷以最大速度開始行走，之后其行走速度與背包的重量成反比，而背包的租賃費與背包的重量成正比。為此，小偷需要規劃一條最佳路線和物品拿取策略，使得遍歷所有城市后能獲得最大凈收益。

根據上述問題描述，設有以下符號和變量。

V={1，2，…，n} n 個城市的序號集，起點城市為1；

d_ij ：城市 i 到 j 的距離；

M_i={1，2，…，m_i} ：城市 i 上放置的物品（ i≥2 ）；

p_ik，w_ik ：城市 i 上第 k 個物品的價值和重量；

W，W_i，C ：背包的容量和小偷離開城市 i 時背包的重量以及單位時間的租金;

max，Umin：小偷的最大和最小行走速度；

：小偷行走速度隨重量的最小變化量；

x_ij={0，1} ：小偷旅行路徑的決策變量，若小偷要從城市i到 j 則為1，否則為0;

y_ik={0，1} ：小偷拿取物品的決策變量，若小偷在城市 χ_i 要拿取第 k 個物品則為1，否則為0。

TTP的數學模型可表示為

u_i-u_j+nx_ij?n-1，?u_i，u_j∈R;i，j∈V

v_i=v_max-ηW_i，i∈V

x_ij={0，1}，i，j∈V

其中：式（1）是總凈收益最大的目標函數；式（2）（3）保證了對于任意一個城市，小偷只能從一條邊進人，也只能從一條邊離開；式（4）用于消除子回路；式（5）表示小偷從城市 χ_i 到 j 所用的時間；式（6）表示小偷從城市 i 到 j 的行駛速度；式（7）表示小偷遍歷所有城市所拿取的物品總重量不超過背包的容量；式（8）是小偷旅行路徑的決策變量;式（9）是小偷拿取物品的決策變量。

2傳統遺傳算法

遺傳算法（geneticalgorithm，GA）由Holland教授首次提出[20]，也被稱為傳統遺傳算法，是一種模擬生物種群進化過程的智能優化算法[21]。受到生物進化論中自然選擇、遺傳、交叉和突變等現象的啟發，GA構建了種群個體的選擇、交叉和變異三個主要環節。通過不斷迭代進化，持續優化種群，直至收斂。GA的基本步驟為：

a）確定染色體編碼方案。常用的有自然數編碼、二進制編碼等。通常，應根據組合優化問題的可行解特征選擇合適的編碼方案。b）種群初始化。根據染色體編碼方案，以隨機的方式生成初始種群。c）個體評價。采用恰當的適應度函數，計算種群個體的適應度值，由此評估種群個體的優劣。d）選擇操作。根據個體的適應度，按照某種方法從父代種群中優選一部分個體構成子代種群，常用的選擇方法有輪盤賭選擇、錦標賽選擇等。e）交叉操作。根據交叉概率以隨機方式使父代種群個體之間進行基因的交換，生成新個體以構成子代種群，模擬了嫁接等生物培育現象。f變異操作。根據變異概率，使用變異算子對個體的某些基因位進行處理，使其突變為新的個體。g）終止進化判斷。若進化代數未達到最大迭代次數，則重復步驟c）～f，反之，則終止進化。

傳統遺傳算法存在收斂速度慢、易陷入局部最優等缺點，但其步驟清晰且每個環節允許自行設計。因此，為了提升算法的整體性能，需要對上述各個步驟進行改進。

3盈虧拿取策略

基于小偷行走過程中背包最差狀態和最好狀態下對旅行商回路上所有物品的預期收益進行評估，以此定義超值物品和虧本物品，然后給出盈虧拿取策略。

3.1 超值物品

對任意給定的旅行商回路，各個城市及其物品的先后順序也相應確定。此時，對城市i上第 k 個物品，可以將其價值 p_ik 與剩余路程背包租金的變化量相比較來衡量它是否具有更高價值，這里的變化量是指在剩余路程中該物品若拿取或不拿取時背包租金的差值，并且考慮剩余路程取最差的情況，即在城市 i 時背包已經裝滿。

記剩余路程長度為 ，則拿取或不拿取該物品走完剩余路程所花時間的計算公式分別為

則剩余路程中背包租金差值的計算公式為

Δr_ik^（1）=C（T′_i1-T_i1）

由此，任意一個物品若在最差情況下行走剩余路程時仍能對背包總凈收益有正的貢獻，則稱該物品為“超值物品”，其計算公式為

Δp_ik^（1）=p_ik-Δr_ik^（1）

對超值物品的識別，有助于針對給定的旅行商回路，動態地選取最有價值的物品，而不至于遺漏，在算法中可以增強尋優能力，加快收斂速度。

3.2 虧本物品

類似地，對任意旅行商回路上城市 i 的第 k 個物品，考慮剩余路程為最好情況（即背包為空），計算在剩余路程中該物品拿取或不拿取時背包租金的差值，若該差值大于物品價值p_ik ，表明該物品即使在最好情況下，也對背包產生了負的凈收益，因此稱其為“虧本物品”。

虧本物品的計算公式如下：

Δr_ik^（2）=C（T_i1^′-T_i1）

Δp_ik^（2）=p_ik-Δr_ik^（2）

對給定旅行商回路上虧本物品的識別，有助于避免其被添加進背包造成的損失，加快了算法的收斂速度。

3.3構建盈虧拿取策略

基于所定義的超值物品和虧本物品，本文構建了一種隨路徑動態變化的盈虧拿取策略，使得小偷在給定旅行商回路上既能拿到最有價值的超值物品，也能避免拿到造成損失的虧本物品，從而在整個回路上獲得更大凈收益，該策略分為四個步驟。

a）通過算法1識別超值物品，將它們全部選入背包。

算法1 識別超值物品

輸入：旅行商回路 tour=（v₁，v₂，…，v_n，v₁） ，城市距離矩陣 D= （204號0 （d_ij） ；各城市物品列表 ;小偷的最大和最小行駛速度 v_max?v_min ;背包容量和單位時間租金 W，C （204

輸出：超值物品列表 PO

POO;L_i10 （2號

η（v_max-v_min）/W

11 按城市序列逐一查找超值物品

for i= 2 to n do

//計算城市 i 之后的剩余路程長度L_i1L_i1+D（tour（i），tour（i+1）） //識別城市 χ_i 中的超值物品for k= 1 to m_i do //拿取物品時T_i1^′L_i1/（v_max-ηW） /／不拿取物品時（204號 //剩余路程背包租金差值 物品的預期收益證 Δp_ik^（1）gt;0 thenPOk// 將 HI 中的物品 k 添加到 PO （204endifend forend for

b）對除超值物品外的剩余物品，通過算法2識別虧本物品并剔除。

算法2識別虧本物品

輸入：旅行商回路 tour=（v₁，v₂，…，v_n，v₁） ；城市距離矩陣 D= （d_ij） ;剩余物品列表 ;小偷的最大和最小行駛速度 ;背包容量和單位時間租金 W，C （204

輸出：虧本物品列表 PL

PL?;L_i10

η（v_max-v_min）/W

11 按城市序列逐一查找虧本物品

for i=2 to n do11 計算城市 i 之后的剩余路程長度L_i1L_i1+D（tour（i），tour（i+1）） （20//識別城市 i 中的虧本物品for k= 1 to m_i do（20 //拿取物品時T_i1L_i1/v_max// 不拿取物品時 ） 11 剩余路程背包租金差值Δp_ik^（2）←p_ik-Δr_ik^（2）// 物品的預期收益if Δp_ik^（2）lt;0 thenPLk// 將 HI 中的物品 k 添加到PLendifend for

end for

c）對剔除虧本物品后的剩余物品按式（18）（19）分別進行

評分，再按算法3進行綜合排序。

為了避免僅依賴單一評分公式導致算法陷入局部最優的困境，采用了兩種不同的評分公式對剩余物品進行評估。這里用到的第一種評分公式由Mei等人[8]提出，其首要原則是選取價值高且不會顯著減緩旅行速度的物品，將它們裝進背包，從而評估整體的收益效果。評分公式如下：

為了避免算法陷入局部最優，引入了Faulkner等人[9提出的另一種評分公式作為補充，以此對物品的選擇優先級進行策略性的擾動。其評分公式如下：

其中 ：β=4.5 。第二種評分公式的影響因素只有物品的價值、重量以及拾取物品所在城市到終點城市的路徑長度，沒有其他的影響因素，能夠減少第一種評分公式對物品選取的局限性。

算法3混合概率排序

輸入：旅行商回路 tour=（v₁，v₂，…，v_n，v₁） ；按照式（18）進行降序排列的物品列表 HV ；按照式（19）進行降序排列的物品列表 HD ；選擇概率p。

輸出：新的物品排序序列 H

H?，q₁1，q₂1

for k= 1 to m dorandom r∈[0，1] if r

1） //將 HV 中第 q₁ 個物品添加到 H //將此物品在 HD 中剔除91q1+1elseHHD（q₂）// 將 HD 中第 q₂ 個物品添加到 H 11 將此物品在 HV 中剔除9292+1end if

end for

d）依據物品排序序列 H ，將物品逐一選入背包，直至達到背包容量上限為止。

4改進遺傳算法

本文結合TTP對傳統遺傳算法進行了針對性改進，設計了融合盈虧拿取策略的改進遺傳算法（improvedgenetic algo-rithm incorporating profit-losspicking strategy，PLPS-IGA）。

4.1 染色體編碼

在遺傳算法中，編碼方案決定了如何對個體實施遺傳算子，影響著算法的性能和效果。針對TTP的行走路徑，以城市序號作為基因點，采用無重復的自然數編碼方案。各基因點之間的順序表示小偷訪問各個城市的先后順序。

4.2改進種群初始化

由于TTP融合了TSP和KP的復雜度，如果采用隨機初始化方法生成種群往往會產生大量質量較低的個體，需要花費較長時間對其進行優化；而采用啟發式初始化方法，又會破壞種群多樣性，加大算法陷入局部最優的風險。為了使路徑種群在初始化階段盡可能生成較高質量的個體，還能夠在一定程度上維持種群多樣性，本文在種群初始化時引入近鄰域搜索策略（nearest neighbor，NN）[22]。這一策略主要體現了貪心思想，把任意一個城市作為起點，選擇距離當前城市最近且尚未訪問的城市作為下一個目的地。重復此過程，直至所有城市都被添加到初始種群中。

采用NN策略生成的路徑起點是隨機的，但TTP要求旅行必須從編號為1的城市出發。對此，引入截斷交換策略[23]對初始種群中每個個體的起點進行修復。如圖1所示，首先在個體中找到編號為1的基因位置，并以此為斷點將個體截斷為兩個基因片段；然后交換這兩個片段的位置；最后組合成一個新的個體，新個體旅行路徑的起點正好是編號為1的城市。

圖1截斷交換策略示例

4.3適應度函數

遺傳算法的適應度函數在優化問題中負責評估個體及整個種群的性能優劣。針對TTP的求解目標是找到一條最優路徑以及最優的物品裝包方案，從而確保旅行結束時能獲取最大化的總凈收益。因此，本文算法的適應度函數取小偷旅行結束時的總凈收益。即對種群的任意個體而言，其適應度為

由適應度函數可知，當適應度值越大，小偷獲取的總凈收益越高，那么該個體就越優。

4.4隨機遍歷抽樣選擇算子

選擇的根本目的是從初始種群中選出表現優秀的個體，使它們能夠進人下一代，并有機會擔當繁衍新個體的父代角色。在這一選擇過程中，個體被選中概率大小直接與其適應度值的高低掛鉤，體現了“優勝劣汰”的自然法則。本文采用隨機遍歷抽樣（stochasticuniversal sampling，SUS）算子[24]進行選擇操作。隨機遍歷抽樣算子是一種改進的輪盤賭選擇，它不僅確保了每個個體都有被選中的機會，而且通過其獨特的等間距抽樣機制，降低了選擇偏差，使得適應度較低的個體也有一定的入選機會，從而維護了種群的多樣性。此外，隨機遍歷抽樣算子相對輪盤賭選擇具有更高的效率，在需要選擇多個個體時，輪盤賭選擇需要多次轉動轉盤，而隨機遍歷抽樣算子只需要轉動一次轉盤便可以得到需要選擇的所有個體。

隨機遍歷抽樣選擇算子的處理步驟為：

a）計算指針的間距 P ，即總適應度值 F 除以需要選擇的個體數目 N b）隨機生成起點指針位置start，該位置在0到 P 之間的隨機數范圍內。c）計算各指針的位置，即start加上 i 乘以 P （其中 i 從0到N-1 ）。d）根據各指針位置選擇出 N 個個體。

4.5 部分匹配交叉

交叉操作旨在通過結合不同父代個體的遺傳信息，生成新的子代個體。在實施交叉操作之前，將父代種群中的個體進行前后兩兩配對。本文采用的是部分匹配交叉算子。如圖2所示，首先，在兩個父代個體的基因序列上隨機產生兩個交叉點，這兩個點之間的基因片段將參與交叉；然后，在這兩個交叉片段內建立一個部分匹配的映射關系，即確定兩個交叉片段內基因位置的對應關系；最后，依據此映射關系將父代A中交叉片段的基因按照父代B中相應基因的順序重新排列，形成第一個子代個體的該部分基因序列，同理生成第二個子代個體的相應部分，對于未參與交叉的基因片段，則直接繼承各自的父代。

圖2部分匹配交叉算子示例

Fig.2Example of partial matching crossover operatol

4.6 二次變異

在遺傳算法中，變異操作不僅維持了種群的多樣性，還是算法能夠突破局部最優解、有效避免早熟收斂的關鍵機制。本文對待變異個體依次施行了基因互換和片段倒序兩種變異手段。如圖3所示，基因互換操作是指在待變異的個體上隨機產生兩個基因位置，然后將這兩個位置的基因進行互換，這一步驟初步增加了基因序列的多樣性。緊接著，片段倒序操作則在已完成基因互換的個體上隨機選取一個基因片段，并將其在原位置上執行倒序排列。通過依次運用這兩種變異策略，不僅顯著提升了種群的多樣性，還為算法探索更廣闊的解空間提供了可能，從而增強了遺傳算法的全局搜索能力和魯棒性。

圖3二次變異操作示例 Fig.3Example of secondary mutation operation

4.7 重插入算子

由于本文的選擇操作具有選擇概率，導致選擇操作后的種群與父代種群規模不一致。為此，在變異操作之后引入了重插入算子。具體來說，該算子是從父代種群中挑選一些優秀個體，并將它們補充到經過變異處理后的種群中，以確保當前種群規模與父代種群規模保持一致。對于父代種群中的優秀個體的選擇，遵循以下原則：一半選取父代種群中旅行商回路長度最短的個體，另一半則是父代種群中總凈收益最大的個體。

4.8算法流程

綜上，PLPS-IGA算法求解TTP的流程如圖4所示。

4.9 算法復雜度分析

PLPS-IGA的計算量包括：計算城市之間的距離矩陣、種群初始化、迭代過程中計算個體適應度值以及遺傳進化操作。計算距離矩陣和種群初始化的運算復雜度分別為 O（n²） 和O（N） ，其中 N 為種群大小。計算個體適應度值的復雜度為O（m?N） ，其中 ?_m 為物品數量。遺傳進化操作包括隨機遍歷抽樣選擇、部分匹配交叉、二次變異以及重插入操作。隨機遍歷抽樣選擇的運算復雜度為 O（N） ；由于需要遍歷交叉點之間的基因片段來建立映射關系，所以部分匹配交叉的運算復雜度為O（n） ；二次變異中基因互換操作的運算復雜度為 O（1） ，因為只需交換兩個位置的基因，片段倒序操作的運算復雜度為O（n） ，最終二次變異的運算復雜度為 O（n） ；由于要遍歷整個父代種群找尋最優個體，所以重插人算子的運算復雜度為O（N） 。距離矩陣的計算、初始化操作是在迭代之前完成，其復雜度為 O（n²） ，適應度值的計算以及遺傳進化操作是在迭代過程中執行，其復雜度為 O（N+n） ，因此，PLPS-IGA的運算復雜度為 O（n²+G?（N+n） ）。

4.10算法的種群多樣性分析

在遺傳算法中，種群的多樣性是算法避免早熟收斂，探索更廣闊解空間的關鍵。針對TTP，本文提出的PLPS-IGA通過以下幾點維持種群多樣性：a）引入近鄰域搜索策略進行種群初始化，能夠保證初始種群的質量，同時其隨機選擇起點的規則在一定程度上維持了種群多樣性;b）采用隨機遍歷抽樣算子進行選擇操作，不僅確保了每個個體都有被選中的機會，而且通過等間距抽樣機制降低了選擇偏差，使得適應度較低的個體也有一定的人選機會，有助于維持種群的多樣性；c）部分匹配交叉算子通過建立交叉片段內的映射關系，生成新的子代個體，增加了基因序列的多樣性;d）二次變異操作則通過基因互換和片段倒序兩種手段，進一步提升了種群的多樣性，為算法探索更廣闊的解空間提供了可能；e）從父代種群中挑選優秀個體重插入到變異后的種群中，既保證了種群規模的一致性，又通過保留父代中的優質基因信息，間接地維持了種群的多樣性。

與傳統遺傳算法相比，PLPS-IGA能夠有效避免早熟收斂、提高全局搜索能力以及增強魯棒性，在維持種群多樣性方面具有優勢。

4.11算法全局與局部尋優能力分析

解決像TTP這樣的復雜組合優化問題時，平衡好全局尋優與局部尋優的關系至關重要。本文PLPS-IGA通過近鄰域搜索、隨機遍歷抽樣選擇、部分匹配交叉等策略，確保了初始種群的質量和多樣性，降低了選擇偏差，并增加了種群在全局范圍內的探索能力，從而有效增強了全局尋優能力；同時，通過引入二次變異和重插入算子，算法在局部解空間內進行精細搜索，提高了局部尋優能力。這些策略的綜合運用，體現了算法設計的綜合性，是實現全局與局部平衡的關鍵。此外，適應度函數作為評價指標，引導算法在搜索過程中不斷逼近全局最優解，并在局部范圍內進行精細調整；參數調整的靈活性使得算法能夠根據具體問題需求在全局和局部尋優之間取得更好的平衡。因此，本文PLPS-IGA在解決TTP時，能夠表現出更高的性能和可靠性，實現了全局尋優與局部尋優的有效平衡。

5仿真實驗

根據Polyakovskiy等人[6]構建的TTP數據集可知每個數據集中的物品在價值與重量方面存在三種不同的關系類型，分別是物品的價值與重量完全無相關（uncorrelatedtype，UC）、物品的價值與重量強相關（bounded strongly correlated type，BSC）和物品重量相似，價值與重量無相關（uncorrelatedtypewithsimilarweights，USW）。本文選擇了eil51、berlin52、st70、eil76、rat99、 kroA100，pr124，ch130，ch150，lin318 共10個數據集中不同關系類型的算例進行實驗。

算法的參數設置如下：種群規模 N=100 ，迭代次數 G= 500，選擇概率 p_s=0.9 ，交叉概率 p_c=0.9 ，變異概率 p_m=0.1 。

5.1盈虧拿取策略消融實驗

為了驗證盈虧拿取策略的有效性，在本文算法中使用盈虧拿取策略與在KP中常用的價值密度拿取策略[25]形成對照，進行測試。所選算例為eil76和 ch150 ，測試結果如圖5所示。

圖5盈虧拿取策略消融實驗

根據圖5可知，經過500次迭代，PLPS-IGA在處理eil76和ch150這兩個算例時，采用盈虧拿取策略相較于價值密度拿取策略能夠獲得更高的總凈收益。尤其是在解決ch150算例時，盈虧拿取策略所獲得的總凈收益是價值密度拿取策略的10倍以上。從收斂速度上看，無論是算例eil76還是ch150，在迭代初期，算法的收益增長相對緩慢，但盈虧拿取策略在這一階段就展現出更強的收益增長潛力。在算法迭代到100代左右，盈虧拿取策略就已經趨于收斂并實現了遠高于價值密度拿取策略的總凈收益。這表明，盈虧拿取策略不僅在最終的總凈收益上優于價值密度拿取策略，而且在相同的迭代次數內，盈虧拿取策略能夠更快地找到更優的物品拿取方案，從而在實際應用中具有更高的效率和實用性。

5.2改進種群初始化消融實驗

為了測試近鄰域搜索的種群初始化策略的性能，體現出該策略的必要性，將其與隨機生成種群的初始化策略進行對比。所選算例為rat99和 ch130 ，測試結果如圖6所示。

由圖6可知，在種群進化初期，采用近鄰域搜索策略生成的個體相較于隨機生成的個體質量更優，有助于找到更好的初始解。在近鄰域搜索策略下，算法能夠更快地鎖定潛在最優解區域，從而減少不必要的搜索空間。種群在進化過程中的收斂速度也明顯快于隨機初始化策略，這使得算法在后續的迭代過程中能夠更快地收斂到全局最優解。這進一步驗證了近鄰域搜索策略的有效性，表明其在提升算法整體性能方面的優勢。

5.3二次變異消融實驗

變異操作是遺傳算法的一個重要組成部分，本文提出了基于基因互換和片段倒序的二次變異算子。為了測試二次變異算子的性能，體現出該操作的必要性，在本文算法中通過使用二次變異與使用基因互換變異算子形成對照。所選算例為berlin52與kroA100，測試結果如圖7所示。

由圖7可知，對算例berlin52和kroA100來說，盡管在前期進化過程中采用二次變異和基因互換變異得到的總凈收益差距很小，但隨著迭代次數的增加，凈收益逐步拉開差距。最終，經過500次迭代后采用二次變異得到的結果要比采用基因互換變異得到的結果更優。這一結果說明了二次變異不僅能夠保持種群的多樣性，還能更有效地引導種群向全局最優解收斂。相比之下，基因互換雖然也能產生新的解，但在探索解空間的深度和廣度上可能稍顯不足。從收斂速度上看，二次變異算子能在較少的迭代次數內達到更優的解，表現出了更快的收斂趨勢，提高了算法解決問題的效率。進一步驗證了二次變異算子在遺傳算法中的有效性與必要性。

圖6改進種群初始化消融實驗

圖7二次變異消融實驗 Fig.7Secondaryvariation ablation experiment

5.4重插入算子消融實驗

重插人算子是本文設計的一種局部尋優操作，為了驗證重插入算子的性能，將其與只插入路徑最短個體的重插入算子進行比較。所選算例為 st70 和 lin318 ，測試結果如圖8所示。

表1算法求解結果對比Tab.1Comparison of algorithm’s solution results

5.6 算法性能對比

5.5算法求解結果對比

為了對比分析PLPS-IGA與當前其他主流算法在TTP求解中的性能差異，在同一個算例但物品的價值與重量關系類型不同的情況下，將PLPS-IGA與算法SH、RLS、（ EA、MATLS、DH進行對比。

實驗數據選取了上述eil51、 Π_st70 、eil76、rat99四個數據集中物品的價值與重量關系類型不同的TTP算例，在相同的實驗環境中將各個算法分別獨立運行20次，記錄并計算出求解結果的平均值。這里對算法的求解結果進行了標準化處理，結果如表2所示。其中標準化處理公式為

由圖8可以看出，在遺傳進化中，若完全采用路徑最短個體重插入進化種群，不僅不能提升凈收益，反而導致凈收益一再下降，甚至降為負值。這是因為只考慮路徑最短會忽略路徑對物品拿取方案的影響，最終導致總凈收益下降。相反，當一半插入路徑最短個體，剩下的插人總凈收益最大個體時，結果呈現上升趨勢。從收斂速度上看，本文設計的重插入算子在迭代初期便能迅速接近最優解，收斂速度明顯快于只插入路徑最短個體的重插入算子。這表明，通過平衡路徑長度和凈收益，本文設計的重插入算子有效提升了算法的尋優能力。

為了驗證算法的整體效能，選取了在物品的價值與重量強相關的情況下的10個不同TTP算例進行實驗，并將PLPS-IGA的實驗結果與簡單啟發式算法（simple heuristic，SH）[5]、隨機局部搜索算法（random local search，RLS）[5]、 （1+1） 進化算法（ （1+1） evolutionary algorithm， （1+1）EA ）[5]基于兩階段局部搜索的模因算法（memetic algorithm with the two-stage localsearch，MATLS）[8]、基于密度的啟發式算法[6]（density-basedheuristic，DH）進行對比。實驗結果已匯總至表1中，該表詳細記錄了使用各個算法獨立進行20次計算后所得的總凈收益的平均值。同時，表1還基于這些平均值，對各個算法進行了排名。

從表1可以看出，PLPS-IGA在應對eil51、berlin52、st70、eil76、rat99、 pr124 、 ch130 和ch150這一系列算例時，展現出了卓越的性能，其求解結果優于表中列出的其他算法。盡管在求解kroA100和 lin318 這兩個算例時，PLPS-IGA沒有排在第一的位置，但也能保持次優的水平。這進一步證明了PLPS-IGA在解決TTP上的廣泛適用性和競爭力。隨著迭代的繼續，解的質量不斷提高，最終算法能夠在有限的迭代次數內找到接近最優的解，表明PLPS-IGA具有良好的收斂精度。從平均排名的角度來看，PLPS-IGA在所有參與對比的算法中表現最優。這一結果不僅充分驗證了PLPS-IGA在解決TTP上的可行性和有效性，更彰顯了算法在設計和優化方面的獨特優勢。

其中： P 是當前算法求解結果的平均值； P_max，P_min 表示所有解法中求解結果的最大平均值和最小平均值。

從表2可以看出，在物品重量相似、價值與重量無相關的情況下，PLPS-IGA僅對 st70 算例的求解結果略低于MATLS算法，而對其他算例的求解，PLPS-IGA均優于表中的其他算法。在物品價值與重量完全無相關的情況下，對于eil76和rat99這兩個算例，MATLS算法的性能略優于PLPS-IGA。在物品的價值與重量強相關的情況下，針對上述四個算例，PLPS-IGA的求解結果優于其他五種算法。綜合來看，PLPS-IGA在大多數情況下針對TTP的求解結果是優于表中列舉的其他算法的，這表明本文提出的PLPS-IGA性能更優。

表2算法性能比較

Tab.2Comparison of algorithm’sperformance

6結束語

本文針對由TSP和KP復合而成的TTP，提出了一種融合盈虧拿取策略的改進遺傳算法。該策略定義了超值物品采取必拿、虧本物品予以剔除的規則，并引人雙評分計算公式和混合排序策略對剩余物品排序選入背包。同時，為提升遺傳算法中初始種群的質量，設計了近鄰域搜索的初始化策略，并引入了隨機遍歷抽樣選擇算子、部分匹配交叉算子，設計了二次變異算子和重插入算子以維護種群多樣性和規模一致性，加快算法的收斂速度。對改進策略的消融實驗表明，相比于遺傳算法的常用算子，其搜索效率有明顯增強；對算法整體的仿真實驗表明，算法的求解精度和性能有明顯提升。考慮到遺傳算法搜索的隨機性，未來可以繼續分析本文改進策略的工作機制和效果，選用社會生產生活中諸如垃圾清運、車輛調度、供應鏈管理等具體實例加以應用和驗證。

參考文獻：

[1]Babaee TE，Goli A，Pahlevan M，et al.A robust bi-objective multitrip periodic capacitated arc routing problem for urban waste collection usinga multi-objective invasive weed optimization[J].Waste Management amp; Research，2019，37（11）：1089-1101.

[2]GuedesPC，Borenstein D，Visentini MS，et al.Vehicle scheduling problem with loss in bus ridership[J].Computersamp; Operations Research，2019，111：230-242.

[3]Zhang Yuzhou，Mei Yi，Huang Shihua，et al.A route clustering and search heuristic for large-scalemultidepot-capacitated arcrouting problem[J]. IEEE Transon Cybernetics，2022，52（8）：8286- 8299.

[4]Bonyadi MR，Michalewicz Z，Barone L.The traveling thief problem：the first step in the transition from theoretical problems to realistic problems [C]//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2013：1037-1044.

[5]Polyakovskiy S，Bonyadi MR，Wagner M，etal．Acomprehensive benchmark set and heuristics for the traveling thief problem[C]// Proc of Annual Conference on Genetic and Evolutionary Computation. New York：ACM Press，2014：477-484.

[6]Bonyadi MR，MichalewiczZ，Przybylek MR，etal.Socially inspired algorithms for the travelling thief problem[C]//Proc of Annual Conference on Genetic and Evolutionary Computation. New York： ACM Press，2014：421-428.

[7]MeiYi，Li Xiaodong，Yao Xin.On investigation of interdependence between sub-problems of the travelling thief problem[J].Soft Computing，2016，20（1）：157-172.

[8].Mei Yi，Li Xiaodong，Yao Xin. Improving efficiency of heuristics for thelarge scale traveling thief problem[C]//Proc of Asia-Pacific Conference on Simulated Evolution and Learning. Cham：Springer， 2014： 631-643.

[9]Faulkner H，Polyakovskiy S，Schultz T，et al.Approximate approaches to the traveling thief problem[C]//Proc of Annual Conference on Genetic and Evolutionary Computation. New York：ACM Press， 2015：385-392.

[10]Wagner M. Stealing items more eficiently with ants： a swarm intelligence approach to the travelling thief problem[C]//Proc of the 10th International Conference on Swarm Intelligence. Cham：Springer， 2016：273-281.

[11]El Yafrani M，Ahiod B.Population-based vs.single-solution heuristicsforthe travelling thief problem[C]//Proc of Genetic and Evolutionary Computation Conference.New York：ACMPress，2O16：317- 324.

[12]Maity A，Das S. Effcient hybrid local search heuristics for solving the travelling thief problem[J].Applied Soft Computing，2020，93： 106284.

[13]Alharbi S T.The design and development of a modified artificial bee colonyapproach for the traveling thief problem[J]. International Journal of Applied Evolutionary Computation，2018，9（3）：32-47.

[14]Vieira D K S，Soares G L，Vasconcelos JA，et al. A genetic algorithmformulti-componentoptimizationproblems：the case ofthetravelling thief problem[C]//Proc of the17th European Conference on Evolutionary Computation in Combinatorial Optimization. Cham： Springer，2017：18-29.

[15]Wu Junhua，Polyakovskiy S，Neumann F.On the impact of the renting rate for the unconstrained nonlinear knapsack problem [C]// Proc of Genetic and Evolutionary Computation Conference.New York：ACM Press，2016：413-419.

[16］馬梅，李和成．求解TTP問題新優化模型的混合遺傳算法［J]. 計算機工程與應用，2018，54（6）：156-160.（Ma Mei，Li Hecheng. Hybrid genetic algorithm for solving new optimization model of TTP [J].Computer Engineering and Applications，2018，54（6）： 156-160.）

［17］朱志翔．基于離散粒子群優化的行竊問題研究與應用［D]．成 都：電子科技大學，2020.（Zhu Zhixiang.Research and application of stealing problem based on discrete particle swarm optimization [D].Chengdu：University of Electronic Science and Technology of China，2020.）

[18]Xiang Yue，Guo Jingjing，Jiang Chao，et al.Multi-objective fiveelement cycle optimization algorithm based on multi-strategy fusion for thebi-objective traveling thief problem[J].Applied Sciences， 2024，14（17） ： 7468.

[19]Herring D，Kirley M，Yao Xin.A comparative study of evolutionary approaches to the bi-objective dynamic traveling thief problem[J]. Swarm and Evolutionary Computation，2024，84：101433.

[20]Holland JH. Genetic algorithms and theoptimal alocation of trials [J].SIAM Journal on Computing，1973，2（2）： 88-105.

[21］王永，呂致為．基于基因庫求解旅行商問題的遺傳算法［J]．計 算機應用研究，2023，40（11）：3262-3268.（WangYong，Lyu Zhiwei. Novel genetic algorithm based on genes pool for traveling salesman problem [J].Application Research of Computers， 2023，40（11）：3262-3268.）

[22]Agrawal A，GhuneN，Prakash S，et al.Evolutionaryalgorithm hybridized with local search and intelligent seeding for solving multiobjective Euclidian TSP[J].Expert Systems with Applications， 2021，181：115192.

[23］王玉．基于改進遺傳算法的旅行小偷問題研究［D]．南充：西華 師范大學，2023．（Wang Yu.Research of traveling thief problem based on improved genetic algorithm[D]. Nanchong：China West Normal University，2023.）

[24]Pencheva T，AtanassovK，Shannon A.Modelling of a stochastic universal sampling selection operator in genetic algorithms using generalized nets [C/OL]//Proc of the 1Oth International Workshop on Generalized Nets.（2009-12-05）.http：//ifigenia.org/wiki/issue： iwgn-2009-01-07.

[25］陳楨，鐘一文，林娟．求解0-1背包問題的混合貪婪遺傳算法 [J]．計算機應用，2021，41（1）：87-94.（Chen Zhen，Zhong Yiwen，Lin Juan.Hybrid greedy genetic algorithm for solving O-1 knapsack problem [J].Journal of Computer Applications，2021，41 （1） ： 87-94.）

收稿日期：2024-12-19；修回日期：2025-02-13基金項目：國家自然科學基金資助項目（42204123）；四川省自然科學基金資助項目（2022NSFSC0558）；教育部產學合作協同育人項目（202102454008）；四川省教育廳重點教改項目（JG2021-959）；研究生教育改革研究項目（2022XM24）

作者簡介：江曉菊（2001—），女，四川遂寧人，碩士研究生，CCF會員，主要研究方向為優化理論與應用；譚代倫（1971—），男（通信作者），重慶銅梁人，教授，碩導，碩士，主要研究方向為優化理論與應用（sxxalun@163.com）；馮世強（1980—），男，四川成都人，副教授，碩士，主要研究方向為優化理論與應用.