基于信息熵的變異算子設(shè)計(jì)

王再見，董育寧

(1.安徽師范大學(xué)物理與電子信息學(xué)院，安徽蕪湖 241000;2.南京郵電大學(xué)通信與信息工程學(xué)院，江蘇南京 210003)

0 引言

遺傳算法(Genetic Algorithms，GAs)模擬的是生物進(jìn)化過程［1］，是一種自適應(yīng)啟發(fā)式概率性迭代全局搜索算法，由于簡單易行在各個(gè)領(lǐng)域得到廣泛應(yīng)用。但是，GAs早熟收斂使其全局收斂性存在一定概率的不穩(wěn)定，降低了算法性能。導(dǎo)致GAs早熟收斂的主要原因是基因多樣性的降低。較大的種群規(guī)模(基因多樣性較好)可以提供較好的全局搜索性能，但收斂相對較慢;而較小的種群規(guī)模(基因多樣性較差)，其搜索空間的分布范圍有限，可以較快地達(dá)到局部最優(yōu)解，容易引起未成熟收斂。在實(shí)際問題的求解過程中，種群規(guī)模是有限的。因此，如何在有限的種群規(guī)模條件下，保持基因多樣性，進(jìn)而快速產(chǎn)生優(yōu)良后代是GAs必須解決的問題。該文針對該問題，從變異算子的設(shè)計(jì)入手，提出了基于信息熵的變異算子。改進(jìn)后的變異算子考慮了變異行為與環(huán)境的關(guān)系，增加了種群信息量，有效地保持種群的多樣性，保證了種群進(jìn)化的質(zhì)量。

1 變異分析

變異是眾所周知的影響GAs收斂性能和搜索效果的重要因素之一，文獻(xiàn)［2］對變異的搜索能力進(jìn)行了詳細(xì)的分析，指出變異是唯一具有全局搜索能力的遺傳算子。文獻(xiàn)［3-6］表明變異與求解的問題有關(guān)。但在GAs研究中變異都是基于概率、固定的且與問題無關(guān)的，其發(fā)生都是隨機(jī)的［7］，變異率也是數(shù)值實(shí)驗(yàn)得到的經(jīng)驗(yàn)值［3，4］，雖然有文獻(xiàn)采用自適應(yīng)變異率來改善算法性能，但僅考慮適應(yīng)度等部分因素，忽略了各因素產(chǎn)生的關(guān)聯(lián)影響，在一些應(yīng)用中算法的效果并不好［8］。正如Trewavas在文獻(xiàn)［9］中指出:對于變異，簡單數(shù)學(xué)工具的使用不僅使所涉及的機(jī)理遠(yuǎn)比實(shí)際的簡單，甚至發(fā)生直接的誤導(dǎo)作用。GAs基于適應(yīng)度的進(jìn)化模式?jīng)]有考慮進(jìn)化的外部環(huán)境和進(jìn)化成分之間的關(guān)系，變異率的使用掩飾了生物學(xué)變異，忽略了個(gè)體的重要性，導(dǎo)致或頻繁破壞已獲得的優(yōu)良模式，或使種群收斂到早熟集，降低了算法搜索能力。

生物進(jìn)化的實(shí)質(zhì)在于種群基因頻率的改變，每個(gè)種群都有它獨(dú)特的基因庫，基因庫代代相傳，并在傳遞過程中得到保持和發(fā)展，種群越大，基因庫也越大;反之，種群越小基因庫也越小。當(dāng)種群變得很小時(shí)，就有可能失去遺傳的多樣性，從而失去了進(jìn)化上的優(yōu)勢而逐漸被淘汰［10，11］。由此可見，變異與具體的環(huán)境有關(guān)，其目的是增加種群的信息量，這在算子設(shè)計(jì)時(shí)需要充分考慮。

2 基于信息熵的變異算子

由信息論可知，信息熵在隨機(jī)事件發(fā)生之前，它是結(jié)果不確定性的量度;在隨機(jī)事件發(fā)生之后，它是從該事件中所得到信息的量度(信息量)［15］。引入信息熵作為基因信息的度量，目的為變異提供判斷依據(jù)。

2.1 幾個(gè)概念

定義2.1 基因庫:解空間所含的全部基因。

定義2.2 當(dāng)前種群基因庫:當(dāng)前種群所含的全部基因。

定義2.3 基因類型:完全一樣的基因?qū)儆谕活愋汀?/p>

定義2.4 基因類型信息熵:對于當(dāng)前種群，如果基因庫S內(nèi)基因類型入選當(dāng)前種群基因庫的概率分布P={p1，…，pn}，則每種基因類型本身的信息為Ii=-log2pi，基因類型的平均信息量為 H=，這個(gè)平均信息量就是基因類型信息熵。

基因類型信息量假設(shè):當(dāng)前種群基因庫不存在的基因類型，各類型的信息量相等，且相互獨(dú)立。

