配送车辆优化调度模型与算法最新章节_郎茂祥著

2.3 爬山算法的原理和实现步骤

爬山算法，也称局部搜索算法，是一种基于邻域搜索技术的、沿着有可能改进解的质量的方向进行单方向搜索（爬山）的搜索方法。该方法的局部搜索能力很强，是一种常用的寻找局部最优解的方法。作者通过文献检索，发现有关用爬山算法求解配送车辆优化调度问题的研究成果很少。

用爬山算法求解组合优化问题时的步骤如下（以目标函数求最小为例）。

第一步：选定一个初始解x ⁰ ；记录当前最优解x ^best =x ⁰ ，令P=N（x ^best ）（表示x ^best 的邻域）。

第二步：当P=φ时，或满足其他停止运算准则时，转第四步；否则，从N（x ^best ）中按某一规则选一个解x ^now ，转第三步。

第三步：若x ^now 的目标函数值f（x ^now ）小于 x ^best 的目标函数值f（x ^best ），则令x ^best =x ^now ，P=N（x ^best ），转第二步；否则，P=P-x ^now ，转第二步。

第四步：输出计算结果，停止。

在爬山算法中，第一步的初始解可以采用随机方法产生，也可用一些经验方法得到，还可采用其他算法得到初始解。在第二步中，其他停止运算准则是指除P=φ以外的其他准则，这些准则一般取决于人们对算法的计算时间、计算结果的要求。第二步中在N（x ^best ）中选取x ^now 的规则可以采用随机选取的规则。

可见，爬山算法从解空间中的一个点出发，通过不断迭代，最终可达到一个局部最优点。算法停止时得到的解的质量依赖于算法的初始解的选取、邻域选点的规则和算法终止条件等。