Research On Improving Strategies And Algorithms Of Ant Colony Optimization

The ant individual has little intelligence, but the entire ant colony is able tocomplete the complex task much far beyond the individual’s ability and achieveincredible intelligence level. According to observations of ants’ social behaviors, the antcolony utilizes a mechanism named stimergy to coordinate the actions of the colonyand enable the colony always to find the shortest path between nest and food source.The foraging behavior of real ants is exactly the inspiring source of Ant ColonyOptimization (ACO) algorithm. In early1990s, the first ACO algorithm-Ant Systemwas emerged in Polytechnic University of Milan. And after that, ACO graduallybecome a vital metaheuristic and its application has spread all over into many felidslike academia, industry, business and so on.As a newly-rising bionic algorithm, Ant System has drawn a multitude of expertsand scholars’ attention and has developed into various improved versions. The concreteimprovements used by these improved ACO algorithms differ from version to version,but they share similar ideas and strategies. This article summarized three widespreadimproving strategies-improvement on the construction of solutions, improvement onthe update of pheromone trails and improvement on the treatment of solutions.Moreover, taking four most well-known ACO algorithms (Ant System with elitiststrategy, Rank-Based Version of Ant System, Ant Colony System and Max-Min AntSystem) as the example, the three strategies are discussed. Additionally, on the basis ofplentiful experiments, this article analyzed the performance and usage of the threestrategies and proved the effectiveness of them. The three strategies can facilitate thestudy and comprehension of ACO algorithms, be adopted to improve the knownalgorithms and guide the design of new ACO algorithms.Generally, the existing ACO algorithms employ the selection bias to perform abiased selection and search at certain probability in the search space. Thus, the positivefeedback can be implemented and accordingly the optimization ability can beguaranteed. However, the use of selection bias is accompanied by local optimum andpremature convergence. In order to conquer the drawbacks, on the basis of thesummarized improving strategies, this article proposes a new ACO algorithm namedModerate Ant System (MAS). In MAS, the traditional artificial ants are divided intotwo sorts: utilization-oriented artificial ants and exploration-oriented artificial ants. The utilization-oriented artificial ants focus on the utilization of learned knowledge, toconstruct the solutions and gradually improve the quality of the solutions. In contrast,exploration-oriented artificial ants concentrate on the exploration of new knowledge inthe search space. Inspired by the adaptive behaviors of some real-world Monomoriumant species, a completely new transition rule is designed for the exploration-orientedartificial ants to make them tend to choose edges with moderate pheromone trails. Inaddition, a new corresponding update rule is also employed to match the searchbehaviors of two sorts of artificial ants. According to the experimental results, MAS isturned out to be able to weaken the adverse impact thereby better exploring the searchspace of the problem. In other words, MAS can overcome the local optimum andpremature convergence to some extent and manifests excellent performance.