第8讲-MATLAB遗传算法工具箱

MATLAB遗传算法工具箱第8讲2现代优化算法现代优化算法禁忌搜索算法模拟退火算法遗传算法人工神经网络蚁群算法粒子群算法混合算法特点：•基于客观世界中的一些自然现象；•建立在计算机迭代计算的基础上；•具有普适性，可解决实际应用问题。3现代优化算法现代优化算法又称智能优化算法或现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据,而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。4现代优化算法的特点它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。5现代优化算法的特点1)不依赖于初始条件；2)不与求解空间有紧密关系,对解域无可微或连续的要求;容易实现，求解稳健。3)但收敛速度慢,能获得全局最优;适合于求解空间不知的情况。4)模拟退火算法和遗传算法等可应用于大规模、多峰多态函数、含离散变量等全局优化问题;求解速度和质量远超过常规方法。6常用的现代优化算法遗传算法GeneticAlgorithm，简称GA模拟退火算法SimulatedAnnealing，简称SA禁忌搜索算法TabuSearch，简称TS……7神经网络算法群智能算法1.蚁群算法(AntColonyOptimization)2.粒子群算法(ParticleSwarmOptimization)微分进化算法（DifferentialEvolution）常用的现代优化算法（续）8搜索示例：三个孩子的年龄(1)两个多年未见的朋友相遇，聊了很多事情。…A：既然你是数学教授，那你帮我算这个题，今天是个特殊日子：我三个儿子都在今天庆祝生日！那么你能算出他们都有多大吗？B：好，但你得跟我讲讲他们的情况。A：好的，我给你一些提示，他们三个年龄之积是36.B：很好，但我还需要更多提示。9三个孩子的年龄(2)A：我的大儿子的眼睛是蓝色的。B考虑了一下说，但是，我还有一点信息来解决你的这个难题。B：哦，够了，B给出了正确的答案，即三个小孩的年龄。A：他们三个年龄之和等于那幢房子的窗户个数。A指着对面的一幢房子说。10三个孩子的年龄(3)根据对话信息，用搜索的方法来解此问题。信息1:三个小孩年龄之积为36只有以下8种可能，搜索范围减少至8种情况:第一个小孩年龄36181299664第二个小孩年龄12342633第三个小孩年龄1111212311三个孩子的年龄(4)信息2:三个小孩年龄之和等于窗户数第一个小孩年龄36181299664第二个小孩年龄12342633第三个小孩年龄11112123窗户数:3821161413131110如果窗户数为38、21、16、14、11、10即可得出答案B还需信息，即窗户数为13.则可能为(9、2、2)或(6、6、1)信息2:大儿子眼睛是蓝色的得答案：(9、2、2)12典型问题——旅行商问题（Travelingsalesmanproblem,TSP）给定n个城市和两两城市之间的距离，要求确定一条经过各城市当且仅当一次的最短路线。123412181032搜索示例：TSP问题13典型问题——旅行商问题（Travelingsalesmanproblem,TSP）计算复杂度：指数灾难城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325yearTSP的搜索的困难14遗传算法(GeneticAlgorithm)进化算法(EvolutionaryAlgorithm)15遗传算法(GA)Darwin(1859):“物竟天择，适者生存”JohnHolland(universityofMichigan,1975)《AdaptationinNaturalandArtificialSystem》遗传算法作为一种有效的工具，已广泛地应用于最优化问题求解之中。遗传算法是一种基于自然群体遗传进化机制的自适应全局优化概率搜索算法。它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工的方式对目标空间进行随机化搜索。16遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。遗传算法的搜索机制17局部全局遗传算法(GA)18Wehaveadream!!IamatthetopHeightis...Iamnotatthetop.Myhighisbetter!Iwillcontinue遗传算法(GA)GA-----第0代19DeadoneNewone遗传算法(GA)GA----第1代20Notatthetop,ComeUp!!!遗传算法(GA)GA----第?代21IamtheBEST!!!遗传算法(GA)GA----第N代22适者生存(SurvivaloftheFittest)GA主要采用的进化规则是“适者生存”较好的解保留，较差的解淘汰遗传算法(GA)23达尔文的自然选择说遗传（heredity）：子代和父代具有相同或相似的性状，保证物种的稳定性；变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。自然选择过程是长期的、缓慢的、连续的过程。生物进化理论和遗传学的基本知识24遗传学基本概念与术语染色体（chromosome）：遗传物质的载体；脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；生物进化理论和遗传学的基本知识25遗传学基本概念与术语基因型（genotype）：遗传因子组合的模型；表现型（phenotype）：由染色体决定性状的外部表现；11111111110111生物进化理论和遗传学的基本知识26遗传学基本概念与术语基因座（locus）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（allele）；个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合，该集合内个体数称为种群的大小；生物进化理论和遗传学的基本知识27遗传学基本概念与术语进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;生物进化理论和遗传学的基本知识28遗传学基本概念与术语选择（selection）：指决定以一定的概率从种群中选择若干个体的操作；复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;交叉（crossover）：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;生物进化理论和遗传学的基本知识29遗传学基本概念与术语变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。生物进化理论和遗传学的基本知识30遗传算法的基本思想遗传算法的基本思想31生物进化与遗传算法对应关系生物进化遗传算法适者生存适应函数值最大的解被保留的概率最大个体问题的一个解染色体解的编码基因编码的元素群体被选定的一组解种群根据适应函数选择的一组解交叉以一定的方式由双亲产生后代的过程变异编码的某些分量发生变化的过程环境适应度函数32遗传算法的基本思想遗传算法先将搜索结构编码为字符串形式,每个字符串结构被称为个体。然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。常用的遗传算子有选择、交叉、变异。33遗传算法把许多很复杂的应用问题,化为简单的位串形式的编码来表示.编码:将问题结构变换为位串形式编码表示的过程.解码:将位串形式的编码表示变换为原问题的结构的过程,也叫译码,它是编码的反过程.遗传算法最常用的编码方法的二进制编码。除此之外，还有其他的编码方法，如：浮点数编码方法,Gray(格雷，灰度)编码，符号编码等。编码与解码34二进制编码与解码参数编码对应关系如下：δ=(B－A)／(2L－1)00000000…00000000=0A00000000…00000001=1A+δ……11111111…11111111=2L-1B假设某一参数取值范围是[A,B]。我们用长度为L的二进制编码串来表示该参数，将[A,B]等分成(2L-1)个子部分，记每一个等分的长度为δ，则它能够产生(2l)种不同的编码，35假设某一个个体的编码是：X：xLxl-1xl-2…x2x1则上述二进制编码对应的解码公式为(转化为十进制形式)：11112221LLiiiiLiiBAxAxAx二进制编码与解码(续)36对TSP问题可以按一条回路城市的次序进行编码。比如码串“134567829”表示从城市1开始，依次是城市3,4,5,6,7,8,2,9，最后回到城市1。一般情况是从城市w1开始，依次经过城市w2,……，wn，最后回到城市w1，我们就有如下编码表示：w1w2……wn由于是回路，记wn+1=w1。要注意w1,w2,……，wn是互不相同的。符号编码方法举例37通过适应度函数来决定染色体的优劣程度,它体现了自然进化中的优胜劣汰原则.对于优化问题,适应度函数就是目标函数,要能够有效地反映每一个染色体与问题最优解染色体之间的差距.例如：TSP的目标是路径总长度为最短，路径总长度的倒数就可以为TSP的适应度函数：其中wn+1=w1，d(wj,wj+1)表示两城市之间的距离。遗传算法的基本机理——适应度函数38适应度函数目标函数值到适应度函数的映射适应度函数值必须非负，任何情况下希望越大越好；而目标函数有正，有负；且目标函数和适应度间的关系也多种多样。如求最大值对应点时，目标函数和适应度变化方向相同；求最小值时，变化方向相反。因此存在目标函数值向适应度映射的问题。首先应保证映射后的适应度是非负的，其次目标函数的优化方向应对应于适应度增大的方向。39对最小化问题，一般采用如下适应度函数f(x)和目标函数g(x)的映射关系：其中：cmax可以是一个输入参数，或是理论上的最大值，或是到目前所有代（或最近的k代）之中见到的g(x)的最大值，此时cmax随着代数会有所变化。其它,0)(),()(maxmaxcxgxgcxf目标函数值到到适应度函数的映射(续)适应度函数40对最大化问题，一般采用下述方法：式中:cmin既可以是输入值也可以是当前最小值或最近的k代中的最小值。其它,0)(,)()(minmincxgcxgxf