雙編碼改進(jìn)遺傳算法求解旅行商問題

王 玉，譚代倫

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

0 引言

旅行商問題(Traveling Salesman Problem，TSP)是一個(gè)經(jīng)典的組合優(yōu)化問題，其求解難度被證明是NP難問題[1]。在現(xiàn)實(shí)生活中，TSP問題廣泛應(yīng)用于貨物零件加工順序[2]、汽配件噴涂順序[3]、倉(cāng)儲(chǔ)系統(tǒng)揀貨路徑規(guī)劃[4]、光伏板清潔[5]等領(lǐng)域。

TSP問題于1959年被Dantzing等人提出[6]，被國(guó)內(nèi)外眾多專家學(xué)者研究，并用于測(cè)試算法效率[7]，目前已有大量研究成果。早期，求解TSP問題主要是精確型算法，如P.M.E.Shutler[8]基于分支定界算法思想，提出新的分支規(guī)則，將次梯度優(yōu)化計(jì)算的最小生成樹的標(biāo)準(zhǔn)下界作為算法下界，再?gòu)牧硪粋€(gè)角度去考慮最后幾棵樹的大部分邊，使決策樹的節(jié)點(diǎn)數(shù)增長(zhǎng)冪為2，減少了解決TSP問題所需要的決策節(jié)點(diǎn)總數(shù)，降低了問題的復(fù)雜度。G.Carpaneto[9]基于子路徑巡回消除方法，從三個(gè)方面對(duì)分支定界算法進(jìn)行了改進(jìn)，提出了一種廣度優(yōu)先分支定界算法，促進(jìn)了成本矩陣的更新，加快了運(yùn)算速度。精確算法的研究具有很強(qiáng)的理論意義，但只適用于求解小規(guī)模TSP問題。

自20世紀(jì)80年代以來，基于啟發(fā)式規(guī)則的智能優(yōu)化算法[10]興起并被快速應(yīng)用于求解TSP問題，如遺傳算法[11-12]、模擬退火算法[13]、蜂群算法[14]、蟻群算法[15]、螢火蟲算法[16]、粒子群算法[17]等，它們普遍具有快速搜索和求解能力，對(duì)規(guī)模更大的TSP問題也有明顯效果。其中，以達(dá)爾文進(jìn)化論、孟德爾遺傳變異理論、模式理論為基礎(chǔ)的遺傳算法[18]逐漸受到重視，它是一種自適應(yīng)全局優(yōu)化的概率搜索算法，具有較強(qiáng)的魯棒性、并行性，容易與其他算法結(jié)合等優(yōu)點(diǎn)，但也存在交叉算子不易操作、容易過早收斂而陷入局部最優(yōu)、收斂速度慢等缺點(diǎn)。為克服遺傳算法存在的缺點(diǎn)，許多專家學(xué)者對(duì)遺傳算法進(jìn)行了不同的改進(jìn)。陳斌等[18]引入深度強(qiáng)化學(xué)習(xí)思想，分離遺傳算法的交叉和變異操作，將其作為智能體(agent)的動(dòng)作空間，訓(xùn)練agent控制交叉和變異操作，把控種群進(jìn)化方向。李利杰等[19]在交叉算子中融入貪婪思想，引入2opt算子和穩(wěn)定狀態(tài)選擇機(jī)制改進(jìn)算法，增強(qiáng)了算法的局部搜索能力，提高了算法的效率。徐佳等[20]優(yōu)化適應(yīng)度函數(shù)和初始種群，引入生物信息基因序列對(duì)比用于交叉算子，采用逆轉(zhuǎn)算子對(duì)個(gè)體變異，使算法加快收斂速度，提高求解精度。劉海等[21]針對(duì)傳統(tǒng)遺傳算法求解TSP問題的交叉操作存在的部分缺點(diǎn)，構(gòu)造了一種新的交叉算子，改善了算法性能。張立毅等[22]借鑒搜尋者優(yōu)化算法的模糊思想與近鄰策略改進(jìn)變異算子，采用啟發(fā)式策略設(shè)計(jì)一種反轉(zhuǎn)算子，提高算法的執(zhí)行效率和收斂性。劉荷花等[23]根據(jù)種群個(gè)體的多樣性和分布情況，提出了計(jì)算算法截止代數(shù)的方法，再在算法中加入初始化信息并改進(jìn)交叉算子，提高了算法的精確性。

