基于改进遗传算法的冷链物流路径优化

    袁紫微

    摘 要：现阶段，我国生鲜食品电商依然处于初级发展阶段，该领域多数电商企业尚未盈利，要想盈利就必须降低成本。而生鲜食品电商成本攀高的主要原因是冷链设备落后以及冷链物流路径设计不合理。因此，本文针对采用基于遗传算法优化冷链物流路径的基础算法，对算法进行相应的优化获得改进遗传算法，以降低冷链物流运输成本，提高冷链物流运输效率。

    关键词：遗传算法；冷链物流；路径优化

    DOI：10.16640/j.cnki.37-1222/t.2019.10.201

    1 引言

    基于改进的遗传算法选择最佳的冷链物流路径，可有效减少冷链物流运输成本，提升冷链物流配送效率和服务水平，从而增加冷链物流企业的经济效益。冷链物流企业基本运作流程如图1所示。

    2 冷链物流路径优化的遗传算法分析与改进

    （1）编码。编码是指为了能够用计算机处理遗传算法的相关数据需要将其转换成计算机可以识别的数据。基于遗传算法的编码设计应该遵循完整性、非冗余性等原则。常用物流路径优化编码方式主要包括二进制编码、符号编码、实数编码三种。其中符号编码、实数编码是主流编码方式。因为冷链物流运输涉及单一配送中心向若干个需求点提供物流配送服务，节点之间存在连续性。因此，可以采用自然数编码方式进行编码。用0表示配送中心，车辆数量用m表示，客户用n表示，就可以用數学模型中解向量编制长度为m+n+1的染色体表示可选的冷链物流运输路径。如染色体“036790251408100”表示以下几条冷链物流运输路径：（1）配送中心0——客户3——客户6——客户7——客户9——配送中心0；车辆路径；（2）配送中心0——客户2——客户5——客户1——客户4——配送中心0；（3）配送中心0——客户8——客户10——配送中心0。

    （2）初始化种群。和其他算法相比，遗传算法最明显的不同在于其搜索对象的不同，遗传算法的搜索对象是种群。基于遗传算法的初始种群产生方式：设种群大小为N，随机形成N个初始解，每一个初始解都与一个个体对应，然后从初始代开始迭代，进化代数为T，当前迭代代数为t，按照一定规则进行搜索迭代，最终在满足特定条件或达到最大迭代次数时停止迭代。在冷链物流路径优化中可以利用混沌遗传算法（CGA），该算法不容易陷入局部最优，更接近真实生物进化过程，使初始种群个体更优良，算法效率更高，有效改善传统遗传算法局部寻优效率低、容易出现早熟的问题。

    （3）适应度函数。在遗传算法中采用适应度来衡量一个个体或解的优劣，适应度值与遗传可能性成正比。而适应度值由适应度函数确定。适应度函数需要结合实际问题进行定义，通常它可以通过目标函数经过相应转换得到。

    （4）选择。选择遗传算法中择优进化过程的关键一步。一般适应度高的解或个体表示其适应能力更强。从种群中选择适应度高的个体或解进行后续的交叉、变异操作，或者直接用于下一代新个体，构建新的种群，充分体现出适者生存的进化规则。当前常用的选择策略包括无回放随机选择、最优保存策略、确定性选择、轮盘赌等等，它们各有特点，各有利弊，应该结合具体问题，具体情况进行开展灵活的选择操作。按照适应度大小选取前m-1个染色体进行混沌扰动，求解出扰动后染色体适应度，可以让选择操作后的优良个体进行再一次的混沌化，以增强种群的多样性，有效避免早熟。

    （5）交叉。在遗传算法中，交叉操作是产生新个体的重要一步。交叉操作是指根据一定的规则交换两条染色体的基因以得到新个体。这个新个体保有上一代的一部分特征，但无法完全确保上一代的优秀基金被完全继承。因此，为了得到更加优质的新一代个体，就必须在进行交叉操作的过程中尽量使新个体继承上一代的优良基因，以提高交叉操作效率，目前常用交叉操作方法主要包括单点交叉、多点交叉、均匀交叉等。本文选用循环交叉（CX）法，基本步骤如下：

    第一步：依据交叉概率选择一对父代染色体，从中找到循环点；

    第二步：复制其中一个父代染色体的循环节点至子代对应位置；

    第三步：删除另一个父代染色体循环节点，将余下的循环节点复制到子代上；

    第四步：同样的方法获得另一个子代。

    （6）变异。在遗传算法中，和交叉操作一样，变异操作的目的同样是得到新个体。变异操作是指通过改变染色体编码串上的一部分基因以得到新个体。变异操作能有效增强种群的多样性，可以保证遗传算法的局部搜索能力，与交叉操作配合实用能够有效确保遗传算法的全局搜索能力。为了有效避免变异后新个体趋同，需要结合变异操作保持种群个体的随机性。本文选用翻转变异方法进行变异操作。

    第一步：依据变异概率选择父代变异个体；

    第二步：随机选取两个变异点，实施翻转操作；

    第三步：获得子代变异个体。

    （7） 终止条件。在经过多次迭代后，遗传算法的解与最优解趋近，但还不能真正得到最优解。因此，需要合理设置一个终止条件。如迭代到一定次数之后，遗传算法自动停止迭代；当迭代过程中染色体适应度停止变化或变化很微小时，就表示遗传算法得到了近似最优解，应停止迭代。本文改进后的终止规则采用双重终止条件，即如果连续几代种群间之间的平均适应度值变化小于某一标准值时；迭代次数达到要求，此时算法终止，提取最优个体并解码，得到冷链物流最优路径。

    3 结束语

    综上所述，本文对传统的冷链物流路径优化中应用的遗传算法进行了改进，旨在更好地发挥遗传算法的作用，提高冷链物流路径优化效率。

    参考文献：

    [1]陶云，张鹏程.基于改进遗传算法的冷链物流路径优化研究[J].蚌埠学院学报，2016，5（03）：85-90.

    [2]孔志周，官东.基于改进遗传算法的车辆路径优化研究[J].统计与决策，2007（16）：163-165.