孔令夷

(西安郵電大學管理工程學院，西安 710061)

1 引 言

公路運輸路徑問題在圖論中具有代表性，已被證明是高維非線性完全問題(NPC，Non-deterministic Polynomial Complete Problem)［1］，具有高度的計算復雜性，多年來都是理論界與企業(yè)界面臨的難題.如何將智能優(yōu)化算法中經(jīng)典的遺傳算法、改進遺傳算法應用于這一難題的全局優(yōu)化求解，也成為了眾多學者研究的對象.

求解公路運輸路徑問題的傳統(tǒng)方法存在明顯的缺陷:設計變量少，與現(xiàn)實不相符;假設較多，對目標函數(shù)有可微或連續(xù)的諸多限制，否則，在求解中必然會產(chǎn)生非可行解，難以得到全局最優(yōu)解，或者也只能求出局部最優(yōu)解.顯而易見，傳統(tǒng)求解方法不能很好地模擬實際問題的各種復雜情境，尤其是存在非連通圖約束的情況下，運籌規(guī)劃等傳統(tǒng)求解方法更是難以應對，無法客觀準確地把實際問題轉化為數(shù)學模型.1967年，Bagley首次提出了遺傳算法(Genetic Algorithm，GA)，相比傳統(tǒng)的運籌規(guī)劃方法應用更加廣泛，實用價值更高，在處理大多數(shù)科學與工程復雜問題時顯得游刃有余，幾乎都能找到滿意解.這主要源于以下四點:第一，GA并不是直接處理運輸路徑中的顯性變量，而是對變量編碼，編碼之后可以任意組合成串，即染色體，這才是GA后續(xù)處理的對象，可見其對運輸路徑優(yōu)化等復雜問題幾乎沒有什么限制;其次，在求最優(yōu)解的過程中，GA對問題的限制不多，對目標函數(shù)的數(shù)學特性要求也不嚴格，能夠接受各種類型的目標函數(shù)，線性或非線性，離散或連續(xù)，可微或不可微，這又再次體現(xiàn)了它的普適性;第三，傳統(tǒng)求解方法往往是從一個初始解開始，經(jīng)過多次迭代的過程求得最優(yōu)解，求解線路單一，而GA不是沿著一條線，而是基于面上的一代種群求解，從上一代(父代)的很多染色體(個體)開始評估選擇，擇優(yōu)后再經(jīng)過交叉變異等基因遺傳方式形成下一代(子代)，這樣就容易保留更多優(yōu)良的個體，而淘汰較劣的個體，實現(xiàn)“優(yōu)勝劣汰，適者生存”，幾代遺傳之后就能基本保證得到全局最優(yōu)解;第四，GA的擇優(yōu)去劣過程，只以個體的適應度值作為判斷，不需要補充更多信息，操作簡便易行;最后，GA基于概率論的知識而進行遺傳操作，求出具有較高可信度的最優(yōu)解，不排除進一步的改善，而不像傳統(tǒng)方法必須給出確定性解，從而也確保了GA的靈活性和可改進性［2］.

