数学建模 算法介绍

《数学建模 算法介绍》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、优化算法基础马建华2011年7月进化算法算法基础遗传算法算法基础算法的概念算法分类算法的评价算法的概念算法—计算方法把求解问题的方法程式化、规范化算法是程序的依据、程序是算法的计算机实现算法思想与依据—实现技术—算法步骤算法构成算法组成初始条件—指定参数、初始解迭代方法—转移规则、生成新可行解的方法终止条件—最优性条件或可接受条件输出结果—最优解或可接受解算法的分类构造算法搜索算法启发式算法进化算法构造算法明确知道最优解的结构特征直接构建最优解，中间过程得到的是最优解的部分，不是可行解；最小支撑树的算法最

2、小支撑树的算法算法思想算法构成关键技术算法思想依据--加上支撑树外的任一边构成唯一的圈，树外边是该圈中权最大的。从权重小的边开始加边，新拿的边如果和已加入的边构成圈就不加，否则就加入。关键技术选择圈中最小的边按权重从小到大排序判断是否构成圈算法构成初始条件：已加边集为空集，未拿边集为全体边迭代规则：从未拿的边中选一个权重最小的，如果该边与已加入边构成权就舍去，否则就加入停止规则：已加边的个数等于顶点数减1或者没有未拿边输出结果：已加边集或没有支撑树搜索算法知道最优解满足的条件，但不知道其结构从一个可行解出

3、发按某种规则生成新的可行解直到满足最优性条件单纯形算法单纯形算法算法思想关键技术算法构成算法思想从基可行解中找最优解，从一个基可行解开始，判断是否满足最优性条件，如果满足就停止，否则看是否没有最优解，如果没有最优解就停止，否则生成一个新的最优解关键技术初始基可行解计算检验数和典式生成新基可行解算法构成初始条件：初始基可行解迭代方法：计算典式和检验数，找初级变量和入基变量终止条件：检验数小于等于零或检验数大于零的分量对应典式列小于等于零输出结果：最优基可行解或没有最优解启发式算法不知道最优解的结构和最优性条

4、件模拟人们的思路或经验贪心算法最短路贪心算法算法思想关键技术算法组成算法思想从起点开始，每一步都选最短的边，直到终点关键技术确定每个点关联的未选的边中权重最小的算法构成初始条件：已选边为空集，当前点为发点迭代规则：从当前点出发的边中选择一个权重最小的边，其头部点为新的当前点。如果没有出点则返回上一个点重新选择。终止条件：当前点为终点，或当前点没有出发点输出结果：一条从起点到终点的路或没有路1.3启发式算法_定义启发式算法（heuristicalgorithm）定义1.基于直观或经验构造的算法，在可接受的花

5、费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解，该可行解与最优解偏差事先不一定可以预计.定义2.启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。特点（与传统优化方法不同）：凭直观和经验给出算法；不考虑所得解与最优解的偏离程度.1.3启发式算法_优点优点：（1）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算法）之中的估界；（4）直观易行；（5）速度较快；（6）程序简

6、单，易修改。1.3启发式算法_不足不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术有关，缺乏规律性；（4）不同算法之间难以比较。1.3启发式算法_分类（1）一步算法（2）改进算法（迭代算法）（3）数学规划算法（4）解空间松弛法1.3启发式算法_分类（5）现代优化算法：80年代初兴起禁忌搜索（tabusearch）模拟退火（simulatedannealing）遗传算法（geneticalgorithms）神经网络（neuralnetworks）

7、蚂蚁算法（AntAlgorithm，群体（群集）智能，SwarmIntelligence）（6）其他算法：多种启发式算法的集成.1.3启发式算法_性能分析（1）最坏情形分析（worstcaseanalysis）利用最坏实例分析计算复杂性、解的效果。(2）概率分析（probabilityanalysis）用最坏情况分析，会因一个最坏实例影响总体评价.在实例数据服从一定概率分布情形下，研究算法复杂性和解的效果.(3)大规模计算分析通过大量实例计算，评价算法效果.注意数据的随机性和代表性.进化算法不知道最优解的

8、结构和最优性条件模拟生物寻优行为，大规模群体优化群体搜索算法遗传算法算法的评价结果评价复杂性评价结果评价全局最优算法局部最优算法近似算法有效算法全局最优算法全局收敛算法得到全局最优解或收敛到全局最优解分支定界算法局部最优解得到局部最优解结果的好坏依赖初始解的选取非线性规划搜索算法近似算法得到一个与最优解的差距不超过一定比例的解需要说明与最优解的差距复杂问题的多项时间算法可接受算法得到一个比较好的解无法说明与最优解的差距贪心算法