Ring Theory-Based Evolutionary Algorithm and its application to D{0-1} KP

In this paper, we propose a new view for designing an evolutionary algorithm by using algebraic theory to solve the combinatorial optimization problem. Using the addition, multiplication and inverse operation of the direct product of rings, we first propose two evolution operators: the global exploration operator (R-GEO) and the local development operator (R-LDO). Then, by utilizing the R-GEO and R-LDO to generate individuals and applying the greedy selection strategy to generate a new population, we propose a new algorithm – the Ring Theory-Based Evolutionary Algorithm (RTEA) – for the combinatorial optimization problem. Moreover, we give a new method for solving the discounted {0-1} knapsack problem (D{0–} KP) by using the RTEA. To verify the performance of the RTEA, we use it and existing algorithms to solve four kinds of large-scale instances of the D{0-1} KP. The computational results show that the RTEA performs better than the others, and it is more suitable for solving the D{0-1} KP problem. Moreover, it indicates that using algebraic theory to design evolutionary algorithms is feasible and effective.