朱紅瑞 譚代倫*

（西華師范大學(xué)數(shù)學(xué)與信息學(xué)院，四川南充 637000）

多旅行商問(wèn)題（Multiple Traveling Salesman Problem,MTSP）是經(jīng)典旅行商問(wèn)題（TSP）的一類重要擴(kuò)展［1］，它是指有多個(gè)旅行商從某個(gè)指定的起點(diǎn)出發(fā)，去訪問(wèn)給定的一組城市，要求每個(gè)城市只被一個(gè)旅行商訪問(wèn)，且只訪問(wèn)一次，求使得總成本最低的最佳行走方案，其中成本可以是路程、時(shí)間等。MTSP問(wèn)題有很多實(shí)際應(yīng)用場(chǎng)景，比如印刷機(jī)的調(diào)度［2］、印刷前廣告的調(diào)度［3］、銀行工作人員的調(diào)度［4］、校車的路線［5］、衛(wèi)星測(cè)量系統(tǒng)的設(shè)計(jì)［6］等現(xiàn)實(shí)問(wèn)題。隨著快遞和外賣配送行業(yè)的不斷發(fā)展，需要最小化各旅行商的最長(zhǎng)路線，使其承擔(dān)的工作任務(wù)盡量均衡，避免資源的浪費(fèi)，所以，均衡多旅行商問(wèn)題（Balanced Multiple Travelling Sales?man Problem,BMTSP）也逐漸得到廣泛的關(guān)注與研究，如何快速且有效地解決該問(wèn)題仍然具有很高的實(shí)際應(yīng)用價(jià)值。

在求解多旅商問(wèn)題時(shí)，大多數(shù)研究者常常只達(dá)到了總路程最短的目標(biāo)，目前，在總路程最短的基礎(chǔ)上使得每個(gè)旅行商的路程均衡的相關(guān)研究成果還不算豐富。劉偉民［7］以最小化各旅行商最長(zhǎng)路線這一負(fù)載均衡為優(yōu)化目標(biāo)，提出了一種結(jié)合構(gòu)造機(jī)制和局域搜索的改進(jìn)蟻群算法，提高了算法性能，得到更優(yōu)結(jié)果。文卡塔斯（Venkatesh）和辛格（Singh）［8］通過(guò)借鑒不同的生物智能，分別提出了不同程度上改進(jìn)的蜂群算法和雜草入侵算法，并且在多數(shù)實(shí)例上得到了較優(yōu)的計(jì)算結(jié)果。胡士娟［9］在遺傳算法中利用繁殖機(jī)制來(lái)產(chǎn)生種群并進(jìn)行遺傳操作；同時(shí)提出一種混合局部?jī)?yōu)化算子來(lái)求解平衡的MTSP 問(wèn)題，提高了算法的搜索效率和收斂精度。

在上述群智能算法中，由于遺傳算法（GA）具有通用性高、魯棒性強(qiáng)、求解性能穩(wěn)定等優(yōu)點(diǎn)，被廣泛應(yīng)用于求解MTSP 問(wèn)題［10］，但為了避免不可行解的出現(xiàn)，常采用更復(fù)雜的部分映射交叉、順序交叉、循環(huán)交叉［11］等特殊的交叉算子，導(dǎo)致遺傳過(guò)程復(fù)雜，計(jì)算效率不高。而單親遺傳算法（PGA）取消了交叉算子，代之以僅在一條染色體上操作的基因重組等遺傳算子，即通過(guò)單親繁殖來(lái)產(chǎn)生后代，遺傳操作得以簡(jiǎn)化，避免了“早熟”問(wèn)題［12］，提高了計(jì)算效率。李茂軍［13］等在2001 年也研究證明單親遺傳算法的基因重組算子隱含了交叉算子的功能。隨著單親遺傳算法受到越來(lái)越多的關(guān)注，許多學(xué)者也將其應(yīng)用于更多的實(shí)際生活中解決相關(guān)的組合優(yōu)化問(wèn)題［14-16］。

基于以上分析，本文提出一種改進(jìn)的快速單親遺傳算法（Improved Fast Partheno-Genetic Algo?rithm,IFPGA）來(lái)求解BMTSP 問(wèn)題，將已經(jīng)被實(shí)驗(yàn)證明求解TSP問(wèn)題有效的基因移位、倒序、交換等變異算子與單親遺傳策略相結(jié)合，增強(qiáng)種群尋優(yōu)能力，同時(shí)引入最近鄰點(diǎn)的局部?jī)?yōu)化策略，以加快種群的收斂。

