1.School of Computer and Information,Hefei University of Technology,Hefei 230009 2.School of Computer Science and Technology,Huaibei Normal University,Huaibei 235000 3.Information Security Center,Beijing University of Posts and Telecommunications,Beijing 100876
Abstract:To solve the optimization problem in complex distributed system (CDS),a collaborative optimization method based on chaotic ant swarm in CDS is presented. The basic dynamic characteristics of complex distributed systems are analyzed under the guide of system theory,and a model of collaborative optimization of CDS is proposed. Thus,a collaborative optimization in CDS is established based on the idea of chaotic ant swarm (CAS),called CAS based collaborative optimization (CAS-CO). The locality-based task allocation in complex networked multi-agent system is resolved by CAS-CO,and the comparison results of the proposed algorithm and the existing ones show that the CAS-CO algorithm is feasible and effective,and the proposed model is correct and the autonomy of an agent is of importance for the design and modeling of CDS.
[1] Modi P,Shen W,Tambe M,et al. ADOPT: Asynchronous Distributed Constraint Optimization with Quality Guarantees. Artificial Intelligence,2005,161(1/2): 149-180 [2] Mailler R,Lesser V. Solving Distributed Constraint Optimization Problems Using Cooperative Mediation // Proc of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems. New York,USA,2004: 438-445 [3] Bertsekas D P,Tsitsiklis J N. Parallel and Distributed Computation: Numerical Methods. Cambridge,USA: MIT Press,1997 [4] Tsitsiklis J N,Bertsekas D P,Athans M. Distributed Asynchronous Deterministic and Stochastic Gradient Optimization Algorithms. IEEE Trans on Automatic Control,1986,31(9): 803-812 [5] Nedic A,Ozdaglar A. Distributed Subgradient Methods for Multi-Agent Optimization. IEEE Trans on Automatic Control,2009,54(1): 48-61 [6] Nedic A,Ozdaglar A,Parrilo A P. Constrained Consensus and Optimization in Multi-Agent Networks. IEEE Trans on Automatic Control,2010,55(4): 922-938 [7] Srivastava K,Nedic A. Distributed Asynchronous Constrained Stochastic Optimization. IEEE Journal of Selected Topics in Signal Processing,2011,5(4): 772-790 [8] Nedic A. Asynchronous Broadcast-Based Convex Optimization over a Network. IEEE Trans on Automatic Control,2011,56(6): 1337-1351 [9] Zhu Minghui,Martinez S. On Distributed Convex Optimization under Inequality and Equality Constraints via Primal-Dual Subgradient Methods[EB/OL]. [2012-03-07]. http://faemino.ucsd.edu/~soniamartinez/papers/data/DCO-extended.pdf [10] Chiang M,Low S H,Calderbank A R,et al. Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures. Proc of the IEEE,2007,95(1): 255-312 [11] Kelly F P,Maulloo A,Tan D. Rate Control for Communication Networks: Shadow Prices,Proportional Fairness and Stability. Journal of the Operational Research Society,1998,49(3): 237-252 [12] Srikant R. The Mathematics of Internet Congestion Control. Basel,Switzerland: Birkhauser,2003 [13] Han-Lim C,Brunet L,How J P. Consensus-Based Decentralized Auctions for Robust Task Allocation. IEEE Trans on Robotics,2009,25(4): 912-926 [14] Kivelevitch E,Cohen K,Kumar M. Market-Based Solution to the Allocation of Tasks to Agents. Procedia Computer Science,2011,6: 28-33 [15] Ferreira Jr P R,Boffo F,Bazzan A L C. Using Swarm-GAP for Distributed Task Allocation in Complex Scenarios // Jamali N,Scerri P,Sugawara T,eds. Massive Multi-Agent Technology. Berlin,Germany: Springer,2008,5043: 107-121 [16] Li Lixiang,Yang Yixian,Peng Haipeng,et al. An Optimization Method Inspired by "Chaotic" Ant Behavior. International Journal of Bifurcation and Chaos,2006,16 (8): 2351-2364 [17] Wei Zhen,Ge Fangzhen,Lu Yang,et al. Chaotic Ant Swarm for the Traveling Salesman Problem. Nonlinear Dynamics,2011,65(3): 271-281 [18] Ge Fangzhen,Wei Zhen,Lu Yiming,et al. Disturbance Chaotic Ant Swarm. International Journal of Bifurcation and Chaos,2011,21(9): 2597-2622 [19] Olfati-Saber R,Fax J A,Murray R M. Consensus and Cooperation in Networked Multi-Agent Systems. Proc of the IEEE,2007,95(1): 215-233 [20] Li Zhongkui,Duan Zhisheng,Chen Guanrong,et al. Consensus of Multiagent Systems and Synchronization of Complex Networks: A Unified Viewpoint. IEEE Trans on Circuits and Systems,2010,57(1): 213-224 [21] Vicsek T,Czirók A,Ben-Jacob E,et al. Novel Type of Phase Transition in a System of Self-Driven Particles. Physical Review Letters,1995,75(6): 1226-1229 [22] Wang Yue,Tao Ran,Li Binzhao. Complex Information Systems Based on Multi-Living Agent. Science in China: Series E,2008,38(12): 2020-2037 ( in Chinese) (王 越,陶 然,李炳照.基于多活性代理的复杂信息系统研究.中国科学E辑,2008,38(12): 2020-2037) [23] Peng Haipeng,Li Lixiang,Yang Yixian,et al. Parameter Estimation of Dynamical Systems via a Chaotic Ant Swarm. Physical Review E,2010. DOI: 10.1103/PhysRevE.81.016207 [24] Wan Miao,Li Lixiang,Xiao Jinghua,et al. CAS Based Clustering Algorithm for Web Users. Nonlinear Dynamics,2010,61: 347-361 [25] Solé R V,Miramontes O,Goodwill B C. Oscillations and Chaos in Ant Societies. Journal of Theoretical Biology,1993,161(3): 343-357 [26] Xing Xiusan. Description of the Dynamic Information Theory and Dynamical Systems. Science in China: Series G,2010,40(2): 158-176 (in Chinese) (邢修三.动态信息理论和动力学系统信息描述.中国科学G辑,2010,40(2): 158-176)