高等运筹学(总).ppt

1,高等运筹学,符卓Tel:82655051mail:zhfu中南大学交通运输工程学院（办公室：交通楼415）,2,课程内容特点,基础运筹学：单目标优化，精确算法。高等运筹学：多目标优化，启发式算法。,3,主要内容,概论现代运筹学的理念柔性多目标规划经典启发式方法模拟退火算法禁忌搜索算法遗传算法,4,第1章概论,1.1运筹学概述1.2最优化问题及其分类1.3计算复杂性概述1.4优化算法及其分类1.5邻域与局部搜索,5,1.1运筹学概述,1.运筹学的产生和发展二战期间，英国海军部召集了一个专家小组，称为“OperationalResearch”小组，美国武装部队的规划总部也建立了一个类似的专家小组，称为“OperationsResearch”小组，从事军事运筹方面的研究。战后，运筹学的方法广泛应用于民用企业，以解决复杂的经营管理问题，并促进运筹学发展成为一门独立的学科。该学科的英文名称就是OperationalResearch或OperationsResearch,简称OR。,6,英国：1948年成立运筹学俱乐部，1950年创办第一份运筹学刊物“OperationalResearchQuarterly”，该俱乐部于1953年改名为运筹学会，刊物也更名为“JournaloftheOperationalResearchSociety”。美国：1952年成立运筹学会，并创刊“OperationsResearch”。中国：1956年在中科院成立我国第一个运筹学小组，1980年成立运筹学会，1982年成为国际运筹学联合会会员国。现创办的主要刊物有“运筹学学报”和“运筹与管理”、“JournaloftheOperationsResearchSocietyofChina”。相关的学术刊物还有很多。“运筹帷幄之中，决胜千里之外”与“运筹学”。OR的发展与计算机的发展分不开。如果没有计算机，OR只不过是一种理论科学，不会成为应用科学。,7,8,2.运筹学的组成部分运筹学研究的现象有三类：一是资源运用的问题，二是竞争现象，三是拥挤现象。其内容相应地划分为三个组成部分：运用分析理论，竞争理论，随机服务理论。运用分析理论：包括分配、选址、资源最佳利用、设备最佳运行等。常用的数学方法有线性规划、非线性规划、网络规划、动态规划、最优控制等。竞争理论：主要方法是对策论。随机服务理论：主要方法是排队论。,9,3.运筹学的性质核心：运用数学方法研究各种系统的优化途径和方案，为决策者提供科学决策依据。研究对象：人类对各种资源的运用及筹划活动。研究方法：定量化和模型化，尤其是运用各种数学模型和优化技术。研究目的：了解和发现这些运用及活动的基本规律，发挥有限资源的最大效益。OR：TheScienceofBetterDecisions.ORusesmathematics,butitisnotabranchofmathematics.,10,4.运筹学的特点强调研究过程的完整性：问题的提出建立模型提出解案付诸实施。强调理论与实践的结合。5.运筹学的应用领域其影响继续扩大：国际运筹学联合会已有50个成员国。应用领域不断增加：如军事运筹学、管理运筹学、交通运输运筹学、工业运筹学、农业运筹学、工程技术运筹学、计算运筹学等。总之，凡是在某些有限的资源限制下寻求一个最优的行动方案，运筹学就有可能用得上。,11,1.2最优化问题及其分类,最优化指最小化或最大化，本课程以最小化为例。最优化问题可分为函数优化问题和组合优化问题两大类。1.函数优化问题优化的对象是可在一定区间内取值的连续变量。2.组合优化问题优化的对象是解空间中的离散状态，即哪一个组合对象最优？解决的是离散事件的最优编排、分组、次序或筛选等问题，是运筹学中一个经典且重要的分支。涉及管理、交通运输、通信网络等诸多领域。,12,组合优化问题可用数学模型描述为：minf(x)s.t.g(x)0,xS,其中，f(x)为目标函数，g(x)为约束函数，x为决策变量，S表示有限个点组成的集合。一个组合优化问题也可用三个参数（S,F,f）来描述：S：决策变量的定义域，即解空间；F=x|xS,g(x)0：可行解区域；f：目标函数值，满足f(x*)=minf(x)|xF的可行解x*称为该问题的最优解。组合优化的特点：可行解集合为有限点集。,13,几个典型组合优化问题：(1)旅行商问题（travelingsalesmanproblem,TSP）一个商人欲到n个城市巡回推销商品，已知城市i和j之间的距离为dij，如何确定一条巡回路线，使得商人从其中的某一城市出发，经过其他城市一次且仅一次后回到原出发点，且所走的路程最短。设,14,则该问题的一种数学模型为：s.t.xij0,1,i,j=1,2,n,ij.参考指派问题数学模型,15,指派问题数学模型为：s.t.xij=0或1,i,j=1,2,n,.,16,(2)0-1背包问题（knapsackproblem）对于n个体积分别为ai(1,2,n)，价值分别为ci(1,2,n)的物品，如何将它们装入总体积为b的背包中，使得所选物品的总价值最大？设则该问题可用数学模型表示为：s.t.xi0,1,i=1,2,n,17,(3)装箱问题（binpackingproblem）如何以个数最少的尺寸为1单位的箱子装入n个尺寸不超过1单位的物品。(4)机器排序问题（machineschedulingproblem）。有n个工件需要在机床A、B上加工，每个工件都必须经过先A而后B的两道工序。以Aj和Bj分别表示工件j（j=1,2,n）在A和B上的加工时间。问应如何安排各工件加工的顺序，才能使从机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止，所用的加工总时间最少？在组合优化问题中，有些可以用整数规划模型表示，有些则用文字叙述更易理解。上述问题描述均非常简单，但求其最优解确很困难。,18,1.3计算复杂性概述,1.算法及算法分析算法:能被机械地执行的动作（或规则）的有限集合，一个动作的一次执行称为一步。算法特征：输入、确定性、可执行性、有限性、输出。算法分析：对算法性能的讨论。算法分析目的：对同一问题的各种可实现的算法进行比较，对它们的性能作出定量的判断。确定算法是否存在什么性能上的限制，给算法设计提供理论上的指导。,19,算法复杂性：算法对时间和空间的需要量分别称为算法的时间复杂性和空间复杂性。算法执行基本操作的次数定义为算法的时间复杂性，记为T(n)；算法执行期间占用的计算机存储单元定义为算法的空间复杂性，记为S(n)。对于占用存储空间不是太多的问题，一般只讨论算法的时间复杂性。算法的复杂性的表示：一般表示为问题规模n（如TSP中的城市数）的函数。当一个算法A对于规模为n的问题进行求解计算时，若所需的基本操作次数的上界（指在最坏情况下）为f(n)，则称f(n)为算法A的时间复杂性函数。在分析复杂性时，可用其函数主要项的阶O(f(n)来表示。,20,若算法A的时间复杂性为T(n)=O(f(n)，且f(n)为n的多项式函数，如O(n)、O(n3)等，则称算法A为多项式算法。时间复杂性函数不属于n的多项式函数的算法统称为指数算法，如f(n)为2n、n!、nn等形式。算法性能：多项式算法是有效算法；指数算法不是有效算法。另外，多项式算法有较好的“闭”性。问题的难易性：若一个问题找到了多项式算法，就可以认为这个问题基本解决了。若一个问题不存在多项式算法，则称这个问题是难解的。有少数复杂度为指数函数的算法，在实践中却被证明是有效的算法，如求解线性规划问题的单纯形法就是一个突出的例子。,21,2.P,NP,NP完全和NP难P类和NP类问题若问题有求解它的多项式算法，则属于P类问题。若问题仍没有找到求其最优解的多项式算法，则称这类问题为非多项式确定问题，即NP类问题。NP完全问题NP完全（NP-complete,NP-C）问题是NP类问题中难度最大的一类问题。为证明一个问题是NP完全的，须证明：该问题是NP的；所有其他NP问题可多项式归约（变换）到该问题。现已证明的NP完全问题已上千个，但没有找到任一问题的多项式算法。性质：任一NP完全问题都不能用任何已知的多项式算法求解；若任一NP完全问题有多项式算法，则一切NP完全问题都有多项式算法。,22,NP难问题有些问题，不能验证它属于NP类，但可以证明所有NP问题都可以多项式归约为该问题，则这类问题称为NP难问题（NP-hard）。一个问题是NP难问题不要求该问题属于NP类，但至少和NP完全问题有同等的难度。,PNPNP完全NP难图1.1四类问题的关系图,23,1.4优化算法及其分类,优化算法：是基于某种思想和机制建立起来的、能求出满足问题要求的解的一种搜索途径或规则。按求解精度分类：精确算法（exactalgorithm）：基于严格的数学推导和证明建立起来的、可求出问题最优解的算法，且一般要求问题能用数学模型表示，但对大规模问题计算量大，应用范围常常受到限制。启发式算法（heuristicalgorithm）：基于直观或经验构造的算法，且一般不要求将问题表述为某种标准数学模型；在可接受的计算量内求出问题的可行解，但不能保证解的最优性。,24,按优化机制与行为分类：经典算法：包括线性规划、动态规划、整数规划和分枝定界等运筹学中的传统算法。构造算法：用构造的方法快速建立问题的一个可行解。如运输问题中的最小元素法。邻域搜索算法：从任一初始解出发，对其邻域的不断搜索和当前解的替换来逐步实现优化。根据搜索行为，又可将其分为局部搜索法和指导性搜索法。基于系统动态演化的方法：将优化过程转化为系统动态的演化过程，以系统动态的演化来实现优化。混合型算法：上述各算法从结构或操作上相混合而产生的各类算法。按其它角度分类：如确定性算法和随机性算法；局部优化算法和全局优化算法等。,25,1.5邻域与局部搜索,1.邻域（neighbourhood）定义:在距离空间中：是指以一点为中心的一个球体。在组合优化中：设某问题所有解构成的解空间为S。对于每个解xiS，有一个在某种意义上是“邻近”xi的解的集合，称集合N(xi)为xi的邻域，每个xjN(xi)称为xi的一个邻域解或邻居（neighbour）。此外，通常约定xjN(xi)=xiN(xj)。,26,2.邻域结构（neighbourhoodstructure，也称邻域函数或解产生函数）其作用是指导如何由一个解来产生一个新的解。设计往往依赖于问题的特性和解的表达方式。函数优化与组合优化中的邻域结构的具体方式存在明显差异：函数优化中：利用距离的概念通过附加扰动来构造邻域结构是最常用的方法，如x=x+，其中x为新解，x为当前解，为尺度参数，为满足某种概率分布的随机数或梯度信息等。组合优化中：因传统的距离概念不再适用，但邻域结构的基本思想仍旧是通过对一个解进行适当变换后产生另一个解。,27,如TSP的解可用置换排列来表示，如排列（1,2,3,4）可表示为有4个城市的TSP的一个解。那么，k个点的交换就可认为是一种邻域结构，即Nk=xjN(xi)|xj可由xi经一次k交换得到如上述排列的2点交换对应的邻域结构将产生新解（2,1,3,4）、（3,2,1,4）等。3.局部最优和全局最优定义：令（S,F,f）为一个优化问题，其中S为所有解构成的解空间，F为S上的可行域，f为目标函数，设为解x*的邻域，若xN(xi)F，满足f(x*)()f(x)，则称x*为f在F上的局部最小（最大）解（点）；若xF，满足f(x*)()f(x)，则称x*为f在F上的全局最小（最大）解（点）。,28,以一维变量x为例，假设可行域为区间1,10中的整数点，目标函数值如图1.2所示，如果采用如下邻域定义：N(x)=xZ+|x-x|1，则x=9为全局最小点；x=5为局部最小点；而x=4既不是局部最大点也不是局部最小点。f(x)+O12345678910 x图1.2局部最优解示意图,29,4.局部搜索算法（localsearch）是一种传统的优化算法，是基于贪婪思想利用邻域结构进行搜索的。又有两种实现方式：上（下）山法：一旦搜索到一个更好的解，就立即接受其作为新的当前解；最陡下降法：只接受当前解整个邻域中的最好解作为下一当前解。以下山法为例介绍求目标函数值最小的局部搜索算法：从一个初始解x0F出发，利用邻域结构持续地在当前解xi的邻域中搜索比它更好的解，若能够找到这样的解，就用这个解取代xi，成为新的当前解，再对当前解重复上述过程；否则搜索过程终止，并以当前解作为算法的最终解。,30,用伪Pascal语言描述的局部搜索算法：ProcedureLocal_Search;Begin任选一初始解x0；xi:=x0（置初始解为当前解）repeat从邻域N(xi)中随机选一个xj；iff(xj)Pk+1，表示Pk比Pk+1有更大的优先权。目标的优先级是一个定性概念，体现决策者偏好。,53,例3.1中：产量要求为首位目标，赋予优先因子P1；设备台时的利用为次位目标，赋予P2；利润为第三位目标，赋予P3。权系数wj：区别同一优先级、且度量单位相同的不同目标间的差别。是一个可用数量衡量的定量指标。优先因子与权系数由决策者按其偏好确定。综上所述，例3.1的目标规划模型可以写为：minZ=P1d1+P2(d2+d2)+P3d3s.t.2x1+x211x1x2+d1d1=0 x1+2x2+d2d2=108x1+10 x2+d3d3=56x1,x2,di,di0,i=1,2,3,54,例3.2某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩电的销售量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标顺序为：(1)充分利用装配线每周计划开动40小时；(2)允许装配线加班，但加班时间每周尽量不超过10小时；(3)装配电视机的数量尽量满足市场需要，因彩电的利润高，取其权系数为2。试建立求解该问题的目标规划模型。,解设x1,x2分别为彩色和黑白电视机的产量，则该问题的目标规划模型为s.t.x1+x2+d1d1=40 x1+x2+d2d2=50 x1+d3d3=24x2+d4d4=30 x1,x2,di,di0,i=1,4minZ=P1d1+P2d2+P3(2d3+d4),55,目标规划特点：(1)目标函数表示为偏差变量的函数，把多目标的优化要求，统一到一个表达式中，把多目标问题化为单目标问题。(2)由于引进定性化的优先因子Pk和定量化的权系数wj，因此，目标规划的目标函数是一种定性与定量分析相结合的决策公式。(3)决策者通过调整目标的优先级和权系数，便可求出多种不同的备选方案。(4)允许对计量单位不同的目标进行综合评价。(5)目标规划中的约束柔性，给决策方案的选择带来了很大的灵活性。,56,3.求解线性目标规划的单纯形法计算步骤如下：(1)建立初始单纯形表，在表中将检验数行按优先因子个数及优先顺序分别列成K行，置k=1。(2)检查该行中是否存在负检验数，且对应的前k1行的检验数是零。若有取其中最小者对应的变量为换入变量，转(3)。若无负数，则转(5)。(3)按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。(4)按单纯形法进行运算，建立新的计算表，返回(2)。(5)当k=K时，计算结束。表中的解即为满意解。否则置k:=k+1，返回(2)。,57,例3.3试用单纯形法来求解例3.1。解将例3.1的数学模型化为标准型：minZ=P1d1+P2(d2+d2)+P3d3s.t.2x1+x2+xs=11x1x2+d1d1=0 x1+2x2+d2d2=108x1+10 x2+d3d3=56x1,x2,xs,di,di0,i=1,2,3取xs,d1,d2,d3为初始基变量，列初始单纯形表:,58,59,进行基变换运算，得：,60,再进行一次基变换运算，得最终表：,61,3.3化多目标为单目标的其它方法,1.分层系列法基本思想：把目标按重要程度给出一个序列，如f1(x),f2(x),fm(x)，然后就逐个地求最优。设方案变量xR0，则：,该方法有解的前提是R1,R2,Rm-1非空。,62,2.乘除法min3.主要目标法思想：解决主要目标，兼顾其它目标。选中其中一个目标作为主要目标，而对其它目标只满足一定规格要求即可，化成求下述规划问题：R=x|fifi(x)fi,i=2,3,m,xR,63,3.4引进次序法,多目标问题的任何两个解只能是半序的，难以比较优劣引进次序法的思想：另外制订一些规则，使非劣解有可能重排次序决定解的去留，一直到最后找到选好解,64,3.5直接求非劣解法,直接求非劣解法：尽可能先把非劣解都找出来，然后让决策者自己去进一步挑选；或者是决策者和提供非劣解者互相讨论，逐步修正，最后找到一个选好解,65,3.6层次分析法（AHP）,1.问题的提出例3.5设某企业拥有一笔资金，现有三种可能的投资去向：办实业、购买股票和存入银行由于不同去向所冒风险大小不等，资金利润率不一样，资金周转快慢也不同问如何选择投资去向才能得到最佳投资效益？目标层G准则层C方案层P权重w1w2w3,投资效益,风险C1,利润C2,周转C3,存款P3,股票P2,实业P1,66,2.层次分析法的基本原理以特征向量方法为基础的数学原理设有n件物体A1,A2,An；它们的重量分别为w1,w2,wn若将它们两两地比较重量，其比值可构成nn阶矩阵A,若用重量向量右乘矩阵A，得到,67,即AW=nW由正矩阵的有关理论可知，W为矩阵A的特征向量，n为矩阵A的特征值AHP法的基本思路：有一组与某一目标有关的因素，需要知道它们对目标影响程度，就可以把这些因素成对比较，构成比较判断矩阵，通过求解判断矩阵的最大特征值及其对应的特征向量，即可得到这些因素对目标影响的程度权重,68,根据正矩阵理论，可以证明若矩阵A（设aij=wi/wj）具有以下特点：(1)aii=1(i=1,2,.,n)(2)aij=1/aji(i,j=1,2,.,n,ij)(3)aij=aik/ajk(或aikakj)(i,j=1,2,.,n,ij)则该矩阵一定存在唯一的不为零的最大特征值max，且max=n若求解时所构造的完全具备上述三个特性，称矩阵完全满足一致性但在实际问题中，在两两比较时，不可能做到判断的完全一致性而存在估计误差必然导致特征值及特征向量也有偏差，变成,69,为了避免使误差过大，需要检验的一致性可用一致性比例指标CR来检验的一致性，其中，当max=n时，CI=0，为完全一致；RI的值如下：当CR0.1时，认为判断矩阵一致性是可以接受的,70,3.AHP法的基本步骤(1)建立递阶层次结构模型需要达到的目标类；判断好坏的准则类；解决问题的方案措施类(2)构造判断矩阵判断同一层次的元素对上一级某一元素的影响程度，并将其定量化元素aij表示对于元素Cs，Pi比Pj的相对重要程度的标度，即两两比较的比率的赋值,71,19标度法：一个递阶层次结构，可以构建若干个判断矩阵，其数目是图中除最低一层以外的所有各层的元素之和在建立判断矩阵时，通常只遵守aii=1和aij=1/aji两个条件，再按一致性检验方法进行检验,72,(3)层次单排序及其一致性检验层次单排序：把本层所有各元素对相邻上一层元素来说排出一个权重次序，即求判断矩阵的特征向量根据判断矩阵进行层次单排序的方根法：先求判断矩阵中每行元素之积Mi：再求Mi的n次方根，得然后对向量进行归一化，得得到特征向量,73,层次单排序的一致性检验：计算判断矩阵的最大特征根（值）：计算计算若判断矩阵不满足一致性条件（0，按从大到小的顺序排列按S(i,j)的上述顺序，逐个考察其端点i和j，若满足以下条件，就将弧(i,j)插入到线路中，其条件是：点i和点j不在一条线路上，且均与点1相邻（不是线路的内点）返回步骤(4)，直至考察完所有可插入弧(i,j)为止,96,例4.2用节约算法求下述的旅行商问题，其中点1为起（终）点，各点对间的距离由下表给出,97,(1)将各点分别与点1相连，组成7条线路.(2)计算节约值S(i,j)=c1i+c1jcij如S(2,3)=c12+c13c23=8+58=5(3)将算出的S(i,j)按从大到小的顺序排列于下表中(4)按照S(i,j)的大小顺序，考虑连接点i和点j,98,2.最邻近法步骤如下：任取一点作为线路的起点寻找与上一次加进线路中的点距离最近的点，把此点加到线路中去重复(2)，直到所有的点都已考虑，这就得到了一条线路例4.3用最邻近法求解上例,99,14235678,100,k-交换(k-最优，k-opt)，一般取k=2,3,4是用解改进策略构造的算法基本原理是应用局部搜索的概念，通过对k条边(弧)进行交换，在初始解的邻域中对初始解进行调整，每次调整接受得到改进的可行解，直至解在其邻域内不能改进为止最终解就叫做k-最优解(k-opt)3.2-交换(2-opt)算法,u-1,u,u+1,v-1,v,v+1,101,4.3-交换(3-opt)算法,102,4.4启发式方法的特点分析,是寻求解决问题的一种基本原理和策略建立在经验和直观推断的基础上.根据所采用的策略不同，算法一般终止于一个可行解（如逐步构解策略），或者是一个与初始解密切相关的局部最优解（如解改进策略）用启发式方法解决问题时强调“满意”，但不能保证得到最优解常常是得到“满意解”决策者就认为可以了，其原因主要是：有很多问题不存在严格（绝对）最优解有些问题，如NP难问题，要得到最优解需花费过大的代价，不合算从实际需求出发，有时不要求问题的解具有很高的精度,103,经典运筹学中的解析式求解算法，是以数学证明和已知的性质为根据，以演绎推理为基础的；而启发式算法是以归纳推理为基础的好的启发式算法与精确算法相比有下述优点：(1)计算步骤简单，易于实现(2)通常不需要高深和复杂的理论知识(3)常可以减少大量的计算工作量.(4)易于将定量分析与定性分析相结合主要缺点：担心出现所求出的最终解远离最优解能够较好地改善此不足之处的一个有效途径，就是运用将在后续各章中介绍的通用启发式算法（metaheuristics）来构造求解相关问题的算法,104,第5章模拟退火算法,模拟退火算法（SimulatedAnnealing,简称SA）是Kirkpatrick等人于1982年提出的一种适合求解大规模组合优化问题，特别是NP-难问题的通用启发式算法算法思想源于对固体物质退火过程的模拟；采用Metropolis接受准则；并用一组称之为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解SA的物理背景：固体物质退火过程使算法跳离局部最优的关键：Metropolis接受准则算法应用的前提：冷却进度表的合理选择,105,主要内容,5.1固体退火过程和Metropolis准则5.2模拟退火算法的基本思想和步骤5.3模拟退火算法关键参数和操作的设计5.4模拟退火算法实现与应用5.5模拟退火算法的改进,106,5.1固体退火过程和Metropolis准则,固体物质退火是先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程.固体物质的退火过程由三部分组成：加温过程：增强粒子的热运动；系统能量随之增大等温过程：系统达到该温度下能量最小状态，即平衡态冷却过程：使粒子的热运动减弱并逐渐有序化对于固体在恒定温度下达到热平衡的过程模拟，Metropolis等人在1953年提出了“重要性采样法”，即以概率接受新状态若EjEi，要依据概率来确定,107,5.2模拟退火算法的基本思想和步骤,1.固体退火与组合优化之间的相似性固体退火概念与优化问题的对应关系,108,2.算法思想和步骤Metropolis算法：从某一初始状态出发，通过计算系统的时间演化过程，求出系统最终达到的状态SA：从某个初始解出发，经过大量解的变换后，求得给定控制参数值t时优化问题的相对最优解然后，减少t的值，重复执行Metropolis算法，就可以在t趋于零时，求得优化问题的全局最优解SA由与Metropolis准则对应的转移概率Pt确定是否接受从当前解xi到新解xj的转移，即,109,ProcedureSimulated_Annealing;Begin任选一个初始解x0；确定初始温度t0和每一个t值下进行迭代的次数L；xi:=x0;（置初始解为当前解）k:=0;（温度变化计数器置0）Repeatl:=0;（迭代次数计数器）Repeat从邻域N(xi)中随机选一xj；计算f=f(xj)-f(xi)；if(f0)thenxi:=xj;elseifexp(-f/tk)random0,1thenxi:=xj;l:=l+1;untill=L;k:=k+1;tk:=t(k);until满足终止条件；End;,110,3.模拟退火算法的特点分析SA依据Metropolis准则接受新解，因此除接受优化解外，还在一定范围内接受恶化解，这正是SA与局部搜索算法的本质区别所在SA具有如下特点：(1)优于局部搜索算法(2)若在每个t值都达到平衡分布，且所构造的邻域结构能使解空间中的任何两个状态可达，则SA渐近收敛于全局最优解(3)随着控制参数t值的减小，算法返回某个全局最优解的概率单调增大.,111,与局部搜索算法相比，SA的性能可概括为高效、健壮、通用和灵活(1)高效性SA可在较短时间里求得更好的最终解(2)健壮性（鲁棒性，robust）即算法的最终解并不十分依赖初始解的选取(3)通用性和灵活性SA能应用于求解多种组合优化问题，为一个问题编制的程序可以有效地用于其它问题,112,5.3SA关键参数及其操作设计,SA主要包括“三函数两准则”：解产生函数（邻域结构）、解接受函数、温度更新函数、内循环终止准则和外循环终止准则1.解产生函数（邻域结构）通常选择当前解经简单变换即可产生新解的方法尽可能保证产生的候选解遍布整个解空间应能使解空间中的任何两个状态可达2.解接受函数判断新解是否被接受的依据是Metropolis准则：,113,3.初始温度从理论上说，初始温度t0应使平稳分布中每一状态被接受的概率相等，也就是使,若取P0.9，则在f=100时，t0949在实际应用中可用以下方法进行简单地估计：(1)f=(目标函数值的上界)(目标函数值的下界)(2)随机产生若干个解，求所有解对间的目标函数差，然后取其中的最大者作为f,114,4.温度更新函数表示温度下降的方式并控制温度下降的速度常用的温度更新函数是tk+1=tk，01，通常=0.750.995.内循环终止准则用于决定在各温度下产生候选解的数目，即每一个tk值下进行迭代的次数LL往往只能取一个近似的足够大的数，如L=100n300n，其中n为问题的规模还可用如下的抽样稳定准则来判断L是否足够大：(1)目标函数的均值是否稳定(2)连续若干步的目标值变化较小,115,6.外循环终止准则用于决定SA何时结束常用的终止准则有：(1)设定终止温度在实际应用中，可以给定一个足够小的正数，当温度tk时，算法终止(2)给定一个确定的外循环总迭代次数(3)给定当前的最好解保持不变的最大连续迭代次数7.冷却进度表初始温度t0，温度更新函数tk+1=tk，每一个tk值下进行迭代的次数L和外循环终止准则称为模拟退火过程的冷却进度表，是SA应用的关键参数这些参数之间存在相互影响,116,5.4模拟退火算法实现与应用,讨论如何在SA所提供的通用算法框架下，针对具体问题予以实现对问题的简明描述：解空间：指问题的所有可能解的集合，它限定了初始解选取和新解产生时的范围目标函数：通常表述为若干优化目标的一个和式目标函数值不一定就是问题的优化目标值，但其对应关系应是明显的此外，目标函数式应当是易于计算的初始解：可以考虑随机生成,117,1.旅行商问题设有n个城市和距离矩阵D=(dij)，其中dij表示城市i到城市j的距离问题是要找遍访每个城市恰好一次的一条回路，且其路径长度为最短求解TSP的模拟退火算法描述如下：解空间：可表示为1,2,n的所有循环排列的集合，即S=(1,2,n)|(1,2,n)为1,2,n的循环排列i=j表示在第i个次序访问城市j，并约定n+1=1初始解：可选为（1,2,n）目标函数：访问所有城市的一个回路的长度,118,u-1,u,u+1,v-1,v,v+1,新解的产生：设用以下方法产生（分别或交替使用）2-交换任选访问的序号u和v（设uv），逆转u和v及其之间的访问顺序当前解：1u-1uu+1v-1vv+1n新解：1u-1vv-1u+1uv+1n目标函数差（2-交换）,119,当距离矩阵D=（dij）为对称矩阵时，因为dij=dji，上式可简化为,120,3-交换任选序号u、v和w（设uvw），将u和v之间的子路径插到w之后访问当前解:1u-1uvv+1ww+1n新解:1u-1v+1wuvw+1n,u-1,u,v,v+1,w,w+1,目标函数差（-交换）,121,2.01背包问题（Zero-oneKnapsackProblem）给定一个装载量为M的背包及n件物品，物品i的重量和价值分别为wi和ci，i=1,2,n要求选择若干件物品装入背包，使其价值之和为最大设则问题的数学模型为xi0,1,i=1,2,n,122,求解0-1背包问题的模拟退火算法描述如下：解空间S=(x1,x2,xn)|w1x1+wnxnM,xi0,1目标函数f(x1,x2,xn)=c1x1+c2x2+cnxnmax新解的产生随机选取物品i，执行下列三种操作之一：若i不在背包中，则将其装入背包若i不在背包中，则将其装入背包，同时从背包中随机取出另一物品j若i已在背包中，则将其取出，并同时随机装入另一物品j归纳：xi:=1xi，且（或）xj:=1xj，ij,123,背包价值差（目标函数差）及重量差根据产生新解的三种可能，相应的背包价值差为为判定解的可行性，求出对应的背包重量差为其中m为当前背包重量m的增量,124,接受准则：是增加了可行性测定的Metropolis准则,125,5.5模拟退火算法的改进,SA的主要不足:返回一个高质量的最终解要花费较长的时间提高搜索效率是主要的改进内容，可能的途径：(1)选择适当的邻域结构和随机数序列(2)选择合理的冷却进度表(3)SA执行过程是一系列“产生新解、判断、接受/舍弃”的迭代过程，提高各个环节的时效可以缩减运算时间(4)改变算法进程的各种变异方法，如有记忆的SA、回火退火法、加温退火法等(5)大规模并行计算,126,第章禁忌搜索算法,禁忌搜索（TabuSearch,TS）的思想是由Glover于1986年提出的，并逐步形成了一套完整的算法算法思想源于对人类智力过程的一种模拟.所以TS也是一种人工智能算法模拟退火(SA)：模拟固体物质退火过程.禁忌搜索(TS)：模拟人类智力过程.遗传算法(GA)：模拟生物进化过程.与SA、GA等通用启发式算法一样，TS也是对局部搜索算法的一种扩展，是一种全局逐步寻优算法所谓禁忌就是禁止重复前面的工作算法引入一个禁忌表记录下已经搜索过的点，在下一次搜索中，利用禁忌表中的信息不再或有选择地搜索这些点,127,主要内容,6.1禁忌搜索算法示例6.2禁忌搜索算法的基本思想和步骤6.3禁忌搜索算法的关键参数和操作设计,128,6.1禁忌搜索算法示例,以TSP为例说明禁忌搜索的主要思想问题规模n=7邻域结构：定义为“互换(swap)”操作，即随机交换两个城市在当前解中的排列位置，则每个解的邻域解有=n(n-1)/2=7(7-1)/2=21个每次迭代用其中最好的5次变换作为候选解每次变换将导致目标函数节约值（即目标函数差）的变化每个被采纳的变换在禁忌表中将滞留3步（称为禁忌长度）若禁忌对象对应的目标函数节约值优于到目前为止所搜索到的最好解（“best-so-far”），则无视其禁忌属性而仍接受该解(藐视准则aspirationcriterion),129,随机产生初始解：(2,5,7,3,4,6,1)目标函数节约值：0,禁忌表：,候选解：,候选解中(5,4)互换的节约值最大，接受，并更新当前解和禁忌表。,*,(2,4,7,3,5,6,1),6,3,130,当前解：(2,4,7,3,5,6,1)节约值：6,禁忌表：,候选解：,候选解中(3,1)互换的节约值最大，接受，并更新当前解和禁忌表。,*,(2,4,7,1,5,6,3),6+2=8,3,3,2,131,当前解：(2,4,7,1,5,6,3)节约值：8,禁忌表：,候选解：,(2,4)互换为非禁忌最佳候选解，接受，并更新当前解和禁忌表。,*,(4,2,7,1,5,6,3),8-4=4,2,3,1,3,2,132,当前解：(4,2,7,1,5,6,3)节约值：4,禁忌表：,候选解：,(4,5)互换是禁忌对象，但因它使总节约值优于到目前为止搜索到的最好解，按藐视准则，接受为新当前解。,*,(5,2,7,1,4,6,3),4+6=10,1,2,3,3,2,1,133,当前解：(5,2,7,1,4,6,3)节约值：10,禁忌表：,候选解：,重复上述步骤，直到算法终止条件成立为止。,*,(5,2,1,7,4,6,3),10+0=10,3,1,2,134,135,归纳起来TS有如下主要特征：(1)邻域结构的设计很关键，它决定了当前解的邻域解的产生形式和数目(2)候选解集仅取其中的少量最佳状态组成(3)禁忌长度直接影响整个算法的搜索进程和行为(4)藐视准则的设置是算法避免遗失优良状态(5)对于非禁忌的候选解，算法无视它与当前解的目标函数值的优劣关系（即可能比当前解差），仅考虑从中取出最佳的一个作为下一步的当前解，以此来实现跳出局部最优（是一种确定性策略）(6)新解不是在当前解的邻域中随机产生，而是非禁忌的最佳候选解，或者是优于“最好解”的候选解(7)必须设置一个合理的终止准则,136,6.2TS的基本思想和步骤,算法的基本思想：给定一个当前解（初始解）和候选解产生函数（邻域结构），然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于到目前为止搜索到的“最好解”（best-so-far），则忽视其禁忌特性，用其替代当前解和“最好解”；若不存在上述候选解，则在候选解集中选择非禁忌的最佳候选解为新的当前解，而无视它与当前解的优劣；两种情况下都将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直到满足停止准则,137,禁忌搜索算法主要步骤流程图,由当前解产生候选解集,将该解作为新的当前解和到目前为止的最好解,有满足藐视准则的候选解否？,算法终止准则满足否？,输出结果,更新禁忌表中各对象的任期,给定算法参数,产生初始解,置禁忌表为空,N,Y,N,Y,选择非禁忌的最佳候选解为新的当前解,138,6.3TS的关键参数和操作设计,1.初始解可以随机产生，也可以借助一些经典启发式方法产生以保证一定的初始解性能2.邻域结构即候选解产生函数，用于从当前解的邻域中产生一个新解对算法搜索质量和效率有重要影响通常选择当前解经过简单地变换即可产生新解的方法如上例中的“互换(swap)”操作为了使算法渐近收敛于全局最优解，所构造的邻域结构应能使解空间中的任何两个状态通过有限步邻域搜索后互达,139,3.候选解的选择候选解数量的确定：确定性或随机性地在当前解的邻域解集中选取一个子集作为候选解集，其大小一般为50500个最佳候选解的选取：选择候选解集中满足藐视准则或非禁忌的最佳候选解4.解评价函数用于对搜索到的候选解进行评价方法：直接用目标函数作为解评价函数；用反映问题目标的某些特征值来作为解评价函数，但要保证特征值的最佳性与目标函数的最优性一致如上例中用“节约值”,140,5.禁忌对象被置入禁忌表中的那些变化元素禁忌的目的是为了尽量避免迂回搜索(1)以整个解的变化为禁忌对象当解状态由x变化到解状态y时，将解y（或xy的变化）视为禁忌对象(2)以解分量的变化为禁忌对象如示例中的情形(3)以目标值的变化作为禁忌对象6.禁忌表和禁忌长度禁忌表（tabulist）是针对禁忌对象所设计的一种结构，可以是一维或二维的禁忌长度t（tabulength）是禁忌对象的禁忌期，即不允许再次被选取的迭代次数每迭代一步，t减少1，当t=0时解禁,141,禁忌长度t的选取：(1)t是一个固定的数如t=7，或者固定为与问题规模相关的一个量，如t=，或t=/2(2)t是动态变化的即设定禁忌长度的变化区间tmin,tmax，如5,10等7.藐视准则若某个禁忌候选解的目标值优于到目前为止搜索到的“最好解”（bestsofar），则解禁此候选解为当前解和新的“最好解”若候选解均被禁忌，且不存在优于“最好解”的候选解，则对候选解中的最佳者进行解禁，以便搜索过程继续进行下去,142,8.终止条件(1)给定最大迭代步数，如N=10000优点是易于操作和控制计算时间，但无法保证解的质量(2)给定当前的最好解保持不变的最大连续迭代次数如2500次(3)设定目标值的偏离幅度若ZLB为问题的下界，为给定的偏离幅度，则当f(x)ZLB时，终止计算(4)设定禁忌对象的最大禁忌频率若某个禁忌对象的禁忌频率超过给定的值，则终止计算,143,TS求解过程演示（示例1，示例2）参考文献1符卓.带装载能力约束的开放式车辆路径问题及其禁忌搜索算法研究.系统工程理论与实践,2004,24(3):123-1282ZFu(符卓),REgleseandLYOLi.Anewtabusearchheuristicfortheopenvehicleroutingproblem.JournaloftheOperationalResearchSociety,2005,56(3):267-274.,144,145,146,第7章遗传算法,生物进化表现为“适者生存，不适者被淘汰”一类新型的全局优化技术仿生类算法：遗传算法(GeneticAlgorithms,GA)仿生过程算法：演化策略进化程序仿生结构算法：人工神经网络蚁群优化算法仿生行为算法：粒子群算法模拟植物生长算法,147,主要内容,7.1生物进化和遗传学基本知识概述7.2遗传算法描述7.3遗传算法的关键参数和操作设计,148,7.1生物进化和遗传学基本知识概述,1.达尔文自然选择学说自然选择学说主要包括以下三个方面：(1)遗传父代通过繁殖把生物信息传给子代，子代按照所得信息而发育、分化(2)变异随机发生，变异的选择和积累是生命多样性的根源(3)生存斗争和适者生存繁殖是现存物种得以生存、延续的必要条件；变异是生物进化的根本保证；在竞争的环境下，自然界不可避免地会对生物的生存进行选择,149,物种被后代所继承的就是那些更能适应环境的个体特征生物进化：是遗传与变异相互作用的结果遗传的主要物质是细胞核中染色体上的基因基因结构：基因位置的排列基因结构的性质及其与物种的关系：,通过优胜劣汰的自然选择，适应值高的基因结构就被保存下来,150,2.现代综合进化论用统计生物学和种群遗传学的成就重新解释达尔文的自然选择理论种群遗传学：研究种群中基因的组成及其变化种群：在一定地域中，一个物种的全体成员构成一个种群生物的进化实际上是种群的进化，个体总是要消亡，但种群则可以继续保留每一代中个体基因结构的改变会影响种群基因库的组成，而种群基因库组成的变化就是这个种群的进化通过个体繁殖机会的差异，也能造成后代遗传组成的改变，自然选择也能够进行,151,生物进化的基本过程：,种群,被淘汰的子种群,获繁殖机会的子种群,子代种群,选择,变异,婚配,(新一代),152,归纳：生物的进化表现为“适者生存，不适者被淘汰”最适合自然环境的种群往往产生了更大的后代种群生物进化是遗传和变异相互作用的结果遗传是通过父代对子代的基因传递来实现；某些遗传信息的改变决定了生物的变异3.基本概念和术语染色体(chromosome)：是遗传物质的主要载体，由多个基因(遗传因子)组成DNA(脱氧核糖核酸)：构成染色体的主要物质基因(gene)：染色体上具有遗传效应的DNA片段.,153,基因型（genotype）：基因组合的模型，染色体的内部表现，它决定了个体的外部表现表现型（phenotype）：由染色体决定的个体的外部表现，即根据