Multi-objective evolutionary computation for topology coverage assessment problem

摘要

In recent years, the smart city has gained large traction in government, academia, and business. Many real-world applications of smart cities can be formed to a topology graph and to optimally select a specified number of vertices to minimize the uncovered part of the topology graph. An example application is the optimal installation of a specified number of monitors at the crossroads of a city. Such a minimization problem is named a topology coverage optimization problem (TCOP) in this study, and it is a single-objective optimization problem (SOP). However, in actual situations, determining such a specific number a priori is usually difficu instead, multiple numbers would be provided to us by the decision-makers and the minimum objective value, as well as the optimal installation solution about each number, is solicited from us such a TCOP about multiple numbers is referred to as "topology coverage assessment problem (TCAP)". Hence, the TCAP consists of a series of SOPs (i.e., a series of TCOP5) each of which is NP-hard to optimize. This study introduces a multi-objective approach that is able to optimize all these TCOP5 simultaneously it is capable of obtaining high quality results about all given numbers at the same time. Besides the simultaneous problem-solving ability, our approach, namely MoCover, also statistically significantly improved the objective value about each provided number, particularly, the vertex cover number result, because of the mutual promoting relations between the TCOP5 and the exploitation of the relations during the optimization process. In this paper, the generalization of MoCover to a class of similar problems is also introduced and discussed. (C) 2019 Elsevier B.V. All rights reserved.