2022年遗传算法之我见 .pdf

《2022年遗传算法之我见 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算法之我见 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、随机化均匀设计遗传算法摘要 ：众所周知，遗传算法的运行机理及特点是具有定向制导的随机搜索技术，其定向制导的原则是：导向以高适应度模式为祖先的“家族”方向以此结论为基础利用随机化均匀设计的理论和方法，对遗传算法中的交叉操作进行了重新设计，给出了一个新的 GA 算法，称之为随机化均匀设计遗传算法最后将随机化均匀设计遗传算法应用于求解函数优化问题，并与简单遗传算法和佳点集遗传算法进行比较通过模拟比较，可以看出新的算法不但提高了算法的速度和精度，而且避免了其它方法常有的早期收敛现象。关键词：遗传算法 (GA) 佳点集理论佳点集遗传算法 (GGA) 随机化均匀设计(RUD) 随机化均匀设计遗传算引言20

2、世纪60年代，美国 Michigan 大学的 John Holland 教授提出了模拟生物进化的仿生智能算法，即遗传算法(Genetic Algorithms ，GA)其基本原理是模仿生物在进化过程中，通过选择淘汰基因突变和遗传等方式产生适应环境变化的优良个体遗传算法以其简单易行性和可靠性，在组合优化问题，机器学习问题，图像处理与模式识别， 通信网络设计等很多领域取得了广泛的应用遗传算法通过适当的编码方式把实际问题转化成生物种群的进化问题，经过多代的选择， 变异，交叉操作最终得到可接受的问题的解算法中“选择，变异，交叉”等操作直接关系遗传算法的效率，一直是遗传算法的研究热点文献1 根据算法初期

3、需要采用较大的交叉， 变异概率来产生更多的新优秀个体；算法后期， 则需采用较小的交叉， 变异概率来保护优良模式， 使算法尽快收敛 提出了自适应遗传算法，由条件发生器来自适应调整交叉变异概率，提高算法的效率文献2 为了改善遗传搜索性能， 通过分析基因池遗传算法的无限种群动力系统，刻画了双峰函数局部极值解的适值差与系统不动点之间的解析关系，提出了针对多模态优化问题的两阶段遗传算法文献3 提出了一种结合模拟退火，最优个体迁移以及参数空间动态退化的混合遗传算法， 来加快算法的收敛和提高搜索全局最优值的能力文献 4 提出了量子遗传算法，在量子个体上实施量子杂交，这一操作有利于保留相对较好的基因段， 并且

4、为了加快算法的收敛速度， 还引入了两阶段局部搜索 . 文献5 指出遗传算法的本质是一个具有定向制导的随机搜索技术，其定向制导的原则是：导向以高适应度模式为祖先的“家族”方向而在高适应度模式为祖先的“家族”中寻找更高的适应度模式主要靠交叉操作来实现名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - 1. 遗传算法交叉操作分析通常GA 算法中的交叉操作， 是按赌轮法随机取两个染色体进行单点交叉操作( 或多点交叉 )，其子孙必属于父辈模式

5、中， 所以GA 算法中的交叉操作即在以高适应度模式为祖先的 “家族”中取一点作为交叉后的后代这种取法当然有其片面性，并不能保证取到的后代的适应度比母体的高由数论方法知： 在高适应度模式空间中产生的均匀散布点集， 它们的平均适应度能代表高适应度模式空间的平均适应度 也就是说， 这些点能很好的代表高适应度模式空间的其他点，即要求此空间中的最优值， 只要在这些点中找即可 故有研究者提出在以高适应度模式为祖先的“家族”中利用正交试验的方法求出几点来作为交叉后的后代，这是一个好主意， 不过当因素的个数和等级增多时，不但试验的规模迅速增加， 而且对应的试验正交表也很难得到， 这些问题给正交交叉法的运用带来

6、一定的困难张铃提出了佳点集遗传算法， 即利用数论中的佳点集方法求出几点来作为交叉后的后代，这可使其精度与维数无关， 且这些点有很好的散布性， 克服了用正交设计法的不足 但是，佳点集的选取在 n取定后是确定的， 且佳点集分布点有方向性，不带随机性，所以很多格子是取不到的， 其上的点也就不能作为交叉后的后代了，这将影响算法的整体搜索效果 为了克服上述不足， 本文提出了随机化均匀设计遗传算法， 利用随机化均匀设计来设计一个新的交叉算法，提高GA 的效率实验证明不管在求解精度上还是在求解速度上，随机化均匀设计遗传算法不仅优于GA ，也优于佳点集遗传算法2. 佳点集遗传算法设在传统的 GA 算法基础上

