Research On Parallel Ant Colony Algorithm

Ant colony optimization (ACO) is a popular intelligent algorithm in recent years, it shows a good performance in solving large-scale combinatorial optimization problem and demonstrates its redevelopment possibility. But existed ant colony algorithm has some inherent shortages which may undermine its performance. Thus, improving the performance of ACO, is a significant task in terms of application and theory work. For that purpose, We introduce the basic idea and the model of ACO while presenting the weakness of ACO: time-cosuming and the low convergence rate. Meanwhile, parallel ant colony algorithm (PAC) is introduced, which has the weakness of searching the fixed model repeatedly. In Contrast to those characteristics, we propose parallel ant colony algorithm based on model-learning (MPAC). We set the standard to learn the fixed model and deliver it to others for reducing the computation complexity. Through simulation on dataset such as berlin52, kroA100, kroE100, bier127,ch150, kroE150 at MATLAB environment, the result shows the accuracy in MPAC is close to the accuracy in PAC, smaller than ACO, we demonstrate the numbers of iterations of MPAC is smaller than the ones of PAC and ACO by recording a good model which speeds up the convergence. On the other hand, the search time decreases by reducing the computation complexity in model-learning. Thus, MPAC is better than PAC and ACO.ACO has the disadvantage of the low convergence rate due to the ergodicity probability in selecting the path. To solve this, we propose chaos and parallel ant colony algorithm based on model-learning (CMPAC). We conduct the chaotic initialization based on its ergodicity. Each of chaos parameter correspond a path, we select the better path, and give the extra pheromone. The pheromone of each path is different, which leads to selecting the path and speeds up the convergence. After the chaotic initialization, the algorithm usually sinks into local optimum. We draw into chaotic perturbation when updating the pheromone, which jumps out of the local optimum. The code that solves berlin52, kroA100, kroE100, bier127, ch150, kroE150 in CMPAC is written, which reflect that CMPAC get the better optimal solution and improves the accuracy in berlin52, kroA100, kroE100, ch150, kroE150 compared with PAC and MPAC, which demonstrates chaotic interference has a positive effect on most problems through the ability of jumping out of the local optimal. The results in berlin52?kroA100?kroE100?bier127?kroE150 also show that CMPAC gets the highest convergence rate because the better path is given extra pheromone after chaos initialization. Thus, CMPAC is better than PAC and MPAC.