基于社群联盟的冲突消解原则求解图着色问题

• 作者: 乔少杰 立玉 舒红平 许源平 郑皎凌
• 来源期刊: 电子科技大学学报
• 学科: 工学
• 关键词: 协作规则 涌现计算 图着色 群体协作 NP-完全 社会计算
• 年，卷（期）: 2016,（1）
• 所属期刊栏目: 复杂性科学专栏
• 页码范围: 2-16
• 页数: 15页
• 分类号: TP311
• 字数: 13349字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-0548.2016.01.001

摘要

该文提出了一种基于群体协作的计算模型。该模型首先将输入的数据单元建模成微观个体，然后基于求解目标设计个体间的协作规则，最后通过个体在协作过程中涌现出的宏观现象来得到全局最优解。通过运用群体协作模型求解具有NP-完全复杂度的最优图着色问题，结果表明该模型的性能优于若干启发式方法，并且得到如下结论：1)如果算法的动力学特征类似于混沌边缘现象，则算法能够在线性或亚线性时间复杂度求解问题。2)如果算法的动力学特征呈现出完全随机性或强收敛性，则算法将退化成蛮力搜索。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	舒红平	成都信息工程大学软件工程系	65	461	11.0	18.0
2	郑皎凌	成都信息工程大学软件工程系	22	102	6.0	9.0
3	乔少杰	西南交通大学信息科学与技术学院	20	339	10.0	18.0
4	许源平	成都信息工程大学软件工程系	6	13	3.0	3.0
5	立玉	成都信息工程大学软件工程系	3	9	2.0	3.0