綜上，現(xiàn)有文獻(xiàn)對(duì)遺傳算法的改進(jìn)主要是從遺傳算子入手來改善算法性能。遺傳算法求解TSP問題時(shí)交叉算子不易操作，其主要原因在于基于路徑節(jié)點(diǎn)的序列編碼方案要求個(gè)體染色體基因是不可重復(fù)的，為此，提出一種雙編碼改進(jìn)遺傳算法(Double Coding Improved Genetic Algorithm， DCIGA)。算法中，再引入一種可重復(fù)自然數(shù)編碼作為第二種基因編碼方案，主要作用于交叉環(huán)節(jié)，使得基因的遺傳交叉不需修復(fù)，可任意設(shè)計(jì)交叉規(guī)則，從而大幅增強(qiáng)種群質(zhì)量和多樣性，提升算法性能。此外，算法還采用了多種交叉算子、變異算子輪流使用的策略，使得經(jīng)交叉和變異后的個(gè)體得到不同程度的遺傳進(jìn)化效果，增強(qiáng)了算法搜索尋優(yōu)能力。通過實(shí)驗(yàn)仿真，結(jié)果表明DCIGA算法是高效可行的。

1 TSP問題及數(shù)學(xué)模型

一般地，TSP問題可描述為：一個(gè)旅行商需要拜訪n個(gè)城市，城市之間的距離是已知的，若旅行商對(duì)每個(gè)城市必須拜訪且只拜訪一次，求旅行商從某個(gè)城市出發(fā)并最終回到起點(diǎn)的一條最短路徑[24]。

記n個(gè)城市序號(hào)構(gòu)成集合為N={1，2，…，n}，旅行商拜訪完n個(gè)城市所經(jīng)過的回路記為

P={p1→p2→…→pn→p1}

(1)

其中pi∈N，pi≠pj(i≠j)，i=1，2，…，n.

若城市之間的距離矩陣為D=(dij)n×n，則TSP問題的數(shù)學(xué)模型可表示為

(2)

其中f(P)表示旅行商行走路線的總路徑長(zhǎng)度。

2 傳統(tǒng)遺傳算法

遺傳算法(Genetic Algorithms，GA)是由J.Holland教授在20世紀(jì)70年代提出的，通常被稱為傳統(tǒng)遺傳算法或標(biāo)準(zhǔn)遺傳算法[18]。它模擬和借鑒了自然界生物進(jìn)化過程中基因的遺傳、交叉與突變等現(xiàn)象，從算法上設(shè)計(jì)了對(duì)種群個(gè)體的選擇、交叉、變異這三個(gè)主要環(huán)節(jié)，被保留和遺傳的個(gè)體是經(jīng)過適應(yīng)性評(píng)估為優(yōu)的個(gè)體，從而體現(xiàn)生物界“適者生存、優(yōu)勝劣汰”的機(jī)制，按此不斷迭代和進(jìn)化，直到滿足某種收斂條件為止[25]。

遺傳算法是一種具有全局優(yōu)化能力的概率搜索算法，通用性高、并行性和魯棒性強(qiáng)，已被成功運(yùn)用于求解TSP問題[3]，其基本步驟為：

Step1 確定基因編碼方案，設(shè)置算法參數(shù)?；蚓幋a方案是根據(jù)優(yōu)化問題的可行解特點(diǎn)而設(shè)計(jì)的編碼結(jié)構(gòu)和取值，其TSP問題通常取基于路徑節(jié)點(diǎn)的不重復(fù)序列編碼。算法參數(shù)主要包括種群規(guī)模、迭代次數(shù)、交叉概率、變異概率等。

