完全圖哈密爾頓圈遺傳算法的MATLAB模擬實(shí)現(xiàn)

劉奕君, 張 立2, 趙 強(qiáng)

(1.徐州醫(yī)學(xué)院醫(yī)學(xué)信息學(xué)院，江蘇 徐州 221000；2.徐州醫(yī)學(xué)院醫(yī)學(xué)影像學(xué)院，江蘇 徐州 221000)

· 計(jì)算機(jī)軟件理論、技術(shù)與應(yīng)用·

完全圖哈密爾頓圈遺傳算法的MATLAB模擬實(shí)現(xiàn)

劉奕君1, 張 立2, 趙 強(qiáng)1

(1.徐州醫(yī)學(xué)院醫(yī)學(xué)信息學(xué)院，江蘇 徐州 221000；2.徐州醫(yī)學(xué)院醫(yī)學(xué)影像學(xué)院，江蘇 徐州 221000)

求解完全圖上的哈密爾頓圈是典型的組合優(yōu)化問題，遺傳算法是解決此類NP問題的一種較理想的方法。對(duì)基本的遺傳算法進(jìn)行改進(jìn)，在選擇操作和變異操作中加入貪心優(yōu)化思想，使算法獲得更優(yōu)的全局最優(yōu)解。在MATLAB環(huán)境下模擬實(shí)現(xiàn)了哈密爾頓圈的經(jīng)典問題——TSP( travelling salesman problem)旅行商問題，從而驗(yàn)證了該算法的可行性和正確性。

哈密爾頓圈；遺傳算法；貪心思想；MATLAB；全局最優(yōu)解

設(shè)G(V，E)是一個(gè)連通圖，若G中一條回路通過G的每個(gè)點(diǎn)恰好1次，這樣的回路稱為哈密爾頓回路，記作H回路。對(duì)于H回路問題，傳統(tǒng)的窮舉搜索法、貪心法、動(dòng)態(tài)規(guī)劃法等串行算法，都面臨著所謂“組合爆炸”問題[1]。對(duì)于這類NP(non-deterministic polynomial)問題，可用并行求解法或演化算法等。演化算法[2-3]是用計(jì)算機(jī)模擬大自然的演化過程，特別是生物進(jìn)化過程，以求解復(fù)雜問題的一類計(jì)算模型，其基本思想是Darwin的進(jìn)化論和Mendel的遺傳學(xué)說。該類算法可通過逐步的演化過程，使群體進(jìn)化到包含或接近最優(yōu)解的狀態(tài)。遺傳算法即典型的演化算法[4]，提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，不依賴于問題的具體領(lǐng)域，對(duì)問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科[5-8]。

TSP(travelling salesman problem)問題的數(shù)學(xué)模型便是帶權(quán)的H回路問題，即對(duì)n個(gè)城市,要找一條走遍每個(gè)城市一次且僅一次的最短閉合路徑。其實(shí)際模型在路徑、網(wǎng)絡(luò)、分配等優(yōu)化問題中有著廣泛的應(yīng)用。用于求解 TSP 的現(xiàn)代優(yōu)化算法主要包括模擬退火算法、人工免疫算法、蟻群算法、禁忌搜索算法、 神經(jīng)網(wǎng)絡(luò)算法等[9]。它們存在著全局搜索能力差的弱點(diǎn)，極有可能找到的是局部最優(yōu)解[10]。本文采用的遺傳算法，具有較好的全局搜索性能，是目前解決TSP問題的較為有效的方法。

1 針對(duì)哈密爾頓圈問題的遺傳算法設(shè)計(jì)

1.1 算法分析與設(shè)計(jì)

遺傳算法的基本流程如圖1所示，包括3個(gè)基本操作：選擇、交叉和變異。選擇(selection)是用來確定重組或交叉?zhèn)€體，以及被選個(gè)體將產(chǎn)生多少個(gè)子代個(gè)體。首先計(jì)算適應(yīng)度，然后按照適應(yīng)度進(jìn)行父代個(gè)體的選擇。基因重組是結(jié)合來自父代交配種群的信息產(chǎn)生新的個(gè)體。交叉之后子代經(jīng)歷的變異，實(shí)際上是子代基因按小概率擾動(dòng)產(chǎn)生的變化。

圖1 遺傳算法的基本流程

遺傳算法的染色體編碼方案，通常有二進(jìn)制編碼和浮點(diǎn)數(shù)編碼2種，而對(duì)于求哈密爾頓圈的問題，浮點(diǎn)數(shù)編碼更適合。例如，染色體(1，2，3，4，5)即表示該哈密爾頓圈由1點(diǎn)出發(fā)，經(jīng)過點(diǎn)2-5又回到1點(diǎn)。回路長(zhǎng)度是度量某個(gè)染色體的優(yōu)良性的標(biāo)準(zhǔn)，長(zhǎng)度越小，說明染色體越優(yōu)秀，應(yīng)該保留，這也是本算法中適用度函數(shù)的考量點(diǎn)。

