多策略遗传算法求解多机器人任务分配问题  

Solving MRTA problem based on multi-strategy genetic algorithm

作　　者：陈海洋[1] 刘妍 都威 黄琦 CHEN Haiyang;LIU Yan;DOU Wei;HUANG Qi(School of Electronics and Information,Xi’an Polytechnic University,Xi’an 710048,China)

机构地区：[1]西安工程大学电子信息学院,陕西西安710048

出　　处：《西安工程大学学报》2024年第6期76-82,共7页Journal of Xi’an Polytechnic University

基　　金：国家自然科学基金(51905405)。

摘　　要：针对遗传算法(genetic algorithm,GA)求解多机器人任务分配(multi-robot task allocation,MRTA)时容易陷入局部最优以及效率不高的问题,提出一种多策略遗传算法(简称DIHA-GA)实现对多个任务的合理分配。首先,采用双染色体编码策略来简化编码方式;其次,将种群分成3个部分来使种群在保持随机性的同时增强染色体的质量;再次,采用启发式交叉算子来拓展解的搜索范围,加大算法跳出局部最优的能力;最后,使用自适应交叉概率和变异概率来使算法更快找到最优解。结果表明:在任务数为20和40这2种情况下,DIHA-GA相比于混合粒子群算法(hybrid particle swarm optimization,HPSO)距离平均值分别减少了14.46 m和17.36 m,距离最小值分别减少了14.89 m和20.86 m,这说明DIHA-GA所得解更接近最优解;DIHA-GA比改进蚁群算法(improved ant colony optimization,IACO)所得距离平均值分别减少了21.32 m和18.73 m,距离最小值分别减少了23.43 m和22.32 m,这是由于IACO过早收敛并且难以跳出局部最优导致的。通过比较,验证了DIHA-GA在求解MRTA问题上的有效性。This paper proposes a multi-strategy genetic algorithm(DIHA-GA)to address the issues of local optima and low efficiency in solving multi-robot task allocation(MRTA)using genetic algorithm(GA).Firstly,a dual chromosome coding strategy was adopted to simplify the coding process.Secondly,the population was divided into three parts to enhance the quality of chromosomes while maintaining randomness.Then,heuristic crossover operators were used to expand the search range of the solution and increase the algorithm′s ability to jump out of local optima.Finally,adaptive crossover probability and mutation probability were used to make the algorithm find the optimal solution faster.The results showed that in the cases of 20 and 40 tasks,compared to the hybrid particle swarm optimization(HPSO),the average distance of the proposed DIHA-GA is reduced by 14.46 m and 17.36 m,respectively,and the minimum distance is reduced by 14.89 m and 20.86 m,respectively.This indicates that the solution obtained by DIHA-GA is closer to the optimal solution.The average distance obtained by DIHA-GA in this article is reduced by 21.32 m and 18.73 m respectively compared to the improved ant colony optimization(IACO),and the minimum distance is reduced by 23.43 m and 22.32 m respectively.This is due to the premature convergence of IACO and its difficulty in jumping out of local optima.The effectiveness of DIHA-GA in solving MRTA problems has been verified through comparison.

关 键 词：多机器人任务分配(MRTA) 仓储物流 遗传算法(GA) 改良圈策略 混合粒子群算法 蚁群算法 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]