眾多學者嘗試應用GA優(yōu)化公路運輸路徑，然而，傳統(tǒng)遺傳算法(TraditionalGenetic Algorithm，TGA)嚴重依賴于參數(shù)設置和交叉變異算子，存在早熟收斂缺陷［3，4］.為此，學者們設計了各種改進遺傳算法.黃永青等設計一種小種群自適應遺傳算法，平衡了探測和開發(fā)操作，提升了尋優(yōu)能力［5］.陶林波在保留自適應性的前提下，引入與種群分布相關聯(lián)的動態(tài)交叉、變異算子，實現(xiàn)動態(tài)種群中尋找最優(yōu)解［6］.李鋒等研究了動態(tài)流量下的路徑求解，引入非平穩(wěn)隨機因子，設計出仿真算法，并用算例檢驗了效果［7］.周輝仁等設計了遞階染色體編碼和矩陣解碼法［8］.王美華等開發(fā)了二進制和整數(shù)混合的染色體編碼方案，優(yōu)化了交叉和變異算子，并驗證了新算法的有效性［9］.韓麗霞等開發(fā)了新的編碼及解碼規(guī)則，引進雜交算子，運用局部搜索加強雜交算子，并驗證了其有效性［10］.朱云飛等引入貪婪的復合變異算子、隔代爬山法算子，算例檢驗了有效性［11］.汪民樂等考慮子代結構及適應度，基于FS理論改進種群成熟度指標，提出早熟預防策略［12］.郟宣耀等基于 Niche思想改進 TGA，既保留子代多樣性及優(yōu)良性，同時提高了求解的可靠性［13］.賀毅朝等研究了TGA中傳統(tǒng)貪心變換的局限性，對其改進后與GA結合，得到了更理想的貪心遺傳算法，并證實了新算法的優(yōu)勢［14］.田建立等引入混沌搜索技術，以加強GA的尋優(yōu)能力［15］.Bierwirth等在對各類交叉操作實驗對比的基礎上，提出優(yōu)先保留交叉法(Precedence Preservation Crossover，PPX)，在很大程度上克服了TGA的常見缺陷［16］.Murata等通過大量仿真實驗研究，提出平移變異(Shift Change Mutation，SCM)操作，并引入局部鄰域搜索，使得GA被改進后能在確保子代遺傳質量的前提下加快收斂［17］.

以上改進都局限于GA的某個環(huán)節(jié)，達不到全局優(yōu)化;或者應用于特定情形，比如小種群、動態(tài)或距離對稱條件.為此，擬提出全過程改進的混沌遺傳算法(Chaos Genetic Algorithm，CGA):綜合隨機法與貪心法生成初始染色體種群;基于遍歷城市次序編碼;執(zhí)行交叉變異、局部鄰域及混沌搜索操作;運用賭輪法作出選擇，并給出最優(yōu)解可行判據(jù).

2 問題描述

現(xiàn)實中的公路運輸路徑問題一般都會有各種約束或限制，比如非連通圖就是一個典型的例子，即公路運輸路徑中要經(jīng)過的某些目的地(比如城市)之間存在障礙物，比如山川、農(nóng)田等，不能直接通達，只有繞道而行，通過其他地點而間接到達.這類問題中經(jīng)過的所有地點將連成一個非連通圖，如圖1所示的城市1和城市2之間.

圖1 非連通圖Fig.1 Unconnected graph

本研究的目的就是尋找最短路徑，將公路運輸成本降到最低.該路徑經(jīng)過所有N個城市，除了起點以外，都要經(jīng)過且只經(jīng)過1次，最終回到起點，這也比較符合實際公路運輸遍歷所有城市實現(xiàn)物流量最大化的實際情形.設有N個城市的集合C=｛c1，c2，…，cN｝，每兩個城市之間的距離為 d(ci，cj)∈R+，其中，ci，cj∈C(1≤i，j≤N).

求使目標函數(shù)

最小的路徑序列｛cП(1)，cП(2)，…，cП(N)｝，其中 П(1)，П(2)，…，П(N)是1，2，…，N 的全排列.

3 混沌遺傳算法設計

3.1 編碼方式

本研究的編碼采用基于公路運輸路徑需要遍歷的所有城市的次序，這也是最常用的編碼方式，以有限的城市數(shù)量作為搜索范圍，有助于提高搜索效率.例如設S=(1，5，4，3，2，6，7)，就可以看成是從城市1 出發(fā)，依次經(jīng)過城市 5、4、3、2、6、7，最終回到起點的公路運輸路徑.

3.2 初始種群生成

初始種群的質量對后續(xù)的優(yōu)化求解具有關鍵作用.若按隨機方式產(chǎn)生初始種群，難以保證其滿足非連通約束，也就容易產(chǎn)生很多非可行解，從而降低了TGA的效率.擬對其改進為綜合隨機法與貪心法來產(chǎn)生初始染色體種群，從而提高其優(yōu)良性.

3.3 交叉變異操作

基于城市次序的編碼方式，基因存在先后關系.為了不破壞這種關系，擬選用PPX和SCM操作.PPX操作過程是:隨機產(chǎn)生兩個父代個體，并產(chǎn)生一個等長的{1，2}隨機串;掃描隨機串，如果第k位是1，則提取第一個父代染色體最左邊的城市號作為子代第k位，如果第k位是2，則提取第二個父代染色體最左邊的城市號，然后刪除兩個父代中的該城市號，重復以上操作，直到隨機串被掃描完.由上可見，PPX與映射交叉、次序交叉或循環(huán)交叉相比，能夠更好地繼承父代優(yōu)良基因.