Step2 初始化種群，即按基因編碼方案的要求和種群規(guī)模的大小生成一組個(gè)體。

Step3 利用適應(yīng)度函數(shù)評(píng)估種群個(gè)體的優(yōu)劣。其中，適應(yīng)度函數(shù)通?；趦?yōu)化問題的目標(biāo)函數(shù)進(jìn)行構(gòu)造。

Step4 選擇操作，即根據(jù)個(gè)體的適應(yīng)度大小，按一定策略優(yōu)選出足夠數(shù)量的個(gè)體構(gòu)成子代種群。個(gè)體適應(yīng)度越好，被選中的概率就越大。常用的選擇策略有輪盤賭策略、精英策略、排序優(yōu)選策略等。

Step5 交叉操作，即將子代種群的個(gè)體繼續(xù)隨機(jī)配對(duì)，根據(jù)交叉概率進(jìn)行基因隨機(jī)交換，使個(gè)體有機(jī)會(huì)獲得更多優(yōu)良基因，從而增強(qiáng)子代種群的多樣性，保持較強(qiáng)的搜索尋優(yōu)能力。

Step6 變異操作，即隨機(jī)選擇一些子代個(gè)體，根據(jù)變異概率對(duì)個(gè)體的某些基因位進(jìn)行改變，使其突變?yōu)樾碌膫€(gè)體，進(jìn)而擴(kuò)大搜索尋優(yōu)范圍。

Step7 重復(fù)Step3—Step6，直到遺傳進(jìn)化操作達(dá)到迭代的終止條件。

傳統(tǒng)遺傳算法具有通用性的算法框架，步驟清楚，各個(gè)環(huán)節(jié)允許自行設(shè)計(jì)，但是也存在收斂速度慢，或收斂過早而陷入局部最優(yōu)等缺點(diǎn)[18]。因此，針對(duì)上述各個(gè)步驟進(jìn)行改進(jìn)，一直是提升算法性能的主要方向。

3 雙編碼改進(jìn)遺傳算法

遺傳算法求解TSP問題時(shí)，其基因編碼方案最常用的是以各城市組成的路徑節(jié)點(diǎn)序列編碼，其優(yōu)點(diǎn)是直觀，對(duì)應(yīng)性強(qiáng)，便于計(jì)算個(gè)體適應(yīng)度。缺點(diǎn)是個(gè)體之間如果直接進(jìn)行交叉操作，很容易導(dǎo)致兩個(gè)個(gè)體出現(xiàn)重復(fù)的基因或基因缺失，從而變成非法個(gè)體。文獻(xiàn)[26]提出了一種與路徑節(jié)點(diǎn)序列編碼具有一一映射關(guān)系的可重復(fù)自然數(shù)編碼，為此本文在傳統(tǒng)遺傳算法基礎(chǔ)上引入這種新編碼方案，提出雙編碼改進(jìn)遺傳算法(DCIGA)。在交叉環(huán)節(jié)采用這種新編碼方案，在變異環(huán)節(jié)仍使用路徑節(jié)點(diǎn)序列編碼方案，將選擇操作放在變異之后，并且選擇之前先將父代種群、交叉后的種群和變異后的種群進(jìn)行合并排序和精英優(yōu)選，以加快收斂速度，下面具體說明本文算法的各個(gè)步驟。

3.1 雙編碼方案

這里，雙編碼方案是指在算法中同時(shí)采用路徑節(jié)點(diǎn)序列編碼和一種可重復(fù)自然數(shù)編碼。

路徑節(jié)點(diǎn)序列編碼就是與式(1)相對(duì)應(yīng)的編碼，它通常用不重復(fù)的自然數(shù)編碼來表示。實(shí)際編碼時(shí)可以去掉式(1)末尾處的起點(diǎn)城市號(hào)。例如，當(dāng)n=6時(shí)，以下兩個(gè)序列都是合法的編碼：

