最优化理论与方法 第一章.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,最优化理论与方法,（现代优化计算方法）,2,内 容,概论,递归、分治、贪心、回溯,禁忌搜索、爬山算法,模拟退火、蚁群算法,遗传算法,神经网络,元胞自动机,随机算法,3,背 景,传统实际问题的特点,连续性问题,主要以微积分为基础，且问题规模较小,传统的优化方法,追求准确,精确解,理论的完美,结果漂亮,主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。,传统的评价方法,算法收敛性（从极限角度考虑）,收敛速度（线性、超线性、二次收敛等）,4,传统运筹学面临新挑战,现代问题的特点,离散性问题,主要以组合优化（针对离散问题，定义见后）理论为基础,不确定性问题,随机性数学模型,半结构或非结构化的问题,计算机模拟、决策支持系统,大规模问题,并行计算、大型分解理论、近似理论,现代优化方法,追求满意,近似解,实用性强,解决实际问题,现代优化算法的评价方法,算法复杂性,5,现代优化,(,启发式,),方法种类,禁忌搜索（,tabu,search,）,模拟退火（,simulated annealing,）,遗传算法（,genetic algorithms,）,神经网络（,neural networks,）,蚁群算法（群体（群集）智能，,Swarm Intelligence,）,拉格朗日松弛算法（,lagrangean,relaxation,）,6,1,现代优化计算方法概述,1.1,组合优化问题,1.2,算法,1.3,计算复杂性的概念,1.4,启发式算法,7,1.1,组合优化问题,组合优化（,combinatorial optimization,）,:,解决离散问题的优化问题,运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。,数学模型：,8,1.1,组合优化问题,组合优化问题的三参数表示：,9,1.1,组合优化问题,例1 0-1背包问题（0-1,knapsack problem,）,10,1.1,组合优化问题,11,1.1,组合优化问题,例2 旅行商问题（,TSP,traveling salesman problem,）,管梅谷教授,1960,年首先提出，国际上称之为中国邮递员问题。,问题描述：一商人去,n,个城市销货，所有城市走一遍再回到起点，使所走路程最短。,12,1.1,组合优化问题,13,1.1,组合优化问题,例,3,装箱问题（,bin packing,）,尺寸为1的箱子有若干个，怎样用最少的箱子装下,n,个尺寸不超过1 的物品，物品集合为：。,14,1.1,组合优化问题,15,1.1,组合优化问题,例,4,约束机器排序问题（,bin packing,）,n,个加工量为,d,i,|i=1,2,n,的产品在一台机器上加工,机器在第,t,个时段的工作能力为,c,t,求完成所有产品加工的最少时段数。,16,1.1,组合优化问题,17,1.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(0rn)。,（2）判断余数：若余数,r=0，,输出,n，,结束。,否则，转（3）。,（3）更新被除数和除数：,mn，nr，,转(1,)。,解二.,开 始,输入,m、n,r=m%n,r=0?,mn，nr,输出,n,是,否,解三.,Euclid(,int,m,int,n,),int,r;,while(,n,!=0),r,=,m,%,n;,m,=,n;,n,=,r;,printf,(,“,%,d”,m,),34,1.3,计算复杂性的概念,评价算法的好坏,计算时间的多少、解的偏离程度,例 非对称距离,TSP,问题的算法实现：所有路径枚举。,计算时间：,n,个城市，固定1个为起终点需要,(n-1)!,个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：,35,1.3,计算复杂性的概念,城市数,2,4,25,26,27,28,29,30,31,计算时间,1,sec,24,sec,10,min,4.3,hour,4.9,day,136.5,day,10.8,year,325,year,随城市增多，计算时间增加很快。到31个城市时，要计算325年。,36,1.3,计算复杂性的概念,描述算法的好坏,计算复杂性,讨论计算时间与问题规模之间的关系,以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。,37,1.3,计算复杂性的概念,问题,（,problem,）,：,要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述：,（1）对所有参数的一般性描述；,（2）答案（或解）必须满足的性质。,实例,（,instance,）,:,给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为,数据,；这些数据输入计算机所占的空间称为,实例的长度,（,size,）,.,38,1.3,计算复杂性的概念,一类最优化问题是由一些类似的具体问题（实例）组成的，每一个具体问题可表达成二元组（,F,C,）,.,F,为可行解集合,;C,是费用函数，是由,F,到,R,（实数集）的映像。,问题是在,F,中找到一个点,f,*，使对,F,中任意的,f,，有,C(f*)C(f),称,f*,为这一具体问题的最优解（或全局最优解）.,39,1.3,计算复杂性的概念,算法计算量的度量：,加、减、乘、除、比较的总运算次数与实例的计算机计算时的二进制输入数据的大小关系。,正整数,x,的二进制位数是,:(,整数到二进制的转换,),如何估算,算法的时间复杂度？,算法,=,控制结构,+,原操作,算法的执行时间,=,元操作,(,i),的执行次数,元操作,(,i),的执行时间,从算法中选取一种对于所研究的问题来说是,基本操作,的原操作，以该基本操作,在算法中重复执行的次数,作为算法运行时间的衡量准则。,43,1.3,计算复杂性的概念,算法计算量的度量之例,TSP,枚举法,计算量的统计：,44,1.3,计算复杂性的概念,实例的输入长度：,实例的输入长度是,n,的多项式函数,枚举法的基本计算量是,n,的阶乘函数，,随,n,的增加，比指数函数增加得还快,.,45,1.3,计算复杂性的概念,46,1.3,计算复杂性的概念,定义,多项式算法,给定问题,P,，算法,A,，对一个实例,I,，存在多项式,函数,g(x),，使（,XX,）成立，称,算法,A,对实例,I,是,多项式算法,；,若存在多项式函数,g(x),，使（,XX,）对问题,P,的任,意实例,I,都成立，称,算法,A,为解决该问题,P,的多项,式算法.,当,g(x),为指数函数时，称,A,为,P,的指数时间算法。,47,1.3,计算复杂性的概念,利用复杂性分析对组合优化问题归类。,定义,多项式问题,给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称,多项式问题(或,P,问题),.所有多项式问题的集合记为,P.,48,1.3,计算复杂性的概念,迄今为止,对许多的组合优化问题都没有找到求最优解的多项式时间算法,因此,比多项式问题更广泛的一类问题是非多项式,确定,(nondeterministic polynomial,简记,NP),问题。,例,一,两,个,矩,阵,相,乘,void,mult,(,int,a,int,b,int,&,c),/,以二维数组存储矩阵元素，,c,为,a,和,b,的乘积,for,(i=1;i=n;+i),for,(j=1;j=n;+j),ci,j=0;,for,(k=1;k=n;,+,k),ci,j+=,ai,k,*,bk,j;,/for,/,mult,基本操作,:,乘法,操作,时间复杂度,:,O(n,3,),常用的时间复杂度有如下的关系：,O(1)=O(log,2,n)=O(n),=O(nlog,2,n)=O(n,2,)=,O(2,n,),=O(n!),四、算法的存储空间需求,算法的,空间复杂度定义为,:,表示随着问题规模,n,的增大，,算法运行所需存储量的增长率,与,g(n),的增长率相同。,S(n)=O(g(n),算法的存储量,包括,:,1,输入数据,所占空间,2,程序本身,所占空间,；,3,辅助变量,所占空间,。,53,1.3,计算复杂性参考书,计算复杂性,作者：,Christos,，,Papadimitriou,清华大学出版社，,2004,年,9月,第,1,版,计算复杂性导论，,作者：堵丁柱等，,高等教育出版社，2002年8月第1版,邻域概念,对于组合优化问题(,D,F,f),D,上的一个映射：,N:S,D N(S)2,D,称为一个邻域映射，其中,2,D,表示,D,的所有子集构成的集合，,N(S),称为,S,的邻域。,邻域的构造依赖于问题决策变量的表示，邻域的结构在现代化优化算法中起重要作用。,1.4,启发式算法,邻域概念,例如,TSP,问题解的另一种表示法为,D=S=(i,1,i,2,i,n,),是1,2,n,的一个排列,可以定义它的邻域映射为2-,opt，,即,S,中的两个元素对换。,1.4,启发式算法,邻域概念,1.4,启发式算法,如4个城市的,TSP,问题，当,S=(1,2,3,4),时，,N(S)=(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(,1,2,4,3).,类似可定义,k-opt(k,2),局部最优与全局最优,1.4,启发式算法,若,s*,满足,f(s*),()f(s),其中,sN(s*)F,则称,s*,为,f,在,F,上的局部(,local),最小（最大）解。,若,s*,满足,f(s*),()f(s),其中,sF,则称,s*,为,f,在,F,上的全局(,global),最小（最大）解。,58,1.4,启发式算法,启发式算法（,heuristic algorithm,）,定义1.,基于,直观或经验,构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个,可行解,，该可行解与最优解偏差事先不一定可以预计.,定义2.,启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。,特点（与传统优化方法不同）：,凭直观和经验给出算法；不考虑所得解与最优解的偏离程度.,近似算法定义,记问题,A,的任何一个实例,I,的最优解和启发式算法,H,解的目标值分别为,z,opt,(I,),和,z,H,(I,),若对某个正数,0，有,|,z,H,(I)-z,opt,(I,)|,|,z,opt,(I)|，,IA,则称,H,是,A,的近似算法。,1.4,启发式算法,60,1.4,启发式算法,优点：,（,1,）有可能比简化数学模型解的误差小；,（,2,）对有些难题，计算时间可接受；,（,3,）可用于某些最优化算法（如分支定界算,法）之中的估界；,（,4,）直观易行；,（,5,）速度较快；,（,6,）程序简单，易修改。,61,1.4,启发式算法,不足：,（,1,）不能保证求得全局最优解；,（,2,）解的精度不稳定，有时好有时坏；,（,3,）算法设计与问题、设计者经验、技术 有关，缺乏规律性；,（,4,）不同算法之间难以比较。,背包问题的贪婪算法,1）将物品以,c,i,/a,i,（,单位体积的价值）由大到小的顺序排列，不妨把排列记为1,2,n,k,:=1;,2）,若 ，则,x,k,=1;,否则,x,k,=0,k:=k+1;,3),当,k=n+1,时，停止；否则，转2).,(,x,1,x,2,x,n,),为贪婪算法所得解，单位体积的价值越大越先放入是贪婪算法的原则。,1.4,启发式算法,简单的邻域搜索算法,给定组合优化问题，假设其邻域结构已确定，算法为,1）任选一个初始解,s,0,F;,2),在,N(s,0,),中按某一规则选一,s；,若,f(s,)f(s,0,),则,s,0,s；,否则，,N(s,0,)N(s,0,)-s;,3),若,N(s,0,)=,停止；否则，返回2).,1.4,启发式算法,算法停止时得到点的性质依赖算法初始解的选取、邻域的结构.,只要选好初始点，就一定可以求到最优解。对,NP-hard,的组合最优化问题，确定这样的初始点非常困难。如何选初始点和如何跳出局部最优值点以达到全局最优点是许多算法的关键。,1.4,启发式算法,65,1.4,启发式算法,（1）一步算法,（2）改进算法（迭代算法）,（3）数学规划算法,（,4,）解空间松弛法,（,5,）现代优化算法,66,1.4,启发式算法,一步算法,该算法的特点是,:,不在两个可行解之间选择,在未终止的迭代中,有可能不是一个可行解,算法结束时得到一个可行解,.,典型实例是背包问题的贪婪算法,67,1.4,启发式算法,一步算法,该算法的特点是,:,不在两个可行解之间选择,在未终止的迭代中,有可能不是一个可行解,算法结束时得到一个可行解,.,典型实例是背包问题的贪婪算法,68,1.4,启发式算法,改进算法,改进算法的迭代过程是从一个可行解到另一个可行解,通常通过两个解的比较而选择好的解,进而作为新的起点进行新的迭代,直到满足一定的要求为止,.,因此,也可以称之为迭代算法。,69,1.4,启发式算法,改进算法,T SP,中的,2-opt,方法,70,1.4,启发式算法,(3)数学规划算法,运筹学内容,(4),解空间松弛法,后续展开,71,1.4,启发式算法,（5）现代优化算法：,80年代初兴起,禁忌搜索（,tabu search,）,模拟退火（,simulated annealing,）,遗传算法（,genetic algorithms,）,神经网络（,neural networks,）,蚂蚁算法（,Ant Algorithm,，,群体（群集）智能，,Swarm Intelligence,）,（6）其他算法：,多种启发式算法的集成.,72,1.4,启发式算法,计算复杂度分析：,如背包问题贪婪算法,n,次除法,n,个数排序,2n,次比较,