组合优化问题与现代优化算法

组合优化问题与仿生优化算法数学建模培训YOURSITEHERE组合最优化（combinatorialoptimization)是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型描述为：•“组合优化问题”存在于生活中的方方面面-田忌赛马，投资组合“组合优化”是通过“优化某种顺序排列方式”实现的何谓组合优化问题？Dxxgtsxf0)(..)(minYOURSITEHERE0-1背包问题设有一个容积为b的背包，n个体积分别为ai(i=1,2,…,n),价值分别为ci(i=1,2,…,n)的物品，如何以最大的价值装包？nixbxatsxciniiiniii,,1},1,0{..max11经典的组合优化问题——背包问题YOURSITEHERE•旅行商问题一个推销员欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得推销员每个城市正好走一遍后回到起点且所走路径最短。经典的组合优化问题——旅行商问题ABCDEFYOURSITEHERE一个经典的组合优化问题——旅行商问题.,,,1,},1,0{},,2,1{,2||2,1||,,1,1,,1,1..min,11jinjixnSnSSxnjxnixtsxdijSjiijniijnjijnjiijij数学模型YOURSITEHERE•旅行商问题的应用领域•旅行商问题要从图G的所有旅行路线中求取最小成本的旅行路线，而从初始点出发最终回到初始点的周游路线一共有n!条，即等于除初始结点外的n个结点的排列数，因此旅行商问题是一个排列问题。•可用于：-指导交通规划，以减轻交通拥堵；-指导物流节点的布局规划，物流路径的合理选择，以减少物流成本；-指导互联网环境中节点的设置，以更好地让信息流动。一个经典的组合优化问题——旅行商问题YOURSITEHERE从n!条周游路线中找出一条具有最小成本的旅行路线，如果用枚举的方法寻找，就是把每一个旅程的成本都计算一次，再比较大小，显然需要计算n!次；当n不断的变大，问题的求解会呈现出一种组合爆炸的状态。所以，寻求有效的算法是解决组合问题的关键。旅行商问题的解YOURSITEHERE•勤劳的小蜜蜂•英国伦敦大学皇家霍洛韦学院等机构的研究人员报告：在花丛中飞来飞去的小蜜蜂显示出了轻而易举破解旅行商问题的能力。人们利用人工控制的假花进行了实验，结果显示，不管怎样改变花的位置，蜜蜂在稍加探索后，很快就可以找到在不同花朵间飞行的最短路径。•蚂蚁觅食•单只蚂蚁的能力和智能非常简单，但它们通过相互协调、分工、合作完成筑巢、觅食、迁徙等复杂行为，比如蚂蚁在觅食过程中能够通过相互协作找到食物源和巢穴之间的最短路径。•其它的动物如蟑螂，鱼，细菌，鸟等都能够利用群智能，采取合理的行动进行觅食，人们仿照这些动物的觅食行为构造了相应的仿生算法。•仿生优化算法——群智能算法YOURSITEHERE仿生优化算法——粒子群算法粒子群优化算法(PSO)是一种集群智能方法的演化计算技术,PSO的基本概念源于对鸟群捕食行为的研究.1995被Kennedy和Eberhart于1995年提出。PSO算法的思想是跟踪最好点，并逐步向最好点靠近。粒子（潜在的解）在解空间跟踪最优的粒子进行搜索。YOURSITEHERE每个寻优的问题解都被想象成一只鸟，我们也称为“Particle”。所有的Particle都有一个fitnessfunction以判断目前的位置之好坏。每一个Particle必须赋予记忆性，能记得所搜寻到最佳位置。每一个Particle还有一个速度以决定飞行的距离与方向。仿生优化算法——粒子群算法YOURSITEHERE仿生优化算法——粒子群算法第i个粒子的“飞翔”速度也是一个D维的向量，记为12(,,,)iiiiDxxxx假设在一个D维的目标搜索空间中，有m个粒子组成一个群落，其中第i个粒子表示为一个D维的向量i=1,2,…m.每个粒子的位置就是一个潜在的解。将其带入一个目标函数就可以计算出其适应值，根据适应值的大小衡量其优劣。12(,,,)iiiiDvvvv记第i个粒子迄今为止搜索到的最优位置为12(,,,)iiiiDpppp12(,,,)ggggDpppp记整个粒子群迄今为止搜索到的最优位置为YOURSITEHERE仿生优化算法——粒子群算法基本思路：•初始化一群随机粒子（随机解）•每次迭代中，粒子通过跟踪两个极值更新自己：——粒子本身找到的历史最好解（个体极值点pbest）——整个种群目前找到的最好解（全局极值点gbest）•需要计算粒子的适应值（目标函数值），以判断粒子位置距最优点的距离。•每次迭代中，根据适应值更新pbest和gbest。•迭代终止条件：设置最大迭代次数或全局最优位置满足预定最小适应阈值。YOURSITEHERE仿生优化算法——粒子群算法每个粒子如何迭代？12(1)()()(-())()(-())(1)()()ididididgdididididvkvkcrandpxkcrandpxkxkxkvkc1,c2—学习因子，经验值取c1=c2=2，调节学习最大步长rand（）—随机数，取值范围（0，1），以增加搜索随机性YOURSITEHERE仿生优化算法——粒子群算法开始初始化粒子群计算每个粒子的适应度根据适应度更新pbest、gbest，更新粒子位置速度结束noyes达到最大迭代次数或全局最优位置满足最小界限？基本粒子群优化算法流程图YOURSITEHERE仿生优化算法——粒子群算法分布式搜寻具记忆性组件较少，容易实现适合在连续性的范围内搜寻YOURSITEHERE粒子群优化算法求解最优化问题Schwefel'sfunctionn:1=i420.9687,=418.9829;=)(minimumglobal500500where)sin()()(1iiniiixnxfxxxxfYOURSITEHERE初始化粒子群位置粒子群优化算法求解最优化问题YOURSITEHERE粒子群优化算法求解最优化问题迭代5次后粒子群位置YOURSITEHERE迭代10次后粒子群位置粒子群优化算法求解最优化问题YOURSITEHERE迭代20次后粒子群位置粒子群优化算法求解最优化问题YOURSITEHERE迭代100次后粒子群位置粒子群优化算法求解最优化问题YOURSITEHERE迭代500次后粒子群位置粒子群优化算法求解最优化问题YOURSITEHERE粒子群优化算法求解车辆路径问题车辆路径问题车辆路径问题可以描述为：有一个中心仓库，拥有k辆车，车场向L个客户送货，第i个客户货运量为gi（i=1,2,……,L）,中心与客户、客户与客户两两间的广义运输费用为cij，车场编号为0，客户编号为i=1，2，……，L，送货卡车装载容量为qk（qkgi,i=0,1,……,L），车辆不允许超载。要求指派运输车辆，并确定每辆车的运输路线，使得总运输费用z最低。YOURSITEHEREmin..11,,0,1,,1,2,,0,1,,01,0,1,,1,2,,010,1,,1,2,,ijijkijkikikikikijkkjiijkijijkkizcxstgyqyiLxyjLkKxyiLxijLkKyiLkK　　　　　　　；　；或　；或　；1,0,kiikyik点的任务由车辆完成点的任务不由车辆完成1,0,ijkkijx车辆从点行驶到否则，粒子群优化算法求解车辆路径问题YOURSITEHERE各发货点坐标及货运量序号01234567坐标(18,54)(22,60)(58,69)(71,71)(83,46)(91,38)(24,42)(18,40)货运量(gi)0.890.140.280.330.210.410.57注：序号0表示中心仓库，设车辆容量皆为q=1.0，由3辆车完成所有任务。(最优路径距离为217.81)粒子群优化算法求解车辆路径问题