一种改进的遗传算法及其应用杨晓燕,李水仙,周武夷(闽江学院计算机系,福建福州350108摘要:为解决遗传算法的早熟和局部收敛现象,提出的一种改进的遗传算法,该算法引入海明距离构造初始种群,在选择、交叉、变异过程中采用最优保存策略。实验表明改进的遗传算法增强了种群的多样性,并在一定程度上避免早熟现象发生,同时又能较快找到全局最优解。关键词:遗传算法;多样性;最优保存策略;背包问题doi:10.3969/j.issn.1008-6749.2010.05.011:TP301.6文献标志码:A:1008-6749(201005-0038-04AnImprovedGeneticAlgorithmYangXiaoyan,LiShuixian,ZhouWuyi(DepartmentofComputerScience,MinjiangUniversity,FuzhouFujian350108,ChinaAbstract:Inthispaper,animprovedgeneticalgorithmisproposedtosolvetheproblemsofprematurityandlocalconvergence.TheHammingdistanceisemployedtogeneratetheoriginalpopulation,andtheelitistpreservedstrategyisusedintheprocessoftheselection,crossover,andmutation.Experimentsshowthattheimprovedgeneticalgorithmisefficient.Keywords:geneticalgorithm;diversity;elitistpreservedstrategy;knapsackproblem收稿日期:2010-08-11基金项目:闽江学院科技育苗基金项目(YKY08004B作者简介:杨晓燕(1976—,女,福建漳州人,讲师,硕士。遗传算法[1]是当今影响最广泛,同时也是发展最迅速的进化计算方法之一。作为一种模拟生物进化过程的新颖方法,遗传算法对非线性和复杂问题具有很强的鲁棒性和全局搜索能力,因此,被广泛应用于机器学习、模式识别、数学规划等领域。但传统的遗传算法往往存在易早熟、易陷入局部最优解、后期收敛速度较慢等不足。针对以上问题,文献[2]提出一种基于物种方程和Kriging算子的多种群遗传算法;文献[3]提出通过引入具有优良性能的修正种群替换进化种群较差个体的策丽水学院学报JOURNALOFLISHUIUNIVERSITY第32卷第5期Vo1.32No.52010年10月Oct.2010略,以提高种群的多样性;文献[4]提出一种自适应调节交叉概率和变异概率的策略以避免早熟,提高算法的收敛速度。本文提出引入海明距离构造初始种群,以提高种群的多样性,在选择、交叉、变异操作中采用最优保存的策略,以提高算法的收敛速度。实验结果表明,改进的遗传算法不仅能加快遗传进化速度,而且还能增强算法的全局收敛性能,从而得到满意的全局最优值。1一种改进的遗传算法1.1初始种群的构造遗传算法对初始种群很敏感,采用随机生成初始种群的方法会导致算法收敛速度较慢。为了加快求解速度,本文引入海明距离的定义[5]来构造初始种群,使得初始种群在解空间中尽量分布均匀。定义1相同长度的以a为基的2个字符串中对应位不相同的个数量称为海明距离,记为GH。设个体是以a为基的字符串,个体的长度为dlen,种群的规模大小为N,则要求入选种群的所有个体之间的海明距离GH必须满足:GHij≥(dlen-b,i≠j,(1式中i、j为2个个体,i、j=1,2,…,N;b是由编码形式而定的一个常数,这里以二进制编码为例,则b=int(dlen/2;a类似于b,a=2表示使用二进制编码。采用这种方法使初始种群个体之间保持一定距离,即各个个体尽可能均匀分布在整个解空间上,这样有利于扩大搜索空间,保证种群的多样性,增加算法收敛于全局最优解的可能。1.2最优保存策略本文提出在遗传算法的选择、交叉和变异操作过程中采用最优保存的策略。在选择操作时将个体按适应度从小到大进行排序,然后将父代种群中适应度最大的10%个体直接进入匹配池成为子代种群中的个体。该方法可保证在遗传过程中所得到的最优个体不会被交叉和变异操作所破坏,能将最优个体保留到下一代,同时该策略又能保持子代的多样性。在交叉和变异操作过程中,最优保存策略只保留最优个体,即只保留交叉和变异的结果优于父个体的子个体。这种最优保存策略容易使得局部最优个体不易被淘汰,从而增强算法的全局搜索能力。2改进的遗传算法在0-1背包问题上的应用0-1背包问题(KnapsackProblem,KP是一个典型的离散的NP难问题。该问题描述为,假定n个物品和一个背包,物品i(i=1,2,…,n的质量是Wi,其价值为Pi,背包的容量是C,如何选择装入背包的物品,使得装入背包中的物品总价值最大。0-1背包问题在数学上实...