基于混洗蛙跳算法的农用机械调度方法

摘要

本发明公开了基于混洗蛙跳算法的农用机械调度方法。该方法包括以下步骤：步骤1，任务请求点通过WIFI发送位置信号至控制中心；步骤2，控制中心通过贪婪算法思想确定各请求点对应的调配中心；步骤3，利用混洗蛙跳算法确定各调配站局部最优的调配方案；步骤4，以各局部最优解作为总的调配方案优化的初始值，并利用混洗蛙跳算法得出全局最优解，即最佳的调配方案；步骤5，通过WIFI将最佳的调配方案发送至各个调配站；步骤6，各调配站执行任务，任务执行完后农用机械返回调配站。本发明提出了一种基于混洗蛙跳算法的农用机械调度方法，能够快速有效的规划农用机械最佳的调度方案，不仅降低了使用成本，同时提高了生产效率，具有良好的实际应用价值。

权利要求

1.基于混洗蛙跳算法的农用机械调度方法，具体步骤如下，其特征在于：步骤1，任务请求点通过WIFI发送位置信号至控制中心；

步骤2，控制中心利用贪婪算法思想确定各请求点对应的调配站；

步骤3，利用混洗蛙跳算法确定各调配站局部最优的调配方案；

步骤3中利用混洗蛙跳算法确定各调配站最优的调配方案的具体步骤为：步骤3.1，初始化种群参数：种群大小F，子群数量m，各子群青蛙数量n，最大迭代次数N，其中种群可以表示为P＝{U(1),U(2),…,U(F)},U(i)为第i只青蛙对应的向量，表达式为U(i)＝{xi,yi}；

步骤3.2，计算各只青蛙对应的适应度值，并以适应度值对各只青蛙进行降序排列；其中第i只青蛙对应的适应度函数fi为：其中Pi表示第i个调配站可调配的农用机械数量，Qi表示第i个调配站待处理的任务请求点总数；D0表示调配站与任务请求点之间的距离，D1表示两不同的任务请求点之间的距离，D2表示农用机械任务完成后返回调配站的距离；

步骤3.3，将F个种群青蛙归为F组，分别用Memetic算法进行搜索，得到局部最优解；

步骤3.3的具体步骤为：

步骤3.3.1，按照适应度值升序确定各种群中最好和最坏的青蛙以及整个种群中最好的青蛙，分别表示为Pg，Pw，Pb；

步骤3.3.2，按照公式d＝rand()×(Pb‑Pw)得出青蛙移动的距离，如果dmin≤d≤dmax(dmax为青蛙移动的最大值)，更新Pw，即：Pw＝Pw+d；

步骤3.3.3，计算更新后的Pw对应的适应度值，如果适应度值比原始Pw对应的小，则更新青蛙位置，否则，用Pg代替Pb；

步骤3.3.4，如果上述方法仍不能生成更好的青蛙，那么就随机生成一个新解取代原来最坏的青蛙Pw；

步骤3.3.5，重复执行步骤3.1‑步骤3.3，直至达到收敛条件，此时迭代完成；

步骤4，以各局部最优解作为总的调配方案优化的初始值，并利用混洗蛙跳算法得出全局最优解，即最佳的调配方案；

步骤4中利用局部最优值确定整体最优值的具体策略为：最优值搜索策略与步骤3保持一致，但此处的适应度函数有别于步骤3，应为：其中F表示调配站总的数量，Pt表示第t个调配站可调配的农用机械数量，Qt表示第t个调配站所包含的任务请求点总数；

步骤5，通过WIFI将最佳的调配方案发送至各个调配站；

步骤6，各调配站执行任务，任务执行完后农用机械返回调配站。

2.根据权利要求1所述的基于混洗蛙跳算法的农用机械调度方法，其特征在于：步骤2中利用贪婪算法思想确定任务请求点相应的调配站的具体策略为：算出任务请求点距离各个调配站的距离dist，并将其归类于最近的调配站，其中坐标(xi1,yi1)和(xi2,yi2)的两点之间的距离dist(i1,i2)定义为：

说明书

基于混洗蛙跳算法的农用机械调度方法

技术领域

[0001] 本发明涉及农用机械调度领域，特别是涉及基于混洗蛙跳算法的农用机械调度方法。

背景技术

[0002] 近年来，我国的科技、工业水平都得到的大力的发展与提升，不断提及智能制造、工业4.0等目标，各行各业都朝着智能化的方向发展。同时我国作为世界人口大国，近年来农机装备水平和农业机械化水平均得到了明显提升，但是与世界发达国家相比，我国农业机械化总体水平仍然偏低，地区间发展不平衡、部分地区农机闲置问题非常突出。

[0003] 其中的农机闲置问题主要由于农用机械调度策略落后造成的，农用机械调度的问题从本质上来说是排列组合的问题，而在实际生产中，所需求解问题的维度或规模过大，指数化增长的计算量导致算法计算效率低下，这远远不满足实际的农用调度需求。由此可见，设计出一个合理有效的农用机械调度方法，从而规划出最佳的调度方案意义重大，这不仅可以降低农用机械的使用成本，大大的提高生产效率，同时对农业的现代化建设有着非常重要的意义。

