Ant Colony Algorithms:
Theory and Applications

TITLE: Ant Colony Algorithms: Theory and Applications AUTHOR: HaiBin DUAN
PUBLISHER: Science Press EDITION: 1st 

In ant societies, the activities of the individuals, as well as of the society as a whole, are not regulated by any explicit form of centralized control. On the other hand, adaptive and robust behaviors transcending the behavioral repertoire of the single individual can be easily observed at society level. These complex global behaviors are the result of selforganizing dynamics driven by local interactions and communications among a number of relatively simple individuals. The simultaneous presence of these and other fascinating and unique characteristics have made ant societies an attractive and inspiring model for building new algorithms and new multiagent systems. In the last decade, ant societies have been taken as a reference for an ever growing body of scientific work.
Among the different works inspired by ant colonies, the ant colony algorithm(ACA) is probably the most successful and popular one. ACA is a novel bioinspired optimization algorithm, which simulates the foraging behavior of ants for solving various complex combinatorial optimization problems. This book clearly defines ACA and its complexities, and presents both the most significant theoretical achievements and the stateoftheart of ACA applications, especially the hardware realization of ACA. This book is broadly divided into 10 chapters and is organized as follows.
Chapter 1 starts with a description of the biological characteristics ants. On the basis of the introduction of the idea origins of ACA, the development of ACA is illustrated.
Chapter 2 presents a wellstructured definition of basic ACA, and detailed implementation process and complexity analyses of basic ACA are also presented in this chapter.
Chapter 3 is dedicated to discuss the indepth convergence proofs for specific classes of ACAs.
Chapter 4 presents detailed experimental analyses on the effect of pertinent parameters and ant colony behaviors in ACA, and an effective “threestep” method for optimum configuration of pertinent parameters in ACA is concluded in this chapter.
Chapter 5 is devoted to the explanation of improvement strategies of ACA in discrete space optimization, and this description takes advantage of the traveling salesman problem(TSP).
Chapter 6 is devoted to the explanation of improvement strategies of ACA in continuous space optimization.
Chapter 7 presents the stateoftheart of ACA typical applications in various fields. The main application principles, that is, rules of thumb to be followed when attacking a new problem, are identified and discussed in this chapter.
Chapter 8 reports on what is currently known about the hardware realization of ACA.
Chapter 9 presents a systematic comparison and detailed combination of ACA and other bioinspired optimization algorithms.
Chapter 10 outlines some ongoing and most promising research trends in ACA.
Finally, there are four appendixes, which are programs of basic ACA, web sources about ACA, terminology(ChineseEnglish) and a piece of poetry extolling ACA.
This book is intended primarily for (1) advanced undergraduate and graduate students in computer science, cybernetics, management science and other related majors; (2) academic and industry researchers in artificial intelligence and computational intelligence; (3) practitioners willing to learn how to implement ACA to solve various combinational optimization problems. 
Preface Abstract Chapter 1 Introduction 1.1 Introduction 1.2 Biological Characteristics of Ants 1.3 Idea Origins of Ant Colony Algorithm(ACA) 1.4 Development of ACA 1.5 Outline of the Book 1.6 Summary References Chapter 2 Principles and Complexity Analysis of Basic ACA 2.1 Introduction 2.2 Principles of Basic ACA 2.3 Systematic Characteristics of Basic ACA 2.4 Mathematical Model of Basic ACA 2.5 Implementation of Basic ACA 2.6 Complexity Analysis of Basic ACA 2.7 Performance Criteria of Basic ACA 2.8 Summary References Chapter 3 Convergence Proofs for ACAs 3.1 Introduction 3.2 Convergence Proof for the Graghbased Ant System(GBAS) 3.3 Short Convergence Proof for a Class of Improved ACA 3.4 Deterministic Convergence Proof for GBAS/tdev and GBAS/tdlb 3.5 A. S. Convergence Proof for Basic ACA 3.6 Convergence Results for a Class of Distributed Ant Routing Algorithms 3.7 Branching Process and Branching Wiener Process based ACA 3.8 Convergence Analysis for a simple ACA 3.9 Markov Convergence Analysis for the Combination of ACA and Genetic Algorithm 3.10 Convergence Analysis for a Class of Generalized ACA(GACA) 3.11 Summary References Chapter 4 Experimental Analysis of ACA and Optimum Configuration Principles of Pertinent Parameters in ACA 4.1 Introduction 4.2 Experimental Analysis of the Effect of Pertinent Parameters and Ant Colony Behaviors in ACA 4.3 “Threestep” Method for Optimum Configuration of Pertinent Parameters in ACA 4.4 Summary References Chapter 5 Improved ACAs in Discrete Space Optimization 5.1 Introduction 5.2 Selfadaptive ACA 5.3 Crossromoving and Local Optimization Strategies based ACA 5.4 Pheromone Diffusion based ACA 5.5 Polymorphic ACA 5.6 Modellearning based Littlewindow ACA 5.7 Hybrid Behavior based ACA 5.8 Improved ACA with Clustering 5.9 Cloud Models Theory based ACA 5.10 Sensational and Consciousness ACA 5.11 Improved ACA with Random Perturbation Behavior 5.12 Information Entropy based ACA 5.13 Summary References Chapter 6 Improved ACAs in Continuous Space Optimization 6.1 Introduction 6.2 Gridding Partion based ACA 6.3 Trail Distributed Function based ACA 6.4 Selfadaptive ACA for Solving Continuous Space Optimization Problems 6.5 Cross and Mutation Operation based ACA 6.6 Improved ACA with Embedded Deterministic Searching 6.7 Dense Heterarchy Continuous Interacting ACA 6.8 Improved ACA for Multiobjective Optimization Problems 6.9 Dynamicwindowsearch ACA for Complex Multistage Decisionmaking Problems 6.10 Summary References Chapter 7 Typical Applications of ACA 7.1 Introduction 7.2 Jobshop Scheduling Problem(JSP) 7.3 Network Routing Problem 7.4 Vehicle Routing Problem(VRP) 7.5 Robot Field 7.6 Power System 7.7 Fault Diagnosis 7.8 Parameter Optimization 7.9 System Identification 7.10 Clustering Analysis 7.11 Data Mining 7.12 Imagine Processing 7.13 Route Planning 7.14 Aircombat Decisionmaking 7.15 Geotechnical Engineering 7.16 Chemical Industry 7.17 Life Science 7.18 Layout Optimization 7.19 Summary References Chapter 8 Hardware Realization of ACA 8.1 Introduction 8.2 Overview of Bioinspired Hardware 8.3 FPGA Implementation of ACA 8.4 Hardware/Software Partioning based on Dynamic Combination of ACA and GA 8.5 Summary References CChapter 9 Comparison and Combination of ACA and Other Bioinspired Optimization Algorithms 9.1 Introduction 9.2 Principles of Several Typical Bioinspired Optimization Algorithms 9.3 Comparison of ACA and Other Bioinspired Optimization Algorithms 9.4 Combination of ACA and GA 9.5 Combination of ACA and Artificial Neural Network (ANN) 9.6 Combination of ACA and Particle Swarm Optimization (PSO) 9.7 Combination of ACA and Artificial Immune Algorithm (AIA) 9.8 Summary References Chapter 10 Prospects 10.1 Introduction 10.2 Model Improvement of ACA 10.3 Theoretical Analysis of ACA 10.4 Parellelization of ACA 10.5 Application Fields of ACA 10.6 Hardware Realization of ACA 10.7 Intelligent Combination of ACA 10.8 Summary References Appendix A: Programs of Basic ACA A.1 C Language Version A.2 Matlab Language Version A.3 Visual Basic Language Version Appendix B: Web Sources about ACA Appendix C: terminology (ChineseEnglish) and Abbreviations Appendix D: (Poetry) Zhe Hu Tian·ACA

Copyright © 2006 By HaiBin Duan, All rights reserved