分支定价框架下的智能计算-ECOLE

2018.05.19分支定价框架下的智能计算柯良军西安交通大学CONTENTS1234智能计算的发展分支定价算法原理复杂组合优化问题的挑战分支定价框架下的智能计算应用及实验分析5总结61智能计算的发展1智能计算通过模拟自然中的智慧现象或过程发展而来的。其迭代过程是一个学习过程，主要由知识发现和知识运用两个过程组成。智能计算的发展蚂蚁的觅食行为鸽群飞行生物进化1智能计算的发展1.1952年HookeandJeeves提出了PatternSearch2.1960年LawrenceJ.Fogel提出了EvolutionaryProgramming3.1975年J.Holland提出了GeneticAlgorithm4.1977年Glover提出了ScatterSearch1.1983年S.Kirkpatrick,C.D.Gelatt和M.P.Vecchi提出了SimulateAnneal2.1986年Glover提出了TabuSearch3.1992年MarcoDorigo提出了Antcolonyoptimization4.1995年Storn等人提出了DifferentialEvolution之前-1940年1940年-1980年1980年-2000年2000年-今启发式思维随着人类的进化不断增强，但在此期间从来没有相关的理论框架提出。前理论时期早期以方法为中心时期以框架为中心时期1.2001年Z.W.Geem提出了HarmonySearch2.2008年Krishnanand提出了FireflyAlgorithm3.2010年Yang提出了BatAlgorithm4.2012年Gandomi和Alavi提出了krillherdAlgorithm(磷虾群算法)lSörensenK,SevauxM,GloverF.Ahistoryofmetaheuristics[J].Handbookofheuristics,2018:1-18.1智能计算特点智能计算的发展ü自适应性强对待求解的优化问题没有过多的要求；在迭代过程中，一般只用到目标函数值等信息。ü优良的全局寻优能力算法具有很好的鲁棒性，对初始条件不敏感，具有很强的容差能力。ü易于实现智能计算方法原理简单，几乎没有数学推导。传统数学规划算法特点ü单点ü迭代ü解质量每一代都有改进ü严密的数学理论基础1思考：智能计算的发展ü数学化üExplorationvsExploitation2复杂组合优化问题的挑战什么是组合优化2复杂组合优化问题的挑战定义：拥有有限个或可数无限个解的离散集合Ø假设是一个求极小的问题，目标函数为Ø是解空间,是可行解空间（可行区域）Ø所谓组合优化，是指在离散的、有限的数学结构上,寻找一个(或一组)满足给定约束条件并使其目标函数值达到最小的解。min()..,,:fxstxSSXSX()fxXS组合优化问题的特点2复杂组合优化问题的挑战拥有有限个或可数无限个解的离散集合Ø是有限集合，从理论上来讲，只要遍历所有的组合，就能找到最优解。（随着问题规模的增大，中解的个数会急剧增大，难以遍历所有的解）Ø一般来说，组合优化问题通常是有大量的局部极值点，且不可微的、不连续的、多维的、多约束、高度。SS组合优化相关的研究课题2复杂组合优化问题的挑战•一些社会现象、活动等实际问题如何建模为组合优化问题？•组合优化问题的快速求解方法？•组合优化问题具有哪些结构信息？•为了快速求解，什么样的结构信息是有用的？典型组合优化模型2复杂组合优化问题的挑战Ø覆盖问题(set-coveringproblem)Ø装箱问题(bin-packingproblem)Ø背包问题(knapsackproblem)Ø指派问题(assignmentproblem)Ø旅行商问题(travelingsalesmanproblem)Ø图优化问题(graphoptimizationproblem)Ø调度问题(schedulingproblem)组合优化的实际应用2复杂组合优化问题的挑战图着色问题给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色，是否有一种着色法使G中任意相邻的2个顶点着不同颜色。可用4种颜色上色使得任意美国相邻两州颜色不同PCB布线问题2复杂组合优化问题的挑战PCB单层布线路径长度问题的数学模型：单层板布线可以等效于多个等电位线网的集合体，每个线网的布线就是路径寻优问题，是一个组合优化问题。无人机任务规划问题2复杂组合优化问题的挑战无人机巡检任务可以归纳为旅行商问题，因而其约束条件服从旅行商问题的数学模型。旅行商问题可以简单描述为求取一条连接平面内给定m个点的闭合的最短路径，同时保证这条路径只经过每个点一次。数学模型：车辆路径问题2复杂组合优化问题的挑战模型1：TOP（TeamOrienteeringProblem）团队定向问题是经典VRP问题的重要推广。它利用一组车辆来服务一些具有一定收益的顾客。其优化目标是使车辆获得的总收益最大化。课题组考虑带时间窗约束、不确定信息的TOP问题（见文献[1,2,3]）。模型2：CCVRP（cumulativecapacitatedVRP），该问题最小化顾客的等待时间（见文献[4]）。1.LiangjunKe,Paretomimicalgorithm:anapproachtotheteamorienteeringproblem.Omega,2015.2.LiangjunKe,Proportionbasedrobustoptimizationandteamorienteeringproblemwithintervaldata.EuropeanJournalofOperationalResearch.2013,226(1):19-31.3.LiangjunKe,etal.,Cooperatingbranch-and-priceandmetaheuristicfortheteamorienteeringproblemwithtimewindows,IEEECEC2014,Beijing.4.LiangjunKe.Atwo-phasemetaheuristicforthecumulativecapacitatedvehicleroutingproblem.Computers&OperationsResearch.2013,40(2):633-638.基于计算复杂度分类2复杂组合优化问题的挑战多项式时间（Polynomialtime）：在计算复杂度理论中，指的是一个问题的计算时间m(n)不大于问题大小n的多项式倍数。图1NPNPCNphard关系的图形表示说明：1.P问题属于NP问题，NPC问题属于NP问题。2.NPC问题同时属于NPhard问题，是NP与Nphard的交集。求解方法分类2复杂组合优化问题的挑战l精确的求解方法Ø穷举Ø分支定界Ø动态规划l近似求解方法，可以进一步划分为：Ø以确保解的精度为目标的方法,Ø以尽可能获得满意解为目标的方法思考：Ø复杂性的原因Ø如何设计高效的智能计算方法2复杂组合优化问题的挑战Ø分解---分而治之解空间的分解典型代表：分支定界Ø约束处理技术3分支定价算法原理3分支定价算法原理分支定价l分支定价的主要思路Ø分支定价采用分支定界算法来构建和维护搜索树Ø在搜索树的每个节点上，它把整数规划松弛为一个LP（线性规划问题），采用列生成法求解该松弛问题，并依据得到的最优解进行分支和定界。3分支定价算法原理分支定界l分支定界法的主要思路Ø通常，把全部可行解空间反复地分割为越来越小的子集，称为分支；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称为定界。在每次分支后，凡是界限超出已知可行解集目标值的那些子集不再进一步分支，这样，许多子集可不予考虑，这称剪支。l分支定界的三要素：Ø分支Ø剪支Ø定界3分支定价算法原理列生成---基本概念Ø列：主问题的变量；子问题的极点。Ø主（原）问题：当由全部列构成的模型时，我们把此模型称之为原问题。Ø限制主问题（RMP）：当只有部分列构成的模型时，我们把此模型称之为限制主问题（RMP）。Ø子问题（sub-problem）：我们把寻找求解可行的一列m称为求解子问题（sub-problem）。GuyDesaulniers,JacquesDesrosiers,MariusM.Solomon.COLUMNGENERATION（GERAD25thanniversaryseries）[M].Publisher:Springer,2005.pp.1-15.3分支定价算法原理列生成3分支定价算法原理列生成RestrictedMasterProblemColumnGeneration(Sub-problems)ColumnsOptimalDualVariablesRLMP，用商用优化软件CPLEX来求解。3分支定价算法原理分支定价算法流程分支定价算法流程图4分支定价框架下的智能计算4分支定价框架下的智能计算研究动机Ø分支定价法=分支定界法+列生成以分支定界法为框架，在搜索树的每个节点上使用列生成来确定相应问题的上界或下界。在精确算法中，一般采用动态规划等来求解列生成子问题。优点：理论上可以求解出问题的最优解。缺点：运行时间长，难以在合理的时间内找到满意解，一般只能求解中小规模问题。Ø智能计算可以快速地求得许多复杂优化问题满意解优点：能够快速地找到比较满意的解。缺点：理论基础薄弱。4研究动机分支定价框架下的智能计算4算法主要流程分支定价框架下的智能计算5应用及实验分析5问题描述团队定向问题中的应用团队定向问题一般定义为：利用一组车辆来服务一些具有一定收益的点（顾客）。每辆车必须在规定的时间内从起点出发，尽可能多地访问点，最终回到终点。一旦某条路径经过某点，它将获得该点对应的收益，其他路径再次经过该点则不能获得对应的收益。团队定向问题的优化目标是使车辆获得的总收益最大化。TimeLimit5带时间窗团队定向问题整数规划数学模型团队定向问题中的应用引入决策变量：ijkikxy、11maxmniikkipy011111..mnmniknjkkikjstxxm2(1,...,;1,...,)ijkjikjkjijixxyjnkm11(1,...,)mikkyinmax01()(1,...,)niikijijkijTycxTkm(1,...,;1,...,)iikiOsCinkm{0,1}(01;1,...,)ijkxijnkm011,{0,1}(,1,...,;1,...,)knkikyyyijnkm（8）（7）（6）（5）（4）（3）（2）（1）目标函数（1）最大化获得的总收益。约束（2）规定路径从起点0出发回到终点n+1。约束（5）、（6）表示时间约束。约束（4）规定除起点和终点外其余点最多只能经过一次。约束（3）保证路径的连通性。约束（7）、（8）规定决策变量为整数5团队定向问题中的应用带时间窗团队定向问题的列生成模型1(\{01})irrraxiVnmaxrrrpx..strrxm{0,1}()rxr（4）（3）（2）（1）将约束（4）松弛到[0,1]，则得到限制主问题的线性松弛问题RLMP。01()rxr（5）令表示与约束（2）对应的对偶变量i令表示与约束（3）对应的对偶变量05团队定向问题中的应用子问题01maxnrririippa..stmax0()()niirijijrijiTacxTr(i1,...,;)iiriOsCnr{0,1}(01;)ijrxijnr011,{0,1}(,1,...,;)rnriraaaijnr：路径的约减收益（ReducedCost）rp根据对偶原理可得：5团队定向问题中的应用子问题求解列生成子问题：怎样来寻找