基于改进人工鱼群算法的多农机调度作业方法

摘要

本发明公开了一种基于改进人工鱼群算法的多农机调度作业方法，包括：基于人工鱼群算法初始化人工鱼群规模及初始化人工鱼群算法参数，每一条人工鱼代表一种调度分配方案；计算人工鱼群中每一条人工鱼的适应度参数f，并将适应度参数f最优的人工鱼编号记录在公告板上；对人工鱼群分别执行觅食、聚群、追尾及随机行为，并分别从更新后的多个人工鱼群中选出最优的人工鱼；将选出的最优的人工鱼分别与公告板上的最优的人工鱼进行比对，若选出的人工鱼的适应度参数f大于公告板上的人工鱼的适应度参数f，则对公告板上的最优的人工鱼进行更新并输出。本发明的算法全局收敛能力，对初始值设置具有很强的适应性，能够快速高效的生成农机调度方案。

说明书

技术领域

本发明涉及农机调度作业领域，更具体的说，是一种基于改进人工鱼群算法的多农机调度作业方法。

背景技术

多农机调度涉及农机任务分配和调度路径规划问题，是多农机协同作业的核心。近年来，多种启发式算法被应用于求解多农机调度问题，如遗传算法、蚁群算法等。但这些算法对初始值设置比较敏感，当初始值设置不当时往往会存在收敛速度慢甚至不收敛等情况。

发明内容

本发明的目的在于提供一种基于改进人工鱼群算法的多农机调度作业方法，本发明的作业方法全局收敛能力，对初始值设置具有很强的适应性，能够根据任务地块和作业农机数量，快速高效的生成农机调度方案。

其技术方案如下：

基于改进人工鱼群算法的多农机调度作业方法，，包括以下步骤：

S1：获取任务农田数量Z、服务农机数量M、每一块任务农田和每一台服务农机的位置信息，并对每一块任务农田及每一台服务农机进行编号；

