最优化理论与方法遗传算法.pptx

OptimizationMethodsSummary of genetic algorithms research最优化理论与方法之遗传算法报告人：罗九晖OptimizationMethodsSummary of genetic algorithms research目录l最优化方法概述l智能算法概述l遗传算法概述OptimizationMethodsSummary of genetic algorithms research经典精确优化算法（数值最优化）经典精确优化算法（数值最优化）经典近似优化算法（解析最优化）经典近似优化算法（解析最优化）智能算法（仿生算法、演化算法）智能算法（仿生算法、演化算法）用来处理目标函数以及约束条件有具体的解析用来处理目标函数以及约束条件有具体的解析表达式且存在导数的情况。表达式且存在导数的情况。通过以模拟物质变化过程或模拟生命体而设通过以模拟物质变化过程或模拟生命体而设计的搜索方式为基础提出的算法。计的搜索方式为基础提出的算法。通过最优解的性质建立迭代公式来求最优解。通过最优解的性质建立迭代公式来求最优解。1.最优化方法概述 数值优化算法和解析优化算法必须建立在目标函数存在导数的性质条件下进行，而在实际中碰到的很多优化问题的目标函数并不存在导数。OptimizationMethodsSummary of genetic algorithms researchl最优化方法概述l智能算法概述l遗传算法概述OptimizationMethodsSummary of genetic algorithms research2.智能算法智能是在任意给定的环境和目标条件下，正确制定决策和实现目标的能力。智能优化算法则是将生物行为与计算机科学相结合，解决优化问题，制定最优化决策。OptimizationMethodsSummary of genetic algorithms research几种智能算法禁忌搜索禁忌搜索方式方式蚁群算法蚁群算法粒子群优粒子群优化算法化算法人工神经人工神经网络网络EquationofstatecalculationsbyFastComputingMachinesAlgorithmsandtheOptimalAllocationofTrialsPositiveFeedbackasasearchstrategyANewoptimizerusingparticleswarmtheoryTabusearchTuringComputabilityWithNeuralNets模拟退火模拟退火模式模式遗传算法遗传算法智能智能算法算法OptimizationMethodsSummary of genetic algorithms research各种算法模拟的自然现象算法名称模拟过程模拟退火算法退火过程中,固体最终达到能量最小的状态,对应于优化算法最终找到了最优解。禁忌搜索算法禁止重复前面的工作蚁群算法某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大粒子群优化算法群体搜寻最优目标时,每个个体将参照当前群体中曾有的最优个体,和自身曾经达到的最优位置调整下一步的搜寻方向人工神经网络对人脑的模拟遗传算法模拟生物界自然选择和遗传机制OptimizationMethodsSummary of genetic algorithms research关于智能算法的几个形象比喻 为了找出地球上最高的山，一群有志气的袋鼠们开始想办法。1.兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是局部搜索，它不能保证局部最优值就是全局最优值。2.袋鼠喝醉了。他随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。这就是模拟退火。3.袋鼠们知道一只袋鼠的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只袋鼠做记号。他们制定了下一步去哪里寻找的策略。这就是禁忌搜索。4.袋鼠们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的袋鼠，多产的袋鼠们自己就会找到珠穆朗玛峰。这就是遗传算法。OptimizationMethodsSummary of genetic algorithms researchl最优化方法概述l智能算法概述l遗传算法概述OptimizationMethodsSummary of genetic algorithms research3.遗传算法概述用“袋鼠跳”问题来粗略领略遗传算法（1）随机生成）随机生成N个个体组成一个种群。个个体组成一个种群。第一批袋鼠被随意分散在山脉上。第一批袋鼠被随意分散在山脉上。（2）完成种群中每个个体适应度的计算。）完成种群中每个个体适应度的计算。得到袋鼠的位置坐标。得到袋鼠的位置坐标。（3）对个体做适应度评价。）对个体做适应度评价。袋鼠爬得越高，越受我们喜爱，适应度越高。袋鼠爬得越高，越受我们喜爱，适应度越高。（4）用选择函数按某种规则择优选择。）用选择函数按某种规则择优选择。每隔一段时间射杀海拔低的袋鼠。每隔一段时间射杀海拔低的袋鼠。（5）让个体基因交叉变异。）让个体基因交叉变异。让袋鼠交配并随机跳动。让袋鼠交配并随机跳动。（6）选择子代。）选择子代。希望活下来的袋鼠是多产的，并在那里生儿育女。希望活下来的袋鼠是多产的，并在那里生儿育女。遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何优点在于你不必去了解和操心如何 去去“找找”最优解。最优解。你不必去指导袋鼠向你不必去指导袋鼠向哪边跳，跳多远。哪边跳，跳多远。而只要简单的而只要简单的“否定否定”一些表现不好的个体就行了。一些表现不好的个体就行了。把那些总是爱走把那些总是爱走下坡路的袋鼠射杀。下坡路的袋鼠射杀。OptimizationMethodsSummary of genetic algorithms research3.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）。OptimizationMethodsSummary of genetic algorithms research遗传算法初窥一个简单的遗传算法一个简单的遗传算法案例案例：注意需要说明的是，表中有些栏的数据是随机产生的。这里为了更好地说明问题，特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中有可能需要一定的循环次数才能达到这个最优结果。OptimizationMethodsSummary of genetic algorithms research3.2遗传算法的理论研究（1 1）编码）编码（2 2）适应度函数）适应度函数（3 3）遗传算子）遗传算子（4 4）参数选择）参数选择（5 5）收敛性分析）收敛性分析（6 6）欺骗问题）欺骗问题（7 7）并行遗传算法）并行遗传算法OptimizationMethodsSummary of genetic algorithms research（1）编码&（2）适应度函数（1）编码传统编码：二进制发展：a.格雷码编码；b.实数编码；c.十进制编码；d.非数值编码。（2）适应度函数将目标函数转换成适应度函数一般应遵循两个原则:a.适应度必须非负;b.优化过程中目标函数的变化方向应与群体进化过程中适应度函数变化方向一致。OptimizationMethodsSummary of genetic algorithms research（3）遗传算子遗遗传传算算子子选选择择算算子子交交叉叉算算子子变变异异算算子子排排序序选选择择轮盘赌轮盘赌均匀变异二元变异高斯变异排序选择算术交叉基本位变异随机联赛选择单点交叉两点交叉均匀交叉最优个体保存OptimizationMethodsSummary of genetic algorithms research（4）参数选择&（5）收敛性分析(4)参数选择遗传遗传算法的参数选择一般包括a.群体规模、b.收敛判据、c.杂交概率、d.变异概率（5）收敛性分析依不同的研究方法及所应用的数学工具,收敛性分析可分为a.Vose-Liepins模型、b.Markov链模型c.公理化模型 OptimizationMethodsSummary of genetic algorithms research(5)欺骗问题 欺骗问题欺骗问题复制算子受欺骗条件的迷惑,使最优低阶模式在组合后形成非最优高阶模式,从而使遗传算法偏离最优解。目前遗传算法的欺骗问题研究主要集中在三个方面:a.设计欺骗函数；b.修改遗传算法以解决欺骗函数的影响；c.理解欺骗函数对遗传算法的影响。OptimizationMethodsSummary of genetic algorithms research（6）并行遗传算法 并行算法的基本思想并行算法的基本思想 将一个复杂的任务分解为多个较简单的子任务,然后将各子任务分别分配给多个处理器并行执行求解。并行遗传的分类并行遗传的分类 a.全局并行遗传算法、b.粗粒度并行遗传算法、c.细粒度并行遗传算法、d.混合并行遗传算法。OptimizationMethodsSummary of genetic algorithms research3.3遗传算法的应用数据挖掘数据挖掘机器学机器学习习遗传编遗传编程程人工生命人工生命图图像像处处理理机器人学机器人学自自动动控制控制生生产调产调度度组组合合优优化化函数函数优优化化遗传算法OptimizationMethodsSummary of genetic algorithms research3.4遗传算法展望现状：遗传算法已经成为目前计算智能领域的热点之一。待探讨：a.遗传算法与优化技术的融合。b.算法的改进以及新型算法的提出。c.混合遗传算法。d.算法的并行化研究。e.加强遗传算法与应用的结合。f.面向多目标优化约束优化问题的算法及理论研究。OptimizationMethodsSummary of genetic algorithms research最优化理论与方法课堂报告安排报告时间报告时间报告人报告人6.11（第十六周）（第十六周）罗九晖、刘伟义、胡宵、徐巧罗九晖、刘伟义、胡宵、徐巧睇睇6.18（第十七周）（第十七周）孟妞妞、黄伟、郑凎云、施翠孟妞妞、黄伟、郑凎云、施翠云云/赵杰赵杰6.25（第十八周）（第十八周）李宗真、姜燕妮、李雪晨、代李宗真、姜燕妮、李雪晨、代成成成成/陈子恒陈子恒7.2（第十九周）（第十九周）李宜洋、彭姣凤、焦肖红、邹李宜洋、彭姣凤、焦肖红、邹萍萍/刘姣刘姣