《大连海事大学《现代优化技术》第5讲：传统启发式算法之构筑法》由会员分享，可在线阅读，更多相关《大连海事大学《现代优化技术》第5讲：传统启发式算法之构筑法（36页珍藏版）》请在金锄头文库上搜索。
1、现代优化技术,第5讲：传统启发式算法之构筑法,主要内容,启发式算法含义 启发式算法的宿命论 启发式算法求解问题的一般程序 启发式算法策略 几种典型的构筑法 （1）背包问题的构筑法 （2）旅行商问题的构筑法 （3）配送问题的构筑法,启发式算法（heuristics）,含义：启发性算法是一种优化技术，可以在可接 受计算时间下给出待求解问题每一个实例的近似最优解，但无法保证所得解的精确度。 目标：求得“满意解”，而非最优解 1）精确解无法找到； 2）过高精度的解无实际意义； 3）求最优解代价太高。,启发式方法的概念图,全局最优解,可行解集合,目标函数,局部最优解,启发式算法的宿命论 例：Travel
2、ing Salesman Problem (TSP),启发式算法的宿命论：计算复杂性 例：Traveling Salesman Problem (TSP),个客户的TSP問題 ( 30! 1030 ) 高性能計算機求解最优解需要日 (n-1)(n-2)321=(n-1)! 1 PIPS (Peta Instruction Per Second)=1015 30!/1015 （秒） 1015 （秒） 105 （世紀） （穷举法）,启发式算法的宿命论：问题复杂性 例：TSP的各种扩展问题及其现实应用,VRP问题:(vehicle routing problems） VRPTW问题: （vehicl
3、e routing problem with time windows） VRPPD问题： (VRP with pickup & delivery) IRP问题： (inventory routing problem: VRP + inventory problem),启发式算法的宿命论：问题复杂性,DANTZIG42 solved by George Dantzig, Ray Fulkerson and Selmer Johnson (1954),启发式算法的宿命论：问题复杂性,GR120 solved by Groetschel (1977),启发式算法的宿命论：问题复杂性,The opt
4、imal tour of ATT532 (532 AT&T switch locations in the USA) found by Padberg and Rinaldi (1987),启发式算法的宿命论：问题复杂性,The optimal tour of GR666 Found by Groetschel and Holland (1987),启发式算法的宿命论：问题复杂性,The optimal tour of USA13509 found by Applegate, Bixby, Chvtal, and Cook (1998),启发式算法的宿命论：问题复杂性,The optimal
5、tour of D15112 found by Applegate, Bixby, Chvtal, and Cook (2001),CPU time used is 22.6 years of computer time, adjusted to a 500 MHz, EV6 Alpha processor,启发式算法的宿命论：问题复杂性,1,904,711-city instance,现世界纪录?,启发式算法求解问题的一般程序,得到的解可接受吗？,可得到有助于搜索的新信息？,有可能重新 考虑问题吗？,分析问题， 建立优化模型,研究模型结构,设计启发式规则,应用规则,修正启发式规则,得到满意解
6、,得不到解,Y,Y,N,Y,N,启发式算法策略,逐步构造解策略：每次增加解的一个元素，直到得到一个完整的满意解 改进解策略：从一个初始解（并非一定为可行解）开始，通过一系列替换，分解和合并过程来逐步修正，以提高解的可接受性。 分解策略：把一个复杂的问题分解成一系列容易处理的子问题来求解，一个子问题的输出为下一个子问题的输入。 分割策略：把一个复杂的问题分解成一些平行的子问题，然后求解每个子问题，最后在相容原则下进行综合，把子问题的解合并成原问题的解。 松弛策略：扩展问题的可行域，得到一个易于处理的松弛问题，然后求解松弛问题，就能很容易得到原问题的一个可行解，再对这一可行解进行修正。,构筑法,(
7、construction algorithms) (greedy algorithms), greedy method for knapsack problem nearest neighbor for TSP nearest addition for TSP random nearest neighbor for TSP saving algorithm for VRP,利用对目标函数值的贡献度来衡量和评价局部解， 继而直接构成实行可行解。,构筑法,knapsack problem,物品的集合： N=1,2,n 物品i 的価値 ： vi 物品i 的重量 ： wi 単位重量的価値： vi /w
8、i 背包的载重量制约 W,构筑法,Greedy algorithm for knapsack problem,Step 1. 按单位重量价值的大小对物品进行排序， 即 vi1 /wi1 vi2 /wi2 vin /win,令 w*=W 以及 k=1,Step 2. 如 wikw*, 则 zik=1； w*=w*-wik; 相反，如wikw*, 则 zik=0,Step 3. 如 kn-1, 则 k=k+1, 返回 step 2. 如 k=n, 输出最终解z.,构筑法,nearest neighbor for TSP,TSP的最近近邻法：从某一个客户出发，选择尚未访问的客户中距现在的客户最近的作
9、为下一个要访问的客户，反复这一步骤，直到所有访问完毕。,V: 客户的集合 SV: 尚未访问的客户的集合,构筑中的部分巡回路,构筑法,nearest neighbor 法图示,构筑法,Nearest neighbor algorithm for TSP,Step 1. 令 k=1，S=V. 从 iV 任选一客户,Step 2. 设,Step 3. 令 返回 step 2.,此时若,则输出巡回路,探索终了。,以及,构筑法,Random nearest neighbor 法,将对目标函数值的贡献度（如巡回路增加值）作为评价指标，以评价值从大到小的顺序（距现行出发点从近到远的顺序），作为几个可行的部分
10、解，然后，从中随机选取一个作为下一个出发点，,反复这一步骤直到得到完整的可行解。 与单纯的nearest neighbor 法对比，加入了随机选择性，使解具有多样性。,构筑法,Random nearest neighbor 法,Random nearest 法图示,1,2,a,b,c,构筑法,Random nearest neighbor algorithm for TSP,Step 1. 令 k=1，S=V. 从 iV 任选一客户,Step 2. 设,Step 3. 对于现在的 i, 从集合S中按dij的从小到大的顺序选择候补客户 j, 其集合为 . Step 4. 从集合 中随机选取一个
11、，作为 i , , 返回 step 2.,此时若,则输出巡回路,探索终了。,构筑法,Multiple fragment method for TSP,Multiple fragment method 多部分巡回路法 思路：首先生成多个部分巡回路（subtour)， 然后连接这些部分，形成完整的巡回路。 条件：在生成部分巡回路的过程中， 1.与各都市相连的枝的个数不超过2个； 2.不能出现部分闭巡回路。 过程：在满足上述2条件的前提下，按dij 的从小到大的顺序多个生成部分巡回路，最后形成完整的巡回路。,Greedy 性,构筑法,Closed subtours,部分闭巡回路（closed sub
12、tour） 图示例,构筑法,多部分巡回路算法用符号,点（dot）：各个都市 枝 (edge)：连接两个客户的部分巡回路 通路 (path)：非闭的部分巡回路 现阶段部分巡回路中包含的枝的集合 现阶段部分巡回路中尚未包含的枝的集合 当中与客户i相连接的枝的个数 通路一端的端点i所对应的另一端端点（客户）号。,构筑法,多部分巡回路算法（1）,构筑法,多部分巡回路算法（2）,构筑法,多部分巡回路法的实行例,(1).途中的多个部分巡回路,(2). 最终得到的完整巡回路,1,2,3,4,5,6,7,8,9,10,构筑法,VRP (vehicle routing problem),配送 中心,顾客,总費用
13、或总距离最小化 route内的顧客需要量不能超过车的載重量 工作時間的上限 不能超过,构筑法,配送 中心,配送 中心,Saving value Sij 的计算 （移動費用対称 cij=cji）,所有客户都从库存点的 之间的直行运输开始！,根据客户i,j连续运输时的節約量 （saving value）的从大到小顺序来连续运输！,Saving algorithm for VRP,构筑法,Saving algorithm for VRP,Step1. 计算所有的顧客对（ i,j）的saving value Sij Step2. saving value Sij的从大到小的顺序重新排列 得到新的顧客对顺序list Step3. 重复以下的操作直到list变空为止： (1). 按list的顺序，调查将顧客 i,j 間直接运输的実行可能性 (2).如果这种実行可能性存在，则连接 i与 j。 (3).如果不存在这种実行可能性，则削除现在的顾客对，然后调查下一个顧客对,构筑法,Saving algorithm解法事例,台,総距離 ,OR Lib. 的199顧客問題附 有重量及工作時間制约条件,DC,Q & A,
