Ant Colony Algorithms:

               Theory and Applications

TITLE: Ant Colony Algorithms:

             Theory and Applications   

AUTHOR       Hai-Bin DUAN     

PUBLISHER:   Science Press
ISBN:            7-03-016204-8
   Dec., 2005
PRICE:          ¥48.00

EDITION:       1st



        Book Review            Contents 


Book Review

        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 self-organizing 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 multi-agent 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 bio-inspired 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 state-of-the-art 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 well-structured 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 in-depth 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 “three-step” 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 state-of-the-art 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 bio-inspired 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(Chinese-English) 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.





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


 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


 Chapter 3 Convergence Proofs for ACAs

3.1 Introduction

3.2 Convergence Proof for the Gragh-based 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


 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 Three-step” Method for Optimum Configuration of Pertinent Parameters in ACA

4.4 Summary


 Chapter 5 Improved ACAs in Discrete Space Optimization

5.1 Introduction

5.2 Self-adaptive ACA

5.3 Cross-romoving and Local Optimization Strategies based ACA

5.4 Pheromone Diffusion based ACA

5.5 Polymorphic ACA

5.6 Model-learning based Little-window 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


 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 Self-adaptive 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 Dynamic-window-search ACA for Complex Multistage Decision-making Problems

6.10 Summary


 Chapter 7 Typical Applications of ACA

7.1 Introduction

7.2 Job-shop 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 Air-combat Decision-making

7.15 Geotechnical Engineering

7.16 Chemical Industry

7.17 Life Science

7.18 Layout Optimization

7.19 Summary


Chapter 8 Hardware Realization of ACA

8.1 Introduction

8.2 Overview of Bio-inspired Hardware

8.3 FPGA Implementation of ACA

8.4 Hardware/Software Partioning based on Dynamic Combination of ACA and GA

8.5 Summary


CChapter 9 Comparison and Combination of ACA and Other Bio-inspired Optimization Algorithms 

9.1 Introduction

9.2 Principles of Several Typical Bio-inspired Optimization Algorithms

9.3 Comparison of ACA and Other Bio-inspired 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


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


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 (Chinese-English) and Abbreviations

Appendix D: (Poetry) Zhe Hu Tian·ACA





                                   Copyright © 2006 By Hai-Bin Duan, All rights reserved