徐江 程美英

摘 要：針對現(xiàn)有共生生物搜索（SOS）算法在求解路徑規(guī)劃等離散型優(yōu)化問題時存在性能較差、收斂速度慢等問題，提出虛擬多任務共生生物搜索（VMTSOS）算法。首先根據(jù)雙向映射解碼策略，實現(xiàn)個體連續(xù)空間位置和離散城市序列轉(zhuǎn)換；然后引入多任務優(yōu)化思想構(gòu)建虛擬多任務環(huán)境，設(shè)計多種群同時優(yōu)化同一任務，并通過停滯閾值控制種群間信息遷移頻率，當主種群達到停滯閾值時，將輔助種群中部分優(yōu)秀個體替換為主種群劣質(zhì)個體；最后對VMTSOS算法時間和空間復雜度進行分析。仿真實驗表明，VMTSOS算法在求解多數(shù)TSP時均能快速收斂至各測試實例目前的最優(yōu)解，而在求解冷鏈物流配送問題時，具有多種群輔助機制的VMTSOS算法能較大程度地降低最優(yōu)總成本。

關(guān)鍵詞：共生生物搜索算法；多任務優(yōu)化；信息遷移；路徑規(guī)劃；冷鏈物流配送

中圖分類號：TP18?? 文獻標志碼：A?? 文章編號：1001-3695（2023）12-012-3599-07

doi：10.19734/j.issn.10013695.2023.04.0152

Virtual multitasking symbiotic organisms search algorithm for path planning problem

Abstract：Aiming at the problems of poor performance and slow convergence of existing symbiotic organisms search （SOS） algorithm in solving discrete optimization problems such as path planning，this paper proposed the virtual multitask SOS（VMTSOS） .Firstly，according to the bidirectional mapping decoding strategy，it realized the transformation between individual continuous spatial position and discrete city sequence.Secondly，it introduced the idea of multitask optimization to construct a virtual multitask environment，designed multiple populations to optimize the same task simultaneously，and the stagnation threshold controlled the frequency of information transfer between populations.Once the main population reached the stagnation threshold，it replaced some excellent individuals in the auxiliary population with inferior individuals in the main population.Finally，it analyzed the time and space complexity of VMTSOS.Experiment results show that VMTSOS converges rapidly to the current optimal solution of each test case when solving most TSP problems，while VMTSOS with multiple groups assistance mechanisms can greatly reduce the optimal total cost when solving cold chain logistics distribution problems.

Key words：symbiotic organisms search algorithm；multitask optimization；information transfer；path planning；cold chain logistics distribution

0 引言

路徑規(guī)劃是指在起點位置到終點位置之間找到一條最優(yōu)路徑或滿足特定約束條件的路徑過程，其廣泛應用于自動駕駛、機器人導航、物流運輸?shù)雀鱾€領(lǐng)域。文獻［1］使用PID控制器和遺傳算法優(yōu)化雙臂工業(yè)機器人路徑規(guī)劃，以實現(xiàn)能量最小化；文獻［2］利用混合遺傳算法為差動輪式機器人生成平滑路徑，以滿足路徑規(guī)劃任務中的安全和最小長度標準；文獻［3］引入基于改進避障策略和雙優(yōu)化蟻群算法優(yōu)化機器人路徑規(guī)劃，并有效應對多種碰撞情況；文獻［4］提出改進人工勢場蟻群算法，用于障礙物環(huán)境機器人路徑規(guī)劃等?，F(xiàn)有路徑規(guī)劃問題大多引入蟻群算法、遺傳算法及其改進算法進行優(yōu)化，而采用共生生物搜索算法對其求解的研究成果卻鮮有報道。

共生生物搜索（symbiotic organisms search，SOS）算法是一種群智能優(yōu)化技術(shù)［5］，通過模擬生態(tài)系統(tǒng)中生物之間互利共生、偏利共生和寄生關(guān)系來達到解決優(yōu)化問題的目的。其中，互利共生和偏利共生在產(chǎn)生新個體基礎(chǔ)上篩選出最優(yōu)個體，提高算法開發(fā)能力，而寄生階段通過變異個體寄生關(guān)系能避免陷入局部最優(yōu)，提高算法探索性能?，F(xiàn)有關(guān)于SOS算法的研究成果主要集中在兩方面：

a）改進SOS算法彌補其易早熟收斂的缺陷。文獻［6］在初始種群生成和寄生階段采用準對立學習理論，避免寄生階段過度探索；文獻［7］將差分進化算法與SOS算法相結(jié)合，有效增強SOS算法局部和全局搜索能力；文獻［8］引入自適應效益因子，并加入隨機加權(quán)反射系數(shù)和控制算子，提出一種基于自適應效益因子的改進SOS算法；文獻［9］提出一種基于多角色優(yōu)化策略的混合灰狼SOS算法，可減少無效搜索并保持SOS算法種群多樣性。

b）SOS算法解決實際優(yōu)化問題，如自動聚類［10］、云計算環(huán)境下最優(yōu)任務調(diào)度［11］ 、師生匹配［12］等問題。

多任務優(yōu)化概念最早由Gupta等人提出［13］，旨在挖掘群體智能算法隱并行性，并引入多因子優(yōu)化（multifactorial optimization，MFO）［13］或多種群演化（multipopulation evolution，MPE）［14］框架，通過任務之間的信息共享，達到同時優(yōu)化多個任務目的［15，16］。然而信息負遷移會抑制干擾多任務優(yōu)化性能，這也是目前尚未完全解決的難題之一［17］。受同時處理相似任務能顯著加速多任務收斂速度以及抑制信息負遷移消極影響啟發(fā)，文獻［18］引入輔助任務顯著降低主任務優(yōu)化難度。本文受此啟發(fā)，以SOS算法為多任務優(yōu)化依托算法，MPE為信息共享框架，為待求解任務配備輔助種群，主種群從輔助種群中獲利以促進待求解問題進化，提出虛擬多任務共生生物搜索（virtual multitasking symbiotic organisms search，VMTSOS）算法，并將其應用于旅行商問題和冷鏈物流配送等經(jīng)典路徑規(guī)劃問題中。本文主要創(chuàng)新點如下：

a）與現(xiàn)有求解路徑規(guī)范問題的生物啟發(fā)式算法相比，SOS算法只需簡單數(shù)學運算即可編碼，故穩(wěn)健性更強、收斂速度更快。SOS算法最初適用于連續(xù)域，而路徑規(guī)劃屬于離散優(yōu)化問題，本文創(chuàng)新性地在SOS算法中引入一種雙向映射解碼策略，將SOS算法中個體連續(xù)位置映射成離散節(jié)點（或城市）序列，使其適用于求解組合型路徑規(guī)劃問題，并能快速獲得較優(yōu)路徑。

b）引入虛擬多任務優(yōu)化思想，彌補SOS算法早熟收斂缺陷?；诙嗳蝿誐PE信息共享框架，創(chuàng)新性地為主任務配備輔助種群，主/輔種群或輔/輔種群在合適的節(jié)點相互遷移信息，在進一步促進SOS算法開發(fā)和探索平衡的同時，也能在一定程度上有效抑制信息負遷移。

c）創(chuàng)新性地將本文提出的VMTSOS算法應用于典型路徑規(guī)劃——冷鏈物流配送問題中，有效縮短物流配送時間，減少成本和碳排放總量。

1 基本SOS算法

SOS算法基本思想是在搜索空間中隨機生成若干生物個體，組成生物種群，每個生物個體代表問題的一個候選解，通過互利共生、偏利共生、寄生三階段不斷優(yōu)化個體，向全局最優(yōu)解靠近，具體描述如下：

1）互利共生階段

隨機選擇生物體xi與xj（i≠j），按式（1）（2）相互作用以增強它們在生態(tài)系統(tǒng)中相互依存的優(yōu)勢，若xnewi或xnewj優(yōu)于xi或xj，則取代之。其中，rand（0，1）為（0，1］的隨機數(shù)縮放因子，1和2分別為［1，2］的隨機數(shù)，表示互利共生生物間受益因子。

2）偏利共生階段

該階段與互利共生階段類似，隨機選擇個體xi與xj（i≠j），讓xi與xj在共生關(guān)系中獲利，但xj既不獲利也不受到傷害。若候選個體xnewi適應度值優(yōu)于原個體，則取代之，具體如式（3）所示。

xnewi=xi+rand（-1，1）×（xbest-xj）（3）

3）寄生階段

個體xi進行突變，引入隨機數(shù)修改xi部分維度上的參數(shù)，產(chǎn)生寄生個體xpv，隨機挑選生物體xj作為宿主，i≠j，若xpv適應度值優(yōu)于xj，則取代xj在種群中的位置。

2 求解路徑規(guī)劃問題的VMTSOS算法設(shè)計與分析

路徑規(guī)劃是一個經(jīng)典NPhard組合優(yōu)化問題，可描述為：假設(shè)有一個無向圖G=（V，E），其中V為節(jié)點集合，E為邊集合，節(jié)點v∈V代表一個位置，每條邊e∈E表示兩個位置間的連通性，每條邊有一個非負權(quán)重w（e），表示通過這條邊所需代價。給定起點s和終點t，構(gòu)造一個從s開始t結(jié)束的最優(yōu)位置向量。

2.1 VMTSOS搜索空間設(shè)置和編/解碼策略

2.1.1 VMTSOS搜索空間設(shè)置和編碼策略

假設(shè)規(guī)模為m的種群求解具有n個節(jié)點的路徑規(guī)劃問題，則搜索空間維度設(shè)為n。種群中i（i∈m）所對應的位置向量表示一個候選解。SOS算法最初用于求解連續(xù)型優(yōu)化問題，為適應路徑規(guī)劃類組合優(yōu)化問題求解，這里先采用自然數(shù)編碼，i（i∈m）隨機生成的n維序列（ζi1，ζi2，…，ζin）即為一個位置向量，根據(jù)雙向映射策略更新節(jié)點位置，促進個體進化。

2.1.2 VMTSOS雙向映射解碼策略

首先將離散位置序列（ζi1，ζi2，…，ζin）映射到SOS算法連續(xù)空間（xi1，xi2，…，xin），SOS算法按式（1）～（3）對個體位置（xi1，xi2，…，xin）迭代更新，然后將其反向映射回離散空間，形成一個新的路徑序列（ζnewi1，ζnewi2，…，ζnewin）。具體如圖1所示。

假如個體i、j和最優(yōu)個體best初始路徑序列分別為（3，5，1，2，4，0）（5，1，3，0，2，4）（4，5，3，1，2，0），若采用式（3）計算得到隨機數(shù)rand（-1，1）為0.12，則得到連續(xù)空間位置為（2.88，5.48，1.0，2.12，4.0，-0.48），將新序列（2.88，5.48，1.0，2.12，4.0，-0.48）中最小值-0.48所在位置索引5映射為新路徑序列中第1個位置值，次小值1.0所在位置索引2映射為新路徑序列中第2個位置值，依此類推，最終形成新路徑序列（5，2，3，0，4，1）。

2.2 VMTSOS信息遷移機制

本文虛擬多任務VMTSOS算法旨在引入輔助種群協(xié)助主任務進化，故構(gòu)建三個規(guī)模均為m的種群S1、S2、S3，其中S1為主種群，S2、S3為輔助種群，S1、S2、S3并行處理同一任務。起初S1、S2、S3獨立搜索，并且S1和S2在互利共生、偏利共生階段根據(jù)式（1）～（3）更新個體，而寄生階段參考變異算子更新機制，S3中個體則借鑒遺傳算法交叉和變異機制迭代更新。

在多任務環(huán)境中，種群間無關(guān)信息共享可能會傷害多任務優(yōu)化性能，進而阻礙整體收斂行為［19，20］。本文VMTSOS算法從如下兩方面遏制信息負遷移的消極影響：a）給主、輔種群分別設(shè)置合適信息遷移節(jié)點，一旦主種群停滯進化次數(shù)達到遷移節(jié)點閾值，則輔助種群S2和S3協(xié)助S1進化；同時為能持續(xù)向主任務輸送優(yōu)質(zhì)信息，一旦輔助種群S2或S3停滯進化，S2或S3之間也可交互信息；b）構(gòu)建基于優(yōu)秀個體的信息遷移方式，一旦主（或輔）種群產(chǎn)生信息遷移需求，則將輔助種群中的部分優(yōu)秀個體位置替換其劣勢個體，具體如圖2所示。

