最优化理论与方法 遗传算法ppt课件.ppt
,最优化理论与方法之 遗传算法,报告人：罗九晖,目录,最优化方法概述 智能算法概述 遗传算法概述,经典精确优化算法（数值最优化）,经典近似优化算法（解析最优化）,智能算法（仿生算法、演化算法）,用来处理目标函数以及约束条件有具体的解析表达式且存在导数的情况。,通过以模拟物质变化过程或模拟生命体而设计的搜索方式为基础提出的算法。,通过最优解的性质建立迭代公式来求最优解。,1.最优化方法概述,数值优化算法和解析优化算法必须建立在目标函数存在导数的性质条件下进行，而在实际中碰到的很多优化问题的目标函数并不存在导数。,最优化方法概述 智能算法概述 遗传算法概述,2.智能算法,智能 是在任意给定的环境和目标条件下，正确制定决策和实现目标的能力。智能优化算法 则是将生物行为与计算机科学相结合，解决优化问题，制定最优化决策。,几种智能算法,禁忌搜索方式,蚁群算法,粒子群优化算法,人工神经网络,Equation of state calculations by Fast Computing Machines,Algorithms and the Optimal Allocation of Trials,Positive Feedback as a search strategy,A New optimizer using particle swarm theory,Tabu search,Turing Computability With Neural Nets,模拟退火模式,遗传算法,智能算法,各种算法模拟的自然现象,关于智能算法的几个形象比喻,为了找出地球上最高的山，一群有志气的袋鼠们开始想办法。1.兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。2.袋鼠喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。3.袋鼠们知道一只袋鼠的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只袋鼠做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。4.袋鼠们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的袋鼠，多产的袋鼠们自己就会找到珠穆朗玛峰。这就是遗传算法。,最优化方法概述 智能算法概述 遗传算法概述,3.遗传算法概述,用“袋鼠跳”问题来粗略领略遗传算法,（1）随机生成N个个体组成一个种群。第一批袋鼠被随意分散在山脉上。（2）完成种群中每个个体适应度的计算。得到袋鼠的位置坐标。（3）对个体做适应度评价。袋鼠爬得越高，越受我们喜爱，适应度越高。（4）用选择函数按某种规则择优选择。每隔一段时间射杀海拔低的袋鼠。（5）让个体基因交叉变异。让袋鼠交配并随机跳动。（6）选择子代。希望活下来的袋鼠是多产的，并在那里生儿育女。遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何 去“找”最优解。你不必去指导袋鼠向哪边跳，跳多远。而只要简单的“否定”一些表现不好的个体就行了。把那些总是爱走下坡路的袋鼠射杀。,3.1遗传算法的执行过程,（1）初始化。确定种群规模N、交叉概率Pc、变异概率Pm和置终止进化准则;随机生成N个个体作为初始种群X(0);置进化代数计数器t0。（2）个体评价。计算或估价X(t)中各个体的适应度。（3）种群进化。选择(母体)。从X(t)中运用选择算子选择出M/2对母体(MN)。交叉。对所选择的M/2对母体,依概率Pc执行交叉形成M个中间个体。变异。对M个中间个体分别独立依概率Pm执行变异,形成M个候选个体。选择(子代)。从上述所形成的M个候选个体中依适应度选择出N个个体组成新一代种群X(t+1)。（4）终止检验。如已满足终止准则,则输出X(t+1)中具有最大适应度的个体作为最优解,终止计算;否则转（3）。,遗传算法初窥,一个简单的遗传算法案例：,注意需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中有可能需要一定的循环次数才能达到这个最优结果。,3.2遗传算法的理论研究,（1）编码（2）适应度函数（3）遗传算子（4）参数选择（5）收敛性分析（6）欺骗问题（7）并行遗传算法,（1）编码&（2）适应度函数,（1）编码传统编码：二进制发展：a.格雷码编码；b.实数编码；c.十进制编码；d.非数值编码。,（2）适应度函数将目标函数转换成适应度函数一般应遵循两个原则:a.适应度必须非负;b.优化过程中目标函数的变化方向应与群体进化过程中适应度函数变化方向一致。,（3）遗传算子,轮盘赌,轮盘赌,均匀变异,二元变异,高斯变异,排序选择,算术交叉,基本位变异,随机联赛选择,单点交叉,两点交叉,均匀交叉,最优个体保存,（4）参数选择&（5）收敛性分析,(4)参数选择遗传遗传算法的参数选择一般包括a.群体规模、b.收敛判据、c.杂交概率、d.变异概率,（5）收敛性分析依不同的研究方法及所应用的数学工具,收敛性分析可分为a.Vose-Liepins模型、b.Markov链模型c.公理化模型,(5)欺骗问题,欺骗问题复制算子受欺骗条件的迷惑,使最优低阶模式在组合后形成非最优高阶模式,从而使遗传算法偏离最优解。目前遗传算法的欺骗问题研究主要集中在三个方面:a.设计欺骗函数；b.修改遗传算法以解决欺骗函数的影响；c.理解欺骗函数对遗传算法的影响。,（6）并行遗传算法,并行算法的基本思想 将一个复杂的任务分解为多个较简单的子任务,然后将各子任务分别分配给多个处理器并行执行求解。并行遗传的分类 a.全局并行遗传算法、b.粗粒度并行遗传算法、c.细粒度并行遗传算法、d.混合并行遗传算法。,3.3遗传算法的应用,3.4遗传算法展望,现状：遗传算法已经成为目前计算智能领域的热点之一。待探讨：a.遗传算法与优化技术的融合。b.算法的改进以及新型算法的提出。c.混合遗传算法。d.算法的并行化研究。e.加强遗传算法与应用的结合。f.面向多目标优化约束优化问题的算法及理论研究。,最优化理论与方法 课堂报告安排,
