机械故障诊断学 钟秉林 第8章模拟退火与演化算法的原理及应用教材课程.ppt

第8章 模拟退火与演化算法的原理及应用;一、概述;定义：组合优化问题π是一个最小化问题，或是一个最大化问题，它由下面三部分组成： (1) 实例集合； (2) 对每一个实例 I，有一个有穷的可行解集合 S(I)； (3) 目标函数 f，它对每一个实例 I 和每一个可行解 ，赋以一个有理数 。 ;一个通俗的定义： 所谓组合优化，是指在离散的、有限的数学结构上，寻找一个（或一组）满足给定约束条件并使其目标函数值达到最大或最小的解。 一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全（难）问题，因此，精确地求解组合优化问题的全局最优解的“有效”算法一般是不存在的。;典型的组合优化问题主要有如下几种： 集覆盖问题（set-covering problem） 装箱问题（bin-packing problem） 0-1背包???题（knapsack problem） 指派问题（assignment problem） 旅行商问题（traveling salesman problem）[TSP、货郎担问题] 影片递送问题（film delivery problem） 图划分问题（graph partitioning problem） 作业调度问题（job-shop scheduling problem）;集覆盖问题（set-covering problem） 对于一个m行n列的0－1矩阵A，每行代表一种任务，每列代表一个人，aij=1表示第j个人能完成第i个任务。每个人都有一个雇佣代价。问题的目标是：用最小的代价选择一些人（矩阵的列），使得每一个任务都至少有一个人能完成。 设向量x的元素 xj=1 表示列 j 被选中（费用是cj0）， xj=0 则表示其未被选中（j=1,2,…,n）。 已经证明集覆盖问题是NP完全问题。;如果所有费用cj都相同，则问题称为单一费用问题（unicost set-covering problem）。如果为等式约束，则称为集划分问题（set partitioning problem）;Cost = 29;装箱问题（bin packing problem）;货运装箱问题 截铜棒问题 布匹套裁问题 。。。 装箱问题属于NP－难问题;0/1背包问题： 给出几个体积为S1，S2，…，Sn的物体和容量为C的背包；要求找出n个物件的一个子集使其尽可能多地填满容量为C的背包。 数学形式： 最大化 满足 ;广义背包问题： 输入由背包容积C和两个向量：物品体积S＝(S1，S2，…，Sn)和物品价值P＝(P1，P2，…，Pn)组成。设X为一整数集合（物品的标识），X＝1，2，3，…，n，T为X的子集，则问题就是找出满足约束条件，并使总价值最大的子集T。 数学形式： 最大化 满足 ;在应用问题中，设S的元素是n项经营活动各自所需的资源消耗，C是所能提供的资源总量，P的元素是人们从每项经营活动中得到的利润或收益，则背包问题就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。 背包问题属于NP-难问题;多选择背包问题： 有一个容积有限的背包。要放入背包的物品被分为不重叠的若干类，每类中有若干不同的物品，从每类中选择一个物品，使得物品总体积在满足背包容积约束的前提下最大化收益。 属于NP－难问题;i为类下标；j为类中物品的下标；ni是第i类中物品的数量；cij是第i类中第j个物品的收益；m是类的数量；wij为第i类中第j个项目的体积，W是背包的容积。;旅行商问题（Traveling Salesman Problem） 寻找一条最短的遍历n个城市的路径，或者说有哪些信誉好的足球投注网站整数子集X＝{1，2，…，n}（X的元素表示对n个城市的编号）的一个排列π(X) = {v1，v2，…，vn}，使下式取最小值。 式中的d(vi, vi+1)表示城市vi到城市vi+1的距离。 对称旅行商问题是NP－难问题;影片递送问题（Film Delivery Problem） 一盘影片拷贝要在n个电影院放映。每个电影院放映的次数已定，记为一个非负的整数di(i＝1，2，…，n)。两个影院间的距离记为wij，若影院i和j不能直接相连，则令wij＝+?。 问题是要为影片递送员找一个巡回，从主影院1开始，将影片拷贝送到第i家影院di(i＝1，2，…，n)次，最后回到主影院1，并极小化总的路线长度。当所有的di(i＝l，2，…，n)为1时，FDP变为经典的TSP。 FDP是TSP的新扩展，它可以推广到一大类路径与排序问题中。;图的二划分问题： 对于一无向图G，设其顶点集合为V，将顶点集合V划分