A knee-based multi-objective evolutionary algorithm: an extension to network system optimization design problem

摘要

High performance computing (HPC) research is confronted with multiple competing goals such as reducing makespan and reducing cost in clouds. These competing goals must be optimized simultaneously. Multi-objective optimization techniques to tackle such HPC problems have received significant research attention. Most multi-objective optimization approaches provide a large number of potential solutions. Choosing the best or most preferred solution becomes a problem. In some practical contexts, even if the decision maker does not have an explicit preference, there exist the regions of the solution space that can be viewed as implicitly preferred because of the way the problem has been formulated. Solutions located in these regions are called "knee solutions". Evolutionary approaches have become popular and effective in solving complex and large problems that require HPC. The aim of this paper is to develop a knee-based multi-objective evolutionary algorithm (MOEA) which can prune the set of optimal solutions with a controllable parameter to focus on knee regions. The proposed approach uses a concept called extended dominance to guide the solution process towards knee regions. A user-supplied density controller parameter determines the number of preferred solutions retained. We verify our approach using two and three-objective knee-based test problems. The results show that our approach is competitive with other well-known knee-based MOEAs when evaluated by a convergence metric. We then apply the approach to a network optimization design problem in order to demonstrate how it can be useful in a practical context related to HPC.