遺傳算法求解多旅行商問題的相對解空間分析

趙新超，郭賽

多旅行商問題(multiple traveling salesman problem，MTSP)可直觀描述為一個旅行商團隊要分頭遍歷若干個城市，每個城市至少被一個旅行商訪問一次且只訪問一次，如何安排m(大于1)位旅行商遍歷n(大于m)個城市，使得總的訪問行程最小[1]。該問題最常見的應用領域是車間調度領域，在生產線上的作業(yè)調度通常被建模為一個旅行商問題(traveling salesman problem，TSP)。如果生產經營擴展到有多條平行線，工作可以分配，這個問題可以建模為一個多旅行商MTSP[2]；另一個經常被建模為多旅行商問題的就是車輛調度問題(VSP)[3]。車輛調度問題是指對一些車輛進行調度，所有的車輛離開并回到原地點，使得每個地方只能而且必須被訪問一次。

由于多旅行商問題的復雜性，必須根據(jù)實際問題的大小采用啟發(fā)式解決方案[4]。遺傳算法(genetic algorithms，GA)[5]是一種基于生物自然選擇和基因遺傳學原理的高效并行、隨機全局優(yōu)化搜索算法。Keshavarz等[6]學者發(fā)現(xiàn)遺傳算法對調度問題有很強的適應性，MTSP有效的遺傳算子也激發(fā)了研究者的極大興趣；張永庫等[7]研究了改進的遺傳算法在模糊聚類中的表現(xiàn)；Katayama等[8]提出的混合變異遺傳算法在旅行商問題中的應用提高了遺傳算法解決旅行商問題的性能。多旅行商問題在實際問題中有很廣泛的應用。Huang等[9]研究了多旅行推銷員問題在熱軋規(guī)劃中的應用；江賀等[10]研究了近年來出現(xiàn)的新NP-難解問題，即黑白旅行商問題(BWTSP)，給出了遺傳算法解決問題的一種新思想；Trigui等[11]提出一種解決多機器人系統(tǒng)多目標多旅行推銷員問題的模糊邏輯方法。最近出現(xiàn)了多種解決TSP問題的方法，王宇平等[12]提出的求解TSP的量子遺傳算法使用了有關量子方面的知識。研究者們也在其他經典優(yōu)化算法[13]中找到了許多新思想。

遺傳算法求解MTSP的關鍵是要根據(jù)問題設計一種好的染色體編碼方法，而好的遺傳算法染色體編碼方案應該能夠從候選解中減少或消除冗余的解。冗余解是指以一種以上的方式表示同一染色體，并多次出現(xiàn)在種群中的染色體編碼方式。相同解的多次再現(xiàn)不僅增加了查找空間，而且降低了查找效率。

本文首先列出了傳統(tǒng)的兩個染色體方案(單染色體設計方案和雙染色體方案)，以及最近提出的較新的兩段式染色體設計方案；本文引入相對解空間概念，以此定量地衡量不同染色體方案給出的相對解空間大小關系，先給出對旅行商數(shù)目和城市數(shù)目在趨于無窮時的極限相對大小關系，接下來近似分析了旅行商數(shù)目與城市數(shù)目在不同情形下解空間的相對大小關系。

1 3種染色體方案

MTSP染色體的設計主要有以下3種[1]。

1.1 單染色體設計

圖1描述了MTSP問題城市數(shù)n=15、旅行商數(shù)m=4時染色體編碼的一種設計方法的一個實例。這種設計使用了一個染色體編碼長度為n+m–1的染色體，因此被稱為“單染色體”(one chromosome)設計。該設計方案中，n個城市用從1～n正整數(shù)編碼表示，并進行無規(guī)則的排列，代表著n個城市的整數(shù)編碼列被–1～–(m–1)這m–1個負整數(shù)分為m段，分別依次對應著有序的m個旅行商所訪問的城市，因此這個長度為n+m–1的整數(shù)列的任何一種排列組合都可能是這個MTSP問題的解。以圖1為例，第一個旅行商將訪問編號為2、5、14、6的這幾座城市，第二個旅行商將訪問編號為1、11、8、13的這幾座城市，依次類推。在這種染色體設計中，MTSP所有問題的解將可能是由(n+m–1)!個解構成的一個空間。這些解中有很多是冗余的，例如，旅行商1與旅行商2的訪問城市全部按順序相互調換位置后的解和現(xiàn)有解。

圖1 單染色體方案Fig. 1 One chromosome

1.2 雙染色體設計

