数学建模算法介绍

数学建模算法介绍第1页，共70页，2023年，2月20日，星期六进化算法算法基础遗传算法第2页，共70页，2023年，2月20日，星期六算法基础算法的概念算法分类算法的评价第3页，共70页，2023年，2月20日，星期六算法的概念算法—计算方法把求解问题的方法程式化、规范化算法是程序的依据、程序是算法的计算机实现算法思想与依据—实现技术—算法步骤算法构成第4页，共70页，2023年，2月20日，星期六算法组成初始条件—指定参数、初始解迭代方法—转移规则、生成新可行解的方法终止条件—最优性条件或可接受条件输出结果—最优解或可接受解第5页，共70页，2023年，2月20日，星期六算法的分类构造算法搜索算法启发式算法进化算法第6页，共70页，2023年，2月20日，星期六构造算法明确知道最优解的结构特征直接构建最优解，中间过程得到的是最优解的部分，不是可行解；最小支撑树的算法第7页，共70页，2023年，2月20日，星期六最小支撑树的算法算法思想算法构成关键技术第8页，共70页，2023年，2月20日，星期六算法思想依据--加上支撑树外的任一边构成唯一的圈，树外边是该圈中权最大的。从权重小的边开始加边，新拿的边如果和已加入的边构成圈就不加，否则就加入。第9页，共70页，2023年，2月20日，星期六关键技术选择圈中最小的边按权重从小到大排序判断是否构成圈第10页，共70页，2023年，2月20日，星期六算法构成初始条件：已加边集为空集，未拿边集为全体边迭代规则：从未拿的边中选一个权重最小的，如果该边与已加入边构成权就舍去，否则就加入停止规则：已加边的个数等于顶点数减1或者没有未拿边输出结果：已加边集或没有支撑树第11页，共70页，2023年，2月20日，星期六搜索算法知道最优解满足的条件，但不知道其结构从一个可行解出发按某种规则生成新的可行解直到满足最优性条件单纯形算法第12页，共70页，2023年，2月20日，星期六单纯形算法算法思想关键技术算法构成第13页，共70页，2023年，2月20日，星期六算法思想从基可行解中找最优解，从一个基可行解开始，判断是否满足最优性条件，如果满足就停止，否则看是否没有最优解，如果没有最优解就停止，否则生成一个新的最优解第14页，共70页，2023年，2月20日，星期六关键技术初始基可行解计算检验数和典式生成新基可行解第15页，共70页，2023年，2月20日，星期六算法构成初始条件：初始基可行解迭代方法：计算典式和检验数，找初级变量和入基变量终止条件：检验数小于等于零或检验数大于零的分量对应典式列小于等于零输出结果：最优基可行解或没有最优解第16页，共70页，2023年，2月20日，星期六启发式算法不知道最优解的结构和最优性条件模拟人们的思路或经验贪心算法第17页，共70页，2023年，2月20日，星期六最短路贪心算法算法思想关键技术算法组成第18页，共70页，2023年，2月20日，星期六算法思想从起点开始，每一步都选最短的边，直到终点第19页，共70页，2023年，2月20日，星期六关键技术确定每个点关联的未选的边中权重最小的第20页，共70页，2023年，2月20日，星期六算法构成初始条件：已选边为空集，当前点为发点迭代规则：从当前点出发的边中选择一个权重最小的边，其头部点为新的当前点。如果没有出点则返回上一个点重新选择。终止条件：当前点为终点，或当前点没有出发点输出结果：一条从起点到终点的路或没有路第21页，共70页，2023年，2月20日，星期六1.3启发式算法_定义启发式算法（heuristicalgorithm）定义1.基于直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解，该可行解与最优解偏差事先不一定可以预计.定义2.启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。特点（与传统优化方法不同）：凭直观和经验给出算法；不考虑所得解与最优解的偏离程度.第22页，共70页，2023年，2月20日，星期六1.3启发式算法_优点

优点：（1）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算法）之中的估界；（4）直观易行；（5）速度较快；（6）程序简单，易修改。第23页，共70页，2023年，2月20日，星期六1.3启发式算法_不足不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术有关，缺乏规律性；（4）不同算法之间难以比较。第24页，共70页，2023年，2月20日，星期六1.3启发式算法_分类（1）一步算法（2）改进算法（迭代算法）（3）数学规划算法（4）解空间松弛法

