束東來(lái)，張玉州

（安慶師范大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽安慶246133）

限容量多旅行商問題（LCMTSP）是對(duì)經(jīng)典旅行商問題（TSP）及多旅行商問題（MTSP）的模型擴(kuò)展。

實(shí)際問題中讓一個(gè)人從一個(gè)城市出發(fā)去拜訪若干個(gè)城市，其工作量是巨大的，所以考慮到工作效率等問題，MTSP更符合實(shí)際，而每個(gè)旅行商的精力是有限的，安排一個(gè)合理訪問城市個(gè)數(shù)的范圍是有必要的[2]，LCMTSP問題在MTSP問題基礎(chǔ)上，給每個(gè)旅行商施加了一個(gè)訪問城市個(gè)數(shù)的限制條件，顯然更符合實(shí)際意義。

本文以3個(gè)旅行商、每個(gè)旅行商訪問城市不少于3個(gè)但不多于10個(gè)、從一個(gè)城市出發(fā)訪問其余19個(gè)城市并回到出發(fā)城市問題為例，對(duì)傳統(tǒng)的遺傳算子稍加改進(jìn)，實(shí)驗(yàn)證明能夠較好的解決限容量多旅行商問題。

1 LCMTSP數(shù)學(xué)模型

帶有容量限制的多旅行問題是在原有的多旅行商問題的基礎(chǔ)上多了一個(gè)容量限制的約束條件。其目標(biāo)函數(shù)為m個(gè)旅行商所走的路程最短，其約束條件為m個(gè)旅行商中每個(gè)旅行商訪問城市的個(gè)數(shù)有上下限。

本文模型與基本TSP問題一樣，是尋找加權(quán)圖中最短回路問題[4]，假設(shè)城市號(hào)從1～n，其中城市1為出發(fā)城市，m個(gè)旅行商。

定義變量：

其中i=1,2...N，k=1,2...M

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

約束條件：

其中Si,k為第k個(gè)人訪問的城市的合集，sik代表第k個(gè)人訪問的第i個(gè)城市，q代表訪問者訪問的城市數(shù)目

公式（4）代表從指定城市1出發(fā)，所有城市僅有1個(gè)訪問者嚴(yán)格訪問一次；

公式（5）表示任意一條路線的次終點(diǎn)城市（iq,k）僅有一個(gè)起始點(diǎn)城市與之相連；

公式（6）表示任意一條路線的起始點(diǎn)城市僅有一個(gè)次終點(diǎn)城市（iq,k）與之相連；

公式（7）表示第k個(gè)訪問者訪問的所有城市；

公式（8）表示所有訪問者訪問的城市總和；

公式（9）每個(gè)訪問者最少訪問a個(gè)城市，最多訪問b個(gè)城市；根據(jù)本文20個(gè)城市、3個(gè)旅行商、每個(gè)旅行商訪問城市個(gè)數(shù)不少于3個(gè)且不多于10，約束條件（9）改為3≤q≤10。

2 遺傳算法設(shè)計(jì)

2.1 編碼

本文采用以遍歷城市的次序排列的一種染色體自然編碼方法，即一個(gè)解序列表示一條染色體。如串碼0-1-2-3-4-5-6-7-8-9-0表示自城市0開始，依次經(jīng)1，2，3，4，5，6，7，8，9，遍歷路徑，最后返回城市0[5]。

如城市為0，1，2，...，19的三個(gè)旅行商問題的一條染色體編碼為：

其中斷點(diǎn)分割隨機(jī)斷點(diǎn)r1、r2；如r1=6，r2=12：

將斷點(diǎn)r1、r2插入染色體編碼中，斷點(diǎn)的選擇會(huì)受到問題容量限制條件的約束，每個(gè)旅行商訪問城市個(gè)數(shù)為不少于3個(gè)且不多于10個(gè)。

則三個(gè)旅行商的路徑分別表示為：

2.2 群體規(guī)模

合理的群體規(guī)模對(duì)遺傳算法的收斂具有重要意義[6]，群體規(guī)模太小難以得到滿意的結(jié)果，群體規(guī)模太大會(huì)使計(jì)算復(fù)雜。根據(jù)經(jīng)驗(yàn)，本文群體規(guī)模取100。

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

