Chaotic Ant Based Collaborative Swarm Algorithms And Their Applications

Swarm intelligence (SI) is derived from the studies of the biological collective behavior, the scientific motivation for studying SI is the analysis of emergent and self-organizing swarming behaviors with distributed interactions among individuals, and the engineering objective for studying SI is to build a distributed autonomous system consisting of a large number of simple embedded equipments, such as wireless ad hoc networks, robot collaboration system. Although a lot of results have been gotten in these two areas, most of them are on the stochastic algorithms including ant colony optimization (ACO) and particle swarm optimization (PSO). In particular, more attentions are paid to apply the above two stochastic algorithms. In previous studies, the effects of both collaborative interactions between the individuals and research scales are concerned to these stochastic algorithms; furthermore, collaborative swarm algorithms are rarely involved.In recent years, a biologist named Cole investigated the behaviors of social ants, and discovered that the single ant shows chaotic activity pattern, while the whole ant colony exhibits a periodic behavior. Moreover, a famous scholar Sole gave a chaotic mapping expression of individual ant’s behavior. As well known, the intelligence of ant colony lies in self-organizing behavior that the ants can cooperate to finish tasks one by one with the spontaneous distributed coordination for resources assignment. From the viewpoint of dynamics, it is evident that the self-organization ability of ant colony must have inherent relations with the chaotic behavior of individual ant. As a result, we believe that the periodic behavior is a process of transforming chaos to self-organization.Therefore, we analyze the relations between the chaotic behaviors of individuals and the self-organizing behavior of ant colony from the aspects of the two scales including individual micro-level, individual micro-level and collective macro-level. Then we focus on how to establish some collaborative swarm algorithms for the combinatorial optimization problems, the high-dimensional function optimization problems, the complex distributed collaborative optimization problems, and the dynamic distributed constraint optimization problems so as to deepen and broaden the studies of SI.The main works of the present dissertation are as follows:(1) At the beginning of our studies, we conduct a survey, analysis and summary on the current researches, and point out some problems to be further resolved in this dissertation. Moreover, we elaborate the collaborative mechanisms of chaotic ant swarm (CAS) from chaos synchronization;(2) In this dissertation, we construct two collaborative swarm algorithms for the combinatorial optimization problems based on CAS from the perspective of the information interactions between the individuals. Firstly, we propose a centralized algorithm for the classical TSP (CAS-TSP). The CAS-TSP is developed by introducing a mapping from a continuous space to a discrete space, a reverse operator and a crossover operator into the CAS. Computer simulations demonstrate that the CAS-TSP is capable of generating optimal solution to some instances of TSPLIB. Secondly, we present a decentralized task allocation algorithm in wireless sensor networks based on chaotic ant swarm (CAS-DTA). The objective function of this algorithm is established according to the energy consumption and reliability of the entire task execution. The optimal solution can be achieved through task mapping, communication routing and task allocation selection by means of the framework of chaotic ant swarm. Task mapping is carried out with ant chaotic behaviors, communication routing is established with neighbor selection method and searched with A*algorithm, while task allocation selection is implemented with the self-organization capability of ant colony. Experimental results show the superiority of our algorithm in terms of both load balancing and lifetime of wireless sensor networks;(3) In this dissertation, we present a disturbance chaotic ant swarm (DCAS) from the perspective of the individual ant’s behavior and the interactions between individuals in order to reduce the amount of computation and communication. To resolve the problems of high computational complexity and low solution accuracy existing in CAS, DCAS is achieved by introducing three strategies, a new method of updating ant’s best position, a neighbor selection method and a self-adaptive disturbance strategy, into CAS. The global convergence of DCAS algorithm is also proved. Extensive computational simulations and comparisons are carried out to validate the performance of DCAS on two sets of benchmark functions with up to1000dimensions. The results show clearly that DCAS is feasible as well as effective;(4) In this dissertation, we propose a collaborative optimization method (CAS-CO) based on CAS and information entropy for complex distributed systems (CDS) from the perspective of the micro-level of the individual interactions and the macro-level of the collective behavior. The basic dynamic characteristics of CDS are analyzed under the guide of system complexity, and a model of collaborative optimization of CDS is formulated; on these bases, CAS-CO is established based on the ideas of CAS; To verify the validity of the proposed model and algorithm, a 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 then illuminate that the proposed model is correct and the autonomy of an agent is of importance for the design and modeling of CDS;(5) In this dissertation, we propose a decentralized coordination algorithm of autonomous swarm from the perspective of the decision-making relations between the micro-level of individuals and the macro-level of a global swarm, which can efficiently coordinate the autonomous swarm to the optimal solution. Our algorithm is inspired by the chaotic behavior of a single ant and the self-organizing behavior of the whole ant colony. To construct this algorithm, we firstly assume that each agent is a nonlinear oscillator presenting the chaotic behavior of a single ant. Then we establish a self-organization mechanism according to the self-organization behavior of the whole ant colony. Moreover, we analyze the convergence of the proposed algorithm. Finally we experimentally evaluate the performance of our algorithm with the clustering and dispersion operations of a swarm. Comparison results of the proposed algorithm and the gradient-type one are also presented to illustrate the effectiveness of the proposed scheme in approximately global optimization for swarms. In addition, we apply the distributed coordination mechanism of DCA, combine with the dynamic distributed constraint optimization problem, and further propose a chaotic ant based algorithm for dynamic distributed constraint optimization problem, named CA-DDCOP. To construct the CA-DDCOP algorithm, we firstly establish a value selecting strategy for the controlled variable of an agent based on chaotic behavior of a single ant to achieve the exploration operation; secondly, we develop a mechanism that an agent is subjected to its neighbors and self-organization ability according to self-organizing behavior of ant colony to achieve exploitation operation; Finally, we devise the decision-making relations between the individual micro-level and the collective macro-level based on the Boltzmann distribution so as to achieve the collaboration of two operations, exploration and exploitation. In order to investigate the performance of the CA-DDCOP algorithm, we apply the CA-DDCOP algorithm to multi-radio multi-channel channel allocation in ad hoc networks. The network nodes communicate with their neighbors, and coordinate their channel configuration according to their channel interference-aware so as to maximize their online rewards. Simulation results show that the CA-DDCOP algorithm can solve the dynamic channel allocation problem effectively.