A Study On The Searching Bias Of Ant Colony Optimization

Ant colony algorithm is a metaheuristic algorithm for solving complex problems. It was first proposed by the Italian scholar M. Dorigo, V.Maniezzo et al. in the early1990s, inspired by the path seeking patterns shown in the ants’foraging process. Since M. Dorigo first designed the ant system (Ant System, AS), many scholars have carried out continuous improvement on such algorithms, so far it has formed a mature framework. Since the ant colony algorithm has the advantages such as global optimization, effectiveness and robustness, its success is not only manifested in dealing with various combinatorial optimization problems, but also reflected by the excellent performance in dealing with a large number of problems. It has a wide range of applications in many areas, and achieved very high-quality results.Although performance of ACO has been in continuously improved, its major success has been shown mostly in the experimental level so far. Unlike other evolutionary algorithms, such as genetic algorithm, simulated annealing algorithm, which have a solid theoretical basis, theoretical study on ACO are still in its early stage. So far, theoretical study on ACO mainly concentrated in the convergence proof, deceptive problem, the time complexity estimation and so on. Although initially made some results in theoretical study on ACO, there are still some very important issues to be resolved. Ant colony algorithm has two types of search bias in the process of solving some problems:positive search bias and negative search bias. Such bias is caused by the nature of the algorithm used or the problem itself. We expect the situation tends to be the positive search bias. However, due to the negative search bias, ACO eventually can not converge to the global optimal solution in solving some problems. When we use the ant colony algorithm to solve some optimization problems, if we can not estimate and avoid such bias, we can not realize that our solution obtained may not be an optimal one. This is very harmful in many practical applicationsThis paper will conduct a comprehensive study on search bias of the ant colony algorithm, and propose an evaluation standard for search bias. We also propose an improved ant colony algorithm to avoid the search bias. Due to the negative effects produced by the search bias, we propose three improvement strategies to increase the diversity of the sulotions and make the improved algorithm effectively avoid the search bias. Finally, we will apply the improved ant colony algorithm in the problem of community detection. The main results and contributions of our research in this paper are as follows:(1) We summarize the types of the searching bias (representation bias, construction bias) in the ACO, and give a third type of bias in ACO which is called feedback bias. We give the definition of the feedback bias, and illustrate its existence and influence on the performance of ACO. We also propose a measurable evaluation criteria for these three biases and test the evaluation criteria. Our experiment results show that our evaluation standard is reasonable and effective.(2) To avoid the search bias produced by the ant colony algorithm, we propose a BA_ACO (Bias-Avoiding ACO) algorithm. We prove the convergence of traditional ant colony algorithm and BA_ACO algorithm respectively on different instances. The experimental results show that our BA_ACO algorithm can successfully avoid searching bias, and eventually converge to global optimal solution.(3) To rectify the nagtive influence of searching bias and increase the diversity of the sulotions, we propose three strategies for ants selecting. Taking the n-digital problem as example, our experimental results show that the proposed strategies can effectively increase the diversity of solutions and overcome the impact produced by the search bias.(4) We apply the improved ant colony algorithm on the problem of community detection. The algorithm is tested on synthetic and real world networks. The experimental results show that our algorithm can achieve higher quality results than other methods.