Week 8: Ant Colony Optimization Flashcards

Question 1

Q

What is a "swarm"?

Answer

A

A group of agents which communicate with each other by acting on their local environment. Their interactions result in a distributive collective problem-solving strategy

Question 2

Q

Interaction between agents in a swarm results in a distributive collective problem-solving strategy. This complex behaviour is not a property of any \_\_\_\_\_\_ \_\_\_\_\_\_ in the swarm, but emerges from their \_\_\_\_\_\_\_

Answer

A

single agent
 interactions

Question 3

Q

For swarms, interaction in biological systems happens in 2 ways. What are they?

Answer

A

1. Direct: physical contact, or by visual, audio, or chemical perception
 
 2. Indirect: local change in the environment, known as "Stigmergy"

Question 4

Q

Insects react to signals that activate a \_\_\_\_\_\_\_ \_\_\_\_\_\_\_ reaction. The effect of these reactions serve as signals to the \_\_\_\_\_\_ insect, or \_\_\_\_\_ insects

Answer

A

genetically encoded
 sender
 other

Question 5

Q

What is computational swarm intelligence?

Answer

A

Building computational models to solve complex problems based on models of behaviours in biological swarms

Question 6

Q

What are some design issues with computational swarm intelligence

Answer

A

- Modeling the agent (or individual)
 - The interaction process
 - Adaptation and Cooperation

Question 7

Q

What are two examples of computational swarm intelligence models?

Answer

A

1. Ant Colony Optimization (ACO)
 
 2. Particle Swarm Optimization (PSO)

Question 8

Q

What does Ant Colony Optimization (ACO) model?

Answer

A

Simple behaviour of pheromone trail following at ants

Question 9

Q

Particle Swarm Optimization models 2 simple behaviours. What are they?

Answer

A

- Moving towards its best closest neighbour
 - Moving back to its own best state

Question 10

Q

In ACO and PSO, the agent/individual is very \_\_\_\_\_\_ and doesn't \_\_\_\_\_\_ at the individual level

Answer

A

simple
 learn

Question 11

Q

What is the range of Ant Colony sizes?

Answer

A

as few as 30 ants, and as large as a million ants

Question 12

Q

Define Stigmergy
 
 Note that ACO uses Stigmergy

Answer

A

Stigmergy is a form of self-organization. It produces complex, seemingly intelligent structures, without need for any planning, control, or even direct communication between all the agents.
 
 Extra: It supports efficient collaboration between extremely simple agents, who may lack memory or individual awareness of each other

Question 13

Q

What are the 3 properties of Stigmergy?
 
 Note that ACO uses Stigmergy

Answer

A

1. Indirect modification of the environment
 
 2. Environmental modification serves as external memory
 
 3. Work can be continued by any individual

Question 14

Q

Ants walking to or from a food source deposit a chemical substance on its way. What is this substance?

Answer

A

Pheromone. Ants deposit pheromone when walking to or from a food

Question 15

Q

Whenever an ants deposit pheromone, how do other ants use it?
 What influence will it have on other ants?
 What path will ants tend to follow?

Answer

A

- Other ants can smell pheromone
 
 - In the presence of pheromone, it will influence the ants' choice of their path
 
 - Ants tend to follow the path with the stronger pheromone trail

Question 16

Q

How are pheromone trails formed?
 What is the purpose of them?

Answer

A

- Pheromone trails are formed by the pheromone deposited on the ground by the ants
 
 - Pheromone trails help the ants to reach good food sources that have been previously identified by other ants

Question 17

Q

What was the conclusion drawn from the binary bridge experiment with ACOs?
 
 The binary bridge experiment involves two bridges which have equal lengths and lead to a food source

Answer

A

- Initially the ants randomly chose a bridge to follow
 
 - After a while, the ants tended to follow the bridge with a stronger pheromone trail
 
 - The selection of one bridge is due to random fluctuations causing it to have higher pheromone concentration

Question 18

Q

What was the conclusion drawn from the non-equal bridge experiment with ACOs?
 
 The non-equal bridge experiment involves two bridges in which one bridge is shorter than the other. They both lead to a food source

