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

The Ant Colony Optimization Algorithm (ACOA) is a new class of stochastic search algorithm proposed for the solution of combinatorial optimisation problems. Di erent 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 e ective 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 di erent 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..