2.2 基于信息熵的變異算子設(shè)計(jì)及性能分析

基于信息熵的變異算子是對生物變異過程的逼近，應(yīng)體現(xiàn)以下特點(diǎn):① 變異既有隨機(jī)性也有普遍性，與當(dāng)前種群(具體的環(huán)境)有關(guān)，體現(xiàn)在變異概率受當(dāng)前種群影響，動態(tài)調(diào)整;② 變異目的是增加種群的信息量，體現(xiàn)在變異算子傾向于引進(jìn)新的基因類型，以增加種群的信息量，避免基因多樣性降低而導(dǎo)致早熟收斂。基于以上分析，該文提出的基于信息熵的變異算子實(shí)現(xiàn)步驟如下:

步驟1 設(shè)定變異概率:

式中，qn為第n代變異概率;α為修正因子，用于調(diào)整基因概率估計(jì)不準(zhǔn)所帶來的誤差(實(shí)驗(yàn)取值1);Hn為第n代基因類型信息熵。

式(1)說明，變異概率的大小取決于當(dāng)代基因類型信息熵:①Hn變大則qn變小，說明隨著種群基因類型信息熵變大，變異的作用變小，這樣避免變異操作頻繁破壞已獲得的優(yōu)良模式，使GAs陷入隨機(jī)搜索。②Hn變小則qn變大，說明隨著種群信息量變小，基因多樣性降低，有導(dǎo)致早熟收斂的可能，此時(shí)需要提高變異概率，補(bǔ)充新的基因，豐富種群的基因類型，為進(jìn)化提供更多的原材料，提高全局搜索的能力，這對于那些積木塊在整個(gè)解空間中分散分布的問題很重要。目前公認(rèn)為GAs操作中，演化初期變異的作用小，起主要作用的是交叉算子，演化后期起主要作用的是變異算子。這在式(1)中得到較好的體現(xiàn)，因?yàn)槌跗诜N群基因類型信息熵大，基因類型豐富，而通常變異概率很小，所以交叉算子作用明顯，演化后期基因多樣性降低，交叉算子無法引入新的基因，易陷入局部最優(yōu)解，此時(shí)變異概率很大，變異算子起主要作用。

步驟2 選擇變異點(diǎn):依據(jù)基因類型信息量，采用輪盤賭的方式選取欲引入的基因，基因類型信息量較高的該類型基因以較大的概率被選中，欲替換的對應(yīng)位置就是變異點(diǎn)。

3 實(shí)驗(yàn)測試

鑒于P={p1，…，pn}很難確定，而GAs的基因就是二進(jìn)制的位，基因的概率決定了其所屬的基因類型概率。但是在實(shí)際運(yùn)算中獲得基因的概率分布幾乎不可能實(shí)現(xiàn)，此外，信息熵的計(jì)算非常復(fù)雜，而具有多重前置條件的信息，更是幾乎不能計(jì)算。因此，對基因類型信息量的計(jì)算作如下簡化:

①屬于當(dāng)前種群基因庫的基因類型，令基因類型i的概率估計(jì)為:

則其信息量為:

式中，Ni為基因類型為i的基因在當(dāng)前種群基因庫中的總數(shù)(當(dāng)Ni變大，意味著Nj(j≠i)變小，導(dǎo)致基因類型分布失衡，當(dāng)前種群的信息熵Hn偏離Hmax越遠(yuǎn))，NP為當(dāng)前種群基因庫缺失的基因類型總數(shù)，ND為當(dāng)前種群基因庫的規(guī)模。對于設(shè)計(jì)過程中將ND、NP拆分，是由于在種群更新時(shí)，因?yàn)獒槍€(gè)體的適應(yīng)度評估，會使得總體質(zhì)量較差的個(gè)體(但是該個(gè)體本身具有個(gè)別的優(yōu)良基因)遭到淘汰，會造成當(dāng)前種群缺失部分優(yōu)良基因。

②當(dāng)前種群基因庫缺失的基因類型，各基因類型信息量相等，設(shè)基因類型概率的估計(jì)皆為:

則信息量為:

由以上分析可以看出，用各類型基因在種群中所占的大致比例來近似基因類型的概率，反映基因類型入選的概率較大則該類型基因出現(xiàn)在當(dāng)前種群中的頻率較高。

該文采用式(6)、式(7)2個(gè)典型的函數(shù)(閾值皆設(shè)為 ±0.005)，將采用新變異算子的 GAs與SGA［12］、FLAGA［13］、HMGA［14］進(jìn)行實(shí)驗(yàn)比較。

函數(shù) f1(x，y)有6個(gè)局部極小點(diǎn)，有2個(gè)點(diǎn)(-0.0898，0.7126)和(0.0898，-0.7126)為全局最小點(diǎn)，最小值為-1.031628;函數(shù)f2(x，y)是個(gè)多峰函數(shù)，只有1個(gè)全局最大點(diǎn)(0，0)，最大值為1。

