BioInspired Computing, Lectures 3-4 (swarms & ACO)

COM3524

What are the three main principles of Swarm Intelligence?

1) Emergence - complex problems solved by simple individuals,

2) Robustness - ability to cope with loss of individuals,

3) Distributed and autonomous - agents have only local sensory information & perform simple actions

What is stigmergy?

A mechanism of indirect coordination through the environment, where the trace left by an action stimulates the performance of a next action by the same or different agent.

What are the three basic behaviours of a Boid in Reynolds' flocking model?

1) Separation - maintain distance from other boids,

2) Cohesion - move towards center of mass of neighbors,

3) Alignment - align velocity with neighboring boids.

For a boid, how does separation force depend on distance?

Separation force is a function of inverse distance: f(d_ij) = 1/(d_ij)^n where n ∈ ℕ, with stronger force at closer distances.

Give two applications of Reynolds' Boids model.

1) Computer graphics industry (e.g., The Lion King 1994)

2) Scientific investigation of theories of organization for flocks, herds, and schools.

What are termites an example of in swarm intelligence?

Stigmergic behavior - they use pheromones to build complex structures through simple decentralized rules without knowing the global state.

How do termites build complex structures like mounds?

Each insect deposits mudball with pheromones, and are attracted to nestmates' pheromones, dropping mudballs near neighbors, leading to pillars, arches, tunnels, and chambers over time.

What is Particle Swarm Optimization (PSO) inspired by?

Birds flocking to find the best food area - combining three strategies: brave (keep flying same direction), conservative (fly back to own best position), swarm (move toward best neighbor).

What does each particle in PSO track?

position vector x_p

velocity vector v_p

performance/fitness at current position f(x_p)

personal best position x_pbest

global best position known x_gbest

What do the three terms in PSO velocity equation represent?

a·v_p(t) = inertial term,

b·2·R1·s_pbest = memory term (autobiographical),

c·2·R2·s_gbest = cooperation term (shared knowledge).

Why is factor 2 included in PSO velocity update?

To allow overshoots around x_pbest and x_gbest, capturing the error range with random numbers between 0 and 1.

What is the basic principle of Ant Colony Optimization (ACO)?

Ants deposit pheromones on paths, others are attracted to pheromone trails. Shorter paths are traversed more frequently, accumulating more pheromone, leading to discovery of shortest paths.

What do parameters α and β control in the ACO equation?

α controls weighting of pheromone trail strength, β controls weighting of desirability (inverse distance to next node).

What are the two components in ant movement decision?

Pheromone strength (incrementally revised quantity, weighted by α) and desirability (fixed local quantity = 1/distance, weighted by β).

Name three applications of ACO.

1) Telecommunications and internet routing

2) Assignment and scheduling problems

3) Network routing with dynamic rerouting capability when nodes fail.

What is the Travelling Salesman Problem (TSP)?

Given a list of cities and distances between each pair, find the shortest possible route that visits each city exactly once and returns to the origin city.

[LAB] What trend was observed as TSP complexity increased?

Answers became less consistent, it was more difficult to determine the true minimum, and algorithms took longer to produce reasonable results.

What are three sources of randomness in Evolutionary Algorithms for TSP?

1) Randomly distributed initial population

2) Random nature of selection (roulette/tournament)

3) Random choice in mutation operators (e.g., TWORS swap).

What happens to EA iteration count when population size is halved?

66.7% found the number of iterations to find a good solution increased (fewer initial solutions means less likely to start near optimum).

What is the tradeoff with increasing EA population size?

Fewer iterations needed to converge (larger pool increases likelihood of good initial solutions), BUT actual time in seconds may be longer (each solution evaluated serially).

What is the optimal range for mutation probability (mp) in EA for TSP?

Intermediate range, typically around 0.35-0.55 or centered near 0.5, depending on problem complexity. Too low = may not find optimum, too high = risk losing good solutions.

What effect did increasing mutation probability (mp) have in EA experiments?

90.2% observed solutions became less accurate (further from true solution) as mp increased beyond optimal range.

What is the optimal range for crossover probability (cp) in EA for TSP?

Intermediate range, typically 0.5-0.75. Too low = less likely to combine good parent subsets, too high = risk losing good solutions.

Which mutation operator performed best for TSP?

RSM (Reverse Sequence Mutation) performed best overall followed by TWORS, then CIM.

Using an energy landscape analogy, what does a smaller EA population mean?

Less likely for initial solutions to be close to the optimum (fewer points sampling the landscape initially).

In the energy landscape analogy, what happens with high selection pressure?

Convergence towards a local minimum rather than exploring broadly for the global minimum (e.g., Select 10 fittest individuals).

What role does mutation play in the energy landscape analogy?

Mutation provides random jumps to explore the energy/fitness landscape (exploration of solution space).

What role does crossover play in the energy landscape analogy?

Crossover improves current solutions and drives solutions toward nearest local minimum (exploitation of potentially good solutions).

What was the optimal value of parameter α (alpha) in ACO experiments? (Weighting of trail pheromone strength)

Approximately α = 1 for most problems (82.9% for 15_nodestsp, 95.1% for bayg29tsp), though optimal value is problem-complexity dependent.

What effect did increasing α have in ACO?

90.2% observed algorithm became less accurate as α increased beyond optimal value. α controls weighting of pheromone trail strength.

What was the optimal value of parameter β (beta) in ACO?

Typically β = 5-10, with mode at β = 10 for many problems. β controls weighting of desirability (1/distance).

What effect did increasing β have in ACO accuracy?

65.2% observed solutions became more accurate up to a certain point (optimal intermediate range), then plateaued or worsened.

Which algorithm (EA or ACO) performed better for simpler TSP problems?

ACO was faster/more efficient for less complex problems (95% chose ACO for problems with

Which algorithm performed better for more complex TSP problems?

EA was more efficient for larger problems, as ACO's runtime scales directly with problem size while EA population can remain constant.

Why does ACO runtime scale differently than EA with problem size?

ACO's solution population (number of ants) is directly proportional to problem size (number of nodes), while EA population size can be kept constant.

How many possible routes exist for Belgium TSP (n=10 cities)?

n!/2 = 10!/2 ≈ 1.8 × 10^6 routes (dividing by 2 eliminates reverse routes).

Why is brute force infeasible for Botswana TSP (n=20)?

Number of routes = 20!/2 ≈ 1×10^18. At 1 microsecond per route evaluation, this would take approximately 10,000 years to evaluate all routes.