大连海事大学《现代优化技术》第5讲:传统启发式算法之构筑法.ppt_第1页
大连海事大学《现代优化技术》第5讲:传统启发式算法之构筑法.ppt_第2页
大连海事大学《现代优化技术》第5讲:传统启发式算法之构筑法.ppt_第3页
大连海事大学《现代优化技术》第5讲:传统启发式算法之构筑法.ppt_第4页
大连海事大学《现代优化技术》第5讲:传统启发式算法之构筑法.ppt_第5页
已阅读5页,还剩31页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

现代优化技术 第5讲:传统启发式算法之构筑法 主要内容 启发式算法含义 启发式算法的宿命论 启发式算法求解问题的一般程序 启发式算法策略 几种典型的构筑法 (1)背包问题的构筑法 (2)旅行商问题的构筑法 (3)配送问题的构筑法 启发式算法(heuristics) 含义:启发性算法是一种优化技术,可以在可接 受计算时间下给出待求解问题每一个实例的近似 最优解,但无法保证所得解的精确度。 目标:求得“满意解”,而非最优解 1)精确解无法找到; 2)过高精度的解无实际意义; 3)求最优解代价太高。 启发式方法的概念图 全局最优解 可行解集合 目标函数 局部最优解 启发式算法的宿命论 例:Traveling 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问题: (vehicle routing problem with time windows) VRPPD问题: (VRP with pickup 相反,如wikw*, 则 zik=0 Step 3. 如 kn-1, 则 k=k+1, 返回 step 2. 如 k=n, 输出最终解z. 构筑法 nearest neighbor for TSP TSP的最近近邻法:从某一个客户出发,选择尚未访 问的客户中距现在的客户最近的作为下一个要访问 的客户,反复这一步骤,直到所有访问完毕。 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 法 将对目标函数值的贡献度(如巡回路增加值)作为评 价指标,以评价值从大到小的顺序(距现行出发点 从近到远的顺序),作为几个可行的部分解,然后 ,从中随机选取一个作为下一个出发点,,反复这 一步骤直到得到完整的可行解。 与单纯的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. 从集合 中随机选取一个 ,作为 i , , 返回 step 2. 此时若 则输出巡回路 探索终了。 构筑法 Multiple fragment method for TSP Multiple fragment method 多部分巡回路法 思路:首先生成多个部分巡回路(subtour), 然后 连接这些部分,形成完整的巡回路。 条件:在生成部分巡回路的过程中, 1.与各都市相连的枝的个数不超过2个; 2.不能出现部分闭巡回路。 过程:在满足上述2条件的前提下,按dij 的从小到大 的顺序多个生成部分巡回路,最后形成完整的巡回 路。 Greedy 性 构筑法 Closed subtours 部分闭巡回路(closed subtour) 图示例 构筑法 多部分巡回路算法用符号 点(dot):各个都市 枝 (edge):连接两个客户的部分巡回路 通路 (path):非闭的部分巡回路 现阶段部分巡回路中包含的枝的集合 现阶段部分巡回路中尚未包含的枝的集合 当中与客户i相连接的枝的个数 通路一端的端点i所对应的另一端端点(客户)号 。 构筑法 多部分巡回路算法(1) 构筑法 多部分巡回路算法(2) 构筑法 多部分巡回路法的实行例 (1).途中的多个部分巡回路(2). 最终得到的完整巡回路 1 2 3 4 5 6 7 8 9 10 构筑法 VRP (vehicle routing problem) 配送配送 中心中心 顾客顾客 v总費用或总距离最小 化 vroute内的顧客需要 量不能超过车的載重 量 v工作時間的上限 不能超过 构筑法 配送配送 中心中心 配送配送 中心中心 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).如果这种実

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论