基于遗传算法的多水面无人艇区域协同探测任务分配方法与流程

1.本发明涉及一种多水面无人艇区域协同探测任务分配方法，特别是一种基于遗传算法的多水面无人艇区域协同探测任务分配方法，属于水面无人艇任务规划领域。

背景技术：

2.水面无人艇是一个拥有自主运行能力的小型水面任务平台，主要用于执行危险以及不适于有人船只执行的任务。随着无人艇的快速发展，其在军事和民用领域都展现出了良好的发展前景。多水面无人艇的任务分配是水面无人艇任务规划的重要组成部分，是多水面无人艇集协同完成任务的重要环节。
3.多水面无人艇区域探测任务是指给定一个未知区域，利用多种无人艇携带的探测载荷，对区域内的目标进行探测。如何分配每个艇的探测区域，及对该区域的探测次数，可以使多无人艇的区域探测覆盖率及目标探测概率不低于任务要求，同时保证时间最优，是多水面无人艇区域协同探测任务规划需要研究的重要问题。
4.目前对区域探测的任务分配算法未考虑探测载荷的探测盲区及对目标的探测概率，不能适应实际任务执行的需要。同时，目前区域协同搜索均为任务区域的均衡覆盖搜索，并且认为任务载荷对目标的探测概率是100％。但是在实际执行任务过程中会派出不同类型的无人艇协同作业，其携带的载荷探测能力不同，对目标的探测概率不同。例如，不同声纳对水下目标的探测能力不同，一次探测对目标的发现概率不是100％。遗传算法是一种智能寻优方法，将自然界中生物的遗传理论和“优胜劣汰，适者生存”的自然选择理论作为基础，构成的一种寻最优解的算法,具有鲁棒性好、不易陷入局部最优等优势。

技术实现要素：