2.2.1 VMTSOS信息遷移節(jié)點設(shè)置

分別為種群S1、S2、S3設(shè)置停滯進化計數(shù)器SC1、SC2、SC3及停滯閾值Γ1、Γ2、Γ3。

這里以主種群S1為例，每次迭代后主種群S1根據(jù)式（4）將種群S1第t代最優(yōu)個體適應度fs1（t）和第（t-1）代最優(yōu)個體適應度fs1（t-1）進行比較，并更新停滯計數(shù)器SC1值。若SC1=Γ1，則主種群S1產(chǎn)生信息遷移需求，輔助種群S2、S3將主種群S1設(shè)置為目標任務，向主種群S1傳遞信息。

2.2.2 VMTSOS信息遷移方式

在VMTSOS中，種群S1、S2、S3之間信息遷移方式各不相同，具體分為以下兩個部分：

a）主/輔種群信息遷移。當主種群S1達到停滯閾值Γ1時，主種群S1產(chǎn)生信息遷移需求，先將種群S1、S2、S3中的個體根據(jù)適應度值由優(yōu)到劣進行排序，再分別選取輔助種群S2、S3中排名前1/3的優(yōu)秀個體位置序列替換主種群S1中排名后2/3劣勢個體位置序列，具體如圖3所示。

b）輔/輔種群信息遷移。若輔助種群S2（或輔助種群S3）停滯進化次數(shù)達到停滯閾值Γ2（或Γ3），則輔助種群S2（或輔助種群S3）產(chǎn)生信息遷移需求，先將種群S2、S3中個體根據(jù)適應度值由優(yōu)到劣進行排序，再分別選取輔助種群S3（或輔助種群S2）中部分優(yōu)秀個體位置序列替換輔助種群S2（或輔助種群S3）中部分劣勢個體位置序列。

2.2.3 局部搜索策略

在多任務環(huán)境中引入局部搜索可使得各任務快速逼近全局最優(yōu)解［14］，這里采用模擬退火（simulated annealing，SA）算法，其更新個體路徑序列方式是按一定概率，利用圖4～7中四大變異算子對種群S1、S2、S3中個體所對應的路徑序列進行擾動。假設(shè)當前個體路徑序列為（3，5，1，2，4，7，0，6）。

a）交換算子：隨機選擇路徑序列中兩個節(jié)點進行交換。如選擇節(jié)點1和7，則交換后個體路徑序列為（3，5，7，2，4，1，0，6）。

b）插入算子：隨機選擇路徑序列中的兩個節(jié)點，將第1個節(jié)點插入到第2個節(jié)點后。如選擇節(jié)點1和4，則插入后個體路徑序列為（3，5，2，4，1，7，0，6）。

c）反轉(zhuǎn)算子：隨機選擇路徑序列中的兩個節(jié)點，將兩個節(jié)點之間（包括自身節(jié)點）的所有節(jié)點進行反轉(zhuǎn)。如選擇節(jié)點1和7，則反轉(zhuǎn)后個體路徑序列為（3，5，7，4，2，1，0，6）。

d）3opt算子：隨機選擇路徑序列中的三個節(jié)點，把第1個和第2個節(jié)點之間（包括自身節(jié)點）的所有節(jié)點插入到第3個節(jié)點后。如第1、2個節(jié)點選擇1和4，第3個節(jié)點選擇0，則更新后個體路徑序列為（3，5，7，0，1，2，4，6）。

考慮到算法時間性能，在優(yōu)化過程中，主種群S1始終使用SA算法進行優(yōu)化，而輔助種群S2、S3只有當停滯進化次數(shù)分別達到Γ2/2、Γ3/2時，才開始使用SA算法進行局部更新。

綜上，VMTSOS算法偽代碼如下：

初始化種群規(guī)模為m、個體維度為n的主種群S1和輔助種群S2、S3，隨機生成個體路徑序列，并分別選取第1個個體作為各自種群當前全局最優(yōu)路徑序列。

while（未達到最大迭代次數(shù)）

for（遍歷種群S1中所有個體）

互利共生、偏利共生、寄生操作產(chǎn)生新個體路徑序列，評價其適應度值，優(yōu)則替換原個體路徑序列

if（SC1=Γ1）

分別將種群S1、S2、S3個體根據(jù)適應度值排序，并選取S2、S3部分優(yōu)秀個體替換S1部分劣質(zhì)個體

end if

end for

采用SA算法優(yōu)化主種群S1個體路徑序列

比較得出主種群S1當前全局最優(yōu)解fs1（t）路徑序列

if（fs1（t）=fs1（t-1））

SC1=SC1+1

else

SC1=0

end if

for（遍歷種群S2中的所有個體）

互利共生、偏利共生、寄生操作產(chǎn)生新個體路徑序列，評價其適應度值，優(yōu)則替換原個體路徑序列

if（SC2=Γ2）

分別將種群S2、S3個體根據(jù)適應度值排序，并選取S3部分優(yōu)秀個體替換S2部分劣質(zhì)個體

end if

end for

if（SC2=Γ2/2）

采用SA算法優(yōu)化輔助種群S2個體路徑序列

end if

比較得出輔助種群S2當代全局最優(yōu)解fs2（t）路徑序列

if（fs2（t）=fs2（t-1））

SC2=SC2+1

else

SC2=0

end if

for（遍歷種群S3中的所有個體）

使用交叉、變異、選擇操作更新個體路徑序列，評價其適應度值，優(yōu)則替換原個體路徑序列

if（SC3=Γ3）

分別將種群S2、S3個體根據(jù)適應度值排序，并選取S2部分優(yōu)秀個體替換S3部分劣質(zhì)個體

end if

end for

if（SC3=Γ3/2）

采用SA算法優(yōu)化輔助種群S3個體路徑序列

end if

比較得出輔助種群S3的當代全局最優(yōu)解fs3（t）路徑序列

if（fs3（t）=fs3（t-1））

SC3=SC3+1

else

SC3=0

end if

end while

輸出主種群S1中最優(yōu)適應度值fs1（t）路徑序列

2.3 VMTSOS算法復雜度分析

假設(shè)三個種群分別為S1、S2、S3，則Sp（p=1，2，3）種群規(guī)模為m，維度為n，VMTSOS算法最大迭代次數(shù)設(shè)為Maxiter，SA算法最大迭代次數(shù)為MaxiterSA，且Maxiter>MaxiterSA。

2.3.1 VMTSOS算法時間復雜度分析

由于VMTSOS算法包括三個種群，且內(nèi)部信息遷移操作之間略有區(qū)別，故而計算時間復雜度時需要分別討論。

1）主種群S1的時間復雜度Q1

（1）運行時間復雜度Q11的分析。

初始化m個個體路徑序列時間復雜度為O（m·n）；計算m個個體適應度值時間復雜度為O（m·n）；選擇第1個個體路徑序列作為當前主種群S1最優(yōu)個體路徑序列時間復雜度為O（1）；種群內(nèi)部實行互利共生、偏利共生、寄生操作時間復雜度均為O（m·n）；計算新個體適應度值時間復雜度為O（m·n）；通過互利共生、偏利共生、寄生操作生成新個體路徑序列適應度值與原個體路徑序列適應度值進行對比，時間復雜度分別為O（m）；主種群m個個體路徑序列執(zhí)行SA算法，其中的四大變異算子時間復雜度均為O（MaxiterSA·m·n）；計算SA算法中四大變異算子所得新個體路徑序列適應度值時間復雜度均為O（m·n）；將SA算法中四大變異算子所得新個體路徑序列適應度值與原個體路徑序列適應度值進行對比，時間復雜度均為O（m）；比較得出主種群S1全局最優(yōu)個體路徑序列時間復雜度為O（m）。由Maxiter>MaxiterSA可知，經(jīng)過Maxiter次迭代后得到Q11=O（Maxiter·m·n）。

（2）信息遷移時間復雜度Q21的分析

假設(shè)主種群S1停滯進化次數(shù)達到停滯閾值Γ1，則種群S1、S2、S3根據(jù)適應度值優(yōu)劣進行冒泡排序，時間復雜度分別為O（m2）；將輔助種群S2、S3中部分個體路徑序列替換主種群S1部分個體路徑序列時間復雜度分別為O（m/3）；個體路徑序列遷移后，選取主種群S1當前最優(yōu)個體路徑序列時間復雜度為O（m2）；其他操作時間復雜度為O（1）。假設(shè)算法在Maxiter次迭代過程中，共執(zhí)行了π1次信息遷移操作，則上述分析可以得出Q21=O（π1·m·n）。綜合（1）和（2）可得：

Q1=Q11+Q21=O（Maxiter·m·n）+O（π1·m·n）

由于Maxiter>π1，得出主種群S1的時間復雜度為Q1=O（Maxiter·m·n）。

2）輔助種群S2、S3時間復雜度Q2、Q3的分析

（1）運行時間復雜度Q12、Q13分析

輔助種群S2時間復雜度分析與主種群S1基本相同，經(jīng)過Maxiter次迭代后得到Q12=O（Maxiter·m·n）。

輔助種群S3交叉操作時間復雜度為O（m/2·n）；計算交叉后產(chǎn)生新個體的路徑序列適應度值時間復雜度為O（m·n）；變異操作時間復雜度為O（m·n）；計算變異后產(chǎn)生新個體的路徑序列適應度值時間復雜度為O（m·n）；選擇操作由于是在新老個體中進行，所以時間復雜度為O（2m·n）；SA算法優(yōu)化操作時間復雜度與主種群S1基本相同。經(jīng)過Maxiter次迭代后得到Q13=O（Maxiter·m·n）

（2）信息遷移時間復雜度Q22、Q23的分析

假設(shè)輔助種群S2、S3停滯進化次數(shù)分別達到停滯閾值Γ2、Γ3，則輔助種群S2、S3個體路徑序列根據(jù)適應度值從優(yōu)到劣進行排序，時間復雜度分別為O（m2）；將輔助種群S2、S3部分個體路徑序列分別替換為對方部分個體路徑序列時間復雜度分別為O（m/3）；個體路徑序列遷移后，選取輔助種群S2、S3當前最優(yōu)個體路徑序列時間復雜度分別為O（m2）；其他操作時間復雜度為O（1）。因信息遷移次數(shù)各不相同，假設(shè)輔助種群S2、S3在Maxiter次迭代過程中，分別經(jīng)歷了共π2、π3次信息遷移操作，則可分別得出Q22=O（π2·m·n）、Q23=O（π3·m·n）。

綜合（1）和（2）可得：

Q2=Q12+Q22=O（Maxiter·m·n）+O（π2·m·n）

Q3=Q13+Q23=O（Maxiter·m·n）+O（π3·m·n）

由于信息遷移次數(shù)不超過算法最大迭代次數(shù)，結(jié)合1）和2），得出整個VMTSOS算法時間復雜度為

T=Q1+Q2+Q3=O（Maxiter·m·n）（5）

2.3.2 VMTSOS算法空間復雜度分析

1）主種群S1所需存儲空間

存放主種群S1中m個個體路徑序列所需存儲空間為m·n；存放m個個體適應度值所需空間為m；存放該種群最優(yōu)個體路徑序列所需空間為n；互利共生、偏利共生、寄生操作后所得新個體路徑序列所需存儲空間均為m·n；存放m個新個體適應度值所需空間為m；SA算法中四大變異算子所得新路徑序列所需存儲空間均為m·n；存放SA算法中四大變異算子所得新個體適應度值所需空間均為m；執(zhí)行信息遷移操作時，由于是直接進行一對一替換，故所需存儲空間與其他操作均為常數(shù)。綜上分析可得，主種群S1空間復雜度為S1=O（m·n）。

2）輔助種群S2、S3所需存儲空間的分析

輔助種群S2所需存儲空間分析過程與主種群S1基本相同，所需空間復雜度為S2=O（m·n）。

輔助種群S3因借鑒遺傳算法，交叉操作需要復制父代個體基因，故而所需存儲空間為2m·n；存放交叉后m個新個體適應度值所需空間為m；變異操作需要存儲原個體基因，故所需存儲空間為m·n；存放變異后m個新個體適應度值所需空間為m；選擇操作過程由于是在新老個體中進行，故而所需存儲空間為2m·n。綜上所述，可以得出S3=O（2m·n）。