Answer

A

- Ants following the shorter bridge will be the first to reach the food source
 
 - Ants following the shorter bridge were the first to reach the nest, since they took the same path home
 
 - All the ants eventually converged to the shorter path due to the pheromone depositing mechanism

Question 19

Q

In ACO, what does the pheromone trail act as?
 
 Does the pheromone evaporate over time? what effect does this have?

Answer

A

- The Pheromone trail acts as collective memory for the ants to communicate by sensing and recording their foraging experience
 
 - Pheromone evaporates overtime which affects the environment

Question 20

Q

Suppose we have an ACO, the environment has two paths of different lengths
 
 What are the initial pheromone values assigned to the paths?

Answer

A

The pheromone values for each path will be equal to each other, and greater than zero.
 
 т_1 = т_2 = c > 0

Question 21

Q

Suppose we have an ACO, the environment has two paths of different lengths
 
 What are the probabilities for the ants to traverse the first path and the second path?

Answer

A

Ants will traverse the first path:
 p1 = т_1/(т_1 + т_2)
 
 Ants will traverse the second path:
 p2 = 1-p1

Question 22

Q

In ACO, usually an evaporation phase is applied in which pheromone is updated.
 
 What is the reason for this?

Answer

A

- To simulate the evaporation of real pheromone
 - To avoid quick convergence to sub-optimal paths

Question 23

Q

In AS ACO, usually an evaporation phase is applied in which pheromone is updated.
 What is the formula for this?

Answer

A

т_i = (1 - ρ)*т_i
 
 ρ ∈ (0,1)
 
 ρ specifies the rate of evaporation

Question 24

Q

With each update, each ant leaves more \_\_\_\_\_\_\_ on its \_\_\_\_\_\_\_ path

Answer

A

pheromone

traversed

Question 25

Q

In real ant colonies, what does the following 5 concepts correspond to for artificial ant colonies?
 
 1. Ant and Pheromone
 2. Food
 3. Continuous ant movements
 4. Pheromone updating while moving
 5. Solution paths being evaluated implicitly

Answer

A

For artificial ant colonies:
 
 1. Ant = Agent, Pheromone = Value
 
 2. Solution
 
 3. Discrete movement of ants
 
 4. Pheromone updates after traversal
 
 5. Explicit function to evaluate solutions

Question 26

Q

For the ACO algorithm, describe the problem space environment as a graph. 
 
 What is the simple ant algorithm used for?

Answer

A

There is a graph G=(N,E) 
 N - the set of nodes (vertices) 
 E - the set of arcs (edges) 
 
 Each arc (i,j) is associated with a value d_ij denoting the distance between nodes i and j

There is a source node (where all the ants start at)and a goal node (food source) 
 A simple ant algorithm is used to find the shortest path between two given nodes in the graph

Question 27

Q

In the ACO algorithm graph, each arc (edge) is associated with a value.
 
 What does value denote? and what is it initialized to?
 
 Upon initialization, what is placed at the source node (nest)?

Answer

A

- Each arc (i,j) is associated with a value т_ij called the "artificial pheromone"
 
 - At the beginning, all arcs are given the same pheromone value
 
 - There are "m" ants placed at the source node

Question 28

Q

In ACO, at each node "i", the ant has a choice to move to any of the "j" nodes connecting to it.

For an ant on node “i”,each node “j” has a probability of being selected equal to p_ij. What isp_ij? What doesα andß mean in the expression for p_ij?

Answer

A

if "j" is not connected to"i", then p_ijwill be 0.

α andß are used to balance the local vs global search ability of the ant

Question 29

Q

What areα andß used in the ACO probability equation?

Answer

A

α - improve the global search ability of the ant (explorative)
ß - improve the local search ability of the ant (exploitative,greedy)

Question 30

Q

In AS ACO, what is the equation for evaporating the artificial Pheromone?
When anantdeposits extra Pheromone on the arc (edge) that it chooses, whats the equation?
What effect does depositing Pheromonehave on the probability of a subsequent ant choosing the same arc (edge)?

