一种基于多智能体进化的广义图染色算法

摘要

基于对广义图染色问题的研究,提出了一种求解广义图染色问题的多智能体进化算法(multiagent evolutionary algorithm for T-coloring problem,简称MAEA-TCP),并将该算法应用到实际中的频率分配问题上,取得了良好的效果.该方法中每个智能体作为一个候选解被固定在智能体网格上,为了增加自身能量而与邻域当中的智能体展开竞争或者合作,同时智能体也可以利用自身的知识进行自学习来增加能量.根据广义图染色问题的特点,为智能体设计了3种算子:竞争算子、自学习算子和变异算子,以引导其进化,并用进化的方式来控制各算子,以协调智能体之间的相互作用.在实验中,分别使用大规模的随机图实例和费城实例来测试算法性能,同时给出参数测试结果和最佳取值区间.比较结果表明,该算法优于其他方法,具有良好的收敛性和实用价值.