結(jié)合1）和2）可知，VMTSOS算法空間復雜度如式（6）所示。

S=S1+S2+S3=O（2m·n）（6）

由式（5）（6）可以看出：本文VMTSOS算法時間復雜度和空間復雜度均為多項式。

3 仿真實驗與結(jié)果分析

為了驗證VMTSOS算法在路徑規(guī)劃問題中的有效性，本章先選取TSPLIB中六個經(jīng)典旅行商問題（travelling salesman problem，TSP）測試集測試VMTSOS性能，然后再將其應用于冷鏈物流配送問題中。

3.1 VMTSOS算法求解TSP實驗結(jié)果分析

VMTSOS算法求解TSP參數(shù)設(shè)置如下：最大迭代次數(shù)Maxiter=500，停滯閾值Γ1=Γ2=Γ3=10，SA算法設(shè)置初始溫度100、最終溫度0.001、降溫系數(shù)0.99、最大迭代次數(shù)3，變異操作概率設(shè)為0.25，交換、插入、反轉(zhuǎn)算子概率分別為0.25、0.25、0.5［21］。其中，測試實例Oliver30、Att48、Eil51、Berlin52種群規(guī)模設(shè)置為m=60，St70、Eil76種群規(guī)模設(shè)置為m=90。本文算法求解TSP所得實驗結(jié)果如表1所示。

表1展示了采用本文VMTSOS算法求解TSP的浮點型和整型結(jié)果，并與官方公布的最優(yōu)解（整型）進行對比。由表1可知，采用VMTSOS算法求解Oliver30、Att48、Eil51、Berlin52、St70時，均與官方公布的最優(yōu)解一致，而本文算法在Eil76上收斂至最優(yōu)解附近，與官方最優(yōu)解僅差2。這說明本文VMTSOS算法能較好地求解不同規(guī)模TSP。

圖8給出采用本文算法求得六個測試實例最優(yōu)解路線圖，圖8所示橫縱坐標均為實例中的城市位置坐標。

為了進一步驗證VMTSOS算法性能，將VMTSOS算法所得結(jié)果與文獻［12，22～29］進行對比，因文獻［12，22～29］給出的最優(yōu)解均為浮點型，故也將本文最優(yōu)解的浮點型與上述文獻進行對比，具體如表2所示。

對表2總體分析可知，本文VMTSOS算法在六個TSPLIB測試實例上尋優(yōu)效果較為顯著。具體分析如下：與文獻［24，28］相比，本文算法求解實例Oliver30所得最短路徑分別優(yōu)化了4.279 5和0.949 5；在實例Att48上，本文VMTSOS算法所得結(jié)果與文獻［25］基本相當，而與文獻［22，26，28］相比，本文最優(yōu)路徑分別縮短了76.852 5、1 214.291 5、89.691 5；在實例Eil51上，VMTSOS所得最優(yōu)路徑與文獻［25］也基本相當，而與文獻［24，27～29］相比，本文所得路徑分別優(yōu)化了194.288 3、84.064 3、7.658 3、12.381 3；在實例Berlin52上，本文算法與文獻［27～29］相比優(yōu)化效果更為顯著，最優(yōu)路徑分別縮短了1 636.299 1、334.024 1、4.627 1；在更高維測試實例St70上，與文獻［22，24，28，29］相比，VMTSOS算法所得最優(yōu)路徑分別縮短了4.645 4、1.490 4、26.850 4、12.069 4；在測試實例Eil76上，與文獻［22，23，27～29］相比，本文算法求得最優(yōu)路徑分別縮短了7.390 7、5.387 7、146.530 1、32.717 7、19.162 7。

因文獻［12］信息遷移多任務優(yōu)化共生生物搜索算法（information transfer multitask SOS，ITMTSOS）與本文VMTSOS算法類似，均以SOS算法為多任務優(yōu)化依托算法，MPE為信息共享框架，兩者區(qū)別在于信息共享機制不同，故這里單獨列出討論。ITMTSOS主要將種群中個體自身最優(yōu)經(jīng)驗和所有鄰域種群適應能力最強個體作為知識模塊遷移至已停滯進化種群中，而本文VMTSOS算法從兩個輔助種群中吸收優(yōu)勢個體協(xié)助主種群進化。從六個TSP經(jīng)典測試實例可以看出，文獻［12］與本文VMTSOS算法在Oliver30、Att48、Eil51、Berlin52、St70測試實例上結(jié)果均相同，但VMTSOS算法在更高維實例Eil76上更勝一籌。

3.2 VMTSOS算法求解冷鏈物流配送問題

3.2.1 冷鏈物流配送問題數(shù)學模型描述

3.1節(jié)TSP屬于無約束路徑規(guī)劃問題，為進一步驗證本文算法有效性，將采用VMTSOS算法求解帶約束的冷鏈物流配送問題。我國生鮮農(nóng)產(chǎn)品冷鏈物流配送發(fā)展滯后于經(jīng)濟發(fā)展和人民群眾消費需求，急需加快生鮮農(nóng)產(chǎn)品冷鏈物流配送產(chǎn)業(yè)升級，從而實現(xiàn)冷鏈物流配送與經(jīng)濟同步發(fā)展。

本文綜合參考文獻［30，31］構(gòu)造冷鏈物流配送模型。具體描述為：配送中心位置已知，且每個配送中心都擁有多輛冷藏車，每輛冷藏車需要在規(guī)定時間內(nèi)配送完客戶訂單并返回配送中心；客戶位置、需求量、期待時間窗均已知，需要在車輛載重限制下，保證客戶需求都被滿足，通過優(yōu)化冷藏車使用數(shù)量和運輸路線，實現(xiàn)運輸總成本最小化。

為方便研究，模型作如下假設(shè)：a）配送中心車輛數(shù)不限，但車輛載重有限，配送中心位置和客戶位置、需求量、期待時間窗均已知；b）車輛均從配送中心出發(fā)，返回配送中心時間不能超過配送中心期待的最晚時間，所有車輛相同且車速不變；c）每輛車需要滿足每一個客戶需求，且一個客戶只能由一輛車配送，一輛車所配送的客戶需求量總和不超過車輛載重。

3.2.2 符號定義

