基于多种群的随机扰动蚁群算法求解分布式约束优化问题  

Random disturbance based multi-population ant colony algorithm to solve distributed constraint optimization problems

作　　者：石美凤 肖诗川 冯欣[1] Shi Meifeng;Xiao Shichuan;Feng Xin(College of Computer Science&Engineering,Chongqing University of Technology,Chongqing 400054,China)

机构地区：[1]重庆理工大学计算机科学与工程学院,重庆400054

出　　处：《计算机应用研究》2022年第9期2683-2688,共6页Application Research of Computers

基　　金：重庆市教育委员会科学技术研究计划青年资助项目(KJQN202001139);重庆市基础研究与前沿探索资助项目(cstc2018jcyjAX0287);重庆理工大学研究生创新项目(clgycx20203116);重庆理工大学科研启动基金资助项目(2019ZD03)。

摘　　要：针对现有的基于蚁群优化思想求解分布式约束优化问题的算法收敛较慢、容易陷入局部最优等问题,提出了一种基于多种群的随机扰动蚁群算法(random disturbance based multi-population ant colony algorithm to solve distributed constraint optimization problems,RDMAD)来求解分布式约束优化问题。首先,RDMAD提出了一种分工合作机制,将种群按比例划分为采用贪婪搜索的子种群和采用启发式搜索的子种群,同时构建分级更新策略,提高算法收敛速度和求解质量;然后对采用贪婪搜索的子种群设计自适应变异算子和奖惩机制,防止算法陷入局部最优;最后在算法陷入停滞时触发随机扰动策略,增加种群多样性。将RDMAD与七种最先进的非完备算法在三类基准问题上的寻优结果进行了实验对比,结果表明RDMAD在求解质量和收敛速度上优势明显,且稳定性较高。Ant colony algorithms to solve distributed constraint optimization problems(ACO_DCOP)have some shortcomings including very slow convergence speed and easily falling into local optima.To cope with these issues,this paper proposed a RDMAD.The method introduced a division of labor and cooperation mechanism to divide the population into two subpopulations for greedy search and heuristic search respectively.It also constructed a hierarchical update strategy to speed up convergence and improve solution quality.Furthermore,this paper designed an adaptive mutation operator and a reward and punishment mechanism for the greedy search subpopulation to prevent RDMAD falling into the local optima.Simultaneously,this paper introduced a random disturbance strategy to increase the population diversity when RDMAD was stagnant.To verify the performance of the proposed algorithm,it compared RDMAD with the other seven advanced incomplete algorithms on three types of benchmark problems.The extensive experimental results show that the RDMAD algorithm is significantly superior to the state-of-the-arts algorithms in solution quality and convergence speed.In addition,RAMAD is far stable than the competing algorithms.

关 键 词：分布式约束优化问题 蚁群算法 自适应变异算子 非完备算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]