Week 8: Ant Colony Optimization Flashcards

Question

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 1

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

Answer 2

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

Answer 3

- 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

Answer 4

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

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

Answer 5

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

Answer 6

- Evaporating artificial Pheromone is: т_ij = (1-ρ)*т_ij , ρ∈(0,1] is the rate of evaporation - Ants deposit extra Pheromone 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

Answer 7

1. 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. 2. 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 *

Answer 8

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 are done by making Δт_ij = Q / L^k, where Q is a random number, and L^k is the length of the path found by ant "k". Thus, the Pheromone update is: т_ij = т_ij + Q / L^k for online delayed. This is completed after the evaporation phase. This approach normally performs better, and is referred to as "Ant System Algorithm (AS)"

Answer 9

- Max number of iterations reached

- Acceptable solution is reached

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

Answer 10

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

Answer 11

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 ρ

Answer 12

1. Transition rule: probability of selection for the ant 2. Pheromone evaporation rule 3. Pheromone update rule 4. Problem heuristic if used 5. Quality of solution measure 6. Memory or list for constraints (Tabu list) 7. Termination Criteria

Answer 13

- 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^k for the kth path

τ_ij = τ_ij + Q/L^k

Answer 14

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

Answer 15

τ_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)

Answer 16

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

Answer 17

Only the globally best ant (i.e., the ant which constructed the shortest tour from the beginning of the trial) is allowed to deposit pheromone.

Answer 18

- 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

Answer 19

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

Answer 20

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

Answer 21

- τ_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

Answer 22

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

Answer 23

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

Answer 24

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

Answer 25

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

Answer 26

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

Answer 27

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

When β is increased, the importance of the distance is increased

Answer 28

- 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)

Answer 29

- 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

Answer 30

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

Answer 31

A given node can have a property of
n_j

Which determines the "goodness" of that node according to the heuristic

Answer 32

- 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)

Answer 33

- 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

Answer 34

- 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

Answer 35

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])

Answer 36

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

Answer 37

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

Answer 38

- 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

Answer 39

heterogeneous | different

Answer 40

moderate colonies single

Answer 41

Alpha encourages exploration

Answer 42

Beta encourages exploitation