P1={2，5，3，1，4，6}，P2={3，2，5，6，4，1}

可重復(fù)自然數(shù)編碼在文獻(xiàn)[26]中被提出，其基本思想是將路徑節(jié)點(diǎn)序列編碼唯一映射為可重復(fù)自然數(shù)編碼，如下：

(3)

其映射規(guī)則為：qi等于P中值為i的碼(記為pk)的左邊比該值小的碼的個(gè)數(shù)。

為便于碼的生成與轉(zhuǎn)換，令

(4)

則qi的計(jì)算公式為

(5)

例如，將上述編碼P1映射為Q1的結(jié)果為：

P1={2，5，3，1，4，6}→Q1={5，1，3，1，0，0}

在Q1中q6=5是因?yàn)樵诰幋aP1中碼6的左邊比它小的碼的個(gè)數(shù)為5個(gè)，其余數(shù)字也是類似得來。同理，編碼P2的映射碼Q2={3，2，2，0，0，0}.

分析映射碼Q，可以發(fā)現(xiàn)它具有以下特征：

q1≡0，0≤qi

因此，映射碼Q還可以去掉q1位，并表示為：

Q={qn-1，…，q2，q1，0≤qi≤i}

(6)

綜上，編碼Q既可根據(jù)式(4)～(5)從編碼P映射得到，也可根據(jù)式(6)直接隨機(jī)生成。因此，第二種編碼方案具有映射規(guī)則簡(jiǎn)單、生成方式靈活、碼可重復(fù)等特點(diǎn)，在遺傳算法求解旅行商問題時(shí)可利用價(jià)值較高。為方便遺傳算法調(diào)用，下面給出這兩種碼相互轉(zhuǎn)換的算法。

算法1：PToQ(編碼P轉(zhuǎn)換為編碼Q)

Input：城市數(shù)n，編碼P={pn，pn-1，…，p2，p1}.

Output：編碼Q={qn-1，…，q2，q1}.

1.InitializeQ

2.Fori=1 ton-1 do

3. Searchpk=i+1 inP

4. Calculateqiby using formula (4)

5. StoreqitoQ

6.End for

算法2：QToP(編碼Q轉(zhuǎn)換為編碼P)

Input：城市數(shù)n，編碼Q={qn-1，…，q2，q1}.

Output：編碼P={pn，pn-1，…，p2，p1}.

韋蘭認(rèn)為，在外部制度環(huán)境和內(nèi)部道德秩序發(fā)生不連續(xù)性時(shí)，道德主體將有可能突破規(guī)則和傳統(tǒng)，拒絕外在制度的約束，形成道德焦慮。在城市化和逆城市化交互作用的今天，眾多村民要么告別熟悉的家園環(huán)境，背井離鄉(xiāng)去城市尋夢(mèng)；要么懷揣著尋找機(jī)遇的美好愿望，成為新一代返鄉(xiāng)農(nóng)民工創(chuàng)造商機(jī)。他們面臨陌生的外部環(huán)境、快速流動(dòng)的人群和變動(dòng)不居的習(xí)俗規(guī)范，約束人的道德秩序和道德行為也在發(fā)生轉(zhuǎn)變，屬于外部因素的道德觀念和道德標(biāo)準(zhǔn)影響著個(gè)體，能夠形成一種新形勢(shì)下的道德觀和道德秩序。道德失去了制度環(huán)境的外在效力，也使得他律將以一種全新的面貌得以呈現(xiàn)。

1.SetP=[1]

2.Fori=1 ton-1 do

3.s=i+1

4. Ifqi=0

5.insertsto the left ofP(1)

6.Else

7.insertsto the right ofP(qi)

8.End if

3.2 種群初始化和適應(yīng)度函數(shù)

