A novel approach for crossover based on attribute reduction - a case of 0/1 knapsack problem

This paper proposes a methodology that incorporates the process of attribute reduction in rough sets into crossover in genetic algorithms (GAs). We develop two algorithms on the basis of the methodology. The first one selects the crossover points either by attribute reduction or randomly; the second one selects the points only by attribute reduction and no crossover otherwise. We study 0/1 knapsack problem due to its NP-hard complexity and solution nature of binary form, and conduct experiments against typical GAs. According to the preliminary results, the incorporation of attribute reduction appears to generate larger means of final solutions and smaller standard deviations of final solutions, especially in the presence of tighter capacity. That is, better solution quality and more clustered solutions are obtained.