最优化理论与方法 第一章

《最优化理论与方法 第一章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1最优化理论与方法（现代优化计算方法）2内容概论递归、分治、贪心、回溯禁忌搜索、爬山算法模拟退火、蚁群算法遗传算法神经网络元胞自动机随机算法3背景传统实际问题的特点连续性问题——主要以微积分为基础，且问题规模较小传统的优化方法追求准确——精确解理论的完美——结果漂亮主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）4传统运筹学面临新挑战现代问题的特点离散性问题——主要以组合优化（针对离散问题，定义见后）理论为

2、基础不确定性问题——随机性数学模型半结构或非结构化的问题——计算机模拟、决策支持系统大规模问题——并行计算、大型分解理论、近似理论现代优化方法追求满意——近似解实用性强——解决实际问题现代优化算法的评价方法算法复杂性5现代优化(启发式)方法种类禁忌搜索（tabusearch）模拟退火（simulatedannealing）遗传算法（geneticalgorithms）神经网络（neuralnetworks）蚁群算法（群体（群集）智能，SwarmIntelligence）拉格朗日松弛算法（lagrangeanrelaxation）6

3、1现代优化计算方法概述1.1组合优化问题1.2算法1.3计算复杂性的概念1.4启发式算法71.1组合优化问题组合优化（combinatorialoptimization）:解决离散问题的优化问题——运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。数学模型：81.1组合优化问题组合优化问题的三参数表示：91.1组合优化问题例10-1背包问题（0-1knapsackproblem）101.1组合优化问题111.1组合优化问题例2旅行商问题（TSP,travelingsalesmanproblem）管梅谷教授

4、1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。121.1组合优化问题131.1组合优化问题例3装箱问题（binpacking）尺寸为1的箱子有若干个，怎样用最少的箱子装下n个尺寸不超过1的物品，物品集合为：。141.1组合优化问题151.1组合优化问题例4约束机器排序问题（binpacking）n个加工量为{di

5、i=1,2,⋯,n}的产品在一台机器上加工,机器在第t个时段的工作能力为ct,求完成所有产品加工的最少时段数。161.1组合优化问题171.2算

6、法评价算法的好坏——计算时间的多少、解的偏离程度先看看算法的基本概念一个有穷规则的有序集合称为一个算法。1.定义.2.算法的特征.输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限。可行性：执行每条指令的时间也有限。1.2算法1．有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；2．确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如

7、何执行。并且在任何条件下，算法都只有一条执行路径；3．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；5．有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。二、算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性2.可读性3．健壮性4．高效率与低存储量需求1．正确性首先，算法应当满足以特

8、定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解有四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。d．程序对于一切合法的输入数据都能得出满足要求的结果；2.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；3．健壮性当输入的数据非法时，算法应当恰当地作出反映或进

9、行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4．高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储