启发式算法作业报告

作者: 陨落的小白 | 来源:发表于2020-05-02 22:46 被阅读0次

启发式算法作业报告
博客园转载
A* 搜索算法
启发式算法
(3.7学堂在线python学习笔记)
八数码问题的A*算法求解
2019-11-12
算法2
遗传算法详解
A搜索算法（python）之八数码问题

问题描述

我们小组选择的问题是TOPTW问题，即the Team Orienteering Problem with Time Windows，中文名称可以译为“带有时间窗的团队定向越野问题”，不过在查找及复现论文的过程中，我们认为这本质就是一个“带有时间窗的车辆路径问题”，即VRPTW。

问题描述如下：地图上存在许多的顾客点，每个顾客点处于可被服务状态的时间是有限的，即存在顾客点可被服务的开始时间OpenTime与结束时间CloseTime，服务每个顾客都需要持续一定的时间ServiceTime，如果一个顾客点被成功服务了，则可以获得一定的收益profit，并且每个顾客最多只能被服务一次；地图上同时存在一个仓库Depot，仓库派出一定数量的服务车，车子从仓库出发，途径各个顾客点服务顾客获得收益，仓库也存在开启时间和关闭时间，因此所有的车子需要在开启时间出发，在关闭时间之前回到仓库；此问题的目标是，给定一定数量的车子，如何规划每辆车子的服务路径，使得所获得的总收益最大。

偏数学描述：给定无向图 $G=(V,A)$ ， $V= \{0,1,2,...,n\}$ 表示地图上的 $n$ 个点， $A= \{(i,j):i\neq j\in V\}$ 代表每两个点之间的边，从点 $i$ 到点 $j$ 之间的时间 $t_{ij}$ 等于两个点之间的距离 $d_{ij}$ ， $0$ 号点代表仓库，仓库的时间窗是 $[O_0,C_0]$ ，其余点 $i=1,...,n$ 代表顾客，每个顾客点有一个收益 $p_i$ ，服务时间 $T_i$ ，和一个时间窗 $[O_i,C_i]$ ，如果车子的服务时间在顾客的时间窗之内则服务成功，如果车子在顾客时间窗未开始之前到达则需要等待，服务成功可获得收益，TOPTW的目标是在车辆有限的情况下通过规划路径获得最大的收益。

算法描述

概括

我们复现的论文使用了Iterative Three-Component Heuristic(I3CH)算法，这个算法综合了三种不同的算法，邻域搜索算法，模拟退火算法以及给定解空间条件下的精确算法，结合他们各自的优势，以期获得更好的解。

The structure of the three-component heuristic

Solution representation

给定可使用的车子数量 $m$ ，该论文使用 $m+1$ 个有序列表对该问题的解进行表示，其中一个列表 $u$ 代表没有被任何一辆车子服务过的顾客点，其余 $m$ 个列表 $r_i,i=1,2,...m$ 代表 $m$ 辆车的顾客点访问顺序（路径），每条路径的表头和表尾都是0，代表仓库，其余数字代表顾客点，按从左往右的顺序在地图上依次访问。

Example of a solution representation
如上图所示，有两辆车的情况下，为未服务的顾客点，代表第一辆车的路径，代表第二辆车的路径，不过在我们的算法实现中，为了操作方便，我们将每个车辆路径列表表头表尾的都删去了，本质上没有变化。

public class route {
    public ArrayList<Integer> tour;
    public int profit;
    private int apr;
    private boolean used;
    public long time;
   }

上述是代码中route的部分，route即每辆车的路径，ArrayList存储车辆路径，profit代表此路径的利润，apr代表路径的权重，这在精确算法部分会用到，used代表此路径是否在精确算法的最终结果中被使用，time代表此路径花费的时间。

 public boolean check(Instance inst) {
        long start = inst.openTime(0);
        long end = inst.closeTime(0);
        int cur = 0;
        int next;
        for (int i = 0; i < tour.size(); i++) {
            next = tour.get(i);
            long ss = start + inst.dist(cur, next);
            if (ss < inst.openTime(next))
                start = inst.openTime(next) + inst.serviceTime(next);
            else if (ss >= inst.openTime(next) && ss <= inst.closeTime(next))
                start = ss + inst.serviceTime(next);
            else {
                return false;
            }
            cur = next;
        }
        if (start + inst.dist(cur, 0) > end){
            return false;
        }
        return true;
    }

此部分用来检测该路径是否可行。而Solution则是以route为元素的数组。同时带有收益，每个顾客点的平均收益，总时间，可能获得的最大收益这些属性。

