探讨单亲遗传算法理论及其应用

《探讨单亲遗传算法理论及其应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、探讨单亲遗传算法理论及其应用-->探讨单亲遗传算法理论及其应用——代写硕士论文Abstract:insolvingbinatorialoptimizationproblems,thereisaclassofproblemstousetheserialnumbercodingGAoperation,butusingthetraditionalGAalgorithmofplicatedoperation,putationalefficiencyisnothigh.X,顺序交叉OX,循环交叉CX等特殊的交叉算子[

2、2],但这些交叉算子遗传操作过程复杂,计算效率不高,且缺乏理论基础,这极大地限制了序号编码GA的推广应用.文献[1]中提出了一种基于序号编码GA的单亲遗传算法(PGA).PGA是专门针对组合优化问题而提出来的,它采用序号编码方式.PGA取消了传统序号编码TGA的交叉算子,代之以仅在一条染色体上操作的基因重组等遗传算子,简化了遗传操作,提高了计算效率,并且不要求初始群体的多样性,对“早熟收敛”问题也有较好的解决.单亲遗传算法的基本原理:PGA的遗传算子有基因换位,基因位移等遗传算子繁殖后代.PGA选择的算子是

3、从旧群体中选择适应性强的个体组成新群体的过程.PGA的基因换位算子是按一定的概率P1交换一条染色体中某些位置上的基因的过程,被交换基因的位置是随机的.基因换位分为单点换位和多点换位.单点换位是一次只交换一对(两个)基因的位置,多点换位是对预先给定的正整数L,取随机数i(1≤i≤L)一次交换i对基因.GA的基因位移是按一定的概率P2把一条染色体上的一些子串中的基因依次往后移位,并把该子串的最后一个位移到最前面的位置,在一条染色体中进行基因位移的子串及其长度是随机选取的.PGA的基因倒位是按一定的概率P3把一条

4、染色体中一些子串中的基因依次倒转,在一条染色体中进行基因位移的子串及其长度是随机选取的.由于PGA采用单亲繁殖方式,不具有双亲繁殖方式,使得不少学者对于PGA是否属于遗传算法的范畴表示怀疑.文献[3]将PGA与TGA进行分析,指出PGA的基因重组算子隐含了序号编码TGA的交叉算子的功能,GA的子代个体保留了父代个体的大部分遗传特征,即PGA具有与TGA类似的进化机制,因此PGA仍属于遗传算法的范畴.2.组合优化类中的N皇后问题组合优化问题是指若干种组合(或排列)运算中寻求最佳的一种组合,从而实现对问题(或策

5、略)的最佳选择规划.N皇后问题是一种较典型的组合优化问题.N皇后问题是指:将皇后置于一个网格的国际象棋棋盘上,使任何一个皇后都不会受到其它皇后的攻击,即要求任意一个皇后没有任何两个在同一行,同一列,同一条斜线上.求解这一问题的算法有很多,如穷举法,回溯算法,人工神经网络法等.但这些算法在问题规模很大时,求解所需时间长,有时甚至达不到可行的结果.文中采用整数编码的单亲遗传算法对此问题进行求解.可设:N个皇后的一个布局为X=x1,x2,x3,x4,x5,…,xn.xi表示第i行的皇后放在第xi列.这里xi(i=

6、1,2,…,n)的值取[1～n]中任一个整数,且加约束条件(1)当i≠j时,xi与xj互不相等,这样保证所有皇后不在同一行,同一列.约束条件(2)xi-xj≠i-j,这样保证所有皇后不在同一条斜线上,3.算法的实现步骤1)编码和种群的选取　采用整数编码,步长为N的染色体,每一个基因是取1到N中的任一整数,且同一条染色体上的基因在数值上互不相等.利用随机函数进行处理可以使同一染色体上的基因数值互不相等.按此编码得到的个体满足约束条件(1);种群的规模大约为N的10到30倍.2)适应度　使用基于排名的选择策略,

7、让群体中个体的函数值由大到小排列,其相应的适应度按一定的规则由小到大选择概率Pi(i=1,2,…,N),然后再根据这个概率使用类似转盘选择的方式选择父体以进行遗传操作.3)交叉和变异　由约束条件(1)的要求,步长为N的染色体上各个基因的取值是互不相同的,如果采用传统的遗传算法进行交叉、变异,可能会存在一些问题.以N=8为例,进行两条染色体交叉父代1为x1x2x3x4x5x6x7x8父代2为x3x4x7x6x8x2x1x5子代1为x1x2x7x6x5x6x7x8子代2为x3x4x3x4x8x2x1x5父代经过

8、交叉后,保证不了子代中的个体上各个基因的取值是互不相同,达不到约束条件(1)的要求.又由于传统遗传算法进行变异操作就是以变异概率P选择个体,然后随机指定其某一位或某几位基因座上的基因值进行0,1反转,但这只能在二进制编码中才能进行,对整数编码,该变异操作不通用.所以文中采用单亲遗传算法的基因换位和基因位移两种遗传算子繁殖后代.其基因换位过程为父代为x1x2x3x4x5x6x7x8子代为x1x2x6x4x5x3x7