面向路徑規(guī)劃問(wèn)題的虛擬多任務(wù)共生生物搜索算法

徐江 程美英

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

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

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

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

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

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

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

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

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

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

1 基本SOS算法

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

1）互利共生階段

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

2）偏利共生階段

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

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

3）寄生階段

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

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

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

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

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

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

2.1.2 VMTSOS雙向映射解碼策略

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

假如個(gè)體i、j和最優(yōu)個(gè)體best初始路徑序列分別為（3，5，1，2，4，0）（5，1，3，0，2，4）（4，5，3，1，2，0），若采用式（3）計(jì)算得到隨機(jī)數(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個(gè)位置值，次小值1.0所在位置索引2映射為新路徑序列中第2個(gè)位置值，依此類推，最終形成新路徑序列（5，2，3，0，4，1）。

2.2 VMTSOS信息遷移機(jī)制

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

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

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

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

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

2.2.2 VMTSOS信息遷移方式

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

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

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

2.2.3 局部搜索策略

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

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

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

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

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

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

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

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

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

for（遍歷種群S1中所有個(gè)體）

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

if（SC1=Γ1）

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

end if

end for

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

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

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

SC1=SC1+1

else

SC1=0

end if

for（遍歷種群S2中的所有個(gè)體）

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

if（SC2=Γ2）

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

end if

end for

if（SC2=Γ2/2）

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

end if

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

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

SC2=SC2+1

else

SC2=0

end if

for（遍歷種群S3中的所有個(gè)體）

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

if（SC3=Γ3）

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

end if

end for

if（SC3=Γ3/2）

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

end if

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

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

SC3=SC3+1

else

SC3=0

end if

end while

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

2.3 VMTSOS算法復(fù)雜度分析

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

2.3.1 VMTSOS算法時(shí)間復(fù)雜度分析

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

1）主種群S1的時(shí)間復(fù)雜度Q1

（1）運(yùn)行時(shí)間復(fù)雜度Q11的分析。

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

（2）信息遷移時(shí)間復(fù)雜度Q21的分析

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

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

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

2）輔助種群S2、S3時(shí)間復(fù)雜度Q2、Q3的分析

（1）運(yùn)行時(shí)間復(fù)雜度Q12、Q13分析

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

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

（2）信息遷移時(shí)間復(fù)雜度Q22、Q23的分析

假設(shè)輔助種群S2、S3停滯進(jìn)化次數(shù)分別達(dá)到停滯閾值Γ2、Γ3，則輔助種群S2、S3個(gè)體路徑序列根據(jù)適應(yīng)度值從優(yōu)到劣進(jìn)行排序，時(shí)間復(fù)雜度分別為O（m2）；將輔助種群S2、S3部分個(gè)體路徑序列分別替換為對(duì)方部分個(gè)體路徑序列時(shí)間復(fù)雜度分別為O（m/3）；個(gè)體路徑序列遷移后，選取輔助種群S2、S3當(dāng)前最優(yōu)個(gè)體路徑序列時(shí)間復(fù)雜度分別為O（m2）；其他操作時(shí)間復(fù)雜度為O（1）。因信息遷移次數(shù)各不相同，假設(shè)輔助種群S2、S3在Maxiter次迭代過(guò)程中，分別經(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ù)不超過(guò)算法最大迭代次數(shù)，結(jié)合1）和2），得出整個(gè)VMTSOS算法時(shí)間復(fù)雜度為

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

2.3.2 VMTSOS算法空間復(fù)雜度分析

1）主種群S1所需存儲(chǔ)空間

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

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

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

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

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

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

由式（5）（6）可以看出：本文VMTSOS算法時(shí)間復(fù)雜度和空間復(fù)雜度均為多項(xiàng)式。

3 仿真實(shí)驗(yàn)與結(jié)果分析

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

3.1 VMTSOS算法求解TSP實(shí)驗(yàn)結(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］。其中，測(cè)試實(shí)例Oliver30、Att48、Eil51、Berlin52種群規(guī)模設(shè)置為m=60，St70、Eil76種群規(guī)模設(shè)置為m=90。本文算法求解TSP所得實(shí)驗(yàn)結(jié)果如表1所示。

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

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

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

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

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

3.2 VMTSOS算法求解冷鏈物流配送問(wèn)題

3.2.1 冷鏈物流配送問(wèn)題數(shù)學(xué)模型描述

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

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

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

3.2.2 符號(hào)定義

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

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

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

a）車輛使用成本C1。

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

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

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

C2=pf×η（9）

其中：C2為配送過(guò)程中總油耗成本；pf為單位油耗價(jià)格。

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

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

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

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

其中：σ1為運(yùn)輸和等待時(shí)單位制冷成本；σ2為服務(wù)時(shí)單位制冷成本。

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

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

e）時(shí)間窗懲罰成本C6。

違背客戶點(diǎn)時(shí)間窗所需懲罰成本計(jì)算如式（13）所示。

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

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

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

目標(biāo)函數(shù)：

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

約束條件：

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

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

3.2.5 VMTSOS求解冷鏈物流配送問(wèn)題實(shí)驗(yàn)結(jié)果

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

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

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

［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］郝琨，張慧杰，李志圣，等.基于改進(jìn)避障策略和雙優(yōu)化蟻群算法的機(jī)器人路徑規(guī)劃［J］.農(nóng)業(yè)機(jī)械學(xué)報(bào)，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］劉師良，杜改麗，黃武峰.勢(shì)場(chǎng)改進(jìn)蟻群算法優(yōu)化機(jī)器人路徑規(guī)劃［J］.機(jī)械設(shè)計(jì)與制造，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］.小型微型計(jì)算機(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］程美英，錢乾，熊偉清.信息遷移多任務(wù)優(yōu)化共生生物搜索算法［J］.計(jì)算機(jī)應(yīng)用，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］程美英，錢乾，倪志偉.多任務(wù)優(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ì)會(huì)，于守水，等.求解旅行商問(wèn)題的波動(dòng)溫控模擬退火算法［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］趙鑫，楊雄飛，錢育蓉.改進(jìn)的蟻群優(yōu)化算法求解旅行商問(wèn)題［J］.計(jì)算機(jī)工程與設(shè)計(jì)，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］鄭娟毅，程秀琦，付姣姣.改進(jìn)蟻群算法在TSP中的應(yīng)用研究［J］.計(jì)算機(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］王原，陳名，邢立寧，等.用于求解旅行商問(wèn)題的深度智慧型蟻群優(yōu)化算法［J］.計(jì)算機(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］.中國(guó)食品衛(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］潘澔，孫俐，高尚.解旅行商問(wèn)題的蟻群分布估計(jì)混合算法［J］.江蘇科技大學(xué)學(xué)報(bào)：自然科學(xué)版，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］趙建強(qiáng)，繆張曉，郭家良，等.基于二進(jìn)制編碼非洲野狗算法的TSP問(wèn)題研究［J］.數(shù)學(xué)的實(shí)踐與認(rèn)識(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］張瑾，畢國(guó)通，李麗麗.一種求解TSP問(wèn)題的離散蝙蝠算法［J］.計(jì)算機(jī)工程與科學(xué)，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］張立毅，肖超，費(fèi)騰.基于細(xì)菌覓食的改進(jìn)蟻群算法［J］.計(jì)算機(jī)工程與科學(xué)，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］周鮮成，蔣濤營(yíng)，賀彩虹，等.冷鏈物流配送的綠色車輛路徑模型及其求解算法［J/OL］.中國(guó)管理科學(xué).（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.）