一种基于双层融合智能算法的多林区航线调度规划方法

摘要

本发明公开了一种基于双层融合智能算法的多林区航线调度规划方法，S1、设置第一层遗传算法的种群；S2‑S6、采用十进制编码方式初始化种群，计算适应度，执行选择、交叉、变异、逆转操作，重新插入到种群中并检查迭代次数；S7、蚁群算法信息素初始化；S8‑S20、设置蚂蚁个数m，分别随机放在待规划的多片区林区节点上，蚂蚁k不重复地将所有片区都遍历，及时更新局部信息素；检查蚂蚁索引号k是否大于蚂蚁个数m；全局信息素更新。检查迭代次数；输出作业顺序路径解集；设置第二层遗传算法种群；采用二进制编码种群Chrom2；计算适应度值；进行选择、交叉、变异操作；重新插入后得更新后种群；检测迭代次数；输出航线最佳调度方案。

说明书

技术领域

本发明涉及林业管理技术领域，尤其涉及一种基于双层融合智能算法的多林区航线调度规划方法。

背景技术

我国林区地形非常复杂，既有集中的大面积林区，也有分散的小面积林地。我国东部地区的林地以道路、村庄以及农田等地区的防护林为主，多为面积较小的片林，在航空施药的过程中，常出现施药区域为多个面积较小的林区，因此，多林区的调度航线规划尤为重要。小面积单林区规划中，应该减少质保飞机掉头次数；在多林区调度规划中，考虑片区进出入点，规划出路线较短的全局区域间调度航线具有重要意义。目前对航空多林区施药作业时调度航线的研究较少，难以满足多林区航空施药作业的使用需求，给多林区施药操作带来了一定的困扰。

发明内容

本发明的目的是针对现有技术的不足，提供一种基于双层融合智能算法的多林区航线调度规划方法，操作简单、效率高。

为了实现上述目的，本发明的技术方案是：

一种基于双层融合智能算法的多林区航线调度规划方法，包括如下步骤：

S1、根据需要喷药的林区数量设置第一层遗传算法的种群大小和长度、交叉概率、变异概率；

S2、采用十进制编码方式，采用随机产生种群的方式得到初始种群Chrom1；

S3、计算初始种群Chrom1的适应度，适应度值为每条染色体对应的作业顺序路径长度的倒数；

S4、对初始种群Chrom1执行选择、交叉、变异、逆转操作；

S5、重新插入到初始种群Chrom1中，得到更新后的更新种群Chrom1；

S6、检查迭代次数是否达到最大值，达到以后就执行S7，否则执行S3；

S7、根据更新种群Chrom1中的结果，进行蚁群算法信息素初始化；如更新种群Chrom1中包含片区1至片区2的路径，就在蚁群算法信息素设置时将片区1至片区2的路径的信息素增加；信息素增加值取更新种群Chrom1中适应度值最大的那条染色体的适应度值；

S8、设置蚁群算法的蚂蚁个数m，信息启发式因子、期望启发式因子、信息素挥发因子、信息素增强系数、蚁群算法迭代次数最大值；将初始迭代次数初值Nc＝0；

S9、迭代计数器增加1，将m只蚂蚁分别随机放在待规划的多片区林区节点上；

S10、蚂蚁禁忌表索引号k＝1,该只蚂蚁按照状态转移概率选择下一个片区，更新局部信息素，即当经过该片区，就将该片区和前一个所在片区之间路径的信息素适当增加，并修改片区禁忌表，即将走过的片区移除待遍历的片区集合，直到该只蚂蚁不重复地将所有片区都遍历完；该只蚂蚁每到一个片区，就更新一次局部信息素；

S11、检查蚂蚁索引号k是否大于蚂蚁个数m；当k≥m，执行S12，否则将蚂蚁禁忌表k＝k+1，并执行S10；

S12、m只蚂蚁都遍历了所有片区，执行全局信息素更新；

