组合优化问题与现代优化算法教材课程.ppt

组合优化问题与仿生优化算法; 组合最优化（combinatorial optimization)是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型描述为： “组合优化问题”存在于生活中的方方面面 田忌赛马，投资组合 “组合优化”是通过“优化某种顺序排列方式”实现的 ; 0-1背包问题 设有一个容积为b的背包，n个体积分别为ai (i=1,2,…,n), 价值分别为ci (i=1,2,…,n)的物品，如何以最大的价值装包？ ;旅行商问题 一个推销员欲到n个城市推销商品，每两个城市 i和j之间的距离为dij，如何选择一条道路使得 推销员每个城市正好走一遍后回到起点且所走 路径最短。 ; ;旅行商问题的应用领域 旅行商问题要从图G的所有旅行路线中求取最小成本的旅行路线，而从初始点出发最终回到初始点的周游路线一共有n!条，即等于除初始结点外的n个结点的排列数，因此旅行商问题是一个排列问题。 可用于： 指导交通规划，以减轻交通拥堵 ； 指导物流节点的布局规划，物流路径的合理选择，以减少物流成本； 指导互联网环境中节点的设置，以更好地让信息流动。 ;从 n!条周游路线中找出一条具有最小成本的旅行路线， 如果用枚举的方法寻找，就是把每一个旅程的成本都计算 一次，再比较大小，显然需要计算n!次；当n不断的变大， 问题的求解会呈现出一种组合爆炸的状态。 所以，寻求有效的算法是解决组合问题的关键。 ;勤劳的小蜜蜂 英国伦敦大学皇家霍洛韦学院等机构的研究人员报告：在花丛中飞来飞去的小蜜蜂显示出了轻而易举破解旅行商问题的能力。人们利用人工控制的假花进行了实验，结果显示，不管怎样改变花的位置，蜜蜂在稍加探索后，很快就可以找到在不同花朵间飞行的最短路径。 蚂蚁觅食 单只蚂蚁的能力和智能非常简单，但它们通过相互协调、分工、合作完成筑巢、觅食、迁徙等复杂行为，比如蚂蚁在觅食过程中能够通过相互协作找到食物源和巢穴之间的最短路径。 其它的动物如蟑螂，鱼，细菌，鸟等都能够利用群智能，采取合理的行动进行觅食，人们仿照这些动物的觅食行为构造了相应的仿生算法。 ;每个寻优的问题解都被想象成一只鸟，我们也称为“Particle”。 所有的Particle 都有一个fitness function 以判断目前的位置之好坏。 每一个Particle必须赋予记忆性，能记得所搜寻到最佳位置。 每一个Particle 还有一个速度以决定飞行的距离与方向。;仿生优化算法——粒子群算法;仿生优化算法——粒子群算法;仿生优化算法——粒子群算法;仿生优化算法——粒子群算法;仿生优化算法——粒子群算法;粒子群优化算法求解最优化问题;初始化粒子群位置;粒子群优化算法求解最优化问题;迭代10次后粒子群位置;迭代20次后粒子群位置;迭代100次后粒子群位置;迭代500次后粒子群位置;粒子群优化算法求解车辆路径问题;; 各发货点坐标及货运量