### 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.cfgfile)

4. Run problem:

4.1 Sequential Version:make SEQ

or

MainSeq ACO.cfg_path instance_path res_file_path4.2 Parallel Version:

4.2.1 ConfigureConfig.cfgfile.

4.2.2 ConfigurepgfileLan(orpgfileWan) : machines where we run the program.

4.2.3 Runmake LAN

or

make WAN