S13、检查迭代次数Nc是否大于蚁群算法迭代次数最大值；当Nc≥Ncmax，执行步骤S14，否则执行步骤S9；

S14、输出作业顺序路径解集；

S15、设置第二层遗传算法种群大小，交叉概率，变异概率，第二层算法最大迭代次数GENMAX2，并将迭代次数初值置1，即gen2＝1；

S16、第二层遗传算法初始化种群Chrom2，采用二进制编码的方式；

S17、计算第二层算法的适应度值，将飞机起降点看成2个点，表示从飞机起降点出发的考虑各片区进出点的全局区域间调度航线，假设算法第一层求得全局区域间调度航线有n种，则该适应度计算公式为

S18、对种群Chrom2中进行选择、交叉、变异操作；然后重新插入后得更新后种群Chrom2；

S19、检测迭代次数是否超过最大迭代次数GENMAX2，当迭代次数未超过最大迭代次数时，返回步骤S17，否则进行步骤S20；

S20、输出最短的全局区域间调度路径，该最短调度路径即为多林区航线调度规划的最佳调度方案。

作为对上述技术方案的改进，所述步骤S1中，第一层遗传算法种群中的种群大小设置为林区数与飞机起降点之和的4～6倍，迭代次数、交叉概率、变异概率、代沟均设置为常数。

作为对上述技术方案的改进，所述交叉概率设置为0.6～0.9，变异概率设置为0.0001～0.1，代沟设置为0.9～0.95。

作为对上述技术方案的改进，所述步骤S8中，蚁群算法的蚂蚁个数、信息启发式因子、期望启发式因子、信息素挥发因子、信息素增强系数均设置为常数。

作为对上述技术方案的改进，蚂蚁个数m设置为片区数的2/3倍，信息启发式因子设置1～5之间，期望启发式因子设置为2～5之间，信息素挥发因子设置为0.1～0.5之间，信息素增强系数设置为100～1000之间。

作为对上述技术方案的改进，所述步骤S15中第二层遗传算法种群中的种群大小设置为林区数与飞机起降点之和的4～6倍，交叉概率、变异概率、代沟均设置为常数。

作为对上述技术方案的改进，交叉概率设置为0.6～0.9，变异概率设置为0.0001～0.1之间，代沟设置为0.9～0.95。

与现有技术相比，本发明具有的优点和积极效果是：

本发明公开了一种基于双层融合智能算法的多林区航线调度规划方法，采用双层融合智能算法对多林区航线调度路径进行规划，特别针对载人大型植保飞机航空施药。第一层采用遗传算法和蚁群算法的组合算法，用遗传算法优化后的结果对蚁群算法的信息素进行初始化，避免了蚁群算法初始搜索阶段的盲目性，从而提升了搜索速度，较快得出较优的作业顺序路径解集；第二层算法采用遗传算法，结合第一层得出的解集，考虑各片区进出点，从而得到最短全局区域间调度路径，其避免了第一层程序里面只求得最短作业顺序路径而陷入的全局区域间调度路径局部最优解，计算效率较高，从而提高了多林区施药的路径规划效率。本发明可以缩短植保作业飞机在单片区林区中的施药转弯次数，可缩短在多林区施药操作的区域间调度路径航程，节约了多林区施药操作的工作时间，提高了林区施药的施药效率，并且其有效减小了航空燃油的使用量，节约了林区施药作业的经济成本，给多林区施药操作带来了便利。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

图1为本发明中的双层融合智能算法流程图；

图2为多林区航线规划任务图；

图3为单片区内航线规划示意图；

图4为多林区全局航线调度规划结果示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

如图1至图4所示，本实施例公开了一种基于双层融合智能算法的多林区航线调度规划方法，其航线规划任务如下：直升机从图2中飞机起落点H出发，然后经过每个片区的进入点和出去点，遍历每个片区，然后回到H。要求区域间调度的航线最短。区域内部采用图3所示的全覆盖航线规划算法，即从边界最长边根据飞机喷幅宽度以此做平行线，到其它边界交界时，飞机掉头飞行，直至遍历完片区所有面积。因此每个片区必有进入点和出入点。调度规划时必须从两点进出，但不具体哪一点。如从图2中A1进入后，必须从A2出，或者从A2进入后，必须从A1出。区域内部按照图3所示的航线规划。按照图1所示的双层融合智能算法进行路线规划，得到如图4所示的较优结果。