給定一個無向圖G={V，E}，V={a0，a1，a2，…，an-1，an}為所有點集合，an表示配送中心，V′={a0，a1，a2，…，an-1}為所有客戶點集合，E為任意兩個點之間的路徑集合，E={（a，b）‖a≠b，a∈V′，b∈V′}，客戶點a、b之間距離為dab。配送中心共有k輛冷藏車，K={1，2，3，…，k}。配送中心時間窗為［DET，DLT］，客戶時間窗［ETa，LTa］分別表示客戶點a期望時間窗中最早和最晚服務時間，早到則需要等待。xabk為01變量，xabk=1表示車輛k從節(jié)點a行駛到節(jié)點b，否則xabk=0；yak為01變量，yak=1表示車輛k服務于客戶點a，否則yak=0。

3.2.3 冷鏈物流配送問題成本函數(shù)設(shè)計

本文所構(gòu)建模型考慮了冷鏈物流配送過程中涉及的車輛使用成本、碳排放成本、油耗成本、制冷成本、貨損成本和時間窗懲罰成本，各成本計算公式如下：

a）車輛使用成本C1。

車輛使用成本C1包括車輛行駛過程中的時間成本、服務過程中的時間成本和車輛本身固定成本，如式（7）所示。μ表示車輛使用單位時間成本，α表示車輛固定成本，v1表示車速，sa表示在客戶點a處的服務時間，sa=qa/v2，qa表示客戶點a的需求量，v2表示卸貨速度。

b）油耗成本C2和碳排放成本C3。油耗主要由車輛行駛情況和制冷兩個方面決定。

其中：η是冷鏈物流配送過程中的總油耗；ρ0、ρ1是車輛載重為空載和滿載時的單位距離油耗；Qab表示從客戶點a到客戶點b過程中車輛擁有的載重；β1是運輸和等待時的制冷油耗；β2是服務時的制冷油耗；ta表示車輛到達客戶點a的時間。

C2=pf×η（9）

其中：C2為配送過程中總油耗成本；pf為單位油耗價格。

配送過程中車輛產(chǎn)生的碳排放成本C3如式（10）所示。

C3=pc×（ψ×η-Cq）（10）

其中：pc為單位碳排放價格；ψ為碳排放系數(shù)；Cq為碳配額。

c）制冷成本C4。為保證貨物新鮮度，在冷鏈物流配送過程中需要對車廂進行降溫，并使用制冷設(shè)備維持，因此會產(chǎn)生一定的制冷成本，具體計算如式（11）所示。

其中：σ1為運輸和等待時單位制冷成本；σ2為服務時單位制冷成本。

d）貨損成本C5。冷鏈貨物在車廂內(nèi)雖有制冷設(shè)備，但仍然可能因為車門開關(guān)等因素導致溫度不穩(wěn)定，從而造成貨物損壞。為了降低貨損成本，使用貨物新鮮度衰減函數(shù)來計算損壞成本，如式（12）所示。

其中：pp是冷鏈產(chǎn)品單位價格；θ1為運輸和等待時貨物新鮮度衰減系數(shù)；θ2為服務時貨物新鮮度衰減系數(shù)；Qa表示離開客戶點a后的車輛載重。

e）時間窗懲罰成本C6。

違背客戶點時間窗所需懲罰成本計算如式（13）所示。

式（14）中C6是總時間窗懲罰成本；ωe和ωl是早到或晚到客戶點時間窗懲罰成本。

3.2.4 冷鏈物流配送數(shù)學模型構(gòu)建

根據(jù)以上定義，將車輛使用成本C1、油耗成本C2、碳排放成本C3、制冷成本C4、貨損成本C5和時間懲罰成本C6總和最小作為目標函數(shù)，如式（15）所示，構(gòu)建如下冷鏈物流配送問題模型：

目標函數(shù)：

min C=C1+C2+C3+C4+C5+C6（15）

約束條件：

其中：式（15）所示目標函數(shù)表示配送總成本最小化；式（16）表示每輛車僅有一條服務路徑，且服務客戶之后必須返回配送中心；式（17）表示每個客戶點只能被一輛車服務一次；式（18）表示每條路徑上的客戶需求之和不超過車輛最大載重；式（19）表示客戶點時間窗限制條件；式（20）表示車輛到達下一個節(jié)點時間等于到達上一節(jié)點時間、上一節(jié)點服務時間和上一節(jié)點到下一節(jié)點行駛時間三者之和所滿足的時間關(guān)系；式（21）和（22）表示01變量。

由上述數(shù)學模型可知，將所得個體路徑序列中的客戶點按順序逐個填入車輛中。車輛從配送中心出發(fā)，按照路徑依次經(jīng)過客戶點，再返回到配送中心。如果將某個客戶點放入車輛中不滿足約束條件，那么車輛配送路徑序列中最后一個客戶點將是除去該客戶點后的子序列。假設(shè)將客戶點a，a∈V′放入車輛k，k∈K中不滿足約束條件，則車輛k最后經(jīng)過的客戶點是a-1（即除去客戶a），并將客戶點a放入車輛k+1中，依此類推，直到將所有客戶點按順序分配到車輛中進行配送，最終根據(jù)車輛數(shù)生成多條配送路徑序列。

3.2.5 VMTSOS求解冷鏈物流配送問題實驗結(jié)果

VMTSOS算法求解冷鏈物流配送問題種群規(guī)模設(shè)置為m=40，其他參數(shù)與求解TSP相同。

本文應用場景的客戶點坐標、需求量和時間窗信息均采用文獻［30］中的數(shù)據(jù)，共有36個客戶點，客戶點序號為0～35，配送中心序號為36。成本相關(guān)參數(shù)參照文獻［30，31］，如表3所示。

VMTSOS算法求解冷鏈物流配送問題所得最優(yōu)路線如表4所示，載重即為每輛車配送各個客戶點需求量總和。

由表4可知：采用VMTSOS算法所得最優(yōu)配送路徑能使每輛車裝載率均在70%以上，其中車輛3和6裝載率分別達到96%和98%，車輛1和7裝載率達到100%。圖9進一步展示了最優(yōu)車輛配送路線行駛軌跡，圖中所示橫縱坐標為客戶點和配送中心坐標。

