Phenotypic genetic algorithm for partitioning problem

摘要

The paper presents a phenotype based genetic algorithm for solving a partitioning problem, which is partitioning N objects into P groups to optimize an objective function. In the genetic algorithm, a phenotypic individual is represented by a way of division of a suffix set {1,...,N} into P subsets. In order to prevent premature convergence, the paper defines a distance between phenotypic individuals and uses it in the adaptive control of crossover rate. Furthermore, the paper proposes a new crossover operation named weighted edge crossover which preserves both the structure of phenotype and the desirable character of parents. These techniques perform well on a test problem: multiprocessor scheduling problem for robot control computation.