一种改进遗传算法及其在TSP问题中的应用

1、遗传算法1,2是由教授于年首先提出John H.Holland 1975来的。这种算法是受达尔文的生物进化论启发而创建的,是基于生物进化中自然选择、适者生存和物种遗传思想的搜索算法。它是一种非数值并行优化算法。近年来,遗传算法在解决连续变量的函数最优化问题和离散变量的组合最优化问题时所表现出的鲁棒性、全局最优性、隐含并行性和自适应性而使其成为目前应用较为广泛的一种智能优化方法1,2。但在传统的遗传算法中1,算法的收敛速度与问题解的质量是影响算法寻优性能的一对主要矛盾。针对上述矛盾,我们提出了一种改进现有寻优性能的综合控制策略:GA (1杂交、变异的并行处理;基于适应值密度的变异操作;(2 自调

2、整父代迁移策略与父代与子代竞争策略。并通过求(3解问题验证了算法的有效性。TSP 遗传算法简介1 设待优化的函数为,是一个向量,它是所有的可能f(xx 的取值构成的该优化问题的变量空间。首先,由构造出f(x一个适应值函数,该适应值函数必须满足其下面g(x=Ff(x两个条件:的值域g(xV R + (R +表示全体非负实数的集合;在取得最优值的点时取得最大值。g(x遗传算法的实现步骤如下1,2:确定遗传算法的参数:种群大小,交叉概(1 POPSIZE 率P c ,变异概率 P m 。初始化:随机产生一个规模为的初始种(2 POPSIZE 群,其中每个个体为二进制位串的形式。并计算每个个体的适应值

3、 Gi 。杂交:从种群中随机选择两个染色体,按一定的杂(3 交概率P c 进行基因交换,交换的位置随机产生。变异:从种群中随机选择一个染色体,按一定的变(4 异概率 Pm 进行基因变异。繁殖:计算当前代每个个体的适应值;根据其相对(5 适应值,计算每个个体(也即染色体的再生次数,并进行繁殖操作。繁殖后保持种群个数不变。POPSIZE 如果满足停止规则,则返回当前代适应值最高的个(6 体所对应的变量空间的点,作为优化的结果;否则,回到x 继续繁衍下去。(3遗传算法研究的主要目标是既要使算法的质量提高,又要求算法具有高的计算效率。一方面,由于遗传算法是一种随机搜索,所以好的解往往需要大的计算量;另

4、一方面,收敛速度高的算法通常导致早熟,使解的质量降低。在传统的中,主要通过变异率来调节收敛速度和解的质量之间的GA 矛盾3。变异率太小,则算法容易陷入局部最优值,导致早熟,使解的质量降低;反之,变异率太大,则遗传算法退化为随机搜索法。因此,我们针对遗传算法的演化步骤,从多方面入手,提出了一种改进遗传算法的综合控制策略。改进遗传算法的控制策略2 好的算法使计算效率和解的质量之间的平衡。可以从遗传算法的选择操作来理解收敛速度与解的质量间的关系。从个体选择方面来讲,高的收敛速度通常通过采用高选择压力,即给予当前代中的具有较高适应值的个体较高的再生概率来实现。另一方面,由于群体规模不变,使得当前代中的

5、具有较低适应值的个体降低了群体中个体的信息含量,使算法搜索新解区域的能力降低,即降低了算法搜索全局最优解的能力。因此,容易导致早熟收敛。既要使算法有较快的收敛速度,又要获得令人满意的解。我们提出的改进遗传算法从以下几方面对传统进行了改进。GA 杂交、变异的并行处理2.1 传统的计算结构模拟生物的遗传进化过程,即采用 GA 一种改进遗传算法及其在问题中的应用TSP 陈斌,徐华中(武汉理工大学自动化学院,武汉430070摘要: 传统遗传算法的收敛速度与问题解的质量是影响算法寻优性能的一对主要矛盾。文章针对上述矛盾,提出了改进遗传算法的控制策略杂交、变异的并行处理、基于适应值密度的变异操作、自调整父

6、代迁移策略和父代与子代竞争策略。并应用于问题中,验证了算法TSP 的有效性。关键词:遗传算法;改进遗传算法;控制策略;旅行商问题An Improved Genetic Algorithm and Its Application in TSP,CHEN Bin XU Huazhong,(School of Automation ,Wuhan University of Technology Wuhan 430070【】Abstract The convergence speed of genetic algorithm and the quality of problem result are

7、the main inconsistency which affects the performance of GA.The paper proposes the control strategies of improved GA,which are parallel operation of crossover and mutation, mutation based on the density of fitness, the adaptive migration of father generation and competition of father generation and f

8、ilial generation. Furthermore, its efficiency is shown by an application in TSP.【】Key words Genetic algorithm; Improved genetic algorithm; Control strategy; Traveling salesmam problem第28卷第9期Vol.28 9计算机工程Computer Engineering2002年9月 September 2002人工智能及识别技术 中图分类号: TP301.6文章编号:10003428(200209 009003文献标识

9、码:A90 串行处理结构杂交、变异再进行选择。这种串行算子操作方式存在弊端:对杂交后的个体进行变异计算,有可能破坏经杂交后所产生的较优个体,从而影响收敛速度。虽然目前大多数改进的遗传算法都是采用自调整杂交率和变异率来解决交叉与变异算子的协调问题,但是串行结构使交叉和变异具有较强的耦合性,因此有时用此种控制策略所达到的效果并不十分理想。要提高的寻优性能,就要改变传统的GA GA 计算结构。将传统的的串行处理结构改为杂交、变异算GA 子分别对父代进行操作。这样,既可以充分保留父代个体的好基因模式、保持杂交寻优的速度,又可降低变异算子的破坏力,同时保证种群的多样性,从而提高的寻优性能。GA 基于适应

10、值密度的变异操作2.2 众所周知,存在早熟的问题,主要原因是由于一种GA 被称为超级个体的现象存在4,即当种群进化到某一代时,在种群中某个个体的适应值远远大于其他任何个体的适应值,因为个体被选中复制的概率与其适应值有关,这样就会造成子代中许多个体来自于同一祖先,从而彼此在基因模式上近似,中的杂交和选择操作失效。为了算法跳出早GA 熟,当某代中所有的个体集中在一起时,取基因突变的位数为普通基因突变位数通常为或位的倍。这样,就能(1234随机、独立地产生许多新个体,从而使整个种群脱离早熟。为判断某代中所有个体的集中程度,采用基于适应值密度的方法。首先,对适应值密度下个定义。适应值密度。D= 其中参

11、数的范围为,通常取值为。010.8当适应值密度小于预先设定的阈值因子时,说明该代中个体不是很集中,则采用普通基因突变位数进行突变。反之,当适应值密度大于预先设定的阈值因子时,说明该代中个体很集中,则采用多位基因突变,以产生许多独立、随机的新个体,增加解空间的搜索范围。自调整父代迁移策略与父代与子代竞争策略2.3 遗传算法的迁移策略也将影响到个体的多样性。遗传算法的个体迁移操作方式体现了自然界父代与子代之间的继承与相互竞争的关系。这种普遍的生物现象,在物种的进化过程中产生了具有广泛适应性的鲁棒性结构。由的算法可GA 以看出,个体的迁移策略是算法必需的一个重要环节5。遗传算法的性能在很大程度上依赖

12、于个体迁移策略,也就是依赖于如何在每一代中选择被替换的个体来提高算法的寻优性能。其实质是怎样既要保留进化过程中父代个体具有的好基因模式,又要用子代中产生的个体所具有的更有效的新基因模式来替换父代中已不再有生命力个体中的旧基因模式。改进遗传算法的算法流程如图所示,由图可以看出,11由于采用并行的杂交操作和变异操作,使得如何确定父代的迁移策略以及父代与子代的竞争策略显得尤为重要。如果在父代迁移策略中采用迁移固定数量的父代,然后与子代进行竞争。实际上采用这种策略忽略了遗传算法优化的动态性,也就是说,遗传算法每一代对解的优化程度是不一样的。与父代相比,具有有效基因模式的个体数量也是随着进化的过程不断变

13、化。迁移固定数量的父代,导致拥有较多好的基因模式的群体中,有些个体拥有的好的基因模式的信息被淘汰掉,降低了算法的寻优性能。自调整父代迁移策略具体分为两步分别求出杂交子:(1代和变异子代平均适应值C rossFitness avg 和MutateFitness avg ;取两者中的较大值并乘以阈值因子一般取(2(0.90-1.10,得到自调整适应值的阈值AdaptFitness=Max( C rossFitness avg , MutateFitness avg 选择大于自调整适应值的父代进入父代较优染AdaptFitness 色体库中,以准备与杂交子代和变异子代共同竞争进入新一代子代。与迁移固

14、定数量的父代策略相比,自调整父代迁移策略迁移的父代的数目随着种群的进化而动态变化。如果子代的平均适应值通过杂交或变异提高得很多,那么父代染色体库中保留较少父代。相反,如果子代的平均适应值通过杂交或变异提高得较少,那么父代染色体库中保留较多父代。这样,此策略增强了算法的寻优性能。由改进遗传算法的算法流程看出,新的子代是由父代较优染色体库中的全部个体、杂交子代个体和变异子代个体组成。因此,新的子代中保留父代中具有有效模式的优秀个体,又产生了经过杂交和变异后产生的具有有效模式的优秀个体。但是,由于杂交概率和变异概率不等于,则杂交子1代和变异子代中一定有父代中没有参加杂交和变异的较优个体,为了保证新的

15、子代在进行赌轮盘选择后群体的多样性,增大解的搜索空间,避免早熟,则一定要限制父代中较好个体在新的子代中出现的次数,因此我们采用父代与子代竞争策略。父代与子代竞争策略具体分为两步:比较杂交子代(1的个体与父代较优染色体库中的个体,与父代较优染色体库中相同的杂交子代的个体不进入新的子代;同样的策(2 略,与父代较优染色体库中相同的变异子代的个体也不进入新的子代。所以,新的子代是由父代较优染色体库中的全部个体,杂交子代的部分个体和变异子代的部分个体所组成。91POPSIZEMaxfitnessFitness Maxfitness m种群大小*(图1 改进遗传算法的算法流程图用改进遗传算法求解旅行商问

16、题3 (TSP问题描述3.1 TSP 问题也称旅行商问题、货郎担问题TSP 6。该问题是寻找一条最短的遍历个城市的路径,也就是说搜索城市集合n 中的元素代表对个城市的编C= (C n 号的一个排列,使得W 取最小值,式中d (W i ,W i+1代表城市 W i 到W i+1的距离。这是 一个典型的优化组合问题,已被证明属于 NP(nondetermini-完全问题,即没有确定的算法能在多项式时stic polynomial间内得到问题的解。对个城市而言,可能的路径总数为n。随着数的增加,路径数将按数率急剧增长,即所谓n!/2 n n 的指数爆炸。以为例,即使用每秒一亿次的计算机按n=20穷举

17、搜索法求解,也需年。因此,任何能使求解此问题350简化的方法,在学术界均予以高度的重视。它是一个经典的人工智能问题。目前比较好的求解方法有反馈神经网络法和遗传算法。用改进遗传算法的综合控制策略求解问题。TSP 算法描述3.2 我们以中国旅行商问题(CTSP6为所需解决的问题,按以下步骤进行。编码:直接采用城市在路径中的相当位置来表示。(1 例如,染色体,它表示从城市出发,先到达R=0538*城市,再到城市,再到城市,最后从城市返回。5314对应于中国旅行商问题,编码从开始,到结束。整个染030色体长度为。31确定适应值函数:取每条旅行路线的总行程的倒(2 g(x数为适应值,则适应值越小,方案越

18、优。确定初始化群体:设群体规模为。我们取(3 POPSIZE 个。先用贪婪法确定个个体,这个个体的起点城市分603131别是,。经过贪婪法产生的个体在一定程0122930度上使得初始群体具有有效的基因模式,有利于算法提高寻优能力,剩余的个体则随机产生。杂交算子:我们采用由提出的算子(4 Davis OX 7通过从一个亲体中挑选一个子序列旅行并保存另一个亲体的城市相对次序来构造后代。变异算子:对于基本的变异算子有倒置、插(5 TSP 入、移位、互换等。我们采用互换变异算子。即在染色体中随机产生两个位置,将这两个位置上的基因互换即可,也即互换基因所对应的城市。在小于适应值密度的阈值时,每个染色体进

19、行次基因互换操作。在大于适应值密度的阈值2时,每个染色体进行次基因互换操作。6参数选择:杂交概率(6 P c 取,变异概率0.9P m 取。一0.8般而言,P m 取值范围。但是由于改进的遗传算法0.0050.01杂交和变异采用并行处理,这样一来,突变不再破坏遗传和杂交的寻优结果,因此变异率可取很大,使算法可以覆盖广泛的解空间。适应值密度阈值因子取。自调整适应值0.7阈值因子取。0.8仿真结果5仿真实验的结果如表所示。1表仿真实验结果1 第1组第2组第3组第4组简单遗传算法0.08210.03240.00820.0006从实验结果可以看到,采用了改进遗传算法的综合控制策略较简单的遗传算法在收敛

20、速度上有明显的提高,使解空间很好地脱离早熟,并且得到了已知的最优解。因此,基于改进的遗传算法对解决复杂的非线性规划问题具有较好的稳定性、收敛性和精确性。结论4 本文分析了传统在解决问题时存在的不足,即传统GA 的收敛速度和对问题解空间覆盖能力之间存在相互制约GA 的关系。这种制约关系使传统在处理复杂非线性规划问GA 题时,难以取得优良的性能。针对这一矛盾,本文提出的改进遗传算法的综合控制策略不仅提高了遗传算法的收敛速度,而且使得求解质量显著提高。参考文献1 Michalewicz Z. Genetic Algorihms+Data Structures=Evolution Progr- ams

21、.Beijing: Science Publishing House,20002 Liu Yong, Tang Lishan, Chen Yuping. Non-digital Parallel Algorithms. Beijing: Science Publishing House,19973 Bhandart D, Muthy C A. Genetic Algorithm with Elitist Model and Its Convergence. International Journal of Pattern Recognition and Artificial Intelligence,1996, 10(64 Potts J C, Gkddens T D, Yadav S B. The Development and Evaluation of an Improved G