Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 714-722 |
| Number of pages | 9 |
| Journal | Applied Soft Computing |
| Volume | 77 |
| Early online date | 12 Feb 2019 |
| DOIs | |
| Publication status | Published - Apr 2019 |
| Externally published | Yes |
Bibliographical note
This article was supported by the Basic Research Project of Knowledge Innovation Program in Shenzhen, China (JCYJ2015032 4140036825), China Postdoctoral Science Foundation (2015M572361), the National Natural Science Foundations of China (61503252, 71371063 and 11471097), the Scientific Research Project Program of Colleges and Universities in Hebei Province, China (ZD2016005), and Natural Science Foundation of Hebei Province, China (F2016403055).Keywords
- Direct product of rings
- Discounted {0-1} knapsack problem
- Evolutionary algorithms
- Residue class ring module m