SCM操作是指隨機選擇插入碼和插入點，進行平移操作.比如S=(1，5，4，3，2，6，7)，若隨機選取插入碼為6，插入點為5與4之間，則S’=(1，5，6，4，3，2，7)，SCM 與對換變異、目標導向變異等相比，更好地保持了基因之間的先后次序，繼承了父代的優(yōu)良性.

3.4 局部鄰域搜索及混沌搜索

擬引入局部鄰域搜索，加快算法收斂，縮短求解時間.以交叉變異操作產(chǎn)生的子代個體為基體，對每個基因采用右鄰基因交換的方法產(chǎn)生新的局部鄰域子代個體.例如 S’=(1，5，6，4，3，2，7)，將基因2與其右鄰的基因7交換，就能生成一個新個體 S’’=(1，5，6，4，3，7，2).因此，局部鄰域搜索能產(chǎn)生N－1個局部鄰域子代個體，從中選擇具有最大適應度的鄰域個體與基體再做比較，以適應度大者為更新后的子代基體.

接著，執(zhí)行基于冪函數(shù)載波的混沌搜索，操作過程如下［15］:

(1)利用混沌向量對初始值的敏感性，對式(2)賦 m 個初始值 zk，l(k=1，2，…，m;l=0)，以此得出m個混沌向量.

初始值不可以是:0，0.25，0.5，0.75，1.

(2)將［0，1］作m 等分，并對分區(qū)間編號:1－m.

(3)運用冪函數(shù)載波理論，按照z'l=zvl把混沌變量zl載波成新混沌變量z'l

v是分段常函數(shù):

若沒有達到條件，則依據(jù)式(2)繼續(xù)迭代生成m個混沌向量，令l=l+1，重新執(zhí)行第3步.

3.5 選擇操作及適應度函數(shù)建立

選擇操作是對生物進化論的“適者生存”思想的體現(xiàn)，越優(yōu)良的個體具有越大的概率進入下一代，種群性能就會隨著進化而不斷優(yōu)化.采用輪盤賭法(Roulette Wheel Selection)，保證將種群中最優(yōu)個體隨機替換掉下一代的個體，這對于不斷尋優(yōu)具有關鍵作用.

適應度函數(shù)是評價個體優(yōu)劣的指標，由于本文研究的路徑問題是最小化路徑長度，因此，適應度函數(shù)取線性定標，如式(3)所示.

式中 α為預先設定的常數(shù);N為城市的數(shù)目;M為包含所有城市的最小正方形的邊長;Td就是根據(jù)式(1)計算得出的實際路徑長度，也就是目標和數(shù)值.

如果按TGA求解該問題，勢必會產(chǎn)生大量非可行解，耗費更多計算程序運行時間與硬件資源，降低了求解效率.擬作如下特殊處理:

記dmax=，按照非連通圖約束，設城市cp，cq之間存在障礙物，無法直接到達，則對兩者之間的距離進行特殊處理，令d(cp，cq)=N·dmax+1.

解決這一問題，通過對非連通城市間距離的特殊處理，就能保證GA的優(yōu)良特性不會受到影響，而且可以更容易地找到該問題的可行解.如上文所述，城市cp，cq之間存在障礙物，假設個體S包含基因片段(…，cp，cq，…)或者(…，cq，cp，…)，則有式(4)成立:

因此，在作出了特殊處理后，若個體S中存在非連通城市相鄰，則必會出現(xiàn)其適應度值小于，按照GA的選擇操作中“適者生存”思想，這些適應度值很小的非可行解必然會隨著進化的歷程而逐漸被淘汰，因此就排除了非連通城市相鄰的情況.反之，若有式(5)成立，則個體S必定為可行解，用反證法可證出，此處從略.

3.6 算法步驟

步驟1 初始化.設置預定常數(shù)、最大迭代次數(shù)、交叉概率Pc、變異概率Pm等參數(shù).