1 BMTSP問(wèn)題及數(shù)學(xué)模型

一般地，均衡多旅行商問(wèn)題（BMTSP）可以描述為：有m 個(gè)旅行商，從某個(gè)指定起點(diǎn)出發(fā)，需要去訪問(wèn)給定的n 個(gè)城市并回到起點(diǎn)（城市之間的距離已知），每一個(gè)城市必須且只被一個(gè)旅行商訪問(wèn)一次，求使得路程最長(zhǎng)的旅行商回路盡量短的均衡最佳行走路線。

基于圖論知識(shí)，BMTSP 問(wèn)題中所有旅行商訪問(wèn)全部城市構(gòu)成一個(gè)圖，記為

其中V為頂點(diǎn)集，v0為旅行商共同的起點(diǎn)、v1,…,vn為要訪問(wèn)的n個(gè)城市；E為邊集，eij為城市vi到城市的邊，記為。

則均衡多旅行商問(wèn)題（BMTSP）的數(shù)學(xué)模型可表示為：

式（1）表示使個(gè)m旅行商的回路最大最小化；式（2）和式（3）表示m個(gè)旅行商都從指定的起點(diǎn)城市出發(fā)并回到起點(diǎn)，使得旅行路徑成為閉回路；式（4）表示每個(gè)城市只被一個(gè)旅行商訪問(wèn)且只訪問(wèn)一次；式（5）用于約束每一個(gè)旅行商不產(chǎn)生子回路［17］；式（6）表示每一個(gè)旅行商至少訪問(wèn)D個(gè)城市，其中D為工作量均衡控制常量。

2 改進(jìn)快速單親遺傳算法設(shè)計(jì)

本文IFPGA算法著重對(duì)單親遺傳策略進(jìn)行了改進(jìn)，并引入了最近鄰點(diǎn)局部?jī)?yōu)化策略，使算法的收斂速度和求解精度得到了明顯提升。下面簡(jiǎn)要說(shuō)明IFPGA算法的各個(gè)步驟。

2.1 基因編碼方案

基因編碼方案是遺傳算法的基礎(chǔ)，決定了種群個(gè)體染色體基因的結(jié)構(gòu)和表現(xiàn)形式，對(duì)遺傳交叉與變異操作都有重要影響。

遺傳算法求解旅行商問(wèn)題（TSP）普遍采用以城市序號(hào)構(gòu)成的路徑節(jié)點(diǎn)序列編碼。對(duì)多旅行商問(wèn)題（MTSP），還需要將路徑節(jié)點(diǎn)序列編碼拆分為多個(gè)片段，以對(duì)應(yīng)于多個(gè)旅行商各自的訪問(wèn)路徑。拆分方法一般是隨機(jī)生成多個(gè)斷點(diǎn)。為此，本文算法也采用路徑節(jié)點(diǎn)序列編碼和斷點(diǎn)相結(jié)合的兩段式染色體編碼。

染色體的第一部分稱為路由編碼段，是所訪問(wèn)的n個(gè)城市v1,…,vn的任意隨機(jī)序列；第二部分稱為斷點(diǎn)編碼段，其作用是將路由編碼段隨機(jī)劃分為m個(gè)片段。這m個(gè)片段即是m個(gè)旅行商各自需要訪問(wèn)的城市序列，每個(gè)片段包含的城市數(shù)應(yīng)不少于常量D，使得每個(gè)旅行商所訪問(wèn)的城市數(shù)大致相等，以體現(xiàn)工作量的均衡性。如圖1所示，表示3個(gè)旅行商需要訪問(wèn)8個(gè)城市的兩段式編碼。

圖1 兩段式染色體編碼示例

記旅行商的起點(diǎn)城市為0，則第一個(gè)旅行商的訪問(wèn)回路為（0-5-2-0），第二個(gè)旅行商的訪問(wèn)回路為（0-4-7-1-0），第三個(gè)旅行商的訪問(wèn)回路為（0-8-3-6-0）。

2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用來(lái)評(píng)估種群個(gè)體在遺傳進(jìn)化過(guò)程中對(duì)生存環(huán)境的適應(yīng)程度。適應(yīng)度較高的個(gè)體，將獲得更多的繁殖機(jī)會(huì)，遺傳到下一代的概率較大，而適應(yīng)度較低的個(gè)體，其繁殖機(jī)會(huì)相對(duì)較少，遺傳到下一代的概率就相對(duì)小一些。

