摘要
该文提出了一种基于群体协作的计算模型。该模型首先将输入的数据单元建模成微观个体,然后基于求解目标设计个体间的协作规则,最后通过个体在协作过程中涌现出的宏观现象来得到全局最优解。通过运用群体协作模型求解具有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.
出处
《电子科技大学学报》
EI
CAS
CSCD
北大核心
2016年第1期2-16,共15页
Journal of University of Electronic Science and Technology of China
基金
国家自然科学基金(61202250
61203172)
四川省教育厅重点项目(ZA150184)
关键词
协作规则
涌现计算
图着色
群体协作
NP-完全
社会计算
cooperation rules
emergent computing
graph coloring
group cooperation
NP-complete
social computing