步驟2 采用遍歷城市排序的編碼方法，利用隨機選取與貪心法相結合的方式來生產(chǎn)初始種群.

While(迭代次數(shù)≤最大迭代次數(shù))do

步驟3 按Pc概率執(zhí)行交叉操作，按Pm概率執(zhí)行變異操作，再執(zhí)行局部鄰域搜索以及混沌搜索.

步驟4 根據(jù)f(S)，基于輪盤賭法執(zhí)行選擇操作，確定子代個體，保證優(yōu)良染色體能夠保留下來.

步驟5 求得最大適應度值的個體作為最終解.

步驟6 檢驗該解的適應度值是否滿足式(5)，如果滿足，則可行，否則該解為非可行解.

End While

4 算法檢驗與分析

使用Matlab R2009a分別對文中CGA和TGA進行編程，在2.53GHz CPU，2.0GB內存的PC上運行，選取我國31個中心城市的地理數(shù)據(jù)用于算法檢驗［18］.設 Pc=0.2，Pm=0.5，MaxItr=1000，結果見表1.可見，兩種算法的快速尋優(yōu)能力都較強，運行時間不超過2 min.但是，在求解方面，CGA的最滿意值為14268 km(如圖2所示)，明顯優(yōu)于TGA的15387 km(如圖3所示)，改進程度為7.3%，說明CGA取得了相比TGA更優(yōu)的解，達到了算法改進的目的.究其原因，主要是由于TGA在初始種群生成方面產(chǎn)生了大量不可行解和在交叉變異過程中缺失局部鄰域擇優(yōu)能力.也就是說，正是由于CGA引入局部鄰域搜索以及混沌搜索操作，所以確保了子代個體快速持續(xù)收斂.

表1 兩種算法的檢驗結果Table.1 Check results of TGA and CGA

圖2 CGA的最滿意值Fig.2 The most satisfactory solution of CGA

對比兩種算法的極差發(fā)現(xiàn)，CGA的種群離散程度較小，集聚性較高，收斂性更好.這源于:其一，CGA的初始種群質量優(yōu)于TGA，其可行染色體比例較高，避免了初期大量不滿意染色體的生成;其二，CGA的局部搜索及混沌搜索操作提高了子代個體的收斂性.總之，CGA的求解能力更強，比TGA更高效.

5 研究結論

本研究將GA應用于非連通圖公路運輸路徑問題，更逼真地模擬了現(xiàn)實中各種復雜因素，研究價值較高.首先，利用隨機選取與貪心法相結合的方式來產(chǎn)生初始種群，確保了初始種群滿足非連通圖約束，克服了TGA在隨機方式下生成大量非可行解的缺陷.接著執(zhí)行交叉變異操作、局部鄰域搜索及混沌搜索操作，以確保優(yōu)良基因，加速染色體收斂.最后，給出了經(jīng)特殊處理的適值函數(shù)、經(jīng)典的選擇方法以及解的可行性判據(jù).今后的研究可以著眼于求出的解為非可行解條件下初始種群的再調整，同時設計在更短時間內收斂的CGA.

［1］梁艷春，吳春國，時小虎，等.群智能優(yōu)化算法理論與應用［M］.北京:科學出版社，2009.［LIANG Y C，WU C G，SHI X H，et al.Group intelligent optimization algorithm theory and application［M］.Beijing:Science press，2009.］

［2］ZHAO X C，Gao X S.Affinity genetic algorithm［J］.Journal of Heuristics，2007，13(2):133-150.

［3］YANG J H，Wu C G，Lee H P et al.Solving traveling salesman problems using generalized chromosome genetic algorithm［J］.Progress in Natural Science，2008，18(7):887-892.

［4］Bhatia A K，Basu S K.Tackling 0/1 knapsack problem with gene induction［J］.Soft Computing，2003，8(1):1-9.

［5］黃永青，梁昌勇，張祥德，等.一種小種群自適應遺傳算法研究［J］.系統(tǒng)工程理論與實踐，2005，25(11):92-97.［HUANG Y Q，LIANG C Y，ZHANG X D，et al.Research on adaptive genetic algorithm with small population［J］.Systems Engineering-Theory＆ Practice，2005，25(11):92-97.］

