大连海事大学现代优化技术第5讲传统启发式算法之构筑法

1、现代优化技术现代优化技术第第5 5讲：传统启发式算法之构筑法讲：传统启发式算法之构筑法主要内容主要内容 启发式算法含义启发式算法含义 启发式算法的宿命论启发式算法的宿命论 启发式算法求解问题的一般程序启发式算法求解问题的一般程序 启发式算法策略启发式算法策略 几种典型的构筑法几种典型的构筑法 （1 1）背包问题的构筑法）背包问题的构筑法 （2 2）旅行商问题的构筑法）旅行商问题的构筑法 （3 3）配送问题的构筑法）配送问题的构筑法启发式算法（启发式算法（heuristicsheuristics）含义：启发性算法是一种优化技术，可以在可接含义：启发性算法是一种优化技术，可以在可接 受计算时间下给

2、出待求解问题每一个实例的近似受计算时间下给出待求解问题每一个实例的近似最优解，但无法保证所得解的精确度。最优解，但无法保证所得解的精确度。目标：求得目标：求得“满意解满意解”，而非最优解，而非最优解 1 1）精确解无法找到；）精确解无法找到； 2 2）过高精度的解无实际意义；）过高精度的解无实际意义； 3 3）求最优解代价太高。）求最优解代价太高。启发式方法的概念图启发式方法的概念图全局最优解全局最优解可行解集合可行解集合目标函数目标函数局部最优解局部最优解启发式算法的宿命论启发式算法的宿命论例：例：traveling salesman problem (tsp)traveling sales

