一种基于改进遗传算法的大件运输监测点布设系统的制作方法

1.本发明属于智能路线规划技术领域，具体涉及一种基于改进遗传算法的大件运输监测点布设系统。


背景技术：

2.公路大件运输已成为影响公路交通安全的重要因素之一，由于大件运输车辆载重大、负荷重，在通过公路桥梁或者技术状况较差的公路路段时，容易导致路基路面塌陷，造成交通事故。山西、河北等地区已陆续推出了大件运输管理系统，对全省的大件运输车辆安全进行核算检验。当前大件运输管理系统主要对车辆负荷提前进行核验，进而规划出符合安全通行条件的大件运输线路，但系统无法实时监测大件运输车辆是否按照规定路线行驶。若大件运输车辆并未按照实际规划路线通行，高负载的通行会大大缩短在役公路基础设施的服役能力，甚至造成交通隐患。为监测大件运输车辆是否按照规定路线行驶，因此需要一种大件运输监测点布设方法，筛选出大件运输车辆通行频率较高的关键路段，并在关键路段布设监测点，通过有限的监测设备尽可能监测到所有通行的大件运输车辆。
3.监测点布设方案规划主要分人工规划和算法规划两种途径。人工规划指用户根据经验从通行频率较高的路段中筛选一定数量的路段，在其布设监测点，但是此种方法效率较低，且要求用户经验丰富，才能做出较为准确的判断。算法规划多采用精确算法或者启发式算法求解最优的布设方案，传统的精确算法主要通过遍历每种方案求解出最佳方案，但是此种暴力求解方法往往会带来巨大的时间复杂度和空间复杂度。启发式算法主要包括粒子群算法和遗传算法等，此类算法计算速度相对较快，能够在一定的迭代次数下获取较好的解，但是当数据量较大时，算法也会陷入计算量大、收敛速度慢等问题。在获取较优解的同时提升模型的计算效率是本发明的重点研究内容。


技术实现要素：

