权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Solving Constraint Satisfaction Problems by Genetic Algorithms

用遗传算法解决约束满足问题

基本信息

批准号：
08680384
负责人：
KANOH Hitoshi
金额：
$ 1.09万
依托单位：
University of Tsukuba
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1996
资助国家：
日本
起止时间：
1996 至 1997
项目状态：
已结题

项目摘要

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.

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