王再見，董育寧

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

0 引言

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

1 變異分析

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

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

2 基于信息熵的變異算子

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

2.1 幾個概念

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

定義2.2 當前種群基因庫:當前種群所含的全部基因。

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

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

基因類型信息量假設:當前種群基因庫不存在的基因類型，各類型的信息量相等，且相互獨立。

2.2 基于信息熵的變異算子設計及性能分析

基于信息熵的變異算子是對生物變異過程的逼近，應體現(xiàn)以下特點:① 變異既有隨機性也有普遍性，與當前種群(具體的環(huán)境)有關(guān)，體現(xiàn)在變異概率受當前種群影響，動態(tài)調(diào)整;② 變異目的是增加種群的信息量，體現(xiàn)在變異算子傾向于引進新的基因類型，以增加種群的信息量，避免基因多樣性降低而導致早熟收斂?；谝陨戏治觯撐奶岢龅幕谛畔㈧氐淖儺愃阕訉崿F(xiàn)步驟如下:

步驟1 設定變異概率:

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

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

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

3 實驗測試

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

①屬于當前種群基因庫的基因類型，令基因類型i的概率估計為:

則其信息量為:

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

②當前種群基因庫缺失的基因類型，各基因類型信息量相等，設基因類型概率的估計皆為:

則信息量為:

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

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

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

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

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

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

4 結(jié)束語

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

［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］.控制與決策，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è)計劃調(diào)度方法［J］.計算機學報，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］劉習春，喻壽益.局部快速微調(diào)遺傳算法［J］.計算機學報，2006，29(1):100-105.

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