差分进化算法在旅行商问题中的应用

2022-07-25白芸高玉渊

科学技术创新 2022年23期

白芸高玉渊

（1、西安外事学院，陕西西安 710077 2、陕汽通汇物流有限公司，陕西西安 710038）

旅行商路线规划问题实际上是一个较为经典的多项式复杂程度非确定性问题，自身具有带权完全无向图中特征，所设定的节点依据全排列的方式布设，随着覆盖作用范围的扩大，会产生组合爆炸的现象，形成一个NP 完全问题[1-2]。但近几年来，随着应用背景及社会环境的复杂化、多元化，传统旅行商单一、固化的应用模式无法再满足需求及标准，对于过程中启发引导信息的获取定义以及最优解的收敛也逐渐暴露出不同程度的问题和缺陷[3]。

因此，对差分进化算法在旅行商问题中的应用作出分析以及研究。通过差分进化法来进行多层级、多目标的双向旅行商计算，得出精准的基础数值。与此同时，营造稳定的收敛测定环境，采用SGA 求解形式，定位存在的缺点因子，采用差分离散处理的方式，排除存在的误差，提升旅行商的并行性以及稳定性，以MapReduce 框架作为测定的基准，联合迭代计算计算出最终处理结果，全面系统地解决存在的问题，实现高效互补应用。

1 差分进化算法在旅行商问题中的应用

1.1 差分粗粒度并行预处理

粗粒度的并行预处理实际上是对旅行商问题测定核算环境的一种搭建。首先，构建初始的差分规则，在算法运行初期，将整个地区以种群划定的形式分为若干个子群，对每一个区域分别进行进化处理。旅行商值以及动态代数达到预设的标准时，计算出单元粗粒度的覆盖距离。在标定的旅行商范围之内，结合并行处理标准，设定对应的并行预处理模式，融入齐次马尔可夫链，增加预处理的层级和目标，扩大对应的范围，确保基础收敛程度，营造对应的差分粗粒度运动结构。与此同时，随着单元粗粒度的变化以及预设旅行商测定区域的延伸，控制每分钟的迭代次数，降低整体的收敛速度，完成对差分粗粒度并行预处理。

1.2 构建交叉进化运算层级

汇总整合基础数据之后，可以依据相关的数值信息，设定最优旅行商核定结构。从路线规划现状中可以得知，旅行商算子的群体分布情况，计算出并行路径距离。根据旅行商的变动情况，划定区域性的进化范围。与此同时，随着进化个体的变化，针对于交叉效率，计算出路径的重叠系数，具体如下：

式中：G 表示路径重叠系数，ℜ 表示平面算子距离，φ 表示初始启发参数，α 表示突变次数，β 表示突变向量，ν 表示迁移系数，λ 表示尝试向量。

通过上述计算，最终可以得出实际的路径重叠系数。此时，得出的路径重叠系数可以设定为交叉进化运算极限标准，配合GA 框架，建立对应的旅行商的基础算子处理结构，并根据商值的变动比率，设定相应的最优解执行目标，通过更改细粒度，提高计算效率。

1.3 建立迭代旅行商离散矩阵

在完成对交叉进化运算层级的构建之后，接下来，需要进行迭代旅行商控离散矩阵的建立。这部分首先需要结合差分粗粒度并行预处理情况以及获取的基础数值信息，编制TSP 执行编码。在旅行商的基础实数之中，首先进行四则运算，在连续域的背景之下，对传统的旅行商标准作出优化处理，此时，根据基础的迭代运行次数，测定商值的算子比例，具体如表1 所示。

表1 迭代旅行商控离散标定值设定表

根据表1，可以完成对迭代旅行商控离散标定值的设定。将每一个变动的离散节点关联在一起，自由组合，根据需要，划定对应的旅行商覆盖范围。需要注意的是，不同的位置，DE 变异算子与旅行商的关联程度不同，存在差值，可以根据运动规律看，对矩阵内部的运算控制环节重新排布，由小到大找出原来的数列，确保迭代次数正常增长的同时，完成迭代旅行商离散矩阵的建立。

1.4 无线差分积累应用模型设计

在完成迭代旅行商离散矩阵的建立之后，接下来，需要设计无线差分积累应用模型。根据状态转移规则，设定基础的运行计算应用程序，在标定的旅行商执行范围之内，实现变动状态的定向融合。与此同时，将对应的转移路线依据特殊的格式导入应用结构之中，扩大最优路线的延伸范围，随着迭代次数的变化，计算出定向的差分单元值，具体如下：

式中：R 表示差分单元值，b 表示定向变化比，μ1表示交换比，h 表示最优解，ϖ 表示扩大范围，i 表示差分延迟距离，υ1表示基因数目。

通过上述计算，最终可以得出实际的差分单元值。在差分进化算法的辅助之下，测定测试的旅行商动态极限差值。设定其为极限值标准，根据所建立的迭代旅行商离散矩阵，构建对应的旅行商动态生成树，具体的结构如图1 所示。