按照DCIGA 算法的設(shè)計(jì)思路，遺傳進(jìn)化將按“交叉--變異--選擇”的順序完成，期間只在交叉環(huán)節(jié)使用可重復(fù)自然數(shù)編碼，其余環(huán)節(jié)仍使用路徑節(jié)點(diǎn)序列編碼，這樣個(gè)體適應(yīng)度計(jì)算和變異操作都不受影響。由于編碼轉(zhuǎn)換遠(yuǎn)比交叉操作本身的復(fù)雜性低，因此利用兩次碼轉(zhuǎn)換完成一輪交叉操作，對(duì)遺傳進(jìn)化操作是值得的。

為此，本文算法的初始種群是基于路徑節(jié)點(diǎn)序列編碼(末尾不含返回起點(diǎn))進(jìn)行初始化。例如，當(dāng)城市數(shù)n=6時(shí)，種群中的每一個(gè)個(gè)體的基因編碼就是由自然數(shù)1～6的隨機(jī)不重復(fù)排列構(gòu)成的一個(gè)序列編碼。

適應(yīng)度函數(shù)的任務(wù)是對(duì)種群個(gè)體的優(yōu)劣進(jìn)行評(píng)估。對(duì) TSP問題，旅行商的回路越短則個(gè)體越優(yōu)，因此本文算法取目標(biāo)函數(shù)(2)式為算法的適應(yīng)度函數(shù)，即對(duì)種群的任意個(gè)體P，其適應(yīng)度為

(7)

3.3 交叉算子

遺傳算法的交叉算子試圖保留更多的優(yōu)良基因，提高個(gè)體適應(yīng)度。由3.1節(jié)可知，第二種編碼的基因是可以重復(fù)的，可以更靈活地設(shè)計(jì)交叉算子。對(duì)此，本文算法設(shè)計(jì)的交叉策略是基于第二種編碼輪流選取以下三種算子對(duì)種群個(gè)體進(jìn)行交叉操作：

(1)兩點(diǎn)交叉，即隨機(jī)產(chǎn)生兩個(gè)基因點(diǎn)，將兩個(gè)個(gè)體對(duì)應(yīng)位置的基因進(jìn)行交換。

(2)片段交叉，即隨機(jī)產(chǎn)生兩個(gè)基因點(diǎn)，將兩個(gè)個(gè)體中介于這兩個(gè)基因點(diǎn)之間的基因片段進(jìn)行整體交換。

(3)一致交叉，即對(duì)兩個(gè)個(gè)體的每一個(gè)對(duì)應(yīng)基因點(diǎn)，按交叉概率進(jìn)行交換。

上述三種交叉算子，對(duì)個(gè)體優(yōu)良基因的改造程度逐次加重，對(duì)交叉后新個(gè)體適應(yīng)度的影響依次加大。輪流運(yùn)用它們，可以合理控制種群基因的進(jìn)化程度，使算法的交叉效果更顯著。

在執(zhí)行上述交叉算子前，需要先調(diào)用編碼轉(zhuǎn)換的“PtoQ”算法，將路徑節(jié)點(diǎn)序列編碼P轉(zhuǎn)換為可重復(fù)自然數(shù)編碼Q；交叉操作結(jié)束后，再調(diào)用“QtoP”算法，將編碼Q再轉(zhuǎn)換為編碼P。

3.4 變異策略

在遺傳算法中，變異算子主要用于維持種群的多樣性，保證算法的局部尋優(yōu)能力，尤其是遺傳進(jìn)化后期其作用更為重要。由于3.3節(jié)設(shè)計(jì)的交叉算子對(duì)種群個(gè)體的交叉作用比較顯著，起到了部分進(jìn)化的作用，為避免破壞交叉效果，本文算法的變異策略是直接針對(duì)父代種群輪流選取以下四種變異算子之一對(duì)種群個(gè)體進(jìn)行變異操作：

(1)基因換位：將待變異個(gè)體中某兩個(gè)隨機(jī)位置處的基因直接進(jìn)行交換。

(2)基因倒序：將待變異個(gè)體中某個(gè)隨機(jī)的基因片段倒序放置。

(3)基因右移：將待變異個(gè)體中某個(gè)隨機(jī)的基因片段循環(huán)右移一次。

