Transcript Swarm intelligence - Winona State University

Swarm Intelligence
Alex Stundzia
What is Swarm Intelligence?

Describes the collective behavior of
decentralized, self organized systems
◦ Both Natural and Artificial

Introduced in 1989

Gerardo Beni and Jing Wang
◦ Working on Cellular Automaton

Swarm Intelligence Systems are typically a set of simple
agents (machines) interacting locally with each other
agent
 Follows very simple rules
No central control to dictate how individual agents should
behave
Global patterns emerge from the individual agents
behavior


Swarm Intelligence Applications

Natural
◦ Flocks/Swarms
 Ants, Birds, Fish
◦ Bacterial Growth

Artificial
◦ Optimization Problems
◦ Artificial Life Simulations
 Cellular Automata
Cellular Automata

Cellular automaton is a very simple virtual machine
 Exhibits complex life-like behavior
Example and properties of a one-dimensional binary machine
Rule Set:
Neighbor 1
1
1
1
1
0
0
0
0
Current Cell State
1
1
0
0
1
1
0
0
Neighbor 2
1
0
1
0
1
0
1
0
>
>
>
>
>
>
>
>
>
Cell Next State
0
1
1
0
1
1
1
0
Input = 0010100010010100010000011…

Rules can produce “random” behavior

Fully deterministic based on rule set

Patterns can reflect/predict actions found in nature
◦ How water flows, how ice freezes
Cellular Automata is a necessary to understanding global patterns
exhibited in swarm intelligence
Optimization Using Swarm
Intelligence

Each individual agent has a fitness level
◦ Fitness is determined using rules common to
each other agent
◦ Differences in position and sensory inputs
affect overall fitness level
Optimization Using Swarm
Intelligence

Simple Optimization Problem
◦ 4 + x = 10000
◦ Fitness is measured as difference between actual
and desired results
◦ Estimate the fitness by taking 1/error





Error
Error
Error
Error
Error
=
=
=
=
=
f(1) = -9995
f(1000) = -8996
f(10000) = 4
f(9995) = 1
f(9995.999) = .001
Fitness = -.0001
Fitness = -.00011
Fitness = .25
Fitness = -1
Fitness = 1000
◦ Fitness will approach infinity when desired answer
is approached (1/0)
Combinatorial Optimization

Travelling Salesman Problem
◦ Consider 3 Cities, A, B, C
◦ Possible Permutations:
 ABC, ACB, BAC, BCA, CAB, CBA = 6 Permutations
 N! permutations
◦ Consider 12 Cities
 479,001,600 permutations
◦ Goal = Find the Shortest Path from Start to Finish
 Achieve this by designing rules to be run in parallel with one
another (heuristics)
 We can consider each individual connection
 We can abandon each route that fails to meet the given rules
◦ Question: You are visiting three cities, Rochester, MN; St.
Paul, MN; and Chicago, IL; Your starting location is La
Crosse, WI
 What is the fastest route?
◦ Importance of heuristics becomes clear as the number of
permutations grows
◦ The term “combination” refers to the situation where
some number of elements is selected from the list of
possibilities, without regard to their order
{Rochester, St. Paul, Chicago} contains these combinations:
{Rochester},{St. Paul},{Chicago},
{Rochester, St. Paul},{Rochester, Chicago},
{St. Paul, Chicago}, {Rochester, St. Paul, Chicago}
Possible Heuristic: Abandon the search when the selected
combination is bound to fail (length is longer than what
was found already)
Similar to how a human brain indexes data
 Necessity for threading is evident in a 3D
environment
 Heuristic exists that brain utilizes

Artificial Neural Networks

An attempt to mimic neural networks found in biology

Usually used to model complex relationships between
inputs and outputs
Also used to find patterns in data
“Learns” from observed data


A feedforward neural network:
information moves in only one
direction, forward, from the input
nodes, through the hidden nodes (if
any) and to the output nodes. There
are no cycles or loops in the network.
Parkinson’s Disease


Particle Swarm Optimization is used to detect Parkinson’s
disease
Actigraphs collect information while attached to patient’s
wrist
 Only record on one axis
Parkinson’s Disease

Using a feedforward neural network and the information
from the actigraphs, Dr Robert Worth & Dr Wojcieszek
created a data set from a particle swarm algorithm
Patient
Normal
Normal
Tremor
Tremor
Normal
Normal
Tremor
Tremor
Output 1 Output 2
0.053
0.948
0.027
0.973
0.917
0.088
0.981
0.019
0.181
0.813
0.025
0.975
0.038
0.962
0.982
0.02
Parkinson’s Disease
Subject with Parkinson’s
Disease
Control Subject
Particle Swarm Optimization

Suppose the following scenario:
A group of birds are randomly searching food in an area.
There is only one piece of food in this area. None of the
birds know the location of the food, but they know how
far away they are at any time.

Best Strategy to find the food?
 Follow the bird which is nearest to the food

Each bird represents a “particle”
Each bird has a fitness, and a velocity
The particles will follow the optimum particles


Particle Swarm Optimization

Can easily be simulated in software
Particle Swarm Optimization

Can be observed in nature
Ant Colony Optimization




In the real world, ants initially wander randomly
Upon finding food, they return to their ant colony while
laying down pheromone trails
Other ants who discover this path will follow it
 If these ants find food, they will also lay down
pheromones
Over time, pheromones evaporate
 Allows for ants to find new trails to food sources
This lets the colony “choose” which trails are the best to
find food
Ant Colony Optimization

Paths that remain will be the paths of least resistance
(most optimal to find food)
Ant Colony Optimization

Ants communicate through their environment
 Exchange information indirectly through pheromones

We can use ACO to help produce solutions to the
travelling salesman problem
 Combinatorial optimization
Future of Swarm Intelligence
Work Cited
Kennedy, James. Swarm Intelligence. San Francisco, CA: Academic
Press, 2001.
Marco, A. "Ant Colony Optimization". Université Libre de Bruxelles.
3/20/2010 <http://www.acometaheuristic.
org/>.
Huang, Haomiao. "How Robots Think". ars technicia. 3/20/2010
<http://arstechnica.com/science/news/2010/03/how-robotsthink.ars/>.
Cellular Automata Java Program:
http://www.mirekw.com/ca/mjcell/mjcell.html