適應(yīng)度函數(shù)是根據(jù)個(gè)體的適應(yīng)值對(duì)其優(yōu)劣判定的評(píng)價(jià)函數(shù)。在旅行商問題中用訪問路徑的總距離的倒數(shù)作為適應(yīng)度函數(shù)來(lái)評(píng)價(jià)求解結(jié)果是否最優(yōu)[7]。即：

2.4 初始化種群及初始化父代

2.4.1 種群初始化 產(chǎn)生一個(gè)sizepop×19的數(shù)組，每一行存儲(chǔ)一個(gè)序列；產(chǎn)生隨機(jī)斷點(diǎn)，存儲(chǔ)在sizepop×2的數(shù)組；把對(duì)應(yīng)的斷點(diǎn)加入初始化數(shù)組中，求出sizepop×19個(gè)體中最優(yōu)的記錄對(duì)應(yīng)序列反下標(biāo)。2.4.2初始化父代 初始化父代采用完全隨機(jī)（inti_rand_nerb）與次優(yōu)選擇(init sub sele)相結(jié)合的方法。產(chǎn)生一個(gè)隨機(jī)數(shù)，如果生成的隨機(jī)數(shù)是0，就采用完全隨機(jī)的方式一個(gè)父代；如果生成的隨機(jī)數(shù)是1，就采用最近鄰法生成一個(gè)父代。

在完全隨機(jī)方法中，首先產(chǎn)生一個(gè)1～19的一個(gè)隨機(jī)數(shù)作為序列的第一個(gè)元素，然后依次循環(huán)產(chǎn)生此序列的下一個(gè)元素，在每次產(chǎn)生下一個(gè)元素的時(shí)候判斷是否與此序列中前面產(chǎn)生的元素相等，若相等則重新產(chǎn)生，否則添加到序列中；然后再進(jìn)行斷點(diǎn)分割，分成三個(gè)旅行商的訪問路徑。

圖1 完全隨機(jī)法初始化父代

在次化選擇法中，首先產(chǎn)生三個(gè)0～2的隨機(jī)數(shù)，看作對(duì)應(yīng)的旅行商，若當(dāng)前產(chǎn)生的隨機(jī)數(shù)為0，則在候選集合中選取距離第一個(gè)旅行商次近的城市，并添至其路徑中，直到候選序列為空。例如下圖2：

圖2 次優(yōu)選擇法初始化父代

0為起始城市；

1,2,3 ,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19為需要訪問的城市；

三個(gè)旅行商分別為T1、T2、T3；

產(chǎn)生一個(gè)0～2的隨機(jī)數(shù)r；

計(jì)：r=0，選擇未被選擇的城市中距離T1所在位置次近的城市；

計(jì)：r=1，選擇未被選擇的城市中距離T2所在位置次近的城市；

計(jì)：r=2，選擇未被選擇的城市中距離T3所在位置次近的城市。

2.5 控制容量操作

根據(jù)本文容量限制這一約束條件，控制每個(gè)旅行商訪問城市個(gè)數(shù)范圍：3≤q≤10；產(chǎn)生一個(gè)length×19的旅行商，隨機(jī)產(chǎn)生一個(gè)3～10之間的隨機(jī)數(shù)，作為第一個(gè)斷點(diǎn)；再產(chǎn)生另外一個(gè)隨機(jī)數(shù)，使得與前面產(chǎn)生的隨機(jī)數(shù)的距離大于3且與終點(diǎn)的距離大于3且不大于10，作為另一個(gè)斷點(diǎn)。

2.6 選擇操作

在群體大小為n的群體中，如果一個(gè)個(gè)體i的適應(yīng)度為fi，則該個(gè)體被選擇的概率，然后對(duì)各個(gè)染色體計(jì)算它們的累積概率，概率Pi表示個(gè)體i的適應(yīng)度在群體的個(gè)體適應(yīng)度總和所占的比例，個(gè)體適應(yīng)度大的被選擇的概率就越高[9]。

運(yùn)用輪盤賭法選擇較優(yōu)個(gè)體，為了選擇父代需要進(jìn)行多次選擇，每次產(chǎn)生一個(gè)[0,1]的均勻隨機(jī)數(shù)，將該隨機(jī)數(shù)作為選擇指針來(lái)確定備選父代個(gè)體。

