BUS606: Operations and Supply Chain Management

The Ant Colony Optimization (ACO) algorithm is a heuristics using the idea of agents (here: ants) imitating their real behavior. Basing on specific information (distance, amount of pheromone on the paths, etc.) ants evaluate the quality of paths and choose between them with some random probability (the better path quality, the higher probability it represents). Having walked the whole path from the source to destination, ants learn from each other by leaving a layer of pheromone on the path. Its amount depends on the quality of solution chosen by agent: the better solution, the bigger amount of pheromone is being left. The pheromone is then "vapouring" to enable the change of path chosen by ants and let them ignore the worse (more distant from targets) paths, which they were walking earlier.

The result of such algorithm functioning is not only finding the solution. Very often it is the trace, which led us to this solution. It lets us analyze not only a single solution, but also permutations generating different solutions, but for our problems basing on the same division (i.e. tasks are scheduled in different order, although they are still allocated to the same processors). This kind of approach is used for solving the problems of synthesis, where not only the division of tasks is important, but also their sequence.

To adapt the ACO algorithm to scheduling problems, the following parameters have been defined:

• Number of agents (ants) in the colony;
• Vapouring factor of pheromone (from the range (0; 1));

The process of choosing these parameters is important and should consider that:

• For too big number of agents, the individual cycle of algorithm can last quite long, and the values saved in the table ("levels of pheromone") as a result of addition will determine relatively weak solutions.
• On the other hand, when the number of agents is too small, most of paths will not be covered and as a result, the best solution can long be uncovered.

The situation is similar for the vapouring factor:

• Too small value will cause that ants will quickly "forget" good solutions and as a result it can quickly come to so called stagnation (the algorithm will stop at one solution, which doesn't have to be the best one).
• Too big value of this factor will make ants don't stop analyze "weak" solutions; furthermore, the new solutions may not be pushed, if time, which has passed since the last solution found will be long enough (it is the values of pheromone saved in the table will be too big).

The ACO algorithm defines two more parameters, which let you balance between:

• α – the amount of pheromone on the path;
• β – "quality" of the next step;

These parameters are chosen for specific task. This way, for parameters:

• α > β there is bigger influence on the choice of path, which is more often exploited,
• α < β there is bigger influence on the choice of path, which offers better solution,
• α = β there is balanced dependency between quality of the path and degree of its exploitation,
• α = 0 there is a heuristics based only on the quality of passage between consecutive points (ignorance of the level of pheromone on the path),
• β = 0 there is a heuristics based only on the amount of pheromone (it is the factor of path attendance),
• α = β = 0 we'll get the algorithm making division evenly and independently of the amount of pheromone or the quality of solution.

Having given the set of neighborhood N of the given point i, amount of pheromone on the path τ and the quality of passage from point i to point j as an element of the table η you can present the probability of passage from point i to j as:

$p_{i j}^{k}= \begin{cases}\frac{\left[\tau_{i}\right]^{\alpha}\left[\eta_{i j}\right]^{\beta}}{\sum_{l \in N_{l}^{k}}\left[\tau_{i j}\right]^{\alpha}\left[\eta_{i j}\right]^{\beta}} & \text { When } j \in N_{i}^{k} \\ 0 & \text { Else }\end{cases}$

Formula 1.

Evaluation of the quality of the next step in the ACO algorithm

In the approach presented here, the ACO algorithm uses agents to find three pieces of information:

• the best / the most beneficial division of tasks between processors,
• the best sequence of tasks,
• searching for the best possible solution for the given distribution.

Agents (ants) are searching for the solutions which are the collection resulting from the first two targets (they give the unique solution as a result). After scheduling, agents fill in two tables:

• two-dimensional table representing allocation of task to the given processor,
• one-dimensional table representing the sequence of running the tasks.

The process of agent involves:

1. collecting information (from the tables of allocation) concerning allocation of tasks to resources and running the tasks;
2. drawing the next available task with the probability specified in the table of task running sequence;
3. drawing resources (processor) with the probability specified in the table of allocation the tasks to resources;
4. is it the last task?

To evaluate the quality of allocation the task to processor, the following method is being used:

1. evaluation of current (incomplete) scheduling;
2. allocation of task to the next of available resources;
3. evaluation of the sequence obtained;
4. release the task;
5. was it the last of available resources?

The calculative complexity of single agent is polynomial and depends on the number of tasks, resources and times of tasks beginning.

Idea of algorithm:

Algorithm:

1. Construct G – structure of tasks non allocation and S – structure of tasks, which may be allocation in next step (for ex ample: begin: G = {Z₁, Z₂,…, Z₇} and S = {Z₁, Z₂, Z₃}); update range of pheromone and consideration of vapouring factor;
2. With S select of tasks with the most strong of trace;
3. Allocate available of task as soon as possible and in accordance with precedence constraints;
4. Remove selected of task with G and S and to add to list of tasks in memory of ant;
5. Update range of pheromone and remain of trace;
6. If G = Ø END of algorithm;
7. Go to 1;

Example:

Two identical processors, digraph of seven tasks Z _i (t _i ), where t _i = time execution.

Parameters of ants' colony have been selected through experiments. Algorithm tuning is to select possibly best parameter values. This process demands many experiments which are conducted for different combinations of parameter values. For each combination of variable values, computation process has been repeated many times, and then an average result has been calculated. The same graphs type of STG, like at previous algorithms, have been applied.

Selected algorithm parameters:

• a – number of ants; for number of tasks n < 50, a = 75 and for n>= 50, a = 1,5 x n
• γ – the pheromone evaporation coefficient = 0,08.