Solving Constraint Satisfaction Problems by Genetic Algorithms

在实际应用中，已有几种近似算法被用来求解大型约束满足问题。虽然这些论文讨论的技术，以摆脱局部最优，这项研究描述了一种方法，积极执行全局搜索。首先，我们提出了一种混合搜索方法，结合了遗传算法（GA）和最小冲突爬山（MCHC）。该方法以遗传算法种群中冲突最少的个体作为MCHC的初始值进行局部搜索。其次，提出了用病毒感染代替变异来提高遗传算法搜索效率的方法。CSP的部分解决方案，即领域特定的知识，被认为是病毒，并创建病毒的人口以及候选解决方案的人口。交叉和感染进行寻找解决方案。感染用病毒的基因取代了由病毒决定的基因座。实验结果表明，在约束密度较低的情况下，该方法比传统的遗传算法和随机迭代的MCHC算法具有更快的寻优速度。最后，提出了一种基于该方法的汽车导航系统路径规划算法。该方法可以在考虑驾驶员舒适度的情况下找到地图中两个路口之间的准最短路径。我们把从起点到终点的路径看作染色体，用交叉符号序列表示。我们也把宽的和/或直的路线看作病毒。通过与Diikstra算法的比较，实验结果表明，该方法能找到最容易行驶的路径。

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.