基于云遗传算法的函数优化

摘要：遗传算法是基于进化理论，并采用遗传结合、遗传变异及自然选择等设计方法的优化技术。遗传算法中交叉概率和变异概率的选择是影响遗传算法行为和性能的关键所在，直接影响算法的收敛性。该文结合正态云模型云滴的随机性和稳定倾向性，由X条件云发生器产生自适应交叉概率和变异概率。函数优化实验结果表明，云遗传算法只需要较少的进化代数就可以收敛，收敛速度明显快于标准遗传算法。

关键词：云模型；遗传算法；函数优化；交叉；变异

中图分类号：TP18 文献标识码：A文章编号：1009-3044(2011)28-6951-03

The Function Optimization Based on Cloud Genetic Algorithm

WU Li-feng

(Department of Computer Science and Technology, SCUFN, Wuhan 430074, China)

Abstract: Genetic algorithm is an optimization technology which is based on the theory of evolution, and using design method of the genetic combination, genetic mutation and natural selection. The selection of Genetic algorithm’s crossover probability and mutation probability are the key which is influenced the behavior and performance of genetic algorithm, directly affects the convergence of the algorithm. This paper combines the normal cloud model cloud droplets of randomness and stable tendency, by X condition cloud generator to generate adaptive crossover probability and mutation probability. Function optimization experiments show that, the cloud genetic algorithm convergence requires fewer generations, convergence rate is faster than the standard genetic algorithm.

Key words: cloud model; genetic algorithm; function optimization; crossover; mutation

遗传算法（Genetic Algorithm，缩写为 GA）是Holland教授首先提出来的一种借鉴生物界自然选择和遗传原理的随机优化搜索策略，一种高度并行、随机和自适应的仿生型优化算法，具有全局搜索能力，鲁棒性强等特点[1]。因此，遗传算法广泛用于组合优化、机器学习、自适应控制、规划设计和神经网络等领域，是21世纪有关智能计算中的关键技术之一。函数优化（Function Optimization）是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例，可以用各种各样的函数来验证遗传算法的性能。

1 函数优化问题

对于一个求函数最大值的优化问题（求函数最小值也类同），一般可以描述为下列数学规划模型：

式中x为决策变量，式1-1为目标函数式，式1-2、1-3为约束条件，U是基本空间，R是U的子集。满足约束条件的解X称为可行解，集合R表示所有满足约束条件的解所组成的集合，称为可行解集合。

2 云模型

云模型是定性定量间的不确定性转移模型，它用期望值Ex、熵En和超熵He表征定性概念，将概念的模糊性和随机性集成在一起，为定性与定量相结合的信息处理提供了有力手段[2]。期望值Ex 反应了云层的重心位置；熵En反应了云层的陡峭程度，En越小越陡峭；超熵He反应了云层的厚度，He越大云层越厚，正态云模型的三个数字特征示意图如图1所示。图1表示当x=Ex时其确定度为1，当x>Ex时，确定度随着x的增大而减小。要使遗传算法的收敛速度加快，不易陷入局部极小，得到正确的结果，必须使适度值小的个体有较大的交叉概率和变异概率，适度值大的个体有相对较小的交叉概率和变异概率。 从图1可以看出当x>Ex时云模型具有这一特点，可以将x作为遗传算法中两交叉个体的最大适应度以及变异个体的适应度，确定度作为交叉概率和变异概率，并且云模型中云滴集中在区间[Ex-3En,Ex+3En]，云层厚度为He，具有很好的随机性和稳定倾向性。

3 遗传算法求解过程

遗传算法是一个迭代过程，在每次迭代中都保留一组候选解。并按某种原则从中选出一些解，利用一些遗传算子对其进行运算，产生新一代的一组候选解，重复此过程，直至满足某种收敛条件，具体过程如下：

1）初始化：根据求解问题选择合适的编码，随机生成M个个体作为初始群体。

2）个体评价：计算群体中各个个体的适应度。

3）选择运算：选择操作建立在群体中个体的适应度评估基础上，将选择算子作用于群体。选择的目的是将优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。

4）交叉运算：交叉算子选择两个不同个体的染色体的部分基因进行交换，形成新个体。该算子确定和扩充解空间，是一个随机化的重组算子，在很大程度上，遗传算法的性能取决于所使用的交换算子的性能。

5）变异运算：变异算子对某些个体的某些基因进行变异，自爱通常的二进制编码方式下，变异操作就是简单地将基因值取反（1变0或者0变1）[3]。

群体经过选择、交叉、变异运算之后得到下一代群体。

6）终止条件判断：达到最大进化代数或者收敛，则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。其具体算法流程如图2所示。

