下载掌阅APP，畅读海量书库
立即打开
爬山算法作为一种启发式算法，其性能主要体现在两个方面，一是算法的寻优效果，即算法所求得的解的质量；二是算法的计算效率，即算法能否在较短的计算时间得到问题的最优解或近似最优解。爬山算法的性能不仅与采用的算法策略有关，而且也受到其运行参数取值的影响。
在2.4节所确定的无时限单向配送车辆优化调度问题的爬山算法中，采用了下述算法策略：解的表示方法采用客户直接排列的表示方法；采用公式（2.12）对解进行评价；采用两交换法实施邻域操作；采用迭代指定步数的终止准则。但根据2.3节所设计的无时限单向配送车辆优化调度问题的爬山算法，其解的表示方法还有客户和虚拟配送中心共同排列的表示方法以及车辆和客户对应排列的表示方法；邻域操作方法还有三交换法、逆转法和插入法等。下面将通过实验计算研究解的表示方法、邻域操作方法及迭代步数等算法策略和运行参数对爬山算法性能的影响。
如前所述，用爬山算法求解无时限单向配送车辆优化调度问题时，解的表示方法主要有三种。在这三种解的表示方法中，车辆和客户对应排列表示方法占用的计算机存储量最大，其次是客户和虚拟配送中心共同排列的表示方法，最少的是客户直接排列的表示方法。解所占用的计算机存储量越大，则在算法迭代过程中的数据处理量越大，算法的计算效率也就越低。据此可以推断出不同解的表示方法下爬山算法的计算效率，即效率最低的是车辆和客户对应排列的表示方法，效率最高的是客户直接排列的表示方法。
从算法的寻优效果看，采用车辆和客户对应排列的解的表示方法时，其确定配送路径方案的方法及对解进行评价的方法与客户和虚拟配送中心共同排列的表示方法大体一致，则采用上述两种解的表示方法时，爬山算法的寻优效果也应基本一致。
为了分析解的表示方法对爬山算法寻优结果的影响，设计了无时限单向配送车辆优化调度问题的基于客户和虚拟配送中心共同排列的解的表示方法的爬山算法，并编制了相应的计算机程序。在该爬山算法中，由于解的表示方法发生了变化，则解的评价方法也应相应变化，为了便于比较，邻域操作仍采用两交换法。作者利用上述爬山算法对实例2.2进行了实验计算，计算时仍采用了以下运行参数：迭代次数取2000，对不可行路径的惩罚权重取300km。利用这种爬山算法对实例2.2随机求解10次，得到的平均计算结果见表2.7。为了便于比较，将2.5节中采用客户直接排列的解的表示方法时，实例2.2 的计算结果也列在表2.7中。
表2.7 求解实例2.2时解的表示方法对爬山算法性能的影响分析表
由表2.7可以看出：无论是从解的平均值看，还是从得到可行解的次数看，用客户直接排列表示方法所求得的计算结果均明显优于客户与虚拟配送中心共同排列的表示方法。从计算效率看，采用客户直接排列表示方法时算法的计算时间较短，收敛速度较快，计算效率较高，这与前面的分析结果是一致的。
由以上分析和计算可以看出：用爬山算法求解无时限单向配送车辆优化调度问题时，在三种解的表示方法中，采用客户直接排列的表示方法不仅占用的计算机存储量最小，算法的计算效率最高，而且寻优效果也最好。鉴于以上原因，本书后续章节在构造配送车辆优化调度问题的禁忌搜索算法、模拟退火算法和遗传算法时，一般均采用客户直接排列的解的表示方法。
如前所述，用爬山算法求解无时限单向配送车辆优化调度问题时，其邻域选点策略有换位法、逆转法和插入法等，其中换位法又包括两交换法和三交换法等；另外每次邻域操作实施换位、逆转和插入操作的次数可以仅取1次，也可以取多次。为了分析邻域选点策略对爬山算法性能的影响，作者又为无时限单向配送车辆优化调度问题分别设计了基于以下几种邻域选点策略的爬山算法：（1）三交换法；（2）逆转法；（3）插入法；（4）三次两交换法（即在每次邻域操作中执行三次两交换操作）。在上述爬山算法中，均采用客户直接排列的解的表示方法及相应的解的评价方法。作者还分别为上述爬山算法编制了计算机程序，并对实例2.2进行了实验计算，计算中仍采用以下运行参数：迭代次数取2000，对不可行路径的惩罚权重取300km。分别利用上述几种基于不同邻域选点策略的爬山算法对实例2.2随机求解10次，得到的平均计算结果见表2.8。为便于比较，将2.5节中采用两交换邻域选点策略时实例2.2的计算结果也列入表2.8中。
表2.8 求解实例2.2时邻域选点策略对爬山算法性能的影响分析表
由表2.8可以看出：从寻优效果看，上述五种邻域选点策略中，采用逆转法时算法的寻优效果最好，其解的质量最高（其配送总里程的平均值比两交换法低9.2%），其次是两交换法和三交换法，再次是三次两交换法，最差的是插入法（其配送总里程的平均值比两交换法多10.4%）。从求解效率看，采用两交换法、逆转法和插入法时计算时间最短，采用插入法时计算时间稍长，而采用三次两交换法时计算时间最长。可见，在爬山算法中，通过采用逆转法实施邻域操作，可使算法搜索更广泛的解空间，从而增强其全局搜索能力，并取得较好的计算结果。上述实验计算结果还说明：采用多次两交换法实施邻域操作只能带来计算时间的增加，却并不能改善算法的寻优效果。
爬山算法的寻优过程是指在算法迭代过程中，其解的质量随搜索次数的增加而不断提高的过程。在爬山算法中，每次迭代只执行一次邻域操作，即搜索次数与迭代步数相等。通过爬山算法的寻优过程，可以看出算法的寻优结果与搜索次数的关系。
由于爬山算法计算的随机性，每次计算的寻优过程也各不相同。例如，2.5节中用爬山算法对实例2.1的第3次求解的寻优过程如图2.3所示；对实例2.2的第10次求解的寻优过程如图2.4所示。
图2.3 用爬山算法求解实例2.1时的寻优过程图
图2.4 用爬山算法求解实例2.2时的寻优过程图
由图2.3和图2.4可以看出：爬山算法具有很快的收敛速度，该算法可在较少的搜索次数内得到问题的最优解或可行解。该算法在搜索的初期，解的质量提高很快，而随着迭代次数的增加，解的质量的改进速度逐渐放缓，当迭代到一定的步数后，解的质量不再提高，说明算法已经收敛到一个局部最优解。