CN118502451B - 一种改进遗传算法的空地异构多目标探测方法 - Google Patents
一种改进遗传算法的空地异构多目标探测方法 Download PDFInfo
- Publication number
- CN118502451B CN118502451B CN202410964535.4A CN202410964535A CN118502451B CN 118502451 B CN118502451 B CN 118502451B CN 202410964535 A CN202410964535 A CN 202410964535A CN 118502451 B CN118502451 B CN 118502451B
- Authority
- CN
- China
- Prior art keywords
- constraint
- unmanned aerial
- unmanned
- time
- aerial vehicle
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000001514 detection method Methods 0.000 title claims abstract description 34
- 230000002068 genetic effect Effects 0.000 title claims abstract description 17
- 238000005265 energy consumption Methods 0.000 claims abstract description 20
- 238000000034 method Methods 0.000 claims abstract description 19
- 210000000349 chromosome Anatomy 0.000 claims description 28
- 230000001133 acceleration Effects 0.000 claims description 18
- 230000035772 mutation Effects 0.000 claims description 15
- 238000005457 optimization Methods 0.000 claims description 10
- 238000006073 displacement reaction Methods 0.000 claims description 9
- 239000011159 matrix material Substances 0.000 claims description 9
- 238000006243 chemical reaction Methods 0.000 claims description 6
- 108090000623 proteins and genes Proteins 0.000 claims description 6
- 241000764238 Isis Species 0.000 claims description 3
- 238000004364 calculation method Methods 0.000 claims description 3
- 230000014759 maintenance of location Effects 0.000 claims description 3
- 230000006870 function Effects 0.000 description 21
- 241000204795 Muraena helena Species 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000008878 coupling Effects 0.000 description 1
- 238000010168 coupling process Methods 0.000 description 1
- 238000005859 coupling reaction Methods 0.000 description 1
- 238000010586 diagram Methods 0.000 description 1
- 230000007613 environmental effect Effects 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
- 230000008447 perception Effects 0.000 description 1
- 230000000007 visual effect Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/40—Control within particular dimensions
- G05D1/43—Control of position or course in two dimensions
-
- G—PHYSICS
- G05—CONTROLLING; REGULATING
- G05D—SYSTEMS FOR CONTROLLING OR REGULATING NON-ELECTRIC VARIABLES
- G05D1/00—Control of position, course, altitude or attitude of land, water, air or space vehicles, e.g. using automatic pilots
- G05D1/60—Intended control result
- G05D1/617—Safety or protection, e.g. defining protection zones around obstacles or avoiding hazards
- G05D1/622—Obstacle avoidance
-
- Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
- Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
- Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
- Y02T10/00—Road transport of goods or passengers
- Y02T10/10—Internal combustion engine [ICE] based vehicles
- Y02T10/40—Engine management systems
Landscapes
- Engineering & Computer Science (AREA)
- Aviation & Aerospace Engineering (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Automation & Control Theory (AREA)
- Investigation Of Foundation Soil And Reinforcement Of Foundation Soil By Compacting Or Drainage (AREA)
- Geophysics And Detection Of Objects (AREA)
- Control Of Position, Course, Altitude, Or Attitude Of Moving Bodies (AREA)
Abstract
本发明公开了一种改进遗传算法的空地异构多目标探测方法，包括以下步骤：（1）构建基于混合整数线性规划MILP的空地协同多目标检测任务模型，包括运动学约束、动态避碰约束、任务分配约束和任务完成约束；（2）建立的空地协同多目标探测任务模型的目标函数，包括时间最短、总时间、总能耗和航迹平滑度；（3）利用改进遗传算法求解最优解，将得出的最优解作为分支定界的输入；（4）利用分支定界法进行优化；本发明考虑运动学约束、动态避碰约束、任务分配约束和避障约束，构建了基于MILP的空地协同多目标探测任务模型，更真实、合理地描述空地协同环境覆盖问题。
Description
技术领域
本发明涉及无人机、无人车技术领域，具体涉及一种改进遗传算法的空地异构多目标探测方法。
背景技术
近些年来，凭借高效性、灵活性和强稳定性等特性，异构智能体组成的无人集群系统受到诸多研究人员的广泛关注，并在灾难救援、持续监测、航空航天等领域展现出巨大的应用潜力。无人机具备快速机动、高度灵活、视野广阔的特点，可以在空中对地面环境进行全面扫描和实时监控，尤其适用于地面障碍复杂的环境。无人地面车辆可以精准观察目标并深入复杂地形区域，携带更多负载并具有较高的持久性。无人机与地面车辆的协同合作能形成互补，通过无人机提供空中视野，地面车辆深入障碍区域，提高整个系统的环境感知与覆盖能力。
在实际应用场景中，无人机和无人车经常需要前往某些指定区域完成相关任务，这涉及到任务分配和路径规划。无人机和无人车都是智能体，运动学参数不同，功能也存在较大差异。为了解决这类优化问题，使其更接近现实，在构建模型时必须充分考虑共性和唯一性。
旅行商问题（TSP）作为最典型的任务分配模型之一，最初被用于只有无人机或只有UGV运行的场景。TSP中的城市被视为需要执行任务的目标点，城市之间的连接可以被视为路径。Murry和Chu提出了飞行伙伴旅行商模型（FSTSP）和并行无人机调度旅行商模型（PDSTSP），这是解决空地协同快递场景中最后一英里问题的理论模型。Mara提出了类似于FSTSP的无人机旅行推销员问题（TSP-D），并增加了对无人机运行里程的限制。
与TSP问题类似的车辆路径问题（Vehicle Routing Problem，VRP）也在空地协调问题中得到了应用和发展。Wang 提出了无人机车辆路径问题（VRPD），它类似于FSTSP，用于描述无人机与卡车一起交付的场景。文献引入多无人机，将模型扩展到VRPD-MD，实现了无人机和无人车的协同路径规划。此外，采用有效不等式（VIEQ）和可变邻域下降过程（ILS-VND）加速求解此类问题，提高了模型在实际应用中的可用性。
然而，旅行推销员问题（TSP）和车辆路径问题（VRP）及其变种受基本模型的限制，因此很难扩展到具有许多约束的模型。这是大多数TSP和VRP模型只能专注于快递配送问题的主要原因。与上述两个模型不同，混合整数线性规划（MILP）没有初始的基本模型，只要满足线性或整数约束，它们就可以成为MILP模型的一部分。因此，混合整数线性规划MILP模型的强扩展性使其广泛用于解决多目标优化问题。
混合整数线性规划MILP非常适合描述空地协调问题。然而，模型的适用性相对较窄，模型只在无人车携带无人机进行配送的场景中较为完整，需要一种具有广泛适用性的模型。任务规划与路径规划有强耦合关系，使得传统的遗传算法难以有效解决此类问题。
发明内容
本发明的目的是提供一种改进遗传算法的空地异构多目标探测方法，解决空地协同多目标检测任务分配和路径规划最优解的问题。
技术方案：本发明所述的一种改进遗传算法的空地异构多目标探测方法，包括以下步骤：
（1）构建基于混合整数线性规划MILP的空地协同多目标检测任务模型，包括运动学约束、动态避碰约束、任务分配约束和任务完成约束；
（2）建立的空地协同多目标探测任务模型的目标函数，包括时间最短、总时间、总能耗和航迹平滑度；
（3）利用改进遗传算法求解最优解，将得出的最优解作为分支定界的输入；
（4）利用分支定界法进行优化。
进一步的，步骤（1）具体如下：设架无人机和架无人车分别前往个目标点完成探测任务；其中，是适合无人机的目标点数量，是适合无人车的目标点数量，是和共同执行检测任务的目标点；目标点的数量满足下列公式：
（1）；
运动学约束公式如下：
(2)；
其中，是横向位移，是纵向位移，是横向速度，是纵向速度，是横向加速度，是纵向加速度，则公式（2）缩写为：
（3）；
其中，是第p个智能体在时刻t的状态矩阵，包括位移和速度，是第p个智能体在时刻t的加速度矩阵；A和B是仅由控制的系数矩阵；加速度参数状态仅由初始位置、初始速度和每一时间步长的加速度控制；
动态避碰约束公式如下：设障碍物为圆形，圆心坐标为，半径为将圆近似划分为M边形，无人机或无人车的避障约束方程如下：
；（4）
（5）；
其中，M为多边形边数，，是比大的常数，是二进制决策变量，表示第p个智能体的避障约束，值为0时，公式（4）一直成立，并且不作为约束；值为1时，表示满足约束条件即第p个智能体的位置被限制在约束范围之外；公式（5）表示第p个智能体的每个方向上，至少有一个方向的=1，第p个智能体需要避开障碍物；则第p个智能体的动态防碰撞约束描述为在每个方向上保持安全阈值的到任何其他无人机的距离；公式如下：
（6）；
（7）；
其中，，第p个智能体的位置坐标；第q个智能体的位置坐标，是比大的常数，是二进制决策变量，表示第p个智能体和第q个智能体之间的避障约束，值为1时，当前方向上满足碰撞避免约束，其他值为0即其他三个方向上不需要满足碰撞避免约束；表示设定的安全距离；
任务分配约束包括：
（S1）适合无人机的目标点，公式如下：
（8）；
其中，表示无人机数量，二进制决策变量用于表示第p个智能体在时间步长t是否需要到达目标点i；若需要，值为 1；否则，值为 0；
（S2）适合无人车的目标点，公式如下：
（9）；
其中，表示无人车数量，二进制决策变量用于表示第p个智能体在时间步长t是否需要到达目标点 i；若需要，值为 1；否则，值为 0；
（S3）适合无人机和无人车的目标点，公式如下：
（10）；
其中，表示无人机数量，表示无人车数量，二进制决策变量用于表示第p个智能体在时间步长t是否需要到达目标点i；若需要，值为 1；否则，值为 0；
任务完成约束，公式如下：
设目标点i的坐标为无人机或无人车在规定的时间t内到达目标点；无人机或无人车在时间步长t到达目标点i周围边长为的正方形内认为任务完成，公式如下：
（11）；
其中，是比大的常数，第p个智能体的位置坐标，目标点i的坐标为；无人机或无人车在规定的时间t内到达目标点。
进一步的，步骤（2）包括以下步骤：
（21）时间最短是检测到最后一个目标点时所消耗的总时间最短的时间，公式如下：
（12）；
其中，表示最长全局时间，是优化函数，通过比较约束和最小目标函数，以线性方式描述最小化时间；
（22）总时间等于每架无人机和无人车完成任务的时间成本之和，公式如下：
（13）；
其中， 表示第个智能体完成所有任务的时间，是优化函数；
（23）总能耗为在恒定速度下总能量消耗目标，公式如下：
（14）；
其中，为比例系数，用于能耗和时间的量纲转换，用于调整第p个无人机在时间步长t的水平速度和垂直速度的总能耗的比例；
（24）构建轨迹平滑度的约束：
（15）；
其中，为比例系数，用于能耗和时间的量纲转换，用于调整轨迹平滑性损失在目标函数中的比例；和分别表示在时间步长t处第p个无人机的横向加速度和垂直加速度。
进一步的，步骤（3）包括以下步骤：
（31）使用整数编码将每个无人机和无人车的任务顺序编码成染色体，初始化种群，随机生成初始染色体集合；其中，根据给定的种群规模选择概率、交叉概率、变异概率和最大进化代数初始化种群；染色体编码为两层结构：第一层表示所有目标点的执行顺序；第二层表示执行相应目标点检测任务的无人车或者无人车的ID号；若目标点总数为，需要同时被无人机和无人地面车检测的目标点数为，则染色体长度为；
（32）计算每条染色体的目标函数值，并作为适应度值；使用算法为解码后的每个无人机或者无人车规划路径；适应度函数公式如下：
；（16）
其中，代表种群中每个无人机和无人车个体，表示总的目标函数，；
（33）使用精英保留策略，即保留适应度更高的个体；从群体中随机选择k个体，将其中适应度最高的个体保存到下一代，重复执行，直到保存到下一代的个体数达到预先设定的数量为止；选择概率计算公式为：
（17）；
其中，代表种群规模，即无人车和无人机个体总数；
（34）根据交叉概率从种群中选择两个染色体，随机确定染色体上的交叉位置，对基因码进行交叉操作；
（35）根据变异概率在种群中随机选择需要变异的个体，然后染色体上随机选择两个变异位置，交换这两个位置上的基因；
（36）将选择出的父代染色体与交叉和变异操作生成的后代染色体合并，形成新一代种群，计算新一代的适应度值，并判断当前代的最优结果是否满足终止迭代条件，如果不满足，则重复步骤（33）-步骤（35）。
进一步的，步骤（4）具体如下：设得出的最优解为当分支定界的解空间B不为空时：从解空间B中选择一个分支检查分支是否可行，如果可行，找到分支的最优解，若比差，则修剪，将更新为；如果满足问题A的整数解要求，则为最优解，退出循环。
有益效果：与现有技术相比，本发明具有如下显著优点：考虑运动学约束、动态避碰约束、任务分配约束和避障约束，构建了基于MILP的空地协同多目标探测任务模型，更真实、合理地描述空地协同环境覆盖问题；提出了一种综合考虑任务完成时间、运行过程中的能量消耗以及路径轨迹平滑性的目标函数，以获得空地协同多目标探测任务分配和路径规划的最优解。提出了一种结合改进遗传算法（IGA-B&B）的分支定界法对目标函数进行求解，得到了空地协同多目标检测的最优任务分配和最优路径。该方法通过对遗传算法中染色体属性和遗传操作的调整，使改进的遗传算法更适合模型，加快了运算速度。
附图说明
图1为本发明的总体流程图；
图2为本发明的障碍物圆形描述图；
图3为本发明的无人机在防碰撞约束中的四个方向；
图4为本发明的目标点任务完成约束示意图。
具体实施方式
下面结合附图对本发明的技术方案作进一步说明。
如图1所示，本发明实施例提供一种改进遗传算法的空地异构多目标探测方法，包括以下步骤：
（1）构建基于混合整数线性规划MILP的空地协同多目标检测任务模型，包括运动学约束、动态避碰约束、任务分配约束和任务完成约束；步骤（1）具体如下：设架无人机和架无人车分别前往个目标点完成探测任务；其中，是适合无人机的目标点数量，是适合无人车的目标点数量，是和共同执行检测任务的目标点；目标点的数量满足下列公式：
（1）；
运动学约束公式如下：
(2)；
其中，是横向位移，是纵向位移，是横向速度，是纵向速度，是横向加速度，是纵向加速度，则公式（2）缩写为：
（3）；
其中，是第p个智能体在时刻t的状态矩阵，包括位移和速度，是第p个智能体在时刻t的加速度矩阵；A和B是仅由控制的系数矩阵；加速度参数状态仅由初始位置、初始速度和每一时间步长的加速度控制；
如图2和图3所示，动态避碰约束公式如下：设障碍物为圆形，圆心坐标为，半径为将圆近似划分为M边形，无人机或无人车的避障约束方程如下：
；（4）
（5）；
其中，M为多边形边数，，是比大的常数，是二进制决策变量，表示第p个智能体的避障约束，值为0时，公式（4）一直成立，并且不作为约束；值为1时，表示满足约束条件即第p个智能体的位置被限制在约束范围之外；公式（5）表示第p个智能体的每个方向上，至少有一个方向的=1，第p个智能体需要避开障碍物；则第p个智能体的动态防碰撞约束描述为在每个方向上保持安全阈值的到任何其他无人机的距离；公式如下：
（6）；
（7）；
其中，，第p个智能体的位置坐标；第q个智能体的位置坐标，是比大的常数，是二进制决策变量，表示第p个智能体和第q个智能体之间的避障约束，值为1时，当前方向上满足碰撞避免约束，其他值为0即其他三个方向上不需要满足碰撞避免约束；表示设定的安全距离；
任务分配约束包括：
（S1）适合无人机的目标点，公式如下：
（8）；
其中，表示无人机数量，二进制决策变量用于表示第p个智能体在时间步长t是否需要到达目标点i；若需要，值为 1；否则，值为 0；
（S2）适合无人车的目标点，公式如下：
（9）；
其中，表示无人车数量，二进制决策变量用于表示第p个智能体在时间步长t是否需要到达目标点i；若需要，值为 1；否则，值为 0；
（S3）适合无人机和无人车的目标点，公式如下：
（10）；
其中，表示无人机数量，表示无人车数量，二进制决策变量用于表示第p个智能体在时间步长t是否需要到达目标点i；若需要，值为 1；否则，值为 0；
如图4所示，任务完成约束，公式如下：
设目标点i的坐标为无人机或无人车在规定的时间t内到达目标点；无人机或无人车在时间步长t到达目标点i周围边长为的正方形内认为任务完成，公式如下：
（11）；
其中，是比大的常数，第p个智能体的位置坐标，目标点i的坐标为；无人机或无人车在规定的时间t内到达目标点。
（2）建立的空地协同多目标探测任务模型的目标函数，包括时间最短、总时间、总能耗和航迹平滑度；包括以下步骤：
（21）时间最短是检测到最后一个目标点时所消耗的总时间最短的时间，公式如下：
（12）；
其中，表示最长全局时间，是优化函数，通过比较约束和最小目标函数，以线性方式描述最小化时间；
（22）总时间等于每架无人机和无人车完成任务的时间成本之和，公式如下：
（13）；
其中， 表示第个智能体完成所有任务的时间，是优化函数；
（23）总能耗为在恒定速度下总能量消耗目标，公式如下：
（14）；
其中，为比例系数，用于能耗和时间的量纲转换，用于调整第p个无人机在时间步长t的水平速度和垂直速度的总能耗的比例；
（24）构建轨迹平滑度的约束：
（15）；
其中，为比例系数，用于能耗和时间的量纲转换，用于调整轨迹平滑性损失在目标函数中的比例；和分别表示在时间步长t处第p个无人机的横向加速度和垂直加速度。
（3）利用改进遗传算法求解最优解，将得出的最优解作为分支定界的输入；包括以下步骤：
（31）使用整数编码将每个无人机和无人车的任务顺序编码成染色体，初始化种群，随机生成初始染色体集合；其中，根据给定的种群规模选择概率、交叉概率、变异概率和最大进化代数初始化种群；染色体编码为两层结构：第一层表示所有目标点的执行顺序；第二层表示执行相应目标点检测任务的无人车或者无人车的ID号；若目标点总数为，需要同时被无人机和无人地面车检测的目标点数为，则染色体长度为；
（32）计算每条染色体的目标函数值，并作为适应度值；使用算法为解码后的每个无人机或者无人车规划路径；适应度函数公式如下：
；（16）
其中，代表种群中每个无人机和无人车个体，表示总的目标函数，；
（33）使用精英保留策略，即保留适应度更高的个体；从群体中随机选择k个体，将其中适应度最高的个体保存到下一代，重复执行，直到保存到下一代的个体数达到预先设定的数量为止；选择概率计算公式为：
（17）；
其中，代表种群规模，即无人车和无人机个体总数；
（34）根据交叉概率从种群中选择两个染色体，随机确定染色体上的交叉位置，对基因码进行交叉操作；
（35）根据变异概率在种群中随机选择需要变异的个体，然后染色体上随机选择两个变异位置，交换这两个位置上的基因；
（36）将选择出的父代染色体与交叉和变异操作生成的后代染色体合并，形成新一代种群，计算新一代的适应度值，并判断当前代的最优结果是否满足终止迭代条件，如果不满足，则重复步骤（33）-步骤（35）。
（4）利用分支定界法进行优化。具体如下：设得出的最优解为当分支定界的解空间B不为空时：从解空间B中选择一个分支检查分支是否可行，如果可行，找到分支的最优解，若比差，则修剪，将更新为；如果满足问题A的整数解要求，则为最优解，退出循环。
Claims (1)
1.一种改进遗传算法的空地异构多目标探测方法，其特征在于，包括以下步骤：
（1）构建基于混合整数线性规划MILP的空地协同多目标检测任务模型，包括运动学约束、动态避碰约束、任务分配约束和任务完成约束；具体如下：设架无人机和架无人车分别前往个目标点完成探测任务；其中，是适合无人机的目标点数量，是适合无人车的目标点数量，是和共同执行检测任务的目标点；目标点的数量满足下列公式：
（1）；
运动学约束公式如下：
(2)；
其中，是横向位移，是纵向位移，是横向速度，是纵向速度，是横向加速度，是纵向加速度，则公式（2）缩写为：
（3）；
其中，是第p个智能体在时刻t的状态矩阵，包括位移和速度，是第p个智能体在时刻t的加速度矩阵；A和B是仅由控制的系数矩阵；加速度参数状态仅由初始位置、初始速度和每一时间步长的加速度控制；
动态避碰约束公式如下：设障碍物为圆形，圆心坐标为，半径为将圆近似划分为M边形，无人机或无人车的避障约束方程如下：
；（4）
（5）；
其中，M为多边形边数，，是比大的常数，是二进制决策变量，表示第p个智能体的避障约束，值为0时，公式（4）一直成立，并且不作为约束；值为1时，表示满足约束条件即第p个智能体的位置被限制在约束范围之外；公式（5）表示第p个智能体的每个方向上，至少有一个方向的=1，第p个智能体需要避开障碍物；则第p个智能体的动态防碰撞约束描述为在每个方向上保持安全阈值的到任何其他无人机的距离；公式如下：
（6）；
（7）；
其中，，第p个智能体的位置坐标；第q个智能体的位置坐标，是比大的常数，是二进制决策变量，表示第p个智能体和第q个智能体之间的避障约束，值为1时，当前方向上满足碰撞避免约束，其他值为0即其他三个方向上不需要满足碰撞避免约束；表示设定的安全距离；
任务分配约束包括：
（S1）适合无人机的目标点，公式如下：
（8）；
其中，表示无人机数量，二进制决策变量用于表示第p个智能体在时间步长t是否需要到达目标点i；若需要，值为 1；否则，值为 0；
（S2）适合无人车的目标点，公式如下：
（9）；
其中，表示无人车数量，二进制决策变量用于表示第p个智能体在时间步长t是否需要到达目标点i；若需要，值为 1；否则，值为 0；
（S3）适合无人机和无人车的目标点，公式如下：
（10）；
其中，表示无人机数量，表示无人车数量，二进制决策变量用于表示第p个智能体在时间步长t是否需要到达目标点i；若需要，值为 1；否则，值为 0；
任务完成约束，公式如下：
设目标点i的坐标为无人机或无人车在规定的时间t内到达目标点；无人机或无人车在时间步长t到达目标点i周围边长为的正方形内认为任务完成，公式如下：
（11）；
其中，是比大的常数，第p个智能体的位置坐标，目标点i的坐标为；无人机或无人车在规定的时间t内到达目标点；
（2）建立的空地协同多目标探测任务模型的目标函数，包括时间最短、总时间、总能耗和航迹平滑度；包括以下步骤：
（21）时间最短是检测到最后一个目标点时所消耗的总时间最短的时间，公式如下：
（12）；
其中，表示最长全局时间，是优化函数，通过比较约束和最小目标函数，以线性方式描述最小化时间；
（22）总时间等于每架无人机和无人车完成任务的时间成本之和，公式如下：
（13）；
其中， 表示第p个智能体完成所有任务的时间，是优化函数；
（23）总能耗为在恒定速度下总能量消耗目标，公式如下：
（14）；
其中，为比例系数，用于能耗和时间的量纲转换，用于调整第p个无人机在时间步长t的水平速度和垂直速度的总能耗的比例；
（24）构建轨迹平滑度的约束：
（15）；
其中，为比例系数，用于能耗和时间的量纲转换，用于调整轨迹平滑性损失在目标函数中的比例；和分别表示在时间步长t处第p个无人机的横向加速度和垂直加速度；
（3）利用改进遗传算法求解最优解，将得出的最优解作为分支定界的输入；包括以下步骤：
（31）使用整数编码将每个无人机和无人车的任务顺序编码成染色体，初始化种群，随机生成初始染色体集合；其中，根据给定的种群规模、选择概率、交叉概率、变异概率和最大进化代数初始化种群；染色体编码为两层结构：第一层表示所有目标点的执行顺序；第二层表示执行相应目标点检测任务的无人车或者无人车的ID号；若目标点总数为，需要同时被无人机和无人地面车检测的目标点数为，则染色体长度为；
（32）计算每条染色体的目标函数值，并作为适应度值；使用算法为解码后的每个无人机或者无人车规划路径；适应度函数公式如下：
；（16）
其中，代表种群中每个无人机和无人车个体，表示总的目标函数，；
（33）使用精英保留策略，即保留适应度更高的个体；从群体中随机选择k个体，将其中适应度最高的个体保存到下一代，重复执行，直到保存到下一代的个体数达到预先设定的数量为止；选择概率计算公式为：
（17）；
其中，代表种群规模，即无人车和无人机个体总数；
（34）根据交叉概率从种群中选择两个染色体，随机确定染色体上的交叉位置，对基因码进行交叉操作；
（35）根据变异概率在种群中随机选择需要变异的个体，然后染色体上随机选择两个变异位置，交换这两个位置上的基因；
（36）将选择出的父代染色体与交叉和变异操作生成的后代染色体合并，形成新一代种群，计算新一代的适应度值，并判断当前代的最优结果是否满足终止迭代条件，如果不满足，则重复步骤（33）-步骤（35）；
（4）利用分支定界法进行优化；）具体如下：设得出的最优解为当分支定界的解空间B不为空时：从解空间B中选择一个分支检查分支是否可行，如果可行，找到分支的最优解，若比差，则修剪，将更新为；如果满足问题A的整数解要求，则为最优解，退出循环。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410964535.4A CN118502451B (zh) | 2024-07-18 | 2024-07-18 | 一种改进遗传算法的空地异构多目标探测方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410964535.4A CN118502451B (zh) | 2024-07-18 | 2024-07-18 | 一种改进遗传算法的空地异构多目标探测方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN118502451A CN118502451A (zh) | 2024-08-16 |
| CN118502451B true CN118502451B (zh) | 2024-09-24 |
Family
ID=92245046
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202410964535.4A Active CN118502451B (zh) | 2024-07-18 | 2024-07-18 | 一种改进遗传算法的空地异构多目标探测方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN118502451B (zh) |
Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113592319A (zh) * | 2021-08-04 | 2021-11-02 | 清华大学 | 基于insga-ⅱ的复杂约束下的柔性作业车间调度方法及装置 |
| CN115808933A (zh) * | 2022-11-30 | 2023-03-17 | 南京信息工程大学 | 一种基于量子海鸥算法的无人机路径规划方法 |
Family Cites Families (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| ATE243409T1 (de) * | 2000-03-01 | 2003-07-15 | Om Partners Hortica | Verfahren zur kombinatorischen optimierung von pflanzen- und tierzucht |
| JP7442070B2 (ja) * | 2019-01-31 | 2024-03-04 | パナソニックＩｐマネジメント株式会社 | 清掃ルート決定装置及び清掃ルート決定方法 |
| CN114567006A (zh) * | 2022-03-02 | 2022-05-31 | 国网浙江省电力有限公司电力科学研究院 | 一种配电网多目标优化运行方法及系统 |
| CN116257082B (zh) * | 2022-11-03 | 2023-09-22 | 天津大学 | 多无人机分布式主动协同探测方法 |
| CN117389277A (zh) * | 2023-11-07 | 2024-01-12 | 大连海事大学 | 基于多轮循环策略的异构多机器人协同海域勘探方法 |
-
2024
- 2024-07-18 CN CN202410964535.4A patent/CN118502451B/zh active Active
Patent Citations (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN113592319A (zh) * | 2021-08-04 | 2021-11-02 | 清华大学 | 基于insga-ⅱ的复杂约束下的柔性作业车间调度方法及装置 |
| CN115808933A (zh) * | 2022-11-30 | 2023-03-17 | 南京信息工程大学 | 一种基于量子海鸥算法的无人机路径规划方法 |
Also Published As
| Publication number | Publication date |
|---|---|
| CN118502451A (zh) | 2024-08-16 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Ropero et al. | TERRA: A path planning algorithm for cooperative UGV–UAV exploration | |
| Obermeyer | Path planning for a UAV performing reconnaissance of static ground targets in terrain | |
| CN108664022B (zh) | 一种基于拓扑地图的机器人路径规划方法及系统 | |
| Ergezer et al. | 3D path planning for multiple UAVs for maximum information collection | |
| CN111337931B (zh) | 一种auv目标搜索方法 | |
| CN111664852B (zh) | 一种无人机路径规划方法及装置 | |
| Kala et al. | Planning of multiple autonomous vehicles using rrt | |
| CN111142542A (zh) | 一种基于vfh*局部路径规划方法的全向移动机器人自主导航系统 | |
| CN115033016B (zh) | 一种异构无人集群编队避障方法及系统 | |
| Geng et al. | UAV surveillance mission planning with gimbaled sensors | |
| Huang et al. | A novel hybrid discrete grey wolf optimizer algorithm for multi-UAV path planning | |
| CN111880534A (zh) | 一种基于栅格地图的二次路径规划方法 | |
| Gao et al. | Path planning algorithm of robot arm based on improved RRT* and BP neural network algorithm | |
| Ghambari et al. | An enhanced NSGA-II for multiobjective UAV path planning in urban environments | |
| Sartori et al. | An efficient approach to near-optimal 3D trajectory design in cluttered environments for multirotor UAVs | |
| Golabi et al. | Bypassing or flying above the obstacles? A novel multi-objective UAV path planning problem | |
| Yu et al. | Reinforcement learning-based differential evolution algorithm for constrained multi-objective optimization problems | |
| Kareem et al. | Planning the Optimal 3D Quadcopter Trajectory Using a Delivery System-Based Hybrid Algorithm. | |
| Zhao et al. | Research on logistics distribution route based on multi-objective sorting genetic algorithm | |
| Xiang et al. | An effective memetic algorithm for UAV routing and orientation under uncertain navigation environments | |
| Bouraine et al. | Safe motion planning based on a new encoding technique for tree expansion using particle swarm optimization | |
| CN118502451B (zh) | 一种改进遗传算法的空地异构多目标探测方法 | |
| Zhou et al. | A novel mission planning method for UAVs’ course of action | |
| CN117829523A (zh) | 面向区域目标的数传与成像联合调度多星任务规划方法 | |
| de Carvalho Santos et al. | An exploratory path planning method based on genetic algorithm for autonomous mobile robots |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |