馬福祥，馬秀娟

青海師范大學計算機學院，西寧810008

1 引言

遺傳算法是模擬生物在自然環(huán)境下的遺傳和進化過程而形成的一種自適應全局優(yōu)化概率搜索方法。它最早由美國密西根大學的Holland教授提出[1]，起源于20世紀60年代對自然和人工自適應系統(tǒng)的研究。

目前，研究人員從染色體的編碼方式[2-4]、遺傳算子的選擇[5-9]、遺傳算法中相關(guān)參數(shù)的設定[10-11]，以及算法的收斂性[12-13]等方面對遺傳算法進行了相關(guān)的研究，并得到了一些重要的結(jié)論。隨著應用領域的不斷擴大和實際工程問題的復雜化，遺傳算法逐漸顯現(xiàn)出一些不足和缺點，針對這些問題，一些改進的算法相繼被提出[14-17]。改進的算法主要從物種多樣性、個體適應度評價函數(shù)和遺傳算子參數(shù)確定等方面進行了研究。研究結(jié)果表明，改進后的算法在個體多樣性的保持，算法搜索能力的提高，全局收斂性的改善等方面取得了較好的效果。

以往的研究表明，為了保證遺傳算法的全局收斂性，就要保持種群的多樣性，避免有效基因的丟失。另一方面，為了加快算法的收斂速度，就要使群體較快地向最優(yōu)狀態(tài)轉(zhuǎn)移，這又會減少群體的多樣性，容易陷入局部最優(yōu)點。本文在基本遺傳算法的基礎上，采用了單點位變異和倒置變異兩次變異操作。通過仿真實驗把改進后的算法應用到TSP問題的求解中，實驗結(jié)果表明，二次變異策略能較好地保證群體的多樣性，同時算法也能較快收斂到最優(yōu)狀態(tài)，算法的搜索能力得到了提高，搜索到了更優(yōu)的適應度值。另外，相同條件下當增大種群規(guī)模時，二次變異后的算法得到的解比基本遺傳算法更優(yōu)。

2 TSP問題描述及改進遺傳算法

2.1 TSP問題描述

旅行商問題（TSP）是一個具有廣泛應用價值和重要理論意義的典型組合優(yōu)化問題?？梢院唵蚊枋鰹椋航o定n個相互聯(lián)系的城市，有一個旅行商從某一個城市出發(fā)，訪問各城市一次且僅一次再回到原出發(fā)城市，要求找出一條最短的巡回路徑。

該問題的數(shù)學描述為：設集合C={c1，c2，…，cn}是n個城市的集合，其中每對城市之間的距離d(ci，cj)∈R+，求一條經(jīng)過C中每個城市一次且僅一次的路線(cπ1，cπ2，…，cπn)，使得下列目標函數(shù)最?。?/p>

2.2 改進遺傳算法及其解決TSP問題的基本思想及操作步驟

本文通過改進基本遺傳算法中的變異策略，增加了變異次數(shù)，采用了單點位變異和倒置變異兩種變異策略來提高算法效率，使得算法在解決TSP問題時搜索到的解比傳統(tǒng)的一次變異更優(yōu)。

改進后的算法解決TSP問題的基本思想為：在隨機生成的M個城市的N條巡回路徑中（N個種群）進行全局搜索，搜索時采用交叉和變異策略。在應用變異策略是，將傳統(tǒng)的單次變異策略改進為二次變異，即在單次變異策略的基礎上對得到的種群進行二次變異，再對得到的新種群通過個體適應度函數(shù)計算比較每個新種群的個體適應度值，最終得到TSP問題的近似最優(yōu)解。

根據(jù)改進后的遺傳算法得到了該算法解決TSP問題的操作步驟，具體如下所述：

（1）隨機生成M個城市的N條路徑構(gòu)成的初始種群p(N)，并進入循環(huán)；

（2）對初始種群中p(N)中的個體進行兩兩交叉操作，形成新的種群個體；

（3）對交叉操作后形成的新個體計算其適應度值，并與交叉前的舊個體進行比較，保留適應度值較優(yōu)的個體；

（4）對交叉操作結(jié)束后種群中的每個個體進行第一次變異，得到新的種群個體；

（5）對變異后的個體計算適應度并與第（3）步得到的結(jié)果進行比較，選出局部最優(yōu)的種群個體；