5.本发明要解决的技术问题是：在进行多水面无人艇协同区域探测任务的任务分配时，考虑任务载荷的探测范围、探测盲区、探测概率等约束，寻多水面无人艇最优任务分配策略，提升多水面无人艇协同区域探测效率。
6.为了解决上述技术问题，本发明的技术方案是提供了一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，包括以下步骤：
7.步骤1、获取探测任务区域参数；
8.步骤2、获取区域探测任务相关任务约束；
9.步骤3、基于探测任务区域参数和区域探测任务相关任务约束获得目标函数，最终目标为寻n个水面无人艇的探测区域及对该区域的探测次数，使n个不同类型的水面无人艇以最短时间完成对任务区域的探测，且探测覆盖率以及对目标的发现概率大于探测任务区域参数中的预设的值；
10.步骤4、采用遗传算法对步骤3的目标函数进行求解，最终解为每个水面无人艇的任务分配结果。
11.优选地，步骤1中，获取的探测任务区域参数包括探测区域面积s、区域探测覆盖率
p及探测目标期望概率p
t
。
12.优选地，步骤2中，区域探测任务相关任务约束，包括：
13.执行任务的水面无人艇数量n；
14.执行任务的水面无人艇最大作业时间t
max
；
15.执行任务水面无人艇的最大探测航速：v
1max
,
2max
,
…
,
nmax
；
16.执行任务水面无人艇的探测范围：l1,l2,
…
,ln；
17.执行任务水面无人艇的探测盲区：d1,d2,
…
,dn；
18.执行任务水面无人艇对探测目标的探测概率：p
t1
,p
t2
,
…
,p
tn
。
19.优选地，步骤s3中，所得到的目标函数为：
20.n1+n2+
…
+nn≥s*p
[0021][0022][0023]
其中：ni表示第i个水面无人艇的探测区域大小，i＝1,2,
…
,n；m
di
表示为满足对探测目标的期望发现概率所需探测的次数；表示为了弥补探测盲区所需的探测次数；mi表示第i个水面无人艇对探测区域ni的总探测次数，mi数值向上取整；表示组合数，即从mi个元素中取出一个元素的组合个数。
[0024]
优选地，步骤3中，所述目标函数的最终目标为：寻n个水面无人艇的探测区域[n1,n2,
…
,nn]及对该区域的探测次数[m1,m2,
…
,mn]，使n个不同类型的水面无人艇以最短时间完成对任务区域的探测，且探测覆盖率大于等于p，对目标的发现概率大于等于p
t
。
[0025]
优选地，步骤4中，最终解为每个水面无人艇的任务分配结果，即：每个水面无人艇的探测区域[n1,n2,
…
,nn]及对该区域的探测次数[m1,m2,
…
,mn]。
[0026]
优选地，所述步骤4包括以下步骤：
[0027]
步骤401、随机产生初始种；
[0028]
步骤402、计算初始种中的个体适应度，通过探测时间衡量种中个体的适应；
[0029]
步骤403、计保存最佳初始种个体：
[0030]
根据适应度函数的计算值，取最大的适应度值的个体作为最佳个体；
[0031]
s404、进行繁殖，迭代寻最优解。
[0032]
优选地，所述步骤401中，在所述初始种中随机产生g个个体，并对每个个体中的基因按顺序进行编码，每个个体满足：
[0033]
n1+n2+
…
+nn≥s*p
[0034][0035][0036]vi
≤v
imax
[0037]
[0038]
式中，vi表示第i个水面无人艇的探测速度。
[0039]
得到父代种如下式所述：
[0040][0041]
其中，[n1,n2,
…
,nn]和[m1,m2,
…
,mn]为一条染体，即一个个体，ni和mi表示染体上的一个基因。
[0042]
优选地，所述步骤402中，第i个基因的适应度为：
[0043]
f(i)＝1/((ni*mi)/(vi*li))
[0044]
个体的适应度取个体中所有基因适应度的最小值,即：
[0045]
f＝min(f(1),f(2),
…
,f(n))。
[0046]
优选地，所述步骤404包括以下步骤：
[0047]
步骤4041、选择操作：
[0048]
采用赌盘原理，实现选择操作，具体包括以下步骤：
[0049]
a)将之前计算出的全部个体的适应度值进行累加，得到总的适应度的值；
[0050]
b)随机选择一个数，使这个数在零到总适应度之间的区间内；
[0051]
c)按顺序从第一个个体的适应度开始逐步累加，直到到累加后的适应度比选择的数高为止；
[0052]
d)将截止位置的所有个体添加到繁殖种中去；
[0053]
步骤4042、交叉操作
[0054]
采用多点交叉的方式完成交叉操作：随机选取两个个体进行配对，如果种个数为奇数，则剩下的最后一个个体不进行交叉操作；在个体的基因编码中任意选择一个交叉点，将配对个体在交叉点之后的内容完成交换，接着判断交叉后的个体是否满足约束条件，如果不满足则对交叉的内容进行变异，直至满足约束条件；
[0055]
步骤4043、变异操作
[0056]
随机选择个体中的基因作为个体的变异基因，对于变异基因，用另外一个随机生成的基因将其替换，变异之后判断个体是否满足约束条件，如果不满足则继续对该基因进行变异，直至满足约束条件。
[0057]
步骤4044、计算子代中每个个体适应度：依据步骤402中的方法计算子代个体的适应度；
[0058]
步骤4045、更新种总的适应度，用于利用赌进行选择，其中，种总的适应度为种中每个个体适应度值的累加和；
[0059]
步骤4046、保存子代最佳个体；
[0060]
步骤4047、将子代内容更新到父代中，该子代作为下一代的父代；
[0061]
步骤4048、更新最佳个体，更新繁殖代数。
[0062]
步骤4049、判断是否到达终止条件，如果达到终止条件则输出最佳个体，如果没有达到终止条件则继续进行步骤s4041的流程。
[0063]
本发明针对多水面无人艇区域探测任务，考虑不同类型水面无人艇的航行性能和探测能力，利用遗传算法，为每个水面无人艇分配探测区域，并保证探测效率，使整个多水面无人艇编队探测效率最高。
附图说明
[0064]
图1为本发明的多水面无人艇区域协同探测任务分配整体算法流程图；
[0065]
图2为本发明的一种基于遗传算法的多水面无人艇区域协同探测任务分配方法的详细算法流程图。
具体实施方式
[0066]
下面结合具体实施例，进一步阐述本发明。应理解，这些实施例仅用于说明本发明而不用于限制本发明的范围。此外应理解，在阅读了本发明讲授的内容之后，本领域技术人员可以对本发明作各种改动或修改，这些等价形式同样落于本技术所附权利要求书所限定的范围。
[0067]
本实施例公开了一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，包括以下步骤：
[0068]
s1：获取区域探测任务区域端点经纬度坐标，计算探测区域面积s。根据任务指令得到区域探测覆盖率p及探测目标期望概率p
t
，探测目标期望概率p
t
表示对目标的期望发现概率。
[0069]
s2：获取区域探测任务相关任务约束，包括：
[0070]
执行任务的水面无人艇数量n；
[0071]
执行任务的水面无人艇最大作业时间(根据续航力获取)t
max
；
[0072]
执行任务水面无人艇的最大探测航速：v
1max
,v
2max
,
…
,v
nmax
；
[0073]
执行任务水面无人艇的探测范围：l1,l2,
…
,ln；
[0074]
执行任务水面无人艇的探测盲区：d1,d2,
…
,dn；
[0075]
执行任务水面无人艇对探测目标的探测概率：p
t1
,p
t2
,
…
,p
tn
。
[0076]
s3：根据探测任务区域和水面无人艇任务执行约束，得到目标函数：
[0077]
n1+n2+
…
+nn≥s*p
[0078][0079][0080]
其中：ni表示第i个水面无人艇的探测区域大小，i＝1,2,
…
,n；m
di
表示为满足对探测目标的期望发现概率所需探测的次数；表示为了弥补探测盲区所需的探测次数；mi表示第i个水面无人艇对探测区域ni的总探测次数，mi数值向上取整；表示组合数，即从mi个元素中取出一个元素的组合个数。对目标的探测概率通过二项分布得到，即每一次探测，探测到目标的概率为p
ti
，探测mi次，探测到目标的概率为
[0081]
最终目标即：寻n个水面无人艇的探测区域[n1,n2,
…
,nn]及对该区域的探测次数[m1,m2,
…
,mn]，使n个不同类型的水面无人艇以最短时间完成对任务区域的探测，且探测覆盖率大于等于p，对目标的发现概率大于等于p
t
。
[0082]
s4：采用遗传算法进行求解，最终解为每个水面无人艇的任务分配结果，即：每个水面无人艇的探测区域[n1,n2,
…
,nn]及对该区域的探测次数[m1,m2,
…
,mn]，具体包括以下
步骤：
[0083]
s4.1随机产生初始种(即父代)，随机产生g个个体，并对每个个体中的基因按顺序进行编码，每个个体满足：
[0084]
n1+n2+
…
+nn≥s*p
[0085][0086][0087]vi
≤v
imax
[0088][0089]
式中，vi表示第i个水面无人艇的探测速度。
[0090]
得到父代种：
[0091][0092]
其中，种由个体组成，[n1,n2,
…
,nn]和[m1,m2,
…
,mn]为一条染体，即一个个体，ni和mi表示染体上的一个基因。
[0093]
s4.2计算父代个体适应度，通过探测时间衡量种中个体的适应度，即个体探测的时间越少，个体适应度越高，被遗传到下一代的概率也越高，第i个基因的适应度为：
[0094]
f(i)＝1/((ni*mi)/(vi*li))
[0095]
个体的适应度取个体中所有基因适应度的最小值,即：
[0096]
f＝min(f(1),f(2),
…
,f(n))
[0097]
s4.3保存最佳父代个体
[0098]
根据适应度函数的计算值，取最大的适应度值的个体作为最佳个体。
[0099]
s4.4进行繁殖，迭代寻最优解，具体包括以下步骤：
[0100]
s4.4.1选择操作
[0101]
选择算子相当于对体中的个体执行优胜劣汰、适者生存的运算，它基于在上一步对个体适应度的计算，以一定的几率将种中的个体遗传到子代种中，其中适应度高的个体遗传到子代的几率大，适应度低的个体遗传到子代的几率小。
[0102]
在选择操作中采用比例选择算子。
[0103]
利用赌盘原理，实现遗传算法的选择操作的过程是：
[0104]
(1)将之前计算出的全部个体的适应度值进行累加，得到总的适应度的值。
[0105]
(2)随机选择一个数，使这个数在零到总适应度之间的区间内。这一步相当于确定了赌盘指针停止的位置。
[0106]
(3)按顺序从第一个个体的适应度开始逐步累加，直到到累加后的适应度比选择的数高为止。
[0107]
(4)将截止位置的所有个体到繁殖种中去。繁殖种之后要完成的交叉、变异等运算。
[0108]
这种方法符合自然选择机制，既保留了大量优良个体，又能够维持种中个体的
多样性和丰富性。
[0109]
s4.4.2交叉操作
[0110]
在遗传算法中，交叉运算就是将已经配对的染体的基因片段完成相互交换，这样就能够产生全新的个体，交叉运算是生成新个体的重要方式，对扩大遗传算法的搜寻范围起重要作用。
[0111]
采用多点交叉的方式完成交叉操作。随机选取两个个体进行配对，如果种个数为奇数，则剩下的最后一个个体不进行交叉操作。在个体的基因编码中任意选择一个交叉点，将配对个体在交叉点之后的内容完成交换，接着判断交叉后的个体是否满足约束条件，如果不满足则对交叉的内容进行变异，直至满足约束条件。
[0112]
s4.4.3变异操作
[0113]
变异运算是生成新个体的辅助方式，不过其同样是不能缺少的，因为变异算子能够增强遗传算法的局部搜索性能，同时也能够保持种中个体的丰富性，预防早熟现象的发生。
[0114]
随机选择个体中的基因作为个体的变异基因，对于变异基因，用另外一个随机生成的基因将其替换，变异之后判断个体是否满足约束条件，如果不满足则继续对该基因进行变异，直至满足约束条件。
[0115]
一般情况下变异的概率为：0.0001～0.1。变异算子在增加体的多样性方面发挥决定性的作用。
[0116]
s4.4.4计算子代中每个个体适应度：依据步骤s4.2中的方法计算子代个体的适应度。
[0117]
s4.4.5更新种总的适应度，用于利用赌进行选择。
[0118]
种总的适应度为种中每个个体适应度值的累加和。
[0119]
s4.4.6保存子代最佳个体。
[0120]
s4.4.7将子代内容更新到父代中，该子代作为下一代的父代。
[0121]
s4.4.8更新最佳个体，更新繁殖代数。
[0122]
s4.4.9判断是否到达终止条件，如果达到终止条件则输出最佳个体，如果没有达到终止条件则继续进行步骤s4.4.1的流程。
[0123]
遗传算法的终止条件采用最大遗传代数，在遗传算法执行到最大遗传代数后将最优解进行输出。最大代数的取值通常为100～1000，本发明中最大遗传代数选择200。
[0124]
本发明考虑多水面无人艇在执行区域探测任务时任务载荷存在盲区且对目标的发现概率不是100％，针对不同类型水面无人艇的航行性能和探测能力，通过遗传算法计算得到多水面无人艇执行区域探测任务的最优分配策略，提升在实际作战任务环境下的多水面无人艇协同探测效率。