[0004] 国内涉及农用机械调度规划的专利有“一种农用机械全覆盖运动路径规划的方法”(201711041170.4)，该专利先采用Boustrophedon分解算法将目标农田与障碍物分割分成若干个相邻的区域，而后结合遗传算法找出覆盖所有区域的最优解，其中为了避免重复作业，引入A*算法搜索农用机械下一工作区域的最佳路径，但该专利中的遗传算法求得的解可能是局部最优而非全局最优，从而导致求得的结果不精确。国家发明专利“一种基于Dijkstra算法的农用机械最短路径规划方法”(201710966489.1)，该方法通过选取出一批较优节点，同时引出一个最大估值K用以限制这批节点的扩散程度，再以这批较优节点作为Dijkstra算法的顶点集，从而保证了搜索的结果是全局最优而非局部最优，但是该专利中所用的Dijkstra算法是一种遍历算法，在搜索节点过多的情况下会大大的增加算法的时间复杂度，在实际应用中存在一定的局限性。由此可见，在农用机械调度领域，设计出一个高效精确的调度方法是非常有必要的。

发明内容

[0005] 为解决上述问题，本发明在贪婪算法思想和混洗蛙跳算法的基础上，提出了一种基于混洗蛙跳算法的农用机械调度方法。为尽可能降低算法求解的难度和准确性，本发明首先采用贪婪算法思想将任务请求点归类于最近的调配中心，而后利用局部到全局的优化策略，结合混洗蛙跳算法求解出最佳的农用机械调度方案，该方法可以快速的给出最优方案，在节约调度成本的同时大大的提高了生产效率。为达此目的，本发明提供基于混洗蛙跳算法的农用机械调度方法，具体步骤如下，其特征在于：

[0006] 步骤1，任务请求点通过WIFI发送位置信号至控制中心；

[0007] 步骤2，控制中心利用贪婪算法思想确定各请求点对应的调配中心；

[0008] 步骤3，利用混洗蛙跳算法确定各调配站局部最优的调配方案；

[0009] 步骤4，以各局部最优解作为总的调配方案优化的初始值，并利用混洗蛙跳算法得出全局最优解，即最佳的调配方案；

[0010] 步骤5，通过WIFI将最佳的调配方案发送至各个调配站；

[0011] 步骤6，各调配站执行任务，任务执行完后农用机械返回调配站。

[0012] 进一步，步骤2中利用贪婪算法思想确定任务请求点相应的调配中心的具体策略为：

[0013] 算出任务请求点距离各个调配站的距离dist，并将其归类于最近的调配站，其中坐标(xi1,yi1)和(xi2,yi2)的两点之间的距离dist(i1,i2)定义为：

[0014] 进一步，步骤3中利用混洗蛙跳算法确定各调配站最优的调配方案的具体步骤为：

[0015] 步骤3.1，初始化种群参数：种群大小F，子群数量m，各子群青蛙数量n，最大迭代次数N，其中种群可以表示为P＝{U(1),U(2),…,U(F)},U(i)为第i只青蛙对应的向量，表达式为U(i)＝{xi,yi}；

[0016] 步骤3.2，计算各只青蛙对应的适应度值，并以适应度值对各只青蛙进行降序排列；其中第i只青蛙对应的适应度函数fi为：

[0017]

[0018] 其中Pi表示第i个调配站可调配的农用机械数量，Qi表示第i个调配站待处理的任务请求点总数；D0表示调配站与任务请求点之间的距离，D1表示两不同的任务请求点之间的距离，D2表示农用机械任务完成后返回调配站的距离。

[0019] 步骤3.3，将F个种群青蛙归为F组，分别用Memetic算法进行搜索，得到局部最优解。

[0020] 步骤3.3的具体步骤为：

[0021] 步骤3.3.1，按照适应度值升序确定各种群中最好和最坏的青蛙以及整个种群中最好的青蛙，分别表示为Pg，Pw，Pb；

[0022] 步骤3.3.2，按照公式d＝rand()×(Pb‑Pw)得出青蛙移动的距离，如果dmin≤d≤dmax(dmax为青蛙移动的最大值)，更新Pw，即：Pw＝Pw+d；

[0023] 步骤3.3.3，计算更新后的Pw对应的适应度值，如果适应度值比原始Pw对应的小，则更新青蛙位置，否则，用Pg代替Pb；

[0024] 步骤3.3.4，如果上述方法仍不能生成更好的青蛙，那么就随机生成一个新解取代原来最坏的青蛙Pw；

[0025] 步骤3.3.5，重复执行步骤3.1‑步骤3.3，直至达到收敛条件，此时迭代完成。

[0026] 进一步，步骤4中利用局部最优值确定整体最优值的具体策略为：

[0027] 最优值搜索策略与步骤3保持一致，但此处的适应度函数有别于步骤3，应为：

[0028]

[0029] 其中F表示调配站总的数量，Pt表示第t个调配站可调配的农用机械数量，Qt表示第t个调配站所包含的任务请求点总数。