（6）對第一次變異后得到的種群中的每個個體進行二次變異，得到新的種群個體；

（7）對倒置變異后的種群個體計算適應度值，并與第（6）步中得到的個體適應度值進行比較，得到局部最優(yōu)值；

（8）記錄上一代的最優(yōu)值，并進入下一代循環(huán)執(zhí)行第2到第7步；

（9）迭代次數(shù)超過最大迭代數(shù)，循環(huán)終止，輸出全局最優(yōu)值。

3 改進遺傳算法的仿真實現(xiàn)及數(shù)據(jù)分析

3.1 改進遺傳算法的仿真實現(xiàn)

通過用M atlab編寫仿真實驗程序?qū)ι鲜鏊惴ㄟM行了仿真實驗，實驗結(jié)果表明：改進后的遺傳算法在解決TSP問題時能更有效地保持個體的多樣性，并有效提高算法的局部搜索能力，得到了比單次變異更優(yōu)的解。

遺傳算法中種群個體的編碼方式、交叉和變異策略的設計對最終的結(jié)果有直接的影響。本文的仿真實驗在種群個體的編碼方式上采取了常用的“路徑編碼串”的編碼方式，即直接采用城市在路徑中的位置進行表示，這種編碼方式能更簡單直觀地表示種群個體和路徑之間的關(guān)系。根據(jù)TSP問題是求解經(jīng)過每個城市一次且僅一次的最短閉合路徑的特點，本文使用了啟發(fā)式交叉策略。即隨機選擇兩條路徑串，并隨機確定兩個串的交叉區(qū)域段，交換刪除兩個串中在交叉區(qū)域出現(xiàn)的城市，然后將剩下的城市與交叉區(qū)域中的城市組成一個新串。變異操作是算法產(chǎn)生新個體的輔助方法，決定了遺傳算法的局部搜索能力，保持了種群的多樣性。本文為了提高遺傳算法中種群的多樣性，提高算法的搜索能力找到更優(yōu)的解，在算法的變異策略上采用了二次變異策略，即采用單點位變異和倒置變異兩種變異策略。單點位變異是指隨機選擇一個串，確定兩個交叉變異點，交換兩點上的城市編號得到新的路徑串；倒置變異是指隨機確定路徑中的倒置變異區(qū)域，然后將該區(qū)域中的城市編號進行倒置得到新的路徑串。通過仿真實驗，可以得到如圖1所示的最短路徑。

圖1 30個城市的最短路徑

3.2 改進遺傳算法的仿真實驗數(shù)據(jù)分析

為驗證本文提出的改進遺傳算法的有效性，設計仿真實驗程序進行了驗證。實驗中的適應度函數(shù)如上述TSP問題描述中的公式（1）所示，相關(guān)參數(shù)的設置及取值由表1給出。

表1 改進遺傳算法仿真實驗各參數(shù)及取值表

為了保證實驗的有效性，本文給出了30次實驗的結(jié)果。圖2給出了相同的種群規(guī)模和迭代次數(shù)下，二次變異的改進遺傳算法與非二次變異的基本遺傳算法的實驗結(jié)果。

圖2 二次變異與非二次變異適應度值曲線圖

從圖2中的曲線可以看出二次變異策略的改進算法能得到的適應度值更優(yōu)。表2給出了適應度值在兩種算法下，30次實驗結(jié)果的最大值、最小值以及平均值。表2的結(jié)果表明，二次變異的改進算法找到的適應度值總是比非二次變異的基本遺傳算法更優(yōu)。

表2 兩種算法下的適應度值比較

另外，在二次變異的改進遺傳算法中，只要增大種群規(guī)模，改進的遺傳算法比基本遺傳算法能找到更優(yōu)的適應度值。圖3給出了種群規(guī)模對二次變異算法的適應度值的影響；表3給出了不同種群規(guī)模下改進算法的適應度值。

圖3 相同迭代次數(shù)下種群規(guī)模對改進算法適應度值的影響

表3 不同種群規(guī)模下改進算法的適應度值