4.本发明目的是提供一种基于改进遗传算法的大件运输全覆盖监测布设点位优化系统，基于大件运输行驶路线数据，构建监测点自动规划算法模型，根据用户需求，推荐合理的大件运输监测点位置；同时降低模型的复杂度，提高模型计算效率。
5.本发明的技术方案是：
6.一种基于改进遗传算法的大件运输监测点布设系统，包括以下模块：
7.构建大件运输路线数据库；
8.根据用户需求确定所需布设的监测点数量和部分监测点位置或不指定监测点位置
9.将路段数据编码，初始化第一代种群；
10.根据适应度函数计算种群中每个个体的适应度；
11.随机从种群中筛选出个体，不断迭代生成最佳监测点布设方案，
12.所述的不断迭代生成最佳监测点布设方案，包括：
13.判断是否达到迭代次数，若达到迭代次数，则对最终生成的编码结果进行解码，算法迭代结束，解码生成最终的监测点布设方案，否则算法继续迭代；
14.使用轮盘赌算法从当前代所有个体中随机选取两个个体；
15.以一定的概率对筛选出的个体进行交叉互换操作；
16.继续使用轮盘赌算法从当前代所有个体中随机选取两个个体；
17.以一定的概率对筛选出的个体进行变异操作；
18.计算新生成的个体的适应度，用适应度值好的个体替换种群中适应度值差的个体。
19.进一步地，所述的构建大件运输路线数据库模块收集所有历史大件运输路线数据，对收集的数据进行数据预处理，和将处理后的数据存入关系型数据库，所述历史大件运输路线数据包括：大件运输事件的开始时间、结束时间、路线起点、路线终点、途经路段、车型、车辆载重信息。
20.进一步地，所述将路段数据编码，初始化第一代种群模块操作之前，定义种群规模、染色体长度、编码方式、迭代次数、交叉概率、变异概率。
21.进一步地，所述根据适应度函数计算种群中每个个体的适应度模块根据每个个体的编码结果统计该方案能够监测的大件运输路线数量；根据适应度函数计算个体适应度，适应度函数计算公式为：
[0022][0023]
其中，i表示某个大件运输路线，n表示所有大件运输路线总数。xi为0/1变量，表示第i个大件运输路线是否被监测到，若被监测到则xi为1，否则xi为0。
[0024]
进一步地，所述的以一定的概率对筛选出的个体进行交叉互换操作模块随机生成两个交叉点，交叉点位置应在染色体长度范围内；将两个染色体对应的两个交叉点之间的基因进行交叉互换，判断交叉互换后的染色体是否满足约束条件，若不满足，重新生成交叉点位置后重复上述交叉互换相关步骤。
[0025]
进一步地，所述的以一定的概率对筛选出的个体进行变异操作模块随机生成两个变异点，变异点位置应该在染色体长度范围内；将两个染色体对应的两个变异点的基因进行变异操作，判断变异后的染色体是否满足约束条件，若不满足，重新生成变异点位置后重复上述变异相关步骤。
[0026]
进一步地，所述判断新生成的个体是否满足约束条件操作，包含以下步骤：
[0027]
解码个体，生成对应的路段；
[0028]
统计所有路段中布设监测点的路段数量，若总数量等于用户确定的监测点数量，则满足约束条件，否则不满足约束条件。
[0029]
本发明的有益效果是：
[0030]
本发明构建了大件运输路线数据库，可以对大件运输路线从不同维度进行管理统计；基于改进遗传算法确定了大件运输监测点位布设方案，可以为用户提供合理的大件运输监测点布设方案，避免了传统算法暴力求解的时间复杂度和空间复杂度问题，降低了计算资源消耗，大大提升了模型计算效率。
附图说明
[0031]
图1为基于改进遗传算法的大件运输监测布设点位优化方法流程图；
[0032]
图2为大件运输路线数据库；
[0033]
图3为交叉互换操作示意图；
[0034]
图4为变异操作示意图；
[0035]
图5为改进遗传算法适应度曲线图；
[0036]
图6为传统遗传算法适应度曲线图；
[0037]
图7是基于改进遗传算法的大件运输监测布设点位优化系统的操作流程图。
具体实施方式
[0038]
本发明提供了一种基于改进遗传算法的大件运输监测点布设系统，可应用于大件运输车辆的行驶路线监控等领域。系统主要包括以下模块：构造大件运输路线数据库；根据用户需求定义监测点位的数量和位置；初始化模型参数，主要包括定义种群规模、染色体长度、编码方式、迭代次数、交叉概率、变异概率；对染色体进行编码，生成初始化种群；通过适应度函数计算初始化种群的适应度，并且筛选出最好的个体；利用轮盘赌算法筛选进化的个体；通过交叉互换和变异操作不断生成新的染色体，计算新的染色体的适应度；通过精英保留策略，用适应度值更佳的个体替换被选中的个体，更新种群中的个体和种群中的最佳个体；循环执行进化操作，直至达到算法最大迭代次数；解码最终生成的种群中的最佳染色体个体，生成最终的大件运输全覆盖监测布设点位方案。本发明在实现大件运输全覆盖监测布设的同时，大大降低了模型的时间复杂度和空间复杂度，提高了模型的效率。
[0039]
下面结合实施例与附图对本发明提供的一种基于改进遗传算法的大件运输全覆盖监测布设点位优化方法作进一步说明。
[0040]
如图1所示，一种基于改进遗传算法的大件运输全覆盖监测布设点位优化方法，其包含以下步骤：
[0041]
步骤1：构造大件运输路线数据库。
[0042]
具体包含以下步骤：
[0043]
步骤1.1：获取大件运输路线数据，主要获取大件运输事件的开始时间、结束时间、路线起点、路线终点、途经路段、车型、车辆载重等信息。
[0044]
步骤1.2：对数据进行预处理，去除异常数据。
[0045]
步骤1.3：将处理后的数据结构化，其中大件运输路线和经过路段的关系为一对多的关系。将结构化的数据导入关系型数据库，大件运输路线数据库的数据表结构如图1所示。其中，id表示大件运输序号，start_time表示开始时间，end_time表示结束时间，start_position表示路线起点位置，end_position表示路线终点位置，route_section表示经过的路段，vehicle_type表示车型，vehicle_load表示车辆载重。
[0046]
步骤2：根据用户需求定义所需布设的监测点位数量和监测点位置。用户可以根据自身需求提供需要布设的监测点位数量以及自定义部分监测点位的位置。
[0047]
步骤3：定义模型的初始化参数，主要包括种群规模、染色体长度、编码方式、迭代次数、交叉概率、变异概率。在本实例中种群规模定义为100，染色体长度按照步骤1中得到的所有路段的数量(或可能布设监测点的备选路段的总数量)进行确定，编码方式设定为0/
1编码，迭代次数设置为1000，交叉概率和变异概率的取值范围为[0.5,0.8]。
[0048]
步骤4：将路段数据编码，随机初始化生成第一代种群。将步骤1中所有的路段去重后按顺序编号，将每个位置初始值赋值为0，在染色体上随机选取用户确定的监测点数量个数的位置，将其赋值为1，生成对应的染色体，完成第一代种群的初始化。
[0049]
步骤5：根据适应度函数计算种群中每个个体(染色体)的适应度值。
[0050]
具体包含以下步骤：
[0051]
步骤5.1：对每个个体进行解码，筛选取值为1的路段，获得该个监测点布设方案的布设路段信息。
[0052]
步骤5.2：根据适应度函数公式计算每个个体的适应度值，适应度函数计算公式为：
[0053][0054]
其中，i表示某个大件运输路线，n表示所有大件运输路线总数。xi为0/1变量，表示第i个大件运输路线是否被监测到，若被监测到则xi为1，否则xi为0。集合plan_set表示某个监测点布设方案，其包含的路段有{road_section1,road_section2,road_section3,
…
}，第i个大件运输路线road_set为{roadsection1,roadsection2,roadsection3,
…
}，判断该监测点布设方案是否能够监测到大件运输路线i，只需判断plan_set和road_set中的路段是否有交集，若有交集表示可以成功监测，即xi为1；无交集表示无法监测到，此时xi为0。同时要求集合plan_set中的路段总数等于用户输入的监测点数量，即所有选取的监测点位数量之和等于用户输入的监测点位数量。
[0055]
步骤6：筛选出适应度最佳的个体。步骤5.2中计算出了各个布设方案的监测率，从中挑选监测率最高的个体，将其保存下来作为当前代的最佳个体。
[0056]
步骤7：判断是否达到迭代次数，若未达到迭代次数，则执行步骤8。若已经达到迭代次数，则对种群中的最佳个体进行解码，对步骤6中的最佳个体的路段编码进行解码，获得最终的路段监测点位布设方案，此时模型运行结束。
[0057]
步骤8：选取需要交叉变异的个体。使用轮盘赌算法从经过步骤5处理后的种群中随机选取两个个体。每次交叉互换或者变异操作都会产生两个新的染色体，比较两个父染色体和两个子染色体的适应度值，用适应度较好的两个个体代替原来的两个父染色体，即保证新加入种群的个体一定不会比从种群中选取出的染色体差，确保算法在迭代过程中较优的个体能够一直被遗传下去，且种群整体向着适应度值更好的方向发展，这是本算法效果较好的关键。传统遗传算法的染色体的更新规则为直接使用所有的子染色体代替父染色体，而不去考虑他们的适应度值，这会导致每次新加入种群中的个体可能会比原来的个体差，导致模型迭代过程中适应度值较好的个体不会一直被遗传下去，算法的最佳适应度值不断波动，可能会造成算法不收敛或者陷入局部收敛的困境，导致模型最终得到的解仅是局部最优而非全局最优。
[0058]
步骤9：以一定的概率对筛选出的个体进行交叉互换操作。交叉互换事件的发生具有随机性，交叉概率在步骤3中定义，当概率事件发生时进行交叉互换，如图3所示，a和b为选取出的需要进行交叉互换的两条染色体，其交叉互换过程具体包括以下步骤：
[0059]
步骤9.1：随机生成两个交叉点位置，交叉点位置应该小于染色体长度(即备选的总路段数量)，如图3所示，其中a和b表示需要进行交叉互换的两条染色体，随机生成的两个交叉点位置为基因4和基因6。
[0060]
步骤9.2：将两个染色体在两个交叉点之间的染色体段进行交叉互换，如图3所示，即将染色体a和染色体b在基因4和基因6之间的基因进行互换，判断新生成的染色体是否满足约束条件，若满足，执行步骤9.3；如不满足，则返回步骤9.1，直至满足约束条件。
[0061]
步骤9.3：依据步骤5.2计算新生成的染色体的适应度函数值，如图3所示，c和d为新生成的染色体，计算其适应度值。
[0062]
步骤9.4：比较新生成的染色体与父染色体的适应度值，用适应度值最佳的两个个体代替筛选出的两个父染色体，达到更新种群个体，保持种群进化的目的，如图3所示，假设染色体b和染色体c的适应度最佳，则用染色体b和c代替种群中的a、b染色体。
[0063]
步骤10：以一定的概率对筛选出的个体进行变异操作，循环执行步骤5。变异事件的发生具有随机性，变异概率在步骤3中定义，当概率事件发生时进行变异操作，如图4所示，具体包括以下步骤：
[0064]
步骤10.1：随机生成两个变异点位置，变异点位置应该小于染色体长度(即备选的总路段数量)，如图4所示，其中a和b表示需要进行变异的两条染色体，染色体a随机生成的两个变异点位置为基因5和基因8，染色体b随机生成的两个变异点位置为基因2和基因7。
[0065]
步骤10.2：对两个染色体对应的变异点位置的基因进行变异，如图4所示，判断变异新生成的染色体是否满足约束条件，若满足，执行步骤10.3；如不满足，则返回步骤10.1，直至满足约束条件。
[0066]
步骤10.3：依据步骤5.2计算新生成的染色体的适应度函数值，如图4所示，新生成的染色体为c和d，计算其适应度值。
[0067]
步骤10.4：比较新生成的染色体与父染色体的适应度值，用适应度最佳的两个个体代替筛选出的两个父染色体，如图4所示，染色体b和d的适应度最佳，故用染色体b和d替代原先的染色体a和b。
[0068]
循环执行步骤5到步骤10，开始新一轮迭代进化。本发明的进化策略中由于随机因素导致的进化方向可能向好的方向发展，也可能向差的方向发展，保证了模型搜素全局最优解的能力，同时，每次迭代中都用最优秀的个体替代种群中原先的旧个体，保证种群整体进化方向是正确的，种群的平均适应度会逐步升高。此外，步骤6筛选出的适应度最佳的个体，不仅保证了其是当前代中的最优个体，也保证了其是整个迭代过程中生成的所有个体中的最优个体。
[0069]
为对比本发明提出的遗传算法和传统遗传算法的算法性能，选用同一份山西省大件运输路线数据进行测试，如图所示。种群规模设置为100；染色体长度设置为100；迭代次数设置为1000；交叉概率和变异概率分别设置为[0.5,0.8]和[0.5,0.8]。记录每轮迭代过程中种群中最佳适应度和平均适应度的变化趋势，具体如图5和图6所示。图5表示本发明提出的改进的遗传算法，图6代表传统的遗传算法，其中实线表示种群中最佳个体的适应度值，虚线表示种群中所有个体的平均适应度值，本发明中算法的适应度值越高越好。可以看出，两个算法迭代过程中的种群平均适应度和最佳适应度均能稳步上升，但平均适应度曲线更为平滑。在迭代1000次的条件下，本发明提出的改进的遗传算法在迭代600次左右时适
应度已较高并趋于稳定，传统的遗传算法在迭代600次以后适应度波动仍较大，且本发明提出的改进的遗传算法最终的适应度值为97.96％，传统的遗传算法最终的适应度值为92.68％。本发明提出的遗传算法收敛速度更快，最终获得的最佳适应度值更高，算法效果明显优于传统的遗传算法。
[0070]
基于同一发明构思，本发明的另一个实施例提供一种基于遗传算法的大件运输监测点布设系统，其包括：
[0071]
大件运输路线数据库构造模块，用于构造大件运输路线数据库；
[0072]
用户需求设置模块，用于供用户定义需要布设的监测点数量和监测点位置；
[0073]
遗传算法模块，用于根据用户需求初始化种群中的所有个体，根据迭代条件和适应度函数不断优化种群中的所有个体，最终筛选出适应度值最高的个体，生成最终的监测点位布设方案。
[0074]
本发明未详细阐述部分属于本领域技术人员的公知技术。以上实施例仅用以说明本发明的技术方案而非对其进行限制，本领域的普通技术人员可以对本发明的技术方案进行修改或者等同替换，而不脱离本发明的原理和范围，本发明的保护范围应以权利要求书所述为准。

