最优化理论与方法 第一章

1最优化理论与方法（现代优化计算方法）2内容概论递归、分治、贪心、回溯禁忌搜索、爬山算法模拟退火、蚁群算法遗传算法神经网络元胞自动机随机算法3背景传统实际问题的特点连续性问题——主要以微积分为基础，且问题规模较小传统的优化方法追求准确——精确解理论的完美——结果漂亮主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）4传统运筹学面临新挑战现代问题的特点离散性问题——主要以组合优化（针对离散问题，定义见后）理论为基础不确定性问题——随机性数学模型半结构或非结构化的问题——计算机模拟、决策支持系统大规模问题——并行计算、大型分解理论、近似理论现代优化方法追求满意——近似解实用性强——解决实际问题现代优化算法的评价方法算法复杂性5现代优化(启发式)方法种类禁忌搜索（tabusearch）模拟退火（simulatedannealing）遗传算法（geneticalgorithms）神经网络（neuralnetworks）蚁群算法（群体（群集）智能，SwarmIntelligence）拉格朗日松弛算法（lagrangeanrelaxation）61现代优化计算方法概述1.1组合优化问题1.2算法1.3计算复杂性的概念1.4启发式算法71.1组合优化问题组合优化（combinatorialoptimization）:解决离散问题的优化问题——运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。数学模型：决策变量有限点集约束函数目标函数,.,0)(..)(minDxxgtsxf81.1组合优化问题组合优化问题的三参数表示：.|)(min)(,:::,,0)(,|:),,(FxxfxfFxxFxfxgDxxFDfFD最优解，如果可行解（点）目标函数有限点集可行域决策变量定义域91.1组合优化问题例10-1背包问题（0-1knapsackproblem）装包？问题：如何以最大价值件物品单位价值，第件物品单位体积，第背包容积.,,1:.,,1::niicniiabii101.1组合优化问题.1,0i0i1(1.3).,,1,1,0(1.2),as.t.(1.1)maxn1ii1iniiiniiDxnixbxxc物品，不装第物品装第，其中决策变量包容量限制总价值数学模型：111.1组合优化问题例2旅行商问题（TSP,travelingsalesmanproblem）管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。121.1组合优化问题ij1ij1min(1.4)s.t.1.1,2,,,(1.5)i1.1,2,,,ijijijnjnidxxinxjn数学模型：总路长只从城市出来一次,(1.6)1,21,1,2,,,(1.7)0,1,,1,2,,,.(1.8):ij,s:s1,ijijsijijijjxssnsnxijnijdijx只走入城市一次在任意城市子集中不形成回路决策变量其中城市与城市之间的距离集合中元素的个数，走城市和城市0.:,,:,,ijjiijjiijTSPddijTSPddij之间的路径，，不走城市和城市之间的路径对称距离非对称距离131.1组合优化问题例3装箱问题（binpacking）尺寸为1的箱子有若干个，怎样用最少的箱子装下n个尺寸不超过1的物品，物品集合为：。12{,,...}naaa141.1组合优化问题11min..1,1,2,,,1,1,2,,,0,1,1,2,,;1,2,,,B:1,0.BibbniibiibibBstxinaxbBxinbBibxib数学模型：其中装下全部物品需要的箱子，第物品装在第个箱子，，第物品不装在第个箱子151.1组合优化问题例4约束机器排序问题（binpacking）n个加工量为{di|i=1,2,⋯,n}的产品在一台机器上加工,机器在第t个时段的工作能力为ct,求完成所有产品加工的最少时段数。161.1组合优化问题171.2算法评价算法的好坏——计算时间的多少、解的偏离程度先看看算法的基本概念一个有穷规则的有序集合称为一个算法。1.定义.2.算法的特征.输入：有零个或多个外部量作为算法的输入。输出：算法产生至少一个量作为输出。确定性：组成算法的每条指令清晰、无歧义。有限性：算法中每条指令的执行次数有限。可行性：执行每条指令的时间也有限。1.2算法1．有穷性对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成；2．确定性对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行。并且在任何条件下，算法都只有一条执行路径；3．可行性算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之；4．有输入作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中；5．有输出它是一组与“输入”与确定关系的量值，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。二、算法设计的原则设计算法时，通常应考虑达到以下目标：1．正确性2.可读性3．健壮性4．高效率与低存储量需求1．正确性首先，算法应当满足以特定的“规格说明”方式给出的需求。其次，对算法是否“正确”的理解有四个层次：a．程序中不含语法错误；b．程序对于几组输入数据能够得出满足要求的结果；c．程序对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得出满足要求的结果；通常以第c层意义的正确性作为衡量一个算法是否合格的标准。d．程序对于一切合法的输入数据都能得出满足要求的结果；2.可读性算法主要是为了人的阅读与交流，其次才是为计算机执行。因此算法应该易于人的理解；另一方面，晦涩难读的程序易于隐藏较多错误而难以调试；3．健壮性当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。4．高效率与低存储量需求通常，效率指的是算法执行时间；存储量指的是算法执行过程中所需的最大存储空间。两者都与问题的规模有关。算法的描述方法.（1）自然语言（2）流程图（3）程序设计语言例.求正整数m、n的最大公因数。解一.（1）求余数：用m除以n，得余数r(0≤r﹤n)。（2）判断余数：若余数r=0，输出n，结束。否则，转（3）。（3）更新被除数和除数：m←n，n←r，转(1)。解二.开始输入m、nr=m%nr=0?m←n，n←r输出n是否解三.Euclid(intm,intn){intr;while(n!=0){r=m%n;m=n;n=r;}printf(“%d”,m)}341.3计算复杂性的概念评价算法的好坏——计算时间的多少、解的偏离程度例非对称距离TSP问题的算法实现：所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：351.3计算复杂性的概念城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325year随城市增多，计算时间增加很快。到31个城市时，要计算325年。361.3计算复杂性的概念描述算法的好坏——计算复杂性——讨论计算时间与问题规模之间的关系以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。371.3计算复杂性的概念问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述：（1）对所有参数的一般性描述；（2）答案（或解）必须满足的性质。实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据；这些数据输入计算机所占的空间称为实例的长度（size）.381.3计算复杂性的概念一类最优化问题是由一些类似的具体问题（实例）组成的，每一个具体问题可表达成二元组（F,C）.F为可行解集合;C是费用函数，是由F到R（实数集）的映像。问题是在F中找到一个点f*，使对F中任意的f，有C(f*)C(f),称f*为这一具体问题的最优解（或全局最优解）.391.3计算复杂性的概念算法计算量的度量：加、减、乘、除、比较的总运算次数与实例的计算机计算时的二进制输入数据的大小关系。正整数x的二进制位数是:(整数到二进制的转换)2()()log(||1)2xlxlxx记的输入规模（编码长度）为，则其中2是考虑了1个符号位和1个数据分隔位。如何估算算法的时间复杂度？算法=控制结构+原操作算法的执行时间=元操作(i)的执行次数×元操作(i)的执行时间∑从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。431.3计算复杂性的概念算法计算量的度量之例——TSP枚举法21,,,(1)!(1)!!;(1)!!(1)!nniinnnnnnnn城市数第一城市为始终点，计算一条路径（,1）长度的基本运算为两两城市间距离的个数求和,共有条路径,求和运算次数为：枚举所有路径进行次比较可得最优路径,基本计算总次数为总计算量:计算量的统计：441.3计算复杂性的概念实例的输入长度：22,,(1)(log12)log12ijijdKLnnKn设对有则（）（）实例的输入长度是n的多项式函数枚举法的基本计算量是n的阶乘函数，随n的增加，比指数函数增加得还快.451.3计算复杂性的概念AAA,()AC(I)()(())()((()))()IlIgxC(I)glICIOglIgx实例实例规模：，算法基本计算总次数：存在函数和一个常数，使得对于该问题的任意实例Ｉ都满足　　　　　　（ＸＸ）则二者关系表示为：的性质决定了算法的性能。461.3计算复杂性的概念定义多项式算法给定问题P，算法A，对一个实例I，存在多项式函数g(x)，使（XX）成立，称算法A对实例I是多项式算法；若存在多项式函数g(x)，使（XX）对问题P的任意实例I都成立，称算法A为解决该问题P的多项式算法.当g(x)为指数函数时，称A为P的指数时间算法。471.3计算复杂性的概念利用复杂性分析对组合优化问题归类。定义多项式问题给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称多项式问题(或P问题).所有多项式问题的集合记为P.481.3计算复杂性的概念迄今为止,对许多的组合优化问题都没有找到求最优解的多项式时间算法,因此,比多项式问题更广泛的一类问题是非多项式确定(nondeterministicpolynomial,简记NP)问题。例一两个矩阵相乘voidmult(inta[],intb[],int&c[]){//以二维数组存储矩阵元素，c为a和b的乘积for(i=1;i=n;++i)for(j=1;j=n;++j){c[i,j]=0;for(k=1;k=n;++k)c[i,j]+=a[i,k]*b[k,j];}//for}//mult基本操作:乘法操作时间复杂度:O(n3)常用的时间复杂度有如下的关系：O(1)=O(log2n)=O(n)=O(nlog2n)=O(n2)=O(2n)=O(n!)四、算法的存储空间需求算法的空间复杂度定义为:表示随着问