双层融合智能算法流程如图1所示：

以下是算法实施过程：

步骤1：有18片林区需要施药，则种群的长度定为18+1＝19。原因在于，将每个林区都用进出入点连线的中点表示，如图2中的A0所示，将图2中的飞机起降点也视为一个点，放在种群长度最后一位，则18片林区的调度任务看成是19片林区调度任务。种群的数量设置为城市数的4-6倍，如将19个片区的调度任务，种群数目可设置为76-114之间。设置第一层算法的迭代次数GEN1为常数，如500；交叉概率、变异概率、代沟都设置为常数。交叉概率设置为0.6-0.9之间，变异概率设置为0.0001-0.1之间，代沟设置为0.9-0.95。

步骤2：采用十进制编码方式，采用随机产生种群的方法，得到初始种群Chrom1。为方便举例，假设种群中有五片林区和一个飞机起降点，则123456、213465、345216都是可以是该种群中其中的一个染色体，要求数字不重复。如第一步种群数设置为30，则初始种群中有30个随机产生的染色体。

步骤3：计算第一层算法中的遗传算法的适应度。为方便快速计算，该算法适应度计算根据片区进出点中点生成的邻域表计算。以图2中的调度任务为例，其18个片区和飞机起降点的坐标如表1所示。其进出点中点生成的邻域表如表2所示。根据表2，可快速计算出该层遗传算法中染色体的适应度。

表1 各林区坐标表

以各片区进出点中点坐标作为参考点计算各林区作业顺序路径距离。并以该18片区中点坐标和飞机起降点坐标生成距离邻域表。

表2 各片区进出点中点生成的距离邻域表

步骤4：执行选择、交叉、变异、逆转操作。选择采用轮盘赌方式。采用逆转操作，可增强去全局搜索的能力。假如染色体为123456，在2和3，4和5处发生断裂再逆转插入，则新码串为12-43-56。

步骤5：重新插入生成更新后的种群Chrom1。

步骤6：检测迭代次数是否超过最大迭代次数GENmin，当迭代次数≥GENmin时，返回步骤3，否则进行步骤7。

步骤7：根据Chrom1中的结果，进行蚁群算法信息素初始化。如Chrom1中包含片区1至片区2的路径，就在蚁群算法信息素设置时将片区1至片区2的路径的信息素增加。信息素增加值取Chrom1中适应度值最大的那条染色体的适应度值。

步骤8、设置蚁群算法的蚂蚁个数m，信息启发式因子、期望启发式因子、信息素挥发因子、信息素增强系数、蚁群算法迭代次数最大值。蚂蚁个数m设置为片区数的2/3倍，信息启发式因子设置1～5之间、期望启发式因子设置为2～5之间、信息素挥发因子设置为0.1～0.5之间、信息素增强系数设置为100～1000之间。将初始迭代次数初值Nc＝0。

步骤9、迭代计数器增加1，将m只蚂蚁分别随机放在待规划的多片区林区节点上。

步骤10、蚂蚁禁忌表索引号k＝1,该只蚂蚁按照蚁群算法状态转移概率公式(4)计算的概率选择下一个片区，按公式(6)更新局部信息素，即当经过该片区，就将该片区和前一个所在片区之间路径的信息素适当增加，并修改片区禁忌表，即将走过的片区移除待遍历的片区集合，直到该只蚂蚁不重复地将所有片区都遍历。

步骤11、检查蚂蚁索引号k是否大于蚂蚁个数m。当k≥m，执行步骤12，否则将蚂蚁禁忌表k＝k+1，并执行步骤10；

