遗传算法编码：解决死锁问题

2023-08-02 理论教育版权反馈

【摘要】：基因的第1～6行分别表示目标编号、任务编号、无人机编号、无人机能力、目标价值和无人机对目标的攻击毁伤概率。如果一个（或多个）无人机均出现这种现象，就会出现无限等待导致“死锁”的情况。为了避免出现“死锁”，就将任务时序信息引入编码过程。由此，编码形成的染色体可以避免“死锁”的情况。

遗传算法编码就是将组合优化问题的解（即染色体）编码成矩阵的形式。每个染色体由Nc个基因组成，每个基因为染色体矩阵的一列，表示将针对某个目标的某个任务指派给某架无人机来执行。令Ta=1，2，3分别表示C、A、V任务，令Ca=1，2分别表示侦察识别功能、攻击功能。以3个无人机攻击3个目标为例，此时，染色体编码如图2-1所示。

在图2-1中，基因①、②、③分别表示侦察识别基因、攻击基因、毁伤评估基因。基因的第1～6行分别表示目标编号、任务编号、无人机编号、无人机能力、目标价值和无人机对目标的攻击毁伤概率。由以上编码方式可知：k=2时，必有Ca=2；k=1或k=3时，必有Ca=1；只有攻击基因的毁伤概率P为非零，其他基因的P均为零。

pagenumber_ebook=23,pagenumber_book=14

图2-1　多类型基因染色体编码示意图

对于某个目标，如果对其执行攻击任务的无人机j比对其执行侦察任务的无人机i先到达目标，则无人机j必须等待无人机i对目标侦察完之后才能实施攻击。如果一个（或多个）无人机均出现这种现象，就会出现无限等待导致“死锁”的情况。为了避免出现“死锁”，就将任务时序信息引入编码过程。在编码过程中，按照目标序号从小到大、任务执行顺序从前到后的排列规则生成基于目标的染色体（目标基染色体），如图2-2所示。图中，第一列的 pagenumber_ebook=23,pagenumber_book=14 表示针对目标T1执行C任务的某无人机，第二列表示针对目标T1执行A任务的某无人机，第三列表示针对目标T1执行V任务的某无人机，同行其他符号的意义可类推；表中第一列的WT1表示目标T1的威胁度，同行其他符号的意义类似；表中第二列的 pagenumber_ebook=23,pagenumber_book=14 表示u2对T1的攻击毁伤概率，同行对应于攻击任务的其他符号的意义类似。