本次算法项目中，我们被要求解决一个“仓库选址问题”。在该问题中，我们被给定了一定数量的顾客和一定数量的仓库。每个顾客到不同的仓库有不同的服务成本，同时每个仓库也有最小的经营成本（这意味着一旦仓库服务了顾客，其就会产生一个额外的成本）。我们的目标是寻找到一个顾客分配方案，使得总的服务成本（包含经营成本）最少。
FLP 是一个经典的 NP 难问题，CFLP 也一样。由于 NP 难问题夸张的求解时间复杂度，我们不能够寻求一个常规的，最优的方案来求解。相对的，我们只能够构建一个能够收敛到近似全局最优的启发式算法来获得一个近似解。
在本次项目中，我们选择了 爬山算法（Hill Climbing Algorithm）） 和 遗传算法（Genetic Algorithm） 作为我们的代码实现，并通过对比来寻求二者间的差异。
为什么选择 HC 和 GA？
HC 和 GA 是启发式算法的两大代表。其中前者是普通的启发式算法，通过不断寻求临域中的最优解来不断迭代，最后爬上“山峰”（即最优解）。但是这种算法存在严重的问题，它没有任何能力来避开局部最优解，因而当其收敛时，其到达的一般只是众多山峰中的一个较小的山峰（局部最优解）。与之相对，GA 作为一种经典的元启发式算法，有着一定的脱离局部最优陷阱的能力，因而通常能够在最后获得一个比 HC 更好的解。
Hill Climbing 爬山算法
爬山算法正如之前所说，是选择领域解池内估价最高的一个解来作为下一跳的起点。更数学化地来说，理想的爬山算法是在函数曲线（面）上的一个点，向着函数梯度方向爬升（下降）。因而如何在离散解集中生成梯度方向的解是爬山算法中的关键。
在本项目中，我们在每个解集输入时记录每个顾客的最低 Assign Cost 和其对应的工厂。然后，我们在生成一个解后，依次替换解中每个顾客的选择为其最低 Cost 值，再从之中选择最优值。如此迭代，最后能取得非常优秀的解（对于 P1，该方法可以收敛到 9300 的总 Cost）。并且得益于非常小的临域空间和无随机干扰（收敛条件可以设置为两次迭代间最优数值没有变化，而不需要继续迭代数次确保收敛）的缘故，其运行速度极快（对于所有测试数据集，算法运行时间均不超过 1 秒（在 MacBook Pro 2017 上测试，使用 g++ 编译））。
Genetic Algorithm 遗传算法
在遗传算法中，我们没有像爬山算法那样“功利”。我们随缘地生成一堆「个体」，或者说「种群」。每个个体持有一个基因，也就是一个问题的可能（但可能非法的）解，然后每次迭代时，我们从其中选取一定数量的个体（通过 K = 2 的竞技场算法）。之后我们令这些个体两两配对，取出双方的基因的拷贝，按给定概率对于基因进行交叉/编译，然后将这些基因用于生成新的个体，并加入下一代种群中。如此一来，就如同大自然的优胜劣汰一般，优秀的基因被不断保留，组合，又结合变异产生的随机扰动，最后更有可能达到一个全局最优值。
在本项目中，我们推荐您使用 20% 的交叉概率，5% 的变异概率，20 的种群大小，来达到结果优秀程度和算法收敛速度的较好平衡。我们在自有平台上测试结果如下：
算法结果对比
在两个算法的表格中我们可以明显看到（以 p1 和 p59 为例）：
| 算例 | 爬山算法结果 | 遗传算法结果 | 爬山算法耗时 | 遗传算法耗时 |
|---|---|---|---|---|
| p1 | 9327 | 9033(-294, -3%) | 0 | 3(+3, +>1000%) |
| p59 | 39121 | 37423(-1698, -4%) | 0 | 9(+9, +>1000%) |
正如我们上面讲的一样，爬山算法的优势在于梯度下降，速度极快，它很快地收敛到了一个局部最优解，而遗传算法在其上更进一步，虽然速度比爬山算法慢了非常多，但是也在较短时间内收敛到了一个优秀解。更重要的是，这个解普遍比爬山算法优秀一些，尤其是在算例规模较大的情况下，这得益于其随机扰动带来的走出局部最优的可能性。但相应的，庞大的解空间为其带来了不小的困扰。
但值得一提的是，这个结果并不能完全显示两者的差距。在遗传算法中，我几乎不需要考虑原本的估价函数的影响因素，也不需要担心生成新解的函数是否能够让解沿梯度下降方向前进——我只需要让种群自己进化，为他们提供交流基因和改变基因的可能就好了。在设计速度上，遗传算法要远胜爬山算法。而在执行效果上也是如此，尤其是对于那些估价函数性质不明显，影响因素不确定的问题，爬山算法可能同样需要面对一个巨大的临域空间，从而难以找到梯度方向，最终得到一个更差的结果，且消耗更久的时间。
在这个特殊 CFLP 中，爬山算法的优点被发挥到了极致，但纵然如此，它也不过是和遗传算法互有胜负。因而我们认为，在更复杂、一般的问题中，遗传算法通常会是一个更好的选择。
