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

Solving Graph Coloring Problem Based on Conflict Resolution Strategies of Social Community Alliance

作　　者：郑皎凌[1] 舒红平[1] 许源平[1] 乔少杰[2] 文立玉[1] 

机构地区：[1]成都信息工程大学软件工程系,成都610225 [2]西南交通大学信息科学与技术学院,成都610031

出　　处：《电子科技大学学报》2016年第1期2-16,共15页Journal of University of Electronic Science and Technology of China

基　　金：国家自然科学基金(61202250;61203172);四川省教育厅重点项目(ZA150184)

摘　　要：该文提出了一种基于群体协作的计算模型。该模型首先将输入的数据单元建模成微观个体,然后基于求解目标设计个体间的协作规则,最后通过个体在协作过程中涌现出的宏观现象来得到全局最优解。通过运用群体协作模型求解具有NP-完全复杂度的最优图着色问题,结果表明该模型的性能优于若干启发式方法,并且得到如下结论:1)如果算法的动力学特征类似于混沌边缘现象,则算法能够在线性或亚线性时间复杂度求解问题。2)如果算法的动力学特征呈现出完全随机性或强收敛性,则算法将退化成蛮力搜索。This study proposes a computing model based on group cooperation. The data unit of the input is first modeled as group individual, the cooperation rules between individuals are then designed based on the target of the problem. Finally, the problem＇s global optimal solution is obtained through the emergence phenomenon of individuals＇ cooperation process. By applying group cooperation model to solve graph coloring problem which has NP-complete complexity, it shows that the proposed model works better than several heuristic methods. Experimental results illustrate that： 1） if the algorithm＇s dynamics exhibits the edge of chaos phenomenon, the algorithm can solve the problem in linear or sub linear time complexity; 2） if the algorithm＇s dynamics is completely random or exhibits strong convergence, the algorithm degenerates into brutal force search.

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

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]