Difference between revisions of "A Brief Introduction to Swarm Intelligence"

(→Intelligence in Nature) |
|||

(5 intermediate revisions by the same user not shown) | |||

Line 3: | Line 3: | ||

==Intellectus (Nous)== | ==Intellectus (Nous)== | ||

+ | <div class="columns"> | ||

+ | <div class="column"> | ||

Capacity for | Capacity for | ||

* logic | * logic | ||

Line 14: | Line 16: | ||

* planning | * planning | ||

* creativity and problem solving | * creativity and problem solving | ||

− | + | </div> | |

+ | <div class="column"> | ||

<center>[[File:intellectus.png]]</center> | <center>[[File:intellectus.png]]</center> | ||

− | <center>{{Figure|'''Source:''' Edward Grant, "Celestial Orbs in the Latin Middle Ages", | + | <center>{{Figure|'''Source:''' Edward Grant, "Celestial Orbs in the Latin Middle Ages", Isis, Vol. 78, No. 2. (Jun., 1987), pp. 152-173.}}</center> |

+ | </div> | ||

+ | </div> | ||

==Intelligence in Nature== | ==Intelligence in Nature== | ||

+ | <div class="columns"> | ||

+ | <div class="column"> | ||

Animals | Animals | ||

− | + | * Human | |

− | + | * Non-human - g Factor | |

− | Vertabrates: Mammals, birds, reptiles, fish Cephalopods | + | ** Vertabrates: Mammals, birds, reptiles, fish Cephalopods |

− | Arthropods | + | ** Arthropods |

− | Plants - Perception? | + | ** Plants - Perception? |

+ | |||

Neuroscience and intelligence | Neuroscience and intelligence | ||

+ | |||

Human | Human | ||

− | + | * Brain volume | |

− | + | * Grey matter | |

− | + | * White matter | |

− | + | * Cortical thickness | |

− | + | * Neural efficiency | |

+ | |||

Primate | Primate | ||

− | + | * Brain size | |

+ | |||

Brain-to-body mass ratio | Brain-to-body mass ratio | ||

+ | </div> | ||

+ | <div class="column"> | ||

<center>[[File:nocturnal-squid.jpg]]</center> | <center>[[File:nocturnal-squid.jpg]]</center> | ||

<center>{{Figure|'''Source:''' https://commons.wikimedia.org/wiki/User:Nhobgood}}</center> | <center>{{Figure|'''Source:''' https://commons.wikimedia.org/wiki/User:Nhobgood}}</center> | ||

+ | </div> | ||

+ | |||

+ | </div> | ||

+ | |||

+ | ==Artificial Intelligence== | ||

+ | |||

+ | Practopoiesis | ||

+ | Conceptual bridge between biological and artificial intelli- gence. | ||

+ | • Weak AI | ||

+ | • Strong AI | ||

+ | AI-hard or AI-complete | ||

+ | |||

+ | Artificial agent | ||

+ | |||

+ | ==A LI’L HISTORY== | ||

+ | |||

+ | -360 | ||

+ | Aristotle described the syllogism, a method of formal, me- chanical thought. | ||

+ | 1206 | ||

+ | Al-Jazari created a programmable orchestra of mechanical human beings | ||

+ | 1600 | ||

+ | René Descartes proposed that bodies of animals are noth- ing more than complex machines | ||

+ | 1642 | ||

+ | Blaise Pascal invented the mechanical calculator, the first digital calculating machine | ||

+ | 1769 | ||

+ | Wolfgang von Kempelen built and toured with his chess-playing automaton, The Turk | ||

+ | 1913 | ||

+ | Bertrand Russell and Alfred North Whitehead published Principia Mathematica, which revolutionized formal logic 1931 | ||

+ | Kurt Gödel, father of theoretical computer science | ||

+ | 1950 | ||

+ | Alan Turing proposes the Turing Test as a measure of ma- chine intelligence | ||

+ | 1997 | ||

+ | The Deep Blue chess machine (IBM) defeats the (then) world chess champion, Garry Kasparov | ||

+ | 2005 | ||

+ | Blue Brain is born, a project to simulate the brain at mo- lecular detail | ||

+ | 2011 | ||

+ | IBM’s Watson computer defeated television game show Jeopardy! champions Rutter and Jennings | ||

+ | 2011 | ||

+ | Apple’s Siri, Google’s Google Now and Microsoft’s Cor- tana are smartphone apps that use natural language to answer questions, make recommendations and perform actions | ||

+ | |||

+ | ==AI Tools== | ||

+ | |||

+ | Search and optimization | ||

+ | Search algorithm, Mathematical optimization and Evolu- tionary computation | ||

+ | Logic | ||

+ | Logic programming and Automated reasoning | ||

+ | Probabilistic methods for uncertain reasoning | ||

+ | Bayesian network, Hidden Markov model, Kalman filter, Decision theory and Utility theory | ||

+ | Classifiers and statistical learning methods | ||

+ | Classifier (mathematics), Statistical classification and Ma- chine learning | ||

+ | Neural networks | ||

+ | Artificial neural network and Connectionism | ||

+ | Control theory Languages | ||

+ | |||

+ | ==42== | ||

+ | |||

+ | In the radio series and the first novel, a group of hyper-in- telligent pan-dimensional beings demand to learn the | ||

+ | Answer to the Ultimate Question of Life, The Universe, and Everything | ||

+ | from the supercomputer, Deep Thought, specially built for this purpose. It takes Deep Thought 71⁄2 million years to compute and check the answer, which turns out to be 42. Deep Thought points out that the answer seems mean- ingless because the beings who instructed it never actually knew what the Question was. | ||

+ | The Ultimate Question: | ||

+ | What do you get if you multiply six by nine? | ||

+ | The Answer: 613 × 913 = 4213 | ||

+ | |||

+ | ==Swarm Intelligence== | ||

+ | |||

+ | Swarm intelligence (SI) is the collective behavior of decentralized, self-orga- nized systems, natural or artificial. Introduced by Gerardo Beni and Jing Wang in 1989, in the context of cellu- lar robotic systems. | ||

+ | Examples in natural systems of SI: | ||

+ | • Ant colonies | ||

+ | • Bird flocking | ||

+ | • Animal herding | ||

+ | • Bacterial growth | ||

+ | • Fish schooling | ||

+ | • Microbial intelligence | ||

+ | Inspiration from Nature | ||

+ | 1. Social Insects | ||

+ | • Natural Navigation | ||

+ | • Natural Clustering | ||

+ | • Natural construction | ||

+ | 2. Foraging | ||

+ | 3. Flocking | ||

+ | |||

+ | ==Algorithms== | ||

+ | |||

+ | Nature Inspired Search Techniques | ||

+ | Particle swarm optimization | ||

+ | Simulating social behaviour. | ||

+ | • Kennedy, J.; Eberhart, R. (1995). “Particle Swarm Optimi- zation”. Proceedings of IEEE International Conference on Neural Networks IV. pp. 1942–1948. | ||

+ | • Shi, Y.; Eberhart, R.C. (1998). “A modified particle swarm optimizer”. Proceedings of IEEE International Confer- ence on Evolutionary Computation. pp. 69–73. | ||

+ | • Kennedy, J. (1997). “The particle swarm: social adapta- tion of knowledge”. Proceedings of IEEE International Conference on Evolutionary Computation. pp. 303– 308. | ||

+ | |||

+ | <center>[[File:psi-example.png]]</center> | ||

+ | <center>{{Figure|'''Source:''' Pedersen, M.E.H., Tuning & Simplifying Heuristical Optimization, PhD Thesis, 2010, University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group.}}</center> | ||

+ | |||

+ | Ant colony optimization | ||

+ | A probabilistic technique in metaheuristic optimizations. | ||

+ | • A. Colorni, M. Dorigo et V. Maniezzo, Distributed Op- timization by Ant Colonies, actes de la première con- férence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991. | ||

+ | • M. Dorigo, Optimization, Learning and Natural Algo- rithms, PhD thesis, Politecnico di Milano, Italy, 1992. | ||

+ | |||

+ | Artificial bee colony algorithm | ||

+ | Intelligent foraging behaviour. | ||

+ | • D. Dervis Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Re- port-TR06,Erciyes University, Engineering Faculty, Computer Engineering Department 2005. | ||

+ | Multi-level thresholding | ||

+ | MR brain image classification Face pose estimation | ||

+ | |||

+ | Differential evolution | ||

+ | A method that optimizes a problem by iteratively trying to improve a candidate solution. | ||

+ | • Storn, R.; Price, K. (1997). “Differential evolution - a sim- ple and efficient heuristic for global optimization over continuous spaces”. Journal of Global Optimization 11: 341–359.. | ||

+ | • Storn, R. (1996). “On the usage of differential evolution for function optimization”. Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS). pp. 519–523. | ||

+ | Parallel computing Multiobjective optimization Constrained optimization | ||

+ | |||

+ | The bees algorithm | ||

+ | A population-based search algorithm | ||

+ | • Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manu- facturing Engineering Centre, Cardiff University, UK, 2005. | ||

+ | • Pham, D.T., Castellani, M. (2009), The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems. Proc. ImechE, Part C, 223(12), 2919-2938. | ||

+ | • Pham, D.T. and Castellani, M. (2013), Benchmarking and Comparison of Nature-Inspired Population-Based Con- tinuous Optimisation Algorithms, Soft Computing, 1-33. | ||

+ | Optimisation of classifiers/Clustering systems Manufacturing | ||

+ | Bioengineering | ||

+ | Multi-objective optimization | ||

+ | |||

+ | Artificial immune systems | ||

+ | A class of computationally intelligent systems. Adaptive systems. | ||

+ | • | ||

+ | J.D. Farmer, N. Packard and A. Perelson, (1986) “The im- mune system, adaptation and machine learning”, Physica D, vol. 2, pp. 187–204. | ||

+ | Bioinformatics | ||

+ | |||

+ | Bat algorithm | ||

+ | A metaheuristic optimization algorithm. | ||

+ | • X. S. Yang, A New Metaheuristic Bat-Inspired Algo- rithm, in: Nature Inspired Cooperative Strategies for Optimization (NISCO 2010) (Eds. J. R. Gonzalez et al.), Studies in Computational Intelligence, Springer Berlin, 284, Springer, 65-74 (2010). | ||

+ | Engineering design | ||

+ | Classifications of gene expression data | ||

+ | |||

+ | Glowworm swarm optimization | ||

+ | The algorithm makes the agents glow at intensities ap- proximately proportional to the function value being opti- mized. | ||

+ | • K.N. Krishnanand and D. Ghose (2005). Detection of multiple source locations using a glowworm metaphor with applications to collective robotics. IEEE Swarm Intelligence Symposium, Pasadena, California, USA, pp. 84- 91. | ||

+ | • K.N. Krishnanand and D. Ghose. (2006). Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications. Multi- agent and Grid Systems, 2(3):209- 222. | ||

+ | • K.N. Krishnanand and D. Ghose. (2009). Glowworm swarm optimization for simultaneous capture of multi- ple local optima of multimodal functions. Swarm Intelli- gence, 3(2):87- 124. | ||

+ | • K.N. Krishnanand and D. Ghose. (2008). Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations. Robotics and Auton- omous Systems, 56(7):549- 569. | ||

+ | |||

+ | Gravitational search algorithm | ||

+ | Based on the law of gravity and the notion of mass interac- tions. | ||

+ | • Rashedi, E.; Nezamabadi-pour, H.; Saryazdi, S. (2009). “GSA: a gravitational search algorithm”. Information Science 179 (13): 2232–2248. | ||

+ | Self-propelled particles | ||

+ | Predict robust emergent behaviours occur in swarms inde- pendent of the type of animal that is in the swarm. | ||

+ | • Buhl, J.; Sumpter, D. J. T.; Couzin, D.; Hale, J. J.; Desp- land, E.; Miller, E. R.; Simpson, S. J. (2006). “From dis- order to order in marching locusts” (PDF). Science 312 (5778): 1402–1406. | ||

+ | |||

+ | Stochastic diffusion search | ||

+ | An agent-based probabilistic global search and optimiza- tion technique best suited to problems where the objective function can be decomposed into multiple independent partial-functions. | ||

+ | A comprehensive mathematical framework. | ||

+ | • Bishop, J.M., Stochastic Searching Networks, Proc. 1st IEE Int. Conf. on Artificial Neural Networks, pp. 329- 331, London, UK, (1989). | ||

+ | Multi-swarm optimization | ||

+ | Use of multiple sub-swarms instead of one (standard) swarm. | ||

+ | Multi-swarm system effectively combines components from Particle swarm optimization, Estimation of distri- bution algorithm, and Differential evolution into a multi- swarm hybrid. |

Capacity for

- logic
- abstract thought
- understanding
- self-awareness
- communication
- learning
- emotional knowledge
- memory
- planning
- creativity and problem solving

Animals

- Human
- Non-human - g Factor
- Vertabrates: Mammals, birds, reptiles, fish Cephalopods
- Arthropods
- Plants - Perception?

Neuroscience and intelligence

Human

- Brain volume
- Grey matter
- White matter
- Cortical thickness
- Neural efficiency

Primate

- Brain size

Brain-to-body mass ratio

Practopoiesis Conceptual bridge between biological and artificial intelli- gence. • Weak AI • Strong AI AI-hard or AI-complete

Artificial agent

-360 Aristotle described the syllogism, a method of formal, me- chanical thought. 1206 Al-Jazari created a programmable orchestra of mechanical human beings 1600 René Descartes proposed that bodies of animals are noth- ing more than complex machines 1642 Blaise Pascal invented the mechanical calculator, the first digital calculating machine 1769 Wolfgang von Kempelen built and toured with his chess-playing automaton, The Turk 1913 Bertrand Russell and Alfred North Whitehead published Principia Mathematica, which revolutionized formal logic 1931 Kurt Gödel, father of theoretical computer science 1950 Alan Turing proposes the Turing Test as a measure of ma- chine intelligence 1997 The Deep Blue chess machine (IBM) defeats the (then) world chess champion, Garry Kasparov 2005 Blue Brain is born, a project to simulate the brain at mo- lecular detail 2011 IBM’s Watson computer defeated television game show Jeopardy! champions Rutter and Jennings 2011 Apple’s Siri, Google’s Google Now and Microsoft’s Cor- tana are smartphone apps that use natural language to answer questions, make recommendations and perform actions

Search and optimization Search algorithm, Mathematical optimization and Evolu- tionary computation Logic Logic programming and Automated reasoning Probabilistic methods for uncertain reasoning Bayesian network, Hidden Markov model, Kalman filter, Decision theory and Utility theory Classifiers and statistical learning methods Classifier (mathematics), Statistical classification and Ma- chine learning Neural networks Artificial neural network and Connectionism Control theory Languages

In the radio series and the first novel, a group of hyper-in- telligent pan-dimensional beings demand to learn the Answer to the Ultimate Question of Life, The Universe, and Everything from the supercomputer, Deep Thought, specially built for this purpose. It takes Deep Thought 71⁄2 million years to compute and check the answer, which turns out to be 42. Deep Thought points out that the answer seems mean- ingless because the beings who instructed it never actually knew what the Question was. The Ultimate Question: What do you get if you multiply six by nine? The Answer: 613 × 913 = 4213

Swarm intelligence (SI) is the collective behavior of decentralized, self-orga- nized systems, natural or artificial. Introduced by Gerardo Beni and Jing Wang in 1989, in the context of cellu- lar robotic systems. Examples in natural systems of SI: • Ant colonies • Bird flocking • Animal herding • Bacterial growth • Fish schooling • Microbial intelligence Inspiration from Nature 1. Social Insects • Natural Navigation • Natural Clustering • Natural construction 2. Foraging 3. Flocking

Nature Inspired Search Techniques Particle swarm optimization Simulating social behaviour. • Kennedy, J.; Eberhart, R. (1995). “Particle Swarm Optimi- zation”. Proceedings of IEEE International Conference on Neural Networks IV. pp. 1942–1948. • Shi, Y.; Eberhart, R.C. (1998). “A modified particle swarm optimizer”. Proceedings of IEEE International Confer- ence on Evolutionary Computation. pp. 69–73. • Kennedy, J. (1997). “The particle swarm: social adapta- tion of knowledge”. Proceedings of IEEE International Conference on Evolutionary Computation. pp. 303– 308.

**Source:** Pedersen, M.E.H., Tuning & Simplifying Heuristical Optimization, PhD Thesis, 2010, University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group.

Ant colony optimization A probabilistic technique in metaheuristic optimizations. • A. Colorni, M. Dorigo et V. Maniezzo, Distributed Op- timization by Ant Colonies, actes de la première con- férence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991. • M. Dorigo, Optimization, Learning and Natural Algo- rithms, PhD thesis, Politecnico di Milano, Italy, 1992.

Artificial bee colony algorithm Intelligent foraging behaviour. • D. Dervis Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Re- port-TR06,Erciyes University, Engineering Faculty, Computer Engineering Department 2005. Multi-level thresholding MR brain image classification Face pose estimation

Differential evolution A method that optimizes a problem by iteratively trying to improve a candidate solution. • Storn, R.; Price, K. (1997). “Differential evolution - a sim- ple and efficient heuristic for global optimization over continuous spaces”. Journal of Global Optimization 11: 341–359.. • Storn, R. (1996). “On the usage of differential evolution for function optimization”. Biennial Conference of the North American Fuzzy Information Processing Society (NAFIPS). pp. 519–523. Parallel computing Multiobjective optimization Constrained optimization

The bees algorithm A population-based search algorithm • Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S and Zaidi M. The Bees Algorithm. Technical Note, Manu- facturing Engineering Centre, Cardiff University, UK, 2005. • Pham, D.T., Castellani, M. (2009), The Bees Algorithm – Modelling Foraging Behaviour to Solve Continuous Optimisation Problems. Proc. ImechE, Part C, 223(12), 2919-2938. • Pham, D.T. and Castellani, M. (2013), Benchmarking and Comparison of Nature-Inspired Population-Based Con- tinuous Optimisation Algorithms, Soft Computing, 1-33. Optimisation of classifiers/Clustering systems Manufacturing Bioengineering Multi-objective optimization

Artificial immune systems A class of computationally intelligent systems. Adaptive systems. • J.D. Farmer, N. Packard and A. Perelson, (1986) “The im- mune system, adaptation and machine learning”, Physica D, vol. 2, pp. 187–204. Bioinformatics

Bat algorithm A metaheuristic optimization algorithm. • X. S. Yang, A New Metaheuristic Bat-Inspired Algo- rithm, in: Nature Inspired Cooperative Strategies for Optimization (NISCO 2010) (Eds. J. R. Gonzalez et al.), Studies in Computational Intelligence, Springer Berlin, 284, Springer, 65-74 (2010). Engineering design Classifications of gene expression data

Glowworm swarm optimization The algorithm makes the agents glow at intensities ap- proximately proportional to the function value being opti- mized. • K.N. Krishnanand and D. Ghose (2005). Detection of multiple source locations using a glowworm metaphor with applications to collective robotics. IEEE Swarm Intelligence Symposium, Pasadena, California, USA, pp. 84- 91. • K.N. Krishnanand and D. Ghose. (2006). Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications. Multi- agent and Grid Systems, 2(3):209- 222. • K.N. Krishnanand and D. Ghose. (2009). Glowworm swarm optimization for simultaneous capture of multi- ple local optima of multimodal functions. Swarm Intelli- gence, 3(2):87- 124. • K.N. Krishnanand and D. Ghose. (2008). Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations. Robotics and Auton- omous Systems, 56(7):549- 569.

Gravitational search algorithm Based on the law of gravity and the notion of mass interac- tions. • Rashedi, E.; Nezamabadi-pour, H.; Saryazdi, S. (2009). “GSA: a gravitational search algorithm”. Information Science 179 (13): 2232–2248. Self-propelled particles Predict robust emergent behaviours occur in swarms inde- pendent of the type of animal that is in the swarm. • Buhl, J.; Sumpter, D. J. T.; Couzin, D.; Hale, J. J.; Desp- land, E.; Miller, E. R.; Simpson, S. J. (2006). “From dis- order to order in marching locusts” (PDF). Science 312 (5778): 1402–1406.

Stochastic diffusion search An agent-based probabilistic global search and optimiza- tion technique best suited to problems where the objective function can be decomposed into multiple independent partial-functions. A comprehensive mathematical framework. • Bishop, J.M., Stochastic Searching Networks, Proc. 1st IEE Int. Conf. on Artificial Neural Networks, pp. 329- 331, London, UK, (1989). Multi-swarm optimization Use of multiple sub-swarms instead of one (standard) swarm. Multi-swarm system effectively combines components from Particle swarm optimization, Estimation of distri- bution algorithm, and Differential evolution into a multi- swarm hybrid.