图1 旅行商动态生成树环节图示

依据差分进化算法，测定旅行商此时的收敛范围，并通过矩阵核算出不同路线的收敛概率。根据得出的收敛概率，划定此时旅行商的收敛范围，结合路线的转移规律，明确实际的应用环节，在无线迭代环境下，积累对应的离散单元。

1.5 C2Opt 算子重复排序

采用DE 算法测定实时收敛速度，将单元区域内易陷旅行商值去除，替换成标定的基准数值。通过TSP NP-hard 求解，在预设的范围之内，布设对应数量的C2Opt 算子，摒弃传统的单一、固化排序，采用重读排序的方式，设定一个算子运行计算核心节点，同时，采用基础的计算路径，利用差分进化法，计算出重叠比，具体如下：

式中：T1表示重叠比，表示定向范围内的算子重叠次数，u 表示极端重复差值，ξ 表示交叉重复单元，E 表示优化差值。

通过上述计算，最终可以得出实际的重叠比。根据重复排序，并遵循C2Opt 算子的测定核算框架，形成双向的启发环节，营造出更为稳定、精准的旅行商处理环境，在2-OPT 算子的执行下进行局部优化，以提高收敛速度和精度，进而完成对C2Opt 算子重复排序的处理。

1.6 逆向旅行域设定

采用巡回旅行的路线，对于城市的最佳路线作出标定。与此同时，根据定向的排序，制定运行编码串。在编码的过程中，针对于不同的覆盖区域，设定第一个的旅行商约束条件，形成区域性的逆向区域，称之为逆向旅行域。可以促使在测定的过程中，集中不形成回路。降低整体的测定误差，采用设定，更改标定的坐标，设立对应的矩阵口，使用Ⅳ矩阵的形式，将逆向旅行域融入旅行商的覆盖范围之内，测定存在的基础偏差，同时测定此时逆向旅行域中的最小路径长度形成逆向旅行域设的变动状态，具体如图2 所示。

图2 逆向旅行域设变动状态图示

根据图2，可以完成对逆向旅行域设变动状态的分析。依据适应度的变化状态，在标定的区域之内，关联相关的变异算子，与逆向旅行域形成反向覆盖区域，以此来进一步优化无线差分积累应用模型，提升整体的应用效果。

1.7 迭代进化完成旅行商问题的应用

在完成对逆向旅行域的设定之后，接下来，还需要采用迭代进化完成旅行商问题的应用。根据上述获取的实时偏差率，在标定的区域之内，划定迭代进化的应用范围。与此同时，采用差分进化算法进行连续域上的优化求解，结合DE 算法。

设定具体的离散路径，根据变动的TSP 编码，构建一种特殊的旅行商适应计算指令，以此来进一步强化局部优化的能力，从多个方向提升综合收敛速度，结合2OPT 算子，在不同的规模之下，实现迭代进化处理，以此来进一步解决旅行商的误差问题，提升整体的旅行商问题应用效果。

2 应用测试

选择6 个城市作为测试的主要目标对象，将每一座城市的路线导入数据库。将蚁群算法、遗传算法以及本文所设定的差分进化法同时应用在旅行商的问题之中，对最终的测试结果对比探究。

2.1 测试准备

将城市按顺序编号，同时设定对应的坐标，具体如表2 所示。

表2 旅行商测定城市编号及坐标表

根据表2，可以完成对旅行商测定城市编号及坐标的设定。根据上述的设定，结合基础的旅行商测定数值，针对存在的调研的路线，进行TSP 编码的编制与调整，设定起点城市和终止城市，可以先利用差分进化法计算出单个城市的环路总长度，具体如下：

式中：d（P1）表示单个城市的环路总长度，i 表示定向中环距离，n 表示是适应度函数。通过上述计算，最终可以得出实际的单个城市的环路总长度。根据特定的路径程度，设定具体的路径循环调整范围。在初始化的种群之中，按照对应的比例，设定单元差分距离，并深化预设旅行商问题中的路线最优解。

2.2 测试过程及结果分析

在完成对上述测试环境的搭建之后，接下来，需要结合差分进化算法，对6 个标定城市中存在的旅行商业问题作出具体测定。根据最小生成树的顶点变化情况，测定实时路线的耗时差别在相同的收敛范围之内，依据运行状态，计算出旅行商最终的规划线路。最终得出的结果对比分析，如表3 所示。

表3 旅行商问题应用结果对比分析表

根据表3，可以完成对旅行商问题应用结果的对比分析：与蚁群算法应用测试组和遗传算法应用测试组相对比，本文所设计的差分进化算法应用测试组最终得出的规划线路数相对较多，可以达到21 条方案，表明在差分进化法的辅助下，旅行商问题得到了更优越的处理，对于6 个城市的路线规划的最优解更加可靠、精准，具有实际的应用价值。