L8 - ACO Flashcards
Define ACO…
A population based metaheuristic that can be used to find approximate solutions for difficult combinatorial optimisation problems.
Define Heuristic…
A problem solving technique that uses a practical approach to find an optimal solution to a complex problem. Heuristics are are designed to quickly arrive at a ‘good enough’ solution.
Define Metaheuristic…
An algorithm that guides exploration and exploitation of search spaces in optimization and search problems
Define Stochastic…
A term used to describe randomness or the presence of chance or probability in a process. It’s the opposite to deterministic.
What are some of the properties that make ACO metaheuristic?
- Problem independent → Is a generic algorithm that can be applied in various scenarios.
- Exploitation and exploration balance.
- Iteratively converge to a more optimal solution.
How can we quickly determine whether we can utilise ACO to find an optimal solution?
Determine whether the problem can be thought of in terms of finding the best path in a weighted graph.
In brief, what are the 4 steps of the ACO algorithm?
- A set of artificial ants searching for a good solution ( path ) over the graph.
- The ants build a solution by applying a pheromone model to the graph as they traverse it. This process is stochastic and is biased by the pheromone model, with ants more likely to take routes of a higher pheromone value. Pheromone values are modified at run time.
- This iterates until a termination criteria is met.
- The optimal solution is chosen.
What is a Construction Graph?
A graph representation of the problem to be solved by ACO.
Edges of the Construction Graph have both a Pheromone and Heuristic value. Define each…
Pheromone Value : Cumulatively create the Pheromone model, which represents the global experience of the ant colony. This is updated during run time.
Heuristic Value : Problem dependent values.
Explain the process of how ACO works on the TSP…
- The process goes:
- Each ant starts at a random vertex, and adds this vertex to their visited vertices.
- Ants take a construction step by travelling to a vertex that they have not visited before.
- Each construction step is chosen probabilistically, which is biased by pheromone and heuristic values of the candidate edges.
- Higher pheromone and heuristic value → Higher probability the ant will take that edge.
- Once each ant has completed their tour, the pheromone values of each edge are updated. Initially, each edge experiences a set reduction ( evaporation ). Then, pheromones are added to each edge based on the quality of solutions that traversed the edge. For example, the edges of the highest quality solution will receive the most pheromones, and the edges of the lowest solution will receive he lowest number of pheromones.
- This repeats until a termination criteria is met.
What is the correlation of a solution path and the pheromone levels?
The higher the quality of the solution path ( shortest ), the higher the pheromone level. They are directly proportional.
What are the 3 key processes that the ACO performs during execution?
Generate Solutions
Daemon Actions
Pheromone Update
Define the Generate Solutions process…
A process within the ACO metaheuristic…
- The phase where ants traverse the graph to construct solutions.
- Construction is defined by the Transition Rule.
What is the Transition Rule? How does it work?
The rules followed at each vertex that determines the ants next step in a probabilistic way.
The probability of taking a certain next path depends on the pheromone and heuristic values of the next edges.
What are the variables of the Transition Rule?
Tao i,j = Pheromone level of next edge.
n i,j = Heuristic value of next edge.
alpha = Global information, exponent of tao.
Beta = Local information, exponent of the Heuristic Value n.
