度量种群多样性的一种新方法

段永红

（太原大学外语师范学院 数学系，山西 太原 030012）

度量种群多样性的一种新方法

段永红

（太原大学外语师范学院 数学系，山西 太原 030012）

本文应用非负矩阵的知识提出了种群多样度的一种定义，并比较了常见衡量种群多样度的做法，在一定程度上改善了以往种群多样性的缺陷，为种群多样性的判断提供了一种新方法。

多样度；非负矩阵；不可约

遗传算法是受生物进化理论启发的搜索算法，是由Holland在19世纪70年代提出来的，而传统的遗传算法由于多样性问题的影响陷入早期收敛，导致的结果是算法陷入局部最优。遗传算法最重要的作用之一是维持种群的多样性，而遗传算法的研究结果告诉我们，增加种群的多样性有益于进化过程，遗传算法多样性需要解决的主要问题是在遗传进化中测定并调节种群多样性及其效果。

生物学中种群多样性指的是种群中不同个体也就是个体结构和行为的不同；遗传进化中，多样性往往指的是结构上的差异，在文[1]中，Landon将基因作为种群多样性的主要因素，其主要原因是在遗传计算中，两个结构相同的个体会在适值上都表现出同样的行为，因此，基因型多样性的降低通常能导致了群体行为多样性的下降。

我们知道，增强算法的性能依靠局部优秀的个体一般不能实现，通常它们还会降低样本的适应性。因此，一个优秀的进化群体应该表现出丰富的多样性。许多学者在种群多样性上进行了不断的研究，并给出了相应的测定方法，并通过这些测定方法来改善遗传算法的性能。

本文重点介绍种群多样性的一般性描述，同时给出种群多样性的定义，并在此基础上利用特殊矩阵的知识给出了一种衡量种群多样度的新方法。

1.从种群的不同个体角度度量种群多样性

在遗传算法中，我们一般用适应度函数来评价种群中个体的优劣程度。通常个体越好适应度越高，个体越差适应度越低。

在遗传算法的设计中，常常用到原始适应度函数和标准适应度函数这两种适应度函数。

其中，原始适应度函数是将问题的目标函数作为适应度函数，常常用于求解极大值问题。然而在许多现实问题中，求解目标往往需要的是求解某个函数的极小值，因而需要我们将其转化为极大值并且适应度值为非负。通常情况下它有以下三种转化形式：

上式中：x是一代种群，f( x)是适应值函数；μ(x)是问题的目标函数；Cmax可以是一个合适的输入值，也可以是 N代进化过程μ(x)的最大值或当前群体中μ(x)的最大值； Cmin可以是合适的输入值，或者当前一代或前N代中μ(x)的最小值。

遗传算法早期群体如果出现超级个体（适应度远远超过了群体平均适应度的个体）会由于在群体中出现过多的复制导致早熟收敛；然而在遗传算法的后期，如果群体平均适应度与最优实验值过于接近时，则会导致停滞现象。

处理遗传算法早熟和停滞问题最常办法就是变换适应度函数。

常用的适应度函数的比例变换方法有以下三种：

上式中：f′(x)是进行比例变换后的适应度函数；f( x)是未经变换的适应度函数；α，β是系数。

上述三种比例变换中，较为常用的是指数比例变换，它可以使得好的染色体串保持较多的复制机会，不但限制了其复制的数目而且避免其过快的控制整个群体。

选择的强制性由系数决定，系数值越小，选择强度就越趋向于那些适应度高的染色体串。度量适应度通常利用原始问题的目标函数，从计算量的角度来讲，运算量显得较大，且影响了遗传算法的执行速度。为此，本文将对进行二进制编码的群体进行种群多样性度量。

2.从基因的角度度量种群多样性

定义1[4]设X是规模为N的一代种群，其个体分别记为个体的字符长度都是L，其中种群 X可以用矩阵表示为：

用Dj表示矩阵X第j列元素和的函数，即

这就是说，若X的第j列元素完全相同，则Dj=1.称为种群的多样度。

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

按定义1多样度D( x)=4，然而事实上，种群x中4个个体有3个是相同的，种群基本上处于成熟状态，可见这个定义很不合适。

由于遗传算法GAS其过程主要是在0，1编码下进行的，所以定义1中矩阵X为非负矩阵，即X≥0，由特殊矩阵性质[8]可知，非负矩阵可分为可约和不可约两种，基于这个原因，这里给出一种种群多样度的新定义，其定义如下：

性质1 0＜D()x≤1

证明 因为0＜r≤L， 所以有0＜D()x≤1

性质2 当A为不可约非负矩阵时，D()x＝1

证明 A≥0，且不可约时，由不可约非负矩阵性质[8]可知，矩阵A为满秩矩阵，则r( A)=0,所以D(X)＝1

按定义1种群X的多样度D(X)=3，按定义2种群多样度 D(X)=1，这个结果与文献[5]提出的种群多样度的算法结果完全一致。

3 结论

利用特殊矩阵分析的相关知识提出了种群多样度的一种新定义，通过对比看到它能准确的反映种群的多样性。另一方面，非负矩阵理论通过著名的矩阵论专家 Braue A, Johnson C R, Varga R S, Ostrowski A等卓有建树的工作，已逐步形成比较完美的理论体系，因此，为种群多样度的衡量提供了理论支持。

[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.自适应控制[M]. 北京：科学出版社，1992.

[4] 郭嗣宗，陈刚. 信息科学中的软计算方法[M]. 沈阳：东北大学出版社，2001.

[5] 纪建春，杨晋，彭亮，左晓霞. 种群多样度的改进[J]. 太原理工大学学报，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