(4)基因左移：將待變異個(gè)體中某個(gè)隨機(jī)的基因片段循環(huán)左移一次。

上述四種變異算子都能對(duì)個(gè)體基因產(chǎn)生較明顯的影響，引起旅行商路徑的變化，從而增加種群的多樣性。因此，綜合運(yùn)用它們會(huì)使算法的變異效果更好。

3.5 選擇算子

通過選擇算子，遺傳算法可以朝著理想解的方向進(jìn)化。傳統(tǒng)的選擇算子，如輪盤賭策略、錦標(biāo)賽策略等，充分體現(xiàn)了遺傳算法的“優(yōu)勝劣汰”機(jī)制，但在個(gè)體進(jìn)化效率不高的情形下收斂速度較慢，甚至出現(xiàn)收斂過早的早熟現(xiàn)象。

考慮到上述因素，本文算法的交叉算子和變異算子都是直接對(duì)父代種群進(jìn)行操作，均能使個(gè)體得到更充分的進(jìn)化，因此選擇算子的設(shè)計(jì)主要借鑒了精英個(gè)體選擇思想。具體做法是將父代種群、交叉后的子代種群和變異后的子代種群進(jìn)行合并，計(jì)算合并后的種群個(gè)體適應(yīng)度值按升序排列，選取排名前N(種群規(guī)模)個(gè)個(gè)體直接作為下一代種群。

上述選擇算子在變異操作后執(zhí)行，相較于傳統(tǒng)的選擇算子，該選擇算子合并了父代和子代種群進(jìn)行選擇，讓遺傳的各個(gè)環(huán)節(jié)中進(jìn)化比較充分的個(gè)體都能被選擇出來遺傳到下一代中，因而其遺傳進(jìn)化的收斂速度將更快。

4 算法流程圖

綜上，DCIGA算法求解TSP問題的流程圖如圖1所示。

圖1 DCIGA算法流程圖

5 實(shí)驗(yàn)仿真與分析

為測(cè)試DCIGA算法的性能和有效性，下面從三個(gè)方面進(jìn)行實(shí)驗(yàn)仿真與分析。首先對(duì)DCIGA算法雙編碼方案和傳統(tǒng)遺傳算法單編碼方案的種群質(zhì)量和多樣性進(jìn)行比較，然后將DCIGA算法與其他遺傳算法、其他智能啟發(fā)式算法在求解效果等方面進(jìn)行比較。

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

實(shí)驗(yàn)硬件環(huán)境為Intel Core i5-7200U CPU/4GB，操作系統(tǒng)為windows10，編程環(huán)境為matlab2019a。實(shí)驗(yàn)數(shù)據(jù)選自TSPLIB數(shù)據(jù)集，包括oliver30、att48、eil51、berlin52、st70、pr76、rat99七個(gè)算例。對(duì)前兩個(gè)算例，DCIGA算法的種群規(guī)模和迭代次數(shù)設(shè)置為N=30、G=400；對(duì)后五個(gè)算例，DCIGA算法的種群規(guī)模和迭代次數(shù)設(shè)置為N=50、G=800。算法所需的交叉概率和變異概率均設(shè)置為Pc=0.8，Pm=0.1。

5.2 DCIGA與GA的種群比較

與傳統(tǒng)遺傳算法(GA)相比， DCIGA算法主要是引入了第二種編碼，補(bǔ)足和增強(qiáng)了種群個(gè)體染色體基因的交叉能力。下面通過實(shí)驗(yàn)比較和分析DCIGA算法相比GA算法在種群質(zhì)量和多樣性上的差異和提升。