為進一步證明VMTSOS算法中的信息遷移機制能提高冷鏈物流配送問題的求解質(zhì)量，這里引入消融法逐步證明只有當輔助種群S2和S3同時協(xié)助主種群S1時，才能有效促進主種群S1進化。具體過程如下：逐一對比分析主種群S1、主種群S1+輔助種群S2、主種群S1+輔助種群S3、主種群S1+輔助種群S2+輔助種群S3（即本文VMTSOS算法）實驗結(jié)果，若涉及相同參數(shù)，則設(shè)為一致。實驗結(jié)果如表5所示。

由表5可知：a）單獨引入輔助種群S2對主種群S1實施信息遷移時（即S1+S2），在總成本、總距離、總時間、碳排放量和懲罰成本上，比單獨運行主種群S1分別節(jié)省了約269.225 2元、79.689 km、2.680 9 h、36.989 kg、23.086 2元。

b）單獨引入輔助種群S3對主種群S1實施信息遷移時（即S1+S3），在總成本、總距離、總時間、碳排放量和懲罰成本上，比單獨運行主種群S1分別節(jié)省了約318.710 6元、95.910 7 km、3.086 1 h、47.444 5 kg、11.955 6元。

c）同時引入輔助種群S2、S3對主種群S1實施信息遷移時（即S1+S2+S3），在總成本、總距離、總時間和碳排放量上，比單獨運行主種群S1分別節(jié)省了約389.58元、110.024 2 km、3.288 3 h、58.026 7 kg、28.250 7元。

通過上述數(shù)據(jù)分析可得，同時引入輔助種群S2和S3協(xié)助主種群S1進化，不僅可以顯著減少總成本、總距離、總時間，還可以有效緩解運輸過程中碳排放對環(huán)境影響和貨物新鮮度的損失，減少車輛早到或晚到的懲罰成本。這在圖10消融實驗所對應的成本收斂曲線圖中得到進一步證實。這進一步證明了在本文VMTSOS虛擬多任務環(huán)境中，利用停滯閾值促使種群間優(yōu)秀個體遷移不僅可以提高任務求解質(zhì)量，還可以加快任務收斂速度。

4 結(jié)束語

本文創(chuàng)新性地將多任務優(yōu)化思想和雙向映射解碼策略引入到SOS算法中，通過為主任務配備輔助種群構(gòu)建虛擬多任務環(huán)境，主輔種群之間遷移信息，提高了主任務求解質(zhì)量并加快了主任務收斂速度，然后將其應用于旅行商問題和冷鏈物流配送等組合優(yōu)化問題中，為SOS算法解決離散型優(yōu)化問題提供了一種新思路。然而，本文VMTSOS算法求解能力隨著問題維度的快速上升稍有下降，在現(xiàn)實生活中，由于人們對冷鏈物流配送需求不斷增加，處理維度將會不斷擴大。如何充分利用種群間的共享知識，進一步提升超高維度下的最優(yōu)解質(zhì)量，也是下一步需要著重解決的問題。

參考文獻：

［1］Nonoyama K，Liu Z，F(xiàn)ujiwara T，et al.Energyefficient robot configuration and motion planning using genetic algorithm and particle swarm optimization［J］.Energies，2022，15（6）：2074.

［2］Luan P G，Thinh N T.Hybrid genetic algorithm based smooth globalpath planning for a mobile robot［J］.Mechanics Based Design of Structures and Machines，2023，51（3）：17581774.

［3］郝琨，張慧杰，李志圣，等.基于改進避障策略和雙優(yōu)化蟻群算法的機器人路徑規(guī)劃［J］.農(nóng)業(yè)機械學報，2022，53（8）：303-312，422.（Hao Kun，Zhang Huijie，Li Zhisheng，et al.Path planning of mobile robot based on improved obstacle avoidance strategy and double optimization ant colony algorithm［J］.Trans of the Chinese Society for Agricultural Machinery，2022，53（8）：303-312，422.）

［4］劉師良，杜改麗，黃武峰.勢場改進蟻群算法優(yōu)化機器人路徑規(guī)劃［J］.機械設(shè)計與制造，2022（11）：301-304.（Liu Shiliang，Du Gaili，Huang Wufeng.Robot path planning algorithm improved by potential field and ant colony［J］.Machinery Design and Manufacture，2022（11）：301-304.）

［5］Cheng Minyuan，Prayogo D.Symbiotic organisms search：a new metaheuristic optimization algorithm［J］.Computers and Structures，2014，139：98112.

［6］elik E.A powerful variant of symbiotic organisms search algorithm for global optimization［J］.Engineering Applications of Artificial Intelligence，2020，87：103294.

［7］Nguyen V S，Nguyen K T，Luong V H，et al.A novel hybrid differential evolution and symbiotic organisms search algorithm for size and shape optimization of truss structure under multiple frequency constraints［J］.Expert Systems with Applications，2021，184：115534.

［8］Nama S，Saha A K，Sharma S.A novel improved symbiotic organisms search algorithm［J］.Computational Intelligence，2022，38（3）：947-977.

［9］敖山，彭雄飛，劉志中.多角色優(yōu)化策略的灰狼共生生物搜索算法［J］.小型微型計算機系統(tǒng)，2021，42（11）：2276-2283.（Ao Shan，Peng Xiongfei，Liu Zhizhong.Multi role optimization strategic grey wolf optimizersymbiotic organisms search algorithm［J］.Journal of Chinese Computer Systems，2021，42（11）：2276-2283.）

［10］Ikotun A M，Ezugwu A E.Improved SOSKMeans automatic clustering algorithm with a threepart mutualism phase and random weighted reflection coefficient for highdimensional datasets［J］.Applied Sciences，2022，12（24）：13019.

［11］Saad S，Muhammed A，Abdullahi M，et al.An enhanced discrete symbiotic organism search algorithm for optimal task scheduling in the cloud［J］.Algorithms，2021，14（7）：124.

［12］程美英，錢乾，熊偉清.信息遷移多任務優(yōu)化共生生物搜索算法［J］.計算機應用，2023，43（7）：2237-2247.（Cheng Meiying，Qian Qian，Xiong Weiqing.Information transfer multitask symbiotic organisms search algorithm［J］.Journal of Computer Applications，2023，43（7）：2237-2247.）

