|
|
|
| Emergent Computation: an Overview |
| LI Jin, XIAO Renbin
|
| School of Automation, Huazhong University of Science and Technology, Wuhan 430074, China |
|
|
|
|
Abstract Firstly we introduce emergent phenomenon in complex systems and the basic principle of emergent computation. Secondly an important emergent computation model—cellular automata (CA) is demonstrated, and the relationship between emergent computation and swarm intelligence is illustrated. Then we discuss some key themes such as the mapping from source problems to emergent computation models, self-organization and synchronization. At last we review the application of emergent computation in aspects of engineering computation and social computation.
|
|
Received: 25 February 2014
Published: 22 June 2026
|
|
|
|
|
|
[1] Wolfram S. Universality and complexity in cellular automata[J]. Physica D: Nonlinear Phenomena, 1984, 10(1): 1-35.
[2] Forrest S. Emergent computation: self-organizing, collective, and cooperative phenomena in natural and artificial computing networks: introduction to the proceedings of the ninth annual CNLS conference[J]. Physica D: Nonlinear Phenomena, 1990, 42(1): 1-11.
[3] Holland J H. Emergence: From Chaos to Order[M]. Redwood City: Oxford University Press, 2000.
[4] Kube C R, Bonabeau E. Cooperative transport by ants and robots[J]. Robotics and autonomous systems, 2000, 30(1): 85-101.
[5] Martin M, Chopard B, Albuquerque P. Formation of an ant cemetery: swarm intelligence or statistical accident?[J]. Future Generation Computer Systems, 2002, 18(7): 951-959.
[6] Chung J R, Choe Y. Emergence of memory in reactive agents equipped with environmental markers[J]. Autonomous Mental Development, IEEE Transactions on, 2011, 3(3): 257-271.
[7] Damiani C, Serra R, Villani M, et al. Cell-cell interaction and diversity of emergent behaviours[J]. Systems Biology, IET, 2011, 5(2): 137-144.
[8] Tao Z, Xiao R, Wang L. Structure emergence in the evolution of social networks and its case study[J]. Procedia Computer Science, 2013, 17: 981-988.
[9] Seiffertt J, Wunsch D. Intelligence in markets: asset pricing, mechanism design, and natural computation[technology review][J]. IEEE Computational Intelligence Magazine, 2008, 3(4): 27-30.
[10] Ha S Y, Ha T, Kim J H. Emergent behavior of a Cucker-Smale type particle model with nonlinear velocity couplings[J]. IEEE Transactions on Automatic Control, 2010, 55(7): 1679-1683.
[11] Park J, Kim H J, Ha S Y. Cucker-Smale flocking with inter-particle bonding forces[J]. IEEE Transactions on Automatic Control, 2010,55(11): 2617-2623.
[12] Finke J, Passino K M. Local agent requirements for stable emergent group distributions[J].IEEE Transactions on Automatic Control, 2011, 56(6): 1426-1431.
[13] Niazi M A, Hussain A. Sensing emergence in complex systems[J]. IEEE Sensors Journal, 2011, 11(10): 2479-2480.
[14] Tsilipanos K, Neokosmidis I, Varoutas D. A system of systems framework for the reliability assessment of telecommunications networks[J]. IEEE Systems Journal, 2013, 7(1): 114-124.
[15] Christie P. A fractal analysis of interconnection complexity[J]. Proceedings of the IEEE, 1993, 81(10): 1492-1499.
[16] Hales D, Patarin S. Computational sociology for systems" in the wild": the case of BitTorrent[J]. IEEE Distributed Systems Online, 2005, 6(7): 1-6.
[17] Santini S, Gupta A, Jain R. Emergent semantics through interaction in image databases[J]. IEEE Transactions on Knowledge and Data Engineering, 2001, 13(3): 337-351.
[18] Shimizu M, Ishiguro A, Kawakatsu T. Slimebot: a modular robot that exploits emergent phenomena[C]//Proceedings of the 2005 IEEE International Conference on Robotics & Automation, 2005: 2982-2987.
[19] Lee S I, Cho S B. Emergent behaviors of a fuzzy sensory-motor controller evolved by genetic algorithm[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B Cybernetics, 2001, 31(6): 919-929.
[20] Kahn J M, Katz R H, Pister K S J. Emerging challenges: mobile networking for “smart dust”[J]. Journal of Communications and Networks, 2000, 2(3): 188-196.
[21] Kunniyur S S, Venkatesh S S. Threshold functions, node isolation, and emergent lacunae in sensor networks[J]. IEEE Transactions on Information Theory, 2006, 52(12): 5352-5372.
[22] Olascuaga-Cabrera J G, Lopez-Mellado E, Mendez-Vazquez A, et al. A self-organization algorithm for robust networking of wireless devices[J]. IEEE Sensors Journal, 2011, 11(3): 771-780.
[23] Charles P. Emergent collectives[J]. IEEE Internet Computing, 2011, 15(5): 99-102.
[24] Gravagne I A, Marks R J. Emergent behaviors of protector, refugee, and aggressor swarms[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B Cybernetics, 2007, 37(2): 471-476.
[25] Cucker F, Smale S. Emergent behavior in flocks[J].IEEE Transactions on Automatic Control, 2007, 52(5): 852-862.
[26] Dressler F, Suda T, Carreras I, et al. Guest editorial bio-inspired networking[J].IEEE Journal on Selected Areas in Communications, 2010, 28(4): 521-523.
[27] Liu Y, Passino K M. Stable social foraging swarms in a noisy environment[J]. IEEE Transactions on Automatic Control, 2004, 49(1): 30-44.
[28] Van Drongelen W, Lee H C, Hereld M, et al. Emergent epileptiform activity in neural networks with weak excitatory synapses[J]. IEEE Transactions on Neural Systems and Rehabilitation Engineering, 2005, 13(2): 236-241.
[29] Yu A R, Thompson B B, Marks R J. Competitive evolution of tactical multiswarm dynamics[J]. IEEE Transactions on Systems, Man, and Cybernetics Systems, 2013, 43(3): 563-569.
[30] Ewert W, Marks R J, Thompson B B, et al. Evolutionary inversion of swarm emergence using disjunctive combs control[J]. IEEE Transactions on Systems, Man, and Cybernetics Systems, 2013, 43(5): 1063-1076.
[31] Li N, Marden J R. Designing games for distributed optimization[J]. IEEE Journal of Selected Topics in Signal Processing, 2013, 7(2): 230-242.
[32] 宋玉蓉, 蒋国平.基于一维元胞自动机的复杂网络恶意软件传播研究[J]. 物理学报, 2009, 58(9): 5911-5918.
Song Yurong, Jiang Guoping. Research of malware propagation in complex networks based on 1-D cellular automata[J]. Acta Physica Sinica. 2009, 58(9): 5911-5918.
[33] Simons N R S, Bridges G E, Podaima B W, et al. Cellular automata as an environment for simulating electromagnetic phenomena[J]. Microwave and Guided Wave Letters, 1994, 4(7): 247-249.
[34] Mamei M, Roli A, Zambonelli F. Emergence and control of macro-spatial structures in perturbed cellular automata, and implications for pervasive computing systems[J]. Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, 2005, 35(3): 337-348.
[35] Mardiris V A, Karafyllidis I G. Universal cellular automaton cell using quantum cellular automata[J]. Electronics letters, 2009, 45(12): 607-609.
[36] Sapin E, Bull L, Adamatzky A. Genetic approaches to search for computing patterns in cellular automata[J]. Computational Intelligence Magazine, 2009, 4(3): 20-28.
[37] 肖人彬, 陶振武. 群集智能研究进展[J]. 管理科学学报, 2007, 10(3): 80-96.
Xiao Renbin, Tao Zhenwu. Development in swarm intelligence[J]. Journal of Management Sciences in China, 2007, 10(3): 80-96.
[38] 肖人彬. 面向复杂系统的群集智能[M]. 北京: 科学出版社, 2013.
[39] Dorigo M, Maniezzo V, Colorni A. The ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on Systems, Man and Cybernetics-Part B, 1996, 26(1) : 29-41.
[40] Weng J, Luciw M D, Zhang Q. Brain-like emergent temporal processing: emergent open states[J]. IEEE Transactions on Autonomous Mental Development, 2013, 5(2): 89-116.
[41] 颜泽贤, 范冬萍, 张华夏. 系统科学导论—复杂性探索[M]. 北京: 人民出版社, 2006.
[42] 金士尧, 黄红兵, 任传俊. 基于复杂性科学基本概念的MAS涌现性量化研究[J]. 计算机学报, 2009, 32(1): 17-29.
Jin Shiyao,Huang Hongbing,Ren Chuanjun. Emergence oriented research on MAS with quantifications based on the notions in science of complexity[J]. Chinese Journal of Computers, 2009, 32(1): 17-29.
[43] 尼科利斯 G, 普里戈金 I. 非平衡系统中的自组织[M]. 徐锡申,译. 北京: 科学出版社, 1986
[44] 哈肯 H. 协同学导论[M]. 张纪岳,郭治安,译. 西安: 西北大学科研处, 1981.
[45] Liu J, Jin X, Tsui K C. Autonomy-oriented computing (AOC): formulating computational systems with autonomous components[J]. IEEE Transactions on Systems, Man and Cybernetics, Part A Systems and Humans, 2005, 35(6): 879-902.
[46] 李健, 李刚, 孙林岩. 分散化供应链的自组织演化机制建模与仿真[J]. 数学的实践与认识, 2008, 38(6): 26-34.
Li Jian, Li Gang, Sun Linyan. Modeling and simulation of distributed supply-chain self-organizing evolution mechanism[J]. Mathematics in Practice and Theory, 2008, 38(6): 26-34.
[47] 顾珊珊, 陈禹. 复杂适应性系统的仿真与研究——基于CAS理论的交通模拟[J]. 复杂系统与复杂性科学, 2004, 1(1): 82-88.
Gu Shanshan, Chen Yu. Modeling & simulation of complex adaptive system-a traffic simulation system[J]. Complex Systems and Complexity Science, 2004, 1(1): 82-88.
[48] 张嗣瀛. 复杂性科学, 整体规律与定性研究[J]. 复杂系统与复杂性科学, 2005, 2(1): 71-83.
Zhang Siying. Complexity science, rules of the whole systems and the qualitative researches[J]. Complex Systems and Complexity Science, 2005, 2(1): 71-83.
[49] 罗吉贵, 刘曾荣. 从同步到涌现[J]. 复杂系统与复杂性科学, 2005, 2(1): 29-32.
Luo Jigui, Liu Zengrong. From synchronization to emergence[J]. Complex Systems and Complexity Science, 2005, 2(1): 29-32.
[50] Winfree A T. Biological rhythms and the behavior of populations of coupled oscillators[J]. Journal of Theoretical Biology, 1967, 16(1):15-42.
[51] Araki H. International symposium on mathematical problems in theoretical physics[J]. Lecture Notes in Physics, 1975, 39.
[52] Néda Z, Ravasz E, Brechet Y, et al. Self-organizing processes: The sound of many hands clapping[J]. Nature, 2000, 403(6772): 849-850.
[53] Strogatz S H. Fromkuramoto to crawford: exploring the onset of synchronization in populations of coupled oscillators[J]. Physica D: Nonlinear Phenomena, 2000, 143(1): 1-20.
[54] 李德毅, 刘坤, 孙岩, 等. 涌现计算: 从无序掌声到有序掌声的虚拟现实[J]. 中国科学 E辑: 信息科学, 2007, 37(10): 1248-1257.
Li Deyi, Liu Kun, Sun Yan, et al. Emergent computation: the virtual reality of applause from disorder to ordered[J]. Science in China(Series E: Information Sciences), 2007, 37(10): 1248-1257.
[55] Li D, Liu K, Sun Y, et al. Emerging clapping synchronization from a complex multiagent network with local information via local control[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2009, 56(6): 504-508.
[56] Wang D L. Emergent synchrony in locally coupled neural oscillators[J]. IEEE Transactions on Neural Networks, 1995, 6(4): 941-948.
[57] Zhang Q, Lu J, Lu J, et al. Adaptive feedback synchronization of a general complex dynamical network with delayed nodes[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2008, 55(2): 183-187.
[58] Chen M. Chaos synchronization in complex networks[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2008, 55(5): 1335-1346.
[59] Boulden S, Iorio A W, Abbass H A. Learning synchronization in networked complex systems using genetic algorithms[C]//IEEE Congress on Evolutionary Computation, 2010: 1-8.
[60] 汪镭, 周国兴. 用Hopfield神经网络进行交流传动系统参数辨识[J]. 模式识别与人工智能, 1996, 9(3): 291-296.
Wang Lei, Zhou Guoxing. Hopfield neural network based AC drive system parameters identification[J]. Pattern Recognitien and Artificial Intelligence, 1996, 9(3): 291-296.
[61] 康琦, 安静, 汪镭, 等. 自然计算的研究综述[J]. 电子学报, 2012, 40(3): 548-558.
Kang Qi, An Jing, Wang Lei, et al. nature-inspired computation: a survey[J]. Aacta Electronica Sinica, 2012, 40(3): 548-558.
[62] 汪镭, 康琦, 吴启迪. 自然计算——人工智能的有效实施模式[J]. 系统工程理论与实践, 2007, 5: 126-134.
Wang Lei, Kang Qi, Wu Qidi. Nature-inspired computation-effective realization of artificial intelligence[J]. Systems Engineering-Theory & Practice, 2007, 5: 126-134.
[63] Dong J, Zhang Z, Ma D. Emergent phenomenon and the local information based DTA model[C]//IEEE Intelligent Transportation Systems, 2003, 2: 1273-1277.
[64] Sotelo M A, Van Lint J W C, Nunes U, et al. Introduction to the special issue on emergent cooperative technologies in intelligent transportation systems[J]. IEEE Transactions on Intelligent Transportation Systems, 2012, 13(1): 1-5.
[65] Linkens D A, Nyongesa H O. Learning systems in intelligent control: an appraisal of fuzzy, neural and genetic algorithm control applications[J]. IEEE Proceedings Control Theory and Applications, 1996, 143(4): 367-386.
[66] Maturana F P, Staron R J, Hall K H. Methodologies and tools for intelligent agents in distributed control[J]. IEEE Intelligent Systems, 2005, 20(1): 42-49.
[67] Arena P, Fortuna L, Frasca M, et al. A CNN-based chip for robot locomotion control[J]. IEEE Transactions on Circuits and Systems I: Re-gular Papers, 2005, 52(9): 1862-1871.
[68] Krasny D P, Orin D E. Generating high-speed dynamic running gaits in a quadruped robot using an evolutionary search[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2004, 34(4): 1685-1696.
[69] Arena P, Patanè L. Simple sensors provide inputs for cognitive robots[J]. IEEE Instrumentation & Measurement Magazine, 2009, 12(3): 13-20.
[70] Floreano D, Mondada F. Evolution of homing navigation in a real mobile robot[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 1996, 26(3): 396-407.
[71] Li Y, Tang Z, Xia G P, et al. A positively self-feedbacked Hopfield neural network architecture for crossbar switching[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2005, 52(1): 200-206.
[72] Dogaru R. Applications of Emergent Computation in Reaction-Diffusion CNNs for Image Processing[C]//19th IEEE International Conference on Control Systems and Computer Science, 2013: 370-377.
[73] 杨淑莹, 刘旭鹏, 陶冲, 等. 基于免疫猫群优化算法的矢量量化的码书设计及语音识别[J]. 模式识别与人工智能, 27(7): 577-583.
Yang Shuying, Liu Xupeng, Tao Chong, et al. Vector quantization codebook design and speech recognition based on immune cat swarm optimization algorithm[J]. Pattern Recognition and Artificial Intelligence, 27(7): 577-583.
[74] Ha S Y, Ha T, Kim J H. Emergent behavior of a Cucker-Smale type particle model with nonlinear velocity couplings[J]. IEEE Transactions on Automatic Control, 2010, 55(7): 1679-1683.
[75] Kahrobaee S, Rajabzadeh R A, Soh L K, et al. A multiagent modeling and investigation of smart homes with power generation, storage, and trading features[J]. IEEE Transactions on Smart Grid, 2013, 4(2): 659-668.
[76] Tero A, Takagi S, Saigusa T, et al. Rules for biologically inspired adaptive network design[J]. Science, 2010, 327(5964): 439-442.
[77] Seiffertt J, Wunsch D. Intelligence in markets: asset pricing, mechanism design, and natural computation technology review[J]. IEEE Computational Intelligence Magazine, 2008, 3(4): 27-30.
[78] Chung J R, Choe Y. Emergence of memory in reactive agents equipped with environmental markers[J]. IEEE Transactions on Autonomous Mental Development, 2011, 3(3): 257-271.
[79] Lee S M, Pritchett A R. Predicting interactions between agents in agent-based modeling and simulation of sociotechnical systems[J]. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 2008, 38(6): 1210-1220.
[80] Hurlburt G, Voas J, Miller K, et al. A nonlinear perspective on higher education[J]. Computer, 2010 (12): 90-92.
[81] Kong Z, Mettler B. Modeling human guidance behavior based on patterns in agent–environment interactions[J]. IEEE Transactions on Human-Machine Systems, 2013, 43(4): 371-384.
[82] Sanchez-Cortes D, Aran O, Mast M S, et al. A nonverbal behavior approach to identify emergent leaders in small groups[J]. IEEE Transactions on Multimedia, 2012, 14(3): 816-832.
[83] Izumi K, Ueda K. Phase transition in a foreign exchange market-analysis based on an artificial market approach[J]. IEEE Transactions on Evolutionary Computation, 2001, 5(5): 456-470.
[84] 栾笑天, 吴桐水, 寇勇刚. 基于CA方法的航空物流市场演化模型设计[J]. 复杂系统与复杂性科学, 2013, 10(4): 31-40.
Luan Xiaotian, Wu Tongshui, Kou Yonggang. Designing the evolution model of aviation logistics market with cellular automata[J]. Complex Systems and Complexity Science, 2013, 10(4): 31-40.
[85] Koritarov V S. Real-world market representation with agents[J]. IEEE Power and Energy Magazine, 2004, 2(4): 39-46.
[86] Chicco G, Napoli R, Piglione F, et al. Emergent electricity customer classification[J]. IEE Proceedings-Generation, Transmission and Distribution, 2005, 152(2): 164-172.
[87] 龚小庆, 范文涛, 丁义明. 建立系统科学基础理论框架的一种可能途径与若干具体思路(之八) —— 固定环境中的稳态涌现[J]. 系统工程理论与实践, 2003, 8: 1-7.
Gong Xiaoqing, Fan Wentao, Ding Yiming. A possible approach to the framework of the fundamental theory of system science: part eight[J]. Systems Engineering-theory & Practice, 2003, 8: 1-7.
[88] 龚小庆, 王展. 关于Zipf律的一点注记[J]. 复杂系统与复杂性科学, 2008, 5(3): 73-78.
Gong Xiaoqing, Wang Zhan. A note on the zipf′s law[J]. Complex Systems and Complexity Science, 2008, 5(3): 73-78.
[89] 龚小庆. 经济系统涌现和演化——复杂性科学的观点[J]. 财经论丛, 2004, 5(111): 12-18.
Gong Xiaoqing. Researches on emergence and evolution of economy——in the view of complexity sciences[J]. Collected Essays on Finance and Economics, 2004, 5(111): 12-18.
[90] 赵剑冬, 黄战. 基于Agent的经济社会系统建模与仿真研究[J]. 复杂系统与复杂性科学, 2011, 8(4): 59-67.
Zhao Jiandong, Huang Zhan. A study on agent based social-economic system modeling and simulation[J]. Complex Systems and Complexity Science, 2011, 8(4): 59-67.
[91] Zeng F, Decraene J, Low M Y H, et al. Evolving optimal and diversified military operational plans for computational red Teaming[J]. IEEE Systems Journal, 2012, 6(3): 499-509.
[92] Lewis R, Paechter B. Finding feasible timetables using group-based operators[J]. IEEE Transactions on Evolutionary Computation, 2007,
11(3): 397-413.
[93] 王飞跃, 史帝夫·兰森. 从人工生命到人工社会—复杂社会系统研究的现状和展望[J]. 复杂系统与复杂性科学, 2004, 1(1): 33-41.
Wang Feiyue, Lansing J S. From artificial life to artificial societies—new methods for studies of complex social systems[J]. Complex Systems and Complexity Science, 2004, 1(1): 33-41. |
|
|
|