Answer

A

Evaporating artificial Pheromone is:т_ij= (1-ρ)*т_ij,ρ∈(0,1] is the rate of evaporation
Ants deposit extraPheromone as:т_ij=т_ij+Δт
Whenever Pheromone is deposited, the probability for subsequent ants to choose that arc is increased. This is known as “online step-by-step” pheromone update

Question 31

Q

In ACO, There are two “online step-by-step” approaches for choosing the value ofΔт - which is used to update the pheromone on each step.

What are these two approaches?

Answer

A

Ant density model.Pheromone is updated by adding Q, (a constant value), hence the final pheromone added to the edge will be proportional to the number of ants choosing it. Edge length is not considered here.
Ant quantity model. Pheromone is updated by adding Q/d_ij,taking the edge length into account, hence enforcing the ant local search ability
* Note:In online step-by-step, ants release pheromone while building their solutions *

Question 32

Q

In ACO, an alternative to the "online step-by-step" pheromone update approach is to use the "online delayed" pheromone update approach - sometimes referred to as the "ant cycle model"

Describe the “online delayed” pheromone update approach. How does it compare to other approaches? It has a special name, what is it?

Answer

A

Online delayed:

After the ant builds the solution, it traces the path backwards, and updates the pheromone trails on the visited arcs according to the solution quantity.

Updates aredone by makingΔт_ij= Q / L^k, where Q is a random number, and L^kis the length of the path found by ant “k”. Thus, the Pheromone update is:т_ij=т_ij + Q / L^kfor online delayed. This is completed after the evaporation phase.

This approach normally performs better, and is referred to as “Ant System Algorithm (AS)”

Question 33

Q

What are the termination conditions for ACO?

Answer

A

- Max number of iterations reached

- Acceptable solution is reached
 
 - All ants (or most of them) follow the same path,ie. stagnation

Question 34

Q

Describe the high level step-by-step algorithm of the ACO metaheuristic

Answer

A

Set parameters, initialize the Pheromone trails
Check if the termination criteria are met,and terminate if they are, otherwise continue
Construct Ant Solutions
Apply Local Search (Optional)
Update Pheromones
Go to step 2

Question 35

Q

What are the 4parameters in ACO? Describe each one

Answer

A

1. Number of ants. More ants means more computations, but also means more exploration

2. Max number of iterations. Has to be enough to allow convergence
 
 3. Initial Pheromone. Can be constant, random, maximum value, or a small value
 
 4. Pheromone decay parameterρ

Question 36

Q

What are the 7componentsin an ACO algorithm?

Answer

A

Transition rule: probability of selection for the ant
Pheromone evaporation rule
Pheromone update rule
Problem heuristic if used
Quality of solution measure
Memory or list for constraints (Tabu list)
Termination Criteria

Question 37

Q

What is the main difference between ACO Algorithm and theAnt System Algorithm?

Answer

A

- Uses the same basic steps outlined in ACO

- The “online delayed” pheromone update is adoped usin all the solutions of the current iteration, that is:
 
 Δτ_ij= Q/L^kfor the kth path
 
 τ_ij=τ_ij+ Q/L^k

Question 38

Q

What is the main differences betweenAnt Colony System (ACS) algorithm and Ant System (AS) Algorithm?

Answer

A

The Ant Colony System (ACS) algorithm is based on the Ant System (AS) algorithm, but differs in:

Transition rule based on elitist strategy (there is an elite). This balances exploration & exploitation
Pheromone update rule
Local Pheromone update
Candidate list

Question 39

Q

What are the 7parameters used in the Ant Colony System (ACS) algorithm?

Answer

A

τ_ij- Pheromone trail combination of (i,j)

n_ij- Local Heuristic combination of (i,j)
 
 p_ij- Transition probability of combination (i,j)
 
 α - Relative importance of pheromone trail
 
 ß - Relative importance of local heuristic
 
 q0 - Relative importance of exploitation vs exploration
 
 ρ - Trail persistence (Pheromone decay factor)

Question 40

Q

