04讲(路线规划)ppt课件.ppt

配送线路规划 第四章 4 6 2020 P2 两点间路径问题 T标号 TentativeLabel P标号 PermanentLabel 4 6 2020 P3 多点间路径问题 4 6 2020 P4 2020 4 6 4 Floyd算法 Floyd算法是寻找加权图 权值可为负 中任意两个结点间最短路径的算法 思路 两结点间的最短路径要么是相邻时最短 要么是以通过几个中间结点为跳板时距离最短 算法每次以其中一个结点为跳板 如果以该结点为跳板后两结点间路径缩短 则更新这两结点间的路径 算法执行V次结束 直到测试完每个充当跳板的结点 4 6 2020 P5 2020 4 6 5 Floyd算法 过程 Floyd算法采用邻接矩阵W作为图的存储结构 W i j 表示结点vi和vj之间的距离 权重 D k 记录经历k步后 两点间的路径长 k 0 n 初始时 W D 0 P记录每步更新时结点间经历的中间结点 通过对P矩阵的回溯操作 可得两点间的最短路径 初始时 P为0矩阵 P5 4 6 2020 P6 2020 4 6 6 Floyd算法 算法第k步的更新规则 以结点k为跳板 测试通过该结点后 两点间距离是否缩短 若距离不缩短则保留k 1步的结果 D k i j D k 1 i j 若距离缩短则更新两点间的距离 D k i j D k 1 i k D k 1 k j 即 D k i j min D k 1 i j D k 1 i k D k 1 k j 如果第k个结点对缩短vi和vj间的路径做出贡献 P i j k 4 6 2020 P7 2020 4 6 7 Floyd算法 Floyd算法实例 图G及算法初始状态 D 0 W P 0 如下所示 2020 4 6 8 Floyd算法 P8 2020 4 6 9 Floyd算法 矩阵D 4 中 无穷大元素表明其坐标对应的结点间无路径可达 其它元素表示两点间最短路径的长度 最终P指示如何通过回溯得到两结点间的最短路径 例 2到4的最短路径经过3 则有2 3 4 2到3经过1 则有2 1 3 4 2到1再无结点 P中对应0 回溯结束 2到4之间最短路径为2 1 3 4 D 2 4 9 P9 运输问题 略 P10 线路问题的引入 1 P11 车辆运送作业是物流中心最终及最具体直接的服务表征 运送管理的困难在于其可变因素太多 而且因素与因素间往往又相互影响 最直接的影响反映在运送的费用上 车辆路线问题 VRP 是物流中心成本问题的重要主体 如考虑到顾客需求量不确定的限制 该问题研究的重点是如何处理车辆的安排 运送路径选择 运送顺序的问题 等等 以求得成本最小 线路问题综述 P12 TSP的假设是 有n个城市C1 C2 Cn Dij表示Ci与Cj间的距离 有一个推销员从某一城市出发 访问各城市且仅一次 再回到原出发城市 要求找一条最短的巡回路线 问题的提出 推销员旅行问题 TSP TravelingSalesmanProblem P13 假设车辆具有容量限制下 找出通过所有需求点总成本最小的数条路线 同时每条路线必须由场站 Depot 出发 服务过数个需求点后再回到场站 主要目标是在满足下列限制 并求得每部车辆拜访顾客的顺序 使得车辆行驶总距离最短 1 每个需求点只能由一辆车服务一次 2 须满足所有需求点的需求 3 每一辆车都由场站出发 最后须回到场站 4 每车辆所服务的总需求量不能超过该车辆的容量 传统车辆路线问题 VRP VehicleRoutingProblem P14 TSP VRP问题的传统求解 穷举搜寻 ExhaustiveSearchMethods 动态规划 DynamicProgrammingMethods 整数规划法 IntegerProgrammingMethods 分枝界限法 BranchandBoundMethods 正确解 ExactSolution P15 穷举搜寻法是一种简单但是费时的方法 因为它要把所有可能的路径集合解都列举出来 然后从中选择一个最短的 从组合数学的理论可知 当城市数目为n时 穷举法的方案数为 如果考虑每条路径要计算n个距离之和 则计算的工作量将正比于n 2 以下是用每秒运算100亿次加法计算的计算机按穷举搜寻法计算TSP所需的时间 穷举搜寻 ExhaustiveSearchMethods P16 以穷举法求解TSP所需的计算时间表 P17 4 6 2020 P18 整数规划法 IntegerProgrammingMethods 4 6 2020 P19 设S表示从v1到vi中间所可能的集合 S中的点的个数要随阶段改变 阶段 S中的点的个数 状态变量 i S 从v1点出发 经过S集合中所有点一次最后到达vi 最优指标函数fk i S 从v1出发 经过S集合中所有点一次最后到达vi 决策变量Pk i S 从v1经k个中间城镇的S到vi城镇的最短路线上邻接vi的前一个城镇 状态转移方程 边界条件 动态规划 DynamicProgrammingMethods 动态规划法最主要的特色 是将一个问题切成好几段相互联系的阶段 接着在每个阶段去进行决策上的最佳化 在此每一个阶段决策最佳化的过程中 无论一开始的状况和一开始的决策为何 以后的最佳化策略都只取决于一开始决策所形成的当时状态 由于动态规划法是经过各个阶段性的最佳化决策过程 将之与穷举法比较 将会减少组合过多的问题 下页列出了不同城市数的TSP动态规划法 空间及时间的复杂度 例如以n 60为例 用一台每秒运算100亿次加法运算的计算机求解TSP时 需时超过3230年 动态规划 DynamicProgrammingMethods P20 不同城市数的TSP动态规划法 空间 时间复杂度 P21 分枝界定法 BranchandBoundMethods 分枝界限法的三个主要步骤为 分枝 界限 剪枝 先将问题的可行解展开为分枝树 而在搜寻分枝的过程中 同时设定解值的上限或下限值 当某节点其下限值超过问题的上限时 表示解比目前已求得的解差 则停止再往下分枝 重复搜寻步骤 再由各个分枝中寻找最佳解 P22 4 6 2020 P23 1 任取初始H圈 C0 v1 vi vj vm v1 2 对所有的i j 1 i 1 j m 若 w vi vj w vi 1 vj 1 w vi vi 1 w vj vj 1 则在C0中删去边 vi vi 1 和 vj vj 1 而加入边 vi vj 和 vi 1 vj 1 形成新的H圈C 即C v1 vi vj vj 1 vi 1 vj 1 vi v1 3 重复步骤 2 直到条件不满足为止 最后得到的C即为所求 二次逐次修正法 4 6 2020 P24 4 6 2020 P25 最差情况下 Worst caseAnalysis 若总节点数目为n 则出发点有n种选择 第2个节点的选择为n 1 第3个节点为n 2 依次递减 所以总组合数目为n 计算量仍然很大 以分枝界限法求解TSP所需的计算时间表 P26 以上问题属于 未定论多项式难度 问题 NondeterministicPolynomialHard NP Hard 即在求解最佳解的时候 随着目标节点的增加 其难度会呈指数增长的问题 我们需要另辟蹊径 首先界定问题 TSP VRP问题传统解法的总结 P27 途程问题 RP RoutingProblem 节线途程问题 LRP LinkRoutingProblem 旅行推销员问题 TSP 节线途程问题 NRP NodeRoutingProblem 多重推销员问题 MTSP 多场站途程问题 MDVRP 单场站途程问题 VRP 随机途程问题 SVRP 中国邮差问题 CPP 载量限制邮差问题 CCPP 基本途程问题族谱图 P28 途程问题细分 P29 启发式 heuristics 意为通过对过去经验的归纳推理以及实验分析来解决问题的方法 即借助于某种直观推断或试探的方法 启发式方法要求分析人员必须运用自己的感知和洞察力 从与研究问题有关而较基本的模型及算法中寻求其间的联系 从中得到启发 去发现适于解决该问题的思路和途径 用启发式方法解决问题时强调 满意 而不去追求最优性和探求最优解 原因是 1 很多问题不存在严格最优解 例如目标之间矛盾的多目标问题 这时 对目标的满意性常比最优性更能准确地描述人们的选择行为 2 对有些问题 得到它的最优解所花的代价太大 3 从实际决策的需要出发 有时要求解具有过高的精度没有意义 启发式方法能够比较快地得到满意解 这对NP Hard来说有着不可估量的作用 启发式算法heuristics P30 P31 4 6 2020 P32 线路优化的常见启发式算法 2 1 50年代Dantzig Ramser 1959 利用整数规划模式 IntegerProgramming 来处理规模较小的问题 大约10到20个客户点 2 60年代Clarke Wright 1964 提出节省法 SavingMethods 来建立车辆配送路线 以及Christofides Eilon 1969 应用2 Opt及3 Opt方法处理较大规模的问题 大约30到100个客户点 3 70年代很多学者提出两阶段启发式算法 Two PhaseHeuristics 来求解车辆途程问题 约有100到1000个客户点 如GillettandMiller 1977 提出先途程后分群 以及Christofidesetal 提出先分群后途程的方法 P33 4 80年代Fisher Jaikumar 1981 提出数学规划法来处理大约50个客户点的问题 5 90年代很多学者利用宏启发式解法 Meta heuristics 来解决车辆途程问题 如 Robusteetal 1990 Alfaetal 1991 利用模拟退火法 SimulatedAnnealing Sement Taillard 1993 Gendreauetal 1994 Rochat Taillard 1995 以及Kelly 1996 都利用禁制搜寻法 TabooSearch 来求解问题 P34 4 6 2020 P35 节省法 SavingAlgorithm 2 1 节省法 SavingAlgorithm SA 本书中的概念是指Clarke Wright 1964 提出的节省法 基础SA为其他衍生节省法的基础 P36 4 6 2020 P37 节省法的运作过程 a 路线连结 join 4 6 2020 P38 节省法的运作过程 b 并入 attach 4 6 2020 P39 节省法的运作过程 c 合并 merge 4 6 2020 P40 节省法的连接节线原则 1 节线 i j 中的i j点 不能被包含在某一路线中 4 6 2020 P41 节省法的连接节线原则 2 若节线 i j 中的i或j已包含在某一路线时 只要此点不是路线中的中间点即可 4 6 2020 P42 节省法的连接节线原则 2 若节线 i j 中的i或j已包含在某一路线时 只要此点不是路线中的中间点即可 4 6 2020 P43 节省法的连接节线原则 3 若节点i与j分属两条不同路线 只要此两点皆是路线的端点 路线就可以合并 i j 4 6 2020 P44 研究问题 节省量计算 节省量排序 连接原则 限制条件 连结 并入 合并 节省量大于0 输出结果 符合 不符合 Y N 节省法求解流程 4 6 2020 P45 无约束的单车辆配送问题 4 6 2020 P46 首先计算节省量 并从大到小排序 4 6 2020 P47 H C B A G F E D 绘制出参考图如下 4 6 2020 P48 H C B A G F E D Step1 4 6 2020 P49 H C B A G F E D Step2 4 6 2020 P50 H C B A G F E D Step3 4 6 2020 P51 H C B A G F E D Step4 4 6 2020 P52 H C B A G F E D Step5 4 6 2020 P53 H C B A G F E D Step6 4 6 2020 P54 H C B A G F E D Step7 4 6 2020 P55 H C B A G F E D 核对 1 0 6 4 2 3 7 5 4 6 2020 P56 有装载容量限制的配送问题 假设有A B C D E F G七个点 A点为场站 其余六点为需求点 每辆卡车容量为25000 必须以A为起点 用卡车载货满足其余六点的需求 各需求点需求量以及七个点之间的相互距离已知 以节省法求算所需卡车数 运送路线以及卡车行走距离 4 6 2020 P57 4 6 2020 P58 计算节省量并排序如下 4 6 2020 P59 A B C D E F G Step1 7000 10000 17000 小于25000 所以此连结是可行的 17000 4 6 2020 P60 A B C D E F G Step2 第2个是C F F的需求为6000 并入原有的路线使总需求增加为17000 6000 23000 小于25000 所以F可以并入 4 6 2020 P61 A B C D E F G Step2 23000 4 6 2020 P62 A B C D E F G Step3 第4是B F 并入B点使总需求增加为23000 5000 28000 大于25000 所以B不并入 第6是B D B D的连结使总需求达28000 不可行 23000 4 6 2020 P63 A B C D E F G Step4 第7是B G B G的需求为5000 10000 15000 小于25000 所以此连结是可行的 23000 15000 4 6 2020 P64 A B C D E F G Step5 第9是D E D E连结也不可行 因为大于25000 第10是F G 连结F G会将上述两条路线合并 其产生的总需求量超过卡车的容量 所以合并是不可行的 4 6 2020 P65 A B C D E F G Step6 既然各站都被纳入路线内 而这两条路线的合并不可行 故求解终止 至此得到两条路线 A F C D A或相反路线 A E B G A或相反路线 所需卡车2 总距离为 24 9 1 20 6 9 11 9 89 4 6 2020 P66 有装载容量限制不同的配送问题 假设有配送中心P向Bi i 1 2 8 配送 需求bj j 1 2 8 和距离已知 中心拥有车辆为4吨 5 6吨 3 试设计最佳配送方案 4 6 2020 P67 由于B5与B6的需求已经超出单车容量 故安排6T与4T的车各一辆为两点配送 所剩余数参加其他各点调配 4 6 2020 P68 计算节约量并排序 重新修改需求表 4 6 2020 P69 作图辅助求解 1 2 3 4 5 6 7 8 4 6 2020 P70 Step1 1 2 3 4 5 6 7 8 B5应该怎样并入 4 6 2020 P71 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 方案1 方案2 10 4 3 15 32 10 5 3 12 30 4 6 2020 P72 Step2 1 2 3 4 5 6 7 8 3 9 4 3 4 6 2020 P73 Step3 1 2 3 4 5 6 7 8 3 9 4 3 5 4 4 6 2020 P74 Step4 1 2 3 4 5 6 7 8 4 3 5 4 5 7 4 6 2020 P75 Step5 1 2 3 4 5 6 7 8 5 4 5 7 配送方案 1 6T一辆直送B5 载6T2 4T一辆直送B6 载4T3 6T一辆送P 3 5 8 6 P 或相反 载5 4T4 6T一辆送P 2 4 1 P 或相反 载5 7T5 4T一辆直送B7 载2 3T 节省法的衍生 机会节省法 OpportunitySavingAlgorithm OSA 此方法的主要概念是将一个适当的机会成本加入到节省值的计算 在两个序对中 不仅有节省值的关系而且也有节省值的各种选择关系 当所有节省值计算后 每一序对最佳和次佳的选择己被决定 放弃选择最佳节省值而选择次佳节省值时 则增加一些机会成本 同步节省法 SimultaneousSavingAlgorithm SSA 此方法主要是在每一次递归时检视节省矩阵的结构 并且预期矩阵将会重复性的变动 某些节省值必须重新计算 不只是接受最佳节省值的组合 也接受超过某一门坎设定值的节省值组合 机会同步节省法 OpportunitySimultaneousSavingAlgorithm OSSA 以机会节省法为基础的同步节省法 除了加入机会成本外 还加入同步节省法的操作 P76 4 6 2020 P77 节省法之改进 2 1 1 4 6 2020 P78 传统启发式 改良启发式 族群搜寻机制 学习机制 组合启发式 求解TSP问题的启发式分类 4 6 2020 P79 两阶段问题 two phasedmethod 线路构建 TourConstruction 线路改善 TourImprovement 传统启发式代表 4 6 2020 P80 随机选定一点做为起点 并根据路线的距离 成本目标 按照某一法则去搜寻下一个点 直接产生较佳的TSP可行解 常见的方法如 节省法 SavingsMethod 最近邻点法 NearestNeighbor 插入法 InsertionMethod 扫描法 sweepheuristic 贪心法 GreedyAlgorithm 最小扩张树法 MinimalSpanningTreeApproach 等 1 路线构建 TourConstruction 4 6 2020 P81 其假设一开始每辆车均只能服务单一需求点 因此 若有N需求点便有N条路线 接着计算出合并每两个需求点所能节省的值 以合并后不违反所有限制且节省值最大的需求点进行连结 并入或合并三种操作 直到没有正的节省值存在为止 节省法 SavingsMethod 4 6 2020 P82 以站场为起始出发点 计算未排入的需求点的距离成本 找出离仓库最近的需求点纳入途程 接下来再以此需求点为起点 找出离此需求点最近且必须满足时窗 车容量等限制的需求点 依此步骤逐一找寻下一巡回需求点 若找不到符合此三项条件的需求点 则加派一台车 意即建构另一条新路线 重复以上的步骤直到所有的需求点皆排入途程为止 最近邻点法 NearestNeighbor 4 6 2020 P83 插入法的应用相当广泛 主要概念是选取起始点后 计算各需求点插入目前途程的准则 如以节省值大小或距离远近为准则 若不违反限制条件则插入 若找不到需求点可插入或满足车容量限制 则再建构另一条新路线 直到所有需求点皆插入为止 插入法 insertionheuristic 4 6 2020 P84 此方法先将需求点分群 将需求点的地理位置转换为极坐标方式 先任选一需求点为起始点 在车容量限制条件下依顺时针或逆时针方向做区域的分割 然后再针对各分区进行排程 扫描法 sweepheuristic 4 6 2020 P85 求得可行初始解后 为进一步降低总旅行距离 则可利用交换的方式对初始解进行改善 一般的交换改善方法可分为节点 node 交换和节线 arc 交换两种 其中分为路线内或路线间交换 不同路线间的节点或节线交换 可减少车辆使用量 而同一路线内之节点或节线交换 则能够缩短车辆行驶距离 通过上述交换方式 以期能达到总距离最短及车辆使用总量最少的效果 路线交换的方式有很多种 但因需考虑车容量的限制 所以大部份的交换法都不可行 以下是几种常见的路线交换法 其中又以Or opt及2 opt 改善效果较好 2 线路改善 TourImprovement 4 6 2020 P86 1 swap节点交换法 2 节点交换法 3 K opt节线交换法 4 Or opt节线交换法 线路改善 TourImprovement 4 6 2020 P87 选取不同两节点 若符合限制则互相交换位置 可用于路线内与路线间顾客点的交换 属 节点交换的1 1节点交换 1 Swap节点交换法 4 6 2020 P88 1 Swap节点交换法 a 路线内 假设目前途程顺序为0 1 2 3 4 5 0 任选其中两点交换 若选择2 5 则经swap交换后 顺序变为0 1 5 3 4 2 0 4 6 2020 P89 1 Swap节点交换法 b 线路间 假设有两途程之顺序为0 1 2 3 4 5 0及0 6 7 8 9 0 分别于路线中各任选一点交换 如选择3与7 则经swap交换后 顺序分别为0 1 2 7 4 5 0与0 6 3 8 9 0 4 6 2020 P90 以1 0 1 1和1 2节点交换较为常见 其中1 0节点交换被视为是一个转移过程 而将1 1及1 2节点交换称为线路间的节点交换 1 1节点交换实际上就是swap 2 节点交换法 4 6 2020 P91 以1 0节点交换为例 假设目前两途程顺序分别为0 1 2 3 4 5 0与0 6 7 8 9 0 任选一插入点与插入位置 若选定插入点3 插入位置为7 8之间 则经1 0节点交换后 顺序分别为0 1 2 4 5 0与0 6 7 3 8 9 0 2 节点交换法 0 1 2 3 4 5 6 7 8 9 4 6 2020 P92 3 K opt节线交换法 K为欲交换的节线数目 K越大则交换运算次数越多 为降低运算过程复杂难度 因此一般将K设定为2或3 此方法主要是以K条路线取代其它K条路线 并重复此动作直到目标函数无法改善为止 可用于线路内和线路间的交换 当K 2时 用于同一条路线内的称为2 opt 而用于两条线路间的称为2 opt 以K 2为例说明如下 4 6 2020 P93 2 opt节线交换法 a 路线内 假设目前途程顺序为0 1 2 3 4 5 0 任选不相邻两节线交换 若选择节线1 2和4 5 则经2 opt交换后 顺序变为0 1 4 3 2 5 0 4 6 2020 P94 2 opt 节线交换法 b 路线间 假设有两途程之顺序为0 1 2 3 4 5 0与0 6 7 8 9 0 4 6 2020 P95 2 opt 节线交换法 b 路线间 于两途程各任选一节线 若选定节线为3 4 7 8 则经2opt 交换后 顺序分别为0 1 2 3 8 9 0与0 6 7 4 5 0 0 1 2 3 4 5 6 7 8 9 4 6 2020 P96 4 Or opt节线交换法 Or opt节线交换法与K opt相似 是将途程中单点 连续两点或连续三点插入同一途程或其它途程中 可适用于路线内与路线间的节点交换改善方式 路线间称为Or opt 以连续二点为例 4 6 2020 P97 4 Or opt节线交换法 a 路线内 假设有一途程顺序为0 1 2 3 4 5 0 任选一节线 连续两点 插入 若选择节线1 2 插入位置为3和4之间 则经Or opt交换后 顺序变为0 3 1 2 4 5 0 4 6 2020 P98 4 Or opt节线交换法 b 路线间 假设有两途程之顺序为0 1 2 3 4 5 0与0 6 7 8 9 0 任选一节线插入 若选定节线为2 3 插入位置为6 7 则经Or opt 交换后 顺序分别为0 1 4 5 0与0 6 2 3 7 8 9 0 由于Or opt路线间的交换方式会造成途程的节点数增加或减少 因此可用于减少路径数 将节点数少的路线之节点插入至其它途程中 再进行其它路径交换的改善 4 6 2020 P99 节省法的修正 Savings 平行节省法 parallelsavings 循序节省法 sequentialsavings 以总路径距离最短为优先 以车辆使用成本最小为优先 4 6 2020 P100 扫描法 SweepAlgorithm 2 2 4 6 2020 P101 扫描法为一种先分群再构建路径 ClusterFirst RouteSecond 的方法 最早由Gillett与Miller以扫描法求解VRP问题 并正式为其命名 进 扫描法时 先以极坐标的方式表示各个顾客点的位置 再任取一顾客点为起始点 以其角度为0 其后依顺时针或逆时针方向扫描 并依照 同限制条件分区 如车辆的最大载重限制和最大行驶距离等 然后再建构各个子区域的 径 4 6 2020 P102 4 6 2020 P103 最邻近法 NearestAlgorithm 2 3 4 6 2020 P104 最邻近法为一种途程建构法 以场站中心为起点 选取距离场站中心距离成本最小 且未被选取过的顾客加入路径 再以被选取的顾客为起始点 重复以上步骤 直至找 到可满足车辆限制条件的顾客时 路径便回到场站 再由场站重新出发 建构新的路径 直到每一位顾客点皆被选取为止 4 6 2020 P105 插入法 InsertionAlgorithm 2 4 4 6 2020 P106 插入法的应用相当广泛 主要概念是选取起始点后 计算各需求点插入目前途程的准则 如以节省值大小或距离远近为准则 若不违反限制条件则插入 重复步骤至找不到需求点可插入或满足车容量限制 则再建构另一条新路线 4 6 2020 P107 线路优化的现代算法简介 3 4 6 2020 P108 遗传算法 GeneticAlgorithm GA 3 1 4 6 2020 P109 1 遗传算法的源起 遗传算法是美国密西根大学教授JohnHolland于1975年所提出的一套算法 根据达尔文的进化论所发展而成 自然界生物在环境多变的压力下 为求永续生存而进行物种的演化 过程包含复制 Reproduction 交配 Crossover 与突变 Mutation 并在 物竞天择 适者生存 的自然定律下 繁衍出更好的下一代 以适应环境的变化 遗传算法基本精神是以达尔文的进化论为基础 模仿生物界中的自然界演进法则 进行求取最佳解的搜寻技术 简单来说 遗传算法是通过模仿自然界的演进法则 应用计算机仿真的方式来计算人为染色体的变化 进而改善过去算法当中难以解决的问题 4 6 2020 P110 在基因算法的演算过程中 一开始必须对将问题里的所有变量编成二进制字符 或者是其它形式如文字 数字等 这些字符就如同生物中的遗传基因 Gene 接着将这些字符组合成一条字符串 String 而一条字符串就代表着问题的一组解 这些字符串就像是自然界当中 各个物种的染色体 有其各不同的组合 而不同物种的组合 即多条字符串所形成的集合 则统称为族群 Community 接着依据族群所必须面对的生态环境 架构出物种对环境适应能力的评估方法 也就是将问题的目标函数 限制方程 转化成适应度函数 FitnessFunction 利用适应度函数来评估各物种的适应能力 决定哪些物种该留下来 而哪些物种必须被淘汰 这就如同生物界的 物竞天择 适者生存 的法则 由于遗传算法最主要的精神为演化 Evolution 及筛选 Selection 因此在适应度函数定义出来之后 就将染色体经由演算过程中主要的三个基本运算子 复制 Reproduction 交配 Crossover 及突变 Mutation 作重复的演算 进而产生新的染色体 如此就能够达到演化的目的 4 6 2020 P111 遗传算法应用到组合最佳化的问题时 每条染色体可以视为问题搜寻过程中的一个暂行解 染色体里的基因则为每个暂时解中的决策变量 而每个暂时解必须符合问题的限制条件才算是可行解 FeasibleSolution 才能存活下来 其是否能成为繁衍下一代的种子 则需视其环境适应能力 Fitness 而定 在染色体反复的演化过程中 犹如在问题的可行区域中做多点的空间搜寻 4 6 2020 P112 2 基因表达 RepresentationaSolution 遗传算法以染色体代表暂时解 而染色体通常都是以二进制的编码方式或是以字符串 String 的方式来表示 以字符串来表示时 字符串里的参数是影响目标函式值大小的决策变数 其可以是包含同一类型决策变量的值简单字符串或是包含不同类型决策变量的值复合字符串 这与问题的复杂度有关 当所欲求解的问题需同时最佳化多种目标时 其字符串就可能表示成复合的数据字符串 在订单分配与运送的问题上 可能一方面要决定订单要如何分配给车辆 另一方面要决定车辆如何配送这些货物 以使车辆的装载率提高 配送车时缩短 像这类的问题 其暂时解可能要同时包含订单与车辆的信息 则字符串里的参数就属于多种的复合数据 其就需要特殊的交配 突变运算子 而不能使用一般的运算子 而需要间接表达 IndirectRepresentation 来表示染色体 4 6 2020 P113 3 初始族群产生 Initialization GA初始必须产生一母群体开始演化 而这一群母群体 即是此一问题的解在进行编码后所形式的 每一个解即是一条染色体 每一个解中有许多的决策变量 这些决策变量就是染色体中的基因 一般而言 在这一部份的操作 是对每一个基因给予0 1的随机值 如图所示 随即完成此一随机母群体 也就是在解空间中产生多个初始解 采用随机的概念 是为了在这解空间上 能平均产生任意解 而随机的概念亦有缺点 大量的母群体 增加了求解难度 4 6 2020 P114 一条染色体achromosome agene 4 6 2020 P115 如 以顾客编号代表染色体基因 而编号出现的先后顺序 即代表顾客在该路线中的配送顺序 4 6 2020 P116 如 以车辆编号代表染色体基因 而编号出现的相对应位置 即为该车辆配送的顾客点 4 6 2020 P117 4 适应值 FitnessValue 适合度函数用以评估原始问题的目标函数 透过此函数的运算 计算每一染色体的适合度值 而此适合度值即可提供判断染色体优劣的依据 适合度值较佳者 其被选取以产生下一代的机会较高 而适合度较差的 则越容易遭到淘汰 以此方式进行优生演化 4 6 2020 P118 5 筛选 Selection 如何利用既有的解来产生新解 是非常重要的一部份 而选择的新解 对寻解的效率而言 占有极为重要的地位 自然界中 如果适应能力越强的物种所繁衍的子代 其适应能力大部份能继承母代 亦成为适应值较佳的物种 所以在筛选的过程 操作上会掌握一个大原则 越优良的解所产生之新解 有较高机率质量较佳 而这只是一个筛选方向 并非绝对 因为质量较差的解产生出的新解质量亦有可能会变佳 筛选机制最常用的方法为轮盘法 Fitness ProportionateSelection 将各目标值与惩罚值合并为适应值 按照适应值优劣给予权重 此过程的功能在于仿真自然界 适者生存 的法则 方式在于从染色体群中 利用适合度值的评估结果 将适应程度较好挑选并复制至交配盘中 以准备演化产生新的染色体子代 4 6 2020 P119 6 交配 Crossover 此交配机制扮演着产生新解 得以让演化有着不同的解继续演化下去的角色 而交配机制的特色 有上一母代的特色 又有新子代的不同点 此演化过程通过交配率以进行基因的重组 以产生新的染色体 其方式是从染色体群中随机选取两个母代染色体 并随机产生一个或多个交配点 以使两父代的染色体基因互换以产生一新的染色体对 交配率依其操作方式的不同而有两种定义 1 决定族群中至少应进行交配的染色体 2 决定是否对预先选好的染色体对进行交配演化 即母体进行交配的机率 所以较高的交配率将可提高染色体进行交配的机率 以产生新基因组合的染色体 但原本适应值好的染色体却有可能因此受到破坏 而演化成适应值较劣的染色体 而失去优生演化的效果 较低的交配率则会影响母体演化的速度 所以一般交配率大概为0 1 0 5 4 6 2020 P120 7 突变 Mutation 此过程的目的在于利用突变率以避免解过早收敛 而陷于局部的最佳解 并由此开发新的搜寻区 其方式为借着已控制的突变率 再随机地选取符合该个数的突变点 以进行基因的突变过程 而突变率依其操作方式的不同而有两种定义 1 决定染色体上的基因是否发生突变 即染色体上基因突变的机率 2 决定母体染色体中发生突变的基因数 提高突变率有助于将染色体导入其它的基因结构 以进行其它可行解区域的搜寻 但过高的突变率将使遗传算法变成随机搜寻的求解方法 一般突变率为0 001 0 05 4 6 2020 P121 8 精英 Elitism 为了确保每一世代的演化 所寻找出的解不比上一世代质量差 这部分扮演了一个重要的角色 操作上 将保留这次世代在演化过程中 解质量最佳的前几名 并保证给予下一世代的交配权 同时将交配和突变过程中 经过适应值计算后的各子代 与未经交配和突变的各母代交配 回交 筛选适合继续演化的母群体 继续演化 这一机制的特点是在整个操作上 基本上只允许进化 精英主义的设定好坏 将影响寻解过程中 收敛的快慢 4 6 2020 P122 通过遗传算法的上述9个部分 将可得到新的染色体子代 且此代中的染色体适合度值将优于父代 持续此演化过程 将可在未来的新子代中搜寻到适合度值更高的染色体 也就是可求出较佳的可行解 4 6 2020 P123 世代G G 0 初始族群产生 筛选 设立适应函数 交配 精英 突变 G setup 演化终止 Y N 4 6 2020 P124 群蚁最佳化算法 AntColonyOptimization ACO 5 2 4 6 2020 P125 1 真实蚂蚁行为 群蚁最佳化算法最早是由Dorigo Colorni Maniezzo于1996年提出 其灵感源于观察蚂蚁的觅食行为而来 当蚂蚁离开巢穴去寻找食物时 在爬行时会分泌一种名叫费洛蒙 Pheromone 的分泌物 蚂蚁会依照费洛蒙的强度来选择其途程路径 在最短的时间内 找到巢穴与食物间最短路径将食物送回巢穴 4 6 2020 P126 N nest F food A B C D d 1 d 1 d 2 d 2 T 0 4 6 2020 P127 N nest F food T 1 ants 30 ants 15 ants 15 4 6 2020 P128 N nest F food T 2 ants 30 ants 20 ants 10 4 6 2020 P129 2 蚂蚁算法 蚁群算法本质上仍是一种随机搜索算法 它通过对候选解组成的群体的进化来寻求最优解 算法由许多蚂蚁共同完成 每只蚂蚁在候选解的空间中独立地搜索解 并在所寻得的解上留下一定的费洛蒙 Pheromone 蚂蚁倾向于朝着该物质浓度高的方向移动 因此 由大量蚂蚁组成的蚁群的集体行为便表现出来一种信息正反馈现象 某一路径上走过的蚂蚁越多 后面的蚂蚁选择该路径的概率就越大 随着算法的推进 较优解上的信息素将逐渐趋于收敛 4 6 2020 P130 3 蚁群算法在TSP中的应用 1 初始化各个城市 点 之间的道路 边 即将所有边的费洛蒙水平赋一个初始值 2 将若干只蚂蚁随机地放在不同的城市中 3 每只蚂蚁根据各条边的费洛蒙 Pheromone 水平和距离 选择下一个城市 4 所有蚂蚁完成周游后更新费洛蒙 Pheromone 水平 所有边的费洛蒙 Pheromone 水平按照一定的比例减少 挥发性 蚂蚁经过次数多的边 其费洛蒙 Pheromone 水平增加较多 分泌激素 判断是否产生新的最优路线 如果是 则记录到全局变量中 5 返回步骤 2 循环 直至满足退出条件 4 6 2020 P131 模拟退火法 SimulatedAnnealing SA 3 3 P131 4 6 2020 P132 对于TSP等路线规划的最佳化组合问题 在现有随机搜寻法中 模拟退火法易于问题求解与近似解实现 虽然一般的经验搜寻决策方式可以满足时间的需求 但此类方法不仅缺乏数学理论的依据 而且搜寻到的解 具有较高机率陷入局部最佳解而中止 模拟退火法已被验证可应用于最佳化组合问题 且可获得整体性的近似解 模拟退火法的起源 P132 4 6 2020 P133 退火是一种金属热处理工艺 是将金属缓慢加热到一定温度 保持足够时间 然后以适宜速度冷却 退火的目的是降低硬度 改善切削加工性 消除残余应力 稳定尺寸 减少变形与裂纹倾向 细化晶粒 调整组织 消除组织缺陷 P133 4 6 2020 P134 模拟退火算法是从统计力学 StatisticalMechanics 的观念发展出来的 仿真退火法之所以能应用于路径优化问题上 主要是在物理现象中的金属退火过程 与一般求解最佳化问题的过程极为相似 金属在进行退火程序处理 AnnealingProcess 时 通常需先将其加热至高温 使其金属原子间的金属键变弱 直到粒子能自由活动 随着温度逐渐降低金属间的位能也会随之减少 当温度逐渐下降 高温的金属通过粒子的自由活动而达到低能量状态 形成低能态 LowEnergyState 并且最后逐渐稳定 形成具有结晶状态的基态 Groundstate 此时称该金属已达到凝结 Freeze 模拟退火法与路径的关系 P134 4 6 2020 P135 若退火温度下降速率 TemperatureDecreasingRate 足够缓慢 则此金属会形成最低能量的状态 仿真物质退火形成结晶体的程序包含两个步骤 1 首先将物质加温至高温 使粒子能自由活动 呈现无排序状态 2 再将金属从高温缓缓降温 直到物质粒子的排序呈紧密状态 呈现低能量稳定的结晶体 P135 4 6 2020 P136 模拟退火就是模拟上述的退火过程 最佳化问题中可行解域 FeasibleSolutionRegion 中的组合就如金属的物质状态 问题的目标函数如金属晶体能量函数 在可行解域内找出所对应目标值最小的解的过程 如同退火过程中金属粒子重新移动 重新排列组合逐渐往能量最低的状态形成 P136 P137 模拟退火法是一种机率攀登搜寻算法 ProbabilityHill ClimbingSearchAlgorithms 主要结合了两种方法 1 最陡坡降法 MethodofSteepestDescent 即梯度搜寻法 GradientSearch 2 随机过程的方式搜寻目标函数 ObjectFunction 的整体最小化 GlobalMinimum 的方法 它以随机的方式产生设计组合变化 并以目标函数值来仿真能量函数 EnergyFunction 使其设计组合在搜寻空间中朝着目标函数值较低的状态移动 借助随机过程 使其设计组合能在某些条件下 具有接受能往目标值较高处移动的机会 此随机过程使得模拟退火法可以逃出局部最优的界限 成为全域搜寻的最优化过程 模拟退火法的关键是 梯度搜寻法以及随机过程中能跳脱局部解的波兹曼分布 BoltzmannDistribution 模拟退火法的特点 P138 模拟退火算法是利用蒙特卡洛模拟 MonteCarloSimulation 而延伸的一种启发式随机搜寻算法 是将组合路径优化问题模拟为金属退火过程中 从高温缓降温至低温时低能量状态的情况 藉此过程寻求近似最佳解 模拟退火算法的基本概念由Metropolis 1953 首次提出 Kirkpatricketal将它首次运用于求解组合最佳化问题 1983 至今已被应用于许多不同领域 物流领域中 Goldenetal 于1983应用模拟退火法求解TSP问题和P median网络区位问题 Bonimietal 对Golden的方法做了改进 模拟退火法采用梯度搜寻法及波兹曼机率分布接受机率条件 在不断的退火迭代过程中 寻求近似最佳解 模拟退火法的流程 P139 迭代过程 以最初的设计组合状态为S0当作金属物理系统的一能量状态 而E S0 为一设计组合状态的目标值 相当于物理系统中的能量值 并以控制参数T模拟退火温度 在每一温度T 以Metropolis提出的抽样法 经由可行解域内随机扰动 得到一组新的设计组合状态S1 计算前后目标值差 E E S1 E S0 若 E 0 则表示新设计组合状态S1好过S0 系统即予接受S1并将系统状态S0置换将系统进化为新状态 P140 迭代过程 若 E 0 表示S1比S0差 则以波兹曼分布接受条件exp E KT 来做判断是否接受S1为新的系统状态 计算出能量差的exp E KT 概率 并且从均匀分配U 0 1 中随机抽出一数值X作比较 若exp E KT X 则接受新的设计组合为一新的系统状态 若exp E KT X 则舍弃此一组合 保留扰动前之原系统状态 P141 4 6 2020 P142 人工神经网络 ArtificialNeuralNetwork ANN 3 4 4 6 2020 P143 1943年心理学家McCulloch与数学家Pitts 1943 两位学者依据人类脑神经组织的特性提出神经细胞数学模型 MP模型 的理论架构 由此 人工智能的发展领域就明显的区分从语言学着手的人工智能与仿真生物神经系统的人工神经网络两大方向 在1949年 Hebb 1949 提出了类神经网络基本学习法则 HebbLearningRules 之后 更为往后仿真生物神经系统的人工神经网络的研究奠定了基础 4 6 2020 P144 1 神经网络的定义 神经网络是一种仿真生物神经对于外界讯号所作的储存反应 学习 等一系列动作的网络 它的观念是来自于观察单一生物细胞获得的灵感 一个神经细胞相当于一个处理单元 突触则类似输入端 输入端的信息经过加总后 通过一转换函数输出到下一层级 当讯号要进入下一层级之前 必须乘以权重才能进入下一个处理单元 这个权重就是所谓的神经腱强度 神经网络是由许多神经元处理单元所组成的 通常一群性质相同的处理单元会形成一个层 而层与层的连接可以是完全连接或是随机连接 输入部分称为输入层 中间部分通常有一到三层的隐藏层 层数视网络性质而定 最后在输出的部分称为输出层 4 6 2020 P145 h1 h2 h3 h4 x1 x2 x3 y1 y2 y3 输入层 隐藏层 输出层 4 6 2020 P146 如同生物的神经网络 并非所有神经元每次都一样地工作 如视 听 摸 想不同的事件 输入不同 各神经元参与工作的程度不同 当有声音时 处理声音的听觉神经元就要全力工作 视觉 触觉神经元基本不工作 主管思维的神经元部分参与工作 阅读时 听觉神经元基本不工作 在人工神经网络中以加权值来控制结点参与工作的程度 正权值相当于神经元突触受到刺激而兴奋 负权值相当于受到抑制而使神经元麻痹直到完全不工作 4 6 2020 P147 如果通过一个样板问题 教会 人工神经网络处理这个问题 即通过 学习 而使各结点的加权值得到肯定 那么 这一类的问题它都可以解 好的学习算法会使它不断积累知识 根据不同的问题自动调整一组加权值 使它具有良好的自适应性 此外 它本来就是一部分结点参与工作 当某结点出故障时 它就让功能相近的其它结点顶替有故障结点参与本题工作 使系统不致中断 所以 它有很强的容错能力 4 6 2020 P148 outputunits inputunits W2 W1 Outputs Y T X1 X2 X3 W3 weights