Elitist-Mutated Ant System Versus Max-Min Ant System: Application to Pipe Network Optimization Problems

Abstract. The Ant Colony Optimization Algorithm (ACOA) is a new class of stochastic search
algorithm proposed for the solution of combinatorial optimisation problems. Dierent versions of ACOA
are developed and used with varying degrees of success. The Max-Min Ant System (MMAS) is recently
proposed as a remedy for the premature convergence problem often encountered with ACOAs using elitist
strategies. The basic concept behind MMAS is to provide a logical balance between exploitation and
exploration. The method, however, introduces some additional parameters to the original algorithm,
which should be tuned for the best performance of the method adding to the computational requirement
of the algorithm. An alternative method to MMAS is proposed in this paper and applied to pipe network
optimization problem. The method uses a simple but eective mechanism, namely Pheromone Trail
Replacement (PTR), to make sure that the global best solution path has always the maximum trail
intensity. This mechanism introduces enough exploitation into the method and more importantly enables
one to exactly predict the number of global best solutions at each iteration of the algorithm without requiring
calculation of the cost of the solutions created. The sub-colony of repeated global best solutions of the
iterations is then mutated, such that a predened number of solutions survive the mutation process. Two
dierent mutation mechanisms, namely deterministic and stochastic mutation processes, are introduced
and used. The rst one uses a one bit mutation with a probability of one on some members of the
sub-colony, while the second one uses a uniform mutation on the whole sub-colony. The probability of
mutation in the second mutation process is adjusted at each iteration, so that the required number of globalbest
solutions survives the mutation. The method is shown to produce results comparable to the MMAS
algorithm, while requiring less free parameter tuning. The application of the method to a benchmark
example in the pipe network optimization discipline is presented and the results are compared.