In Ant Colony System (ACS) algorithm, how does each ant select the next node "j"?

Answer

A

1. Generate a random number q between 0 and 1

2. If q < q0, then j = maximum of all neighboursτ_ij* n_ij^ß
 
 3. Else, generate probabilities for each neighbour using p_ij
 
 
 * Note: this creates bias for choices of better quality, in which q0 controls the bias *
 Note that n_ij = 1/cost_ij

Question 41

Q

ACS uses offline pheromone update. How does this work?

Answer

A

Only theglobally best ant (i.e., the ant which constructed theshortest tour from thebeginning of the trial) is allowedto deposit pheromone.

Question 42

Q

In the Ant Colony System (ACS) algorithm, the original ant system was modified in three aspects. What are they?

Answer

A

- The edge selection is biased towards exploitation (i.e. favoring the probability of selecting the shortest edges with a large amount of pheromone);

- While building a solution, ants change the pheromone level of the edges they are selecting by applying a local pheromone updating rule;
 
 - At the end of each iteration, only the best ant is allowed to update the trails by applying a modified global pheromone updating rule

Question 43

Q

In ACS (ant colony system) algorithm, how is the pheromone updated?
 What are the equation for this?
 When selecting the best, is it iteration best, global best, or both?
 
 Recall that it uses an elitist approach

Answer

A

Firstly pheromones are updated based on the either the iteration best or the global best:
 
 τ_ij = (1 - ρ_1) * τ_ij + ρ_1 * Δτ_ij_best
 
 Next, an online step-by-step update is performed after the global update of τ_ij. We ensure that no pheromone falls below τ_0:
 
 τ_ij = (1 - ρ_2) * τ_ij + ρ_2*τ_0

Question 44

Q

In the Max-Min Ant System (MMAS) Algorithm, how is the update done? Equation?

Answer

A

The update is done using:
 - The best solution (best ant) in the current iteration or best solution overall
 - The decay in the update of the pheromone
 
 τ_ij = (1 - ρ_1) * τ_ij + ρ_1 * Δτ_ij_best

Question 45

Q

In the Max-Min Ant System (MMAS) Algorithm, the values of the pheromone are restricted between τ_min and τ_max.
 
 What is the purpose of this?
 How are these values chosen?
 What effect does this have on performance (compared to AS)?

Answer

A

- τ_min and τ_max allow for high exploration in the beginning and more intensification later
 
 - τ_min and τ_max are chosen experimentally, although they could be calculated analytically if the optimal solution is known
 
 - Performance is significantly better than AS

Question 46

Q

What are 3 applications of ACO?

Answer

A

1. Traveling Salesman Problem (TSP)
 2. Assembly Line Balancing (ALB)
 3. Cell Assignment in PCS networks (CA)

Question 47

Q

What happens in the "Construct Ant Solutions" step in ACO algorithm?

Answer

A

For each ant:
 - A new node is selected chosen according to the selection probability formula
 - (sometimes) This node's added to the ant's tabu list, so that it doesn't get re-selected

Question 48

Q

What happens in the "Apply Local Search" step in ACO algorithm? What are these actions referred to as?

Answer

A

One of the following is typically used:
 - Apply local search method in order to improve the constructed solution
 - Add extra pheromone (known as delayed update) based on the collection of some global information
 These actions are referred to as daemon actions

Question 49

Q

What happens in the "Update Pheromones" step in ACO algorithm?

Answer

A

- Apply pheromone evaporation
 - Update the pheromone trails using a chosen set of good solutions

Question 50

Q

In ACO, when Pheromones are updated, what are recommended approaches for updating pheromones based on good solutions?

Answer

A

- All the solutions found in the current iteration
 - The best solution found in the current iteration
 - The best solution found so far

Question 51

Q

What effect does adjusting α or β have on the ACO algorithm?

Answer

A

When α is increased, the importance of the pheromone values is increased
 
 When β is increased, the importance of the distance is increased

Question 52

Q

What happens after an ant completes a search from source node to goal node in ACO? (assume online delayed)

Answer

A