為評(píng)估種群質(zhì)量，取種群個(gè)體適應(yīng)度的平均值為衡量指標(biāo)(記為AVGR)。對(duì)TSP問題，AVGR值越小，意味著種群個(gè)體的平均適應(yīng)度越小，即旅行商路徑更短，含有優(yōu)良基因的個(gè)體更多，因此種群質(zhì)量就更高。為評(píng)估種群的多樣性，取種群中個(gè)體之間基因不相同個(gè)數(shù)的平均值為其衡量指標(biāo)(記為CH)[1]。CH值越大，則種群中不同個(gè)體相同基因的含量越少，個(gè)體的差異性越明顯，所代表的旅行商路徑不相同的程度越大，因此種群的多樣性更豐富，進(jìn)而有利于更大范圍內(nèi)的搜索尋優(yōu)。

AVGR和CH指標(biāo)的計(jì)算公式如下：

(8)

(9)

其中N為種群規(guī)模，fiti是種群第i個(gè)體的適應(yīng)度值，H(P1，P2)表示個(gè)體P1與P2對(duì)應(yīng)位置基因值不同的個(gè)數(shù)。

對(duì)上述選取的七個(gè)算例，實(shí)驗(yàn)記錄DCIGA算法與GA算法在運(yùn)行同一個(gè)算例相同迭代次數(shù)下種群的AVGR值和CH值，再將算法在相同實(shí)驗(yàn)環(huán)境重復(fù)運(yùn)行20次，計(jì)算出AVGR和CH指標(biāo)的平均值，結(jié)果如表1所示。

從表1可以看到，相比GA算法，DCIGA算法對(duì)七個(gè)算例在種群質(zhì)量和多樣性上都有比較明顯的改善。在種群質(zhì)量上，七個(gè)算例的AVGR指標(biāo)值平均下降幅度為21%，下降幅度最少的是算例att48，約為13%；下降幅度最大的是算例rat99，達(dá)到37%。在種群多樣性上，七個(gè)算例的CH指標(biāo)值平均提升幅度為148%，提升幅度最少的是算例rat99，約為98%，提升幅度最大的是算例oliver30，達(dá)到258%。

綜合來看，采用雙編碼方案，增強(qiáng)遺傳算法的交叉操作后，對(duì)改善種群質(zhì)量和提升種群多樣性均有比較明顯的效果，為算法搜索尋優(yōu)奠定了良好的基礎(chǔ)。

表1 種群質(zhì)量和多樣性比較

5.3 DCIGA與其他改進(jìn)遺傳算法結(jié)果對(duì)比

DCIGA算法是在傳統(tǒng)遺傳算法基礎(chǔ)上改進(jìn)的，為驗(yàn)證該算法與其他改進(jìn)遺傳算法的性能，將DCIGA算法與GA算法、混合遺傳算法(Hybrid Genetic Algorithm，HGA)[27]和改進(jìn)遺傳算法(Improve the Genetic Algorithm，IGA)[18]進(jìn)行比較。

實(shí)驗(yàn)數(shù)據(jù)仍選取5.1節(jié)中所述七個(gè)算例，各個(gè)算法在相同實(shí)驗(yàn)環(huán)境中分別獨(dú)立運(yùn)行20次，記錄并統(tǒng)計(jì)求解結(jié)果的最好最優(yōu)解(Best)、平均值(AVG)、偏差率(Dr)、方差(PD)，將其作為算法的比較指標(biāo)。 其中偏差率和方差的計(jì)算公式為：

(10)

(11)

式中，Opt為TSPLIB數(shù)據(jù)集提供的最優(yōu)解。

