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

摘要：

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

关键词：协作规则、涌现计算、图着色、群体协作、NP-完全、社会计算

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金61202250,61203172；四川省教育厅重点项目ZA150184

在线出版日期：2016-03-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共15页

页码：2-16