Ant Colony Optimization

    Ant Colony Optimization (ACO) studies artificial systems that take inspiration from the behavior of real ant colonies and which are used to solve discrete optimization problems. Recently (1999), the Ant Colony Optimization metaheuristic has been defined by Dorigo, Di Caro and Gambardella. The first ACO system was introduced by Marco Dorigo in his Ph.D. thesis (1992), and was called Ant System (AS). It was initially applied to the travelling salesman problem, and to the quadratic assignment problem. Since 1995 many researchers have been working on various extended versions of the AS paradigm.

ACO is a population-based algorithm where several artificial ants search for good solutions. Every ant builds up a solution step by step thereby going through several decision until a solution is found. Ants that found a good solution mark their paths through the decision space by putting some amount of pheromone on the edges of the path. The following ants of the next generation are attracted by the pheromone so that they will search in the solution space near good solutions.

 1 t = 0
 2 initialize pheromone trail, PT(t)
 3 initialize heuristic information, H
 4 while not end do
 5    t = t + 1
 6    generate solutions S(t) using PT(t-1) and H
 7    update PT(t) using S(t) and PT(t-1)

The Ant Colony Optimization skeleton (ACO) requires the classes:

• Problem
• Solution
• Heuristic
  

The class Problem corresponds to the definition of a problem instance. The skeleton filler must provide a complete definition of this class.

The class Solution corresponds to the definition of a solution (feasible or not) of a problem instance. The skeleton filler must provide a complete definition of the class Solution.

And finally, the class Heuristic corresponds to the additional information that the problem requires. This information is taken account of by the algorithm to decide the next step that an ants perform. The skeleton filler must provide a complete definition of this class.

In adition, the user must configure the following algorithm parameters (in file ACO.cfg):

• number of independent runs.
• number of generations.
• size of population (number of ants).
• Trial information: trail dimension, minimum and maximum trail values, local update, selection size, initial trial pheromone and q0 (exploration/explotation tradeoff).
• alpha (pheromone trail importance), beta (heuristic information importance).
• Inter operators (operators to apply between sub-populations) parameters: operator number, operator rate, number of individuals and selection of individual to send and replace.
• Parallel Configuracion: interval of generation to refresh global state, running mode (synchronized or asyncronized) and interval of generations to check solutions from other populations.

There are several basic steps to running a problem solve with ACO skeleton:

1. Change to the problem directory

cd Mallba/rep/ACO/problem

2. Compile skeleton.

make

3. Configure algorithm parameters (ACO.cfg file)
4. Run problem:
       4.1 Sequential Version:

make SEQ
     or
MainSeq ACO.cfg_path instance_path res_file_path

        4.2 Parallel Version:
                     4.2.1 Configure Config.cfg file.
                     4.2.2 Configure pgfileLan (or pgfileWan) : machines where we run the program.
                     4.2.3 Run

make LAN
     or
make WAN

[Up]