實(shí)驗(yàn)結(jié)果如表2所示，當(dāng)所求得的最優(yōu)解優(yōu)于Opt時(shí)，表中指標(biāo)偏差率(Dr)和方差(PD)就用“*”表示。從表2可以看到，DCIGA算法在給定算法參數(shù)下能求得比另外三種改進(jìn)遺傳算法更好的最優(yōu)解，當(dāng)TSP問題規(guī)模較小時(shí)(算例oliver30、att48)，DCIGA算法還可以求得比TSPLIB數(shù)據(jù)集所給最優(yōu)解更好的結(jié)果，其中oliver30算例的優(yōu)化幅度達(dá)到了9.76%。從最優(yōu)解平均值(AVG)來看，前六個(gè)算例的求解結(jié)果均優(yōu)于另外三種改進(jìn)遺傳算法，并且多次運(yùn)行時(shí)的方差(PD)值也更小，表明DCIGA算法的穩(wěn)定性和魯棒性都更強(qiáng)。對(duì)算例rat99，雖然IGA算法和HGA算法的平均值(AVG)和方差(PD)略優(yōu)于DCIGA算法，但在最好最優(yōu)解(Best)上，DCIGA算法的表現(xiàn)要更優(yōu)，體現(xiàn)了它具有更強(qiáng)的全局搜索尋優(yōu)能力。此外，DCIGA算法的所有算例最優(yōu)解平均值都優(yōu)于GA算法最好最優(yōu)解，優(yōu)化幅度約為17%～34%，且城市規(guī)模越大，兩者之間差距越大。從偏差率(Dr)來看，DCIGA算法的平均偏差率低于其他算法的平均偏差率，表明DCIGA算法求解TSP問題的精度更優(yōu)。

表2 4種改進(jìn)遺傳算法實(shí)驗(yàn)結(jié)果對(duì)比

綜合來看，DCIGA算法優(yōu)于其他的改進(jìn)遺傳算法，具有良好的求解性能和尋優(yōu)效果，能夠較好的求解TSP問題，對(duì)中小規(guī)模TSP問題的求解性能更為突出。

5.4 DCIGA與其他啟發(fā)式算法結(jié)果對(duì)比

為進(jìn)一步驗(yàn)證DCIGA算法的性能，本節(jié)將DCIGA算法與最近領(lǐng)域算法(The Nearest Neighborhood Algorithm，NN)[28]、模擬退火算法 (Simulated Annealing，SA)[18]、雙向擴(kuò)展差額結(jié)合算法(Two Directions Moving With Difference Algorithm，TDMDA)[29]、蟻群算法(Ant Colony Optimization，ACO)[30]等啟發(fā)式算法的求解結(jié)果進(jìn)行對(duì)比，本文中的DCIGA算法仍然在前述給定參數(shù)和實(shí)驗(yàn)環(huán)境下運(yùn)行，如表3所示。

表3 DCIGA算法與啟發(fā)式算法實(shí)驗(yàn)結(jié)果對(duì)比

從表3可以看到，DCIGA算法在最好最優(yōu)解(Best)和最優(yōu)解平均值(AVG)上都要優(yōu)于其他四種啟發(fā)式算法，表明該算法的整體求解性能要優(yōu)于其他啟發(fā)式算法，算法穩(wěn)定性和全局尋優(yōu)能力更強(qiáng)。圖2為表3中DCIGA算法對(duì)3組算例所求得的最好最優(yōu)解(Best)所對(duì)應(yīng)的最優(yōu)路徑圖。

(a)att48 (b)eil51 (c)pr76

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

本文在遺傳算法的通用框架下，針對(duì)經(jīng)典的旅行商(TSP)問題，引入一種基因可重復(fù)的編碼方案，使得遺傳算法設(shè)計(jì)交叉算子時(shí)更靈活和方便，既避免了非法編碼個(gè)體的產(chǎn)生，也大大增強(qiáng)了種群的質(zhì)量和多樣性，相比算法中增加的編碼轉(zhuǎn)換所耗費(fèi)的時(shí)間，實(shí)驗(yàn)表明這種做法是值得的。此外，本文還將多種交叉算子、變異算子輪流選擇，作用于不同的個(gè)體，也增強(qiáng)了算法的局部尋優(yōu)能力，特別是在迭代后期，有利于算法避免早熟，跳出局部最優(yōu)。這些改進(jìn)思路對(duì)促進(jìn)遺傳算法的運(yùn)用和發(fā)展都有積極意義，和遺傳算法的其他策略相結(jié)合，甚至可以進(jìn)一步有效求解中大規(guī)模TSP問題，將來可以為生產(chǎn)實(shí)踐提供更多決策依據(jù)。