Natural Computation Methods for Machine Learning Note 14
Swarm Intelligence
Intelligence < Social behavior
 Intelligence can emerge from social interaction.

Emergent behaviour – when a group behaves in ways that were not ”programmed” into its members

Swarm intelligence
 simulated social interaction
 emergent collective intelligence in groups of simple agents
Bird flocks and fish schools
 Local interaction
 No leader
 Simple local rules – a weighted combination of several goals
 match velocity of neighbours
 avoid collisions with neighbours
 avoid getting too far from neighbours
 Sufficient to make very realistic simulations
 used in movies and computer graphics
 remove the matchvelocity rule: insect swarm
 remove collision rule: cultural interaction
Ants
 Individual ants can not find shortest route. The colony does.
 Ant colonies are much more intelligent than ants.
 Ant colonies build cognitive map in their environment, through pheromone trails.
Stigmergy ❗❗❗
Indirect communication and coordination, by local modification and sensing of the environment.
Computational tools
 Cellular automata
 Ant Colony Optimization
 Particle Swarm Optimization
Cellular automata
 Massively parallel system of identical communicating state machines (cells).
 A cell’s state (e.g. on/off) is a function of the states of it communicates with (its neighbours).
 Used to model/animate fluids (e.g. the water in Find Nemo), gases, bacterial growth, swaying grass, social interaction, epidemics, in ecological simulations etc.
application:
 Construction and repair
 Collaborating simple robots
 Modelling
 Water, avalanches, traffic flows
 Map/level generators for games
Ant Colony Optimization
Family of combinatorial optimization algorithms, based on ant behaviour
Common benchmark: the Travelling Salesman Problem (TSP)
Common ’real’ applications: Scheduling and Network routing (AntNet)
Members: ACS, AntQ, MMAS, ASrank,
 most of which are extensions to Dorigo’s Ant
System (AS)
Traveling Salesman Problems (TSP)
 Find the shourtest tour through N cities, and then back to the starting point, such that each city is visited once and only once.
 NPhard
 (N1)!/2 possible tours
 exhaustive search intractable
 Specialized algorithms exist
 and are hard to beat
Ant System for TSP
Each ant (k)
 is placed in a randomly selected city
 remembers the partial solution found so far (initially, the start city only)
 moves stochastically from city (i) to city (j), by some transition probability p_{i j}^{k}(t)
which depends on
 pheromone intensity, \tau_{i j}
 local information, \eta_{i j} (distance)
 whether j is feasible (not already visited)
Transition probabilities
Effects of \alpha and \beta
p_{i j}^{k}(t)=\frac{\left[\tau_{i j}(t)\right]^{\alpha} *\left[\eta_{i j}\right]^{\beta}}{\sum_{c \in C_{i}^{k}}\left[\tau_{i c}(t)\right]^{\alpha} *\left[\eta_{i c}\right]^{\beta}}, j \in C_{i}^{k}
 If a=0, b>0
 Pheromone information discarded, only local info used
 Stochastic greedy search with multiple starting points
 If a>0, b=0
 No local information used, only pheromones
 May lead to premature convergence
Pheromone update
When all ants have completed a tour, let each
ant deposit pheromones on the paths it followed
\tau_{i j}(t+1)=(1\rho) \tau_{i j}(t)+\sum_k \Delta \tau_{k}{i j}^{k}(t) \quad \forall(i, j)
\rho Evaporation rate(蒸发率) 1<\rho\leq 1
k Sum over all ants, k
\Delta \tau_{i j}^{k}(t)=\left{\begin{array}{cl}1 / L_{k}(t)&\text { if path ij was used by ant } k\\0&\text { otherwise }\end{array}\right.
L_{k}(t)= length of ant k’s tour
Ant Colony Opt
 ACO is most promising for nonstationary
problems (e.g. network routing)  The TSP solution demonstrated here
works, but is not stateoftheart
What is "optimal"?
This is different from other course
In practice, optimality includes other factors as well
 time and cost to setup (not only to run)
 amount of knowledge required
 sufficiently good is often good enough
It is often better to use an algorithm/method you know well,
than to search for (and tune) the "best" one.
But, of course, if you happen to know the best one ...
文章评论