［6］陶林波，沈建京，韓強.一種解決早熟收斂的自適應遺傳算法設計［J］.微計算機信息，2005，22(12):268-270.［TAO L B，SHEN J J，HAN Q.An algorithm design for solving premature convergence of adaptive genetic algorithm ［J］. Microcomputer Information，2005，22(12):268-270.］

［7］李鋒，魏瑩.基于仿真的遺傳算法求解動態(tài)旅行商問題［J］.系統(tǒng)管理學報，2009，18(5):591-595.［LI F，WEI Y.A simulation-based genetic algorithm for dynamic traveling salesman problem ［J］.Journal of Systems ＆ Management，2009，18(5):591-595.］

［8］周輝仁，唐萬生，牛犇.基于遞階遺傳算法的多旅行商問題優(yōu)化［J］.計算機應用研究，2009，26(10):3754-3757.［ZHOU H R，TANG W S，NIU B.Optimization of multiple traveling salesman problem based on hierarchical genetic algorithm ［J］.Application Research of Computers，2009，26(10):3754-3757.］

［9］王美華，田緒紅，廖鴻翔.求解廣義旅行商問題的混合染色體遺傳算法［J］.計算機工程與應用，2009，45(27):59-61.［WANG M H，TIAN X H，LIAO H X.Mixed chromosomes genetic algorithm for solving the generalized traveling salesman problem ［J］.Computer Engineering and Applications，2009，45(27):59-61.］

［10］韓麗霞，王宇平.解旅行商問題的一個新的遺傳算法［J］.系統(tǒng)工程理論與實踐，2007，(12):145-150.［HAN L X，WANG Y P.A novel genetic algorithm for traveling salesman problem ［J］. Systems Engineering-Theory ＆ Practice， 2007，(12):145-150.］

［11］朱云飛，蔡自興，袁琦釗，等.求解多目標旅行商問題的混合遺傳算法［J］.計算機工程與應用，2011，47(7):52-56.［ZHU Y F，CAI Z X，YUAN Q Z，et al.Hybrid genetic algorithm for multiple-objective TSP［J］.Computer Engineering and Applications，2011，47(7):52-56.］

［12］汪民樂，高曉光，劉剛.遺傳算法早熟問題的定量分析及其預防策略［J］.系統(tǒng)工程與電子技術，2006，28(8):1249-1251.［WANG M L，GAO X G，LIU G.Quantitative analysis and prevention of genetic algorithm premature convergence［J］. Systems Engineering and Electronics， 2006， 28(8):1249-1251.］

［13］ 郟宣耀，王芳.一種改進的小生境遺傳算法［J］.重慶郵電學院學報(自然科學版)，2005，17(16):721-723.［JIA X Y，WANG F.Improved niching genetic algorithm［J］.Journal of Chongqing University of Posts and Telecommunications(Natural Science)，2005，17(16):721-723.］

［14］賀毅朝，劉坤起，張翠軍，等.求解背包問題的貪心遺傳算法及其應用［J］.計算機工程與設計，2007，28(11):2655-2657［HE Y C，LIU K Q，ZHANG C J，et al.Greedy genetic algorithm for solving knapsack problems and its applications［J］. Computer Engineering and Design， 2007， 28 (11):2655-2657.］

［15］田建立，晁學鵬.求解0-1背包問題的混沌遺傳算法［J］.計算機應用研究，2011，28(8):2838 －2839.［TIAN J L， CHAO X P. Novel chaos genetic algorithm for solving 0-1 knapsack problem ［J］.Application Research of Computers，2011，28(8):2838-2839.］

［16］Bievwirth C，Mattfeld D，Kopfer H.On permutation representations for scheduling problems［C］//Proceedings of the 4th International Conference on Parallel Problem Solving from Nature. Berlin，Germany:Springer，1996:310-318.

［17］Murata T，Ishibuchi H，Tanaka H.Genetic algorithms for flowshop scheduling problem［J］.Computers＆Industrial Engineering，1996，30(4):1061-1071.

［18］ 康立山，謝云，尤矢勇，等.模擬退火算法［M］.北京:科學出版社，1994:150-151.［KANG L S，XIE Y，YOU S Y et al.Simulated Annealing Algorithm［M］.Beijing:Science Press，1994:150-151.］