一种改进的遗传算法Scatter GA

一种改进的遗传规划算法作者：唐淑珍来源：《电脑知识与技术》2010年第04期摘要:遗传规划的实质是用广义的层次化计算机程序描述问题,比较适合于求解一类由于各种不确定因素导致的复杂非线性问题。

该文采用了一种改进的遗传规划算法,建立了相应的预测模型,将其与Weka里的GP算法在标准数据集上进行对比测试,结果表明该改进的遗传规划算法是有效的、可行的。

关键词:遗传规划;适应度;预测中图法分类号:TP18 文献标识码:A文章编号:1009-3044(2010)04-0895-02An Improved Genetic Programming AlgorithmTANG Shu-zhen(Tianjin Jinghai County Hospital, Tianjin 301600, China)Abstract: The genetic programming is essentially the level of generalized computer program description of the problem, more suitable for solving a class due to various uncertainties caused by the complex non-linear problems. In this paper, an improved genetic programming algorithm to establish the corresponding prediction model, where the GP with Weka algorithm for the standard data set on the comparison test results show that the improved genetic programming algorithm is effective and feasible.Key words: genetic programming; fitness; forecast影响数值问题预测的因素多种多样,各因素间存在着复杂的非线性关系,采用一般的统计方法很难准确预测其含量[1]。

遗传算法的研究和改进遗传算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法，其应用优势在于处理传统搜索方法难以解决的复杂和非线性问题，本论文研究内容包括：小生境遗传算法的改进、自适应遗传算子的设计、免疫的进化算法。

本文主要工作如下：（1）遗传算法的起源、其基本概念以及研究概况;（2）遗传算法的基本理论.主要介绍了模式定理、积木块假说、内在并行性、Walsh模式变换、欺骗问题等;（3）基本遗传算法.主要介绍了编码、适应度函数、遗传操作等.（4）遗传算法的改进.主要介绍了分层遗传算法、CHC算法、messy遗传算法、自适应遗传算法、基于小生境技术的遗传算法、混合遗传算法等几种遗传算法的改进.（5）遗传算法的应用.关键词：遗传算法;进化计算;进化规划;进化策略;遗传操作;适应度函数;Walsh函数ABSTRACTGenetic algorithm is a kind of random searching method using lives’ natural selection and genetic mechanism. Its application predominance lies in complicated and non-linear problems, which are difficult for traditional searching methods. Three improved algorithms are proposed in the dissertation: improved niche genetic algorithm, improved adaptive genetic algorithm, genetic algorithm based on immune mechanism. They are summarized as following:Firstly, the dissertation analyses characters of several traditional genetic algorithms for niche. Following this, a new method, combined parallelism evolution technique for niches based on local competition with parent mutation mechanism, is proposed which improved the genetic algorithms for niche. Compared with genetic algorithm with sharing, it has some improvements in both converging velocity and precision.Secondly, analyzing the inadequacies of the evaluation indices for premature convergence, a novel improved adaptive genetic algorithm (IAGA) is described. The calculation result of an example shows that IAGA is able to get the real-time information of population diversity during the process of evolution.Finally, applying the immune mechanism to genetic algorithm, the immune genetic algorithm expatiated on this paper comes over the phenomenon of premature in some extent. The result of experiment shows that the global convergence and searching velocity are both improved.Keyword: genetic algorithms, evolution strategy, Walsh function第一章 绪论§1.1 引言遗传算法（Genetic Algorithm ——GA ），是一类以达尔文的自然进化论与遗传变异理论为基础的求解复杂全局优化问题的仿生型算法[1]。

交叉算子自适应遗传算法
自适应遗传算法(Adaptive Genetic Algorithm，AGA)是对基本遗传算法的一种改进，它通过对遗传参数的自适应调整，大大提高了遗传算法的收敛精度，加快了收敛速度。

适应度函数是评价个体适应环境的能力，在进行选择操作时经常用到，它的选取是否恰当直接影响到遗传算法的性能，所以就形成了很多计算适应度的函数，改进这些适应度函数是为了使适应度能更好的反映个体的优劣，使得适应度低的个体被淘汰，适应度高的个体被保留。

自适应的适应度函数可以随着种群代数的增加自适应的调整，在算法的开始阶段，适应度差别较大，为了防止一些适应度较差的个体在一开始就丢失，可以通过改变适应度函数使得它们得以保留下来，另外，当种群趋于收敛时，适应度差别很小，这时为了加快收敛的速度，应对适应度进行调整，使得个体适应度差别增大，从而更快的收敛到全局最优解。

常用的适应度变换方法有：线性变换、幂函数变换和指数变换。

另外，采用适应度结合了模拟退火的思想。

选择的作用是按某种方法从父代群体中选取一些将要进行交叉的个体，常用的选择方法很多，它们大多有一个共同的特点，就是都是基于适应度的选择，适应度大的个体被选中的概率就大，适应度小的个体被选中的概率就小。

常用的选择算法有适应度比例法、精英保留策略、联赛选择法等。