第25页，共70页，2023年，2月20日，星期六1.3启发式算法_分类（5）现代优化算法：80年代初兴起禁忌搜索（tabusearch）模拟退火（simulatedannealing）遗传算法（geneticalgorithms）神经网络（neuralnetworks）蚂蚁算法（AntAlgorithm，群体（群集）智能，SwarmIntelligence）（6）其他算法：多种启发式算法的集成.第26页，共70页，2023年，2月20日，星期六1.3启发式算法_性能分析（1）最坏情形分析（worstcaseanalysis）利用最坏实例分析计算复杂性、解的效果。(2）概率分析（probabilityanalysis）

用最坏情况分析，会因一个最坏实例影响总体评价.在实例数据服从一定概率分布情形下，研究算法复杂性和解的效果.

(3)大规模计算分析通过大量实例计算，评价算法效果.注意数据的随机性和代表性.第27页，共70页，2023年，2月20日，星期六进化算法不知道最优解的结构和最优性条件模拟生物寻优行为，大规模群体优化群体搜索算法遗传算法第28页，共70页，2023年，2月20日，星期六算法的评价结果评价复杂性评价第29页，共70页，2023年，2月20日，星期六结果评价全局最优算法局部最优算法近似算法有效算法第30页，共70页，2023年，2月20日，星期六全局最优算法全局收敛算法得到全局最优解或收敛到全局最优解分支定界算法第31页，共70页，2023年，2月20日，星期六局部最优解得到局部最优解结果的好坏依赖初始解的选取非线性规划搜索算法第32页，共70页，2023年，2月20日，星期六近似算法得到一个与最优解的差距不超过一定比例的解需要说明与最优解的差距复杂问题的多项时间算法第33页，共70页，2023年，2月20日，星期六可接受算法得到一个比较好的解无法说明与最优解的差距贪心算法不需要太多的理论知识第34页，共70页，2023年，2月20日，星期六复杂性评价算法复杂性多项式时间算法非多项式时间算法第35页，共70页，2023年，2月20日，星期六1.2计算复杂性的概念评价算法的好坏——计算时间的多少、解的偏离程度例非对称距离TSP问题的算法实现：所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：第36页，共70页，2023年，2月20日，星期六1.2计算复杂性的概念城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325year随城市增多，计算时间增加很快。到31个城市时，要计算325年。描述算法的好坏——计算复杂性——讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。第37页，共70页，2023年，2月20日，星期六1.2计算复杂性的概念问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述：（1）对所有参数的一般性描述；（2）答案（或解）必须满足的性质。实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据；这些数据输入计算机所占的空间称为实例的长度（size）.第38页，共70页，2023年，2月20日，星期六1.2计算复杂性的概念一类最优化问题是由一些类似的具体问题（实例）组成的，每一个具体问题可表达成二元组（F,C）.F为可行解集合;C是费用函数，是由F到R（实数集）的映像。问题是在F中找到一个点f*，使对F中任意的f，有C(f*)C(f),称f*为这一具体问题的最优解（或全局最优解）.第39页，共70页，2023年，2月20日，星期六1.2计算复杂性的概念算法计算量的度量：加、减、乘、除、比较的总运算次数与实例的计算机计算时的二进制输入数据的大小关系。正整数x的二进制位数是:(整数到二进制的转换)

第40页，共70页，2023年，2月20日，星期六1.2计算复杂性的概念算法计算量的度量之例——TSP枚举法计算量的统计：第41页，共70页，2023年，2月20日，星期六1.2计算复杂性的概念实例的输入长度：实例的输入长度是n的多项式函数枚举法的基本计算量是n的阶乘函数，随n的增加，比指数函数增加得还快.第42页，共70页，2023年，2月20日，星期六1.2计算复杂性的概念第43页，共70页，2023年，2月20日，星期六1.2计算复杂性的概念定义多项式算法给定问题P，算法A，对一个实例I，存在多项式函数g(x)，使（XX）成立，称算法A对实例I是多项式算法；若存在多项式函数g(x)，使（XX）对问题P的任意实例I都成立，称算法A为解决该问题P的多项式算法.当g(x)为指数函数时，称A为P的指数时间算法。第44页，共70页，2023年，2月20日，星期六1.2计算复杂性的概念利用复杂性分析对组合优化问题归类。定义多项式问题给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称多项式问题(或P问题).所有多项式问题的集合记为P.例：线性规划是否为多项式问题？第45页，共70页，2023年，2月20日，星期六1.2计算复杂性参考书计算复杂性,

作者：Christos，Papadimitriou

清华大学出版社，2004年9月第1版计算复杂性导论，作者：堵丁柱等，高等教育出版社，2002年8月第1版

第46页，共70页，2023年，2月20日，星期六遗传算法基本思想关键技术算法步骤实例第47页，共70页，2023年，2月20日，星期六遗传算法起源遗传算法是由美国的J.Holland教授于1975年在他的专著《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。第48页，共70页，2023年，2月20日，星期六遗传算法基本思想生物进化过程模拟技术第49页，共70页，2023年，2月20日，星期六生物进化过程遗传信息决定个体性能子代信息来自父代个体会发生变异通过自然选择、适者生存具有整体寻优性能种群父代群子群单亲、双亲繁殖优胜劣汰第50页，共70页，2023年，2月20日，星期六进化过程种群选择父群子群交叉变异可行解子集合可行解子集合新解子集合选择交叉、变异第51页，共70页，2023年，2月20日，星期六遗传算法的搜索机制遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。

第52页，共70页，2023年，2月20日，星期六模拟技术表示可行解初始子集合选择标准生成新的子集合（选择、交叉、变异）编码方式产生初始种群适应度函数遗传算子（选择、交叉、变异）第53页，共70页，2023年，2月20日，星期六编码GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。第54页，共70页，2023年，2月20日，星期六函数优化示例求下列一元函数的最大值：

x∈[-1,2]，求解结果精确到6位小数。第55页，共70页，2023年，2月20日，星期六GA对于本例的编码由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3×106等份。又因为221<3×106<222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间[-1，2]内对应的实数值转化为一个二进制串（b21b20…b0）。第56页，共70页，2023年，2月20日，星期六几个术语基因型：1000101110110101000111表现型：0.637197编码解码个体（染色体）基因第57页，共70页，2023年，2月20日，星期六初始种群SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。第58页，共70页，2023年，2月20日，星期六适应度函数

遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。第59页，共70页，2023年，2月20日，星期六选择算子遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。第60页，共70页，2023年，2月20日，星期六轮盘赌选择方法轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：第61页，共70页，2023年，2月20日，星期六轮盘赌选择方法的实现步骤（1）计算群体中所有个体的适应度函数值（需要解码）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。第62页，共70页，2023年，2月20日，星期六交叉算子所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。第63页，共70页，2023年，2月20日，星期六单点交叉运算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉点第64页，共70页，2023年，2月20日，星期六变异算子