The Research On The Constraint Solving Algorithms Based On Ant Colony Optimization

Constraint Satisfaction Problems, or CSPs is an important problem of the field of artificialintelligence research, is currently a hot research problem. CSPs are widely used, especially inour daily lives, such as scheduling, resource allocation, pattern recognition and machinevision. The study of CSPs has a long history. In fact, as early as a hundred years before thebirth of the computer, it was suggested that the classic8-queens problem, opened the preludeof CSPs research. Along with the development of computer technology, CSPs graduallytransfer from pure research to real-world applications, and to play an active role in addressingmany important issues. The modern framework of CSPs originated Ivan Sutherland’s doctoralthesis in1963,“Sketchpad: A man-machine graphical communication system.”The two major areas of CSPs research are the representation and reasoning. Constraintnetwork is an important representation of CSPs that can unify various CSPs instances as aformal representation of the mathematical paradigm. This representation has two advantages:First, the simple specification, the researchers do not need to understand the specific problems,they can simply know the information about the problems on reading the constraint network,that will make the researchers concentrate their energy on the problem solving, unifiedplatform also easy for people to communicate with each other; Second, easy to implement,developers can easily implement the constraint network data structure with a computer thatbrings great convenience for experiments and practical applications. The CSPs reasoning ismainly divided into two categories: inference and search. The core technology of theinference is constraint propagation, of which the aim is to simplify the problem; core searchtechnology is backtracking, which could theoretically completeness solving all CSPsinstances.This article examines the application of CSPs in the Combinatorial OptimizationProblems, or COPs. COPs are more closely linked with our daily lives, such as Job-shopscheduling. In fact, all the limited resource allocation problems are combinatorialoptimization problems. For example, it is that resource shortage and environmentaldegradation which become more and more prominent in the last few years, in essence, the contradiction between earth’s limited resources and human’s endless demand. The vastmajority of COPs can use constraint network explicitly expressed, largely solving CSPs andsolving COPs can be common.Backtracking method is inefficient when CSPs instance is complex and large scale, manyimprovements have been proposed. The main direction is to improve the efficiency ofconstraint propagation and the intelligence of backtracking search, which well-behaved onsome problems. Unfortunately, there is not a way which is able to show a good performanceon all CSPs instances. In this paper, we try to use ant colony optimization algorithm to solveCSPs.Ant Colony Optimization, or ACO proposed by Dorigo in1994, was originally used tosolve COPs. Its superior performance to attract people to applied it to solve CSPs. The mainfeature of ACO, which has achieved good results in many problems, is versatility. However,there is a gap between the efficiency of ACO and a dedicated algorithm for a particularproblem. The purpose of this study is to improve the efficiency of ACO for solving CSPs,design and implementation the efficient and universal CSPs solver based on the ACO.Arc Consistency, or AC algorithm is an important constraint propagation method that caneffectively remove redundant parts of the search space, and simplify complex CSPs instancewith small cost.Parameter adjustment is a very important part of the ACO, which has a significantimpact on the performance and robustness of the ACO. In this paper, we detailed analysis themechanism of the ACO parameter adjustment, and propose a more practical parameteradjustment scheme called pre-arranged parameters adjustment.This paper first introduces the basic concepts and methods of ACO and CSPs, andanalyses Ant-Solver, which is a solver based on the ACO for solving CSPs; On this basis, wecombine AC pretreatment and pre-arranged parameter adjustment with Ant-Solver, proposeimproved algorithm AC-AS; Finally, we use the AC-AS to solve COPs with CSPs instancesrepresentation, by which we prove that the AC-AS performed well on most problems. AC-ASlargely overcome the major defects of ACO-premature convergence, however, the algorithmwill still fall into a local optimum trap in rare cases. We believe that the AC-AS still has muchroom for improvement with develop other methods and improve existing methods (forexample, design an adaptive parameter adjustment method), that will further improve theperformance of the algorithm, and finally solve the problem of premature convergence.In short, AC-AS could play a positive role in solving of unknown type CSPs instancesand the CSPs instances for which dedicated solver does not work, meet robustness and user-friendly, show broad prospects in efficient universal solver design.