第6讲(局部与随机搜索策略)VIP免费

高级搜索一般认为，NP完全问题的算法复杂性是指数级的。当问题规模达到一定程度时，以前这些算法显得无能为力。局部搜索算法、模拟退火算法和遗传算法等是较新发展起来的算法，算法引入了随机因素，不一定能找到最优解，但一般能快速找到满意的解。主要内容：基本概念局部搜索算法模拟退火算法组合优化问题优化问题设x的决策变量，D为x的定义域，f(x)是指标函数，g(x)是约束条件集合。则优化问题可以表示为，求解满足g(x)的f(x)最小值问题。即：组合优化问题如果在定义域上，满足条件g(x)的解是有限的，则优化问题称为组合优化问题。现实世界中很多问题属于组合优化问题，或者可以转化为组合优化问题求解，如旅行商问题、皇后问题。))(|)((minxgxfDx组合优化问题举例TSP问题从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？约束机器排序问题n个加工量为di(i=1,2,…n)的产品在一台机器上加工，机器在第t个时段的工作能力为ct,完成所有产品加工的最少时段数。指派问题一家公司经理准备安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时获得的回报是不同的。如何分配工作方案可以获得最大收益？组合优化问题举例0-1背包问题设有一个容积为b的背包，n个体积分别为ai(i=1,2,…n),价值分别为ci(i=1,2,…n)的物品，如何以最大的价值装包？装箱问题如何用个数最少的尺寸为1的箱子装进n个尺寸不超过1的物品？SAT问题称判定一个公式是否存在一个模型的问题为可满足性问题(以后简称为SAT问题)。如果一个公式存在模型，则称该公式是可满足的，否则称为不可满足的。组合优化问题举例皇后问题在n×n的国际象棋棋盘上，摆放n个皇后，使得n个皇后之间不能相互“捕捉”？TSP问题从某个城市出发，经过n个指定的城市，每个城市只能且必须经过一次，最后回到出发城市，如何安排旅行商的行走路线以使总路程最短？QQQQ6135710bacde7691010问题规模与算法复杂度问题的规模通常用输入数据量n来衡量。如旅行商问题的城市数目、皇后问题的皇后数目等。当问题规模比较小时，由于组合优化问题的解是有限的，总可以通过枚举法获得问题的最优解。但当问题的规模比较大时，其状态数往往呈指数级增长，很难再通过枚举方法获得问题的解。对于同一个问题，不同的求解方法，其效率是不同的，差别可能会非常大。通常用算法的时间复杂度来评价一个求解方法的好坏。常用的算法复杂性函数多项式时间算法O(logn)、O(n)、O(nlogn）、O(n2)指数时间算法O(2n)、O(n!)、O(nn)旅行商问题和皇后问题，用枚举法的时间复杂度为O(n!)完备算法的复杂性在通常情况下仍是指数型的。对指数时间算法，当问题的规模大到一定程度时，因为所花费的时间太长了，以至于不能求解。时间复杂性函数比较-数值说明nh(n)10203040100n10ns20ns30ns40ns100nsnlogn10ns26ns44.3ns64.1ns200nsn2100ns400ns900ns1.6us10us2n1.0us1.9ms1.1s18.3min4.0世纪n!3.6ms77.1年8.4×1013世纪2.6×1029世纪3.0×10139世纪大规模组合优化问题的求解策略一些难以求解的组合优化问题，至今尚未找到多项式时间算法来获得问题的最优解，如旅行商问题。实际上，在很多情况下追求最优解不一定有意义，一个满意解就可以了。如买西瓜。求满意解的基本思想是：引入随机因素，每次运行并不能保证求得问题的最优解，但经过多次运行后，一般总能得到一个与最优解相差不太大的满意解，以放弃每次必然找到最优解的目标，来换取算法时间复杂度的降低，以适合于求解大规模的优化问题。邻域的概念在组合优化问题中，变量x的一个取值看作一个点；如果是多变量的问题，一组变量的一个取值组合可以看作一个点,即:点就是一个候选解。邻域，简单地说就是一个点附近的其他点的集合。在距离空间中，邻域一般定义为以该点为中心的一个圆。在组合优化问题中，可将邻域定义为：设D是问题的定义域，若存在一个映射N，使得：N：S∈D→N(S)2∈D则称N(S)为S的邻域，称S‘∈N(S)为S的邻居。常见的几种邻域一...