基于遗传算法和Best-First图搜索的约减集求解算法

提出了两种新的约减算法，分别运用遗传算法和Ｂｅｓｔ－Ｆｉｒｓｔ搜索方法求约减集，前者利用了遗传算法的寻优特性从种群中获得一最优及一组次优个体，进而获得一组约减；后者采用Ｂｅｓｔ－Ｆｉｒｓｔ搜索方法，相对于Ａ算法可扩大搜索空间，并可从ｏｐｅｎ表前部获得一最优及一组次优的状态节点，进而获得一组约减。实验结果表明，文中提出的算法是有效且合理的。

Reducts Deriving Algorithms Based on Genetic Algorithm and Best-First Search Algorithm

Because some existing methods are based on A algorithm, they are easily to be trapped in local optima and can get only one solution. These drawbacks limit the application of rough set theory in the field of knowledge discovery and data mining. In order to conquer these problems the paper put forward two new algorithms, which are based on genetic algorithm and Best First Search algorithm respectively. The former utilizes the characteristics of genetic algorithm (GA) and gets a set of solutions from its population. The latter enlarges the search space and derives a set of solutions from the front of its open table. The experiment results prove the validity and efficiency of the two algorithms.