数学建模组合优化问题和计算复杂性.ppt

第一章组合优化问题和计算复杂性,1.1组合优化问题与算法1.2计算复杂性问题1.3启发式算法,1.1组合优化问题与算法,共有3!=6种可能,得到分配矩阵：,如何嫁娶，使获得的礼品最多？,Example1婚姻问题(matchingproblem),3,27,1,5,10,4,26,28,7,1.1组合优化问题与算法,婚姻问题的数学模型：,设：,1.1组合优化问题与算法,贪婪（Greedy)解一般不会产生最差解；,在某些模型中,贪婪算法能得到最优解；,3.可以使用穷举法，但是以时间为代价,贪婪解的结果：28+5+1=34,最优解的结果：27+4+26=57,Note：,1.1组合优化问题与算法,Example2背包问题（KP，KnapsackProblem）,假设有人要出发旅行,他考虑要带7种物品（每件物品的重量与价值如表）现在假设他最多带35kg物品，问：该带哪几件物品总价值最大？,设：,共有27种可能,1.1组合优化问题与算法,Example3旅行商问题（TSP,TravellingSalesmanProblem),一个商人要到n座城市去做生意，设两个城市i和j之间的距离为dij.如何选择一条道路使得商人每个城市走一遍后回到起点且所走路程最短,TSP可分为：对称（dij=dji)和非对称(dijdji)距离两种,共有（n-1)!种可能,1.1组合优化问题与算法,设：,TSP问题的数学模型：,为了减少变量个数,作用是什么,共有多少变量？,n(n-1),1.1组合优化问题与算法,若|s|=n则由n个点构成的一个回路是可行方案。,因为由前面两个约束条件的限制，不可能由n-1个点构成回路而留一个点在外面。,Note：条件(1)，(2)表示每个城市经过一次，但不能保证它可行，要求局部不构成圈，条件(3)就是为了约束这一点。,为什么？,1.1组合优化问题与算法,共同特点：可行方案是有限的组合优化问题,Definition1组合优化问题是一个极小化（或极大化）的问题，它是由以下三部分组成：,（1）实例集合；,（2）对每个实例I，有一个有穷的可行解集合S（I）,(3)目标函数f，它对于每个实例I和每个可行解S（I），赋以一个有理数f(I,).则实例I的最优解为这样一个可行解*S(I),它使得对于所有S（I），都有f(I,*)f(I,)（f(I,*)f(I,)）。,1.1组合优化问题与算法,组合优化的数学模型：,Minf(x)s.t.g(x)0 xD,其中x为决策变量,f(x)为目标函数,g(x)为约束函数,D为决策变量的定义域，D为有限集合。,F=x|xD,g(x)0可行域,所以，可由（D，F，f）定义一个组合优化问题。,组合优化的描述方法：,1数学模型（规划模型）,2文字语言叙述,1.1组合优化问题与算法,一类实际问题的数学模型的总称，如TSP、LPetc.,（一个问题中总包含了若干个参数）对问题给定一组参数所得到的例子。,一个科学的计算过程，指一步步求解问题的通用程序，它是解决问题的程序步骤的一个清晰描述。,算法是相对问题而言的，不单单是针对问题的某个实例。,如果算法从前一步到后一步的运行是由当时状态唯一确定的如：单纯形法，表上作业法。,遗传算法是随机性算法。,问题：,实例：,算法：,Note：,确定性算法：,1.1组合优化问题与算法,对于一个极小化（极大化）优化问题，如果给定任意一个实例I，算法A总能找到一个可行解*S(I)。使得f(I,*)f(I,)（f(I,*)f(I,)）,启发式算法（近似算法，在1.3节中介绍）,组合优化总存在最优算法，但它以时间为代价,最优算法：,返回,1.2计算复杂性问题,在广泛的意义下，执行算法的效率是用执行算法所用的全部计算资源的多少来衡量(时间、空间),但通常用时间作为衡量标准，这就是计算(时间)复杂性问题.,设有n个城市(有向图)则有(n-1)！种可能方案。以计算机1秒可以完成24个城市所有路径枚举为单位，则,讨论TSP问题,1s,24s,10min,4.3h,4.9d,136.5d,10.8y,325y,1.2计算复杂性问题,一、如何计算时间,1与实例的输入规模有关，是输入规模的函数（输入规模指的是：一个问题的实例所有参数的二进制表示的长度的总和。可简化为决策变量的个数n，或者顶点的个数m.）f(n),g(m)etc.,用初等运算算术运算、比较、转移等指令的次数，来表示一个算法在假设的计算机上执行时所需的时间。,相关因素:,1.2计算复杂性问题,2与实例的参数有关，如LP问题：maxz=cxs.t.Axbx0,c0,b0,算法的时间复杂性是关于实例输入长度的函数，用来表示算法的时间需求。对于每一个可能的输入长度，它是该算法解此输入长度的最坏可能的实例所需的时间（基本运算步骤）。,相关因素:,Definition2,1.2计算复杂性问题,研究计算复杂性问题主要是针对n很大的情形,19n2与2n2O(n2),2f(n)=12n4-8n3+5n2+2n-80,f(n)=O(n4),当n无限增大时，,Lnn,n(0),an（a1）,趋向于无穷大的速度如何？,Note：,问：,1.2计算复杂性问题,二、如何评价算法的好坏（从计算复杂性角度）,复杂性分析的一个研究方向：对算法进行评价,给定n个整数x1，x2，xn，要求将他们从小到大重新排列,取出x1，x2，xn中的最小者（需比较n-1次）令其为b1（需n赋值次），从x1，x2，xn中去掉b1，在余下的n-1个数中选出最小者，令其为b2，直到得到b1,b2,bn，易知其算法共做了n(n-1)/2次比较，至多n(n+1)/2次赋值，计算复杂性为，O(n2).,Example4整序问题：,比较交换法：,1.2计算复杂性问题,先将两个单调不减的数列u1，u2um与v1，v2vm合并为一个单调不减的数列w1，w2w2m方法为u1与v1比较,若u1v1，w1:=v1。再对u1与v2进行比较，依次对w2，w3w2m赋值，计算量为O(m)。,快速算法：,将x1，x2，xn从小到大重新排列（设：n=2p+1如果n不是2的幂次可补充若干个很大的数字使之成为2的幂次）。,确定一个wj需要一次比较一次赋值，共需要（2m-1）次比较，2m次赋值。,1.2计算复杂性问题,将2p+1个数分成2p个单调不减的2元组,计算量为O(2p),O(2p)=2p-1O(2),计算量为O（2p）,综上，算法总工作量为：(p+1)*O(2p)=O(nlogn),81967532,(81)(96)(75)(32),18695723,(1869)(5723),16892357,12356789,将2元组两两合并成2p-1个单调不减的4元组，计算量为O(2p),依次类推，最后将两个2p元组合并成为一个单调不减的2p+1元组,2p+1=n,1.2计算复杂性问题,设机器速度100万次/秒,快速算法O(nlogn)需20秒,设计算机速度为M次/秒,问题D,算法A计算复杂性n2,算法B计算复杂性2n,给定1秒的机器时间,算法A可解规模,算法B可解规模,n=100万,比较交换法O(n2)需5.8天,M=n2,1.2计算复杂性问题,设机器速度100万次/秒,给定1秒的机器时间,算法A可解规模n=,算法B可解规模n=,给定1秒的机器时间,算法A可解规模n=1000,算法B可解规模n=20,设机器速度提高100倍为1亿次/秒,给定1秒的机器时间,算法A可解规模n=100010,算法B可解规模n=20+log2100,Log21000,称H是A的a-近似算法（a-approximationalgorithm）,当且仅当|ZH(I)-Zopt(I)|a|Zopt(I)|,用启发式概念定义的算法集合包含了近似算法概念定义的算法集合，近似算法强调给出算法最坏情况的误差界限，而启发式算法不需考虑偏差程度。,1.3启发式算法,算法为:step1任选一个初始解soS；step2在N(so)中按某一规则选一s，若f(s)f(so)，则so:=s返回step2；否则，N(so):=N(so)-s;若N(so)=，停止;否则，返回step2.,Example10简单的邻域搜索（localsearch）算法,给定组合优化问题，假设其邻域结构已确定，设S为可行解集合，f为S上的费用函数，N为邻域结构。,1.3启发式算法,简单的邻域搜索达到一个局部最优点,依赖于初始解选取、邻域结构、邻域选点的规则,启发式算法的长处：,1）数学模型是实际问题的简化，有可能使最优算法所得解比启发式算法所得解产生更大误差；,2）不少难的组合优化问题可能还没找到有效的最优算法；,3）一些启发式算法可以用在最优算法中，如在分支定界算法中，可以用启发式算法估界；,1.3启发式算法,4）简单易行，比较直观，易被使用者接受；,5）速度快，在适时管理中非常重要；,6）多数情况下，程序简单，因此易于修改。,1）不能保证求得最优解；,启发式算法的不足：,2）表现不稳定；,3）算法的好坏依赖于实际问题、经验和设计者的技术，使不同算法之间难以比较。,1.3启发式算法,三、常见启发式算法类型,1、一步算法,该算法的特点是：不在两个可行解之间选择，在未终止的迭代中，有可能不是一个可行解，算法结束时得到一个可行解。,Example11最优H-回路的路线搜索算法,Step1,Step2,1,2,3,4,5,1,3,8,2,3,5,2,1,3,3,Z=15依赖于数据特征和初始点的选取，从2开始可得更好的解,1.3启发式算法,该算法的特点是：从一个可行解到另一个可行解的选择，通常通过两个解的比较而选择好的解，进而作为新的起点进行新的迭代，直到满足一定的要求为止。,2、改进算法,如简单的邻域搜索算法。,四个城市1，2，3，4的TSP问题，两个城市i和j之间的距离dij构成的距离矩阵为,Example12TSP中简单的2-opt方法,f(so)=d12+d23+d34+d41=5+7+6+12=30,设初始点为so=(1,2,3,4)则,1.3启发式算法,so的2-opt邻域是对so的任两个元素对换，如果固定第一个城市1，即,简单的2-opt方法是比较邻域中的所有点，选出最好解。比较可知N(so)中最好的解为s1=(1,2,4,3),目标值f(s1)=29,下一次迭代是以s1重复以上的计算过程，直到目标值无法改进为止。,N(so)=(1,3,2,4),(1,4,3,2),(1,2,4,3),数学规划算法、解空间松弛算法、现代优化算法,1.3启发式算法,四启发式算法的性能分析,评价启发式算法的性能有不同的角度，主要分为：,（1）对算法复杂性的分析,（2）对算法计算效能的分析,对随机算法还要考虑稳定性,性能分析的常用方法,（1）最坏情形分析（2）概率分析（3）大规模计算分析,每个方法都可以从以上两个角度进行分析,1.3启发式算法,（1）最坏情形分析,从最坏情形分析评价一个算法的计算效果时，其评价的指标是计算解的目标值同最优目标值最坏情形时的差距，这个差距越小，说明算法越好。,Definition10,若D是一个极大化问题，实例I的最优值为Zopt(I),启发式算法H所得的解值为ZH(I)，记,则启发式算法H的绝对性能比RH定义为,1.3启发式算法,如何求（或证明）RH=a,寻找（证明）存在常数a使得对任意的实例I,有ZH(I)aZopt(I)则RHa；,界,构造实例I使,或构造一系列实例In使,则RHa,从而有RH=a,1.3启发式算法,启发式算法H的渐近性能比,启发式算法的性能比是对算法近似程度的一种最坏情形分析，,越接近1表示启发式,解越接近最优解。,一般有,1.3启发式算法,（2）概率分析,最坏情形分析是以最坏的实例来评价一个算法或其解，这样不免会只因一个实例而影响对一个算法或其解的总体评价。,概率分析则是假设实例的数据服从一定的概率分布，在这个数据概率分布的假设下，研究其算法或解的平均效果。,概率分析在评价算法方面的一个成功应用是对LP的单纯形法的评价。,最坏情形分析和概率分析方法的共同特点，用理论方法分析算法同最优解之间的误差界，要求有较强的数学基础。,1.3启发式算法,（3）大规模计算分析,实际中大量的组合优化问题是采用大规模计算分析,大规模计算分析就是通过大量的实例计算评价算法的计算效果,算法的计算效果分成两个方面：,计算复杂性：它的效果通过计算机的中央处理器（CPU）的计算时间表现；,计算解的性能：它通过计算停止时,输出的解表现。,1.3启发式算法,对一个算法