Adaptive Ant Colony Optimization For Constraint Satisfaction Problems

Ant colony optimization is a kind of swarm intelligence optimization algorithms, which is according to ants foraging process. Ants mark the ideal foraging path by releasing chemical called pheromone and provide prior information to other members. Constraint satisfaction problems include a series of variables, the range and the corresponding constraint relationship between the variables. The solutions are one or more groups of values assigned to these variables which are satisfied with all the constraint relationships. Constraint satisfaction problems are NP-hard problems which designed to find a satisfactory solution in a limited time.First we introduce the basic principle of ant colony optimization solving constraint satisfaction problems, and elaborate the five pheromone update strategies of ant colony optimization. We use the binary constraint satisfaction problems to verify the performance of the ant colony optimization, and by comparing the five pheromone update strategies, we sum up the effect of these strategies when solving constraint satisfaction problems. Then, we use the adaptive pheromone update strategies to solve constraint satisfaction problems. Through the adaption algorithm, the pheromone update can make adjustment with different search criteria adaptively, so the ant colony optimization could meet the constraints better. Finally, we introduce seven heuristics variable orders of the constraint satisfaction problems. Ants iteratively choose values for the variables based on the heuristics variable orders during assignment, so the choice of variable orders also have an important influence on problem solving. Through the experiments, we compare the performance of each heuristic variable orders, and use the adaptive heuristic variable orders to solve constraint satisfaction problems.According to the experimental results, we analyze the different pheromone update strategies of ant colony algorithm solving the constraint satisfaction problems, and make adaptive pheromone update algorithm comparing with single pheromone update strategy. Through the parameter adjustment, convergence analysis, convergence time, success rate and cost, we prove that adaptive pheromone update strategy is superior in solving performance. Then, by comparing different heuristics variable orders, we summarize the pros and cons of each order, and illustrate the advantages of the adaptive heuristics variable...