1、PDF外文：http:/ 1 中文 4197 字 出处： Li M, Cai Z, Sun G. An adaptive genetic algorithm with diversity-guided mutation and its global convergence propertyJ. Journal of Central South University of Technology, 2004, 11(3): 323-327. 具有基于多样性的变异因子的自适应遗传算法及其全局收敛性 摘要 本文提出了一种具有基于多样性的变异 因子的自
2、适应遗传算法（ AGADM），它混合了具有自适应交叉率和变异率的遗传因子。通过均匀有限马尔科夫链，本文证明了在有最优解的情况下， AGADM 和具有基于多样性的变异因子的遗传算法（ GADM）能够收敛到全局最优解，研究了具有自适应交叉率和变异率的自适应遗传算法的收敛性，并且就上述几种算法在解决单峰函数和多峰函数最优化问题的结果进行了比较。结果表明：对于多峰函数，AGADM 的平均收敛代数是 900，少于具有自适应概率的自适应遗传算法和具有基于多样性的自适应遗传算法。 AGADM 能够避免早熟现象的发生，能够平衡早熟 发生和收敛速度的矛盾。 1 引言 &n
3、bsp; 众所周知，遗传算法的好坏依赖于所采用的遗传因子，改善遗传因子的自适应性是提高遗传算法性能的有效途径，例如：取得更好的最优解，提高收敛速度等。因此，一些研究者尝试根据解的情况自适应的调整遗传因子 1-3。同时，早熟是遗传算法的一个主要问题，自适应的遗传算法容易导致早熟的发生 4。为了克服早熟，我们引入多样性的概念。多样性对遗传算法的性能有很多的影响，特别在避免早熟和陷入局部最优解方面。一些研究者 5-8用种群的多样性来控制进化算法的搜索方向。 通过混合 Srnivas 提出的自适应交叉和变异因子和基于多样性的变异因子，本文提出了一种具有基于多样性的变异因子的自适应遗传算法（
4、 AGADM） ,并且用均匀有限马尔科夫链证明了，当存在最优解的情况下， AGADM 和具有基于多样性的变异因子的遗传算法 (GADM)。但是具有自适应交叉率和变异率的自适应遗传算法（ AGA）不总式收敛于全局最优解。最后，比较了 AGA， GADM 和 AGADM 的性能 。 2 主要内容 遗传算法过去常被用来解决静态优化问题。假设种群中有 N 个个体（候选解），我们用固定长度为 l 的二进制串来表示每个个体：1 2.i i ilg g g，（ijg=0， 1， j=1，2， .,l,i=1,2,N ） ,适应度值表示为 |0iiff ，
5、i=1,2,N . 定义 1 设tz是一个随机变量的序列，它代表状态为 i 的种群进化到第 t 代时，种群中个体的最佳适应度值， *f 是全局最优解。假如*li m ( ) 1tx p z f ，那么认为遗传算法能够收敛到全局最优解。 2 在执行遗传算法时，假如种群中的最佳适应度值在genN代中没有改进，就认为算法结束，这常被用来当做算法收敛的判断条件。收敛速度是遗传算法达到收敛条件之前 运行的代数（收敛代数）。本文中，在 15 维函数的优化问题中设 genN =300，在 2 维函数的优化问题中设 genN =50. 定义 2 对于方阵 A
6、=,()i j n na （ 1） 假如,ija 0， , 1, ., i j n ，那么 A 为非负矩阵（ A 0）； （ 2） 假如,ija>0， , 1, ., i j n ，那么 A 为正定矩阵。 对于非负矩阵 A： （ 1） 假如存在 k>0 使得 kA >0，那么 A 为原始矩阵； （ 2） 假如,1nijj a=1， , 1, ., i j n ，那么称 A 为随机矩阵。 假如一个随机矩阵的每一列至少有一个正值，那么我们称随机矩
7、阵式列允许的。 引理 19 设 C,M 和 S 式随机矩阵，其中 M 是正定矩阵， S 是列允许的，那么 CMS 式正定矩阵。 定理 1 设 C， M,aM和 S 式随机矩阵，假如 M 是正定矩阵， S 是列允许的，aM式 对角线正定矩阵，那么 P=CMaMS 是正定矩阵。 证明： M=,()i j n nm ，aM=,()i j n np ，0M=MaM=,()i j n nu . 因为 M 是正定矩阵， 那么有, , , , ,1 0ni j i k k j i j
8、 i jku m p m p （其中0S,0M 是正定矩阵） 因为随机矩阵的乘积还是随机矩阵。 根据引理 1 知， P（ P=CMaMS=C0MS）是正定矩阵。 定理得证。 3 改进的自适应遗传算法 AGADM 具有 基于多样性的变异因子和自适应的交叉 概率和变 异概率 的改进遗传算法（算法1） 可以描述为 ： 开始 3 选择初始种群； &
9、nbsp; 计算每个个体的适应度值； 执行选择； Do 执行具有自适应概率的交叉因子； 执行基于多样性的变异因子； 执行具有自适应概率的变异因子； 计算每个个体的适应度值； 执行选择； unitil 某个终止条件满足 本文以后称算法 1 为具有基于多样性的变异因子的自适应遗传算法。在算法 1 中，“执行基于多样性的变异因子” （算法 2） 可以描述为： &n
10、bsp;开始 计算种群的多样性 d； If（ d<1）执行变异率为5k的变异因子； Else if（ d<2） 执行变异率为6k的变异因子； Else 执行变异率为7k的变异因子。 结束 算法 2 中， 0<1<2<1,0<6k<5k<1,>
11、;0 且无限接近于 0. 算法 1 中，种群中个体的自适应交叉率和变异率记为 ( , )cp i j和 ()mpi，它们由当前种群中个体的适应度决定 。 Srinivas 提出的计算 ( , )cp i j和 ()mpi的方法如下： ''m a x1m a x'2,( , ),a v ga v gca v gffk f fffp i jk f f (2)
12、; m a x3m a x4,(),a v ga v gma v gffk f fffpik f f (3) 其中 0<1k<2k 1,0<3k<4k<1,maxf和avgf为种群的最大适应度值和平均适应度值， 'f 是执行交叉的两个个体 i 和 j 中适应度值的较大值， f 是执行变异的个体 i 的适应度值 。 ZONG et al2,3通过修改公式 （ 2） 和 (3)改进了 Srinvas 的自适应遗传算法。 他们提出的算法虽然可以 提高收敛速度，但是还存在一些缺陷：