另外，也可以将这些选择算法混合使用，如今还出现了启发式的搜索选择策略，这种策略是用每个个体所带有的启发信息来确定它被选中的概率。

遗传优化算法遗传优化算法（Genetic Algorithm，GA）是一种仿生学被广泛应用的理论框架和多目标优化方法，它利用“自然选择”和“遗传变异”的进化机制来求解复杂的优化问题。

其主要思想基于人工生物学中的“自然选择”和“遗传变异”的基本原理，将优化问题的求解转化为一种模拟生物进化的过程。

它是一种模拟进化的迭代算法，也就是说，它依照进化原理，对已有的解进行重新编码，运用变异、交叉等操作进行繁殖，得到新的解，以期求得较优解。

遗传优化算法在求解优化问题时，首先设定一个种群，所有搜索空间内可能的解都被描述为一个个个体，即基因序列，然后根据某种评价准则对个体进行适应度测评，再根据适应度的大小对个体进行排序，同时在排序的基础上进行遗传算子操作，如变异、交叉等，以搜索出更优解，最终形成新一代种群，这种过程不断迭代，直至满足某个终止条件为止。

遗传算法的优势是搜索范围广，可以应用于非常复杂的优化问题，可以同时解决多个目标优化问题，而且不易陷入局部最优解，在计算复杂度方面也比较小，但是它不能保证求得全局最优，而且受种群初始状态影响较大，收敛速度较慢，以及受“被动进化”概念影响，搜索出的解往往只能是局部最优，也就是说，解空间中有多个相似的解，但是其中只有一个是最优，而GA可能搜索到其他相似的解。

遗传优化算法的核心组成部分有三个：编码、适应度函数和遗传操作。

编码是指将优化问题中的参数用一定的数据结构表达出来，例如，将参数用二进制表示，适应度函数则是用来衡量优化问题中的适应度的函数，它通常是一个优化目标函数；遗传操作是指以特定的概率从当前种群中随机选取个体，并以一定的概率进行变异、交叉等操作，使得每一代的种群更加接近最优解。

因此，遗传优化算法是一种仿真进化算法，它是以自然界生物的进化模式为借鉴，通过模拟遗传过程，使优化解慢慢演化接近最优解，用于解决复杂的优化问题。

遗传算法论文：浅谈遗传算法的研究与改进【摘要】遗传算法是模拟自然界生物进化机制的概率性搜索算法，可以处理传统搜索方法难以解决的非线性问题。

但是经典遗传算法存在局部收敛、收敛速度慢等缺点，这使得经典遗传算法有时很难找到全局最优解。

本文针对经典遗传算法中所存在的缺点，采用阶段式的适应度函数、基于竞争机制的交叉方式和仿粒子群变异操作，使遗传算法的收敛速率、全局收敛概率都得到了较大的提高。

【关键词】遗传算法适应度交叉操作仿粒子群变异一遗传算法遗传算法（genetic algorithm，简称ga）是holland 在研究自然遗传现象与人工系统的自适应行为时，模拟生物进化现象，并采用自然进化机制来表现复杂现象的一种全局群体搜索算法。

遗传算法的基本思想起源于darwin进化论和mendel的遗传学说。

作为一类智能计算工具和学习算法，由于其实现简单、对目标函数要求不高等特性，遗传算法已广泛应用于如人工智能、组合优化等研究领域。

1．遗传算法的优越性遗传算法（genetic algorithm）利用某种编码技术作用在称为染色体的二进制串上，模拟由这些串组成的个体的进化过程。

通过有组织的、随机的信息交换来重新结合那些适应性好的串，在每一代中，利用上一代串结构中适应性好的位和段来形成一个新的串的群体，同时在串结构中尝试用新的位和段来代替原来的部分以形成新的个体，以增加种群的多样性。

遗传算法的最大优点是能够通过群体间的相互作用，保存已经搜索到的信息，这是基于单次搜索过程的优化方法所无法比拟的。

但是，遗传算法也存在着计算速度较慢，并且容易陷入局部最优解的问题中。

遗传算法的优越性归功于它与传统搜索方法不同的特定结构。

第一，遗传算法的操作对象是编码，对问题的限制极少，对函数的一些约束条件如连续性、可导性等不做要求，减少了要解决问题的复杂性。

第二，遗传算法同时搜索解空间内的许多点，因而可以有效地防止搜索过程中收敛到局部最优解，并获得全局最优解，与其他单点搜索的方法相比，在计算时间上也有较大的优势。

基于改进遗传算法的多目标优化问题求解方法研究在实际问题中，有很多的问题不仅仅只有单一的目标，而是具有多个目标。

例如生产计划问题中既要满足生产成本，又要满足生产效率，这时需要进行多目标优化问题的求解。

然而，多目标优化问题难以找到一个全局最优解，因此需要采用一些特殊的算法来解决这些问题。

其中改进遗传算法是一种有效的方法。

改进遗传算法（Improved Genetic Algorithm，简称IGA）是在遗传算法的基础上发展而来的。

