少物流成本； - 指导互联网环境中节点的设置，以更好地让信息流动。
YOUR SITE HERE
旅行商问题的解
从 n!条周游路线中找出一条具有最小成本的旅行路线， 如果用枚举的方法寻找，就是把每一个旅程的成本都计算 一次，再比较大小，显然需要计算n!次；当n不断的变大， 问题的求解会呈现出一种组合爆炸的状态。 所以，寻求有效的算法是解决组合问题的关键。
——粒子本身找到的历史最好解（个体极值点pbest） ——整个种群目前找到的最好解（全局极值点gbest） • 需要计算粒子的适应值（目标函数值），以判断粒子位 置距最优点的距离。 • 每次迭代中，根据适应值更新pbest和gbest。 • 迭代终止条件：设置最大迭代次数或全局最优位置满足 预定最小适应阈值。
C A
F E
B
D
YOUR SITE HERE
一个经典的组合优化问题——旅行商问题
数学模型
n
min dij xij
i j
n
s.t. xij 1, i 1,, n
j 1
n
xij 1, j 1,, n
i 1
xij | S | 1, 2 | S | n 2,
YOUR SITE HERE
仿生优化算法——粒子群算法
假设在一个D维的目标搜索空间中，有m个粒子组成一个
群落，其中第i个粒子表示为一个D维的向量 xi (xi1, xi2, , xiD)
i=1,2,…m.每个粒子的位置就是一个潜在的解。将其带入一 个目标函数就可以计算出其适应值，根据适应值的大小衡 量其优劣。 第i个粒子的“飞翔”速度也是一个D维的向量，记为
i, jS
xij {0,1}, i, j 1,, n, i j.
S {1,2,, n}
YOUR SITE HERE
一个经典的组合优化问题——旅行商问题
• 旅行商问题的应用领域 • 旅行商问题要从图G的所有旅行路线中求取最小成本的旅
行路线，而从初始点出发最终回到初始点的周游路线一共 有n!条，即等于除初始结点外的n个结点的排列数，因此 旅行商问题是一个排列问题。 • 可用于： - 指导交通规划，以减轻交通拥堵 ； - 指导物流节点的布局规划，物流路径的合理选择，以减
• 蚂蚁觅食
• 单只蚂蚁的能力和智能非常简单，但它们通过相互协调、 分工、合作完成筑巢、觅食、迁徙等复杂行为，比如蚂蚁 在觅食过程中能够通过相互协作找到食物源和巢穴之间的 最短路径。
• 其它的动物如蟑螂，鱼，细菌，鸟等都能够利用群智能， 采取合理的行动进行觅食，人们仿照这些动物的觅食行为 构造了相应的仿生算法。
YOUR SITE HERE
•仿生优化算法——群智能算法
• 勤劳的小蜜蜂
• 英国伦敦大学皇家霍洛韦学院等机构的研究人员报告：在 花丛中飞来飞去的小蜜蜂显示出了轻而易举破解旅行商问 题的能力。人们利用人工控制的假花进行了实验，结果显 示，不管怎样改变花的位置，蜜蜂在稍加探索后，很快就 可以找到在不同花朵间飞行的最短路径。
YOUR SITE HERE
仿生优化算法——粒子群算法
每个寻优的问题解都被想象成一只鸟，我们也称 为“Particle”。
所有的Particle 都有一个fitness function 以判断 目前的位置之好坏。
每一个Particle必须赋予记忆性，能记得所搜寻到 最佳位置。
每一个Particle 还有一个速度以决定飞行的距离 与方向。
YOUR SITE HERE
仿生优化算法——粒子群算法
YOUR SITE HERE
仿生优化算法——粒子群算法
粒子群优化算法( PSO) 是一种集群智能方 法的演化计算技术, PSO的基本概念源于对鸟群捕 食行为的研究. 1995 被Kennedy和Eberhart于 1995年提出。PSO算法的思想是跟踪最好点，并 逐步向最好点 靠近。粒子（潜在的解）在解空间 跟踪最优的粒子进行搜索。
vi (vi1, vi2, , viD )
记第i个粒子迄今为止搜索到的最优位置为
pi ( pi1, pi2, , piD)
记整个粒子群迄今为止搜索到的最优位置为
pg ( pg1, pg2, , pgD )
YOUR SITE HERE
仿生优化算法——粒子群算法
基本思路： • 初始化一群随机粒子（随机解） • 每次迭代中，粒子通过跟踪两个极值更新自己：
xD
• “组合优化问题”存在于生活中的方方面面 - 田忌赛马，投资组合 “组合优化”是通过“优化某种顺序排列方式”实现的
YOUR SITE HERE
经典的组合优化问题——背包问题
0-1背包问题
设有一个容积为b的背包，n个体积分别为ai (i=1,2,…,n), 价值分别为ci (i=1,2,…,n)的物品，如何以最大的价值装包？
YOUR SITE HERE
仿生优化算法——粒子群算法
每个粒子如何迭代？
vid (k 1) vid (k) c1 rand () ( pid - xid (k)) c2 rand () ( pgd - xid (k)) xid (k 1) xid (k) vid (k) c1,c2—学习因子，经验值取c1=c2=2，调节学习最大步长 rand（）—随机数，取值范围（0，1），以增加搜索随机性
组合优化问题与仿生优化算法
数学建模培训
何谓组合优化问题？
组合最优化（combinatorial optimization)是通过对 数学方法的研究去寻找离散事件的最优编排、分组、次 序或筛选等。所研究的问题涉及信息技术、经济管理、 工业工程、交通运输、通信网络等领域。该问题可用数 学模型描述为：
min f (x) s.t. g(x) 0
n
max ci xi
i 1
n
s.t. ai xi b
i 1
xi {0,1},
i 1,, n
YOUR SITE HERE
经典的组合推销商品，每两个城市 i和j之间的距离为dij，如何选择一条道路使得 推销员每个城市正好走一遍后回到起点且所走 路径最短。