您好,欢迎访问三七文档
遗传算法应用1遗传算法概述遗传算法(GeneticAlgorithm)是一种通过模拟自然进化过程搜索最优解的方法,它是由美国Michigan大学J.Holland教授于1975年首先提出来的,并出版了颇有影响的专著《AdaptaioninNaturalandArtificialSystems》,GA这个名称才逐渐为人所知,J.Hilland教授所提出的GA通常为简单遗传算法(SGA)。遗传算法是从代表问题可能潜在的解集的一个种群(population)开始的,而一个种群则由经过基因(gene)编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体,即多个基因的集合,其内部表现(即基因型)是某种基因组合,它决定了个体的形状的外部表现,如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此,在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂,往往进行简化,如二进制编码,初代种群产生之后,按照适者生存和优胜劣汰的原理,逐代(generation)演化产生出越来越好的近似解,在每一代,根据问题域中个体的适应度(fitness)大小挑选(Selection)个体,并借助于自然遗传学的遗传算子(geneticoperalors)进行组合交叉(crossover)和变异(mutation),产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境,末代种群中的最优个体经过解码(decoding),可以作为问题近似最优解。这些性质已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。是现代有关智能计算中的关键技术之一。2遗传算法的原理与特点2.1遗传算法的特点遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法。与传统的优化算法相比,主要有以下特点:2.1.1遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际值本身,而遗传算法处理决策变量的某种编码形式,使得我们可以借鉴生物学中的染色体和基因的概念,可以模仿自然界生物的遗传和进化机理,也使得我们能够方便的应用遗传操作算子。2.1.2遗传算法直接以适应度作为搜索信息,无需导数等其它辅助信息。2.1.3遗传算法使用多个点的搜索信息,具有隐含并行性。2.1.4遗传算法使用概率搜索技术,而非确定性规则。2.2遗传算法的原理遗传算法是的思想源于生物遗传学和适者生存的自然规律,是具有“生存+检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象,并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中,选择、交叉和变异构成了遗传算法的遗传操作。参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。作为一种新的全局优化搜索算法,遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显著特点,在各个领域得到了广泛应用,取得了良好效果,并逐渐成为重要的智能算法之一。2.3遗传算法的理论基础2.3.1模式定理模式是指个体基因串中的相似样板。在二进制编码中,模式是基于三个字符集(0,1,*)的字符串,符号*代表0或1。如:10**1。定义1出现在模式H中的0或1的数目称为模式H的阶,记作O(H)。如:O(10**1)=3。定义2模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距,记作δ(H)。如:δ(10**1)=4。模式定理:具有低阶、短定义距和平均适应度高于种群平均适应度的模式在后代中呈指数增长。2.3.2积木块假设积木块假设:遗传算法通过短定义距、低阶和高平均适应度的模式(积木块),在遗传操作下相互结合,最终接近全局最优解。模式定理保证了遗传算法找到全局最优解的可能性存在,而积木块假设指出了在遗传操作下能生成全局最优解。两者构成了分析遗传算法进化行为的基本理论。3遗传算法的应用3.1遗传算法应用举例遗传算法可以用于很多优化问题。一个问题可以有多余一个的解决方案,这些方案的品质不同,遗传算法产生候选姐姐犯案的种群,然后通过自然选择使这些解决方案进化,从而得到最优的解。著名的旅行推销问题(TSP):给定有限个城市N,以及两个城市之间旅行的费用(或距离),要找出花费最少(或路程最短)的路线,而每个城市都能到达,且仅到达一次后回到出发点。这样的问题很难通过组合搜索技术得到解决。TSP问题的搜索空间包含N个城市的所有可能组合,因此搜索空间的可能大小为N!。因为城市的数目可能很大,因此主调路径地检查是不可行的。TSP问题通常出现在运输和后勤应用中,例如,在学校所属区域内为接送孩子的校车安排路线,给回家的人送饭,为仓库的塔式起重机安排计划,安排收取邮件的卡车路线等。最近几年,TSP问题的规模不断扩大,研究人员使用不同的技术来解决这个问题。这些技术包括模拟退火、离散线性编程、神经网络、分支定界算法、马尔可夫链和遗传算法。遗传算法尤为适合解决TSP问题,因为这种算法可以直接地在搜索空间搜索可行的区域。3.2利用遗传算法解决TSP问题要解决TSP问题,首先要决定推销员路线的方法,最自然的方式是路径表示法。每个城市用字母或数字标明,城市间的录像用染色体表示,用合适的遗传操作来产生新的路线。假设有七个城市,用1~7来表示,在一个染色体中,整数的顺序表示推销员参观城市的顺序。例如,染色体表示图3-1所示的路线,销售员从城市1出发,到所有的其他城市参观一次并回到出发点。传统形式的交叉操作不能直接在TSP问题中使用,采用顺序交叉法,通过交换亲代染色体的交换部分得到两个自带染色体接下来将亲代最初城市按照最初的顺序排列,忽略另一个染色体中交换部分的城市。TSP采用两种突变操作:倒数交换和倒置。通过倒数交换操作简单地交换染色体中随机选择的两个城市。而倒置操作在染色体中选择两个随机的点,然后倒叙排列两点间的城市。创建TSP的遗传操作比较复杂,但是适应性函数比较简单。利用遗传算法,使用不同的染色体种群大小,不同的交叉率和不同的突变率进行测试,可以找到最佳路线。4总结遗传算法对于复杂的优化问题无需建模和进行复杂运算,只要利用遗传算法的算子就能寻找到问题的最优解或满意解。利用遗传算法可以把问题的候补解视为生物个体,而生物个体对环境有很高的适应能力,这样应用进化机构,就能够提供更好解答的候补解。
本文标题:遗传算法应用
链接地址:https://www.777doc.com/doc-2009859 .html