S2：根据获取的上述信息，基于人工鱼群算法初始化人工鱼群规模及初始化人工鱼群算法参数，人工鱼群X＝(x

S3：计算人工鱼群中每一条人工鱼的适应度参数f，并将适应度参数f最优的人工鱼编号记录在公告板上；

S4：对人工鱼群分别执行觅食、聚群、追尾及随机行为，人工鱼群在执行完上述每一行为后则对人工鱼群进行更新，并分别从更新后的多个人工鱼群中选出最优的人工鱼；

S5：将选出的最优的人工鱼分别与公告板上的最优的人工鱼进行比对，若选出的最优的人工鱼的适应度参数f大于公告板上的最优的人工鱼的适应度参数f，则对公告板上的最优的人工鱼进行更新；

S6：输出公告板上最优的人工鱼编号，该人工鱼编号对应的调度分配方案即为最优的调度分配方案。

进一步地，在步骤S3中，人工鱼的适应度参数f满足以下公式：

其中，c为服务农机的运行成本，S

进一步地，在步骤S4的觅食行为中，具体包括以下步骤：

对人工鱼群中的每一条人工鱼随机选择执行交换觅食行为或替换觅食行为；

人工鱼群中的全部人工鱼执行完交换觅食行为或替换觅食行为后，更新人工鱼群；

计算更新后的人工鱼群中每一条人工鱼的适应度参数，并从中选出适应度参数最优的人工鱼，将该人工鱼与公告板上的人工鱼进行比对，如果该人工鱼的适应度参数大于公告板上的人工鱼的适应度参数，则用该人工鱼的编号替换公告板上的人工鱼的编号，否则，保持公告板上的人工鱼编号不变。

进一步地，对人工鱼群中的每一条人工鱼随机选择执行交换觅食行为或替换觅食行为，具体包括以下步骤：

在交换觅食行为中，随机选择人工鱼中一定数量的服务农机对，并交换选择的服务农机对中服务农机的顺序，形成新的人工鱼；

如果交换后的人工鱼的适应度参数大于交换前的人工鱼的适应度参数，则用交换后的人工鱼代替交换前的人工鱼，否则，则继续执行交换觅食行为；

在替换觅食行为中，随机选择人工鱼中一定数量的服务农机，并选择备用的服务农机替换选择的服务农机，形成新的人工鱼；

如果替换后的人工鱼的适应度参数大于替换前的人工鱼的适应度参数，则用替换后的人工鱼代替替换前的人工鱼，否则，则继续执行替换觅食行为；

其中，人工鱼在执行交换觅食行为或替换觅食行为时，记录交换觅食行为或替换觅食行为的执行次数，如果执行次数达到最大尝试次数T

进一步地，对人工鱼群中的每一条人工鱼随机选择执行交换觅食行为或替换觅食行为之前，具体还包括：

随机选择一条人工鱼；

随机生成一个小于等于1的正实数p；

判断正实数p是否大于0.5；

如果p>0.5，则对选择的人工鱼执行交换觅食行为，否则执行替换觅食行为。

进一步地，在步骤S4的聚群行为中，具体包括以下步骤：

判断人工鱼群中的人工鱼是否满足聚群行为，如果满足则执行聚群行为；

在执行聚群行为中，首先搜寻人工鱼X

如果中心位置人工鱼X

替代后的人工鱼与原人工鱼群中剩余的人工鱼组成新的人工鱼群，计算新的人工鱼群中的每一条人工鱼的适应度参数，并从中选出适应度参数最优的人工鱼，将该人工鱼与公告板上的人工鱼进行比对，如果该人工鱼的适应度参数大于公告板上的人工鱼的适应度参数，则用该人工鱼的编号替换公告板上的人工鱼的编号，否则，保持公告板上的人工鱼编号不变。

进一步地，在步骤S4的追尾行为中，具体包括以下步骤：

判断人工鱼群中的人工鱼是否满足追尾行为，如果满足则执行追尾行为；

在执行追尾行为中，首先搜寻人工鱼X

如果最优人工鱼X

替代后的人工鱼与原人工鱼群中剩余的人工鱼组成新的人工鱼群，计算新的人工鱼群中的每一条人工鱼的适应度参数，并从中选出适应度参数最优的人工鱼，将该人工鱼与公告板上的人工鱼进行比对，如果该人工鱼的适应度参数大于公告板上的人工鱼的适应度参数，则用该人工鱼的编号替换公告板上的人工鱼的编号，否则，保持公告板上的人工鱼编号不变。

进一步地，在步骤S4之后，还包括以下步骤：

对于人工鱼群中连续N

新生成的人工鱼与人工鱼群中未淘汰的人工鱼构成新的人工鱼群，继续参与后续算法迭代。

进一步地，人工鱼X的视野满足以下公式：

下面对本发明的优点或原理进行说明：

本发明将人工鱼群算法用于多农机调度作业中，人工鱼群算法对初始值适应性强，具有并发性强、效率高、收敛能力强等特点，特别适合于农机调度这种随机性强和实时性高的场景。本发明可根据任务地块及作业农机数量，快速高效生成农机调度方案。

附图说明

图1是本发明的多农机调度作业方法的总的流程图。

具体实施方式

下面结合附图对本发明的较佳实施例进行详细阐述，以使本发明的优点和特征能更易于被本领域技术人员理解，从而对本发明的保护范围做出更为清楚明确的界定。

如图1所示，本发明公开一种基于改进人工鱼群算法的多农机调度作业方法。

本发明的多农机调度作业方法具体包括以下步骤：

S1：获取任务农田数量Z、服务农机数量M、每一块任务农田和每一台服务农机的位置信息，并对每一块任务农田及每一台服务农机进行编号。

S2：根据获取的上述信息，基于人工鱼群算法初始化人工鱼群规模及初始化人工鱼群算法参数，人工鱼群X＝(x

以人工鱼编码为(1,4,1,2,1,2,3,3,4)的个体为例，该个体表示的方案为：

农机1：农机站→田块1→田块3→田块5→农机站；

农机2：农机站→田块4→田块6→农机站；

农机3：农机站→田块7→田块8→农机站；

农机4：农机站→田块2→田块9→农机站。

在初始化人工鱼算法参数时，则可设置人工鱼群算法种群规模N、每条人工鱼的初始化编码、人工鱼的视野Visual、最大尝试次数T

对于每一条人工鱼，适应度参数满足以下算法：

其中，C为每台农机的运行成本，S

可根据上述公式评价每条人工鱼的适应度参数，适应度参数越大，则表示该条人工鱼的调度方案越优。

S3：计算人工鱼群中每一条人工鱼的适应度参数f，并将适应度参数f最优的人工鱼编号记录在公告板上。

S4：对人工鱼群分别执行觅食、聚群、追尾及随机行为，人工鱼群在执行完上述每一行为后则对人工鱼群进行更新，并分别从更新后的多个人工鱼群中选出最优的人工鱼。

S5：将选出的最优的人工鱼分别与公告板上的最优的人工鱼进行比对，若选出的最优的人工鱼的适应度参数f大于公告板上的最优的人工鱼的适应度参数f，则对公告板上的最优的人工鱼进行更新；

S6：输出公告板上最优的人工鱼编号，该人工鱼对应的调度分配方案即为最优的调度分配方案。

人工鱼群在执行觅食行为中，具体包括以下步骤：

对人工鱼群中的每一条人工鱼随机选择执行交换觅食行为或替换觅食行为；

人工鱼群中的全部人工鱼执行完交换觅食行为或替换觅食行为后，更新人工鱼群；

计算更新后的人工鱼群中每一条人工鱼的适应度参数，并从中选出适应度参数最优的人工鱼，将该人工鱼与公告板上的人工鱼进行比对，如果该人工鱼的适应度参数大于公告板上的人工鱼的适应度参数，则用该人工鱼的编号替换公告板上的人工鱼的编号，否则，保持公告板上的人工鱼编号不变。

在觅食行为中，为了覆盖整体解空间，可定义交换和替换两种觅食行为。其中，在交换觅食行为中，针对的是人工鱼中调度农机不发生变化的场景；替换觅食行为针对的是人工鱼中调度农机发生改变的场景。交换觅食行为与替换觅食行为发生的概率均为50％。在每一次觅食行为中，可首先随机选择一条人工鱼，然后随机生成一个小于等于1的正实数p，接着判断正实数p是否大于0.5,如果p＞0.5，则对选择的人工鱼执行交换觅食行为，否则执行替换觅食行为。

在对人工鱼执行交换觅食行为与替换觅食行为，具体包括以下内容：

在交换行为中，随机选择人工鱼中一定数量(≤Visual/2)的服务农机对，并交换选择的服务农机对中服务农机的顺序，形成新的人工鱼；

如果交换后的人工鱼的适应度参数大于交换前的人工鱼的适应度参数，则用交换后的人工鱼代替交换前的人工鱼，否则，则继续执行交换觅食行为。

以人工鱼X

人工鱼在执行交换觅食行为时，记录交换觅食行为的执行次数，如果交换觅食行为的执行次数达到最大尝试次数T

在替换觅食行为中，随机选择人工鱼中一定数量(≤Visual/2)的服务农机，并选择备用的服务农机替换选择的服务农机，形成新的人工鱼；

如果替换后的人工鱼的适应度参数大于替换前的人工鱼的适应度参数，则用替换后的人工鱼代替替换前的人工鱼，否则，则继续执行替换觅食行为。

在替换觅食行为中，以人工鱼X

其中，人工鱼在执行替换觅食行为时，记录替换觅食行为的执行次数，如果替换觅食行为的执行次数达到最大尝试次数T

在人工鱼群的聚群行为中，具体包括以下步骤：

判断人工鱼群中的人工鱼是否满足聚群行为，如果满足则执行聚群行为；

在执行聚群行为中，首先搜寻人工鱼X

如果中心位置人工鱼X

替代后的人工鱼与原人工鱼群中剩余的人工鱼组成新的人工鱼群，计算新的人工鱼群中的每一条人工鱼的适应度参数，并从中选出适应度参数最优的人工鱼，将该人工鱼与公告板上的人工鱼进行比对。如果该人工鱼的适应度参数大于公告板上的人工鱼的适应度参数，则用该人工鱼的编号替换公告板上的人工鱼的编号，否则，保持公告板上的人工鱼编号不变。

中心位置人工鱼编码可以通过Most(X

在人工鱼群的追尾行为中，具体包括以下步骤：

判断人工鱼群中的人工鱼是否满足追尾行为，如果满足则执行追尾行为；

在执行追尾行为中，首先搜寻人工鱼X

如果最优人工鱼X

替代后的人工鱼与原人工鱼群中剩余的人工鱼组成新的人工鱼群，计算新的人工鱼群中的每一条人工鱼的适应度参数，并从中选出适应度参数最优的人工鱼，将该人工鱼与公告板上的人工鱼进行比对，如果该人工鱼的适应度参数大于公告板上的人工鱼的适应度参数，则用该人工鱼的编号替换公告板上的人工鱼的编号，否则，保持公告板上的人工鱼编号不变。

在对人工鱼群执行完觅食、聚群、追尾、随机行为后，对于人工鱼群中连续N

新生成的人工鱼与人工鱼群中未淘汰的人工鱼构成新的人工鱼群，继续参与后续算法迭代。

上述淘汰行为在不会增加算法复杂度的基础上可以有效提高算法的效率。

在人工鱼群算法中，视野Visual参数决定了人工鱼的搜索范围。传统的人工鱼群采用的是固定视野，没有考虑鱼群中不同人工鱼的分布特点以及与最优人工鱼之间的相对位置，导致搜索能力受限。为了提高人工鱼的搜索能力，人工鱼X的视野满足以下公式：

其中，与最优人工鱼之间距离较远的人工鱼具有较大的视野，提高全局搜索能力；与最优人工鱼之间距离较近的人工鱼具有较小的视野，提高搜索精度。

人工鱼群在执行觅食、聚群、追尾、随机行为时，判断迭代终止的条件包括以下：连续多次所得值的均方差小于允许的误差；或判断聚集于某个区域的人工鱼的数目达到某个比例；或连续多次所得的均值不超过已寻找的极值；或限制最大迭代次数。若满足终止条件，则输出公告牌的最优人工鱼的编号，该最优人工鱼编号对应的调度方案即为最优的调度方案；否则继续迭代。

本实施例将人工鱼群算法用于多农机调度作业中，人工鱼群算法具有较强的收敛能力，对初始值适应性强，具有并发性强、效率高、收敛能力强等特点，特别适合于农机调度这种随机性强和实时性高的场景。本实施例可根据任务地块及作业农机数量，快速高效生成农机调度方案。

本发明的实施方式不限于此，按照本发明的上述内容，利用本领域的普通技术知识和惯用手段，在不脱离本发明上述基本技术思想前提下，本发明还可以做出其它多种形式的修改、替换或组合，均落在本发明权利保护范围之内。