Research On Automatic Configuration Of Constraint Solving Algorithms

The performance of classical and meta-heuristic constraint solving algorithms in solving NP-hard problems usually depends on their parameter configuration.In fact,it has always been considered an important task to configure an appropriate parameter for an algorithm,which leaves a problem for every algorithm designer and user: how to configure the parameters correctly?In the past,people have been using manual method to configure parameters.Through the study of various algorithms,it is found that manual processing of parameters is actually a very complex problem.It needs to constantly change parameters in the process of operation and spend a lot of time to test the program to achieve the desired results.This is undoubtedly a very troublesome thing.It not only wastes manpower,material resources and financial resources,but also brings troubles to programmers' programming.Moreover,optimization by experiential method or trial-and-error method is not only time-consuming and labor-consuming,but also easy to make mistakes.Sometimes,it usually leads to uneven optimization of different algorithms.In addition,trial-and-error optimization relies too much on the experience of intuition and algorithm developers,and this method is difficult to correspond to strict mathematical proofs,so manual parameter allocation does not have generalization.In recent years,parameter optimization algorithm has gradually become an important part of the algorithm development process.Many high-performance algorithms have many parameters,and parameter configuration has an important influence on the behavior of the control algorithm,especially for the algorithm for solving difficult-to-optimize problems.Finding parameter configurations for heuristic algorithm performance optimization usually requires considerable overhead.In most cases,the parameter configuration is performed by cumbersome and complicated manual operations,and the quality of the configuration personnel is extremely high.Therefore,the research on the automatic parameter configuration has important practical significance.Moreover,automatic algorithm configuration has the following advantages: it can reduce development time and human intervention;it can providemore powerful technical support for algorithm design;it can exploit algorithm design space by using computing power;it can release human creativity for higher-level tasks;it can provide help for algorithm designers in designing programs.Configuring complex algorithm parameters is a highly labor-intensive task,which consumes a large part of the overall development time.The method of automatic algorithm configuration can save time significantly,and even get potentially better results.A central problem in comparing heuristic algorithms is how to make them better fundamentally.The reason for the success of heuristic algorithms is that the developers are more successful in optimizing their parameters.The automatic allocation method of the algorithm can alleviate the problem of unfair comparison and promote more meaningful comparative study.The ability of complex heuristic algorithms to solve difficult instances often depends on the configuration of appropriate parameters.Users often know little about the impact of parameter configuration on the performance of the algorithm,so they simply use the default configuration.Even if the algorithm has been carefully optimized by the standard benchmark group,the default configuration may not be the best configuration for the instance of a particular problem encountered,and the algorithm will not show the best performance.This paper first introduces the algorithm configuration,the definition of the algorithm configuration problem and related concepts,then introduces some methods to solve the algorithm configuration problem,mainly in two aspects of research.(1)The popular software irace,which has important influence on the automatic configuration parameters of algorithms,is deeply studied.Using Irace software to automatically configure parameters for acotsp program,through detailed analysis and comparison of the results of parameters under different configurations,we have a deeper understanding of the algorithm automatic configuration.(2)Based on the popular ParamILS algorithm configuration framework,an attempt is made to configure constrained solver-level algorithm automatically.The experimental results show that the automatic algorithm configuration at the constrained solver-level improves the efficiency of constrained solution obviously.Of course,constraints solving algorithm and automatic configuration of constraints solver are still at a relatively elementary level.In the future,we hope to further study constraints solving algorithm and provide a possibility to study efficient constraints solving algorithm from the perspective of automatic configuration of algorithm.