基于种群熵的改进型遗传算法

摘 要：本文针对遗传算法具有早熟或局部收敛的缺点，根据种群熵S的实际意义，设计了一种可按照当前种群熵S的大小自动切换适应度函数的自适应适应度函数。对基本遗传算法，分别采用指数适应度函数，反比例适应度函数和本文定义的自适应适应度函数，在三种常用检测函数上进行实验，结果表明采用自适应适应度函数的基本遗传算法继承了指数适应度函数和反比例适应度函数的优点，既有强劲的收敛能力，又能保持种群多样性，可以更好更快更精确地收敛到问题的最优解。

关键词：遗传算法 种群熵S 适应度函数

中文分类号： TP13 文献标识码：a DoI: 10.3969/j.issn.1003-6970.2012.02.039

A Improved Genetic Algorithm Based on Population Entropy

LIU li-fang1, MeNG zhi-gang2, ZHaNG Chang-li1(1.College of Information Engineering, Taiyuan University of Technology, Taiyuan 030024, China; 2.College of Electrical Engineering, XinjiangUniversity, 830046, China)

【Abstract】According to the practical meaning of population entropy S, this paper designs a self-adapting fitness function which could automatically select a proper fitness function according to the population entropy S now. The test conducts on three common test functions with SGA adopted exponential fitness function, inverse proportion fitness function and adaptive fitness function respectively shows that SGA with adaptive fitness function inherit the advantage of both exponential fitness function and inverse proportion fitness function, and not only could search the population robustly but also could hold the variety of the population, and gets a better, more rapid and more accurate convergence to the optional solution.

【Key words】genetic algorithm; population entropy S; fitness function

0 引 言

随着经济社会的迅猛发展, 人类科学研究与生产活动的广度与深度都得到极大拓展，面对这浩瀚深邃的探索领域，各种复杂庞大、非线性、不确定、建模复杂及难以解析描述的新型问题对信息与控制科学提出了前所未有的挑战。为迎接这种挑战，各种智能信息处理算法如雨后春笋般涌现出来。作为其中的重要一员, 遗传算法以其鲁棒性强、易于实现和效果好的独特性能引起了人们的广泛关注[1]。虽然GA在许多领域都有成功地应用，但其本身还存在一些不足，主要有：局部搜索能力弱、存在早熟现象、收敛结果不稳定和随机漫游或振荡等现象[8]，这些缺点降低了遗传算法寻优性能和可信度。为此，国内外许多学者一直不懈努力，提出了各种改善遗传算法寻优性能的方法。

本文针对遗传算法具有早熟或局部收敛的缺点及适应度函数在遗传算法搜索过程中的重要性，根据种群熵S的实际意义，定义了一种可按照当前种群熵S自动切换适应度函数的自适应适应度函数，并在三种常用的检测函数上进行了实验。

1 改进型遗传算法

遗传算法[2] (Genetic Algorithm，简称GA)是一种模拟自然界生物进化和遗传过程，具有极强鲁棒性的并行启发式的有导向的随机搜索优化算法，以其简易实用、适应性强，不需要专门领域知识的特点，在工程实践中得到广泛的应用。

它以模拟生物界“优胜劣汰，适者生存”的进化过程和交叉变异等遗传过程为指导思想，构造适应度函数计算种群中个体的适应度值，将待优化参数转换为相应编码以实现交叉或变异等遗传操作。其大致搜索过程为按个体适应度值及一系列遗传操作对各个体进行筛选,从而使适配值高的个体保留下来,组成新的群体,新群体包含了上一代的大量信息,并有优于上一代的个体。循环迭代,群体中个体适应度不断提高,直至满足一定停止条件就结束算法，群体中适应值最高的个体所对应解即为待优化问题的最优解或满意解。

针对遗传算法存在早熟和局部收敛等缺点，本文采用信息熵的思想对其进行了改进。

1.1 种群熵S及其阈值

本文在文献[3]定义的遗传算法种群熵的基础上，给出了如何根据种群熵S的值，来判断遗传算法出现早熟或局部收敛，并提供了一种可使遗传算法当前搜索跳出早熟或局部收敛的方法 ――自适应度函数。

种群熵S [3]：根据遗传算法中个体生存几率pi与其适应度f(xi)成正比，假设种群规模为N的遗传算法运行到第t代，并以事件Ai表示个体i生存下来，随机变量X表示试验结果(令Xt=i,表示事件Ai发生)，则第i个体生存下来的概率pti定义为

种群熵S的收敛判定定理[3] 若群体的熵值出现持续增大或保持不变时，则必定发生了成熟前收敛。

根据上述定理，可以通过检测种群熵S值的变化来发现种群是否出现了早熟或局部收敛。具体方法为：设定种群熵S的上限阈值θmax，当连续Ts代（视具体情况而定）都有S≥θmax时，则认为当前种群分布过于集中，出现了早熟或局部收敛。