2.7 交叉操作

交叉算子是遺傳算法里面的核心算子。交叉算子里面的交叉概率的設(shè)置較為重要，交叉概率大能增強(qiáng)遺傳算法開拓新搜索空間的能力，但有可能會(huì)破壞一些性能較好的基因串，而交叉概率小又會(huì)引起算法遲鈍。本文交叉概率取0.8。

對(duì)于LCMTSP問題，本文交叉算子采用PMX算子、OX算子、CX算子以及最小路徑交叉規(guī)則等算子與斷點(diǎn)分割過程相結(jié)合。

部分匹配交叉算子（Partially Matched Crossover，PMX）是針對(duì)TSP問題提出的基于路徑表示的交叉操作，先均勻隨機(jī)分布兩個(gè)交叉點(diǎn)，定義這兩個(gè)點(diǎn)之間的區(qū)域?yàn)槠ヅ浣徊鎱^(qū)域，使用位置交換操作將兩個(gè)父代該區(qū)域進(jìn)行交換，交換出現(xiàn)重復(fù)的部分用原基因位的數(shù)字代替[10]。

順序交叉算子（Ordered Crossover，OX）是針對(duì)TSP問題提出的基于路徑表示的交叉操作，該算子能夠保留排列并融合不同排列的有序結(jié)構(gòu)單元[11]。兩個(gè)父代交叉時(shí)，選擇其中一個(gè)父代的一部分，保存另一個(gè)父代中代碼的相對(duì)順序生成子個(gè)體。

循環(huán)交叉算子（Cycle Crossover，CX）也是針對(duì)TSP問題提出的[12]，循環(huán)交叉操作中子代的代碼順序根據(jù)其任意父代個(gè)體產(chǎn)生。

最小路徑交叉規(guī)則(Minimam Puth Crossover,MPC)是本文在三個(gè)旅行商之間操作的一種交叉算子，根據(jù)斷點(diǎn)分割后的三個(gè)旅行商，用產(chǎn)生的隨機(jī)數(shù)對(duì)其中兩個(gè)旅行商進(jìn)行交叉互換操作。例如：

一條父代的染色體編碼為：

產(chǎn)生兩個(gè)隨機(jī)數(shù)r1、r2∈（0,2），如r1=0、r2=1就旅行商A與旅行商B進(jìn)行交叉；計(jì)算旅行商A與旅行商B中旅行商訪問城市少的城市個(gè)數(shù)，如上所示，旅行商A訪問城市個(gè)數(shù)為6，旅行商B訪問城市個(gè)數(shù)為9，選擇L=6（L為需交叉的路徑長(zhǎng)度）；產(chǎn)生兩個(gè)隨機(jī)數(shù)q1、q2∈（1，6），如q1=2，q2=5，對(duì)旅行商A、B進(jìn)行交叉互換：

2.8 變異操作

變異算子在遺傳算法中屬于局部搜索操作，其目的是維持種群的多樣性。變異算子里的變異概率也較為重要，較低的變異概率能防止種群中優(yōu)良基因的丟失，但是降低了遺傳算法開拓新搜索空間的能力[13]，而較高的變異概率又會(huì)降低算法的收斂度和穩(wěn)定性。本文變異概率取0.01。

對(duì)于LCMTSP問題，本文變異算子采用SWAP算子、2-opt算子、3-opt算子以及SI、DI算子與斷點(diǎn)分割過程相結(jié)合。

SWAP算子是兩點(diǎn)對(duì)換算子，將位置r1，r2，將這兩個(gè)位置的數(shù)字進(jìn)行對(duì)換。

2-opt算子是為了加速進(jìn)化而加入的一個(gè)操作，具有單向性，即只有逆轉(zhuǎn)之后個(gè)體變得更優(yōu)才會(huì)執(zhí)行2-opt操作，否則逆轉(zhuǎn)無(wú)效[14]。根據(jù)小路徑取反原則，產(chǎn)生[1,19]之間的兩個(gè)位置r1、r2，將r1和r2之間的基因序列進(jìn)行反向排序。

