度量種群多樣性的一種新方法

段永紅

（太原大學(xué)外語(yǔ)師范學(xué)院 數(shù)學(xué)系，山西 太原 030012）

度量種群多樣性的一種新方法

段永紅

（太原大學(xué)外語(yǔ)師范學(xué)院 數(shù)學(xué)系，山西 太原 030012）

本文應(yīng)用非負(fù)矩陣的知識(shí)提出了種群多樣度的一種定義，并比較了常見(jiàn)衡量種群多樣度的做法，在一定程度上改善了以往種群多樣性的缺陷，為種群多樣性的判斷提供了一種新方法。

多樣度；非負(fù)矩陣；不可約

遺傳算法是受生物進(jìn)化理論啟發(fā)的搜索算法，是由Holland在19世紀(jì)70年代提出來(lái)的，而傳統(tǒng)的遺傳算法由于多樣性問(wèn)題的影響陷入早期收斂，導(dǎo)致的結(jié)果是算法陷入局部最優(yōu)。遺傳算法最重要的作用之一是維持種群的多樣性，而遺傳算法的研究結(jié)果告訴我們，增加種群的多樣性有益于進(jìn)化過(guò)程，遺傳算法多樣性需要解決的主要問(wèn)題是在遺傳進(jìn)化中測(cè)定并調(diào)節(jié)種群多樣性及其效果。

生物學(xué)中種群多樣性指的是種群中不同個(gè)體也就是個(gè)體結(jié)構(gòu)和行為的不同；遺傳進(jìn)化中，多樣性往往指的是結(jié)構(gòu)上的差異，在文[1]中，Landon將基因作為種群多樣性的主要因素，其主要原因是在遺傳計(jì)算中，兩個(gè)結(jié)構(gòu)相同的個(gè)體會(huì)在適值上都表現(xiàn)出同樣的行為，因此，基因型多樣性的降低通常能導(dǎo)致了群體行為多樣性的下降。

我們知道，增強(qiáng)算法的性能依靠局部?jī)?yōu)秀的個(gè)體一般不能實(shí)現(xiàn)，通常它們還會(huì)降低樣本的適應(yīng)性。因此，一個(gè)優(yōu)秀的進(jìn)化群體應(yīng)該表現(xiàn)出豐富的多樣性。許多學(xué)者在種群多樣性上進(jìn)行了不斷的研究，并給出了相應(yīng)的測(cè)定方法，并通過(guò)這些測(cè)定方法來(lái)改善遺傳算法的性能。

本文重點(diǎn)介紹種群多樣性的一般性描述，同時(shí)給出種群多樣性的定義，并在此基礎(chǔ)上利用特殊矩陣的知識(shí)給出了一種衡量種群多樣度的新方法。

1.從種群的不同個(gè)體角度度量種群多樣性

在遺傳算法中，我們一般用適應(yīng)度函數(shù)來(lái)評(píng)價(jià)種群中個(gè)體的優(yōu)劣程度。通常個(gè)體越好適應(yīng)度越高，個(gè)體越差適應(yīng)度越低。

在遺傳算法的設(shè)計(jì)中，常常用到原始適應(yīng)度函數(shù)和標(biāo)準(zhǔn)適應(yīng)度函數(shù)這兩種適應(yīng)度函數(shù)。

其中，原始適應(yīng)度函數(shù)是將問(wèn)題的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，常常用于求解極大值問(wèn)題。然而在許多現(xiàn)實(shí)問(wèn)題中，求解目標(biāo)往往需要的是求解某個(gè)函數(shù)的極小值，因而需要我們將其轉(zhuǎn)化為極大值并且適應(yīng)度值為非負(fù)。通常情況下它有以下三種轉(zhuǎn)化形式：

上式中：x是一代種群，f( x)是適應(yīng)值函數(shù)；μ(x)是問(wèn)題的目標(biāo)函數(shù)；Cmax可以是一個(gè)合適的輸入值，也可以是 N代進(jìn)化過(guò)程μ(x)的最大值或當(dāng)前群體中μ(x)的最大值； Cmin可以是合適的輸入值，或者當(dāng)前一代或前N代中μ(x)的最小值。

遺傳算法早期群體如果出現(xiàn)超級(jí)個(gè)體（適應(yīng)度遠(yuǎn)遠(yuǎn)超過(guò)了群體平均適應(yīng)度的個(gè)體）會(huì)由于在群體中出現(xiàn)過(guò)多的復(fù)制導(dǎo)致早熟收斂；然而在遺傳算法的后期，如果群體平均適應(yīng)度與最優(yōu)實(shí)驗(yàn)值過(guò)于接近時(shí)，則會(huì)導(dǎo)致停滯現(xiàn)象。

