《数学建模算法介绍幻灯片.ppt》由会员分享，可在线阅读，更多相关《数学建模算法介绍幻灯片.ppt（70页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数学建模算法介绍第1页，共70页，编辑于2022年，星期六进化算法v算法基础v遗传算法第2页，共70页，编辑于2022年，星期六算法基础v算法的概念v算法分类v算法的评价第3页，共70页，编辑于2022年，星期六算法的概念v算法计算方法v把求解问题的方法程式化、规范化v算法是程序的依据、程序是算法的计算机实现v算法思想与依据实现技术算法步骤v算法构成第4页，共70页，编辑于2022年，星期六算法组成v初始条件指定参数、初始解v迭代方法转移规则、生成新可行解的方法v终止条件最优性条件或可接受条件v输出结果最优解或可接受解第5页，共70页，编辑于2022年，星期六算法的分类v构造算法v搜索算法v启
2、发式算法v进化算法第6页，共70页，编辑于2022年，星期六构造算法v明确知道最优解的结构特征v直接构建最优解，中间过程得到的是最优解的部分，不是可行解；v最小支撑树的算法第7页，共70页，编辑于2022年，星期六最小支撑树的算法v算法思想v算法构成v关键技术第8页，共70页，编辑于2022年，星期六算法思想v依据-加上支撑树外的任一边构成唯一的圈，树外边是该圈中权最大的。v从权重小的边开始加边，新拿的边如果和已加入的边构成圈就不加，否则就加入。第9页，共70页，编辑于2022年，星期六关键技术v选择圈中最小的边 按权重从小到大排序v判断是否构成圈第10页，共70页，编辑于2022年，星期六算
3、法构成v初始条件：已加边集为空集，未拿边集为全体边v迭代规则：从未拿的边中选一个权重最小的，如果该边与已加入边构成权就舍去，否则就加入v停止规则：已加边的个数等于顶点数减1或者没有未拿边v输出结果：已加边集或没有支撑树第11页，共70页，编辑于2022年，星期六搜索算法v知道最优解满足的条件，但不知道其结构v从一个可行解出发按某种规则生成新的可行解直到满足最优性条件v单纯形算法第12页，共70页，编辑于2022年，星期六单纯形算法v算法思想v关键技术v算法构成第13页，共70页，编辑于2022年，星期六算法思想v从基可行解中找最优解，从一个基可行解开始，判断是否满足最优性条件，如果满足就停止，
4、否则看是否没有最优解，如果没有最优解就停止，否则生成一个新的最优解第14页，共70页，编辑于2022年，星期六关键技术v初始基可行解v计算检验数和典式v生成新基可行解第15页，共70页，编辑于2022年，星期六算法构成v初始条件：初始基可行解v迭代方法：计算典式和检验数，找初级变量和入基变量v终止条件：检验数小于等于零或检验数大于零的分量对应典式列小于等于零v输出结果：最优基可行解或没有最优解第16页，共70页，编辑于2022年，星期六启发式算法v不知道最优解的结构和最优性条件v模拟人们的思路或经验v贪心算法第17页，共70页，编辑于2022年，星期六最短路贪心算法v算法思想v关键技术v算法组
5、成第18页，共70页，编辑于2022年，星期六算法思想v从起点开始，每一步都选最短的边，直到终点第19页，共70页，编辑于2022年，星期六关键技术v确定每个点关联的未选的边中权重最小的第20页，共70页，编辑于2022年，星期六算法构成v初始条件：已选边为空集，当前点为发点v迭代规则：从当前点出发的边中选择一个权重最小的边，其头部点为新的当前点。如果没有出点则返回上一个点重新选择。v终止条件：当前点为终点，或当前点没有出发点v输出结果：一条从起点到终点的路或没有路第21页，共70页，编辑于2022年，星期六1.3 启发式算法_定义v启发式算法（heuristic algorithm）v定义定
6、义1.基于直观或经验直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解可行解，该可行解与最优解偏差事先不一定可以预计.v定义定义2.启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。v特点（与传统优化方法不同）：特点（与传统优化方法不同）：凭直观和经验给出算法；凭直观和经验给出算法；不考虑所得解与最优解的偏离程度不考虑所得解与最优解的偏离程度.第22页，共70页，编辑于2022年，星期六1.3 启发式算法_优点 优点：优点：（1）有可能比简化数学模型解的误差小；（2）对有些难题，计算
7、时间可接受；（3）可用于某些最优化算法（如分支定界算 法）之中的估界；（4）直观易行；（5）速度较快；（6）程序简单，易修改。第23页，共70页，编辑于2022年，星期六1.3 启发式算法_不足不足：不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术 有关，缺乏规律性；（4）不同算法之间难以比较。第24页，共70页，编辑于2022年，星期六1.3 启发式算法_分类（1）一步算法）一步算法（2）改进算法（迭代算法）改进算法（迭代算法）（3）数学规划算法）数学规划算法（4）解空间松弛法）解空间松弛法 第25页，共70页，编辑于2022年，
8、星期六1.3 启发式算法_分类（5）现代优化算法：）现代优化算法：80年代初兴起v禁忌搜索（tabu search）v模拟退火（simulated annealing）v遗传算法（genetic algorithms）v神经网络（neural networks）v蚂蚁算法（Ant Algorithm，群体（群集）智能，Swarm Intelligence）（6 6）其他算法：）其他算法：多种启发式算法的集成.第26页，共70页，编辑于2022年，星期六1.3 启发式算法_性能分析（1）最坏情形分析（worst case analysis）利用最坏实例分析计算复杂性、解的效果。(2）概率分析（p
9、robability analysis）用最坏情况分析，会因一个最坏实例影响总体评价.在实例数据服从一定概率分布情形下，研究算法复杂性和解的效果.(3)大规模计算分析 通过大量实例计算，评价算法效果.v注意数据的随机性和代表性.第27页，共70页，编辑于2022年，星期六进化算法v不知道最优解的结构和最优性条件v模拟生物寻优行为，大规模群体优化v群体搜索算法v遗传算法第28页，共70页，编辑于2022年，星期六算法的评价v结果评价v复杂性评价第29页，共70页，编辑于2022年，星期六结果评价v全局最优算法v局部最优算法v近似算法v有效算法第30页，共70页，编辑于2022年，星期六全局最优算
10、法v全局收敛算法v得到全局最优解或收敛到全局最优解v分支定界算法第31页，共70页，编辑于2022年，星期六局部最优解v得到局部最优解v结果的好坏依赖初始解的选取v非线性规划搜索算法第32页，共70页，编辑于2022年，星期六近似算法v得到一个与最优解的差距不超过一定比例的解v需要说明与最优解的差距v复杂问题的多项时间算法第33页，共70页，编辑于2022年，星期六可接受算法v得到一个比较好的解v无法说明与最优解的差距v贪心算法v不需要太多的理论知识第34页，共70页，编辑于2022年，星期六复杂性评价v算法复杂性v多项式时间算法v非多项式时间算法第35页，共70页，编辑于2022年，星期六1
11、.2 计算复杂性的概念计算复杂性的概念v评价算法的好坏计算时间的多少、解的偏离程度v例 非对称距离TSP问题的算法实现：所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：第36页，共70页，编辑于2022年，星期六1.2 计算复杂性的概念计算复杂性的概念城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325year随城市增多，计算时间增加很快。到31个城市时，要计算325年。描述算法的好坏计算复杂性讨论计算时间与问题规模
12、之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。第37页，共70页，编辑于2022年，星期六1.2 计算复杂性的概念计算复杂性的概念v问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述：（1）对所有参数的一般性描述；（2）答案（或解）必须满足的性质。v实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据；这些数据输入计算机所占的空间称为实例的长度（size）.第38页，共70页，编辑于2022年，星期六1.2 计算复杂性的概念计算复杂性的概念 一类最
13、优化问题是由一些类似的具体问题（实例）组成的，每一个具体问题可表达成二元组（F,C）.F为可行解集合;C是费用函数，是由F到R（实数集）的映像。问题是在F中找到一个点f*，使对F中任意的f，有C(f*)C(f),称f*为这一具体问题的最优解（或全局最优解）.第39页，共70页，编辑于2022年，星期六1.2 计算复杂性的概念v算法计算量的度量：加、减、乘、除、比较的总运算次数与实例的计算机计算时的二进制输入数据的大小关系。v正整数x的二进制位数是:(整数到二进制的转换)第40页，共70页，编辑于2022年，星期六1.2 计算复杂性的概念v算法计算量的度量之例算法计算量的度量之例TSP枚举法枚举
14、法计算量的统计：计算量的统计：第41页，共70页，编辑于2022年，星期六1.2 计算复杂性的概念v实例的输入长度：v实例的输入长度是n的多项式函数v枚举法的基本计算量是n的阶乘函数，随n的增加，比指数函数增加得还快.第42页，共70页，编辑于2022年，星期六1.2 计算复杂性的概念第43页，共70页，编辑于2022年，星期六1.2 计算复杂性的概念定义 多项式算法给定问题P，算法A，对一个实例I，存在多项式函数g(x)，使（XX）成立，称算法A对实例I是多项式算法；若存在多项式函数g(x)，使（XX）对问题P的任意实例I都成立，称算法A为解决该问题P的多项式算法.当g(x)为指数函数时，称
15、A为P的指数时间算法。第44页，共70页，编辑于2022年，星期六1.2 计算复杂性的概念v利用复杂性分析对组合优化问题归类。v定义多项式问题多项式问题 给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称多项式问题多项式问题(或或P问题问题).所有多项式问题的集合记为P.v例：线性规划是否为多项式问题？第45页，共70页，编辑于2022年，星期六1.2 计算复杂性参考书v计算复杂性计算复杂性,作者：Christos，Papadimitriou清华大学出版社，2004年9月第1版v计算复杂性导论，计算复杂性导论，作者：堵丁柱等，高等教育出版社，2002年8月第1版第
16、46页，共70页，编辑于2022年，星期六遗传算法v基本思想v关键技术v算法步骤v实例第47页，共70页，编辑于2022年，星期六遗传算法起源 v 遗传算法是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。第48页，共70页，编辑于2022年，星期六遗传算法基本思想v生物进化过程v模拟技术第49页，共70页，编辑于2022年，星期六生物进化过程v遗传信息决定个体性能v子代信息来自父代个体v会发生变异v通过自然选择、适者生存v具有整体寻优性能种群父代群子群单亲、双亲繁殖优胜劣汰第50页，共70页，
17、编辑于2022年，星期六进化过程种群选择父群子群交叉变异可行解子集合可行解子集合新解子集合选择交叉、变异第51页，共70页，编辑于2022年，星期六遗传算法的搜索机制 v 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。第52页，共70页，编辑于2022年，星期六模拟技术 v表示可行解v初始子集合v选择标准v生成新的子集合（选择、交叉、变异）v编码方式v产生初始种群v适应度函数v遗传算子（选择、交叉
18、、变异）第53页，共70页，编辑于2022年，星期六 编码 GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。第54页，共70页，编辑于2022年，星期六函数优化示例 v求下列一元函数的最大值：v x-1,2 x-1,2 ，求解结果精确到，求解结果精确到6 6位小数。位小数。第55页，共70页，编辑于2022年，星期六GA对于本例的编码 v 由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。又因为221 3106 222，所以本例的二进制编码长度至少需要22位
19、，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b0）。第56页，共70页，编辑于2022年，星期六几个术语 v基因型：1000101110110101000111 v表现型：0.637197 编码解码个体（染色体）基因第57页，共70页，编辑于2022年，星期六初始种群 v SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。第58页，共70页，编辑于2022年，星期六 适应度函数 v 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行
20、自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。第59页，共70页，编辑于2022年，星期六选择算子v 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。第60页，共70页，编辑于2022年，星期六轮盘赌选择方法v 轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的
21、概率为：第61页，共70页，编辑于2022年，星期六轮盘赌选择方法的实现步骤v（1）计算群体中所有个体的适应度函数值（需要解码）；v（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；v（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。第62页，共70页，编辑于2022年，星期六交叉算子 v 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法
22、。SGA中交叉算子采用单点交叉算子。第63页，共70页，编辑于2022年，星期六单点交叉运算 v交叉前：v00000|01110000000010000v11100|00000111111000101v交叉后：v00000|00000111111000101v11100|01110000000010000交叉点交叉点第64页，共70页，编辑于2022年，星期六变异算子 v 所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的
23、相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。第65页，共70页，编辑于2022年，星期六基本位变异算子 v 基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。第66页，共70页，编辑于2022年，星期六基本位变异算子的执行过程 v变异前：v000001110000000010000v变异后：v000001110001000010000变异点变异点第67页，共70页，编
24、辑于2022年，星期六运行参数 v（1）M ：种群规模 v（2）T ：遗传运算的终止进化代数 v（3）Pc ：交叉概率 v（4）Pm：变异概率 第68页，共70页，编辑于2022年，星期六算法步骤 产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次第69页，共70页，编辑于2022年，星期六3、遗传算法的特点 v（1）群体搜索，易于并行化处理；v（2）不是盲目穷举，而是启发式搜索；v（3）适应度函数不受连续、可微等条件的约束，适用范围很广。第70页，共70页，编辑于2022年，星期六