IGA采用交叉、变异、选择等基本操作来产生下一代个体，并通过引入模拟退火、随机扰动等算法改进，以尽可能与全局最优解接近。

IGA将问题形成一个多维空间中的解，并通过不同的目标函数对这些解进行评价。

例如，对于一个生产计划问题，可以设置成本最小和效率最大两个目标函数。

迭代事非常快，因此不同的处理器能同时求解。

通过改进遗传算法，可以有效地解决多目标优化问题。

IGA将问题转化为一个多维空间中的解空间，在搜索过程中采用多极搜索，每次搜索依据遗传算法变异、交叉和选择操作计算每个个体满足问题的目标值。

同时，IGA还采用了一些其他优化方法，如引入模拟退火算法，使得IGA可以快速收敛到全局最优解。

IGA的优点在于既可以处理离散问题，也可以处理连续问题。

同时，其使用也非常方便，只需要将问题转化为遗传算法的模型即可。

虽然IGA在多目标优化问题中的表现非常出色，但其仍然存在一些不足之处。

例如，IGA对于不同目标函数之间的相对重要性的考虑可能不够充分。

同样，在应用IGA时需要根据不同的问题特点进行一系列参数的设置，这增加了应用的难度。

总结：多目标优化问题在实际问题中非常普遍，而改进遗传算法是解决这一问题的一种有效手段。

IGA通过在遗传算法的基础上添加随机扰动、模拟退火和多维搜索等算法，成功地解决了多目标优化问题。

但是，IGA仍然存在一些不足之处，需要在实际应用中进行不断优化和改进。

一种改进选择算子的遗传算法
陈有青;徐蔡星;钟文亮;张军
【期刊名称】《计算机工程与应用》
【年(卷),期】2008(044)002
【摘要】遗传算法(Genetic Algorithm,GA)是一种模拟生物进化的智能算法,被广泛应用于求解各类问题.简单遗传算法(Simple GA)仅靠变异产生新的数值,常常存在搜索精确度不高的问题.针对这个问题,对SGA的选择算子进行改进,即把相似个体分在同一组中,以组为单位进行选择,并通过该组个体的特点进行高斯搜索生成新的群体.这样使得GA在搜索过程中不仅可以很好地保持个体的多样性,并且可以提高解的精确度.通过对11个函数(单峰和多峰)的仿真实验,证明了采用新的选择算子后,GA在求解问题的精确度上有了很大地改善.
【总页数】6页(P44-49)
【作者】陈有青;徐蔡星;钟文亮;张军
【作者单位】中山大学,软件学院,广州,510275;中山大学,软件学院,广州,510275;中山大学,计算机科学系,广州,510275;中山大学,计算机科学系,广州,510275
【正文语种】中文
【中图分类】TP301
【相关文献】
1.一种基于混合概率选择算子的改进遗传算法 [J], 赵鑫宁;喻歆;吴锡
2.一种改进选择算子的遗传算法在泊松曲线沉降预测模型中的应用 [J], 谢盛嘉
3.一种改进选择算子和基于小生境的遗传算法 [J], 陈友文
4.基于改进的选择算子和交叉算子的遗传算法 [J], 曹道友;程家兴
5.一种基于混合概率选择算子的改进遗传算法 [J], 赵鑫宁;喻歆;吴锡;
因版权原因，仅展示原文概要，查看原文内容请购买。

一种求解TSP问题的改进遗传算法
符一平;陈光喜
【期刊名称】《桂林电子科技大学学报》
【年(卷),期】2007(027)004
【摘要】遗传算法(GA)是基于生物进化论的一种全局优化搜索算法,是求解TSP问题的一种方法,但它存在如何较快地找到最优解并防止"早熟"收敛的问题.结合TSP 问题最优解一般包含城市与其最近城市的相连的特点,提出了贪婪两点插入变异算子,改进了启发式杂交算子,并根据个体适应度与群平均适应度根据个体的适应度赋予不同的变异概率,使得较好的个体探测路径,较差个体开发新个体.对初始群体作局部优化提高其质量加快算法的收敛速度,最优个体连续几代一直保留,则采用局部微调算子使子代中的最优个体跳离局部解.通过实验分析,改进的算法能较快的收敛到TSP问题的已知最优解;其测试结果与国际标准测试库TSPLIB中的最优路径相比,或接近或优于.
【总页数】4页(P287-290)
【作者】符一平;陈光喜
【作者单位】桂林电子科技大学,数学与计算科学学院,广西,桂林,541004;桂林电子科技大学,数学与计算科学学院,广西,桂林,541004
【正文语种】中文
【中图分类】TP18
【相关文献】
1.一种改进的求解TSP问题的遗传算法 [J], 陈智军
2.一种改进的遗传算法求解TSP问题 [J], 张晓玲
3.一种基于改进遗传算法的TSP问题求解方法 [J], 纪怀猛;蔡海滨
4.一种改进的求解TSP问题的遗传算法 [J], 陈智军
5.一种求解TSP问题的改进遗传算法 [J], 杨华芬; 魏延
因版权原因，仅展示原文概要，查看原文内容请购买。