根據(jù)BMTSP問(wèn)題的數(shù)學(xué)模型，其目標(biāo)函數(shù)是使路程最長(zhǎng)的旅行商回路最小化，為此本文算法的適應(yīng)度函數(shù)取m個(gè)旅行商路程長(zhǎng)度的最大者。設(shè)m個(gè)旅行商各自所訪問(wèn)的城市數(shù)（除起點(diǎn)城市外）分別為n1,n2,…,nm，第k個(gè)旅行商所訪問(wèn)的城市編碼序列記為{0,1,2,…,nk}（0 是起點(diǎn)城市的編號(hào)），則適應(yīng)度函數(shù)的計(jì)算公式為：

由適應(yīng)度函數(shù)可知，當(dāng)適應(yīng)度值越小，意味著路程最長(zhǎng)的旅行商回路越短，那么個(gè)體更優(yōu)。

2.3 快速單親變異策略

單親遺傳算法取消了交叉操作，因此如何基于父代個(gè)體進(jìn)行單親變異，是算法設(shè)計(jì)的關(guān)鍵。遺傳算法求解TSP 問(wèn)題時(shí)，被廣泛采用的變異算子有“基因換位、倒序、左移、右移”等，其尋優(yōu)能力較強(qiáng)。為此，本文算法將這四種變異算子與隨機(jī)插入思想相結(jié)合，形成以下4 種新的快速單親變異算子：

a.基因換位，隨機(jī)產(chǎn)生兩個(gè)基因點(diǎn)，將這兩個(gè)基因點(diǎn)的基因進(jìn)行交換，再將介于這兩個(gè)基因點(diǎn)之間的基因片段剪切插入到染色體的另一個(gè)隨機(jī)點(diǎn)位置；

b.基因倒序，隨機(jī)產(chǎn)生兩個(gè)基因點(diǎn)，將這兩個(gè)基因點(diǎn)內(nèi)的基因片段按位倒序，再將倒序后的基因片段剪切插入到染色體的另一個(gè)隨機(jī)點(diǎn)位置；

c.基因左移，隨機(jī)產(chǎn)生兩個(gè)基因點(diǎn)，將這兩個(gè)基因點(diǎn)內(nèi)的基因片段按位循環(huán)左移一次，再將改變后的基因片段剪切插入到染色體的另一個(gè)隨機(jī)點(diǎn)位置；

d.基因右移，隨機(jī)產(chǎn)生兩個(gè)基因點(diǎn)，將這兩個(gè)基因點(diǎn)內(nèi)的基因片段按位循環(huán)右移一次，再將改變后的基因片段剪切插入到染色體的另一個(gè)隨機(jī)點(diǎn)位置。

對(duì)單個(gè)染色體隨機(jī)執(zhí)行其中之一的變異算子來(lái)進(jìn)行變異操作。通過(guò)上述4種變異算子的單親繁殖與變異，較大幅度增加了種群多樣性，提升了種群全局尋優(yōu)能力，也加快了進(jìn)化速度。將變異片段剪切后進(jìn)行隨機(jī)插入，有利于迭代后期防止陷入局部最優(yōu)。

2.4 選擇策略

在遺傳算法中，選擇策略的作用是從種群中挑選出基因優(yōu)良的個(gè)體，淘汰掉弱勢(shì)個(gè)體，從而實(shí)現(xiàn)仿生學(xué)的“優(yōu)勝劣汰、適者生存”機(jī)制。常用的選擇策略包括輪盤賭策略、錦標(biāo)賽策略、精英選擇策略，以及一些演變和改進(jìn)的新型選擇策略，它們往往各有針對(duì)性，適用于不同的情形。

在本文算法中，通過(guò)執(zhí)行快速單親變異策略后，種群個(gè)體得到快速繁殖，種群多樣性得到較大的豐富和提高，為此采用一種改進(jìn)的精英選擇策略，其方法是將父代種群和子代種群合并，再按個(gè)體適應(yīng)度排序，最后選擇適應(yīng)度最好的前N個(gè)精英個(gè)體（N為種群規(guī)模），構(gòu)成下一代種群。

精英選擇策略只選擇種群中的最優(yōu)良個(gè)體，因此它可以大幅加快收斂速度，但是如果種群遺傳進(jìn)化的多樣性不夠，則該策略將導(dǎo)致算法早熟而陷入局部最優(yōu)。