[0030] 本发明基于混洗蛙跳算法的农用机械调度方法，有益效果：本发明的技术效果在于：

[0031] 1.本发明从多因素考虑，构建准确有效的农用机械调度方法，同时利用贪婪算法思想将任务请求点归类于最近的调配中心，在一定程度上提高了算法的优化速度；

[0032] 2.本发明采用具有高效的计算性能和优良的全局搜索能力的混洗蛙跳算法准确的实现对农业机械调度方法的求解，较传统的算法提高了优化速度；

[0033] 3.本发明利用局部优化到全局优化思想，一方面提高了算法优化速度，另一方面避免了因优化求解时陷入局部最优而造成的结果不精确问题。

附图说明

[0034] 图1为农用机械调度方法示意图；

[0035] 图2为本发明的流程图；

[0036] 图3为混洗蛙跳算法的求解流程图。

具体实施方式

[0037] 下面结合附图与具体实施方式对本发明作进一步详细描述：

[0038] 本发明提出了一种基于混洗蛙跳算法的农用机械调度方法，旨在解决农用机械调度效率低下而造成的农机闲置问题。图1为本发明的农用机械调度方法示意图，可以看出：控制中心，各调配中心和各任务请求点之间以WIFI作为通信媒介，这提高了通信的效率，同时避免了传统有线通信受环境，布线等因素的不良影响。同时控制中心，各调配中心和任务请求点都有着相应的坐标位置，依据各位置坐标将不同的任务请求点归类于相应的调配中心，在一定程度上缩短了整体算法的优化时间。

[0039] 图2为本发明的流程图。下面结合流程图对本发明的步骤作详细介绍。

[0040] 步骤1，任务请求点通过WIFI发送位置信号至控制中心；

[0041] 步骤2，控制中心利用贪婪算法思想确定各请求点对应的调配中心；

[0042] 步骤2中利用贪婪算法思想确定任务请求点相应的调配中心的具体策略为：

[0043] 算出任务请求点距离各个调配站的距离dist，并将其归类于最近的调配站，其中坐标(xi1,yi1)和(xi2,yi2)的两点之间的距离dist(i1,i2)定义为：

[0044] 步骤3，利用如图3所示混洗蛙跳算法确定各调配站局部最优的调配方案；

[0045] 步骤3中利用混洗蛙跳算法确定各调配站最优的调配方案的具体步骤为：

[0046] 步骤3.1，初始化种群参数：种群大小F，子群数量m，各子群青蛙数量n，最大迭代次数N，其中种群可以表示为P＝{U(1),U(2),…,U(F)},U(i)为第i只青蛙对应的向量，表达式为U(i)＝{xi,yi}；

[0047] 步骤3.2，计算各只青蛙对应的适应度值，并以适应度值对各只青蛙进行降序排列；其中第i只青蛙对应的适应度函数fi为：

[0048]

[0049] 其中Pi表示第i个调配站可调配的农用机械数量，Qi表示第i个调配站待处理的任务请求点总数；D0表示调配站与任务请求点之间的距离，D1表示两不同的任务请求点之间的距离，D2表示农用机械任务完成后返回调配站的距离。

[0050] 步骤3.3，将F个种群青蛙归为F组，分别用Memetic算法进行搜索，得到局部最优解。

[0051] 步骤3.3的具体步骤为：

[0052] 步骤3.3.1，按照适应度值升序确定各种群中最好和最坏的青蛙以及整个种群中最好的青蛙，分别表示为Pg，Pw，Pb；

[0053] 步骤3.3.2，按照公式d＝rand()×(Pb‑Pw)得出青蛙移动的距离，如果dmin≤d≤dmax(dmax为青蛙移动的最大值)，更新Pw，即：Pw＝Pw+d；

[0054] 步骤3.3.3，计算更新后的Pw对应的适应度值，如果适应度值比原始Pw对应的小，则更新青蛙位置，否则，用Pg代替Pb；

[0055] 步骤3.3.4，如果上述方法仍不能生成更好的青蛙，那么就随机生成一个新解取代原来最坏的青蛙Pw；

[0056] 步骤3.3.5，重复执行步骤3.1‑步骤3.3，直至达到收敛条件，此时迭代完成。

[0057] 步骤4，以各局部最优解作为总的调配方案优化的初始值，并利用混洗蛙跳算法得出全局最优解，即最佳的调配方案；

[0058] 步骤4中利用局部最优值确定整体最优值的具体策略为：

[0059] 最优值搜索策略与步骤3保持一致，但此处的适应度函数有别于步骤3，应为：

[0060]

[0061] 其中F表示调配站总的数量，Pt表示第t个调配站可调配的农用机械数量，Qt表示第t个调配站所包含的任务请求点总数。

[0062] 步骤5，通过WIFI将最佳的调配方案发送至各个调配站；

[0063] 步骤6，各调配站执行任务，任务执行完后农用机械返回调配站。

[0064] 以上所述，仅是本发明的较佳实施例而已，并非是对本发明作任何其他形式的限制，而依据本发明的技术实质所作的任何修改或等同变化，仍属于本发明所要求保护的范围。