技术特征：

1.一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，包括以下步骤：步骤1、获取探测任务区域参数；步骤2、获取区域探测任务相关任务约束；步骤3、基于探测任务区域参数和区域探测任务相关任务约束获得目标函数，最终目标为寻n个水面无人艇的探测区域及对该区域的探测次数，使n个不同类型的水面无人艇以最短时间完成对任务区域的探测，且探测覆盖率以及对目标的发现概率大于探测任务区域参数中的预设的值；步骤4、采用遗传算法对步骤3的目标函数进行求解，最终解为每个水面无人艇的任务分配结果。2.如权利要求1所述的一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，步骤1中，获取的探测任务区域参数包括探测区域面积s、区域探测覆盖率p及探测目标期望概率p
t
。3.如权利要求2所述的一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，步骤2中，区域探测任务相关任务约束，包括：执行任务的水面无人艇数量n；执行任务的水面无人艇最大作业时间t
max
；执行任务水面无人艇的最大探测航速：v
1max
，v
2max
，...，v
nmax
；执行任务水面无人艇的探测范围：l1，l2，...，l
n
；执行任务水面无人艇的探测盲区：d1，d2，...，d
n
；执行任务水面无人艇对探测目标的探测概率：p
t1
，p
t2
，...，p
tn
。4.如权利要求3所述的一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，步骤s3中，所得到的目标函数为：n1+n2+
…
+n
n
≥s*p≥s*p其中：n
i
表示第i个水面无人艇的探测区域大小，i＝1，2，...，n；m
di
表示为满足对探测目标的期望发现概率所需探测的次数；表示为了弥补探测盲区所需的探测次数；m
i
表示第i个水面无人艇对探测区域n
i
的总探测次数，m
i
数值向上取整；表示组合数，即从m
i
个元素中取出一个元素的组合个数。5.如权利要求4所述的一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，步骤3中，所述目标函数的最终目标为：寻n个水面无人艇的探测区域[n1，n2，
…
，n
n
]及对该区域的探测次数[m1，m2，
…
，m
n
]，使n个不同类型的水面无人艇以最短时间完成对任务区域的探测，且探测覆盖率大于等于p，对目标的发现概率大于等于p
t
。6.如权利要求5所述的一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，步骤4中，最终解为每个水面无人艇的任务分配结果，即：每个水面无人艇的探测区域[n1，n2，
…
，n
n
]及对该区域的探测次数[m1，m2，
…
，m
n
]。
7.如权利要求6所述的一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，所述步骤4包括以下步骤：步骤401、随机产生初始种；步骤402、计算初始种中的个体适应度，通过探测时间衡量种中个体的适应；步骤403、计保存最佳初始种个体：根据适应度函数的计算值，取最大的适应度值的个体作为最佳个体；s404、进行繁殖，迭代寻最优解。8.如权利要求7所述的一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，所述步骤401中，在所述初始种中随机产生g个个体，并对每个个体中的基因按顺序进行编码，每个个体满足：n1+n2+
…
+n
n
≥s*p≥s*pv
i
≤v
imax
式中，v
i
表示第i个水面无人艇的探测速度；得到父代种如下式所述：其中，[n1，n2，
…
，n
n
]和[m1，m2，
…
，m
n
]为一条染体，即一个个体，n
i
和m
i
表示染体上的一个基因。9.如权利要求8所述的一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，所述步骤402中，第i个基因的适应度为：f(i)＝1/((n
i
*m
i
)/(v
i
*l
i
))个体的适应度取个体中所有基因适应度的最小值，即：f＝min(f(1)，f(2)，...，f(n))。10.如权利要求9所述的一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，所述步骤404包括以下步骤：步骤4041、选择操作：采用赌盘原理，实现选择操作，具体包括以下步骤：a)将之前计算出的全部个体的适应度值进行累加，得到总的适应度的值；b)随机选择一个数，使这个数在零到总适应度之间的区间内；c)按顺序从第一个个体的适应度开始逐步累加，直到到累加后的适应度比选择的数高为止；d)将截止位置的所有个体添加到繁殖种中去；步骤4042、交叉操作采用多点交叉的方式完成交叉操作：随机选取两个个体进行配对，如果种个数为奇
数，则剩下的最后一个个体不进行交叉操作；在个体的基因编码中任意选择一个交叉点，将配对个体在交叉点之后的内容完成交换，接着判断交叉后的个体是否满足约束条件，如果不满足则对交叉的内容进行变异，直至满足约束条件；步骤4043、变异操作随机选择个体中的基因作为个体的变异基因，对于变异基因，用另外一个随机生成的基因将其替换，变异之后判断个体是否满足约束条件，如果不满足则继续对该基因进行变异，直至满足约束条件。步骤4044、计算子代中每个个体适应度：依据步骤402中的方法计算子代个体的适应度；步骤4045、更新种总的适应度，用于利用赌进行选择，其中，种总的适应度为种中每个个体适应度值的累加和；步骤4046、保存子代最佳个体；步骤4047、将子代内容更新到父代中，该子代作为下一代的父代；步骤4048、更新最佳个体，更新繁殖代数。步骤4049、判断是否到达终止条件，如果达到终止条件则输出最佳个体，如果没有达到终止条件则继续进行步骤s4041的流程。

技术总结

本发明涉及一种基于遗传算法的多水面无人艇区域协同探测任务分配算法，其特征在于，包括以下步骤：获取探测任务区域参数；获取区域探测任务相关任务约束；基于探测任务区域参数和区域探测任务相关任务约束获得目标函数；采用遗传算法对目标函数进行求解，最终解为每个水面无人艇的任务分配结果。本发明针对多水面无人艇区域探测任务，考虑不同类型水面无人艇的航行性能和探测能力，利用遗传算法，为每个水面无人艇分配探测区域，并保证探测效率，使整个多水面无人艇编队探测效率最高。使整个多水面无人艇编队探测效率最高。使整个多水面无人艇编队探测效率最高。