Application Intelligence Ant Algorithm To Solve The Traveling Salesman Problem

Traveling Salesman Problem (TSP) is one of most widely studied combinatorial problems. TSP is not only important in theoretical research but in applied science.Proven as a Non-polynomial-complete (NPC) problem, TSP is unlikely solved within polynomial calculations. Therefore, researches are divided into two main streams. Some scientists are working on ways of providing polynomial algorithms that guarantee performance. At the same time, many researchers are interested in finding efficient heuristics that can provide satisfying solution within short time.Ant System (AS) is a new, promising heuristics. AS came from studying of ants in reality. When ants search food, they deposit pheromone although their ways. By communicating through pheromone and reinforcing searching, ants can always find best way from home to food. Same as ants in reality, core of AS is the pheromone. Artificial ants communicate with each other, search new ways based on historical results, and give satisfying solutions to TSPs finally.Based on Ant Colony System (ACS), we introduce a new AGO, Intelligent Ant System (IAS). In IAS, pheromone is no longer useful. Ants communicate and search in a cheap way hence a lot of calculation is saved. Besides canceling pheromone, we introduce other improvements which make searching more effective.This paper is organized as followings,In the first chapter, we briefly introduce some concepts on combinatorial problems and TSPs.In the second one, AS is introduced and studied, both main achievements and shortcomings are mentioned.In the third part, two typical ACOs, namely ACS and MMAS, are described and studied.Then comes the highlight of the whole thesis. We introduce the new algorithm based on analysis of ACS. After that, a brief and whole procedure of IAS is described. At last, different ACOs are compared and conclusion is made upon the results.We provide a clearer view of the algorithm in chapter 5, which includes system analysis, design and implementation.In the last chapter, some possible directions of further study are given.Source code of the Demo is appended to help interested readers.