4 函数优化实验原理及结果

设优化问题的目标函数为：式中x的取值范围是1～31，求f（x）的最大值。

4.1 初始化编码

遗传算法的第一步是将x编码为有限长度的串，针对本例中自变量的定义域，考虑采用二进制数来对二编码，恰好可用5位二进制数来表示，例如01001对应x=9，11111对应x=31[4]。

4.2 选择

为了克服适应度比例法的选择误差，即适应度高的个体也存在淘汰的可能。因此，提出根据每个个体在下一代群体中的生存期望值进行随机选择，其过程如下：

1）计算群体中每个个体Ai在下一代群体中的生存期望数目Mi：

，该式中，N表示群体中个体的数量；f(Ai)表示个体Ai的适应度。

2）若某个个体被选择参与交叉，则它在下一代中的生存期望数目减去0.5，若不参与交叉，则该个体的生存期望数目减去1。

3）若个体的生存期望数目小于0，则不参与选择。

4.3 交叉

交叉将染色体的基因进行互换，从而产生新的后代，本文采用单点交叉：随机选取某个基因位，从此位开始交换两父本后面的序列，相应地产生两个后代，实例如下：

父本1：α1, α2, α3, α4, α5, α6, α7, α8

父本2：β1, β2, β3, β4, β5, β6, β7, β8

子代1：α1, α2, α3, α4, β5, β6, β7, β8

子代2：β1, β2, β3, β4, α5, α6, α7, α8

交叉概率pc [5]由云模型产生，公式如下：

4.4 变异

变异的情况是遗传算法的三个主要操作之一，符合生物进化的规律，只有通过变异才能更好的丰富生物多样性。

变异作用在单个染色体上，并且产生一个不同于父本的染色体，变异方式有多种，本文采用简单变异：简单变异又称为点变异或二进制变异，一个个体中任一位按某一概率pm进行取反运算，即1变0或0变1。示例如下：

个体：10110011 新个体：10010011

第三位由1变为0。

变异概率pm公式[5]如下：

交叉概率和变异概率中的f为群体的平均适应度，fmax为群体的最大适应度，f为变异个体的适应度，f'为两交叉个体中的最大适应度值，ci(i=1,2)和k为控制参数，c1用来控制云的陡峭程度，根据“3En”规则，一般取3附近的值，c2用来控制云层的厚度，一般取10附近的值；k可取0.95~1之间的常数。

4.5 适应度函数

函数本身的值。

4.6 实验结果

在编码方案、选择算子、交叉算子、变异算子、适应度函数相同的情况下，分别用固定的交叉概率和变异概率即标准的遗传算法以及自适应的交叉概率和变异概率即云遗传算法连续运行程序10次。10次实验的进化代数与收敛值对比结果如表1所示。通过表1可以看出，10次实验中标准遗传算法以及云遗传算法全部都收敛，都是8次收敛于全局极大值100，2次收敛到局部极值，在收敛次数以及极值上是相同的。但是，云遗传算法的进化代数明显少于标准遗传算法的进化代数，收敛速度快。

5 结束语

交叉概率越大，新个体产生的速度就越快。然而，当交叉概率过大时，遗传模式被破坏的可能性也越大，使得具有高适应度的个体结构很快就会被破坏；但是如果交叉概率过小，会使搜索过程缓慢，以至停滞不前。对于变异概率，如果变异概率过小，就不易产生新的个体结构；如果变异概率取值过大，那么遗传算法变成了纯粹的随机搜索算法。由X条件云发生器产生改进的自适应交叉概率和变异概率，能够使适应度大的采用小的交叉或变异概率，适应度小的采用大的交叉或变异概率，选择自适应的交叉概率和变异概率，可以使群体平均拟合和最优模式拟合都能较迅速地改进，快速收敛。

参考文献：

[1] 韩红燕,潘全科,任文娟,张凤荣.基于遗传和声算法求解函数优化问题[J].计算机应用研究,2010,27(5):1723-1725.

[2] 刘常昱,李德毅,杜o等.正态云模型的统计分析[J].信息与控制,2005,34(2):236-239.

[3] 张云涛,龚玲.数据挖掘原理与技术[M].北京：电子工业出版社,2004:123-157.

[4] 杨建刚.人工神经网络实用教程[M].杭州：浙江大学出版社,2001:148-157.

[5] Zhu Yunfang, Dai Chaohua, Chen Weirong, Lin Jianhui.Adaptive probabilities of crossover and mutation in genetic algorithms based on cloud generators[J].Journal of Computational Information Systems,2005,1(4):671-678.