2.5 最近鄰點(diǎn)局部?jī)?yōu)化策略

通過(guò)執(zhí)行2.3節(jié)的快速單親變異策略，種群規(guī)模得到快速擴(kuò)大，全局尋優(yōu)能力得到增強(qiáng)，但是在局部尋優(yōu)能力上還有所欠缺，特別是在迭代的中后期，個(gè)體已經(jīng)進(jìn)化比較充分，如何進(jìn)一步提高求解精度、逼近理論最優(yōu)解，還可以設(shè)計(jì)新的輔助策略。

局部尋優(yōu)能力的增強(qiáng)，意味著需要對(duì)旅行商路徑中部分不優(yōu)的節(jié)點(diǎn)序列進(jìn)行調(diào)整，對(duì)此貪心思想［18］是一種常見(jiàn)的處理方法，即對(duì)旅行商路徑的某部分節(jié)點(diǎn)序列，按一定的貪心規(guī)則進(jìn)行重新排序，使旅行商的整個(gè)路徑長(zhǎng)度更短，對(duì)應(yīng)個(gè)體的適應(yīng)度更優(yōu)。

為此，本文算法給出基于最近鄰點(diǎn)的局部?jī)?yōu)化策略，其處理步驟如下：

Step1：對(duì)種群的每一個(gè)體，查找路徑最大旅行商所對(duì)應(yīng)的染色體，記為R；

Step2：對(duì)染色體R，隨機(jī)生成兩個(gè)基因點(diǎn)I1和，將從I1到I2所包含的基因片段記為；

Step3：對(duì)基因片段S，從基因 1Ir開始，在右側(cè)節(jié)點(diǎn)集合中查找它的最近鄰點(diǎn)（距離最近的節(jié)點(diǎn)），將其交換到該基因的后面；重復(fù)本操作，直到S中全部基因被處理完；

Step4：重新計(jì)算該個(gè)體的適應(yīng)度，若比之前的適應(yīng)度更優(yōu)，則保持對(duì)基因片段S的局部?jī)?yōu)化，否則還原基因片段S；

Step5：返回Step1 處理下一個(gè)個(gè)體，直到種群個(gè)體全部處理完畢。

在Step4中，借鑒了自然界生物個(gè)體的競(jìng)爭(zhēng)排斥思想［19］，對(duì)局部?jī)?yōu)化前后的個(gè)體按適應(yīng)度優(yōu)劣進(jìn)行競(jìng)爭(zhēng)，把適應(yīng)度差的個(gè)體排斥掉，保留適應(yīng)度優(yōu)的個(gè)體，以此增強(qiáng)個(gè)體的局部尋優(yōu)能力。

上述局部?jī)?yōu)化策略，只對(duì)每個(gè)個(gè)體中路徑最大的旅行商路徑進(jìn)行基于最近鄰點(diǎn)的貪心局部?jī)?yōu)化，既符合BMTSP問(wèn)題對(duì)旅行商路徑最大最小化的目標(biāo)要求，又對(duì)算法的計(jì)算量進(jìn)行了合理的控制，使得算法具有較快的運(yùn)算速度。

2.6 算法流程圖

根據(jù)單親遺傳算法的基本流程，本文設(shè)計(jì)的IFPGA 算法首先需要隨機(jī)生成初始種群，并設(shè)置算法所需的有關(guān)參數(shù)，如城市坐標(biāo)，旅行商人數(shù)，算法最大迭代次數(shù)等；然后對(duì)每個(gè)初始個(gè)體進(jìn)行快速單親變異操作繁殖后代，這樣可以保證種群的多樣性，擴(kuò)大解空間的搜索范圍；計(jì)算父代與子代的適應(yīng)度值，利用精英策略選擇出優(yōu)良個(gè)體；對(duì)優(yōu)良個(gè)體進(jìn)一步局部?jī)?yōu)化，使每個(gè)旅行商所走路徑更短，從而得到最優(yōu)解。結(jié)合上述算法設(shè)計(jì)，算法具體流程圖如圖2所示。

圖2 改進(jìn)快速單親遺傳算法流程

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

3.1 實(shí)驗(yàn)準(zhǔn)備

