遗传算法解决物流中心选址的问题

2016-08-31韩秀梅王欣大连科技学院

科学中国人 2016年17期

韩秀梅，王欣大连科技学院

遗传算法解决物流中心选址的问题

韩秀梅，王欣
大连科技学院

摘要：随着经济的发展，网络技术的应用，物流中心的数量越来越多，在城市经济发展中的作用越来越重要。本文为解决物流中心选址问题采取了遗传算法，通过对物流中心位置的建模，选取适当的适应值函数，对物流中心的位置进行合理分配，使得选址建址过程中花费的费用最低。

注：项目名称：大连科技学院科学技术研究一般项目（编号：KJY201410）。

1　分析问题

对于物流中心选址问题，简言之，就是在产地和需求地点之间找一点，使从产地到物流中心和从物流中心道需求地点这两个过程中花费的费用最低。这个费用和运输量及运输距离成正比。这是个类似于TSP的问题，TSP即旅行商问题，它的解决办法是应用遗传算法。因此，物流中心选址问题，也应用遗传算法。首先对其进行建模。

式中：Fc总运输成本，vi为i点的运输量，fi为到i点的运输费率，di从待定的物流中心到i点的距离。

距离可由下式获得

2　算法总体设计

2.1根据遗传算法的流程和步骤，针对物流中心选址问题的总体设计作如下说明：

（1）本算法制定了一定的迭代次数来作为算法的结束准则，当达到一定的迭代次数时，算法结束，输出最优解。

（2）根据适应值函数进行选择时，记录当前最优解，在经过交叉变异更新群体后，保证新的迭代循环中的群体越来越好。

（3）本例是按照适应值函数值来选择种群的，并使数目减少，当每次变异操作后，产生随机路径补充群体的个数不变，再次循环，这样在一定程度上防止了因为初始群体的选择问题而陷入局部最优致使无法得到最优解。

2.2设计详情

（1）编码和随机初始群体的生成

（2）和适应值函数

在求解该问题时，适应值函数为费用的和，费用的和越大，说明花费的越多，适应度就越小，反之，则适应度大。通过每次选择适应度大的个体，来逐步找到最优解。

每个个体（每条距离路径）总和计算的编程实现为：

式中，Cmax是当前F(X)的最大值，此时，Cmax会随着代数有变化。

2.3选择操作

按照某种选择策略从群体中选择出若干个体进入交配池，交配池只不过的个体通过遗传算子的作用产生新一代群体。选择策略应遵循的基本原则是：适应值越大的个体被选中的概率应该越大[27]。即选择策略应遵循自然界“优胜劣汰、适者生存”的自然选择规律。

本文中使用适应值函数 fitness为：

利用 fitness>rand来选择个体，将费用较大（适应值大）的个体选择下来，但是这种算法的群体变少，并且优秀个体的数目较少，使可能收敛的数目变慢，在算法的调试的过程中证明了这一点。

2.4交叉操作

选择操作虽然能够从旧种群中选择则出优秀者，但不能创造新的染色体。交叉操作模拟生物进化过程中的繁殖现象，通过两个染色体的交换组合，来产生新的优良品种，从而检测到搜索空间中新的点。因此，交叉操作时遗传算法的核心操作部分，通过交叉，能生成具有更多模式的个体，使个体的多样化能促进算法搜索到全局最优解。

本文中的交叉采用部分匹配策略，其基本实现步骤如下：

（1）随机选择两个交叉点；

（2）将两个交叉点中间的基因互换；

（3）将互换的基因段以外的部分中与互换后基因段中元素冲突的用另一附带的相应位置代替，直到没有冲突为止。

过程实例如图所示，交叉点为2、7，交换匹配段后，A中冲突的有7、6、5，在B的匹配段中找出与A匹配段中对应为止的值7-3、6-0、5-4，继续检测冲突直到没有冲突。对B做同样的操作，得到最后结果。

图4.1匹配段交换图例

2.5变异操作

从遗传运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力，而变异运算知识产生新个体的辅助方法，但它也是必不可少的一个运算步骤，因为它决定了遗传算法的局部搜索能力。交叉算子与变异算子的相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。

本文中变异操作使用互换操作算子，也就是随机交换染色体中的两个不同基因编码的位置，互换操作相对于逆序操作和插入操作更有利于算法的大范围搜索

例如，变异交换位置为2和8。