public class Solution {
    public int profit;
    public route[] Sol;
    private double ave_pro;
    private long sumTime;
    public int maxPro;
}

The Neighborhood Operator

本论文使用了八个邻域算子，分别是 $eliminator$ ， $0-relocate$ ， $1-relocate$ ， $2-relocate$ ， $0-exchange$ ， $1-exchange$ ， $2-exchange$ ， $2-opt$ ，接下来重点描述一下 $eliminator$ 算子。

$eliminator$ 首先随机地从每条路径中移除一些顾客节点，如果原路径中没有任何节点则不进行移除操作，之后从路径 $u$ ，即未被服务的顾客节点中选择头节点，将其插入路径 $r_i$ 中第一个可以插入的位置，即插入之后路径是一个可行路径。如果所有的位置都无法插入，则将该节点置于 $u$ 的末尾，继续选择下一个头节点进行上述操作，直至 $u$ 中的每一个节点都无法再插入任何位置。此时的Solution则被定义成一个complete Solution，即在不改变路径中顾客顺序的情况下， $u$ 中的所有顾客点都无法被插入到路径中。

这个算子的设计点之一在于，如何从路径中移除顾客点更有效率。论文采用的设计是计算出当前解中每个顾客结点给予的平均收益值，如果某个顾客点的收益大于平均收益，则以较小的概率移除，否则以较大的概率移除，这样子可以让留下来的顾客节点大部分具有更大的收益。

其余算子由于课堂上都进行过详细的讲述，这里不再重点展开，简单来说，其余六个算子中， $1-relocate$ ， $2-relocate$ ， $1-exchange$ ， $2-exchange$ ， $2-opt$ 在受访问顾客点不变的情况下，通过改变顾客点的访问顺序，降低路径所需的总时间，以期可以插入更多的未服务顾客节点；而 $0-relocate$ ， $0-exchange$ 可以从 $u$ 中选择节点放置在路径中或者与路径的某个节点互换，以期增大路径的收益。

介绍基础算子之后，本论文通过一个Post-Processing的操作对后七个常用算子进行了聚合，即循环使用 $2-relocate$ ， $2-opt$ ， $2-exchange$ ， $1-relocate$ ， $1-exchange$ ， $0-relocate$ ， $0-exchange$ 对某个solution进行处理，直至此solution无法得到有效的改进。

Illustration of operators in the post-processing procedure

Local Search & Simulated Annealing

Local Search和Simulated Annealing是I3CH算法中的前两个的部分，它们也都是被广泛使用的算法，在I3CH中，使用它们的目的是为了得到一个较好的解以及在探索过程中收集所有可行的 $route$ ，以便在精确算法中对它们进行组合。

Local Search

LS算法较为基础，在本论文中，对于一个Solution $X$ ，我们通过 $eliminator$ 算子生成它的 $N$ 个邻域解，如果邻域解没有超过 $X$ 的，则使用最后一次探索过程中的解代替 $X$ ，反之，用邻域中最优的解替代 $X$ ；用 $X_{LS}$ 记录迭代过程中得到的最优解，如果一次迭代过程后 $X$ 优于 $X_{LS}$ ，则用 $X$ 更新 $X_{LS}$ ；不断重复上述过程，直至连续没有得到优化的迭代次数超出了设定值 $I_{ls\_no\_impr}$ ，至此，论文通过LS对解 $X$ 进行了优化，并得到了许多用于组合的可行路径。在实现过程中，考虑到单独一个 $eliminator$ 算子实际探索邻域的范围可能较小，我们将Post-Processing操作也用在了邻域的探索中。

Simulated Annealing