圖3中的數(shù)據(jù)表明，二次變異的改進遺傳算法對種群規(guī)模有很強的敏感性，當增大種群規(guī)模時，算法能找到更優(yōu)的適應度值。表3中的數(shù)據(jù)表明，雖然基本遺傳算法也對種群規(guī)模有一定的敏感性，但相同條件下二次變異的改進算法對種群規(guī)模的敏感性更強。仿真實驗比較了30次實驗找到的所有適應度值，并給出了不同種群規(guī)模下適應度的最小值、最大值和平均值。通過比較，進一步驗證了在遺傳算法中采用二次變異的策略有利于提高算法的搜索能力。

4 結(jié)語

通過在基本遺傳算法中增加二次變異策略來改進算法，仿真結(jié)果表明，二次變異的改進遺傳算法找的適應度值比基本遺傳算法更優(yōu)；另外，二次變異的改進算法對種群規(guī)模有更好的敏感性。改進后的算法更好地保持了種群的多樣性，在提高算法的搜索能力上也有更好的效果。本文算法除了應用在TSP問題中外，還可以應用到復雜網(wǎng)絡求解最短路徑和平均路徑長度等問題中，有一定的可擴展性。

[1]Holland J H.Adaptation in natural and artificial systems：an introductory analysis with applications to biology，control，and artificial intelligence[M].2nd ed.Cambridge：M IT Press，1992.

[2]Yang Xiaohua，Yang Zhifeng，Yin Xinan，et al.Chaos graycoded genetic algorithm and its application for pollution source identifications in convection-diffusion equation[J].Communications in Nonlinear Science and Numerical Simulation，2008，13（8）：1676-1688.

[3]梁旭，王佳，黃明.解決大規(guī)模生產(chǎn)調(diào)度問題的一種新編碼方法[J].計算機集成制造系統(tǒng)，2008，14（10）：1974-1982.

[4]He Yaohua，Hui Chiwai.A binary coding genetic algorithm for multi-purpose process scheduling：a case study[J].Chemical Engineering Science，2010，65（16）：4816-4828.

[5]Tang Kezong，Sun Tingkai，Yang Jingyu.An improved genetic algorithm based on a novel selection strategy for nonlinear programming problems[J].Computers and Chemical Engineering，2011，35（4）：615-621．

[6]Boris P L，Jessica S C.A determ inistic annular crossover genetic algorithm optimisation for the unit commitment problem[J].Expert System s with Applications，2011，38（6）：6523-6529．

[7]Wang Lei，Tang Dunbing.An improved adaptive genetic algorithm based on hormone modulation mechanism for Job-Shop scheduling problem[J].Expert Systems with Applications，2011，38（6）：7243-7250．

[8]鞏敦衛(wèi)，郝國生，嚴玉若.交互式遺傳算法基于用戶認知不確定性的定向變異[J].控制與決策，2010，25（1）：74-78．

[9]Murat A，Novruz A.Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithm s[J].Expert Systems with Applications，2011，38（3）：1313-1320.

[10]閆利軍，李宗斌，楊曉春.基于混合優(yōu)化算法的遺傳算法參數(shù)設定研究[J].系統(tǒng)工程與電子技術(shù)，2007，29（10）：1753-1756.

[11]李慧賢，龐遼軍，蔡皖東.基于信息熵對遺傳算法中雜交概率的研究[J].系統(tǒng)工程與電子技術(shù)，2009，31（7）：1743-1745.

[12]喻壽益，鄺溯瓊.保留精英遺傳算法收斂性和收斂速度的鞅方法分析[J].控制理論與應用，2010，27（7）：843-848.

[13]馬永杰，馬義德，蔣兆遠，等.一種快速遺傳算法及其收斂性[J].系統(tǒng)工程與電子技術(shù)，2009，31（3）：714-718.

[14]孟偉，韓學東，洪炳镕.蜜蜂進化型遺傳算法[J].電子學報，2006，34（7）：1294-1300.

[15]魯宇明，黎明，李凌.一種具有演化規(guī)則的元胞遺傳算法[J].電子學報，2010，38（7）：1603-1607.

[16]Zhang Jinhua，Zhuang Jian，Du Haifeng，et al.Self-organizing genetic algorithm based tuning of PID controllers[J].Information Sciences，2009，179（7）：1007-1018.

[17]Li Fachao，Xu Lida，Jin Chenxia，et al.Intelligent Bionic Genetic A lgorithm（IB-GA）and its convergence[J].Expert Systems with Applications，2011，38（7）：8804-8811.