3-opt算子是在2-opt算子的基礎(chǔ)上又選了一個(gè)逆轉(zhuǎn)點(diǎn)，產(chǎn)生[1,19]之間的三個(gè)位置r1、r2、r3，將離第一個(gè)城市最近的位置點(diǎn)與第一個(gè)城市位置點(diǎn)之間的序列進(jìn)行反向排序，將后兩個(gè)位置點(diǎn)之間的基因序列進(jìn)行反向排序。

SI算子是一種單插入變異算子，將路徑中一個(gè)位置r1的數(shù)刪除，插入該路徑的另一個(gè)位置r2前面。例如：

一條父代的染色體編碼為：

DI算子是一種雙插入變異算子，它將路徑中連續(xù)兩個(gè)位置r1、r2從當(dāng)前位置刪除，插入該路徑的另一個(gè)位置r3前面。例如：

一條父代的染色體編碼為：

本文考慮到所有位置變異情況，即上述5種變異算子中每一個(gè)點(diǎn)都要進(jìn)行測(cè)試，即遍歷所有可能的情況，選擇最優(yōu)的過程，算改變后的總距離，然后選取最優(yōu)的解（總距離最短），遺傳到下一代。

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

本文借助 C 語(yǔ)言，在 Intel（R）Core（TM）i5-6500 CPU處理器計(jì)算機(jī)環(huán)境中對(duì)LCMTSP問題的遺傳算法進(jìn)行研究，用3個(gè)旅行商訪問20個(gè)城市的LCMTSP實(shí)例進(jìn)行測(cè)試，選取100個(gè)染色體作為初始種群，最大遺傳代數(shù)為1000，交叉概率為0.8，變異概率為0.01。

實(shí)驗(yàn)對(duì)程序進(jìn)行了運(yùn)行10次、20次、50次、100次，將本文提出的模型與原始MTSP模型進(jìn)行對(duì)比，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，取實(shí)驗(yàn)結(jié)果的平均值及最小值的方法來(lái)提高實(shí)驗(yàn)的準(zhǔn)確性和可信度。

實(shí)驗(yàn)對(duì)LCMTSP問題進(jìn)化代數(shù)100、300、600、1000、1500代進(jìn)行了實(shí)驗(yàn)，取實(shí)驗(yàn)結(jié)果的平均值及最小值的方法來(lái)提高實(shí)驗(yàn)的準(zhǔn)確性和可信度。

實(shí)驗(yàn)結(jié)果如表1和表2所示：

表1 LCMTSP與原始MTSP實(shí)驗(yàn)對(duì)比

表2 gen=100、300、600、1000、1500代時(shí)的解、運(yùn)行時(shí)間

借助Matlab2014a軟件，程序運(yùn)行一次，LCMTSP模型進(jìn)化軌跡圖如圖3-圖8所示：

圖3 種群初始化

圖5 gen=300，l=341.893153

圖6 gen=600，l=289.967866

圖7 gen=1000，l=250.927191

圖8 gen=1500，l=279.258567

從程序運(yùn)行結(jié)果可以知道，由于遺傳算法是一種啟發(fā)式算法的特性，每次運(yùn)行的結(jié)果大都不相同但都相近。

從實(shí)驗(yàn)結(jié)果最優(yōu)解與平均解可以看出本文限容量多旅行商問題與傳統(tǒng)多旅行商問題實(shí)驗(yàn)結(jié)果總距離差距不大甚至更優(yōu)。

從實(shí)驗(yàn)運(yùn)行時(shí)間來(lái)看，本文模型運(yùn)行時(shí)間比傳統(tǒng)多旅行商問題運(yùn)行時(shí)間稍短。

從實(shí)驗(yàn)對(duì)LCMTSP問題進(jìn)化代數(shù)來(lái)看，在進(jìn)化到1000代左右時(shí)，總距離基本已經(jīng)可以達(dá)到最小值，再進(jìn)化更多代數(shù)總距離無(wú)明顯改進(jìn)。

綜合實(shí)驗(yàn)結(jié)果與實(shí)際意義，本文提出的限容量多旅行商問題模型比傳統(tǒng)多旅行商問題更具有實(shí)踐意義與價(jià)值。