7、, 在进行过复制后 , 对池中的元素按赌轮法选择两个元素 A1, A2进行佳点交叉操作不妨设 A1与A2的前t 个分量不同 , 后L- t 个分量相同由A1与A2进行交叉 (不管是单点交叉或是多点交叉), 其子孙必属于 H , 于是要在“高适应度模式为祖先的家族方向” 上搜索出更好的样本 , 就是要在 H中搜索出更好的样本来 . 现在我们要在 H 上利用佳点集方法求出好样本来, 其方法是 : 将H 的前t 个分量看成一个 t 维的立方体 ( 仍记为 H ), 然后在H 上求佳点集 . 或将H 的每d 个分量分成一组 ( 不妨设共分成 s组), 每组表示一个实数 , 于是s个组就表示s 个实数

8、, 这样就将 H 变换成一个 s 维的实空间 , 可将其归一化变换成一个s 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 维的单位立方体 , 然后在其上求佳点集 . 如(1,1,0,0,1,0,1,0,1,1,0,1)是12 维二进制单位立方体中的一点, 我们可以将它化成三维的实值空间的点( 每4个分量合成一个实数 ) (1100,1010,1101)=(12,10,13);再将它归一化 , 得点(12/16,10/16,13

9、/16)=(3/4,5/8,13/16),即为实单位立方体中的一点, t 维的单位立方体 . 取定后 , 下面就是如何取佳点集的问题: 在t 维空间中取佳点的方法如下: 在t 维空间H 中作含 n个点的佳点集 ( 当H 是二进制立方体时 ) 其中p是满足 p =2t + 3的最小素数 , 或 a 表示a 的小数部分 . 令交叉后产生的 n 个后代中第 k 个染色体 , 其中：其中 a 表示 , 若a 的小数部分小于 0.5, 则a = 0; 否则 a = 1 这样在其 “家族”中产生出 n 个后代 , 取其中适应值最大者 ( 或最大的几个 ) , 作为交叉后的后代，上述的交叉操作, 称为佳点集

10、交叉操作。给定交叉概率 pc和突变概率 pm , 佳点集遗传算法 (GA ) 如下: (1) 每次进行遗传操作 , 以概率复制Ai, 其中fi是Ai 的适应度值(2) 以赌轮法随机取两个染色体, 对其进行佳点集交叉(3) 以概率 pm 进行变异遗传操作 . (4) 把经过遗传操作后得到的染色体都放到染色体池中, 对新得到的染色体 , 计算其适应度值。若假定染色体的容量一定 , 当染色体的个体超过容量时, 就将适应度小的染色体从池中删去( 或按a% 进行删除 ) (5) 进行上述的遗传算法至第T 代后(T是预先给定的常数 ), 在第T 代的染色体中取适应度最大的染色体, 即为所求的染色体。当H是

11、s维实单位立方体时 , 即将t 维的二进位数分成 s组, 设各组的位数分别为d1, d2, ?, ds. 在H 中取佳点集名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 其中p是满足 p =2t + 3的最小素数 , 或令交叉后产生的 n 个后代中第 k 个染色体 , 其中：其中a 表示取 a 的小数部分乘上，再取其整数部分 , 最后将整数部分表示成二进制 , 所得到的数为 a 。如：设j =2,d2=4,r 2=3.67, k