實(shí)驗(yàn)環(huán)境為AMD A8-45000M CPU/8GB、操作系統(tǒng)為windows7、編程語(yǔ)言為matlab2019a。實(shí)驗(yàn)數(shù)據(jù)從TSPLIB中選取3組算例共12種情形，包括eil51 算例的三種情形（m=3、5、10），kroA100 算例的四種情形（m=3、5、10、20），kroB150算例的五種情形（m=3、5、10、20、30），后續(xù)計(jì)算時(shí)式（8）中的常量D取所有旅行商近似均分全部城市節(jié)點(diǎn)。

為了檢驗(yàn)IFPGA 算法的性能與有效性，下面從3 個(gè)方面進(jìn)行實(shí)驗(yàn)與分析。首先，分析IFPGA算法的求解性能，尤其是最近鄰點(diǎn)局部?jī)?yōu)化策略和隨機(jī)插入操作對(duì)性能的提升效果；其次，驗(yàn)證IFPGA 算法對(duì)所選取算例的求解能力；最后，將IFPGA算法與其他啟發(fā)式算法對(duì)所選取算例的求解結(jié)果進(jìn)行比較。

3.2 IFPGA算法的求解性能分析

以算例kroB150為例，旅行商人數(shù)為m=10，種群規(guī)模為N=400、迭代次數(shù)為G=1 200。用IFPGA算法求解該算例，分別測(cè)試基于最近鄰點(diǎn)的局部?jī)?yōu)化策略起作用和不起作用時(shí)的求解性能，繪制遺傳進(jìn)化曲線如圖3所示。

圖3 最近鄰點(diǎn)局部?jī)?yōu)化策略對(duì)算法性能的提升

從圖3 可以看到，IFPGA 算法的收斂速度非?？欤?dāng)?shù)?00 次左右就已經(jīng)快速下降。當(dāng)采用了最近鄰點(diǎn)的局部?jī)?yōu)化策略時(shí)，遺傳進(jìn)化效果得到明顯提升，求解精度更高。

為測(cè)試算法中單親遺傳算子與隨機(jī)插入思想的融合效果，仍按上述算例及參數(shù)分別作有隨機(jī)插入和無(wú)隨機(jī)插入的單親遺傳操作，繪制求解過(guò)程的遺傳進(jìn)化曲線如圖4所示。

圖4 隨機(jī)插入操作對(duì)算法性能的提升

從圖4 可以看到，隨機(jī)插入操作對(duì)迭代的中后期具有持續(xù)改進(jìn)的能力，進(jìn)一步提升了算法在進(jìn)化后期的局部尋優(yōu)能力，也能較好地避免陷入局部最優(yōu)。

3.3 IFPGA算法對(duì)算例的求解能力

對(duì)上述選取的3 個(gè)算例（Example）12 種旅行商人數(shù)（m）的情形，選取適當(dāng)?shù)乃惴▍?shù)：種群規(guī)模（N）、迭代次數(shù)（G）。將IFPGA算法在相同環(huán)境和參數(shù)下獨(dú)立運(yùn)行30次，統(tǒng)計(jì)所求最優(yōu)解的最大值（Max）、最小值（Min）、均值（Mean）、標(biāo)準(zhǔn)差（Std）、平均耗時(shí)（Times），結(jié)果如表1所示。

表1 IFPGA對(duì)3個(gè)算例12種情形的求解結(jié)果

從表1 可以看到，IFPGA 算法能以較小的種群規(guī)模和迭代次數(shù)在較少的時(shí)間內(nèi)求得最優(yōu)解。從求解穩(wěn)定性上，對(duì)3 個(gè)算例12 種情形所求得最優(yōu)解的最大值、最小值相對(duì)于均值都沒(méi)有出現(xiàn)明顯的偏離，標(biāo)準(zhǔn)差也較小，體現(xiàn)出算法較強(qiáng)的穩(wěn)定性。從求解的平均耗時(shí)上，表現(xiàn)出旅行商人數(shù)少則耗時(shí)多，反之則耗時(shí)少的特點(diǎn)。例如，對(duì)算例kroB150，IFPGA 算法的平均耗時(shí)（Times）與旅行商人數(shù)（m）的變化趨勢(shì)如圖5所示。

圖5 平均耗時(shí)－旅行商人數(shù)的變化關(guān)系

由于旅行商人數(shù)較少時(shí)，每個(gè)旅行商平均需要各自經(jīng)過(guò)的城市數(shù)就更多，路徑也更長(zhǎng)，此時(shí)求解所花費(fèi)的時(shí)間必然更多；隨著旅行商人數(shù)增多，每個(gè)旅行商需要各自經(jīng)過(guò)的城市數(shù)變少，此時(shí)IF?PGA 算法的求解性能明顯提升，特別是平均耗時(shí)（Times）有明顯下降。