- Pheromone trails get evaporated
 - The ant that found a solution will enforce a pheromone value Q/L on all the edges (L is the length of the path)

Question 53

Q

In ACS algorithm, we can perform the algorithm without pheromone, or without heuristics
 
 What effect does this have on the algorithm?
 
 Why is one better than the other?
 
 What about ACS with both?

Answer

A

- ACS without heuristics performs better than ACS without pheromone
 
 - ACS with Pheromone and no Heuristics is still guided. by the global update rule (which reflects the importance of the solution)
 
 - ACS without pheromone reduces to a stochastic multi-greedy algorithm
 
 - ACS with Pheromone AND Heuristics is better. Confirms the role of cooperation

Question 54

Q

For TSP, does ACS outperform GA, or SA?

Answer

A

Yes, ACS outperforms Genetic Algorithm and Simulated Annealing for Traveling Salesman Problem

Question 55

Q

Which parameter integrates heuristics in ACO?

Answer

A

A given node can have a property of
 n_j
 
 Which determines the "goodness" of that node according to the heuristic

Question 56

Q

How does the transition probability inACS change with and without heuristics?

Question 57

Q

What are the characteristics of problems that can be solved with ACO?

Answer

A

Combinatorial Optimization Problems
Problems which aren’t feasible to solve using classical optimization methods if the problem size is large
Discrete optimization problems (there are some variants of ACO for continuous problems)

Question 58

Q

What are the advantages of ACO?

Answer

A

ACO is stochastic, population based method
ACO retains memory of the entire colony instead of just previous generation (as in GA)
ACO is less affected by poor initial solutions due to combinations of random path selection
Can handle dynamic environments

Question 59

Q

What are the disadvantages of ACO?

Answer

A

Mainly experimental. There is little theoretical analysis.
It may take a long time to converge
It uses a lot of parameters, selection of values is experimental

Question 60

Q

In ACSGA, we have Genetic Annealing (GA) running on top of Ant Colony System (ACS) for adaptation.

What is the purpose of the GA? How does this affect the ant’s performance

Answer

A

GA runs on top the ACS to optimizes its parameters:

q0, the parameter determining whether the greedy or probabilistic selection is adopted
ρ, the local pheromone updating factor
ß, the relative importance of the visibility heuristic

Each ant would have its own values of these parameters in a fixed range ([0,1], [0,1], [1,127])

Question 61

Q

In ACSGA, we have Genetic Annealing (GA) running on top of Ant Colony System (ACS) for adaptation.

How are the GA chromosomes initialized?
What type of crossover?
What type of mutation?

Answer

A

In ACSGA:

Chromosomes are randomly initialized
Crossover was the single simple crossover
Mutation was bit-wise mutation (mutate every bit on a given probability)

Question 62

Q

In ACSGA, we have Genetic Annealing (GA) running on top of Ant Colony System (ACS) for adaptation.

Give the high level step-by-step of this algorithm

Answer

A

For each Generation:
1. Choose the best 4 individuals

For each of the 4 individuals, run ACS TSP on the given parameters. Record the result as the individual’s fitness.
The global pheromone update is done by the ant which produced the best tour
Choose the 2 individuals with the best fitness from the chosen 4
Produce the 2 children by crossover or copy from the 2 chosen best individuals
Mutate the 2 children
Replace the worst 2 individuals from the chosen 4 in the population with the 2 children

Question 63

Q

There are two approaches to investigate cooperation between different ant colonies in ACO.
Describe them

Answer

A

A heterogeneous approach, in which the ants in the two colonies have different behaviours (different optimization criteria)
A homogeneous approach, in which all the ants show a similar behaviour

Question 64

Q

For cooperative ACO with a ________ approach, each colony was used to optimize a ______ criteria

Answer

A

heterogeneous

different

Answer 64

A

moderate
colonies
single

Answer 65

A

Alpha encourages exploration

Answer 66

A

Beta encourages exploitation

Brainscape's Knowledge GenomeTM

Week 8: Ant Colony Optimization Flashcards

Brainscape's Knowledge Genome^TM