Solving large knowledge base partitioning problems using an intelligent genetic algorithm
Shinn‐Ying Ho, Hung-Ming Chen, Li-Sun Shu · 1999
Developing large knowledge bases that are complex enough to be useful in real-world applications may result in large complicated systems that partitioning the system into smaller subsystems is an absolute requirement. The problem of allocation of production rules among several partitions of limited size such that the sum of inter-partition connections is minimized is termed as the knowledge base partitioning problem. In this paper, a novel intelligent genetic algorithm (IGA) is proposed to solve the large knowledge base partitioning problem which is a well-known NP-complete problem. IGA uses a new intelligent crossover based on the ability of orthogonal arrays that the chromosomes of the children are formed from the best combinations of the better genes representing variables of a function from the parents rather than the random combinations of parents' genes. It is shown empirically that the proposed general-purpose IGA needing no heuristic outperforms the existing methods, heuristic clustering, simple genetic algorithm, and heuristic evolutionary algorithm, available in the literature in solving knowledge base partitioning problems using the same benchmark, especially in solving very large partitioning problems.