3、man problem (tsp) 启发式算法的宿命论：计算复杂性启发式算法的宿命论：计算复杂性例：例：traveling salesman problem (tsp)traveling salesman problem (tsp)个客户的个客户的tsptsp問題問題 ( 30! ( 30! 10103030 ) )高性能計算機求解最优解需要日高性能計算機求解最优解需要日(n-1)(n-1)(n-2)(n-2)3 32 21=(n-1)!1=(n-1)!1 pips (peta instruction per second)=101 pips (peta instruction per sec

4、ond)=101515 30!/10 30!/101515 （秒）（秒） 101015 15 （秒）（秒） 10 105 5 （世紀）（世紀）（穷举法）（穷举法） 启发式算法的宿命论：问题复杂性启发式算法的宿命论：问题复杂性例：例：tsptsp的各种扩展问题及其现实应用的各种扩展问题及其现实应用vrpvrp问题问题:( :(vehicle routing problemsvehicle routing problems）vrptwvrptw问题问题: : （vehicle routing problem with time windowsvehicle routing problem with

5、 time windows）vrppdvrppd问题问题： (vrp with pickup & delivery)(vrp with pickup & delivery)irpirp问题问题： (inventory routing problem: (inventory routing problem: vrp + inventory problem) vrp + inventory problem) 启发式算法的宿命论：问题复杂性启发式算法的宿命论：问题复杂性dantzig42 solved bygeorge dantzig, ray fulkerson and selmer johnso

6、n (1954) 启发式算法的宿命论：问题复杂性启发式算法的宿命论：问题复杂性gr120 solved by groetschel (1977) 启发式算法的宿命论：问题复杂性启发式算法的宿命论：问题复杂性the optimal 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)

7、启发式算法的宿命论：问题复杂性启发式算法的宿命论：问题复杂性the optimal tour of usa13509 found by applegate, bixby, chvtal, and cook (1998) 启发式算法的宿命论：问题复杂性启发式算法的宿命论：问题复杂性the optimal 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 proc

8、essor 启发式算法的宿命论：问题复杂性启发式算法的宿命论：问题复杂性1,904,711-city instance 现世界纪录现世界纪录?启发式算法求解问题启发式算法求解问题的一般程序的一般程序得到的解可接受吗？得到的解可接受吗？可得到有助于搜索的新信息？可得到有助于搜索的新信息？有可能重新有可能重新考虑问题吗？考虑问题吗？分析问题，分析问题， 建立优化模型建立优化模型研究模型结构研究模型结构设计启发式规则设计启发式规则应用规则应用规则修正启发式规则修正启发式规则得到满意解得到满意解得不到解得不到解y yy yn ny yn n启发式算法策略启发式算法策略逐步构造解策略：每次增加解的一个元

9、素，直到得逐步构造解策略：每次增加解的一个元素，直到得到一个完整的满意解到一个完整的满意解改进解策略：从一个初始解（并非一定为可行解）改进解策略：从一个初始解（并非一定为可行解）开始，通过一系列替换，分解和合并过程来逐步修开始，通过一系列替换，分解和合并过程来逐步修正，以提高解的可接受性。正，以提高解的可接受性。分解策略：把一个复杂的问题分解成一系列容易处分解策略：把一个复杂的问题分解成一系列容易处理的子问题来求解，一个子问题的输出为下一个子理的子问题来求解，一个子问题的输出为下一个子问题的输入。问题的输入。分割策略：把一个复杂的问题分解成一些平行的子分割策略：把一个复杂的问题分解成一些平行的

10、子问题，然后求解每个子问题，最后在相容原则下进问题，然后求解每个子问题，最后在相容原则下进行综合，把子问题的解合并成原问题的解。行综合，把子问题的解合并成原问题的解。松弛策略：扩展问题的可行域，得到一个易于处理松弛策略：扩展问题的可行域，得到一个易于处理的松弛问题，然后求解松弛问题，就能很容易得到的松弛问题，然后求解松弛问题，就能很容易得到原问题的一个可行解，再对这一可行解进行修正。原问题的一个可行解，再对这一可行解进行修正。构筑法构筑法(construction algorithms)(greedy algorithms) greedy method for knapsack problem

11、 nearest neighbor for tsp nearest addition for tsp random nearest neighbor for tsp saving algorithm for vrp利用对目标函数值的贡献度来衡量和评价局部解，利用对目标函数值的贡献度来衡量和评价局部解，继而直接构成实行可行解。继而直接构成实行可行解。构筑法构筑法knapsack problem物品的集合：物品的集合： n=1,2,nn=1,2,n物品物品i i 的的価値価値 ： v vi i物品物品i i 的重量的重量 ： w wi i単位重量的価値：単位重量的価値： v vi i /w /wi

12、 i背包的载重量制约背包的载重量制约 w w1616万円2323万円2828万円2kg3kg4kg5kg19万円極小小中大构筑法构筑法greedy algorithm for knapsack problemstep 1. 按单位重量价值的大小对物品进行排序，按单位重量价值的大小对物品进行排序， 即即 vi1 /wi1 vi2 /wi2 vin /win令令 w*=w 以及以及 k=1step 2. 如如 wikw*, 则则 zik=1； w*=w*-wik; 相反，如相反，如wikw*, 则则 zik=0 step 3. 如如 kn-1, 则则 k=k+1, 返回返回 step 2. 如如

13、k=n, 输出最终解输出最终解z.构筑法构筑法nearest neighbor for tsptsp的最近近邻法：从某一个客户出发，选择尚未访的最近近邻法：从某一个客户出发，选择尚未访问的客户中距现在的客户最近的作为下一个要访问问的客户中距现在的客户最近的作为下一个要访问的客户，反复这一步骤，直到所有访问完毕。的客户，反复这一步骤，直到所有访问完毕。v: 客户的集合客户的集合sv: 尚未访问的客户的集合尚未访问的客户的集合构筑中的部分巡回路构筑中的部分巡回路构筑法构筑法nearest neighbor 法图示法图示构筑法构筑法nearest neighbor algorithm for tsp

14、step 1. 令令 k=1，s=v. 从从 iv 任选一客户任选一客户step 2. 设设step 3. 令令 返回返回 step 2. issik/,此时若此时若,s则输出巡回路则输出巡回路 探索终了。探索终了。ijsjdiminarg以及以及1 kk构筑法构筑法random nearest neighbor 法法将对目标函数值的贡献度（如巡回路增加值）作为评将对目标函数值的贡献度（如巡回路增加值）作为评价指标，以评价值从大到小的顺序（距现行出发点价指标，以评价值从大到小的顺序（距现行出发点从近到远的顺序），作为几个可行的部分解，然后，从近到远的顺序），作为几个可行的部分解，然后，从中随机

15、选取一个作为下一个出发点，从中随机选取一个作为下一个出发点，,反复这反复这一步骤直到得到完整的可行解。一步骤直到得到完整的可行解。与单纯的与单纯的nearest neighbor 法对比，加入了随机选法对比，加入了随机选择性，使解具有多样性。择性，使解具有多样性。构筑法构筑法random nearest neighbor 法法random nearest 法图示法图示12abc构筑法构筑法random nearest neighbor algorithm for tspstep 1. 令令 k=1，s=v. 从从 iv 任选一客户任选一客户step 2. 设设step 3. 对于现在的对于现在

16、的 i, 从集合从集合s中按中按dij的从小到的从小到大的顺序选择候补客户大的顺序选择候补客户 j, 其集合为其集合为 . step 4. 从集合从集合 中随机选取一个中随机选取一个 ，作为，作为 i , , 返回返回 step 2. issik/,此时若此时若,s则输出巡回路则输出巡回路 探索终了。探索终了。1 kklll,.,2 , 1l构筑法构筑法multiple fragment method for tspmultiple fragment method 多部分巡回路法多部分巡回路法思路：首先生成多个部分巡回路（思路：首先生成多个部分巡回路（subtour)， 然后然后连接这些部分，

