2 遗传算法种群多样性的分析研究

第

卷第期年月

控制理论与应用!

,

,

遗传算法种群多样性的分析研究张晓绩

‘

戴冠中

徐乃平西安,

西北工业大学自动控制系

摘要

种群的多样性是遗传算法进化的前提条件本文提出用种群方差和嫡两个量来全面刻,、

画遗传算法中种群的多样性分析了选择交换和变异三个主要算子对种群方差和嫡的影响同时,

比较了编码机制对种群多样性的影响得出了一些重要的结论

关键词

遗传算法

选择操作

交换操作

变异操作

种群多样性

引

言,

红年来虽然遗传算法得到了广泛的应用并取得了一定的成果但目前没有完整的理论解

释算法的机理阻碍了遗传算法的应用甚至引起了部分人的怀疑提出的图式定理是遗传算法的主要理论但图式定理只揭示了种群平均适应值的进化情况对种群中个体的分布情况并未给出信息我们知道种群只有在保持一定的多样性的情况下才能进化那么种群的多样性用什么来度量又有什么样的影响,,,、

,

,

,

选择交换和变异操作对种群的多样性这些问题对进一步理解遗传算法是

编码机制对种群多样性有什么影响

很重要的这也是本文要解决的问题

种群多样性的表示我们可以从两方面来理解种群的多样性一是种群的空间分布显然从这个意义上来看种群的空间分布越大种群的多样性就越强因此我们用方差来描述种群的空间分布情况,

,

,

,

,

定义…,,

若第

代种群中的个体川由厉,

个基因构成即川一厉

,

尸,

尸…

,

二

产〕

,

,

,

,

定义第

代种群的平均个体牙,

如下厉‘,

一,

挤

,

…

厉

,

」

其中习

一

艺

洲

,

由此定义第,

代种群的方差为

「尸‘任,

’

…,

,

〕

其中

‘,

一

艺

二

“

一

‘,

“

,

…

,

从定义间分布显然

可以看出方差,

,

是

维的行向量每一个分量表示出了种群在这维坐标上的空

,

贷越大则种群在第

维坐标上的空间分布就越大,

方差仅反映出了种群的空间偏离程度还不能完全刻画出种群的多样性例如种群,,

,

,

,

由五个个体构成显然,

,

一

而种群,

,

,

,

,

,

方差

一

虽然后者比前者的

方差大但前者比后者更具有进化能力为此我们引入描述种群多样性的第二个量定义,,,,

若第…,,

代种群有。,

个子集凡凡,

,

,

…凡,

,

。

,

—各个子集所包含的个体数目记为,、,

嫡

且对任意

宁

任

,

,

…

,

,

,

门

司

一

,

,

‘

为第代种群

国家自然科学基金重大项目资助课题本文于

!

。

年

月

日收到

年

月

日收到修改稿

控制理论与应用

卷

的集合

则定义第

代种群的墒如下

一‘

万户

,

户

,

其中’

,

厂

一

止

夭粤

止

,’一’

二为种群中个体数目曰,’一

‘

,

‘

”’

‘

’

一

’

定义

告诉我们两点一是当种群中所有个体都相同时即,

,

一

,

这时嫡取最小值,,

一

第二点是当大,

一

时嫡取最大值,

,

一

种群中个体类型越多分配得越平均嫡就越

对于十进制编码嫡的最大值为

盆一

、

对二进制编码嫡的最大值为

盘

、

如果种群的方差和嫡都很大种群的情况如图

,

所示一般初始种群就是这个样子种群的方差很,

,

当种群的方差很大嫡很小时如图,,

,

,

所示,

,

种群收敛于几个分散的点上所示

小嫡很大时种群集中在一个很小的区域内如图

种群的方差和嫡都很小时种

群收敛如图

,

所示经过很多代进化后种群处于这种状态

,

,

套

图

种群多样性与方差和嫡的关系

遗传算子对种群方差的影响选择操作对种群方差的影响遗传算法的选择操作可以描述为从个体对对…概率尸‘,

,

,

二

介中选择出个体城是适应函数〔,,,

‘,

斌

,

…

,

入

,

满足

一

川对…

,

,

二

灼一

二,

艺一

衬

,

这里,

习

在「〕中得出种群数目无穷情况下选择操作对种群的概率密度函数

的

影响为,

了

川其中,

二

关仁

’

「

表示数学期望

,

!,,

还证明了当

。时种群概率密度函数

,

‘

收敛于冲

激函数、

占

劣

一

‘

这里

,

‘

是初始种群中适应值最好的个体种群数目为无穷在只有选择操作作用下有,,,

定理

证定理

由

式显然定理

成立,,

虽然说明了种群数目为无穷时方差收敛 …… 此处隐藏：7302字，全部文档内容请下载后查看。喜欢就下载吧 ……