在初步實(shí)現(xiàn)時(shí)，發(fā)現(xiàn)基本的輪轉(zhuǎn)法和變異算法在獲得全局最優(yōu)解時(shí)，性能較差，很難在隨機(jī)的自然選擇中得到和保留最優(yōu)的種群基因，故本文將貪心的思想加入這2個(gè)步驟中。這種貪心思想是最優(yōu)保存方法的體現(xiàn)。遺傳算法的理論已經(jīng)證明了輪轉(zhuǎn)法選擇算子不能收斂到全局最優(yōu)解，而最優(yōu)保存方法[11]能收斂到全局最優(yōu)解。在選擇種群時(shí)，每次用最好的種群基因?qū)⒆畈畹囊徊糠只蛱鎿Q掉，再用輪轉(zhuǎn)法選擇，在變異時(shí)，將變異概率增大，使得上一次的優(yōu)秀基因有更多的變異機(jī)會(huì)，這樣可以在一定程度上解決因貪心選擇造成的種群多樣性減少的問題。同時(shí)，在變異時(shí)，同樣加入貪心的思想，只有當(dāng)變異后的基因優(yōu)于原基因時(shí)，才使此次變異成功，否則失敗。這樣又能使整體算法的收斂速度加快，也更易獲得全局最優(yōu)解。在交叉操作中，選擇文獻(xiàn)[10]的順序交叉操作方法，因?yàn)檫@種交叉方法更適合于哈密爾頓圈的特性。

1.2 算法描述

步驟1 編碼初始化。設(shè)置最大進(jìn)化代數(shù)MaxG，種群規(guī)模N，貪心替換算子Pr，變異算子Pm和交叉算子Pc，并生成初始隨機(jī)種群。

步驟2 個(gè)體評(píng)價(jià)。用適應(yīng)度函數(shù)對(duì)每個(gè)基因進(jìn)行評(píng)價(jià)。

步驟3 選擇操作。首先用最優(yōu)的染色體方案替換占種群規(guī)模Pr的最壞個(gè)體，再用基本輪轉(zhuǎn)法進(jìn)行選擇。

步驟4 交叉操作。采用順序交叉操作方法。

步驟5 變異操作。只有當(dāng)變異后的基因優(yōu)于原基因時(shí)，變異成功。

步驟6 終止條件。當(dāng)進(jìn)化代數(shù)大于MaxG時(shí)，算法結(jié)束，否則轉(zhuǎn)向步驟2。

2 MATLAB編碼實(shí)現(xiàn)

本文的MATLAB仿真并沒有采用已有的遺傳算法工具包，而是根據(jù)設(shè)計(jì)的算法進(jìn)行了重新編寫，特別是選擇和變異操作。選擇操作中的貪心思想代碼如圖2所示，變異操作中的貪心思想代碼如圖3所示。

圖2 選擇操作中的貪心思想代碼

圖3 變異操作中的貪心思想代碼

3 算法驗(yàn)證與試驗(yàn)分析

3.1 算法驗(yàn)證

本文采用經(jīng)典的Oliver 30城市問題[12]進(jìn)行算法驗(yàn)證。當(dāng)最大進(jìn)化代數(shù)MaxG取400，種群規(guī)模N取600，貪心替換算子Pr取0.25，變異算子Pm取0.12和交叉算子Pc取0.3時(shí)，經(jīng)過數(shù)次運(yùn)行，得到的最優(yōu)路徑，如圖4所示。比傳統(tǒng)的二叉樹描述法的結(jié)果428.90和啟發(fā)式搜索法的結(jié)果436.01[13]都有更高的性能，且速度更快。圖5示出某次運(yùn)行得到的最優(yōu)解隨進(jìn)化代數(shù)的趨勢(shì)。

圖6示出的是再隨機(jī)生成200個(gè)城市的坐標(biāo)(X，Y坐標(biāo)的范圍在[0,800])，經(jīng)過數(shù)次運(yùn)行后，得到的最優(yōu)解。

圖4 30城市問題求解的最優(yōu)路徑

圖5 30城市問題求解的最優(yōu)解隨進(jìn)化代數(shù)的趨勢(shì)圖

圖6 隨機(jī)產(chǎn)生的200城市問題求得的最優(yōu)路徑

3.2 實(shí)驗(yàn)分析