步骤12、m只蚂蚁都遍历了所有片区，执行全局信息素更新，按照公式(5)进行。

步骤13、检查迭代次数Nc是否大于蚁群算法迭代次数最大值。当Nc≥Ncmax，执行步骤14，否则执行步骤9；

步骤14、输出作业顺序路径解集；

步骤15、设置第二层遗传算法种群大小，交叉概率，变异概率。如种群大小设置为林区数与飞机起降点之和的4～6倍，如18片区，则设种群数为100；交叉概率、变异概率、代沟均设置为常数；交叉概率设置为0.6～0.9，如0.8，变异概率设置为0.0001～0.1之间，如0.1，代沟设置为0.9～0.95，如0.9。第二层算法最大迭代次数GENMAX2，如2000。并将迭代次数初值置1，即gen2＝1；

步骤16、第二层遗传算法初始化种群Chrom2，采用二进制编码的方式。编码方式采用二进制编码，以四片片区域为例，作业顺序假定为ABCD，其中A表示飞机起降点。B区域的作业起始点可分别为B1与B2或B2与B1，两种状态分别用0与1表示。则A1A2B1B2C1C2D1D2的状态编码为0000，特别说明的是，飞机起降点A1和A2的坐标完全相同，表明作业顺序为从A出发，B1进，B2出，C1进，C2出，D1进，D2出，再回到A。则A1A2B2B1C1C2D2D1的状态编码即为0101。如此可以表示从飞机起降点出发的考虑各片区进出点的各片区间作业调度路径情况。

步骤17、计算第二层算法的适应度值。为方便第二层遗传算法适应度的计算，同样利用邻域表，该邻域表为将表1中的各片区进出点横坐标、纵坐标生成的邻域表，如表3所示。由于18个片区的考虑进出入点的邻域表太大，这里就展示4个片区和1个飞机起降点的领域距离矩阵。四个片区分别A、B、C、D，将每个片区的进出点分别表示为两个代号，如A片区的进出点表示为A

表3 考虑片区进出入点和飞机起落点的领域距离矩阵

步骤18、对种群Chrom2中进行选择、交叉、变异操作；然后重新插入后得更新后种群Chrom2；

步骤19、检测迭代次数是否超过最大迭代次数GENMAX2，当迭代次数未超过最大迭代次数时，返回步骤17，否则进行步骤20；

步骤20、输出最短的全局区域间调度路径，该最短调度路径即为多林区航线调度规划的最佳调度方案。

本发明通过采用双层融合智能算法对多林区航线调度路径进行规划，特别针对载人大型植保飞机航空施药。考虑到安全及各林区间调度无喷施飞行距离，因此将植保喷雾作业续航航程、载药量、植保喷雾作业续航时间参数的设置小于飞机自身性能参数。分别根据续航里程、载重量、续航时间计算施药面积，而最终确定的作业面积为上述三者中最小值。

本发明的双层融合智能算法采用串联式融合方法，迭代次数为两次算法各自迭代次数相加之和，速度较嵌套式融合更快。第一层采用遗传算法和蚁群算法的组合算法，利用了遗传算法初期搜索速度快的特点，用遗传算法优化后的结果对蚁群算法的信息素进行初始化，避免了蚁群算法初始搜索阶段的盲目性，从而提升了蚁群算法搜索速度，较快得出较优的作业顺序路径解集；第二层算法采用遗传算法，结合第一层得出的作业顺序路径解集，考虑各片区进出点，从而得到最短全局区域间调度路径，其避免了第一层程序里面只求得最短作业顺序路径而陷入的全局区域间调度路径局部最优解，计算效率较高，从而提高了多林区施药的路径规划效率。

本发明可以缩短植保作业飞机在单片区林区中的施药转弯次数，可缩短在多林区施药操作的区域间调度路径航程，节约了多林区施药操作的工作时间，提高了林区施药的施药效率，并且其有效减小了航空燃油的使用量，节约了林区施药作业的经济成本，给多林区施药操作带来了便利。