组合优化问题及算法.ppt

Talk on CBIR MATHEMATICA MODEL 引言 一些例子 一些例子 一些例子 一些例子 一些例子 启发式算法 启发式算法 启发式算法 启发式算法 启发式算法 启发式算法 启发式算法 启发式算法 启发式算法 启发式算法的类型 模拟退火算法 模拟退火算法 模拟退火算法 模拟退火算法的渐近收敛性 模拟退火算法应用的一般要求 冷却进度表 冷却进度表 冷却进度表的参数设置 冷却进度表的参数设置 冷却进度表的参数设置 冷却进度表的参数设置 冷却进度表的参数设置 模拟退火算法的优点 模拟退火算法的优点 模拟退火算法的不足和改进途径 参考书 3）通用性和灵活性 该算法能应用于多种组合优化问题，为一个问题编制的程序可有效地用于其他问题。解的质量与CPU时间呈反向关系，针对不同的实例以及不同的解质要求，适当调整冷却进度表的参数值可使算法执行获得最佳的解时关系。 Talk on CBIR * Talk on CBIR * 制作: 龚劬 组合优化问题及其算法 组合最优化（combinatorial optimization)是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学(operations research)中的一个重要分支。所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型描述为： 其中D表示有限个点组成的集合。 1. 0-1背包问题 设有一个容积为b的背包，n个体积分别为 ai(i=1,2,…,n),价值分别为ci (i=1,2,…,n)的物品，如何以最大的价值装包？ 2. 旅行商问题(TSP，traveling salesman problem) 一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路径最短。 3.有约束的机器调度问题(capacitated machine scheduling) n个加工量为{di|i=1,2,…,n}的产品在一台机器上加工，机器在第t个时段的工作能力为ct,求完成所有产品加工所需时段数最少的调度方案 其中xit,T为决策变量,xit=1表示产品i在第t时段加工 4. 装箱问题(bin packing) 如何把n个尺寸不超过1的物品装入尺寸为1的箱子，并使所用的箱子个数最少。 5. 二维装箱问题（平面上的套裁问题） 原料的尺寸大于需求的尺寸，需求的品种尺寸可以不同，最终的目标是在满足需求的前提下，使边角余料最小。 6. 车间作业调度问题(job shop scheduling) n个工件，J1,…,Jn在m台机器M1,M2,…,Mm上加工。每个工件Ji有ni个工序，Oi1,…,Oini,第Oij工序的加工时间为pij，必须按工序进行加工且每一工序必须一次加工完成。一台机器在任何时刻最多只能加工一个产品，一个工件不能同时在两台机器上加工，如何安排才能使最后一个完工的工件完工时间最小？ 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)…… 上述问题都是NP-hard问题，目前人们认为它们不存在求解最优解的多项式时间算法，大规模情形只有尝试用一些近似算法或启发式算法求解。 邻域概念 对于组合优化问题(D,F,f),D上的一个映射： N:S?D ? N(S)?2D 称为一个邻域映射，其中2D表示D的所有子集构成的集合，N(S)称为S的邻域。 邻域的构造依赖于问题决策变量的表示，邻域的结构在现代化优化算法中起重要作用。 邻域概念 例如，前面例子2给出的TSP问题模型。由解空间 D={x?{0,1}n?(n-1)}，可以定义它的一种邻域为： k为一个正整数。 TSP问题解的另一种表示法为 D={S=(i1,i2,…,in)是1,2,…,n的一个排列} 邻域概念 TSP问题解的另一种表示法为 D={S=(i1,i2,…,in)是1,2,…,n的一个排列} 可以定义它的邻域映射为2-opt，即S中的两个元素对换。 如4个城市的TSP问题，当S=(