Solving Graph Coloring Problem Based on Conflict Resolution Strategies of Social Community Alliance
-
摘要: 该文提出了一种基于群体协作的计算模型。该模型首先将输入的数据单元建模成微观个体,然后基于求解目标设计个体间的协作规则,最后通过个体在协作过程中涌现出的宏观现象来得到全局最优解。通过运用群体协作模型求解具有NP-完全复杂度的最优图着色问题,结果表明该模型的性能优于若干启发式方法,并且得到如下结论:1) 如果算法的动力学特征类似于混沌边缘现象,则算法能够在线性或亚线性时间复杂度求解问题。2) 如果算法的动力学特征呈现出完全随机性或强收敛性,则算法将退化成蛮力搜索。
-
[1] LEEUWARDEN N H. Shared space: Reconciling people, places, traffic[J]. Built Environment, 2008, 34(2): 161-181. [2] BOL L, CUNNINGHAM W. The wiki way[M]. Boston, MA: Addison Wesley Press, 2001. [3] BRINGSJORD S, TAYLOR J. P=NP[J]. Machine Ethics, 2011, 7(7): 361-374. [4] KHATIB F, DIMAIO F. Crystal structure of a monomeric retroviral protease solved by protein folding game players[J]. Nature Structural and Molecular Biology, 2011, 364(19): 1175-1177. [5] AXELROD R. The evolution of cooperation[M]. Princeton: Princeton University Press, 1997. [6] CHRIS A. The long tail: Why the future of business is selling less of more[M]. New York: Hyperion Press, 2008. [7] NICHOLAS C, FOWLER J. Connected: the surprising power of our social networks and how they shape our lives[M]. New York: Brown and Company Press, 2009. [8] JAMES S. The wisdom of crowds, economies, societies and nations[M]. New York: Little Brown Press, 2004. [9] ROBERT A. The evolution of cooperation[M]. London: Basic Books Press, 2006. [10] TAPSCOTT D, WILLIAMS A D. Wikinomics: How mass collaboration changes everything[M]. New York: Portfolio Trade Press .2006. [11] ARAL S, ALSTYNE V. Network structure and information advantage[C]//Proceedings of the Academy of Management Conference. Philadelphia. USA: ACM Press, 2007: 3-8. [12] DAWBER T. The framingham study: the epidemiology of atherosclerotic disease[M]. Cambridge, MA: Harvard University Press, 1980. [13] PENTLAND A. Computational social science[J]. Science, 2009, 323(5915): 721-723. [14] PENTLAND A. Pervasive sensing to model political opinions in face-to-face networks[J]. Pervasive Computing, 2011, 14(23): 214-231. [15] PENTLAND A. Sensible organizations: Technology and methodology for automatically measuring organizational behavior[J]. IEEE Transactions on Systems, Man, and Cybernetics Part B, 2009, 39(1):43-55. [16] GONZALEZ M. Understanding individual human mobility patterns[J]. Nature, 2008, 453: 779-782. [17] MONTOULIU R, GATICAL P. Discovering human places of interest from multimodal mobile phone data[J]. Multimed Tools Appl, 2013, 62: 179-207. [18] LU Hong. The Jigsaw continuous sensing engine for mobile phone applications[C]//Proceedings of the 8th ACM Conference on Embedded Networked Sensor Systems. Zürich, Switzerland: ACM Press, 2010: 71-84. [19] LIU Ji-ming, Autonomy oriented computing(AOC): Formulating computational systems with autonomous components[J]. IEEE Transactions on Systems, Man and Cybernetics, 2005, 35(6): 100-139. [20] NELKEN R, YAMANGIL E. Mining wikipedia's article revision history for training computational linguistics algorithms[C]//Proceedings of the 1st AAAI Workshop on Wikipedia and Artificial Intelligence. Chicago, USA: ACM Press, 2008:423-430. [21] SCHAERF A. A survey of automated time tabling[J]. Artificial Intelligence Review, 2009, 16(48): 87-127. [22] DELARK DE WERRA. Heuristics for graph coloring[J]. Computing Supplementum, 1990, 7(2): 191-208. [23] 马艳萍, 吴晓军. 解决图着色问题的一种新禁忌搜索算 法[J]. 计算机应用与软件, 2012, 29(2): 279-281. MA Yan-ping, WU Xiao-jun. A new tabu search algorithm of graph coloring[J]. Computer Applications and Software, 2012, 29(2): 279-281. [24] 徐杰, 杜文, 李宗平, 等. 基于模拟退火算法和图着色 的调车机车安排研究[J]. 铁道学报, 2003, 25(3): 24-30. XU Jie, DU Wen, LI Zong-ping, et al. Study on the plan of using shunting locomotives based on simulated annealing algorithm and graph coloring[J]. Journal of The China Railway Society, 2003, 25(3): 24-30. [25] PHILIPE G, HAO Jin-kao. Hybrid evolutionary algorithms for graph coloring[J]. Journal of Combinatorial Optimization, 1999, 3(4): 379-397. [26] RAILSBACK S. Agent-based and individual-based modeling: a practical introduction[M]. Cambridge: Princeton University Press, 2011.
点击查看大图
计量
- 文章访问数: 4892
- HTML全文浏览量: 139
- PDF下载量: 310
- 被引次数: 0