圖2 描述了同樣一個MTSP問題由遺傳算法中染色體編碼方案的另一種設計方法。一般稱它為“雙染色體(two chromosomes)”設計。這種設計使用兩個長度為n的染色體表示一個解。圖2中，第一個染色體表示n個城市的一組排列，第二個染色體的每一位數(shù)對應上面相應的城市，由對應編碼的旅行商來訪問。例如，旅行商l訪問的城市為5、14、10、15，旅行商2 訪問的城市為 2、8、12、9。使用這種編碼設計，對應的空間是由n!mn個可能的解構成的一個集合。同樣，這種編碼方案也有許多冗余的解。例如，上述事例解中頭兩個基因位交換位置后得到的解與現(xiàn)有解就是相同的。

圖2 雙染色體方案Fig. 2 Two chromosomes

1.3 兩段式染色體設計

圖3 描述了一個新的染色體設計方案，它由前后兩個部分組成，因此稱為“兩段式染色體(two-part chromosome)”設計。前段是整數(shù) l～n的一個排列，代表了n個城市的一個順序排列；后段長度為m，按順序分別表示m個旅行商在前段編碼中對應訪問的城市數(shù)，并且這m個數(shù)之和等于n。圖3所示旅行商l訪問前段中的頭4個城市順序分別為2、5、l4、6；旅行商3訪問從第4+4+1個開始的連續(xù)3個城市，分別為4、10、3。使用新的兩段式染色體設計，不僅減少了查找空間，而且由于固定了旅行商的順序而消除了部分(但不是全部的)冗余的解。使用這種染色體編碼設計，對于前段可能會有n!種排列，后段由于是一個和為n的正整數(shù)向量，因此需要種可能的m維正整數(shù)表示，才能滿足要求。從而，可以得到解空間大小為。

圖3 兩段式染色體方案Fig. 3 Two-part chromosome

2 3種染色體編碼方案下的相對解空間分析

上一節(jié)介紹了遺傳算法求解多旅行商問題的3種染色體編碼方案。文獻[1]給出了3種染色體編碼方案對應的搜索空間的大小，僅是定性分析了3種方案的優(yōu)劣，即兩段式染色體方案對應的解空間優(yōu)于前兩種編碼方案對應的解空間，而第一種單染色體設計方案優(yōu)于雙染色體編碼方案。如果只是定性地了解3種編碼方案對應解空間大小關系，對染色體編碼方案和算法設計以及實際工程應用并沒有太大的指導意義。因此本文首先引入相對解空間概念，然后詳細地定量分析了3種染色體方案對應的解空間相對大小，這對多旅行商問題的研究和求解具有現(xiàn)實的指導意義。

2.1 相對解空間

3種染色體編碼方案對應的解空間大小[1]分別為

式中：Cone表示單染色體編碼對應的解空間規(guī)模，Ctwo表示雙染色體編碼對應的解空間規(guī)模，表示兩段式染色體解空間的規(guī)模。從3種編碼方案解空間的代數(shù)表達式可以看出，它們都是城市數(shù)n和旅行商數(shù)目m的二元函數(shù)，自變量n和m的取值范圍是正整數(shù)，且一般m＜n(旅行商人數(shù)小于城市數(shù))。

2.2 相對解空間的極限分析

在現(xiàn)實的工程應用中，比如車輛調度問題，m、n一般取值較大，因此隨著自變量的增大或問題規(guī)模的擴大，我們需要了解相對解空間對應的比值結果的變化趨勢，從而從數(shù)學表達式中討論m和n取較大正整數(shù)時，相對解空間的極限行為，也可以認為是討論m、n趨于無窮時的極限。

2.2.1 C31的極限分析

1) m適當大時

在多旅行商問題中，城市數(shù)目與旅行商數(shù)目之間的差距一般都比較大，因此當討論C31的極限性質時，不妨假設，當n充分大、m應適當大時，對C31取對數(shù)，分析可得：

所以 C31＜1。

C31＜1意味著第三種編碼方案對應的解空間嚴格小于第一種方案對應的解空間，這嚴格證明了Carter[1]給出的解空間的定性比較結果。當n足夠大時，所需的旅行商數(shù)也有相應增大，因此當n充分大、m適當大時，。例如：m=10，。

2) m是不大的常數(shù)時

(n–1)!可與 (n+m–1)!相抵消，n!可與 (n–m)!相抵消，所以當n趨于無窮時得出：

即當旅行商人數(shù)m取不大的常數(shù)時，隨著城市數(shù)目的增加，單染色體編碼方案對應的空間約是兩段式染色體方案解空間的(m–1)！倍，此結果與兩種解空間的極限分析是一致的。

2.2.2 C32的極限分析

1)m適當大時

C32＜1同樣意味著第三種編碼方案對應的解空間小于第二種方案對應的解空間。同C31的分析類似，當n足夠大、m適當大時，。

2)m是不大的常數(shù)時

由對C32的分析可知，當m取大于2的常數(shù)時，C32＜ 1。此結果顯示，第三種編碼方案對應的解空間小于第二種編碼方案對應的解空間，此結果與兩種解空間的極限分析是一致的。

