Fundamentals of Computational Swarm Intelligence

ISBN-13: 9780470091913 / Angielski / Twarda / 2005 / 616 str.

Andries P. Engelbrecht

Opis

Fundamentals of Computational Swarm Intelligence provides a comprehensive introduction to the new computational paradigm of Swarm Intelligence (SI), a field that emerged from biological research, and is now picking up momentum within the computational research community. Bio-inspired systems are becoming increasingly important research areas for computer scientists, engineers, economists, bioinformaticians, operational researchers, and many other disciplines. This book introduces the reader to the mathematical models of social insects collective behaviour, and shows how they can be used in solving optimization problems. Focusing on the algorithmic implementation of models of swarm behavior, this book:

• Examines how social network structures are used to exchange information among individuals, and how the aggregate behaviour of these individuals forms a powerful organism.
• Introduces a compact summary of the formal theory of optimisation.
• Outlines paradigms with relations to SI, including genetic algorithms, evolutionary programming, evolutionary strategies, cultural algorithms and co-evolution.
• Looks at the choreographic movements of birds in a flock as a basis for the Particle Swarm Optimization (PSO) models, and provides an extensive treatment of different classes of PSO models.
• Shows how the behaviour of ants can be used to implement Ant Colony Optimization (ACO) algorithms to solve real-world problems including routing optimization, structure optimization, data mining and data clustering.
• Considers different classes of optimization problems, including multi-objective optimization, dynamic environments, discrete and continuous search spaces, constrained optimization, and niching.

• Includes an accompanying website containing Java classes and implementations of the different algorithms that can be used to test PSO and ACO algorithms: http: //si.cs.up.ac.za

The interdisciplinary nature of this field will make Fundamentals of Computational Swarm Intelligence an essential resource for readers with diverse backgrounds. In addition, it will be an excellent reference for computer scientists, practitioners in business or industry and researchers involved in the analysis, design and simulation of multibody systems. Advanced undergraduates and graduate students in artificial intelligence, collective intelligence and engineering will also find this book an invaluable tool.

Spis treści

List of Tables.

List of Figures.

List of Algorithms.

Preface.

1. Introduction.

PART I: OPTIMIZATION THEORY.

2. Optimization Problems and Methods.

2.1 Basic ingredients of optimization problems.

2.2 Optimization problem classifications.

2.3 Optimality conditions.

2.4 Optimization method classes.

2.5 General conditions for convergence.

2.6 Summary.

3. Unconstrained Optimization.

3.1 Problem definition.

3.2 Optimization algorithms.

3.3 Example benchmark problems.

3.4 Summary.

4. Constrained Optimization.

4.1 Definition.

4.2 Constraint handling methods.

4.3 Example benchmark problems.

4.4 Summary.

5. Multi–solution Problems.

5.1 Definition.

5.2 Niching algorithm categories.

5.3 Example benchmark problems.

5.4 Summary.

6. Multi–objective Optimization.

6.1 Multi–objective problem.

6.2 Pareto–optimality.

6.3 Summary.

7. Dynamic Optimization Problems.

7.1 Definition.

7.2 Dynamic environment types.

7.3 Example benchmark problems.

7.4 Summary.

PART II: EVOLUTIONARY COMPUTATION.

8. Introduction to Evolutionary Computation.

8.1 General evolutionary algorithm.

8.2 Representation.

8.3 Initial population.

8.4 Fitness function.

8.5 Selection.

8.6 Reproduction operators.

8.7 Evolutionary computation versus classical optimization.

8.8 Summary.

9. Evolutionary Computation Paradigms.

9.1 Genetic algorithms.

9.2 Genetic programming.

9.3 Evolutionary programming.

9.4 Evolution strategies.

9.5 Differential evolution.

9.6 Cultural algorithms.

9.7 Summary.

10. Coevolution.

10.1 Competitive coevolution.

10.2 Cooperative coevolution.

10.3 Summary.

PART III: PARTICLE SWARM OPTIMIZATION.

11. Introduction.

12. Basic Swarm Optimization.

12.1 Full PSO model.

12.2 Social network structures.

12.3 Basic variations.

12.4 Basic PSO parameters.

12.5 Performance measures.

12.6 PSO versus EC.

12.7 Summary.

13. Particle Trajectories.

13.1 Convergence.

13.2 Surfing the waves.

13.3 Swarm equilibrium.

13.4 Constricted trajectories.

13.5 Unconstricted trajectories.

13.6 Parameter selection heuristics.

13.7 Summary.

14. Convergence Proofs.

14.1 Convergence proof for basic PSO.

14.2 PSO with guaranteed local convergence.

14.3 Global convergence of PSO.

14.4 Summary.

15. Single–Solution Particle Swarm Optimization.

15.1 Social based PSO algorithms.

15.2 Hybrid algorithms.

15.3 Sub–swarm–based PSO.

15.4 Memetic PSO algorithms.

15.5 Multi–start PSO algorithms.

15.6 Repelling methods.

15.7 Summary.

16. Niching with Particle Swarm Optimization.

16.1 Niching capability of basic PSO.

16.2 Sequential PSO niching.

16.3 Parallel PSO niching.

16.4 Quasi–sequential niching.

16.5 Performance measures.

16.6 Summary.

17. Constrained Optimization Using Particle Swarm Optimization.

17.1 Reject infeasible solutions.

17.2 Penalty function methods.

17.3 Convert to unconstrained problems.

17.4 Repair methods.

17.5 Preserving feasibility methods.

17.6 Pareto ranking methods.

17.7 Boundary constraints.

17.8 Applications.

17.9 Summary.

