An Ant Colony Algorithm Based On Arbitrary Edge Insertion

Ant colony algorithm is a heuristic search algorithm proposed by the Italian scholarDorigo M in the1990s[1]. When in the process of looking for food, natural ants can alwaysfind the shortest path between the nest and food. Ant colony algorithm has been applied inmany typical combinatorial optimization problems by many scholars, such as networkcommunication problems, postman problems and traffic scheduling problems. It has excellentsolving skills. Ant colony algorithm attracted the attention of many scholars and encouragethem to join the research team of the ant colony algorithm. So far, the theory and practicework has achieved fruitful results.As a new heuristic search algorithm, ant colony algorithm has several distinctadvantages: strong robustness, positive feedback, distributed computing and easy to combinewith other algorithms. But the basic ant colony algorithm also has some limitations, such aseasy to fall into local optimal solution, need a long calculation time and so onTimo Kotzingproposed an improved method differs from the orderly edge selection: the arbitrary edgeinsertion method. By comparing to the orderly edge selection, its performance has beenanalyzed theoretically. According to theoretical analysis, the ant colony algorithm based onarbitrary edge selection will shorten the iteration to find the optimal solution, and has higherquality to solve problems. This novel ant colony algorithm is still in the theoretical analysisphase.Based on the theoretical analysis of Timo Kotzing and other scholars, this paperillustrate the basic principles of ant colony algorithm based on arbitrary edge selection[2]. Themain point of the Arb algorithm is, when the artificial ant choose the next path, the candidateset consists of all the edge, instead of the node next to the current node. The process of theedge insertion can be abstracted as there is an ant which can jump from one edge to another,in the search space, leading to the formation of a path from nest to food.Design experiments, run the Arb and Ord algorithm on the traveling salesman problem.Traveling salesman problem is a typical combinatorial optimization problems, manycombinatorial optimization problems can be transformed to the traveling salesman problem.Many of bionic algorithm is firstly run on the traveling salesman problem. Through theanalysis and comparison of experimental data, this paper verify the effectiveness of Arbalgorithm and outstanding solution finding ability.Based on this, this paper study the parallel ability of Arb algorithm. The parallel versionof Arb algorithm can shorten the running time of the Arb algorithm. Design experiment, implement the parallel Arb algorithm and run it on the TSP problem. Analysis theexperimental data, validate the effectiveness of the parallel Arb algorithm.