Multi-Level Ant System - a new approach through the new pheromone update for Ant Colony Optimization

摘要

Ant Colony Optimization (ACO) is a meta-heuristic approach inspired by the study of the behavior of real ant colonies when finding the shortest path from their nest to food source. ACO has been used for solving approximately NP-hard problems and its elite effects has been proved by the experiments. Currently, two famous ACO algorithms are Ant Colony System (ACS) and Max-Min Ant System (MMAS) proposed by M. Dorigo and T. Stutzle. In this paper, we introduce the idea about Multi-level Ant System (MLAS) and its application as an improved version of Max-Min Ant System through a novel pheromone updating scheme. We applied the new algorithm to the well-known combinatorial optimization problems such as Traveling Salesman Problem, in which we compared the results of the new algorithm with that of MMAS algorithms. Experimental results based on the standard test data showed that M LAS algorithm is more effective than MMAS in term of both the average and the best solution.