與SGA相比，采用新變異算子的GAs在平均收斂代數(shù)、早熟次數(shù)及平均收斂時(shí)間3個(gè)指標(biāo)方面優(yōu)勢明顯;與FLAGA和HMGA相比也有較好的改善。其原因在于，SGA沒有考慮環(huán)境對種群質(zhì)量的影響，其變異算子的設(shè)計(jì)是固定的，與問題無關(guān)。而FLAGA和HMGA的變異盡管也是基于概率的，但是通過微調(diào)或記憶等措施保證種群基因信息量，這些保證措施可看作是變異算子的組成部分，事實(shí)上此時(shí)的變異與環(huán)境有關(guān)，間接實(shí)現(xiàn)了該文的思想，因此實(shí)驗(yàn)效果接近。

圖1給出種群“變異概率”和“基因類型總數(shù)”之間的關(guān)系圖(迭代100次的統(tǒng)計(jì)平均)，該圖表明變異概率與當(dāng)前基因分布有關(guān)，總體趨勢是:隨著種群中基因類型增多，種群變異概率變小，避免陷入隨機(jī)搜索;隨著種群中基因類型減少，種群變異概率變大，目的是增加新基因。

圖1 種群“變異概率”和“基因類型總數(shù)”的關(guān)系圖

4 結(jié)束語

該文從設(shè)計(jì)思想入手，分析了GAs中傳統(tǒng)變異算子存在的不足，在此基礎(chǔ)上，引入信息熵，利用基于信息熵的變異算子改進(jìn)傳統(tǒng)的變異方式，有效地克服了早熟收斂，增強(qiáng)了GAs對復(fù)雜問題的求解能力。并根據(jù)此機(jī)理提出一個(gè)稍加改進(jìn)的GAs，最后對2個(gè)典型的函數(shù)優(yōu)化問題進(jìn)行了模擬比較，結(jié)果表明基于信息熵的變異算子大大增強(qiáng)了算法的尋優(yōu)能力，改進(jìn)了搜索性能。

［1］YANG Wen-zhu，LI Dao-liang，ZHU Liang.An Improved Genetic Algorithm for Optimal Feature Subset Selection from Multi-character Feature Set［J］.Expert Systems with Applications，2011，38(3):2733-2740.

［2］KAYA I.A Genetic Algorithm Approach to Determine the Sample SizeforControlChartswith Variablesand Attributes ［J］.Expert Systems with Applications，2009，36(5):8719-8734.

［3］王洪峰，汪定偉，楊圣祥.動態(tài)環(huán)境中的進(jìn)化計(jì)算［J］.控制與決策，2007，22(2):127-131.

［4］YANG Sheng-xiang， YAO Xin. Population-based IncrementalLearning with Associative Memory for Dynamic environments ［J］.IEEE Transactions on Evolutionary Computation，2008，12(5):542-561.

［5］JIN Yao-chun，BRANKE J.Evolutionary optimization in uncertain environments-a survey ［J］.IEEE Transactions on Evolutionary Computation，2005，7(3):303-317.

［6］SPEARS W M.Evolutionary algorithms:The role of mutation and recombination(Natural Computing Series)［M］.Berlin:Springer Verlag，2000:28-34.

［7］SUZUKI J.A further result on the Markov chain model of genetic algorithms and its application to A simulated annealing-like strategy［J］.IEEE Trans Systems，Man ＆Cybernetics，1998，28(1):95-102.

［8］劉敏，嚴(yán)雋薇.基于自適應(yīng)退火遺傳算法的車間日作業(yè)計(jì)劃調(diào)度方法［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(7):1164-1172.

［9］TREWAVAS A J.The importance of individuality.Lerner H R.Plant Responses to Environmental Stresses:FromPhytohormones to Genome Reorganization ［M］.New York:Marcel Dekker Inc，1999:27-42.

［10］RAVEN PETER H，JOHNSON GEORGE B.Biology［M］.New York:The McGraw-Hill Companies，2005.

［11］KARIN Klontke，ANTOINE Barrière，IRINA Kolotuev，et al.Trends，Stasis，and Drift in the Evolution of Nematode Vulva Development ［J］.Current Biology，2007，20(17):1925-1937.

［12］SRINVAS M，PATNAIK L M.A daptive probabilities of crossover and mutation in genetic algo rithms［J］.IEEE Transactions on SMC，1994，24(4):656-666.

［13］劉習(xí)春，喻壽益.局部快速微調(diào)遺傳算法［J］.計(jì)算機(jī)學(xué)報(bào)，2006，29(1):100-105.

［14］陳昊，黎明，陳曦.動態(tài)環(huán)境下基于混合記憶策略的遺傳算法［J］.應(yīng)用科學(xué)學(xué)報(bào)，2010，28(5):540-545.