處理遺傳算法早熟和停滯問(wèn)題最常辦法就是變換適應(yīng)度函數(shù)。

常用的適應(yīng)度函數(shù)的比例變換方法有以下三種：

上式中：f′(x)是進(jìn)行比例變換后的適應(yīng)度函數(shù)；f( x)是未經(jīng)變換的適應(yīng)度函數(shù)；α，β是系數(shù)。

上述三種比例變換中，較為常用的是指數(shù)比例變換，它可以使得好的染色體串保持較多的復(fù)制機(jī)會(huì)，不但限制了其復(fù)制的數(shù)目而且避免其過(guò)快的控制整個(gè)群體。

選擇的強(qiáng)制性由系數(shù)決定，系數(shù)值越小，選擇強(qiáng)度就越趨向于那些適應(yīng)度高的染色體串。度量適應(yīng)度通常利用原始問(wèn)題的目標(biāo)函數(shù)，從計(jì)算量的角度來(lái)講，運(yùn)算量顯得較大，且影響了遺傳算法的執(zhí)行速度。為此，本文將對(duì)進(jìn)行二進(jìn)制編碼的群體進(jìn)行種群多樣性度量。

2.從基因的角度度量種群多樣性

定義1[4]設(shè)X是規(guī)模為N的一代種群，其個(gè)體分別記為個(gè)體的字符長(zhǎng)度都是L，其中種群 X可以用矩陣表示為：

用Dj表示矩陣X第j列元素和的函數(shù)，即

這就是說(shuō)，若X的第j列元素完全相同，則Dj=1.稱(chēng)為種群的多樣度。

由下面例1可以看出定義1的多樣度公式存在缺陷。

按定義1多樣度D( x)=4，然而事實(shí)上，種群x中4個(gè)個(gè)體有3個(gè)是相同的，種群基本上處于成熟狀態(tài)，可見(jiàn)這個(gè)定義很不合適。

由于遺傳算法GAS其過(guò)程主要是在0，1編碼下進(jìn)行的，所以定義1中矩陣X為非負(fù)矩陣，即X≥0，由特殊矩陣性質(zhì)[8]可知，非負(fù)矩陣可分為可約和不可約兩種，基于這個(gè)原因，這里給出一種種群多樣度的新定義，其定義如下：

性質(zhì)1 0＜D()x≤1

證明 因?yàn)?＜r≤L， 所以有0＜D()x≤1

性質(zhì)2 當(dāng)A為不可約非負(fù)矩陣時(shí)，D()x＝1

證明 A≥0，且不可約時(shí)，由不可約非負(fù)矩陣性質(zhì)[8]可知，矩陣A為滿(mǎn)秩矩陣，則r( A)=0,所以D(X)＝1

按定義1種群X的多樣度D(X)=3，按定義2種群多樣度 D(X)=1，這個(gè)結(jié)果與文獻(xiàn)[5]提出的種群多樣度的算法結(jié)果完全一致。

3 結(jié)論

利用特殊矩陣分析的相關(guān)知識(shí)提出了種群多樣度的一種新定義，通過(guò)對(duì)比看到它能準(zhǔn)確的反映種群的多樣性。另一方面，非負(fù)矩陣?yán)碚撏ㄟ^(guò)著名的矩陣論專(zhuān)家 Braue A, Johnson C R, Varga R S, Ostrowski A等卓有建樹(shù)的工作，已逐步形成比較完美的理論體系，因此，為種群多樣度的衡量提供了理論支持。

[1] Feldbaum A A.Dual control theory:I[J]. Automation and remote Control，1960.

[2] Feldbaum A A.Dual control theory:I[J]. Automation and remote Control，1961.

[3] Astom K J，Wittenmark B.自適應(yīng)控制[M]. 北京：科學(xué)出版社，1992.

[4] 郭嗣宗，陳剛. 信息科學(xué)中的軟計(jì)算方法[M]. 沈陽(yáng)：東北大學(xué)出版社，2001.

[5] 紀(jì)建春，楊晉，彭亮，左曉霞. 種群多樣度的改進(jìn)[J]. 太原理工大學(xué)學(xué)報(bào)，2009.

A New Way of Measuring Group Diversity

DUAN Yong-hong

This paper presents a definition of group diversity by referring to non-negative matrix theory, and compares common ways of measuring group diversities, which improves the flaws of group diversity to some degree, and provides a new way of judging group diversities.

diversity; non-negative matrix; irreducible

O151.21

A

1008-7427（2012）02-0156-02

2011-12-20