启发式算法
邻域概念
TSP问题解的另一种表示法为
D={S=(i1,i2,…,in)是1,2,…,n的一个排列} 可以定义它的邻域映射为2-opt，即S中的两个 元素对换。
如4个城市的TSP问题，当S=(1,2,3,4)时， N(S)={(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3, 2,4),(1,4,3,2),(1,2,4,3)}.
i 1
xi {0,1},
i 1,, n
一些例子
2. 旅行商问题(TSP，traveling salesman problem)
一个商人欲到n个城市推销商品，每两个城市i和j之
间的距离为dij，如何选择一条道路使得商人每个城市正 好走一遍后回到起点且所走路径最短。
n
min dij xij
i j
n
组合优化问题及算法
引言
组合最优化（combinatorial optimization)是通过 对数学方法的研究去寻找离散事件的最优编排、分组、次 序或筛选等，是运筹学(operations research)中的一个 重要分支。所研究的问题涉及信息技术、经济管理、工业 工程、交通运输、通信网络等领域。该问题可用数学模型 描述为：
邻域的构造依赖于问题决策变量的表示，邻 域的结构在现代化优化算法中起重要作用。
启发式算法
邻域概念
例如，前面例子2给出的TSP问题模型。由解空间 D={x{0,1}n(n-1)}，可以定义它的一种邻域为：
N (x) {y |yx| |yijxij|k, y D }
i,j
k为一个正整数。 TSP问题解的另一种表示法为 D={S=(i1,i2,…,in)是1,2,…,n的一个排列}
n个加工量为{di|i=1,2,…,n}的产品在一台机器上加工， 机器在第t个时段的工作能力为ct,求完成所有产品加工所需时
段数最少的m调in度T方案
T
s.t. xit 1, i 1,,n
t1 n
di xit ct , t 1,2,T
i1
xit {0,1}, i 1,,n, t 1,2,,T
其中xit,T为决策变量,xit=1表示产品i在第t时段加工
一些例子
7. 最大截问题(MCP,Max Cut Problem) 8. 图的顶点着色问题（GCP,Graph Colouring Problem) 9. 独立集问题（ISP,Independent Set Problem) 10.调度问题(SCP,Scheduling Problem) 11.划分问题(PAP,Partition Problem) 12.布局问题（PLP, Placement Problem)……
启发式算法
近似算法定义
记问题A的任何一个实例I的最优解和启发式 算法H解的目标值分别为zopt(I)和zH(I),若对某 个正数0，有
|zH(I)-zopt(I)| |zopt(I)|，IA 则称H是A的近似算法。
启发式算法
背包问题的贪婪算法
1）将物品以ci/ai（单位体积的价值）由大到小的顺 序排列，不妨把排列记为{1,2,…,n},k:=1;
上述问题都是NP-hard问题，目前人们认为它们不存在 求解最优解的多项式时间算法，大规模情形只有尝试用一 些近似算法或启发式算法求解。
启发式算法
邻域概念
对于组合优化问题(D,F,f),D上的一个映射： N:SD N(S)2D
称为一个邻域映射，其中2D表示D的所有子集构 成的集合，N(S)称为S的邻域。
一个基于直观或经验构造的算法，在可接受 的花费（计算时间、占用空间等）下给出待解决 问题每一个实例的一个可行解，该解与最优解的 偏离程度不一定能预计。
启发式算法是一种技术，使在可接受的计算 开销内寻找最好的解，但不一定能保证所得解的 可行性和最优性，甚至多数情况下，无法给出所 得解同最优解的近似程度。
一些例子
4. 装箱问题(bin packing)
如何把n个尺寸不超过1的物品装入尺寸为1的箱子，并使 所用的箱子个数最少。
5. 二维装箱问题（平面上的套裁问题）
原料的尺寸大于需求的尺寸，需求的品种尺寸可以不同， 最终的目标是在满足需求的前提下，使边角余料最小。
6. 车间作业调度问题(job shop scheduling)
n个工件，J1,…,Jn在m台机器M1,M2,…,Mm上加工。每个工 件Ji有ni个工序，Oi1,…,Oini,第Oij工序的加工时间为pij，必须 按工序进行加工且每一工序必须一次加工完成。一台机器在任 何时刻最多只能加工一个产品，一个工件不能同时在两台机器 上加工，如何安排才能使最后一个完工的工件完工时间最小？
s.t. xij 1, i 1,, n
j1
n
xij 1, j 1,, n
i1
xij | S | 1, 2 | S | n 2,
i, jS
xij {0,1}, i, j 1,, n, i j.
S {1,2,, n}
一Байду номын сангаас例子
3. 有 约 束 的 机 器 调 度 问 题 ( capacitated machine scheduling)
类似可定义k-opt(k2)
启发式算法
局部最优与全局最优
若s*满足 f(s*)()f(s),其中sN(s*)F,
则称s*为f在F上的局部(local)最小（最大）解。 若s*满足 f(s*)()f(s),其中sF,
则称s*为f在F上的全局(global)最小（最大） 解。
启发式算法
启发式算法定义
min f ( x) s.t. g ( x) 0
xD
其中D表示有限个点组成的集合。
一些例子
1. 0-1背包问题
设有一个容积为b的背包，n个体积分别为
ai(i=1,2,…,n),价值分别为ci (i=1,2,…,n)的物品，如 何以最大的价值装包？
n
max ci xi
i 1
n
s.t. ai xi b
k1
2）若 di xi dk b ，则xk=1;否则xk=0,k:=k+1; i1
3) 当k=n+1时，停止；否则，转2).
(x1,x2,…,xn)为贪婪算法所得解，单位体积的价值越 大越先放入是贪婪算法的原则。
启发式算法
简单的邻域搜索算法
给定组合优化问题，假设其邻域结构已确定， 算法为 1）任选一个初始解s0F; 2) 在N(s0)中按某一规则选一s；若f(s)<f(s0),则 s0s；否则，N(s0) N(s0)-s; 3) 若N(s0)=,停止；否则，返回2).