記算法的平均耗時(shí)和旅行商人數(shù)分別為變量T,m，通過(guò)擬合可近似建立兩者的變化關(guān)系式為

利用式（8）可以對(duì)IFPGA 算法求解kroB150算例在不同旅行商人數(shù)時(shí)的平均耗時(shí)進(jìn)行大致估計(jì)。對(duì)其他算例或?qū)嵗龜?shù)據(jù)，也可以類似獲得IF?PGA算法的平均耗時(shí)估計(jì)式，以此為算法的實(shí)用性進(jìn)行更好的評(píng)估和控制。

3.4 IFPGA算法與其他算法的比較與分析

為進(jìn)一步驗(yàn)證IFPGA 算法的性能，本節(jié)將其與其他文獻(xiàn)中啟發(fā)式算法的求解結(jié)果進(jìn)行比較。與經(jīng)典TSP不同，MTSP沒(méi)有開放的指定算例用于算法測(cè)試。為保持公平性，并且更有效地測(cè)試本文所設(shè)計(jì)算法的改進(jìn)效果，因此選取一些已有的采用同個(gè)測(cè)試算例的改進(jìn)遺傳算法和其他算法得到的實(shí)驗(yàn)數(shù)據(jù)（均來(lái)自相關(guān)文獻(xiàn)）與之對(duì)比。參與比較的算法包括：利用兩部分染色體交叉算子的改進(jìn)遺傳算法（TCX）［20］、穩(wěn)態(tài)分組遺傳算法（GGA-SS）［21］、入侵雜草優(yōu)化算法（IWO）［19］、融合雜草算法繁殖機(jī)制和局部?jī)?yōu)化變異算子的改進(jìn)遺傳算法（RLGA）［9］，結(jié)果如表2所示。

表2 幾種算法求解3個(gè)算例12種情形的結(jié)果比較

從表2 可以看到，與TCX、GGA-SS、IWO 和RLGA相比，IFPGA算法的求解結(jié)果都優(yōu)于其余幾種算法得到的結(jié)果。尤其是在算例kroB150中，當(dāng)旅行商人數(shù)m為3、5時(shí)，與其他幾種算法相比，求解精度的提高更為明顯，表明IFPGA 算法對(duì)較大規(guī)模BMTSP 問(wèn)題在較少旅行商人數(shù)時(shí)具有比其余幾種算法更優(yōu)良的求解能力。當(dāng)旅行商人數(shù)較多時(shí)，雖然IFPGA算法的求解精度提升幅度不多，但是通過(guò)3.3 節(jié)的分析可知，其平均耗時(shí)下降很快，因此求解速度將會(huì)更快。

4 結(jié)語(yǔ)

針對(duì)均衡多旅行商問(wèn)題（BMTSP），本文首先利用0-1變量添加了有工作量均衡要求的約束條件，完善了BMTSP 問(wèn)題的數(shù)學(xué)模型，為后續(xù)在均衡條件下進(jìn)行算法求解奠定了基礎(chǔ)；其次，基于遺傳算法的通用框架，提出了一種改進(jìn)的快速單親遺傳算法，把加快速度的重點(diǎn)在于強(qiáng)化單親變異策略上，將常用的四種基因變異算子與隨機(jī)插入思想相結(jié)合，比較明顯地改善了父代個(gè)體變異為子代個(gè)體的多樣性，擴(kuò)大了算法的搜索尋優(yōu)范圍；最后，受貪婪算法思想的啟發(fā)，在算法中單獨(dú)設(shè)置基于最近鄰點(diǎn)的局部?jī)?yōu)化策略，以便對(duì)經(jīng)過(guò)精英優(yōu)選的子代個(gè)體再次進(jìn)行局部改善，從而進(jìn)一步增強(qiáng)種群個(gè)體的局部搜索尋優(yōu)能力。實(shí)驗(yàn)仿真表明，本文的改進(jìn)方法是可行且有效的。這些改進(jìn)思路和方法對(duì)遺傳算法的進(jìn)一步運(yùn)用和發(fā)展有較好的推動(dòng)作用，也對(duì)多旅行商問(wèn)題的深入研究甚至實(shí)用化提供更多的手段，為生產(chǎn)實(shí)踐提供更多的決策分析依據(jù)。