技术特征：
1.一种基于改进遗传算法的大件运输监测点布设系统，其特征在于，包括以下模块：构建大件运输路线数据库；根据用户需求确定所需布设的监测点数量和部分监测点位置或不指定监测点位置将路段数据编码，初始化第一代种群；根据适应度函数计算种群中每个个体的适应度；随机从种群中筛选出个体，不断迭代生成最佳监测点布设方案，所述的不断迭代生成最佳监测点布设方案，包括：判断是否达到迭代次数，若达到迭代次数，则对最终生成的编码结果进行解码，算法迭代结束，解码生成最终的监测点布设方案，否则算法继续迭代；使用轮盘赌算法从当前代所有个体中随机选取两个个体；以一定的概率对筛选出的个体进行交叉互换操作；继续使用轮盘赌算法从当前代所有个体中随机选取两个个体；以一定的概率对筛选出的个体进行变异操作；计算新生成的个体的适应度，用适应度值好的个体替换种群中适应度值差的个体。2.根据权利要求1所述的基于改进遗传算法的大件运输监测点布设系统，其特征在于，所述的构建大件运输路线数据库模块收集所有历史大件运输路线数据，对收集的数据进行数据预处理，和将处理后的数据存入关系型数据库，所述历史大件运输路线数据包括：大件运输事件的开始时间、结束时间、路线起点、路线终点、途经路段、车型、车辆载重信息。3.根据权利要求1所述的基于改进遗传算法的大件运输监测点布设系统，其特征在于，所述将路段数据编码，初始化第一代种群模块操作之前，定义种群规模、染色体长度、编码方式、迭代次数、交叉概率、变异概率。4.根据权利要求1所述的基于改进遗传算法的大件运输监测点布设系统，其特征在于，所述根据适应度函数计算种群中每个个体的适应度模块根据每个个体的编码结果统计该方案监测的大件运输路线数量；根据适应度函数计算个体适应度，适应度函数计算公式为：其中，i表示某个大件运输路线，n表示所有大件运输路线总数。x
i
为0/1变量，表示第i个大件运输路线是否被监测到，若被监测到则x
i
为1，否则x
i
为0。5.根据权利要求1所述的基于改进遗传算法的大件运输监测点布设系统，其特征在于，所述的以一定的概率对筛选出的个体进行交叉互换操作模块随机生成两个交叉点，交叉点位置应在染色体长度范围内；将两个染色体对应的两个交叉点之间的基因进行交叉互换，判断交叉互换后的染色体是否满足约束条件，若不满足，重新生成交叉点位置后重复上述交叉互换相关步骤。6.根据权利要求1所述的基于改进遗传算法的大件运输监测点布设系统，其特征在于，所述的以一定的概率对筛选出的个体进行变异操作模块随机生成两个变异点，变异点位置应该在染色体长度范围内；将两个染色体对应的两个变异点的基因进行变异操作，判断变异后的染色体是否满足约束条件，若不满足，重新生成变异点位置后重复上述变异相关步骤。
7.根据权利要求5或6所述的基于改进遗传算法的大件运输监测点布设系统，其特征在于，所述判断新生成的个体是否满足约束条件操作，包含以下步骤：解码个体，生成对应的路段；统计所有路段中布设监测点的路段数量，若总数量等于用户确定的监测点数量，则满足约束条件，否则不满足约束条件。

技术总结
本发明公开了一种基于改进遗传算法的大件运输监测点布设系统，包括以下模块：构造大件运输路线数据库；根据用户需求定义监测点位的数量和位置；初始化模型参数；对染色体进行编码，生成初始化种群；通过适应度函数计算初始化种群的适应度，并且筛选出最好的个体；利用轮盘赌算法筛选进化的个体；通过交叉互换和变异操作生成新的染色体，计算新染色体的适应度；用适应度值更佳的个体替换被选中的个体；循环执行进化操作，直至达到算法最大迭代次数；解码最终生成的种群中的最佳染色体个体，生成最终的大件运输全覆盖监测布设点位方案。本发明在实现大件运输全覆盖监测布设的同时，大大降低了模型的时间复杂度和空间复杂度，提高了模型的效率。高了模型的效率。高了模型的效率。


技术研发人员：郝艳军 谢立安 姚广 杨喜英 孟利强 吕永萍 付玉强 杨睿之 高浩 孙恒 何鑫 贺炜 吴森
受保护的技术使用者：山西省智慧交通研究院有限公司
技术研发日：2023.05.24
技术公布日：2023/8/4