Based On Ant Colony Algorithm Of Constraint Solving

Constraint satisfaction problem is a very important branch of artificial intelligence,which in reality a lot of problems can be abstracted as constraint algorithm to solve the problem, commonly used constraints to production scheduling and resource allocation algorithm to solve the practical problems in the scale of the problem may be very big, also can is a np-hard problem, if use the traditional methods can be difficult to obtain satisfactory solution in a reasonable amount of time, and constraint solving algorithm with high efficiency in dealing with this kind of problem, constraint algorithm is commonly used in backtracking algorithm such as MAC algorithm, will be embedded in the backtracking algorithm of arc algorithm, compatible arc is used to delete some incompatible values, to compress the solution space, thus improve the solution efficiency.Through the bionics research, it was found that the individual behavior of simple ants can be done in the absence of group command complex task, through further study found that ants from the release of information to create complete cooperation and communication. In the process of inspired by the Italian scholar m. own, V.M aniezzo put forward the ant colony algorithm, the ant colony foraging process and TSP problems are similar, so the ant colony algorithm is usually used to solve TSP problem. Ant colony algorithm is also be used in production scheduling, combinatorial optimization, data mining and other fields.When to solve constraint satisfaction problem constraint solving technology has a good efficiency, but in the actual problem, the problem on a big scale, high to the requirement of time, because of time constraint solving technology is a complete algorithm will cost more, but if you use ant colony algorithm to solve constraint satisfaction problem,efficiency will be higher. Based on the common constraint solving algorithm and the basis of the basic ant colony algorithm, using ant colony algorithm to solve constraint satisfaction problem was studied in this paper.(1) is discussed in this paper, the commonly used MAC algorithm framework, and embedded in some of the MAC algorithm compatible arc algorithm, such as AC3, AC4, AC2001 algorithm, analysis how to explain the MAC algorithm back and how to choose the branching strategy, AC3, AC4, AC2001 number inspection method and inspection algorithm about each with data structure. This paper introduces the principle of ant colony algorithm and the basic ant colony algorithm to solve TSP problem.(2) will apply to constraint solving benchmark data model into corresponding TSP problem, the variable values of each variable mapping into a city in the TSP problem, ants crawling in time will not go over each city, will only go a value of eachvariable.(3) the ants on the next node selection probability formula to follow when it will be different, this article put forward the two formulas, formula one ant pheromone concentration, formula 2 there will be a pheromone concentration factors, but also there will be a basic ant colony algorithm probability formula of the distance to the local factors,the local factors is to select the node with the ant has come to increase conflict between the node number.(4) by compared with algorithm based on the MAC- AC3, illustrates the effectiveness of the algorithm.