Research On Correlation Heuristics Based On Pareto Optimality

Constraint programming originated from artificial intelligence,and combined with the research results of artificial intelligence,operations research,algorithm,graph theory.It is a software technology that used to describe and effectively solve the constraint satisfaction and constraint optimization problems.Constraint programming has become a hot topic of artificial intelligence research.It has high flexibility in the modeling of practical problems and diversity of solving methods,and is widely used in many fields.Variable ordering heuristic is a key technique of constraint programming to solve constraint satisfaction problem.Appropriate variable ordering heuristic can effectively prune the search tree in the search phase of constraint programming to reduce the search space and improve the efficiency of problem solving.In order to further improve the efficiency and ability of correlation heuristics to solve the problem,an improved correlation heuristic based on pareto optimality and the instantiation failure statistics was proposed.It adopts ParetoHeu,the Pareto optimal heuristic combination method,combined correlation heuristics with the classic general heuristic dom/wdeg.The search tree can be pruned as much as possible after the variables are instantiated by selecting the variables with the greatest possibility of backtracking through the double measures of variable range changing frequency in search and variable correlation constraint leading to backtracking times.At the same time,the use of dual measurement also prevents the problem from being solved for too long or even unable to be solved due to the inapplicability of the single heuristic,thus enhancing the universality of the heuristic.After combining heuristics,the weight statistics method based on the failure of instantiation is used to select variables with relatively higher possibility of searching conflicts after instantiation,so as to further improve the efficiency of problem solving.Experimental results show that the proposed method is more efficient than popular variable ordering heuristics in solving multiple problems.This thesis has 16 figures,10 tables and 94 references.