一种改进的遗传算法及其应用

1、一种改进的遗传算法及其应用杨晓燕,李水仙,周武夷(闽江学院计算机系,福建福州350108摘要:为解决遗传算法的早熟和局部收敛现象,提出的一种改进的遗传算法,该算法引入海明距离构造初始种群,在选择、交叉、变异过程中采用最优保存策略。实验表明改进的遗传算法增强了种群的多样性,并在一定程度上避免早熟现象发生,同时又能较快找到全局最优解。关键词:遗传算法;多样性;最优保存策略;背包问题doi :10.3969/j.issn.1008-6749.2010.05.011中图分类号:TP301.6文献标志码:A文章编号:1008-6749(201005-0038-04An Improved Genetic

2、AlgorithmYang Xiaoyan ,Li Shuixian ,Zhou Wuyi(Department of Computer Science ,M injiang University ,Fuzhou Fujian 350108,China Abstract :In this paper ,an improved genetic algorithm is proposed to solve the problems of prematurity and local convergence.The Hamming distance is employed to generate th

3、e original population ,and the elitist preserved strategy is used in the process of the selection ,crossover ,and mutation.Experiments show that the improved genetic algorithm is efficient.Key words :genetic algorithm ;diversity ;elitist preserved strategy ;knapsack problem收稿日期:2010-08-11基金项目:闽江学院科技

4、育苗基金项目(YKY08004B 作者简介:杨晓燕(1976,女,福建漳州人,讲师,硕士。遗传算法1是当今影响最广泛,同时也是发展最迅速的进化计算方法之一。作为一种模拟生物进化过程的新颖方法,遗传算法对非线性和复杂问题具有很强的鲁棒性和全局搜索能力,因此,被广泛应用于机器学习、模式识别、数学规划等领域。但传统的遗传算法往往存在易早熟、易陷入局部最优解、后期收敛速度较慢等不足。针对以上问题,文献2提出一种基于物种方程和Kriging 算子的多种群遗传算法;文献3提出通过引入具有优良性能的修正种群替换进化种群较差个体的策丽水学院学报JOURNAL OF LISHUI UNIVERSITY第32卷第

5、5期Vo1.32No.52010年10月Oct.2010略,以提高种群的多样性;文献4提出一种自适应调节交叉概率和变异概率的策略以避免早熟,提高算法的收敛速度。本文提出引入海明距离构造初始种群,以提高种群的多样性,在选择、交叉、变异操作中采用最优保存的策略,以提高算法的收敛速度。实验结果表明,改进的遗传算法不仅能加快遗传进化速度,而且还能增强算法的全局收敛性能,从而得到满意的全局最优值。1一种改进的遗传算法1.1初始种群的构造遗传算法对初始种群很敏感,采用随机生成初始种群的方法会导致算法收敛速度较慢。为了加快求解速度,本文引入海明距离的定义5来构造初始种群,使得初始种群在解空间中尽量分布均匀。

6、定义1相同长度的以a为基的2个字符串中对应位不相同的个数量称为海明距离,记为GH。设个体是以a为基的字符串,个体的长度为dlen,种群的规模大小为N,则要求入选种群的所有个体之间的海明距离GH必须满足:GH ij(dlen-b,ij,(1式中i、j为2个个体,i、j=1,2,N;b是由编码形式而定的一个常数,这里以二进制编码为例,则b=int(dlen/2;a类似于b,a=2表示使用二进制编码。采用这种方法使初始种群个体之间保持一定距离,即各个个体尽可能均匀分布在整个解空间上,这样有利于扩大搜索空间,保证种群的多样性,增加算法收敛于全局最优解的可能。1.2最优保存策略本文提出在遗传算法的选择、

7、交叉和变异操作过程中采用最优保存的策略。在选择操作时将个体按适应度从小到大进行排序,然后将父代种群中适应度最大的10%个体直接进入匹配池成为子代种群中的个体。该方法可保证在遗传过程中所得到的最优个体不会被交叉和变异操作所破坏,能将最优个体保留到下一代,同时该策略又能保持子代的多样性。在交叉和变异操作过程中,最优保存策略只保留最优个体,即只保留交叉和变异的结果优于父个体的子个体。这种最优保存策略容易使得局部最优个体不易被淘汰,从而增强算法的全局搜索能力。2改进的遗传算法在0-1背包问题上的应用0-1背包问题(Knapsack Problem,KP是一个典型的离散的NP难问题。该问题描述为,假定n

8、个物品和一个背包,物品i(i=1,2,n的质量是W i,其价值为P i,背包的容量是C,如何选择装入背包的物品,使得装入背包中的物品总价值最大。0-1背包问题在数学上实际是一个0-1规划问题,即Xi为0-1决策变量,物品装入背包中表示为Xi=1,物品不装入背包中表示为X i=0。其数学模型为:m ax f(x1,x2,xn=ni=1P i X i,s.t.ni=1W i X iC。(22.1修正策略由于约束条件的存在,初始种群以及经由交叉、变异操作而产生的备选解不一定为可行解,因此,通常背包问题只对不可行解进行修正使之成为可行解。本文提出借鉴贪心算法对不可行解及背包承重不足的可行解都进行修正的

9、策略。2.1.1对可行解修正对背包承重不足的可行解的具体操作如下: (1如果被选物品总质量还没有超出背包的最大容量,则将剩余物品按价值密度(Pi/W i从大到小排列;(2按上述排列的先后次序依次从剩余物品中取出价值密度最大的物品,加入背包,直到超出背包最大容量。2.1.2对不可行解修正对于不可行解,通过以下步骤将其修正6:(1如果被选物品质量超出背包的最大容量,则将背包中的物品按价值密度(Pi/W i从小到大排列;(2按上述排列的先后次序依次减掉背包中价值密度最小的物品,直到形成可行解为止。修正策略通过贪心算法对个体(可行解、不可行解进行改良,提高了遗传算法的集中搜索能力,提高了搜索速度,能较

10、快得到全局最优解。2.2求解0-1背包问题的改进的遗传算法改进遗传算法求解0-1背包问题的步骤如杨晓燕,李水仙,周武夷:一种改进的遗传算法及其应用第5期39 图2基本遗传算法最优解增长情况下:(1确定种群规模,采用海明距离方式产生均匀的初始种群,根据算法修正初始种群。(2计算个体的适应度。(3采用最优个体保存和轮盘赌结合的方法,实现选择操作。(4按交叉率P c 从子代新种群中选择部分个体进行交叉,并对交叉后得到结果采用修正策略进行修正;用最优保存策略得到新种群。(5按变异率P m 从子代新种群中选择部分个体进行变异,并对变异后得到结果采用修正策略进行修正;用最优保存策略得到新种群。(6检查是否

11、达到停止准则,如果是,则输出全优结果,结束运行;若否,转(2继续。3仿真实例为验证本文算法的有效性,将本文算法与基本遗传算法进行比较,2种算法独立运行20次。待优化函数为:y =cos (5x -sin (3x +10,式中x 1,7,求函数的最大值。该函数当x 为3.7419,得到全局最大值为11.9638。2种算法参数设置为:群体大小M =200,终止进化代数T =20,交叉概率P c =0.97,变异概率P m =0.1。图1是本文算法求得的平均最优解增长情况,图2是采用基本遗传算法求得的最优解增长情况,采用本文算法平均第7代达到最优解,采用基本遗传算法第15代才达到最优解。实验表明本文

12、对初始种群的构造,能保证种群的多样性;最优保存策略可以有效避免优良个体因为交叉、变异而被破坏,能较快得到全局最优解。为进一步验证本文算法的有效性,用本文算法求解典型的组合优化问题(0-1背包问题,并将本文算法分别与贪心算法、基本遗传算法和混合遗传算法6进行比较,各种算法独立运行20次。各种遗传算法参数设置为:群体大小M =200,终止进化代数T =100,交叉概率P c =0.6,变异概率P m =0.05。测试数据如下:背包容量C =1000,物品的质量W =80,82,85,70,72,70,66,50,55,25,50,55,40,4850,32,22,60,30,32,40,38,35

13、,32,25,28,30,22,50,30,45,30,60,50,20,65,20,25,30,10,20,25,15,10,10,10,4,4,2,1,物品的价值量P =220,208,198,192,185,180,165,162,160,158,155,130,125,122,120,118,115,110,105,101,100,100,98,96,95,90,88,82,80,77,75,73,72,70,69,66,65,63,60,58,56,50,30,25,15,10,8,5,3,1。该题的最佳装入价值是3106。各种算法运行结果如表1所示,其中每个单元格中的数据表示运算2

14、0次获得最佳装入价值、最佳装入质量。表1各种算法装入价值、装入质量结果对比表2列出在1000次实验中,上述3种遗传算法获得次优解(装入价值超过3036的平均迭代次数 。图1最优解增长情况算法贪心算法基本遗传算法混合遗传算法改进遗传算法最佳装入价值3036307731033106最佳装入质量99999910001000丽水学院学报402010年表2获得次优解(装入价值超过3036的平均迭代次数算法基本遗传算法混合遗传算法改进遗传算法平均迭代次数(代/次从表1和表2的结果可看出,在求解0-1背包问题时,改进的遗传算法无论是在求解的质量方面,还是在求解速度方面,都比其他3种算法更优越。这是由于改进的

15、遗传算法中借鉴贪心算法的思想,对不可行解及背包承重不足的可行解进行修正,这样产生的初始种群全局最优值已经比较接近问题的解,因此可以节省搜索时间,提高算法收敛速度。同时在交叉与变异的过程中采用最优保存策略,当子代个体比父代个体更优,才进行该次的交叉或变异,这样就保证了父代种群中最优个体能保留到子代种群,从而得到了较高的求解速度和精度。4结语遗传算法存在过早收敛、易于陷入局部最优等问题。针对0-1背包问题,本文提出引入海明距238358离构造初始种群、最优保存策略以及修正策略,实验表明改进的遗传算法增强了种群的多样性,并在一定程度上避免早熟现象的发生,同时本文算法又能较快找到全局最优解,因此本文算法是较有效的。参考文献:1Holland John H.Adaptation in natural and artificial systems M .Michigan:The University of Michigan Press,1975.2陈曦,王希诚.一种改进的多种群遗传算法J .辽宁科技大学学报,2009.32(2:160-163.3苏子林.求解作业车间调度问题的多种群改进遗传算法J.鲁东大