Difference between revisions of "A Brief Introduction to Swarm Intelligence"
(14 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
__NOTOC__ | __NOTOC__ | ||
+ | <center>H. Kemal Ilter<br>2019</center> | ||
+ | |||
==Intellectus (Nous)== | ==Intellectus (Nous)== | ||
Line 19: | Line 21: | ||
<div class="column"> | <div class="column"> | ||
<center>[[File:intellectus.png]]</center> | <center>[[File:intellectus.png]]</center> | ||
− | <center>{{Figure|''' | + | <center>{{Figure|'''Credit:''' E. Grant<ref>Edward Grant, "Celestial Orbs in the Latin Middle Ages", Isis, Vol. 78, No. 2. (Jun., 1987), pp. 152-173.</ref>.}}</center> |
</div> | </div> | ||
</div> | </div> | ||
Line 47: | Line 49: | ||
Brain-to-body mass ratio | Brain-to-body mass ratio | ||
− | |||
</div> | </div> | ||
<div class="column"> | <div class="column"> | ||
<center>[[File:nocturnal-squid.jpg]]</center> | <center>[[File:nocturnal-squid.jpg]]</center> | ||
− | <center>{{Figure|''' | + | <center>{{Figure|'''Credit:''' Wikimedia Commons, Nhobgood<ref>[https://commons.wikimedia.org/wiki/User:Nhobgood Wikimedia Commons, Nhobgood].</ref>.}}</center> |
</div> | </div> | ||
Line 59: | Line 60: | ||
Practopoiesis | Practopoiesis | ||
− | Conceptual bridge between biological and artificial | + | |
− | + | Conceptual bridge between biological and artificial intelligence. | |
− | + | ||
+ | * Weak AI | ||
+ | * Strong AI | ||
+ | |||
AI-hard or AI-complete | AI-hard or AI-complete | ||
Line 69: | Line 73: | ||
-360 | -360 | ||
− | Aristotle described the syllogism, a method of formal, | + | Aristotle described the syllogism, a method of formal, mechanical thought. |
+ | |||
1206 | 1206 | ||
Al-Jazari created a programmable orchestra of mechanical human beings | Al-Jazari created a programmable orchestra of mechanical human beings | ||
+ | |||
1600 | 1600 | ||
− | René Descartes proposed that bodies of animals are | + | René Descartes proposed that bodies of animals are nothing more than complex machines |
+ | |||
1642 | 1642 | ||
Blaise Pascal invented the mechanical calculator, the first digital calculating machine | Blaise Pascal invented the mechanical calculator, the first digital calculating machine | ||
+ | |||
1769 | 1769 | ||
Wolfgang von Kempelen built and toured with his chess-playing automaton, The Turk | Wolfgang von Kempelen built and toured with his chess-playing automaton, The Turk | ||
+ | |||
1913 | 1913 | ||
− | Bertrand Russell and Alfred North Whitehead published Principia Mathematica, which revolutionized formal logic 1931 | + | Bertrand Russell and Alfred North Whitehead published Principia Mathematica, which revolutionized formal logic |
+ | |||
+ | 1931 | ||
Kurt Gödel, father of theoretical computer science | Kurt Gödel, father of theoretical computer science | ||
+ | |||
1950 | 1950 | ||
− | Alan Turing proposes the Turing Test as a measure of | + | Alan Turing proposes the Turing Test as a measure of machine intelligence |
+ | |||
1997 | 1997 | ||
The Deep Blue chess machine (IBM) defeats the (then) world chess champion, Garry Kasparov | The Deep Blue chess machine (IBM) defeats the (then) world chess champion, Garry Kasparov | ||
+ | |||
2005 | 2005 | ||
− | Blue Brain is born, a project to simulate the brain at | + | Blue Brain is born, a project to simulate the brain at molecular detail |
+ | |||
2011 | 2011 | ||
IBM’s Watson computer defeated television game show Jeopardy! champions Rutter and Jennings | IBM’s Watson computer defeated television game show Jeopardy! champions Rutter and Jennings | ||
+ | |||
2011 | 2011 | ||
− | Apple’s Siri, Google’s Google Now and Microsoft’s | + | Apple’s Siri, Google’s Google Now and Microsoft’s Cortana are smartphone apps that use natural language to answer questions, make recommendations and perform actions |
==AI Tools== | ==AI Tools== | ||
Search and optimization | Search and optimization | ||
− | Search algorithm, Mathematical optimization and | + | |
+ | Search algorithm, Mathematical optimization and Evolutionary computation | ||
+ | |||
Logic | Logic | ||
+ | |||
Logic programming and Automated reasoning | Logic programming and Automated reasoning | ||
+ | |||
Probabilistic methods for uncertain reasoning | Probabilistic methods for uncertain reasoning | ||
+ | |||
Bayesian network, Hidden Markov model, Kalman filter, Decision theory and Utility theory | Bayesian network, Hidden Markov model, Kalman filter, Decision theory and Utility theory | ||
+ | |||
Classifiers and statistical learning methods | Classifiers and statistical learning methods | ||
− | Classifier (mathematics), Statistical classification and | + | |
+ | Classifier (mathematics), Statistical classification and Machine learning | ||
+ | |||
Neural networks | Neural networks | ||
+ | |||
Artificial neural network and Connectionism | Artificial neural network and Connectionism | ||
+ | |||
Control theory Languages | Control theory Languages | ||
==42== | ==42== | ||
− | In the radio series and the first novel, a group of hyper- | + | In the radio series and the first novel, a group of hyper-intelligent pan-dimensional beings demand to learn the |
Answer to the Ultimate Question of Life, The Universe, and Everything | 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 | + | 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 meaningless because the beings who instructed it never actually knew what the Question was. |
The Ultimate Question: | The Ultimate Question: | ||
What do you get if you multiply six by nine? | What do you get if you multiply six by nine? | ||
Line 117: | Line 143: | ||
==Swarm Intelligence== | ==Swarm Intelligence== | ||
− | Swarm intelligence (SI) is the collective behavior of decentralized, self- | + | Swarm intelligence (SI) is the collective behavior of decentralized, self-organized systems, natural or artificial. Introduced by Gerardo Beni and Jing Wang in 1989, in the context of cellular robotic systems. |
Examples in natural systems of SI: | Examples in natural systems of SI: | ||
• Ant colonies | • Ant colonies | ||
Line 136: | Line 162: | ||
Nature Inspired Search Techniques | Nature Inspired Search Techniques | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | Ant colony optimization | + | <div class="columns"> |
− | A probabilistic technique in metaheuristic optimizations. | + | <div class="column"> |
− | + | ''Particle swarm optimization.'' Simulating social behaviour. | |
− | + | * Kennedy, J.; Eberhart, R. (1995). “Particle Swarm Optimization”. 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 Conference on Evolutionary Computation. pp. 69–73. | ||
+ | * Kennedy, J. (1997). “The particle swarm: social adaptation of knowledge”. Proceedings of IEEE International Conference on Evolutionary Computation. pp. 303– 308. | ||
+ | </div> | ||
+ | <div class="column"> | ||
+ | <center>[[File:psi-example.png]]</center> | ||
+ | <center>{{Figure|'''Credit:''' M. E. H. Pedersen<ref>Pedersen, M.E.H., Tuning & Simplifying Heuristical Optimization, PhD Thesis, 2010, University of Southampton, School of Engineering Sciences, Computational Engineering and Design Group.</ref>.}}</center> | ||
+ | </div> | ||
+ | </div> | ||
+ | |||
+ | <div class="columns"> | ||
+ | <div class="column"> | ||
+ | ''Ant colony optimization.'' A probabilistic technique in metaheuristic optimizations. | ||
+ | * A. Colorni, M. Dorigo et V. Maniezzo, Distributed Optimization by Ant Colonies, actes de la première conférence européenne sur la vie artificielle, Paris, France, Elsevier Publishing, 134-142, 1991. | ||
+ | * M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy, 1992. | ||
+ | </div> | ||
+ | <div class="column"> | ||
+ | <center>[[File:aco-example.png]]</center> | ||
+ | <center>{{Figure|'''Credit:''' Wikimedia Commons<ref>[https://commons.wikimedia.org/wiki/File:Aco_shortpath.svg Wikimedia Commons].</ref>.}}</center> | ||
+ | </div> | ||
+ | </div> | ||
+ | |||
+ | ''Artificial bee colony algorithm.'' Intelligent foraging behaviour. | ||
+ | * D. Dervis Karaboga, An Idea Based On Honey Bee Swarm for Numerical Optimization, Technical Report-TR06,Erciyes University, Engineering Faculty, Computer Engineering Department 2005. | ||
− | |||
− | |||
− | |||
Multi-level thresholding | Multi-level thresholding | ||
+ | |||
MR brain image classification Face pose estimation | MR brain image classification Face pose estimation | ||
− | Differential evolution | + | ''Differential evolution.'' A method that optimizes a problem by iteratively trying to improve a candidate solution. |
− | A method that optimizes a problem by iteratively trying to improve a candidate solution. | + | * Storn, R.; Price, K. (1997). “Differential evolution - a simple 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 | + | Parallel computing |
+ | |||
+ | Multi-objective 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, Manufacturing 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 Continuous Optimisation Algorithms, Soft Computing, 1-33. | ||
+ | |||
+ | Optimisation of classifiers/Clustering systems | ||
+ | |||
+ | Manufacturing | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
Bioengineering | Bioengineering | ||
+ | |||
Multi-objective optimization | Multi-objective optimization | ||
− | Artificial immune systems | + | ''Artificial immune systems.'' A class of computationally intelligent systems. Adaptive systems. |
− | A class of computationally intelligent systems. Adaptive systems. | + | * J.D. Farmer, N. Packard and A. Perelson, (1986) “The immune system, adaptation and machine learning”, Physica D, vol. 2, pp. 187–204. |
− | + | ||
− | J.D. Farmer, N. Packard and A. Perelson, (1986) “The | ||
Bioinformatics | Bioinformatics | ||
− | Bat algorithm | + | ''Bat algorithm.'' A metaheuristic optimization algorithm. |
− | A metaheuristic optimization algorithm. | + | * X. S. Yang, A New Metaheuristic Bat-Inspired Algorithm, 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 | Engineering design | ||
+ | |||
Classifications of gene expression data | Classifications of gene expression data | ||
− | Glowworm swarm optimization | + | ''Glowworm swarm optimization.'' The algorithm makes the agents glow at intensities approximately proportional to the function value being optimized. |
− | The algorithm makes the agents glow at intensities | + | * 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. Multiagent and Grid Systems, 2(3):209- 222. | |
− | + | * K.N. Krishnanand and D. Ghose. (2009). Glowworm swarm optimization for simultaneous capture of multiple local optima of multimodal functions. Swarm Intelligence, 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 Autonomous Systems, 56(7):549- 569. | |
− | + | ||
+ | ''Gravitational search algorithm.'' Based on the law of gravity and the notion of mass interactions. | ||
+ | * 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 independent of the type of animal that is in the swarm. | ||
+ | * Buhl, J.; Sumpter, D. J. T.; Couzin, D.; Hale, J. J.; Despland, E.; Miller, E. R.; Simpson, S. J. (2006). “From disorder to order in marching locusts” (PDF). Science 312 (5778): 1402–1406. | ||
− | + | ''Stochastic diffusion search.'' An agent-based probabilistic global search and optimization technique best suited to problems where the objective function can be decomposed into multiple independent partial-functions. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
A comprehensive mathematical framework. | A comprehensive mathematical framework. | ||
− | + | ||
− | Multi-swarm optimization | + | * Bishop, J.M., Stochastic Searching Networks, Proc. 1st IEE Int. Conf. on Artificial Neural Networks, pp. 329- 331, London, UK, (1989). |
− | Use of multiple sub-swarms instead of one (standard) swarm. | + | |
− | Multi-swarm system effectively combines components from Particle swarm optimization, Estimation of | + | ''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 distribution algorithm, and Differential evolution into a multiswarm hybrid. | ||
+ | |||
+ | {{references}} |
Capacity for
Credit: E. Grant[1].
Animals
Neuroscience and intelligence
Human
Primate
Brain-to-body mass ratio
Credit: Wikimedia Commons, Nhobgood[2].
Practopoiesis
Conceptual bridge between biological and artificial intelligence.
AI-hard or AI-complete
Artificial agent
-360 Aristotle described the syllogism, a method of formal, mechanical thought.
1206 Al-Jazari created a programmable orchestra of mechanical human beings
1600 René Descartes proposed that bodies of animals are nothing 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 machine 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 molecular 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 Cortana are smartphone apps that use natural language to answer questions, make recommendations and perform actions
Search and optimization
Search algorithm, Mathematical optimization and Evolutionary 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 Machine learning
Neural networks
Artificial neural network and Connectionism
Control theory Languages
In the radio series and the first novel, a group of hyper-intelligent 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 meaningless 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-organized systems, natural or artificial. Introduced by Gerardo Beni and Jing Wang in 1989, in the context of cellular 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.
Credit: M. E. H. Pedersen[3].
Ant colony optimization. A probabilistic technique in metaheuristic optimizations.
Credit: Wikimedia Commons[4].
Artificial bee colony algorithm. Intelligent foraging behaviour.
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.
Parallel computing
Multi-objective optimization
Constrained optimization
The bees algorithm. A population-based search algorithm.
Optimisation of classifiers/Clustering systems
Manufacturing
Bioengineering
Multi-objective optimization
Artificial immune systems. A class of computationally intelligent systems. Adaptive systems.
Bioinformatics
Bat algorithm. A metaheuristic optimization algorithm.
Engineering design
Classifications of gene expression data
Glowworm swarm optimization. The algorithm makes the agents glow at intensities approximately proportional to the function value being optimized.
Gravitational search algorithm. Based on the law of gravity and the notion of mass interactions.
Self-propelled particles. Predict robust emergent behaviours occur in swarms independent of the type of animal that is in the swarm.
Stochastic diffusion search. An agent-based probabilistic global search and optimization technique best suited to problems where the objective function can be decomposed into multiple independent partial-functions.
A comprehensive mathematical framework.
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 distribution algorithm, and Differential evolution into a multiswarm hybrid.
References
hkilter.com by H. K. Ilter is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License
© 2020 H. K. Ilter