首页资源分类其它科学普及 > 遗传算法原理及应用

遗传算法原理及应用

已有 453308个资源

下载专区

上传者其他资源

文档信息举报收藏

标    签: 遗传算法

分    享:

文档简介

关于遗传算法的简单介绍,能清楚遗传算法的原理。

文档预览

中国科技论文在线 http://www.paper.edu.cn 遗传算法理论与应用发展研究 汪刚强1,胡峰松1,刘佳豪2* (1. 湖南大学信息科学与工程学院,长沙 410082; 2. 中国人民解放军 95916 部队,武汉 430077) 摘要:遗传算法是一种仿生优化算法,它是借鉴生物界自然选择和遗传机制发展起来的随机 搜索算法。近年来,遗传算法作为一种实用、高效、鲁棒性的优化技术发展极为迅速,受到 了越来越多的国内外学者的广泛关注。本文简要回顾了遗传算法的发展过程和研究现状,重 点介绍了算法的主要特点、基本理论及其设计步骤,并将它和传统算法作了比较。最后,指 出了相关的研究方向和应用领域。 关键词: 遗传算法;适应值函数;选择;交叉;变异; 中图分类号:TP301.6 The Research of Theory and Application Development for the Genetic Algorithm WANG Gangqiang1, HU Fengsong1, LIU Jiahao2 (1. Information Science and Engineering College,Hunan University,Changsha 410082; 2. The People's Liberation Army Troop 95916,Wuhan 430077) Abstract: Genetic algorithm is a bionic optimization algorithm, which is a random search algorithm developed by using natural selection and genetic mechanism of the biosphere for reference. In recent years, genetic algorithm received extensive attention of more and more scholars both at home and abroad because of its rapid development as a practical, efficient and robust optimization technology. This paper briefly reviews the development process and the research status of genetic algorithm. The paper mainly introduces the main characteristics, basic theory and its design steps, and makes it compared with traditional algorithms. Finally, the paper points out that the related research direction and application domains. Key words: genetic algorithm; fitness function; selection; crossover; mutation; 1 引言 遗传算法(Genetic Algorithm,GA)起源于对生物系统所进行的计算机模拟研究。美国 Michigan 大学 Holland 教授及其学生受到生物模拟技术的启发,创造出了一个基于生物遗传 和进化机制的适合于复杂系统优化的自适应概率优化技术——遗传算法。1976 年,Holland 学生 Bgaley 在他的博士论文中首次提出了“遗传算法”一词。1975 年,Holland 教授系统论述 了遗传算法和人工自适应系统[1]。1975 年,DEJONG 建立了遗传算法的工作框架[2]。1989 年,Goldberg 系统地总结了遗传算法的主要研究成果,全面完整地论述了遗传算法的基本原 理及其应用[3]。1991 年,Davis 介绍了遗传算法在科学计算、工程技术和社会经济中的大量 实例[4]。1992 年,KOZA 提出了遗传编程的概念[5]。国外好多学者也证明了遗传算法在太空 应用中要优于传统方法。另外,自 1985 年以来,国际上已召开了多次遗传算法的学术会议 和研讨会,国际遗传算法学会组织召开的 ICGA(International Conference on GA)会议和 FOGA(Workshop on Foundation of GA)为研究和应用遗传算法提供了国际交流的机会。从遗 传算法的整个发展历程来看,20 世纪 70 年代是兴起阶段,80 年代是发展阶段,90 年代是 作者简介:汪刚强(1982 年-),男,硕士,主要研究方向:分布式系统. E-mail: wgq_ccc@163.com -1- 中国科技论文在线 http://www.paper.edu.cn 高潮阶段。延续发展至今,遗传算法不论是在应用上、算法设计上,还是基础理论上,均取 得了较大的发展,已成为信息科学、计算机科学、运筹学和应用数学等诸多学科所共同关注 的热点研究领域。 2 遗传算法的特点 遗传算法是一种宏观意义下的仿生算法。它是基于 Darwin 的进化论和 Mendel 的遗传 学说,通过模拟 Darwin“优胜劣汰、适者生存”的原理激励好的结构,和通过模拟 Mendel 遗 传变异理论在迭代过程中保持已有的结构,同时寻找更好的结构。作为一种随机的优化与搜 索方法,遗传算法有着鲜明的特点[6]: (1)遗传算法的操作对象是一组可行解,而非单个可行解;搜索轨道有多条,而非单条, 因而具有良好的并行性。 (2)遗传算法只需利用目标的取值信息,而无需梯度等高价值信息,因而适用于任何大 规模、高度非线性的不连续多峰函数的优化以及无解析表达式的目标函数的优化,具有很强 的通用性。 (3)遗传算法择优机制是一种“软”选择,加上其良好的并行性,使它具有良好的全局优 化性和稳健性。 (4)遗传算法操作的可行解集是经过编码化的,目标函数解释为编码化个体的适应值, 因而具有良好的可操作性与简单性。 (5)基本思想简单,运行方式和实现步骤规范,便于具体使用。 然而,遗传算法作为一种优化方法,它也存在自身的局限性[7]:编码不规范及编码存在 表示的不准确性;单一的遗传算法编码不能全面地将优化问题的约束表示出来;通常的效率 比其他传统的优化方法低;容易出现过早收敛;对算法的精度、可信度、计算复杂性等方面, 还没有有效地定量分析。 3 遗传算法基本原理 遗传算法的基本思想是从代表问题可能潜在解集的一个种群开始的,一个种群由经过基 因编码的一定数目的个体组成,初始种群产生之后,按照适者生存和优胜劣汰的原则,逐步 进化产生出越来越好的近似解。在每一代,根据问题域中个体的适应度大小选择个体,并借 助自然遗传学的遗传算子进行交叉和变异,产生出代表新的解集的种群。这个过程将导致种 群向自然进化一样的后代种群比前代更加适应环境,末代种群中的最优个体经过解码,可以 作为问题近似最优解。在遗传算法的实现过程中,主要涉及五个要素:编码方案、初始种群 的设定、适应值函数、遗传算子的设计和控制参数的设定。 3.1 遗传算法流程 遗传算法是一个以适应度函数为依据,通过对群体个体施加遗传操作,实现群体内个体 结构重组的迭代处理过程。它的基本步骤如下:①确定合适的编码方案,将解空间与编码对 应;②根据规则确定适应度函数;③设计遗传策略,主要是遗传算子的选择和运行参数的确 定;④随机产生初始种群;⑤根据染色体编码计算种群中个体的适应度,作为选择操作的依 据;⑥以确定好的遗传算子和运行参数来产生新个体;⑦对种群性能进行判断,以此决定算 法运行与否。运算流程[8]如图 1 所示: -2- 中国科技论文在线 http://www.paper.edu.cn 图1 遗传算法运算流程图 Fig.1 the Flow Chart of Genetic Algorithm Operation 3.2 编码方案 在编码方面,标准遗传算法(SGA: Standard Genetic Algorithm)采用二进制编码[1]方式, 将问题的一个解表示成一个长度为 l 的二进制串,作为一个个体, l 称为链长。其优点在于 编码、解码操作简单,交叉、变异等遗传操作便于实现,而且便于利用模式定理[1]进行理论 分析等;其缺点在于,不便于反映所求问题的特定知识。对于一些连贯函数的优化问题等, 由于遗传算法的随机特性而使得其局部搜索能力较差,当链长较小时,可能达不到精度要求; 而链长较大时,虽然能提高精度,但却会使算法的搜索空间急剧扩大。后来许多学者对遗传 算法的编码方式进行了改造。例如,为改善遗传算法的计算复杂性,提高运算效率,提出了 格雷码编码[9]、浮点数编码、符号编码方法[10]等;为便于利用求解问题的专门知识,便于相 关近似算法之间的混合使用,提出了形式编码法[11]等。 3.3 初始种群的设定 产生初始种群的方法通常有两种。一种是完全随机的方法产生,适合于对问题的解无任 何先验知识的情况;另一种是有某些先验知识转变为必须满足的一组要求,然后再满足这些 要求的解中随机选取样本。选择哪种产生初始种群的方法要根据要解决的实际问题来确定。 3.4 适应值函数(Fitness Function) 适应值函数的选取直接影响到遗传算法的收敛速度以及能否找到最优解,因为遗传算法 在进化搜索中基本不利用外部信息,仅以适应值函数为依据,利用种群中每个个体的适应值 来进行搜索。适应值函数设计要满足许多条件,如单值、连续、非负、最大化等。因为适应 值函数的复杂度是遗传算法复杂性的主要组成部分,所以适应值函数的设计应尽可能简单, 使计算的时间复杂度最小。 -3- 中国科技论文在线 http://www.paper.edu.cn 3.5 遗传算子的设计 遗传算法对实际问题进行优化的过程主要依靠三个算子的操作:选择、杂交和变异。 (1)选择算子(selection) 从群体中选择优胜个体,淘汰劣质个体的操作叫选择。选择的目的是为了从当前群体中 选出优良的个体,使他们有机会作为父代繁殖下一代子孙。判断个体优良与否的标准是他们 的适应值 fi 。除 SGA 采用的轮盘赌选择法外,还有随机遍历抽样法、局部选择法、锦标赛 选择法、精英选择策略等[7]。 (2)杂交算子(crossover) 在自然界生物进化过程中起核心作用的是生物遗传基因的重组加上少量的变异,因此, 遗传算法中起核心作用的是遗传操作中的杂交算子。杂交是遗传算法获得新优良个体的最重 要手段。所谓杂交是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。 SGA 采用的是单点杂交,分两步进行:首先对配对库(经选择操作后形成的父代群体) 中的个体进行随机配对;其次,在配对个体中随机设定一个杂交点,配对个体按杂交概率彼 此交换杂交点后的信息。如下图 2 所示: 图 2 单点交叉 Fig.2 one-point crossover 常见的杂交方式除单点杂交外还有多点杂交、均匀杂交等。 多点杂交是随机选择多个杂交点,在杂交点之间的基因间续地相互交换,产生两个新的 后代。多点杂交的思想源于控制个体特定行为的染色体表示信息的部分无须包含于邻近的子 串,多点杂交的破坏性可以促进解空间的搜索,避免过早收敛。下面所示是两点杂交的示意 图: 图3 两点交叉 Fig.3 two-point crossover (3)变异算子(mutation) 变异是一个重要的遗传机制。如果没有变异,遗传过程经常收敛到局部最优解。变异可 以把搜索空间扩大到整个解空间。变异本身是一种局部随机搜索,它与选择、杂交算子结合 在一起,保证了遗传算法的有效性,使遗传算法具有全局搜索能力,保持了种群的多样性, 防止早熟。在变异操作中,变异概率不易太大,如果变异概率大于 0.5,遗传算法就退化为 随机搜索,而遗传算法的一些重要的数学特性和搜索能力将不复存在。 -4- 中国科技论文在线 http://www.paper.edu.cn 3.6 控制参数的设定 遗传算法中的控制参数选择非常关键,控制参数的不同选取会对遗传算法的性能产生较 大的影响,影响到整个算法的收敛性。这些参数包括群体规模 N、进化中止条件、交叉概率 Pc 、变异概率 Pm 等。一般来说,种群规模较大时可以同时处理更多的解,因而容易找到最 优解,其缺点是增加了每次迭代的时间。种群规模一般选择 20~100 之间的偶数。 杂交概率决定了杂交操作的频率。杂交频率越高,收敛速度越快,因此一般选取较大的 杂交概率,但太高的概率也可能导致过早收敛,所以一般选择在 0.4~0.99 之间。变异概率的 选取一般受种群规模、染色体链长等因素的影响,若选取高的变异概率,虽然增加了样本模 式的多样性,但可能会退化为随机搜索,一般选择在 0.0001~0.1 之间。 这些参数都需要根据经验人为地设定。对于具体问题,衡量参数设置恰当与否,要依据 多次运行的收敛情况和解得质量来判断。如果调整参数难以有效地提高遗传算法的性能,则 往往需要借助对遗传算法本身的改进。改进的手段可以是多方面的,如适应值动态调整、引 入自适应杂交概率和变异概率等。 4 与传统算法的比较 4.1 遗传算法与启发式算法的比较 启发式算法是指通过寻求一种能产生可行解的启发式规则,找到问题的一个最优解或近 似最优解。该方法求解问题的效率较高,但是它对每一个所求的问题必须找出其特有的启发 式规则,这个启发式规则一般无通用性,不适用于其他问题。但遗传算法采用的不是确定性 规则,而是强调利用概率转换规则来引导搜索过程。 4.2 遗传算法与爬山法的比较 爬山法是直接法、梯度法和 Hessian 法的通称。爬山法首先在最优解可能存在的地方选 择一个初始点,然后通过分析目标函数的特性,有初始点移到一个新的点,然后再继续这个 过程。爬山法的搜索过程是确定的,它通过产生一系列的点收敛到最优解(有时是局部最优 解),而遗传算法的搜索过程是随机的,它产生一系列随机种群序列。 4.3 遗传算法与穷举法的比较 穷举法就是对解空间内的所有可行解进行搜索,但是通常的穷举法并不是完全穷举法, 即不是对所有解进行尝试,而是有选择地尝试,如动态规划法、限界剪枝法。对于特定的问 题,穷举法有时也表现出很好的性能。但一般情况下,对于完全穷举法,方法简单易行,但 求解效率太低;对于动态规划法、限界剪枝法,则鲁棒性不强。相比较而言,遗传算法具有 较高的搜索能力和极强的鲁棒性。 4.4 遗传算法与盲目随机法的比较 与上述的搜索方法相比,盲目随机搜索有所改进,但它的搜索效率仍然不高。一般而言, 只有解在搜索空间中形成紧致分布时,它的搜索才有效。而遗传算法作为导向随机搜索方法, 是对一个被编码的参数空间进行高效搜索。 经过上面的探讨,能看到遗传算法与传统优化算法在本质上有着不同之处,主要有四个 不同[7]:①遗传算法搜索种群中的点是并行的,而不是单点;②遗传算法并不需要辅助信息 或辅助知识,只需要影响搜索方向的目标函数和相对应的适应度;③遗传算法使用概率变换 -5- 中国科技论文在线 http://www.paper.edu.cn 规则,而不是确定的变换规则;④遗传算法工作使用编码参数集,而不是自身的参数集。 5 遗传算法的研究方向 遗传算法是多学科结合与渗透的产物,它已经发展成为一种自组织、自适应的综合技术, 广泛应用在计算机科学、工程技术和社会科学等领域。其研究方向主要有下述几个方面[10]: (a)基础理论:遗传算法的数学理论并不完善,张玲[12]等对遗传算法的模式定理和隐性 并行性进行了分析研究,指出其不足并指出遗传算法本质上是一个具有定向制导的随机搜索 技术。在遗传算法中,群体规模和遗传算子的控制参数的选取非常困难,但它们有时必不可 少的试验参数。遗传算法还有一个过早收敛的问题,如何阻止过早收敛也是正在研究的问题 之一。 (b)分布式并行遗传算法:遗传算法在操作上具有高度的并行性,许多研究人员都在探 索并行机和分布式系统上高效执行遗传算法的策略。研究表明,只要通过保持多个群体和恰 当控制群体间的相互作用来模拟并发执行过程,即使不使用并行计算机,也能提高算法的执 行效率。遗传算法的并行性主要从三个方面考虑,即个体适应度评价的并行性、整个群体各 个个体适应度评价的并行性及子代群体产生过程的并行性。 (c)分类系统:分类系统属于基于遗传算法的机器学习中的一类,包括一个简单的基于 串规则的并行生成子系统,规则评价子系统和遗传算法子系统。分类系统被越来越多地应用 到科学、工程和经济领域,是目前遗传算法研究中一个十分活跃的方向。 (d)遗传神经网络:遗传神经网络包括连接级、网络结构和学习规则的进化。遗传算法 与神经网络相结合,成功地用于从分析时间序列来进行财政预算。在这些系统中,信号是模 糊的,数据是有噪声的,般很难正确给出每个执行的定量评价.如果采用遗传算法,就能克 服这些困难,显著提高系统性能。 (e)进化算法:模拟自然进化过程可以产生鲁棒的计算机算法——进化算法。遗传算法 是其三种典型的算法之一,其余两种算法是进化规划和进化策略,这三种算法是独立发展起 来的。 (f)人工生命与遗传算法:近几年来,通过计算机模拟再现种种生命现象,已达到对生命 更深刻理解的人工生命的研究正在兴起。已有不少学者对生态系统的演变、食物链的维持以 及免疫系统的进化等用遗传算法做了生动的模拟。遗传算法在实现人工生命中的基本地位和 能力究竟如何,这是值得研究的课题。 6 基于遗传算法的应用 遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题具体的领域, 对问题的种类有很强的鲁棒性,所以广泛应用于许多学科。下面是遗传算法一些主要的应用 领域。 1.函数优化:函数优化时遗传算法的经典应用领域,也是对遗传算法进行性能评价的常 用算例。可以用各种各样的函数来验证遗传算法的性能。对一些非线性、多模型、多目标的 函数优化问题,使用遗传算法可得到较好的效果[13]。 2.组合优化:随着问题规模的增大,组合优化问题的搜索空间也急剧扩大,有时在目前 计算机上用枚举法很难甚至不能求解出问题的最优解,而遗传算法就是寻求这种满意解得最 佳工具之一。遗传算法研究在求解旅行商问题、0-1 背包问题、装箱问题、布局优化、图形 划分问题等各种具有 NP 问题中得到成功的应用[3,14,15],实践证明,遗传算法对于组合优化中 -6- 中国科技论文在线 http://www.paper.edu.cn 的 NP 完全问题非常有效。 3.生产调度问题:采用遗传算法能够解决复杂的生产调度问题。在单件生产车间调度、 流水线生产车间调度、生产规划、任务分配[16,17]等方面,遗传算法都得到了有效地应用。 4.自动控制:在自动控制领域中有很多与优化相关的问题需要求解,遗传算法已在其中 得到了初步应用,并显示出了良好的效果。例如,基于遗传算法的模糊控制器优化设计[18], 用遗传算法进行航空控制系统的优化[19]等。` 5.机器人学:机器人是一类复杂的难以建模的人工系统,而遗传算法的起源来自于对人 工自适应系统的研究。例如,遗传算法已经在移动机器人路径规划[20]、机器人逆运动学求 解等方面得到很好的应用。 6.图像处理:图像处理是计算机视觉中的一个重要领域,在图像处理过程中,不可避免 地会存在一些误差,如何使这些误差最小是使计算机视觉达到实用化的重要要求,遗传算法 在这些图像处理的优化计算方面得到应用[21,22]。 7.遗传编程[5,23,24]:KOZA 发展了遗传程序设计的概念,他使用了以 LISP 语言所表示的 编码方法,算法基于一种树型结构所进行的遗传操作来自动生成计算机程序。 8.机器学习[25]:基于遗传算法的机器学习可用于调整人工神经网络的连接权,也可用于 神经网络结构的优化设计。 9.数据挖掘:数据挖掘是指大型数据库或数据仓库中提取隐含的、未知的、非平凡的及 有潜在应用价值的信息或模式,它是数据库研究中的一个很有应用价值的新领域,基于遗传 算法的特点,遗传算法可用于数据挖掘中的规则开采[26]。 10.信息战:遗传算法在信息战领域得到了初步应用[27]。使用遗传算法能够进行雷达目 标识别、数据挖掘、作战仿真、雷达辐射源、雷达天线优化设计、雷达目标跟踪、盲信号处 理、空间谱估计、天线设计等。 7 结论 遗传算法自诞生以来就受到许多学者的关注。经过 30 多年的不断发展,在基础理论和 算法设计研究上都取得了长足的进步,尤其是在越来越多的领域中得到成功应用。遗传算法 作为一种仿生优化算法,为复杂系统优化提供解决方案,实践证明其效果显著,被认为是 21 世纪有关智能计算中的关键技术之一。进入 21 世纪以来,应用领域将是遗传算法的主要 研究方向,同时其理论和技术研究也需要进一步深入完善,可引入新的数学工具和生物学的 新成果。 [参考文献] (References) [1]HOLLAND J H. Adaptation in natural and artificial systems [M].Ann Arbor:University of Michigan Press, 1975. [2]DEJONG K A. The analysis of the behavior of a class of genetic adaptive systems [D].Ann Arbor:University of Michigan,1975. [3]Goldberg D E. Genetic algorithms in search, Optimization and machine Learning [M].Boston: Addison-Wesley Longman Press,1989. [4]Davis L. Handbook of genetic algorithms [M]. Van Nostrand Reinhold,1991. [5] KOZA J R. Genetic programming:on the programming of computers by means of natural selection [M]. Cambridge:MIT Press,1992. [6]张文修,梁怡.遗传算法的数学基础(第 2 版)[M].西安:西安交通大学出版社,2003. -7- 中国科技论文在线 http://www.paper.edu.cn [7]雷英杰,张善文,李续武,周创明.MATLAB 遗传算法工具箱及应用[M].西安:西安电子科技大学出版 社,2005. [8]LU Yujun,LI Renwang,HAN Jin.Adaptive genetic algorithms for the job—shop scheduling problems.Proceedings of the 7th World Congress on Intelligent Control and Automation, WCICA’08,2008. [9]周明,孙树栋.遗传算法原理及应用[M].北京:国防工业出版社,2002. [10]王小平,曹立明.遗传算法——理论、应用与软件实现[M].西安:西安交通大学出版社,2002. [11] 贺 晓 丽 , 王 翠 萍 , 许 曰 滨 , 赵 志 刚 . 一 种 变 形 杂 交 算 子 —— 轮 转 杂 交 算 子 [J]. 计 算 机 工 程 与 应 用 , 2003.Vol.39,No.9:105-107. [12]张铃,张钹.统计遗传算法[J].软件学报,1997,8(5):335~344. [13]黄冀卓,王湛,马人乐.一种新的求解约束多目标化问题的遗传算法[J].计算机工程与应用,2006,42(23): 47-51. [14] 钱 志 勤 , 滕 弘 飞 , 孙 治 国 . 人 机 交 互 的 遗 传 算 法 及 其 在 约 束 布 局 优 化 中 的 应 用 [J]. 计 算 机 学 报,2001 ,24(5) :553~5581. [15] 王征应、石冰心.基于启发式遗传算法 QOS 组播路由问题求解[J].计算机学报,2001 ,24(1) :55~611. [16]耿汝年,须文波.基于自适应选择遗传算法的任务调度与分配[J].计算机工程,2008,34(3):43~45. [17]周琛琛.基于遗传算法的网格任务调度算法研究(D).安徽:安徽大学,2007. [18]李辉,韩红,韩崇昭.基于遗传算法的模糊逻辑控制器优化设计[J].西安交通大学学报,2002,36(4): 385~389. [19] 虞 蕾 , 赵 红 , 赵 宗 涛 . 一 种 基 于 遗 传 算 法 的 航 迹 优 化 方 法 [J]. 西 北 大 学 学 报 : 自 然 科 学 版 , 2006,36(2):205~208,213. [20] 王 科 俊 , 徐 晶 , 王 磊 等 . 基 于 可 拓 遗 传 算 法 的 机 器 人 路 径 规 划 [J]. 哈 尔 滨 工 业 大 学 学 报 , 2006,38(7):1135~1138. [21]赵应丁,刘金刚.基于遗传算法的指纹图像二值化算法研究[J].计算机工程,2006,32(7):169~171. [22]王建锋,吴庆标.分层遗传算法实现图像边缘检测[J].计算机工程与应用,2006,42(14):95~96,15l. [23] KOZA J R. Genetic programming II:automatic discovery of reusable programs [M]. Cambridge: MIT Press, 1994. [24] KOZA J R,BENNETT III F H,ANDRE D,et al. Four problems for which a computer program evolved by genetic programming is competitive with human performance[C]//Proc of IEEE International Conference on Evolutionary Computation.1996:1~10. [25]Tom M.Mitchell . 机器学习[M]. 曾华军 , 张银奎.北京:机械工业出版社,2003. [26] 张 细 政 , 邢 立 宁 , 伍 栖 . 基 于 决 策 树 的 遗 传 算 法 在 数 据 挖 掘 领 域 的 应 [J]. 哈 尔 冰 工 程 大 学 学 报,2006,27(7):384~388. [27]扬俊安,陈怡,钟子发.标准遗传算法的改进及其在信息战领域应用展望[J].中国人民解放军电子工程学 院学报,2002,21(3):41~44. -8-

Top_arrow
回到顶部
EEWORLD下载中心所有资源均来自网友分享,如有侵权,请发送举报邮件到客服邮箱bbs_service@eeworld.com.cn 或通过站内短信息或QQ:273568022联系管理员 高进,我们会尽快处理。