Solving multi-scenario cardinality constrained optimization problems via multi-objective evolutionary algorithms

作     者：Xing ZHOU Huaimin WANG Wei PENG Bo DING Rui WANG 

作者机构：College of Computer National University of Defense Technology College of Systems Engineering National University of Defense Technology 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2019年第62卷第9期

页      面：73-90页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 081104[工学-模式识别与智能系统] 08[工学] 070105[理学-运筹学与控制论] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：supported by National Natural Science Foundation of China (Grant Nos. 61751208, 61502510, 61773390) Outstanding Natural Science Foundation of Hunan Province (Grant No. 2017JJ1001) Special Program for the Applied Basic Research of National University of Defense Technology (Grant No. ZDYYJCYJ20140601) 

主　　题：evolutionary computation multi-objective optimization cardinality-constrained optimization problem multiple scenarios transformation p-median problem portfolio optimization problem 

摘      要：Cardinality constrained optimization problems(CCOPs) are fixed-size subset selection problems with applications in several fields. CCOPs comprising multiple scenarios, such as cardinality values that form an interval, can be defined as multi-scenario CCOPs(MSCCOPs). An MSCCOP is expected to optimize the objective value of each cardinality to support decision-making processes. When the computation is conducted using traditional optimization algorithms, an MSCCOP often requires several passes(algorithmic runs) to obtain all the(near-)optima, where each pass handles a specific cardinality. Such separate passes abandon most of the knowledge(including the potential superior solution structures) learned in one pass that can also be used to improve the results of other passes. By considering this situation, we propose a generic transformation strategy that can be referred to as the Mucard strategy, which converts an MSCCOP into a low-dimensional multi-objective optimization problem(MOP) to simultaneously obtain all the(near-)optima of the MSCCOP in a single algorithmic run. In essence, the Mucard strategy combines separate passes that deal with distinct variable spaces into a single pass, enabling knowledge reuse and knowledge interchange of each cardinality among genetic individuals. The performance of the Mucard strategy was demonstrated using two typical MSCCOPs. For a given number of evolved individuals, the Mucard strategy improved the accuracy of the obtained solutions because of the in-process knowledge than that obtained by untransformed evolutionary algorithms, while reducing the average runtime. Furthermore, the equivalence between the optimal solutions of the transformed MOP and the untransformed MSCCOP can be theoretically proved.