2.2.3 C12的極限分析

至此，在合理適當?shù)臈l件下：n適當大，對3種解空間的相對大小給出詳細嚴密的論證，很好地補充了文獻[1]中定性的結論，即，而且由分析可知，當n充分大、m適當大時，。

以上分析中，對一般的m和n給出的是相對解空間理論上的對比，但是如果只知道相對大小，對實際問題應用幾乎沒有實質性的幫助，例如求C31的極限，實質上m為常數(shù)，n逐漸增大，也就是說，在某一個多旅行商問題中，我們保持商人的數(shù)目不變，增大工程的規(guī)模，讓城市數(shù)目逐漸增大，這也就意味著單個商人訪問的城市數(shù)目隨著城市數(shù)目的增多而無限增加下去，這顯然不符合實際情況，因為每個旅行商訪問的城市數(shù)目是有上限的，即最大負荷能力。因此單一用這個極限結果去估計解空間的大小，雖然能得出嚴密的定量分析結果，但是其代表的實際意義是不乏片面性的。

2.3 相對搜索空間的粗略估計

圖4描述了l5個城市，是旅行商數(shù)量從l增加到14時，3種染色體編碼設計的搜索空間的變化示意圖。圖4的縱軸表示搜索空間的數(shù)量級。由圖4可以看出，在旅行商逐步增加的情況下，單染色體編碼對應的搜索空間數(shù)量的增加由快到慢；雙染色體編碼對應的搜索空間數(shù)量的增加比較平穩(wěn)；而兩段式染色體編碼對應的搜索空間數(shù)量呈現(xiàn)兩端相當、中間略微增加的大體對稱的情況。因此圖4與2.2節(jié)的解空間分析結果顯示出了兩段式染色體編碼設計的初步優(yōu)越性。

眾所周知，當城市數(shù)目逐步增加時，旅行商人數(shù)也應該相應增加，而m一般會隨n的變化而變化。以下詳細討論m與n有特定關系時的相對搜索空間。例如：n=10m，n=m2，n=em三種情形下，相對搜索空間的變化趨勢。

圖4 解空間變化示例Fig. 4 Example of solution space change

從圖5～7所示的3組函數(shù)圖像可以看出，3種情形下的相對搜索空間變化，總體來說，從相對搜索空間上比較，在n=10m和n=m2情形下，C31和C32在前期的差別不大，縱軸隨著m的增大很快收斂，且C12在n=m2情形下比在n=10m情形下收斂得更快些；在n=em情形下C32相對搜索空間和C12相對搜索空間比其他兩種情形收斂更快，但C31在前期收斂得有些緩慢，而在n=em情形下明顯比其他兩種情形收斂更快。從同一情形下看3種相對搜索空間的變化時，可以看出C31、C32和C12都是縱軸隨著m的增大很快收斂，C32和C12收斂較快些，在m≤6時就能定性地看出收斂；C31收斂最慢，在m取較大值時能判斷出也是收斂的。從兩種判斷方法中我們能夠看出收斂，但是很難直觀地從函數(shù)圖像上直接看出m取較大值時的收斂狀況，也即只能定性得出收斂的結論，這與前面的結論亦是吻合的。

圖5 n=10m情形下的相對搜索空間變化曲線圖Fig. 5 Solution space change in the case of n= 10 m

圖6 n=m2情形下的相對搜索空間變化曲線圖Fig. 6 Solution space change in the case of n=m2

2.4 分情形下的相對解空間大小分析

2.4.1 Stirling公式

相對解空間表達式中出現(xiàn)階乘項，增加了相應的分析和對比運算，而我們在此要討論的是m、n取較大正整數(shù)時相對解空間的變化屬性，因此本文用Stirling公式來近似化簡分式[14](當n取充分大的正整數(shù)時，用多項式代替階乘運算)，圖8為階乘項和等價的多項式項的變化示意圖。Stirling公式為

2.4.2 n=10m時相對解空間分析

當n=10m時：

圖7 情形下的相對搜索空間變化曲線圖Fig. 7 Solution space change in the case of

圖8 n!與變化示意圖

式（8）是一個關于m的分式，可分為3個部分。當m取較大值時，第一部分可以用近似代替，第二部分是冪指數(shù)次項，在m較大時可以用代替，第三部分可以化簡為。在這三項中，增長速度主要體現(xiàn)在第二項和第三項冪指數(shù)項，也就是說，我們評價整個代數(shù)表達式隨著m的增大其增長速度可以用第二項和第三項代替。

