Abstract
In response to the increasing demands for solving various optimization problems arisen from complex systems, the paper focuses on the study of a general-purpose distributed/decentralized self-organized computing method, with the help of agent-oriented modeling method. The goal of this paper is to unravel the microscopic characteristics and the hidden complexity of complex computational systems, and furthermore, construct proper mechanisms that will support self-organized computation.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Achlioptas D, Naor A, Peres Y (2005) Rigorous location of phase transitions in hard optimization problems. Nature 435: 759–764
Ahuja RK, Ergun O, Orlin JB, Punnen AP (2002) A survey of very large-scale neighborhood search techniques. Discret Appl Math 123: 75–102
Albert R, Barabási AL (2007 August) The architecture of complexity, from network structure to human dynamics. IEEE Control Syst, pp 33–42
Barabási AL, Albert R (1999) Emergence of scaling in random networks. Science 286(5439): 509–512
Boettcher S, Percus AG (2000) Nature’s way of optimizing. Artif Intell 119: 275–286
Boettcher S, Percus AG (2003) Optimization with extremal dynamics. Complexity 8: 57–62
Bonabeau E (2002) Agent-based modeling: methods and techniques for simulating human systems. PNAS 99(suppl. 3): 7280–7287
Brin S, Page L (1998) The anatomy of a large-scale hypertextual web search engine. Comput Netw ISDN Syst 30: 107–117
Cheesman P, Kanefsky B, Taylor WM (1991) Where the really hard problems Are. Proc IJCAI’91, pp 163–169
Chen Y, Zhang P (2006) Optimized annealing of traveling salesman problem from the nth-nearest-neighbor distribution. Phys A 371: 627–632
Duch J, Arenas A (2005) Community detection in complex networks using extremal optimization. Phys Rev E 72: 27104
Frey BJ, Dueck D (2007) Clustering by passing messages between data points. Science 315: 972–976
Gutin G, Punnen AP (2002) The traveling salesman problem and its variations. Kluwer Academic Publishers, Netherland
Hordijk W (1997) A measure of landscapes. Evol Comput 4(4): 335–360
Jennings NR, Bussmann S (2003 June) Agent-based control systems. IEEE Control Syst Mags, pp 61–73
Kauffman SA (1993) The origins of order: self-organization and selection in evolution. Oxford University Press, Oxford
Langton CG (1995) Artificial life: an overview. The MIT press, Cambridge
Li W, Alidaee B (2002) Dynamics of local search heuristics for the traveling salesman problem. IEEE Trans on Syst Man Cybern 32(2): 173–184
Liu J (2001) Autonomous agents and multi-agent systems: explorations in learning, self-organization and adaptive computation. World Scientific Publishing Co., Inc., USA
Liu J (2008) Autonomy-oriented computing: the nature and implications of a paradigm for self-organized computing. Keynote talk at the 4th International conference on natural computation (ICNC’08), and the 5th International conference on fuzzy systems and knowledge discovery (FSKD’08), October, pp 18–20
Liu J, Han J, Tang YY (2002) Multi-agent oriented constraint satisfaction. Artif Intell 136: 101–144
Liu J, Jin X, Tsui KC (2005) Autonomy oriented computing: from problem solving to complex systems modeling. Kluwer Academic Publishers/Springer, Heidelberg
Liu J, Chen YW, Lu YZ, Yang GK (2008) Self-organized combinatorial optimization. HongKong Baptist University, Computer Science, Technical reports: COMP-08-001. http://www.comp.hkbu.edu.hk/en/research/?content=tech-reports
McCoy BM, Wu Tai Tsun (1973) The Two-dimensional ising model. Harvard University Press, Cambridge
Mertens S (2002 May/June) Computational complexity for physicists. Comput Sci Eng, pp 31–47
Merz P (2004) Advanced fitness landscape analysis and the performance of memetic algorithms. Evol Comput 12(3): 303–325
Mézard M, Zecchina R (2002) Random K-satisfiability problem: from an analytic solution to an efficient algorithm. Phys Rev E 66: 056126
Mézard M, Parisi G, Zecchina R (2002) Analytic and algorithmic solution of random satisfiability problems. Science 297: 812–815
Mitchell M (1998) Computation in cellular automata: a selected review, nonstandard computation. VCH Verlagsgesellschaft, Weinheim, pp 95–140
Mitchell M (2006) Complex systems: network thinking. Artif Intell 170: 1194–1212
Monasson R, Zecchina R, Kirkpatrick S, Selman B, Troyanskyk L (1999) Determining computational complexity from characteristic ‘phase transitions’. Nature 400: 133–137
Newman MEJ (2003) The structure and function of complex networks. SIAM Rev 45(2): 167–256
Newman MEJ (2006) Modularity and community structure in networks. PNAS 103(23): 8577–8582
Opper M, Saad D (2001) Advanced mean field methods: theory and practice. MIT Press, Cambridge
Poelwijk FJ, Kiviet DJ, Weinreich DM, Tans SJ (2007) Empirical fitness landscapes reveal accessible evolutionary paths. Nature 445(25): 383–386
Reinelt G (1991) TSPLIB-a traveling salesman problem library. ORSA J Comput 3(4): 376–384
Samanidou E, Zschischang E, Stauffer D, Lux T (2007) Agent-based models of financial markets. Reports Prog Phys 70: 409–450
Schuurmans D, Southey F (2001) Local search characteristics of incomplete SAT procedures. Artif Intell 132: 121–150
Strogatz SH (2001) Exploring complex networks. Nature 410: 268–276
Tsang EPK (1993) Foundations of constraint satisfaction. Academic Press, London
Variano EA, McCoy JH, Lipson H (2004) Networks, dynamics, and modularity. Phys Rev Lett 92(18): 188701
Author information
Authors and Affiliations
Corresponding author
Additional information
The abstract of this paper was accepted for the poster session at the European Conference on Complex Systems (ECCS) 2009.
Rights and permissions
About this article
Cite this article
Liu, J., Chen, YW. Toward understanding the optimization of complex systems. Artif Intell Rev 38, 313–324 (2012). https://doi.org/10.1007/s10462-011-9256-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10462-011-9256-4