17、形成完整的巡回路。连接这些部分，形成完整的巡回路。条件：在生成部分巡回路的过程中，条件：在生成部分巡回路的过程中，1.与各都市相连的枝的个数不超过与各都市相连的枝的个数不超过2个；个；2.不能出现部分闭巡回路。不能出现部分闭巡回路。过程：在满足上述过程：在满足上述2条件的前提下，按条件的前提下，按dij 的从小到大的从小到大的顺序多个生成部分巡回路，最后形成完整的巡回的顺序多个生成部分巡回路，最后形成完整的巡回路。路。greedy 性性构筑法构筑法closed subtours部分闭巡回路（部分闭巡回路（closed subtour）图示例图示例构筑法构筑法多部分巡回路算法用符号多部分巡回路算

18、法用符号点（点（dot）：各个都市）：各个都市 枝枝 (edge)：连接两个客户的部分巡回路：连接两个客户的部分巡回路 通路通路 (path)：非闭的部分巡回路：非闭的部分巡回路 现阶段部分巡回路中包含的枝的集合现阶段部分巡回路中包含的枝的集合现阶段部分巡回路中尚未包含的枝的集合现阶段部分巡回路中尚未包含的枝的集合 当中与客户当中与客户i相连接的枝的个数相连接的枝的个数通路一端的端点通路一端的端点i所对应的另一端端点（客户）所对应的另一端端点（客户）号。号。 :reste :i:sole :isole构筑法构筑法多部分巡回路算法（多部分巡回路算法（1） viallforiiiandenjini

19、jieletstepsolrest, 0, 11,. 1jieeletandetheindimumthebetojisupposesteprestrestrestij,/min,.2 ) 1(. 2, 22. 3条件steptobackgojoriifstep )2(. 2,1. 4条件steptobackgoijandiifstep构筑法构筑法多部分巡回路算法（多部分巡回路算法（2） ijjijjiiletandjjiijieeletstepsolsol, 1, 1,.5 . 2;1,)21(, 1. 6steptobackgootherwisejijieethenineifstepsols

20、olsol个的客户仅剩下此时构筑法构筑法多部分巡回路法的实行例多部分巡回路法的实行例(1).途中的多个部分巡回路途中的多个部分巡回路(2). 最终得到的完整巡回路最终得到的完整巡回路ca )(ac )(abc12345678910构筑法构筑法vrp (vehicle routing problem)vrp (vehicle routing problem)v总費用或总距离最小总費用或总距离最小化化vrouteroute内的顧客需要内的顧客需要量不能超过车的載重量不能超过车的載重量量v工作時間的上限工作時間的上限 不能超过不能超过构筑法构筑法saving value ssaving value