從圖4和圖6可以看到，求得的路徑均沒有產(chǎn)生交叉的線路，表明該算法求解是有效的。另外，從圖5可以看到，當(dāng)進(jìn)化到第1個(gè)做標(biāo)記的代數(shù)時(shí)，算法開始趨于收斂，同時(shí)又存在很小的波動(dòng)，且這些波動(dòng)是趨向于更好的染色體形態(tài)，這是在變異時(shí)加入了貪心思想的原因。圖5的收斂種群代數(shù)約為200代，較文獻(xiàn)[12]的收斂速度慢，這是因?yàn)樵谶x擇操作時(shí)的貪心替換，使得種群的多樣性下降，有更多的進(jìn)化代數(shù)便是這種選擇要付出的代價(jià)；因此，在交叉和變異算子的選擇時(shí)，應(yīng)適當(dāng)增大相應(yīng)的取值，以增加種群的個(gè)體多樣性，從而獲得全局最優(yōu)解。

4 結(jié)束語

本文對(duì)基本的遺傳算法進(jìn)行了改進(jìn)，在進(jìn)行選擇操作時(shí)，將最優(yōu)值替換和輪轉(zhuǎn)法相結(jié)合，使算法更容易獲得全局最優(yōu)解，同時(shí)，在變異操作中采用取優(yōu)值的貪心方法，以獲得更優(yōu)秀的變異個(gè)體。本文的后繼工作主要考慮：如何使算法整體的收斂速度得到提升；在交叉操作時(shí)，如何提升貪心的效率。

[1]方俊,潘勇.哈密頓回路問題的DNA表面計(jì)算模型[J].計(jì)算機(jī)工程與應(yīng)用，2006，42(30):62-64.

[2]李悅喬,康立山,李程俊.求解TSP問題的實(shí)數(shù)編碼演化算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2007(19):14-16.

[3]蔡之華,彭錦國,高偉，等.一種改進(jìn)的求解TSP問題的演化算法[J].計(jì)算機(jī)學(xué)報(bào),2005(5):74-79.

[4]劉勇，劉寶坤，李光泉.基于MATLAB平臺(tái)的遺傳算法工具包[J].天津大學(xué)學(xué)報(bào)：自然科學(xué)版,，2001(4):490-494.

[5]Mat Buckland.游戲中的人工智能技術(shù)[M]. 吳祖增，沙鷹，譯.北京：清華大學(xué)出版社， 2006：723-764.

[6]王小平，曹立明.遺傳算法：理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安：西安交通大學(xué)出版社，2002:300-400.

[7]張文修，梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)[M]. 西安：西安交通大學(xué)出版社， 2000：500-560.

[8]周明，孫樹棟.遺傳算法原理及應(yīng)用[M]. 北京：國防工業(yè)出版社， 1999：120-200.

[9]周康,強(qiáng)小利,同小軍，等.求解TSP算法[J].計(jì)算機(jī)工程與應(yīng)用,2007, 43(29):43-47.

[10]高友智.基本遺傳算法及其改進(jìn)[J].武漢化工學(xué)院學(xué)報(bào)，2003(2):77-78.

[11]謝勝利，張燕姑，李廣.基于遺傳算法的旅游商問題求解[J].溫州師范學(xué)院學(xué)報(bào)：自然科學(xué)版，2002，22(3)7-10.

[12]曲中水，劉淑蘭.基本遺傳算法的收斂性分析方法[J].哈爾濱理工大學(xué)學(xué)報(bào)，2003(1):45-48.

[13]劉振,胡云安.一種多粒度模式蟻群算法及其在路徑規(guī)劃中的應(yīng)用[J].中南大學(xué)學(xué)報(bào)：自然科學(xué)版,2013(9):150-159.

(編校：饒莉)

TheSimulationofGeneticAlgorithmforHamiltonCircleonCompleteGraphinMATLABEnvironment

LIU Yi-jun1, ZHANG Li2, ZHAO Qiang1

(1.SchoolofMedicineInformation，XuzhouMedicalCollege，Xuzhou221000China;2.SchoolofMedicalImaging，XuzhouMedicalCollege，Xuzhou221000China)

Solving Hamilton-circle on a complete graph is a typical combinatorial optimization problem. Genetic algorithm is a good way to solve such an NP problem. In this paper, the basic genetic algorithm is improved. Particularly, the greedy optimization ideas are applied to the selection and mutation operation in order to obtain global optimal solutions with the algorithm. In the MATLAB environment, the algorithm was simulated to implement classical Hamilton circle- TSP (travelling salesman problem) and the results verify the feasibility and correctness of the algorithm.

Hamilton-circle; genetic algorithm; greedy thoughts; MATLAB; global optimal solutions

2014-03-13

徐州市科技計(jì)劃項(xiàng)目(XM13B021)；徐州市科技計(jì)劃項(xiàng)目(XM12B077)。

劉奕君(1983—)，女，講師，主要研究方向?yàn)橛?jì)算機(jī)軟件設(shè)計(jì)、信號(hào)處理。

TP311; TP312

：A

：1673-159X(2015)04-0013-04

10.3969/j.issn.1673-159X.2015.04.003