在計算機程序設計中，衡量一個算法的好壞，通常會用到時間復雜度和空間復雜度。性按照某一速度增長。它只表示增長的速度(Order)，這個時間或空間復雜度并不是與程序復雜性嚴格相等的數(shù)學表達式，它只抽象表示增長速度的類型，通常用大O表示法。本文中的解空間的大小也稱為空間復雜度，也同樣用算法設計中的空間復雜度表示法(大O表示法)來衡量本文中討論的3種染色體設計方案的相對解空間。

因增長速度主要體現(xiàn)在第二項和第三項冪指數(shù)項，也就是說，我們評價整個代數(shù)表達式隨著m的增大其增長速度可以用第二項和第三項代替。于是，式(8)化簡結果為

同樣

當m取較大正整數(shù)時，指數(shù)項可以用二項展開式的前兩項近似替代，具體過程不在此贅述，以下相似替代過程將不特殊說明，式(11)化簡為

則該等式可表示為

對于C12同樣可得到：

則該等式可表示為

由前兩個關系式：

用等式(17)除以等式(16)可得

2.4.3 平方關系下的相對解空間分析

上一小節(jié)討論了3種染色體方案在城市數(shù)目與旅行商人數(shù)為線性關系時，解空間的相對大小關系，實際上，在線性關系n=km下，系數(shù)k代表的是平均每個商人訪問的城市數(shù)目。因此討論相對解空間時，讓m逐漸遞增時，k是作為常數(shù)處理的，也就是說，平均每個商人訪問的城市數(shù)目是大體不變的。在現(xiàn)實的工程問題中，隨著工程規(guī)模的增加，即待訪問城市數(shù)目的急劇增多，旅行商的人數(shù)也應該隨之增加?？紤]這個實際問題時，不應該單純依靠旅行商人數(shù)的增加來完成所有城市的訪問，也應該隨著城市的增加，相應地增大每個商人的工作負載，即訪問城市的數(shù)目。于是，我們應該找到一個函數(shù)來表示城市數(shù)目和旅行商人數(shù)的關系，滿足隨著城市數(shù)目的增多，旅行商人數(shù)也隨之增加，同時平均每個商人訪問的城市數(shù)目也隨之相應增加?？紤]到城市數(shù)與旅行商人數(shù)的關系和商人訪問城市效率的不同，本文選擇兩種常見的不同增速關系，即二次冪函數(shù)與指數(shù)增長關系。

本節(jié)討論n與m在二次函數(shù)關系下相對解空間的收斂速度。

將 n=m2代入式（19）：

同樣用二項展開式的前兩項去近似代替指數(shù)項部分，式（19）可簡化為

同樣將n=m2代入式（22）：

式（22）的增長速度仍取決于第二項的冪指數(shù)項，所以式（22）關系可表示為

童話大王鄭淵潔說：“寫童話，我不如孩子！”童話大王為什么這么說呢？大概是因為隨著年齡的增長，人的認識越來越理性。人越來越成熟，而童真童趣卻離我們越來越遠。也許，在你三歲的時候，你會說出“風把嗓子哭啞了”這樣的句子，而現(xiàn)在卻只能說出“狂風怒吼”這樣的成語……想要找回自己的童真童趣，一定有很多辦法。今天老師要介紹的方法就是：在比你更小的小小孩身上去尋找自己的童年。你有三四歲的小弟弟小妹妹嗎？請觀察他們，記錄他們的行為、他們的語言……持續(xù)觀察一些日子，你一定會有所收獲的。

繼而將n=m2代入C12化簡得到

2.4.4 指數(shù)關系下的相對解空間分析

本節(jié)討論n與m在指數(shù)函數(shù)關系下相對解空間的收斂速度。

將 n=em代入式（4）：

同樣將n=em代入式（5）得

式(28)的增長速度仍是取決于第二項的冪指數(shù)項，所以式（28）關系可表示為

繼而將n=em代入C12化簡得到：

3 結束語

本文首先介紹了多旅行商問題的概念和3種染色體編碼方案，已有文獻只是定性地給出3種編碼方案對應解空間的大小關系，并沒有給出嚴格證明。本文首先給出相對解空間的概念，然后在城市數(shù)充分大和城市數(shù)大于旅行商人數(shù)的條件下，在極限意義下嚴格證明了3種解空間的相對大小關系，最后利用Stirling公式嚴密分析了幾種染色體編碼方案中旅行商人數(shù)和城市數(shù)目在不同關系下相對解空間的大小，得出了相對解空間的理論增長速度，給實際工程問題求解中染色體編碼方案的選擇提供了科學的參考依據(jù)和指導意義。

基于3種染色體方案求解多旅行商問題的相對解空間大小關系分析，就目前方案給出的解空間仍然有冗余解存在。兩段式染色體方案在單染色體方案和雙染色體方案基礎之上消除了相當大的一部分冗余，雖然沒有完全消除，但是給了我們很大啟發(fā)，去尋找更加合理的新的染色體編碼方案以進一步減小解空間的冗余。