［13］Gupta A，Ong Y S，F(xiàn)eng Liang.Multifactorial evolution：towards evolutionary multitasking［J］.IEEE Trans on Evolutionary Computation，2016，20（3）：343-357.

［14］Cheng Meiying，Gupta A，Ong Y S，et al.Coevolutionary multitasking for concurrent global optimization：with case studies in complex engineering design［J］.Engineering Applications of Artificial Intelligence，2017，64：1324.

［15］Qiao Kangjia，Liang Jing，Yu Kunjie，et al.A selfadaptive evolutionary multitask based constrained multiobjective evolutionary algorithm［J］.IEEE Trans on Emerging Topics in Computational Intelligence，2023，7（4）：10981112.

［16］Han Honggui，Bai Xing，Hou Ying，et al.Multitask particle swarm optimization with dynamic ondemand allocation［J］.IEEE Trans on Evolutionary Computation，2022，27（4）：10151026.

［17］程美英，錢乾，倪志偉.多任務優(yōu)化算法研究綜述［J］.控制與決策，2023，38（7）：18021815.（Cheng Meiying，Qian Qian，Ni Zhiwei.Review of multitask optimization algorithm［J］.Control and Decision，2023，38（7）：18021815.）

［18］Zhang Fangfang，Mei Yi，Nguyen S，et al.Surrogateassisted evolutionary multitask genetic programming for dynamic flexible JobShop scheduling［J］.IEEE Trans on Evolutionary Computation，2021，25（4）：651-665.

［19］Feng Liang，Zhou Lei，Zhong Jinghui，et al.Evolutionary multitasking via explicit autoencoding［J］.IEEE Trans on Cybernetics，2019，49（9）：3457-3470.

［20］Song Hui，Qin A K，Tsai P W，et al.Multitasking multiswarm optimization［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2019：19371944.

［21］陳晟宗，張紀會，于守水，等.求解旅行商問題的波動溫控模擬退火算法［J］.控制與決策，2023，38（4）：911-920.（Chen Shengzong，Zhang Jihui，Yu Shoushui，et al.A simulated annealing algorithm with wave temperature control for the traveling salesman problem［J］.Control and Decision，2023，38（4）：911-920.）

［22］趙鑫，楊雄飛，錢育蓉.改進的蟻群優(yōu)化算法求解旅行商問題［J］.計算機工程與設(shè)計，2022，43（4）：962-968.（Zhao Xin，Yang Xiongfei，Qian Yurong.Improved ant colony optimization algorithm for TSP［J］.Computer Engineering and Design，2022，43（4）：962-968.）

［23］鄭娟毅，程秀琦，付姣姣.改進蟻群算法在TSP中的應用研究［J］.計算機仿真，2021，38（5）：126130，167.（Zheng Juanyi，Cheng Xiuqi，F(xiàn)u Jiaojiao.Application research of improved ant colony algorithm in TSP［J］.Computer Simulation，2021，38（5）：126130，167.）

［24］王原，陳名，邢立寧，等.用于求解旅行商問題的深度智慧型蟻群優(yōu)化算法［J］.計算機研究與發(fā)展，2021，58（8）：15861598.（Wang Yuan，Chen Ming，Xing Lining，et al.Deep intelligent ant colony optimization for solving traveling salesman problem［J］.Journal of Computer Research and Development，2021，58（8）：15861598.）

［25］王建新，李騰旭，王曄茹.基于離散型麻雀搜索算法的食品抽檢路徑優(yōu)化［J］.中國食品衛(wèi)生雜志，2021，33（4）：409-414.（Wang Jianxin，Li Tengxu，Wang Yeru.Optimization of food sampling inspection based on discrete sparrow search algorithm［J］.Chinese Journal of Food Hygiene，2021，33（4）：409-414.）

［26］潘澔，孫俐，高尚.解旅行商問題的蟻群分布估計混合算法［J］.江蘇科技大學學報：自然科學版，2021，35（6）：5963.（Pan Hao，Sun Li，Gao Shang.A hybrid algorithm of ant colony distribution estimation for the traveling salesman problem［J］.Journal of Jiangsu University of Science and Technology：Natural Science Edition，2021，35（6）：59-63.）

［27］趙建強，繆張曉，郭家良，等.基于二進制編碼非洲野狗算法的TSP問題研究［J］.數(shù)學的實踐與認識，2018，48（22）：304-312.（Zhao Jianqiang，Miao Zhangxiao，Guo Jialiang，et al.Research on TSP based on binary code African wild dog algorithm［J］.Mathematics in Practice and Theory，2018，48（22）：304-312.）

［28］張瑾，畢國通，李麗麗.一種求解TSP問題的離散蝙蝠算法［J］.計算機工程與科學，2018，40（11）：2085-2091.（Zhang Jin，Bi Guotong，Li Lili.A discrete bat algorithm for the traveling salesman problem［J］.Computer Engineering and Science，2018，40（11）：2085-2091.）

［29］張立毅，肖超，費騰.基于細菌覓食的改進蟻群算法［J］.計算機工程與科學，2018，40（10）：18821889.（Zhang Liyi，Xiao Chao，F(xiàn)ei Teng.An improved ant colony optimization algorithm based on bacterial foraging［J］.Computer Engineering and Science，2018，40（10）：18821889.）

［30］陳雨蝶，干宏程，程亮.“雙碳”背景下聯(lián)合配送冷鏈物流模型及求解算法［J］.控制與決策，2023，38（7）：19511959.（Chen Yudie，Gan Hongcheng，Cheng Liang.Cold chain logistics model based on joint distribution and its optimization algorithm under the background of double carbon［J］.Control and Decision，2023，38（7）：19511959.）

［31］周鮮成，蔣濤營，賀彩虹，等.冷鏈物流配送的綠色車輛路徑模型及其求解算法［J/OL］.中國管理科學.（20220927）［20230404］.DOI：10.16381/j.cnki.issn1003207x.2022.0461.（Zhou Xiancheng，Jiang Taoying，He Caihong，et al.Green vehicle routing model and its solution algorithm in coldchain logistics distribution［J/OL］.Chinese Journal of Management Science.（20220927）［20230404］.DOI：10.16381/j.cnki.issn1003207x.2022.0461.）