最优化理论与方法 遗传算法课件

1、最优化理论与方法之 遗传算法报告人：罗九晖目录 最优化方法概述 智能算法概述 遗传算法概述经典精确优化算法（数值最优化）经典近似优化算法（解析最优化）智能算法（仿生算法、演化算法） 用来处理目标函数以及约束条件有具体的解析表达式且存在导数的情况。 通过以模拟物质变化过程或模拟生命体而设计的搜索方式为基础提出的算法。 通过最优解的性质建立迭代公式来求最优解。1.最优化方法概述 数值优化算法和解析优化算法必须建立在目标函数存在导数的性质条件下进行，而在实际中碰到的很多优化问题的目标函数并不存在导数。 最优化方法概述 智能算法概述 遗传算法概述2.智能算法 智能 是在任意给定的环境和目标条件下，正确

2、制定决策和实现目标的能力。 智能优化算法 则是将生物行为与计算机科学相结合，解决优化问题，制定最优化决策。 几种智能算法禁忌搜索方式蚁群算法粒子群优化算法人工神经网络Equation of state calculations by Fast Computing MachinesAlgorithms and the Optimal Allocation of TrialsPositive Feedback as a search strategyA New optimizer using particle swarm theoryTabu searchTuring Computability

3、With Neural Nets模拟退火模式遗传算法智能算法各种算法模拟的自然现象算法名称模拟过程模拟退火算法退火过程中,固体最终达到能量最小的状态,对应于优化算法最终找到了最优解。禁忌搜索算法禁止重复前面的工作蚁群算法某一路径上走过的蚂蚁越多, 则后来者选择该路径的概率就越大粒子群优化算法群体搜寻最优目标时,每个个体将参照当前群体中曾有的最优个体,和自身曾经达到的最优位置调整下一步的搜寻方向人工神经网络对人脑的模拟遗传算法模拟生物界自然选择和遗传机制3.遗传算法概述用“袋鼠跳”问题来粗略领略遗传算法（1）随机生成N个个体组成一个种群。第一批袋鼠被随意分散在山脉上。（2）完成种群中每个个体适应

4、度的计算。得到袋鼠的位置坐标。（3）对个体做适应度评价。袋鼠爬得越高，越受我们喜爱，适应度越高。（4）用选择函数按某种规则择优选择。每隔一段时间射杀海拔低的袋鼠。（5）让个体基因交叉变异。让袋鼠交配并随机跳动。（6）选择子代。希望活下来的袋鼠是多产的，并在那里生儿育女。 遗传算法并不保证你能获得问题的最优解，但是使用遗传算法的最大优点在于你不必去了解和操心如何 去“找”最优解。你不必去指导袋鼠向哪边跳，跳多远。 而只要简单的“否定”一些表现不好的个体就行了。把那些总是爱走下坡路的袋鼠射杀。3.1遗传算法的执行过程（1）初始化。确定种群规模N、交叉概率Pc、变异概率Pm和置终止进化准则; 随机生

5、成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）。遗传算法初窥一个简单的遗传算法案例：注意需要说明的是，表中有些栏的数

6、据是随机产生的。这里为了更好地说明问题，特意选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中有可能需要一定的循环次数才能达到这个最优结果。 （4）参数选择&（5）收敛性分析(4)参数选择遗传遗传算法的参数选择一般包括a.群体规模、b.收敛判据、c.杂交概率、d.变异概率 （5）收敛性分析依不同的研究方法及所应用的数学工具, 收敛性分析可分为a.Vose-Liepins模型、b.Markov链模型c.公理化模型 (5)欺骗问题 欺骗问题复制算子受欺骗条件的迷惑,使最优低阶模式在组合后形成非最优高阶模式, 从而使遗传算法偏离最优解。 目前遗传算法的欺骗问题研究主要集中在三个方面: a.设计欺骗函数； b. 修改遗传算法以解决欺骗函数的影响； c. 理解欺骗函数对遗传算法的影响。（6）并行遗传算法 并行算法的基本思想 将一个复杂的任务分解为多个较简单的子任务, 然后将各子任务分别分配给多个处理器并行执行求解。 并行遗传的分类 a.