二進制編碼GA基因種群多樣性數(shù)學模型研究

趙紅??肖文潔??李瀅????

摘要摘要：針對GA早熟收斂中存在的種群多樣性定義缺乏統(tǒng)一性和普適性問題，建立了二進制編碼GA基因?qū)哟畏N群多樣性數(shù)學模型。首先，提煉了該多樣性的含義，提出用任意代種群中表示各編碼基因位取值的變量來描述種群多樣性的大小，該變量可看作隨機變量；其次，設計了基因位直方圖、基因位曲線圖等圖形化方法來體現(xiàn)其在GA進化過程中的變化規(guī)律；最后，指出了進一步的分析思路和方向。

關鍵詞關鍵詞：GA；種群多樣性；基因?qū)哟?；隨機變量；基因位圖

DOIDOI：10.11907/rjdk.1511258

中圖分類號：TP301

文獻標識碼：A文章編號文章編號：16727800（2015）011000803

基金項目基金項目：國家自然科學基金項目（61202136）；江蘇省高校自然科學研究項目（13KJD520007）；南京市可信云計算與大數(shù)據(jù)重點實驗室項目（2015）；江蘇省未來網(wǎng)絡前瞻性研究項目（BY2013095-3-11）

作者簡介作者簡介：趙紅（1982-），女，黑龍江哈爾濱人，博士后，南京曉莊學院信息工程學院講師，研究方向為人工智能、機器學習。

0引言

遺傳算法（Genetic Algorithm， GA）計算過程簡單，對搜索空間具有廣泛的適應性，是21世紀有關智能計算的關鍵技術(shù)之一。目前，早熟收斂仍是GA中最亟待研究和解決的問題之一，現(xiàn)有研究表明GA進化過程中種群多樣性如何變化對其收斂狀態(tài)具有本質(zhì)影響。因此，關于種群多樣性在GA進化過程中變化趨勢問題的研究具有重要意義。 縱觀現(xiàn)有文獻中關于GA種群多樣性的定義方式，諸多作者提出可以從微觀[14]（基因?qū)哟危┖秃暧^[2，5，6]（個體層次）兩個角度進行統(tǒng)一?；?qū)哟畏N群多樣性是從遺傳操作的角度衡量種群的進化能力，是分析GA進化過程和收斂狀態(tài)的重要指標。

但是以上定義或往往用于計算種群中兩個個體的差異性，如Hamming距離[4]、歐式距離[5]、基因座權(quán)重[6]等，并且是在設計交叉算子時使用，目的是保證和維持交叉后一定的種群多樣性，但對于整個種群多樣性在進化的不同階段、在三個遺傳算子不斷作用后的變化規(guī)律及其對收斂狀態(tài)的影響卻無法體現(xiàn)和分析；或計算量大，不便于使用，如種群熵[2]等，大大限制了其適用性。此外，現(xiàn)有文獻往往從遺傳算子的改進入手來保持或提高GA種群多樣性，并且從算法產(chǎn)生的新個體或收斂到的最優(yōu)解來說明其有效性，但是對于遺傳算法控制參數(shù)及遺傳算子是如何影響GA種群多樣性的變化并且貫穿GA進化整個過程的卻沒有直觀的體現(xiàn)和分析[7-14]。 而種群多樣性是GA進化過程中最重要的性能指標，其如何變化將直接影響GA的收斂狀態(tài)和收斂速度。因此，本文所作的有關這方面的研究有重要意義。

進一步研究可從以下兩個方面展開：①該模型在不同外界條件下：如初始種群、種群規(guī)模、遺傳算子參數(shù)（包括選擇不同的遺傳算子）、進化代數(shù)等控制參數(shù)，如保持其中三項不變，只改變一項時，該模型的變化規(guī)律及其對GA收斂狀態(tài)和收斂速度的影響；②對克服GA早熟收斂的典型算法性能進行研究，探索并總結(jié)克服GA早熟收斂的可行性方向及方法。

3結(jié)語

本文對現(xiàn)有眾多GA種群多樣性的定義進行分析，提煉出其本質(zhì)含義，借鑒隨機變量的概念來建立了統(tǒng)一通用的GA基因?qū)哟畏N群多樣性的數(shù)學模型。定義了基因位期望值、基因位偏離度、方差等一系列概念，提出基因位直方圖、基因位曲線圖等圖形化方法對GA進化不同階段種群多樣性的變化規(guī)律進行了有效分析。

參考文獻參考文獻：

[1]LIU S，ZhAO H.Effect of genetic crossover and mutation on population diversity[J].Control and Decision，2009，24（10）：15251539.

[2]ZHANG X G，DAI G Z，XU N P.Study on diversity of population in Genetic Algorithms[J].Control Theory and Application，1998，15（1）：1722.

[3]LIAO G C，TSAO T P.Application embedded chaos search immune genetic algorithm for shortterm unit commitment[J].Electric Power Systems Research.2004（71）：135144.

[4]LIU Q，WANG X Y，F(xiàn)U Q M，et al.Double elite coevolutionary genetic algorithm[J].Journal of Software，2012，23（4）：765？775 .

[5]江中央，蔡自興，王 勇.求解全局優(yōu)化問題的混合自適應正交遺傳算法[J].軟件學報，2010，21（6）：12961307.

[6]祝希路，王柏.一種基于社團劃分的小生境遺傳算法[J].控制與決策，2010，25（7）：11131116.

[7]TANG K Z，SUN T K，YANG J Y.An improved genetic algorithm based on a novel selection strategy for nonlinear programming problems[J].Computers and Chemical Engineering，2011，35（4）：615621.

[8]BORIS P L，JESSICA S C.A deterministic annular crossover genetic algorithm optimisation for the unit commitment problem[J].Expert Systems withm Applications，2011，38（6）：65236529.

[9]WANG L，TANG D B.An improved adaptive genetic algorithm based on hormone modulation mechanism for JobShop scheduling problem[J].Expert Systems withm Applications，2011，38（6）：72437250.

[10]NEDIM T.Opyimization of multimodal continuous functions using a new crossover for the realcoded genetic algorims[J].Expert Systems withm Applications，2009，36（4）：81728177.

[11]MURAT A，NOVRUZ A.Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J].Expert Systems withm Applications，2011，38（3）：13131320.

[12]LING S H，LEUNG F H F.An improved genetic algorithm with averagebound crossover and wavelet mutation operations[J].Soft Computing，2007，11（1）：731.

[13]莊健，楊清宇，杜海峰，等.一種高效的復雜系統(tǒng)遺傳算法[J].軟件學報，2010，21（11）：27902801.

[14]WANG Y，LIU H，CAI Z X，et al.An orthogonal design based constrained evolutionary optimization algorithm[J].Engineering Optimization，2007，39（6）：715736.

責任編輯（責任編輯：陳福時）