《GA遗传算法概述》由会员分享，可在线阅读，更多相关《GA遗传算法概述（5页珍藏版）》请在金锄头文库上搜索。
1、遗传算法及其应用 摘要：遗传算法是一种基于生物自然选择和遗传机理的随机搜索与优化方法。近年来,由于遗传算法在求解复杂问题中的巨大潜力及其在工业工程领域的成功应用,受到了国内外学者的广泛关注。本文详细介绍了遗传算法的基本原理、主要特征以及主要应用。关键词：遗传算法；选择算子；交叉算子；变异算子Genetic Algorithm and Its ApplicationAbstract: Genetic algorithm is a random search and optimization method based on biological natural selection and gene
2、tic mechanism. In recent years,genetic algorithm has attracted many domestic and overseas scholars attention for its potential in solving many complex problems and its successful application in the field of industrial engineering, This paper introduces the basic principle ,the main characteristics a
3、nd applications of genetic algorithm in detail.Key words: genetic algorithm, selection operator, crossover operator, mutation operator1. 遗传算法发展历史1967年，Holland的学生Bagley在其博士论文中首次提出“遗传算法”1。1970年，Cavicchio把遗传算法应用于模式识别2。Hollstien最早把遗传算法应用于函数优化3。20世纪70年代，Holland教授提出了遗传算法的基本定理模式定理4，从而奠定了遗传算法的理论基础。1975年，Hol
4、land教授出版了第一本系统论述遗传算法和人工自适应系统的专著Adaptation in Natural and Artificial Systems。同年，K.A.De Song在博士论文遗传自适应系统的行为分析结合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，为遗传算法及其应用打下了坚实的基础，他所得出的许多结论迄今仍具有普遍的指导意义。2. 遗传算法理论 2.1 遗传算法的基本思想 遗传算法借鉴 Darwin 的物竞天择、优胜劣汰、适者生存的自然选择和自然遗传的机理。与传统搜索算法不同，遗传算法从一组随机产生的初始解（称为群体）开始。群体中的每个个体是问题的一个解
5、，称为“染色体”，这些染色体在后代迭代过程中不断进化。遗传算法主要通过选择、交叉和变异来实现,其本质是一种求解问题的高效并行全局搜索方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法是一个迭代的过程，在每次迭代过程中都保留一组候选解，按解的好坏进行排序，按照约束条件从中选取一组解，利用遗传算法中的三个算子对其进行计算，产生新一代的候选解，重复此过程直到满足某种收敛条件为止。2.2 遗传算法的数学基础定义1： 模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集（0,1，*）的字符串，符
6、号*代表（0,1）中的任意字符。例如：10*1定义2： 模式H中确定位置的个数称为模式H的阶，记O(H)。例如O(10*1)=3。定义3： 模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距，记作(H)。例如(10*1)=4。模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。定义4： 个体即要处理的对象、结构，也就是可行解。定义5： 适应度即可行解对应的适应函数的值，表现为个体对于环境的适应程度。 模式定理：具有低阶、短定义距以及平均适应度高于
7、种群平均适应度的模式在子代中呈指数增长。模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。2.3 群体的规模群体规模的确定，根据模式定理，受遗传操作中选择算子的影响最大。一般来说，群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险越小。但群体规模太大，从计算效率着眼，群体越大其适应度评估次数增加，所以计算量增加，从而影响计算性能。太小会使遗传算法的搜索空间中分布范围有限，因而搜索有可能停在未成熟阶段，引起早收敛现象。初始群体的确定通常采用以下两个方法：（1）用随机方法产生，只有这样选取才能达到所有状态的遍历，使最优解在遗传算法的进化中最终得
8、以生存。（2）使用其他优化方法或启发式方法选取使初始群体更优良。2.4 遗传算子简介2.4.1 选择算子把当前群体中的个体按与适应值成比例的概率f(xi)f(xi)复制到新的群体中，遗传算法中最常用的选择方式是轮盘赌选择方式。轮盘赌选择步骤如下：（1）求群体中所有个体的适应值总和S；（2）产生一个0到S之间的随机数M；（3）从群体中编号为1的个体开始，将其适应值与后续个体的适应值相加，直到累加和大于等于M，则停止。其中，那个最后加进去的个体即为新选择的个体。选择算子作用的效果是提高了群体的平均适应值及最差的适应值，低适应值的个体趋于被淘汰，高适应值的个体趋于被复制，但是是以损失群体的多样性为代
9、价，选择算子并没有产生新的个体，当然群体中最好个体的适应值不会改进。 2.4.2 交叉算子交叉算子（又称杂交算子）每次作用在种群随机选取的两个个体上产生两个不同的子个体，它们一般与父个体不同，但又包含父个体的遗传物质，交叉运算是遗传算法区别于其它进化算法的重要特征。交叉规则内容包括两个方面：（1）从种群中对个体随即配对，并按预定的交叉概率来决定是否进行交叉操作。（2）设定个体的交叉点，并对这些点前后的配对个体的基因相互交换。例如：首先产生一个1到h（其中h为染色体分量的个数）的随机数i（称为交叉点），然后配对的两个个体相互交换从（i+1）到h的位子，如对以下两个数进行交叉且交叉点选择在2，即i
10、=2，则 1 1 |0 1 1 1 0 1 |1 0 1 0对种群要确定交叉概率Pc。随机选择NPc个个体进行交叉，其余不变。显然，利用选择、交叉算子可以产生具有更高平均适应值和更好个体的群体。但仅仅如此，容易导致局部最优解。 2.4.3 变异算子变异算子能使个体发生突然变异，导入新的遗传信息，使寻优有可能指向未探知区域，是提高全局最优搜索能力的有效步骤，也是保持群体差异，防止过早出现收敛现象的重要手段。以一个很小的变异概率Pm，随机的改变染色体上的某个基因（0110），具有增加群体多样性的效果。例如：010 0002.5 遗传算法求解步骤（1） 选择问题解的一个编码，给出一个有N个染色体的初
11、始群体pop(1)，t=1。 （2） 对群体中的每一个染色体popi(t)，计算它的适应函数值f(xi)。（3） 若停止规则满足，则算法停止，否则计算概率Pi=f(xi)f(xi)，并以此概率分布，从pop(t)中随机选取N个染色体构成一个新的种群newpop(t)。(4) 通过交叉（交叉概率为Pc），得到N个染色体的crosspop(t+1)。(5) 以较小的变异概率Pm，使得某染色体的一个基因发生变异，形成新的群体mutpop(t+1)。 令t=t+1，pop(t)=mutpop(t)，重复第（2）步。流程如图一所示。2.6 遗传算法特点 遗传算法的优越性：（1）作为数值求解方法具有普适性
12、，对目标函数几乎没有要求，总能以极大概率找到全局最优解。（2）遗传算法在求解很多组合优化问题时，不需要很高的技巧和对问题有非常深入的了解，在给问题的决策变量编码后，其计算过程比较简单。（3）与其他启发式算法有较好的兼容性，易于别的技术相结合，形成更优的问题解决方法。遗传算法的欺骗性问题：（1）在遗传进化的初期，通常会产生一些超常个体，按比例选择，这些个体竞争力太强而控制了选择过程，影响算法的全局优化性能。（2）在遗传进化的后期，即算法接近收敛时，由于种群中个体适应度差异较小，继续优化的潜能降低，可能获得某个局部最优解。3. 遗传算法的改进与应用 遗传算法的初期应用研究主要围绕组合优化问题求解，
13、但近年来已迅速扩展到机器学习、 设计规划、神经网络优化、自律分布控制和人工生命等众多领域。此外，还在核反应控制和喷气发动机设计等工程应用中进行了十分有意义的尝试。下面是遗传算法的一些主要应用领 域 7。 3.1 在组合优化中的应用组合优化问题是遗传算法最基本也是最重要的应用领域。所谓组合优化问题是指在离散 的、有限的数学结构上，寻找一个满足给定约束条件并使其目标函数达到最大或最小的解。在日常生活中，特别是在工程设计中，有许多这样的问题。最典型的是旅行商问题和背包问题 。 3.2 在生产调度中的应用在很多情况下，生产调度问题建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因
14、简化的太多而使得求解结果与实际相差甚远。目前，在现实生产中，主要靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产调度、任务分配等方面遗传算法都得到了有效的应用。3.3在自动控制中的应用在自动控制领域中，有很多与优化相关的问题需要求解。例如，用遗传算法进行航空控制系统的优化、设计空间交会控制器等都显示出在这些领域中应用的可能性。3.4 在图像处理中的应用 图像处理是计算机视觉中的一个重要研究领域，目前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。3.5 在机器学习方面的应用 基于遗传算法的机器学习是当前遗传算法应用研究的热点，特别是分
15、类器系统，在很多领域中的到了应用。3.6 遗传算法在数据挖掘方面的应用 数据挖掘是近几年出现的数据库技术，它能够从大型的数据库中提取隐含、未知、有潜力、有应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题，数据库可看作搜索空间，挖掘算法看作是搜素策略。因此，应用遗传算法在数据库中进行搜索，对随机产生的一组规则进化，直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则。由于传统遗传算法的缺陷，现已提出许多改进后的遗传算法，例如：（1）免疫遗传算法(Immune Genetic Algorithm,IGA)，免疫遗传算法就是将免疫理论(Immune Algorithm,IA)和基本遗传算法(Simple Genetic Algorithm,SGA)各自的优点结合起来的一个多学科相互交叉、渗透的优化算法。该算法既保留了遗传算法的搜索特性，又利用了免疫算法的多机制求解多目标函数最优解的自适应特性，在很大程度上避免了“早熟”，收敛于局部极值。（2）基于模拟退火的混合遗传算法，遗传算法和模拟退火算法都是启发式随机搜索算法，遗传算法局部搜索能力较差，但把握搜索过程总体的能力较强，模拟退火算法具有较强的局部搜索能力。基于模拟退火的混合遗传算法是将遗传算法与模拟退火算法相结合而构成的一种优化算法。与基本的遗