1.2 自适应适应度函数

本文认为适应度函数对遗传算法的运行起着宏观调控的作用，是遗传操作进行的主要依据，影响着遗传算法的搜索方向，是遗传算法的瓶颈环节。为使搜索过程跳出早熟或局部收敛，本文采用了一种可根据当前种群熵S值自适应得选择适应度函数F(x)的方法，如下所示：

式中――α，β为调整参数，S为种群熵，γ为种群熵阈值，f(x)为实际函数值。

γ反映了当前种群的多样性，根据具体问题取值。当S≤γ时，说明当前种群多样性好，选择可以使个体适应度值区分度较大的指数适应度函数，以便种群迅速向优秀个体靠拢，加快种群的收敛速度；当γ≤S≤1时，说明当前种群多样性较差，选择使个体适应度值区分度较小的反比例适应度函数，以便维持种群基因的多样性，避免搜索形成早熟或局部收敛。

2 检测函数

2.1 三种常用检测函数

该函数是由K.A.DeJorlg设计得二维Rosenbrock连续单峰函数，其最小值f(1,1)=0位于一狭长抛物面的平坦凹处，这种病态特点使遗传算法极易形成早熟，而难以得到全局最小值。为此，它成为测试遗传算法是否可以跳出早熟及适应度函数是否具备极强区分能力的理想函数。2）检测函数2[5]：该函数为二维Schwefel连续函数，其最大值f(0,0)=3600位于搜索空间的中心，但在其周围有四个函数值为2748.78的局部极小值点。采用该测试函数可以检测算法的全局收敛性及其成功概率。

2.2 三种常用检测指标

本文以各文献通用的三种算法性能评价指标对基本遗传算法分别采用三种不同适应度函数在上述三个测试函数上进行了对照实验。这三种算法性能指标为：①收敛次数Ncon，本文取算法寻优值收敛到精确解的1%邻域范围即为收敛，这是算法的最基本要求，值越大说明算法性能越稳定可靠；②收敛成功率Psuc，算法成功收敛到全局最优解万分之一邻域范围的次数占总搜索次数的比例，值越大反映算法性能越好；③平均收敛代数Nave，本文将其与Ncon结合定义为当算法收敛到精确解的1%范围内的迭代次数。值越小说明算法收敛速度越快。

3 仿真结果

本文将采用不同适应度函数的基本遗传算法在上述三个测试函数上分别运行100次，进行了对照实验。每次实验基本遗传算法的主要控制参数依次为：最大迭代次数T=[100,100,100]，种群数size=[20,60,100]，种群熵阈值γ=[0.7,0.9,0.75]。实验结果如图1和表1所示。

表1 基本遗传算法在三种适应度函数上的实验结果

Tab.1 The experiment results of the simple genetic algorithm though the three different fitness functions

由图1可知，基本遗传算法采用指数适应度函数极易出现早熟或局部收敛，其种群熵S大约在前十代就超过0.9，并保持 不变；基本遗传算法采用反比例适应度函数虽不易出现早熟或局部收敛，但搜索过程极慢，其种群熵S大都会徘徊于相对较低的位置，不利于优秀个体的迅速繁衍；而基本遗传算法采用本文定义的自适应适应度函数则可扬长避短，继承了上述两者的优点，使得搜索过程既有强劲的收敛能力，又能保持种群个体的多样性，可以高效收敛于最优解。表2的实验数据，进一步验证了采用自适应适应度函数的基本遗传算法可以更好更快更精确地收敛到问题的最优解。

4 结 论

针对遗传算法具有早熟或局部收敛的缺点，本文根据种群熵的实际意义，设计了一种可按照当前种群熵的大小自动切换适应度函数的自适应适应度函数。对基本遗传算法，分别采用指数适应度函数，反比例适应度函数和本文定义的自适应适应度函数，在三种常用检测函数上进行实验，结果表明采用自适应适应度函数的基本遗传算法继承了指数适应度函数和反比例适应度函数的优点，既有强劲的收敛能力，又能保持种群多样性，可以更好更快更精确地收敛到问题的最优解。

参考文献

[1] 王小平，曹立明.遗传算法―理论、应用与软件实现[M].西安：西安交通大学出版社，2002：11-29.

[2] 张常利.基于均匀设计和熵的遗传算法及其在线性控制系统中的应用 [D].太原：太原理工大学，2011.

[3] 郝翔，李人厚.基于信息熵的自适应遗传算法[J].西安建筑科技大学学报，1997，29（1）：34-38.

[4] Ke-Zong Tang, Ting-Kai Sun, Jing-Yu Yang.An improved genetic algorithm based on a novel selection strategy for nonlinear programming problems[OL]. Computers and Chemical Engineering(2010),doi:10.省略pchemeng.2010.06.014.

[5] Kusum Deep, Manoj Thakur.A new crossover operator for real coded genetic algorithms[J].Applied Mathematics and Computation,2007,188:895-911.