一種基于二次變異策略的改進(jìn)型遺傳算法

馬福祥，馬秀娟

青海師范大學(xué)計(jì)算機(jī)學(xué)院，西寧810008

1 引言

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

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

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

2 TSP問(wèn)題描述及改進(jìn)遺傳算法

2.1 TSP問(wèn)題描述

旅行商問(wèn)題（TSP）是一個(gè)具有廣泛應(yīng)用價(jià)值和重要理論意義的典型組合優(yōu)化問(wèn)題?？梢院?jiǎn)單描述為：給定n個(gè)相互聯(lián)系的城市，有一個(gè)旅行商從某一個(gè)城市出發(fā)，訪問(wèn)各城市一次且僅一次再回到原出發(fā)城市，要求找出一條最短的巡回路徑。

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

2.2 改進(jìn)遺傳算法及其解決TSP問(wèn)題的基本思想及操作步驟

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

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

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

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

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

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

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

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

（6）對(duì)第一次變異后得到的種群中的每個(gè)個(gè)體進(jìn)行二次變異，得到新的種群個(gè)體；

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

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

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

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

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

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

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

圖1 30個(gè)城市的最短路徑

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

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

表1 改進(jìn)遺傳算法仿真實(shí)驗(yàn)各參數(shù)及取值表

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

圖2 二次變異與非二次變異適應(yīng)度值曲線圖

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

表2 兩種算法下的適應(yīng)度值比較

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

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

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

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

4 結(jié)語(yǔ)

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

[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)度問(wèn)題的一種新編碼方法[J].計(jì)算機(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)，郝國(guó)生，嚴(yán)玉若.交互式遺傳算法基于用戶認(rèn)知不確定性的定向變異[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ù)設(shè)定研究[J].系統(tǒng)工程與電子技術(shù)，2007，29（10）：1753-1756.

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

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

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

[14]孟偉，韓學(xué)東，洪炳镕.蜜蜂進(jìn)化型遺傳算法[J].電子學(xué)報(bào)，2006，34（7）：1294-1300.

[15]魯宇明，黎明，李凌.一種具有演化規(guī)則的元胞遺傳算法[J].電子學(xué)報(bào)，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.