臭丫头,站住
分层遗传算法
2019-3-12 臭丫头,站住


对于一个问题,首先随机地生成N*n个样本(N>2,n>2),然后将它们分成N个了种群,每个子种群包含n样本,对每个子种群独立地运行各自的遗传算法,记它们为GAi(i=1,2,…N,)。这N个遗传算法最好在设置特性上有较大的差异,这样就可以为将来的高层遗传算法产生更多种类的优良模式。



在每个子种群的遗传算法运行到一定代数后,将N个遗传算法的结果种群记录到二维数组R[1…N,1…n]中,则R[i,j](i=1…N,j=1…n)表示GAi的结果种群平均适应值。高层遗传算法与普通遗传算法的操作相类似,也可分成如下三个步骤:



1. 选择



基于数组A[1…N],即N个遗传算法的平均适应度值,对数组R代表的结果种群进行选择操作,一些结果种群由于它们的平均适应度值高而被复制,甚至复制多次;另一些结果种群由于它们的种群平均适应值低而被淘汰。



2. 交叉



如果R[I,1…n]和R[j,1…n]被随机地匹配到一起,而且从位置x进行交叉(1《=I,j<=N;1<=x<=n-1),则 R[i,x+1,…n]和R[j,x+1,…n] 相互交换相应的部分。这一步骤相当于交换GAi和GAj中结果种群n-x个个体。



3. 变异



以很小的概率将少量的随机生成的新个体替换R[1…n,1…n]中随机抽取的个体。



至此,高层遗传算法的第一轮运行结束。N个遗传算法GAi(i=1,2,…,N)可以相应于新的R[1…N,1…n]种群继续各自的操作。



在N个GAi再次各运行到一定代数后,再次更新数组R[1…n,1…n]和A[1…N],并开始高层遗传的第二轮运行。如果继续循环操作,直到满意的结果.



上述改进的遗传算法,称为分层遗传算法(Hierarchic Genetic Algorithm,HGA)。N个低层遗传算法中的每一个在经过一段时间后均可获得位于个体串的一些特定位置的优良模式。通过高层遗传的操作,GAi(i=1,2,…N)可以获得包含不同种类的优良模式的新个体,从而它们提供了更加平等的竞争机会。这种改进的遗传算法与并行或分布遗传算法相比,在上一层的个体交换上,它不需要人为地控制应交换什么样的个体。这样必进的遗传算法不但在每个处理器上运行着遗传,同时对各处理器不断生成的新种群进行着高一层的运算和控制。





发表评论:
昵称

邮件地址 (选填)

个人主页 (选填)

内容