SA是通过对物理中的退火现象进行观察而得来的，其本质是在一定概率下接受一个相对不那么好的邻域解，借此跳出局部最优。本论文的SA需要用到的参数有初始温度 $T_o$ ，降温系数 $\alpha$ ，退火温度 $T$ ，以及最大无优化次数 $I_{sa\_no\_impr}$ ；对于某个Solution $Y$ ，记 $Y_{SA}$ 为SA过程中得到的最优解，对于 $Y$ 应用 $eliminator$ 算子得到解 $Y^{'}$ ，如果 $Y^{'}$ 的收益优于 $Y$ ，则使用 $Y^{'}$ 更新 $Y$ 继续进行退火的过程，如果 $Y^{'}$ 的收益比 $Y$ 还要低，则以 $P_{sa}=exp\{\frac{1}{T}\frac{Y^{'}-Y}{Y_{SA}}\}$ 的概率接受 $Y^{'}$ ，即使用 $Y^{'}$ 更新 $Y$ 继续进行退火；为了与LS相适应，论文将LS中的 $N$ 作为一次迭代过程中退火的次数，每一次退火之后都使用 $T=\alpha *T$ 对退火温度进行更新，降低接受较差解的概率；不断重复上述过程，直至连续没有得到优化的迭代次数超出了设定值 $I_{sa\_no\_impr}$ ；至此，论文通过SA对解进行了另一种方式的优化，同时生成了许多可行的路径。

Route Recombination

RR算法是一种精确算法，理论上说，如果可以找出所有可行的车辆路径，对其进行组合，则一定可以找到TOPTW的最优解，但实际操作中过于复杂，因此不太实用，但其思想仍然可以借鉴。本论文即是通过两个有效的算法，对所有可行的车辆路径的范围进行缩小，只对算法实施过程中生成的车辆路径进行组合，以期得到更好的解。同时，为了说明这一操作的有效性，论文提出了两个定理：
第一：对于一个求解TOPTW的算法，对其在求解过程中得到的所有可行车辆路径进行符合条件的组合，得到的“最优组合解”不比原算法得出的最优解更差。

第二：对于两个不同的求解TOPTW的算法，对它们在求解过程中得到的所有可行车辆路径进行符合条件的组合，得到的“最优组合解”不比它们任何一个得到的最优解更差。
根据这两个定理，我们可以得出，如果待组合的路径包含上述两个算法过程中所有生成的可行路径，则I3CH算法得出的最优解，一定可以通过组合得出来。

尽管通过两个算法实施过程中得出的可行路径数量相对于所有的可行数量大大降低了，但依然是个较大的数字，我们只能存储有限数量的可行路径，所以论文采用了一定的策略进行优化。首先，给每一条路径都增加一个权重，即为上文提到的 $apr$ ，我们使用优先队列对探索出的可行路径进行存储，记为 $POOL$ ，权重小的路径“优先级”较高，路径刚进入 $POOL$ 时，权重设为0，RR算法对 $POOL$ 中的路径进行组合时，最终结果中，被选中的路径的 $apr$ 增加100，其余未被选中的路径的 $apr$ 减少1， $apr$ 即代表一条可行路径的“优秀程度”,越优秀的路径，被选中的可能性更大，其权重也更高； $POOL$ 存在一个容量上限 $S_{pool}$ ，当优先队列中存储的路径数量已经达到 $S_{pool}$ 时，将优先级高即权重最小的路径从队列中移除，再添加新的路径。通过上述策略，可以在有限容量的情况下，对路径进行遴选以保留优秀的路径。

对于 $POOL$ 之内的路径的组合，采用了精确算法即整数规划的算法，论文是通过调用cplex对整数规划问题进行求解，建模如下： $POOL=\{r_1,r_2,...,r_{S_{pool}}\}$ 代表路径的集合， $j\in V\setminus \{0\}$ ， $k\in \{1,2,...,S_{pool}\}$ ， $a_{jk}=1$ 代表顾客 $j$ 在路径 $k$ 中被访问了，否则 $a_{jk}=0$ ，第 $k$ 条路径 $r_k$ 的收益由 $q_k=\sum_{j\in V\setminus \{0\}}{p_ja_{jk}}$ 表示。定义决策变量 $x_k=1$ 表示路径 $r_k$ 在最终组合里被选中，否则 $x_k=0$ ，目标函数和约束条件如下：
$Maximize \ \ \ \ \ \ \sum_{k=1}^{S_{pool}}{q_kx_k} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$
$Subject \ \ to \ \ \ \ \ \ \sum_{k=1}^{S_{pool}}{a_{jk}x_k} \leq 1\ \ \ \ \ \ \ \ \ \ (2)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \sum_{k=1}^{S_{pool}}{x_k} \leq m \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_k \in \{0,1\} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$
其中 $(1)$ 式表达了目标函数即备选路径的总收益最大化， $(2)$ 式表明每个顾客最多只能出现在一条路径中， $(3)$ 式表明选择的路径数量不能超过车的数量。通过对以上整数规划问题的求解，我们可以得出当前 $POOL$ 中可以产生的最优的组合。

Construction

一个优秀的启发式算法有四个组主要的部分，Solution representation，Construction ， Solution neighborhood，Escaping local optima，其中Solution representation上文已经提到，Solution neighborhood则由那八个算子进行生成，Escaping local optima可以通过SA算法中对于较差解的接受准则来实现，因此接下来简要分析初始解的构造部分。

在论文中，算法的开始需要构造初始解，首先，将 $eliminator$ 算子作用于一个所有的 $r_i$ 都为空，而 $u$ 包含了所有顾客点的Solution A，因为 $r_i$ 都为空，所以无法从中移除任何顾客点，而直接从 $u$ 中选取顾客点向 $r_i$ 中插入，直至得到一个complete solution A，之后对其进行Post-Processing操作，得到一个改进后的A；对上述过程重复 $3*n$ 次，从中选择最优的solution作为初始解，进行接下来的操作。同样地，在初始解构造过程中，将探索得到的可行 $route$ 加入到 $POOL$ 中去，以便于第一次组合。

算法框架

有了上述的部分，我们可以对I3CH的总体算法框架进行描述。
首先，设定最大迭代次数 $I_{max}$ ，构造初始解 $A$ ，以及路径集合 $POOL$ ；之后，对于 $POOL$ 中的 $route$ 进行组合，得到解 $Z_{RR}$ ，对 $A$ 应用LS算法，得到解 $X_{LS}$ ，对 $A$ 应用SA算法，得到解 $Y_{SA}$ ，令解 $B$ 复制 $\{A,Z_{RR},X_{LS},Y_{SA}\}$ 中总收益最大的解，用 $B$ 更新 $A$ ；不断重复上述过程直至迭代次数超过 $I_{max}$ ，如果某次迭代过后得到的解 $A$ 中的 $route$ 已经覆盖了所有的顾客点，则跳出循环。

总结

以上便是对该论文提出的I3CH算法的简要描述，在复现过程中，我们基本上原封不动地遵从论文的设定进行复现，只有几个小的地方与原论文有所差异，基本不够成影响。在对该算法的学习过程中，我们认为该算法是一种朴实且有效的算法，其思想并不复杂。算法应用了几种十分常用的算子，其中对于 $eliminator$ 算子根据问题做出了一定的优化；采用了两种常用的启发式算法，LS和SA，对初始解进行优化，其创新之处在于合理地运用了Set Packing的方法，通过只对算子操作过程中出现的可行 $route$ 进行收集，同时通过优化策略保留优秀 $route$ ，大大降低了Set Packing的实施范围，提高了解的求解效率以及质量。此算法同时具有很好的拓展性，譬如可以设计出更多的算子收集可行 $route$ ，扩大可能收集到的 $route$ 的范围，提出更多的遴选策略保留优秀 $route$ ，以达到进一步改进解的质量的目的。

结果比较

虽然此算法分析起来较为简单，但由于具体实现起来涉及到各种细节，比如算子的进一步优化，算法框架的具体形式，参数的选择，因此最后的结果与论文的结果仍有一定的差距

我们对算例pr11-pr20进行了测试，令，可以发现，除了pr11这个较小规模算例以较长的时间达到了最优解之外，在运行时间差不多的情况下，复现结果比论文结果要低1%~8%，这说明我们复现的代码没有很好的实现该算法的优越性。我们认为可能有以下几个原因：

1.在对算子的复现过程中，由于这些算例问题规模较小，因此对于 $0-relocate$ ， $1-relocate$ ， $2-relocate$ ， $0-exchange$ ， $1-exchange$ ， $2-exchange$ ， $2-opt$ 这些改变顾客点访问顺序的结果使用了一定程度上遍历穷举的方式进行实现，但在具体的实现上，譬如四条路径之间的 $2-opt$ 如何更大程度的穷举出来，出现了问题，其他的算子在实现过程中，也有些许的问题，因此在算子对解进行优化时，很可能难以得出一个接近论文最优解的解，而无论是LS还是SA的操作，甚至是RR算法对 $route$ 进行组合，最根本的就是这些算子，因此整体解的质量弱于论文的解；同时，对算子进行的优化较少，这也是一个不足之处。

2.参数调整，由于我们实现出的代码与论文的代码存在许多细节差异，因此我们无法直接按照论文里的最优参数进行使用，需要尝试出一个较好的参数，并且有些地方我们更改了参数的使用方式，譬如 $eliminator$ 算子部分，我们没有使用论文中的 $p_h$ ，“p_l”这两个不同的概率对不同收益值的顾客点进行移除，而只使用了 $p_h$ ，因此也可能影响到解的质量，参数方面依然有很大的调整空间。