趙新超，郭賽

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

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

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

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

1 3種染色體方案

MTSP染色體的設(shè)計(jì)主要有以下3種[1]。

1.1 單染色體設(shè)計(jì)

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

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

1.2 雙染色體設(shè)計(jì)

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

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

1.3 兩段式染色體設(shè)計(jì)

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

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

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

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

2.1 相對(duì)解空間

3種染色體編碼方案對(duì)應(yīng)的解空間大小[1]分別為

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

2.2 相對(duì)解空間的極限分析

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

2.2.1 C31的極限分析

1) m適當(dāng)大時(shí)

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

所以 C31＜1。

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

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

(n–1)!可與 (n+m–1)!相抵消，n!可與 (n–m)!相抵消，所以當(dāng)n趨于無(wú)窮時(shí)得出：

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

2.2.2 C32的極限分析

1)m適當(dāng)大時(shí)

C32＜1同樣意味著第三種編碼方案對(duì)應(yīng)的解空間小于第二種方案對(duì)應(yīng)的解空間。同C31的分析類似，當(dāng)n足夠大、m適當(dāng)大時(shí)，。

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

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

2.2.3 C12的極限分析

至此，在合理適當(dāng)?shù)臈l件下：n適當(dāng)大，對(duì)3種解空間的相對(duì)大小給出詳細(xì)嚴(yán)密的論證，很好地補(bǔ)充了文獻(xiàn)[1]中定性的結(jié)論，即，而且由分析可知，當(dāng)n充分大、m適當(dāng)大時(shí)，。

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

2.3 相對(duì)搜索空間的粗略估計(jì)

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

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

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

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

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

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

2.4 分情形下的相對(duì)解空間大小分析

2.4.1 Stirling公式

相對(duì)解空間表達(dá)式中出現(xiàn)階乘項(xiàng)，增加了相應(yīng)的分析和對(duì)比運(yùn)算，而我們?cè)诖艘懻摰氖莔、n取較大正整數(shù)時(shí)相對(duì)解空間的變化屬性，因此本文用Stirling公式來(lái)近似化簡(jiǎn)分式[14](當(dāng)n取充分大的正整數(shù)時(shí)，用多項(xiàng)式代替階乘運(yùn)算)，圖8為階乘項(xiàng)和等價(jià)的多項(xiàng)式項(xiàng)的變化示意圖。Stirling公式為

2.4.2 n=10m時(shí)相對(duì)解空間分析

當(dāng)n=10m時(shí)：

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

圖8 n!與變化示意圖

式（8）是一個(gè)關(guān)于m的分式，可分為3個(gè)部分。當(dāng)m取較大值時(shí)，第一部分可以用近似代替，第二部分是冪指數(shù)次項(xiàng)，在m較大時(shí)可以用代替，第三部分可以化簡(jiǎn)為。在這三項(xiàng)中，增長(zhǎng)速度主要體現(xiàn)在第二項(xiàng)和第三項(xiàng)冪指數(shù)項(xiàng)，也就是說(shuō)，我們?cè)u(píng)價(jià)整個(gè)代數(shù)表達(dá)式隨著m的增大其增長(zhǎng)速度可以用第二項(xiàng)和第三項(xiàng)代替。

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

因增長(zhǎng)速度主要體現(xiàn)在第二項(xiàng)和第三項(xiàng)冪指數(shù)項(xiàng)，也就是說(shuō)，我們?cè)u(píng)價(jià)整個(gè)代數(shù)表達(dá)式隨著m的增大其增長(zhǎng)速度可以用第二項(xiàng)和第三項(xiàng)代替。于是，式(8)化簡(jiǎn)結(jié)果為

同樣

當(dāng)m取較大正整數(shù)時(shí)，指數(shù)項(xiàng)可以用二項(xiàng)展開式的前兩項(xiàng)近似替代，具體過(guò)程不在此贅述，以下相似替代過(guò)程將不特殊說(shuō)明，式(11)化簡(jiǎn)為

則該等式可表示為

對(duì)于C12同樣可得到：

則該等式可表示為

由前兩個(gè)關(guān)系式：

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

2.4.3 平方關(guān)系下的相對(duì)解空間分析

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

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

將 n=m2代入式（19）：

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

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

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

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

繼而將n=m2代入C12化簡(jiǎn)得到

2.4.4 指數(shù)關(guān)系下的相對(duì)解空間分析

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

將 n=em代入式（4）：

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

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

繼而將n=em代入C12化簡(jiǎn)得到：

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

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

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