求解连续型分布式约束优化问题的自适应多点交叉遗传算法  

Adaptive multi-point crossover genetic algorithm for solving continuous distributed constraint optimization problems

作　　者：廖鑫 石美凤 陈媛[1] LIAO Xin;SHI Meifeng;CHEN Yuan(College of Computer Science and Engineering,Chongqing University of Technology,Chongqing 400000,China)

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

出　　处：《智能系统学报》2023年第4期793-802,共10页CAAI Transactions on Intelligent Systems

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

摘　　要：针对连续型分布式约束优化问题(continuous distributed constraint optimization problems,C-DCOPs)求解算法的anytime属性的缺失、约束函数形式的限制和无法保证收敛等局限,本文提出一种求解C-DCOP的自适应多点交叉遗传算法(adaptive multi-point crossover genetic algorithm based C-DCOP,AMCGA)。在AMCGA中,智能体(agent)构建分布式种群和广度优先搜索(breadth first search,BFS)伪树以分布式地计算个体适应度;通过贪婪策略选择精英个体进行自适应多点交叉实现全局搜索,智能体之间协同通信保证分布式种群中解的一致性;利用变异算子完成局部搜索。AMCGA适用于任意形式的约束函数,并被证明具有任意时间属性和全局收敛性。在4类基准问题上的广泛实验结果表明,AMCGA的求解质量优于最先进的C-DCOP求解算法,能有效地打破目前C-DCOP求解算法的局限,并在求解质量方面存在20%~30%的提升。Aiming at the limitations of the solving algorithm for continuous distributed constraint optimization problems(DCOPs),such as the lack of anytime property,the limitation of constraints function form and the inability to guarantee convergence,an adaptive multi-point crossover genetic algorithm for solving C-DCOP(AMCGA)is proposed.In AMCGA,the agent firstly builds distributed population and breadth first search(BFS)pseudo-tree to calculate the individual fitness in a distributed way.Secondly,the agent selects elite individuals through greedy strategy for adaptive multipoint crossover,achieving global search;cooperative communication between agents ensures the consistency of solutions in the distributed population.Finally,the agent uses mutation operator to complete local search.AMCGA is suitable for any form of constraint function and is proved to have anytime property and global convergence.Extensive experimental results on four types of benchmark problems demonstrate that the solution quality of AMCGA is superior to the state-of-the-art C-DCOP solving algorithms,it can effectively break through the limitations of current C-DCOP solving algorithms,and improve the solution quality by 20% to 30%.

关 键 词：连续型分布式约束优化问题 任意时间属性 自适应多点交叉 遗传算法 分布式种群 广度优先搜索伪树 智能体 求解质量 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]