18. Multi–Objective Optimization with Particle Swarms.

18.1 Objectives of MOO.

18.2 Basic PSO versus MOO.

18.3 Aggregation–based methods.

18.4 Criterion–based methods.

18.5 Dominance–based methods.

18.6 Performance measures.

18.7 Summary.

19. Dynamic Environments with Particle Swarm Optimization.

19.1 Consequences for PSO.

19.2 PSO solutions for dynamic environments.

19.3 Performance measurement in dynamic environments.

19.4 Applications of PSO to dynamic problems.

19.5 Summary.

20. Discrete Particle Swarm Optimization.

20.1 Binary PSO.

20.2 General Discrete PSO.

20.3 Example applications.

20.4 Design of combinational circuits.

20.5 Summary.

21. Particle Swarm Optimization Applications.

21.1 Neural networks.

21.2 Game learning.

21.3 Clustering applications.

21.4 Design applications.

21.5 Scheduling and planning applications.

21.6 Controllers applications.

21.7 Applied mathematics.

21.8 Applications in power systems.

21.9 Miscellaneous applications.

21.10 Summary.

PART VI: ANT ALGORITHMS.

22. Introduction.

23. Ant Colony Optimization Meta–Heuristic.

23.1 Foraging behaviour of ants.

23.2 Simple ant colony optimization.

23.3 Early ant algorithms.

23.4 Parameter settings.

23.5 Summary.

24. General Frameworks for Ant Colony Optimization Algorithms.

24.1 ACO algorithms characteristics.

24.2 Generic frameworks.

24.3 Summary.

25. Ant Colony Optimization Algorithms.

25.1 Single colony ACO algorithms.

25.2 Continuous ACO.

25.3 Multiple colony algorithms.

25.4 Hybrid ACO algorithms.

25.5 Multi–objective optimization.

25.6 Dynamic optimization problems.

25.7 Parallel ACO algorithms.

25.8 Summary.

26. Ant Colony Optimization Applications.

26.1 General requirements.

26.2 Ordering problems.

26.3 Assignment problems.

26.4 Subset problems.

26.5 Grouping problems.

26.6 Summary.

27. Collective Decision–Making.

27.1 Stigmergy.

27.2 Artificial Pheromone.

27.3 Heterarchy.

27.4 Summary.

28. Ant Colony Optimization Convergence.

28.1 Convergence proofs and characteristics.

28.2 Convergence measures.

28.3 Summary.

29. Cemetery Organisation and Brood Care.

29.1 Basic ant colony clustering model.

29.2 Generalized ant colony clustering model.

29.3 Minimal model for ant clustering.

29.4 Ant clustering ensemble.

29.5 Hybrid clustering approaches.

29.6 Ant clustering applications.

29.7 Summary.

30. Division of Labor.

30.1 Division of labor in insect colonies.

30.2 Task allocation based on response thresholds.

30.3 Adaptive task allocation and specialization.

30.4 Summary.

31. Final Remarks.

References.

Further Reading.

Appendix A: Acronyms.

Appendix B: Symbols.

B.1 Part I – Optimization Theory.

B.2 Part II – Evolutionary Computation.

B.3 Part III – Particle Swarm Optimization.

B.4 Part IV – Ant Algorithms.

Index.

O autorze

Prof Andries P. Engelbrecht, Computational Intelligence Research Group, Department of Computer Science, School of Information Technology, University of Pretoria, Pretoria 0002, South Africa

His areas of expertise include: artificial neural networks, swarm intelligence, evolutionary computation, data mining and artificial immune systems. He has been active in this area since 1994 and he is one of the few people in the field leading a very active research group in Swarm Intelligence, specifically in Particle Swarm Optimization (PSO). Particularly he is currently developing a number of new PSO approaches which are unique contributions to the field. His research group has produced about 15% of the total number of articles on PSO.

Blurb

Fundamentals of Computational Swarm Intelligence Provides a comprehensive introduction to the new computational paradigm of swarm intelligence (SI), a field that emerged from biological research, and which is now picking up momentum within the computational research community. Bio–inspired systems are becoming increasingly important research areas for computer scientists, engineers, economists, bioinformaticians, operational researchers, and many other disciplines. This book introduces the reader to the mathematical models of social insects′ collective behaviour, and shows how they can be used in solving optimization problems.

Focusing on the algorithmic of modes of swarm behaviour, this book:

• Examines how social network structures are used to change information among individuals, and how the aggregate behaviour of these individuals forms a powerful organism.
• Introduces a compact summary of the formal theory of optimization.
• Outlines paradigms with relations to SI, including genetic algorithms, evolutionary programming, evolutionary strategies, cultural algorithms and co–evolutionary.
• Looks at the choreographic movements of birds in a flock as a basis for the particle swarm optimization (PSO) different classes of PSO models.
• Shows how the behaviour of ants can be used to implement Ant Colony Optimization (ACO) algorithms to solve real–world problems including routing optimization, structure optimization, data mining, and data clustering.
• Considers different classes of optimization problems, including multi–objective optimization, dynamic environments, discrete and continuous search spaces, constrained optimization, and niching.
• Includes an accompanying website containing java classes and implementations of the different algorithms that can be used to test PSO and ACO algorithms: http://si.cs.up.ac.za

The interdisciplinary nature of this field will make Fundamentals of Computational Swarm Intelligence an essential resource for readers with diverse backgrounds. Practitioners in business or industry and researchers involved in the analysis, design and simulation of multibody systems. Advanced undergraduates and graduate students in artificial intelligence, collective intelligence and engineering will also find this book an invaluable tool.