欧阳浩 广西科技大学计通学院

基于遗传禁忌算法的仓库选址优化

欧阳浩 广西科技大学计通学院

针对物流行业的仓库选址问题，本文提出了一种基于遗传禁忌算法的解决方法。在算法的计算过程中，先对选址问题进行有效的编码，然后对编码后的染色体进行选择，交叉以及变异。而其中的变异计算采用的是禁忌算法，可以有效避免遗传算法的过早收敛，从而获得更优的值。

1 引言

如何优化仓库的选址一直是物流行业中的一个重要问题，优化后的选址可以大大降低物流中的运营成本。因此，该问题实质上是如何对一个最优化问题的求解。遗传算法在求解最优化问题中得到了普遍的运用，其实现起来简单，可以在较短的时间里获得一个比较理想的结果，但传统的遗传算法也有着一定的局限性，当其进化到一定程度，算法将将陷入到某个局部最优解中，从而无法再进化下去。

本文将根据遗传算法的特点，在此基础上引入禁忌算法，将禁忌算法作为遗传算法的变异算子，从而使得计算可以跳出局部最优解，最终获得全局上的优化结果。

2 遗传算法与禁忌算法

遗传算法是一种模拟大自然中“适者生存”法则的智能进化算法，模拟过程中，包括种群的“选择”，“交叉”以及“变异”计算。从而不断地迭代和进化，使得计算结果逐渐优化。

禁忌算法是在计算过程中使用一张禁忌表，禁忌表中将记录最近计算得到的值，在今后的一段时间内，表中的值禁忌出现。为了提升算法的求解能力，若计算获得的新值优于此前设定的某个阈值时，这个新的值不管是否在禁忌表中，都能被接受，此过程称为“破禁”。算法的计算过程如图2所示。计算中，迭代次数记为NG，适应度的计算公式为C(X)，禁忌表为T。

图2 禁忌算法计算过程

3 基于遗传禁忌算法的仓库选址优化

由于遗传算法容易陷入到“局部最优”中，从而使得进化过程将停滞不前，因此，改变遗传算法中传统的“变异”算子，使用禁忌算法作为遗传算法的“变异”算子，将大大提升遗传算法的进化能力。完成新算法中，需要考虑的问题还包括问题的编码，适应度函数的确定，“选择”和“交叉”算子的设计。

3.1 仓库选址的数学模型

为了解决仓库选址问题，首先需要将该区域划分为多个方格，方格中包括了货物的需求地点以及仓库候选地点，从而构成选址问题的数据模型，此模型的示意图见图3。

设数学模型中包括n个货物需求地点，m个仓库候选地点，由此，仓库选址问题就演变成了如何从m个候选地点中选出K个确定的地点。此问题若采用传统的穷举法，计算量会随着m的增大而成指数上升。由此，采用智能计算方式有利于计算此类问题。

图3 仓库选址的模型

3.2 遗传算法的编码和适应度函数

在遗传算法的编码过程中用Xi来表示第i个候选地点是否被选中。fij表示第i个候选地点到达地第j个需求地的货物量，rij表示第i个候选地点到达地第j个需求地的距离。

这样，仓库选址实际上就是去求得下面G(X)公式的最优值。适应度函数可以取1/G(X)。

3.3 遗传算法的各个算子

在采用遗传算法解决仓库的选址问题中，为了简化问题，“选择”算子采用由概率计算的轮盘赌算法，使得适应度高的染色体优选被选中，同时，适应度低的染色体也有被选中的可能，这样既可以保证种群的优越性，也能保证其多样性。“交叉”算子采用部分映射交叉的方式，可以保证每次生成的子代染色体都是有效的解。“变异”算子采用前面所述的禁忌算法，可以避免算法过早的收敛，而导致无法找到全局的最优解。

4 小结

本文介绍了一种基于遗传禁忌的算法来解决仓库选址的优化问题，相对传统的遗传算法而言，本文提出的算法可以更好地获得全局最优解。当然，本文提出的数学模型未能考虑选址中是否存在限定条件等因素，在今后的研究中，需要进一步研究和改进。

[1]欧阳浩,王萌,黄镇谨等.用遗传算法解决物流中的仓库选址问题[J].制造业自动化,2014,36(1):51-52,64.

[2]赵振亚,霍国先.基于模拟退火算法的应急物流仓库选址优化[J].大连交通大学学报,2010,31(3):102-106.

本文由广西科技大学校科自No.174523资助。