Solving Constraint Satisfaction Problems by Genetic Algorithms

点击翻译按钮获取中文摘要

Several approximate algorithms have been reported to solve large constraint satisfaction problems (CSPs) in a practical time. While these papers discuss techniques to escape from local optima, this study describes a method that actively performs global search. We, first, proposed a hybrid search method that combines a genetic algorithm (GA) with a min-conflicts hill-climbing (MCHC). In our method, the individual that has the fewest conflicts in the population of a GA is used as the intitial value of MCHC to search locally.Secondly, we proposed the method that is to improve the of search of a GA using viral infection instead of mutation. Partial solutions of a CSP,that is domain specific knowledge, are considered to be viruses, and a population of viruses is created as well as a population of candidate solutions. Crossover and infection conduct search for a solution. Infection substitutes the gene of a virus for the locus decided by the virus. Experimental results using randomly generated CSPs prove that the proposed method is faster than a usual GA and a randomly restating MCHC to find a solution when the constraint density of a CPS is low.Finally, we propose a path-planning algorithm for car navigation systems based on the present method. This method can find the quasi-shortest route between two crossings in a map while considering the amenity of drivers. We regard the routes from the start to the destination as chromosomes and express them by using sequences of crossin symbols. We also regard wide and/or straight routes as viruses. In a comparison with the Diikstra algorithm, experimental results prove that the present method can find the route that is easiest to drive.