遗传算法研究进展综述.pdf

遗传算法研究进展综述 许良凤潘孟贤安良 (合肥工业大学计算机与信息学院图像信息处理研究室230009) 摘要本文阐述了基本遗传算法(SGA)存在的一些缺陷，从初始群体的产生，交叉变异算 子，选择算子及重要参数的选择四个方面总结了国内外相应的改进方法，最后结合 这些缺陷介绍了几种改进的遗传算法。 关键词遗传算法适应度早熟 1序言 遗传算法(GA)是一类借鉴生物界自然选择和遗传机制的随机化有哪些信誉好的足球投注网站算法，GA作为-．种全 局优化有哪些信誉好的足球投注网站算法，它简单通用，鲁棒性强【1】。近年来在模式识别，神经网络，遗传学等方面 得到广泛应用[2】[3】。用SGA解决的问题越复杂，目标越不明确其优越性越明显，但是它与其 他新事物一样，也存在着缺点。为克服这些缺点，一些改进的GA不断出现，许多学者已提出 一系列有效解决方案。本文阐述SGA存在的一些缺点，针对这些缺点介绍国内外几种改进GA。 2遗传算法的缺点及改进这些缺点的方案 SGA缺点[4】：①收敛速度慢。②重要参数如胛(群体规模)，P。(交叉概率)，Pm(变异概 率)选择。③局部有哪些信誉好的足球投注网站能力较弱。④单一群体更新方式难以兼顾多样性和收敛性要求．⑤早熟 和有哪些信誉好的足球投注网站迟钝。针对这些缺点改进方案不少可从初始群体产生，交叉变异算子等方面寻求改进。 (1)初始群体的产生 初始群体的特性对计算结果和效率均有重要影响，经典GA是按随机方法产生一组原始 解，这样就可能导致初始群体在解空间分布不均匀，从而影响算法性能，针对这个问题许多研 究者提出很多解决方案，如吴斌【5】等提出了在初始群体产生上要求各个个体间保持一定的距 离，尽可能均匀地分布在整个解空间上。为此假设种群大小为N和个体字符串长度为K，则 要求入选种群的所有个体间的海明距Hii(ij1，2，3．--,N,i予厶j)大于等于某个设定值，初始群体采 用这种方式产生就能保证随机产生的各个体间有较明显差别，使它们能比较均匀地分布在解 空间上，以增加收敛于全局最优解可能。文献【6】将一些实验设计方法如正交设计与GA相结 合，这样就能保证产生的初始群体在解空间均匀分布，使GA从好的初始群体出发均匀有哪些信誉好的足球投注网站整 个解空间。文献[7】用“竞赛法”代替SGA中“赌轮法”，即随机在种群中选取两个或两个以 上的个体，比较它们适应度大小，使适应度最大的个体存活并被保留在新一代种群中，重复 这一过程，直到得到与初始群体中个体数相等的新一代种群。在“竞赛法”中每个个体都要 753 经优胜劣汰这一选择过程，优胜者才能被保留到新的一代中，而且适应度大的个体可能被多次 复制，从而使新一代种群的整体适应度加大。这样就提高了GA收敛速度。 (2)交叉算子和变异算子的改进 遗传算法通过交叉和变异这～对相互配合又相互竞争的算子使有哪些信誉好的足球投注网站能力得到飞速提高， 交叉操作在遗传算法中是核心的遗传操作，对GA的收敛性起决定作用[8】。变异操作在遗传 算法中主要有两个目的[9】①改善遗传算法的局部有哪些信誉好的足球投注网站能力。②维持群体多样性防止出现早熟 现象。当群体陷入局部解而不能由交叉解决时，配合有效的变异可使之跃出局部解，而后期 的变异可能破坏已产生的对形成最优解有建设性作用的模式。为此应有效的配合交叉和变异， 如在自适应遗传算法【10】(AGA)中，P。，．Pm随个体适应值的改变而改变，P。，Pm定义如下： p。：尼。—fmax—-ft厂，≥歹，p。：尼，厂·一f fmax——f w厂·≥歹， p。：七。厂·一f p。=k2_fm—ax-jf ，max-厂 自适应遗传算法通过上述的公式实现根据每一个基因的适应度大小自适应调整[10】其交 叉率和变异率大小。其中f一群体平均适应度，．厂I一交叉双方适应度大者的适应度，厶。。一 群体的最大适应者，O≤kI．k2。k3，l(4≤1．卜为常数。 文献【l1】中对变异算子采取多位变异的策略，即动态地根据个体优劣情况决定其变异的位 数，将这个变异的策略与AGA结合起来形成一种自适应多位变异算子，即当前代中某一个体 在种群中越差则变异位数越多。在自调整遗传算法[121，父代群体进化质量由两个指标来衡量： ①子代中互异的新个体数。②父代群体平均适应度的增长率，即父