Abstract: Studying the attribute reduction in incomplete information systems, a GA-based algorithm is proposed to reduce assignment with the compatibility relation taken into account. The one-dimensional binary code is used to encode the algorithm because it is suitable to express genetic operators. Penalty function is introduced in the adaptive value function to speed up the convergence of the algorithm and ensure that the assignment reduction includes fewer attributes with stronger support. In addition, the single-point crossing is used as the rule with a given MaxGen iterative solution taken as termination criterion, thus providing a good searching result. An exemplifying analysis shows that the algorithm proposed is quick and effective in solving the problems of reducing knowledge.