基于個體相似性評價策略的改進遺傳算法

湯可宗　張　彤　羅立民

1(東南大學計算機科學與工程學院　江蘇 南京 210094)2(景德鎮陶瓷學院信息工程學院　江西 景德鎮 333403)

?

基于個體相似性評價策略的改進遺傳算法

湯可宗1張彤2羅立民1

1(東南大學計算機科學與工程學院江蘇 南京 210094)2(景德鎮陶瓷學院信息工程學院江西 景德鎮 333403)

遺傳算法是一種通過模擬自然進化過程搜索最優解的方法。但這種算法在求解最優解過程中總是以計算時間為代價來換得最優解的產生。對此，提出一種基于個體相似`性評價策略的改進遺傳算法，融入了一種新的旋轉交叉算子，每個子個體根據其與父個體的相似度和可信度來確定個體的適應度值，僅當可信度值低于某個閾值時，個體才做真實的適應度計算。實驗結果顯示，相似性評價策略計算得到的個體適應度值接近真實的適應度值，并且改進的算法求得最優解需要的評價次數明顯要少于傳統遺傳算法，而在測試準測上的數據表明：提出的改進遺傳算法相對于傳統遺傳算法，性能較好且求得的最優解也較為理想。

遺傳算法相似性評價交叉算子

0　引　言

圖1　遺傳算法模型

遺傳算法GA(Geneticalgorithm)是一種借鑒生物界的進化規律(適者生存、優勝劣汰遺傳機制)演化而來的隨機化搜索方法。目前已被廣泛應用于求解各類優化問題[1-5]。然而，這種基于種群搜索機制的優化方法在求解復雜計算問題時總是以計算時間為代價來換得最優解的產生，盡管現今硬件技術的快速發展，使得GA朝著最優解方向的搜索時間得到了縮短，但從算法自身的執行進制出發，縮短算法的搜索時間，提高算法的運行效率，是更值得研究人員思考的問題。

一般而言，傳統的GA模型可分為三個部分[6]，見圖1所示。

存儲器用于存儲每一代種群的優良個體，算法執行初始階段，存儲器中是一組隨機生成的個體，每一個體代表著優化問題的一個候選解。進化器中包括兩個主要算子：交叉和變異算子。進化器的作用是接收存儲器傳遞過來的父代個體，對個體執行交叉和變異操作，得到子代個體。進化器產生的每一個子代個體都需要經過評價器的測試。在求解優化問題中，評價器往往是一個帶有約束條件的待優化的單目標或多目標函數, 每個個體都有一個相應的目標函數值(標量或矢量形式)，根據預先設定的準則來比較個體間的優劣關系，以選擇出優秀個體進入到下一代種群。

GA模型的執行時間在很大程度上集中在進化器和評價器上。就進化器組成部分而言，已經提出了不少改進策略[7-9]，這些改進策略在增強GA搜索性能的同時也帶來了額外的時間成本。在個體評價過程中，執行時間主要取決于個體目標函數的計算次數。由此，我們可以初步設想通過減少目標函數的計算次數來達到縮短GA總的執行時間。

本文提出一種基于相似性評價策略的改進遺傳算法IGA(Animprovedgeneticalgorithmbasedonsimilarstrategyofevaluation)。IGA與傳統遺傳算法TGA(Traditionalgeneticalgorithm)的執行流程基本一致[10]，不同之處主要表現在：(1)進化器中引入一種新的旋轉交叉算子，達到增強種群個體多樣性的目的。(2)在評價器中，本文借鑒了生物學物種相似性特點，通過分析個體性狀的基因相似性規律，提出一種新的基因相似性計算方式。因此，在求解優化問題中，個體適應度的評價不再僅僅通過待優化的函數計算得到，通過對子個體與父個體進行相似性度量，根據度量的結果來指定子個體的適應度值f與可信度值r，r是一個反映個體適應度值f與真實適應度值接近的參數。通過在測試函數上的實驗結果，我們驗證了所提出算法的有效性和改進思想的先進性。

1　IGA描述

自然界中物種都各有其不同的特征性狀，比如：世界上不存在兩片完全一樣的樹葉，無論從大小、顏色、形狀及重量，而決定這些特征性狀的關鍵因素取決于物種自身內在的基因序列。通常，每一物種內在的不同基因對外表現出的特征狀態是不一樣的，物種內在的基因有其似性特點，但同時也存在著差異，但就基因相似概率來判斷物種是否同屬于一類末必可行。比如，老鼠和人類在基因、基因內容和DNA序列方面高度相似，僅從基因角度很難判斷是鼠還是人。新的研究發現，人類基因有許多重復的內容，這些重復內容早期一直被稱為“垃圾DNA＂，有學者認為正是重復的內容才分開了人與鼠。單就人類自身而言，做DNA鑒定，可以通過基因的相似特點來判定子女是否是父母所生，這源于子女的遺傳物質各有一半分別來父親和母親。因此，子女在特征性狀上和自己的父母存在相似的同時也存在著差異，這在生物學上的表現被稱之為“基因”相似性和“基因”多樣性?，F實科技領域中，人們基于現有的基因學知識，通過模擬物種間的進化和遺傳等演變過程，已經將GA很好地應用于許多實際復雜系統問題，但在求解復雜優化問題時，對個體間的相似性如何評價以及基因的多樣性如何增強一直是眾多學者研究的熱點之處。在此，本文借鑒生物學知識，提出以下基因相似性評價策略和種群多樣性的增強方法，從而更好地優化GA模型功能，提高解決實際問題的能力，同時也為模擬生物學某些特有現象以更好地為提高解決復雜系統問題的能力提供了一定可借鑒之處。

1.1相似性評價策略

從遺傳學角度來說，物種的父代與子代之間，通常父代的基因特征決定著子代的對外特征表現，也即子代的特征在某種程度上依賴于父代的內在基因特征，父代的基因遺傳物質即有完全遺傳的可能，也有發生變異遺傳的概率；同一染色體中，處于不同位置的基因在決定對外特征的表現功能也是不一樣的。類似地，在GA求解復雜系統問題的每一代進化過程中，由于子個體與父個體存在著較高的相似特征，子個體的適應度值在一定程上依賴于父個體的適應度值；因此，子個體的適應度值可以基于父個體的適應度值為參照來評價其自身的適應度值，暫時不考慮個體真實適應度函數的計算方式，在某種程度上能夠減少目標函數的計算次數，縮短算法的執行時間。顯然，這對提高GA的執行效率，優化GA模型的功能起到了一定的實質效果。但僅僅采用這種策略來計算個體的適應度值是不完善的，當種群中個體適應度值嚴重與個體真實的適應度值失真時(即兩者相差較大)，就會影響優良個體進入下一代種群；在此，給每個個體設定一個與之相應的評價其適應度值好壞的可信度參數r，當r小于預先設定的閾值T時，重新使用真實的適應度函數來計算個體的適應度值；否則，就使用預先設定的適應度評價策略來評價個體的適應度值。在此，稱這兩種情況下得到的適應度值分別為“真實性適應度值”TFV(Truefitnessvalue)和“評價性適應度值”EFV(Evaluationfitnessvalue)。

本文在相似性評價策略中，可信度r的設定方式考慮子個體與父個體兩者間的適應度比值關系，使r能夠更好地反映出個體EFV的可信程度。另外，在EFV的評價方式上，本文算法并不簡單計算子個體與父個體同位互異基因的個數，通過給每一位基因位分別指定一個相應的效能系數λ，計算出子個體與父個體間的差分，由此確定出兩者的相似性。實驗中，使用本文算法給出的評價個體適應度的方式，可以縮短與EFV和TFV間的差距。此外，本文算法的可信度閾值T采用了固定和動態地兩種方式。這樣，算法執行時就能動態地調節具有EFV的個體比例，使得評價過程在確保優良個體進入下一代種群的同時，也更加接近真實狀態下的選擇過程。

本文算法生成下一代子個體的方式按以下步驟進行：

隨機性生成一個初始種群。每個個體p均由三個元素組成：二進制編碼字符串(染色體)、適應度值f、可信度r。初始種群中的每個個體使用真實的適應度函數計算f，并置r為1。

(1) 從種群中選擇兩個父個體p1和p2進行交叉與變異運算，并對生成的子個體c1與c2分別計算個體的f和r。

子個體與父個體相似性的度量，使用的是個體間的差分計算方式，由于處于不同位置的基因重要性是不相同的。在此，本文給出以下計算個體間差異的權值差分方法：

(1)

其中，函數D(c, p)計算出子個體c與父個體p間的差分值，個體的染色體編碼形式為：c=(c0,c1,…,cn-1)、p=(p0,p1,…,pn-1)。參數用于調節不同基因位受重視的程度，稱為效能系數；子個體c與父個體p間的差分是一個介于0與1之間的數字，兩個體間的相似性由下式給出：

S = 1-D(c, p)

(2)

可以看出：個體間的差分D(c, p)越大，個體間的相似性就越??；反之越大。

在此，假定子個體c1與父個體p1、p2的相似性分別為S1、S2。如果S1= 1，表明子個體c1與父個體p1完全“相似”， 從遺傳學角度來說，c1完全繼承了父個體p1的全部基因；此時，c1的兩個元素分別設置為：f = f1, r = r1；否則，如果S2= 1，則f = f2, r = r2。

如果上述兩個條件都不滿足，則個體c1的適應度f和可信度r分別按下述方式進行計算：

(3)

(4)

對于種群中的每個個體而言，個體的可信度r是一個介于0與1間的數值，反映了個體EFV和TFV間的近似程度。r越大，EFV越接近TFV。因此，在子個體可信度r的計算方式上融入對適應度的比值計算是可行的，仿真實驗表明：這種改進在一定程度提高了個體適應度的可信度，降低了對目標函數的計算次數，提高了算法的運行效率。

(2) 從種群個體適應度是否真實性的角度出發，如果完全采用上述個體適應度的評價方式，則種群中個體的適應度值與真實的適應度值就會產生嚴重的“失真”，不利于選擇過程的進行。為此，本文算法中預先設定一個閾值T，如果個體的r小于T，則f采用真實的適應度函數計算方式代替“評價性適應度值”，并重新置r = 1；否則，保留“評價性適度值f”，并維持目前的r。實驗中T的設置分兩種情況：一種是動態地進行設置。在每一代種群中統計出具有“評價性適應度值”個體占有的比率k，若k小于指定的W1，則T按照指定的方式動態變??；若k大于指定的閾值W2，則T以指定的方式動態變大；兩種情況都不滿足，則保持 T不變。另一種方式是在算法執行的整個過程中，T始終保持不變。比較這兩種方式，T的動態設置更有利于調節種群中具有TFV的個體比率，提高選擇過程的真實性。從式(3)和式(4)可以看出：子個體c1的適應度值總是介于兩個父個體f1與f2之間，其可信度r

1.2旋轉交叉算子

對于從種群中選定的兩個個體p1與p2，先將每個個體首尾相連，構成一個圓環形狀，再讓兩個圓環相交，并同時讓兩個圓環按預置的速度分別進行旋轉，在設定的時刻到達后，互換圓環交叉部分，達到增強種群多樣性的目的，具體過程見圖2所示。

p1=1001101010110011

p2=1011011100110010

圖2　旋轉交叉過程

1.3變異算子

變異是在種群中按照變異概率pm任選若干基因位改變其位值，對于二進制編碼來說，就是反轉位值。本文所提出的算法中，使用與傳統進化算法相同的變異方式[9]。

2　仿真結果

本文選用來自文獻[10]的兩個標準測試函數來驗證所提出算法的有效性，每一個輸入參數使用8位二進制編碼方式，因此，每位基因的效能系數λi根據其二進制所在的權值做歸一化處理，見表1所示。

表1　效能系數計算方式

測試函數描述如下：

-5.12

-200

其中,F1(x)和F2(x)兩個函數的維數D=20。TGA和IGA用于求解上述兩個函數的最大值。兩種算法在兩個測試函數中使用的參數設置相同，參數設置見表2所示。

表2　TGA和IGA在不同測試函數中的參數設置

比較TGA和IGA兩種算法間的性能差異，我們考察整個行進過程中出現的三個重要時刻來評價各算法間的性能優劣。根據總的函數評價次數Niter，這三個位置時刻分別設定在1/3Niter、2/3Niter和Niter位置。針對每一個位置，都有一個對應的測試點， 例如，在E1=1/3 Niter時，其對應的測試點如圖3所示。

圖3　IGA和TGA性能差異的比較

圖3中實線和虛線分別描述了TGA和IGA在每次評價中的最優適應度值變化曲線。在E1=1/3Niter時, 圖2中的兩個菱形和圓點被用于比較TGA和IGA的性能差異，其性能測試準則定義如下[4]：

在此，ΔE介于0和1之間，若E2為某一固定值，ΔE越大，則由IGA獲得與TGA相同的適應度值所需要的評價次數越少。而ΔF越大，在相同的評價次數下，由IGA獲得的適應度值越大。

圖4顯示出TGA和IGA在不同測試函數上的進化曲線過程，星號(“﹡”)線描述TGA求解函數最優適應度值的曲線變化過程；菱形(“◇”)線描述IGA在固定閾值T=0.4時的尋優路徑；叉形 (“×”) 線描述IGA在動態閾值T初始為0.8，且閾值W=W1=W2=0.5的動態變化曲線。在圖4(a)中，可以觀察到這樣一種現象，IGA在固定和動態閾值T的情況下，都能最終獲得測試函數的最優適應度值，兩者在進化過程中的路徑變化較為相似，也即每次函數評價時，得到的最優適應度值較為相近，但IGA在動態閾值 T變化情況下獲得最優適應度值略微更好。IGA和TGA兩種算法最終都能求得F1函數的最優適應度值，在進過程中，IGA的兩種閾值設置方式得到的最優適應度值都略高于TGA。在圖4(b)中也出現了與圖4(a)類似的情況，但兩種算法獲得的最優適應度值只能接近真實最優適應度值，并且IGA在動態情況下獲得的最優適應度值最好。

圖4　GA 和IGA在不同測試函數上的進化曲線

表3和表4分別描述了GA和IGA在兩個函數尋優過程中，在三個測試點上表現出來的性能差異，可以看出：通過IGA獲得與TGA相同的適應度值，IGA所需要的評價次數明顯較少，而執行相同的評價次數時，IGA相對于GA能夠獲得更高的適應度值。例如，對函數F1而言：在測試點TP1上，若T=0.4，說明IGA需要的評價次數相對于TGA要少13.41%, 而在相同的評價次數下，IGA獲得的EFV比通過TGA獲得的TFV要高10.27%。 雖然ΔF在三個測試點上的性能都能計算出來，但在最終測試點TP3，由于TGA很難以實現與IGA相同的最優適應度值，故ΔE無法計算。表格中的數據顯示出：IGA在兩種閾值T的設置中，動態閾值T的效果較好。

表3　GA 和IGA在函數F1 上的性能比較

表4　GA和IGA在函數F2 上的性能比較

綜上所述，本文在TGA中引入相似性評價策略并提出IGA。在IGA執行過程中，子個體能夠較好地根據與父個體的相似性及可性度r計算個體的“評價性適應度值”，從而減少真實個體適應度的計算次數，有利于縮短總的尋優時間，測試準則上的數據也較好地說明本文提出的“評價策略”能夠確保種群在接近真實適應度值的同時，縮短評價次數，最終獲得理想的最優適應度值結果。

3　結　語

本文從遺傳學角度，探討了一種評價個體相似性的策略，在TGA中引入這種個體相似性評價策略，實驗的效果顯示出IGA能夠以較少的評價次數得到與TGA的十分接近的結果。就兩個測試準則而言，IGA在動態閾值T下取得的效果要比固定閾值T下取得的效果更好，但兩種設置方式相對TGA，都能以相對較少的評價次數獲得接近真狀下的TFV，雖然在進化過程中，IGA中個體的適應度值都要略高于TGA，但IGA最終也能較好地求得全局最優解。

本文算法的后繼工作將分析IGA的時間及復雜度性能，并借鑒生物學中的其他知識，通過真實的模擬其內在演變規律，達到更好的優化GA模型功能，從而為生物學知識轉變為現實的解決復雜系統問題的方式提供一定的可借鑒之處。

[1] 李學峰. 遺傳算法同步選擇特征和支持向量機參數的網絡入侵檢測[J].計算機應用與軟件，2014，31(3)：301-303,333.

[2] 張彬，鄧紅霞，李海芳．應用兩階段遺傳算法優化求解動態因果模型[J]．計算機應用與軟件，2014，31(4)：278-280,292．

[3] 朱夏, 李小平,王茜.基于總空閑時間增量的無等待流水調度混合遺傳算法[J]. 計算機研究與發展, 2011,48(3):455-463.

[4]TangKZ,YuanXJ,SunTK,etal.Animprovedschemeforminimumcrossentropythresholdselectionbasedongeneticalgorithm[J].Knowledge-Basedsystems, 2011,24(8):1131-1138.

[5]TangKZ,SunTK,YangJY.Animprovedgeneticalgorithmbasedonanovelselectionstrategyfornonlinearprogrammingproblems[J].Computers&ChemcialEngineering, 2011, 35 (4): 615-621.

[6]SalamiM,HendtlassT.Afastevaluationstrategyforevolutionaryalgorithms[J].Appliedsoftcomputing, 2003,2(3):156-173.

[7]TangKZ,YangJY,ChenHY.Animprovedgeneticalgorithmfornonlinearprogrammingproblems[J].TheJournalofSystemsEngineeringandElectronic,2011,22(3):540-546.

[8] 劉全, 王曉燕, 傅啟明.雙精英協同進化遺傳算法[J].軟件學報, 2012,23(4):765-775.

[9]CasillasJ,Martlnez-LópezFJ.MiningUncertaindatawithmultiobjectivegeneticfuzzysystemstobeappliedinconsumerbehaviourmodelling[J].ExpertSystemsWithApplication, 2009,36(2):1645-1659.

[10] 李敏強, 寇紀凇. 遺傳算法的基本理論與應用[M].北京：科學出版社，2002.

[11]KumarS,RaoCSP.Applicationofantcolony,geneticalgorithmanddatamining-basedtechniquesforscheduling[J].RoboticsandComputer-IntegratedManufacturing,2009,25(6):901-908.

[12]ZhanZH,ZhangJ,LiY,etal.AdaptiveParticleswarmoptimization[J].IEEETransactionsonSystems,Man,andCybernetics-PartB:Cybernetics,2009,39(6):1362-1381.

IMPROVEDGENETICALGORITHMBASEDONINDIVIDUALSIMILARITYEVALUATIONSTRATEGY

TangKezong1ZhangTong2LuoLimin1

1(School of Computer Science and Engineering, Southeast University, Nanjing 210094,Jiangsu,China)2(Institute of Information Engineering, Jingdezhen Ceramic Institute, Jingdezhen 333403,Jiangxi,China)

Geneticalgorithmisamethodofsearchingtheoptimalsolutionbysimulatingnaturalevolutionaryprocess.Butitalwaysrequireslongercomputationtimeforthebestsolutioninsolvingprocess.Thispaperpresentsanimprovedgeneticalgorithm,itisbasedonindividualsimilarityevaluationstrategy.Initanewrotationcrossoveroperatorisincorporated.Thefitnessvalueofeachindividualisassignedaccordingtoitssimilarityandreliabilitywithitsparents.Therealfitnessofindividualisonlyevaluatedwhenthereliabilityvalueisbelowathreshold.Experimentalresultsshowthatthefitnessvaluesofindividualderivedfromsimilarityevaluationstrategyareclosetotheactualones,andthenumberofevaluationsrequiredforseekingtheoptimalsolutionbytheimprovedgeneticalgorithmissignificantlylessthanthatoftraditionalgeneticalgorithm.Additionally,thedataontestcriterionshowthattheperformanceoftheproposedalgorithmandtheoptimalsolutionderivedfromitarerelativelybetterthanthetraditionalgeneticalgorithmaswell.

GeneticalgorithmSimilarityevaluationCrossoveroperator

2014-07-09。國家自然科學基金項目(61202313)；江西省教育廳科研項目(GJJ13637，2013BAB211020)。湯可宗，副教授，主研領域：多目標優化。張彤，本科。羅立民，教授。

TP301.6

ADOI:10.3969/j.issn.1000-386x.2016.03.055