12、=5, 则r 2k为3.675= 18.35 ( 取小数部分 ) 0.35, ( 乘) =5.6, ( 取整) 5, ( 表示成二进制 ) 0101, 最后得= (0101) 。3. 随机化均匀设计3.1 随机化均匀设计方法 : (1) 对于固定的 t 和n N，选取均匀设计的生成向量(n：h1，h2，? ，ht) ；(2) 从多项分布中抽取 t 一1个样本, 并令=0；(3) 令Xk=(Xkl,Xk2, ?,Xkt) ，k=1,2, ?,n 其中x 表示取 X的小数部分，称这样所得到的点集为随机化均匀设计点集。称这种方法为随机化均匀设计(Random Uniform Design(RUD)

13、方法，若，k=1，? ，n，j=1 ，? ，t ，其中 x 表示取 x的小数部分，则称点集为均匀设计点集。实际上，这种随机化均匀设计是通过对均匀设计( 即(4) 式中的)进行模 1随机平移而得到的这种平移总共有个，而每组样本点个数为n，这样正好将全体个格子都以同等机会抽到，因此，它具有较好的搜索能力，而名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 且由下面 3.2 可见每组点集都具有良好的散布均匀性。3.2 随机化均匀设计的性

14、质首先介绍几个基本概念和记号：为Pn的偏差 ( 用来衡量点集 Pn的均匀散布性 )，其中I(*)为示性函数， d=(dl ，d2，? ,dt)，Pkd 意味着对所有的 i 均有ai(k)di ，i=1 ，2，? ，t 引理1设An为由(4) 式给出的均匀设计点集，则当n为素数时，其偏差满足下式定理1设xk为由(3) 式给出的随机化均匀设计点集，则其偏差满足下式定理l 说明：随机化均匀设计点集的偏差比佳点集小，并且它能随机地取到所有的格子，所以搜索能力更强，故能比佳点集有更好的表现。4. 随机化均匀设计遗传算法设在传统的 GA 算法基础上 , 在进行过复制后 , 对池中的元素按赌轮法选择两个元素

15、 A1, A2进行佳点交叉操作不妨设 A1与A2的前t 个分量不同 , 后L- t 个分量相同由 A1，A2进行交叉 (不管是单点交叉或是多点交叉) 其子孙必属于 H，于是要在“高适应度模式为祖先的家族方向”上搜索出更好的样本，就是要在H中搜索出更好的样本随机化均匀设计交叉操作就是要在H上利用随机化均匀设计方法找出好样本来、其具体方法是：(1) 对于固定的 t 和n N，选取均匀设计的生成向量(n：h1，h2，? ，ht) ；(2) 从多项分布中抽取 t 一1个样本, 并令=0；(3) 令Xk=(Xkl,Xk2, ?,Xkt) ，k=1,2, ?,n 名师资料总结 - - -精品资料欢迎下载

16、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 其中x 表示取 X的小数部分，称这样所得到的点集(4) 令交叉后产生的 n个后代中第 k个染色体为，其中表示，若a的小数部分小于 0.5 ，则=0；否则=1。这样在其“家族”中，产生n个后代，取其中适应值最大者(或最大的几个 ) ，作为交叉后的后代。给定交叉概率 Pc和变异概率 Pm 后，随机化均匀设计遗传算法如下：(1) 每次进行遗传操作，以概率复制A，其中 fi 是Ai的适应度值(2) 随机取两个染色体，以概率Pc对其

17、进行随机化均匀设计交叉操作( 产生n个后代，n为待定参数 ) (3) 以概率 Pm 进行变异遗传操作(4) 把经过遗传操作后得到的染色体都放到染色体池中，对新得到的染色体，计算其适应度值若假定染色体的容量一定，当染色体的个体超过容量时，就将适应度小的染色体从池中删除(或按a进行删除 ) (5) 进行上述的遗传算法至第T代后(T是预先给定的常数 ), 在算法执行过程中记录适应度最大的染色体，即为所求的染色体，再进行解码得到最优解5. 随机化均匀设计遗传算法的测试5.1 实验分析在P4 3.0G PC 机器上，在 Matlab7.0 计算平台上，利用遗传算法工具箱中“简单遗传算法”，文献 5 中的

18、“佳点集遗传算法”和这里的“随机化均匀设计遗传算法”按文献 5 中提供的 5个函数进行了计算比较。 计算中参数为： 种群规模为100，最大迭代代数为 150，交叉概率为 0.85 ，变异概率取 0.05 ，每个执行 100次。测试函数：1. 0=x=1 2. 0=x=1 3. 0=x=1 4. -5=x1=10 0=x2=15 5.-100=x1x2=100 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - 由上面测试函数的结果得

19、知：不管在求解精度上，还是在求解速度上，随机化均匀设计遗传算法比简单遗传算法和佳点集遗传算法的性能都要好得多，并能成功地避免“早熟”现象。结论本文改进了遗传算法中的交叉操作，我们根据遗传算法的机理( 遗传算法是一个具有定向制导的随机搜索技术，其定向制导的原则是： 导向以高适应度模式为祖先的“家族”方向 ) 可知，任何一种交叉操作都无非是在以其父代为“祖先”的“家族”中寻找一个适应度值高的后代现有的交叉算法( 如单点交叉，多点交叉，树交叉等 )都只能保证求到的后代落在上述家族中，而无法保证所求到的后代的适应度值较高； 佳点集法利用求得的子集的均匀散布性，使它们能较好代表其“家族”性能的普遍性，

20、所以佳点集遗传算法构造的交叉操作提高了搜索适应度值高的后代的能力，但佳点集布点有方向性，并且当n取定后是确定的，不带随机性， 这导致了其无法搜索到所有的格子，整体搜索能力仍不够强 随机化均匀设计方法就克服了上述不足， 随机化均匀设计方法所得的样本具有比佳点集更好的均匀散布性， 并且每次取得的样本集是随机均匀散布的，它们可以以同等概率取到所有的格子所以随机化均匀设计遗传算法具有极强的整体搜索能力从以上实验结果也可看出不管在求解精度上还是在求解速度上，随机化均匀设计遗传算法不仅优于 GA ，也优于佳点集遗传算法， 并能较好地避免早熟现象， 收敛到最优解。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -