logo

SCIENCE CHINA Information Sciences, Volume 62 , Issue 9 : 192104(2019) https://doi.org/10.1007/s11432-018-9720-6

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

More info
  • ReceivedJul 29, 2018
  • AcceptedNov 24, 2018
  • PublishedJul 30, 2019

Abstract

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.


References

[1] Stephan R. Cardinality constrained combinatorial optimization: Complexity and polyhedra. Discrete Optimization, 2010, 7: 99-113 CrossRef Google Scholar

[2] Karp R M. Reducibility among combinatorial problems. In: Proceedings of Complexity of Computer Computations, 1972. 85--103. Google Scholar

[3] Banfield R E, Hall L O, Bowyer K W. Ensemble diversity measures and their application to thinning. Inf Fusion, 2005, 6: 49-62 CrossRef Google Scholar

[4] Moghaddam B, Weiss Y, Avidan S. Spectral bounds for sparse pca: exact and greedy algorithms. In: Proceedings of Advances in Neural Information Processing Systems, 2005. 915--922. Google Scholar

[5] Bruckstein A M, Donoho D L, Elad M. From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images. SIAM Rev, 2009, 51: 34-81 CrossRef Google Scholar

[6] Zhou X, Huaimin W, Bo D. How many robots are enough: a multi-objective genetic algorithm for the single-objective time-limited complete coverage problem. In: Proceedings of IEEE International Conference on Robotics and Automation, 2018. 2380--2387. Google Scholar

[7] Chai R, Li H, Meng F. Energy consumption optimization-based joint route selection and flow allocation algorithm for software-defined networking. Sci China Inf Sci, 2017, 60: 040306 CrossRef Google Scholar

[8] Deb K, Pratap A, Agarwal S. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Computat, 2002, 6: 182-197 CrossRef Google Scholar

[9] Wang R, Purshouse R C, Fleming P J. Preference-Inspired Coevolutionary Algorithms for Many-Objective Optimization. IEEE Trans Evol Computat, 2013, 17: 474-494 CrossRef Google Scholar

[10] Wang R, Zhou Z, Ishibuchi H. Localized Weighted Sum Method for Many-Objective Optimization. IEEE Trans Evol Computat, 2018, 22: 3-18 CrossRef Google Scholar

[11] Yong Wang , Han-Xiong Li , Yen G G. MOMMOP: multiobjective optimization for locating multiple optimal solutions of multimodal optimization problems.. IEEE Trans Cybern, 2015, 45: 830-843 CrossRef PubMed Google Scholar

[12] Gupta A, Ong Y S, Feng L. Multifactorial Evolution: Toward Evolutionary Multitasking. IEEE Trans Evol Computat, 2016, 20: 343-357 CrossRef Google Scholar

[13] Gupta A, Ong Y S, Feng L. Multiobjective Multifactorial Optimization in Evolutionary Multitasking.. IEEE Trans Cybern, 2017, 47: 1652-1665 CrossRef PubMed Google Scholar

[14] Knowles J D, Watson R A, Corne D W. Reducing local optima in single-objective problems by multi-objectivization. In: Proceedings of International Conference on Evolutionary Multi-Criterion Optimization, 2001. 269--283. Google Scholar

[15] Wu Song , Yong Wang , Han-Xiong Li . Locating Multiple Optimal Solutions of Nonlinear Equation Systems Based on Multiobjective Optimization. IEEE Trans Evol Computat, 2015, 19: 414-431 CrossRef Google Scholar

[16] Bienstock D. Computational study of a family of mixed-integer quadratic programming problems. Math Program, 1996, 74: 121--140. Google Scholar

[17] Burdakov O, Kanzow C, Schwartz A. On a reformulation of mathematical programs with cardinality constraints. In: Proceedings of Advances in Global Optimization, 2015. 3--14. Google Scholar

[18] Sun X, Zheng X, Li D. Recent Advances in Mathematical Programming with Semi-continuous Variables and Cardinality Constraint. J Oper Res Soc China, 2013, 1: 55-77 CrossRef Google Scholar

[19] Rifki O, Ono H. A survey of computational approaches to portfolio optimization by genetic algorithms. In: Proceedings of the 18th International Conference Computing in Economics and Finance, 2012. Google Scholar

[20] Ruiz-Torrubiano R, Garc'ıa-Moratilla S, Suárez A. Optimization problems with cardinality constraints. In: Proceedings of Computational Intelligence in Optimization, 2010. 105--130. Google Scholar

[21] Chang T J, Meade N, Beasley J E. Heuristics for cardinality constrained portfolio optimisation. Comput Operations Res, 2000, 27: 1271-1302 CrossRef Google Scholar

[22] Volgenant A. Solving the k-cardinality assignment problem by transformation. Eur J Operational Res, 2004, 157: 322-331 CrossRef Google Scholar

[23] Radcliffe N J, George F A. A study in set recombination. In: Proceedings of the 5th International Conference on Genetic Algorithms, 1993. 23--30. Google Scholar

[24] Kariv O, Hakimi S L. An algorithmic approach to network location problems. SIAM J Appl Math, 1979, 37: 539-560 CrossRef Google Scholar

[25] Reese J. Solution methods for the p-median problem: An annotated bibliography. Networks, 2006, 48: 125-142 CrossRef Google Scholar

[26] Mladenovi? N, Brimberg J, Hansen P. The p-median problem: A survey of metaheuristic approaches. Eur J Operational Res, 2007, 179: 927-939 CrossRef Google Scholar

[27] ReVelle C S, Eiselt H A, Daskin M S. A bibliography for some fundamental problem categories in discrete location science. Eur J Operational Res, 2008, 184: 817-848 CrossRef Google Scholar

[28] Hosage C M, Goodchild M F. Discrete space location-allocation solutions from genetic algorithms. Ann Oper Res, 1986, 6: 35-46 CrossRef Google Scholar

[29] Alp O, Erkut E, Drezner Z. An efficient genetic algorithm for the p-median problem. Ann Operations Res, 2003, 122: 21-42 CrossRef Google Scholar

[30] Li X, Xiao N, Claramunt C. Initialization strategies to enhancing the performance of genetic algorithms for the p-median problem. Comput Industrial Eng, 2011, 61: 1024-1034 CrossRef Google Scholar

[31] Lim A, Xu Z. A fixed-length subset genetic algorithm for the p-median problem. In: Proceedings of Genetic and Evolutionary Computation Conference, 2003. 1596--1597. Google Scholar

[32] Correa E S, Steiner M T A, Freitas A A. A Genetic Algorithm for Solving a Capacitated p-Median Problem. Numer Algorithms, 2004, 35: 373-388 CrossRef ADS Google Scholar

[33] Alba E, Domínguez E. Comparative analysis of modern optimization tools for the p-median problem. Stat Comput, 2006, 16: 251-260 CrossRef Google Scholar

[34] Hansen P, Mladenovi? N. Complement to a comparative analysis of heuristics for the p-median problem. Stat Comput, 2008, 18: 41-46 CrossRef Google Scholar

[35] Daskin M S, Maass K L. The p-median problem. In: Location Science. Berlin: Springer, 2015. 21--45. Google Scholar

[36] Daskin M S. Network and Discrete Location: Models, Algorithms, and Applications. Hoboken: John Wiley & Sons, 2013. Google Scholar

[37] Galv?o R D, ReVelle C. A Lagrangean heuristic for the maximal covering location problem. Eur J Operational Res, 1996, 88: 114-123 CrossRef Google Scholar

[38] K?rkel M. On the exact solution of large-scale simple plant location problems. Eur J Operational Res, 1989, 39: 157-173 CrossRef Google Scholar

[39] Cesarone F, Scozzari A, Tardella F. Efficient algorithms for mean-variance portfolio optimization with hard real-world constraints. In: Proceedings of the 18th AFIR Colloquium: Financial Risk in a Changing World, 2008. Google Scholar

[40] Ponsich A, Jaimes A L, Coello C A C. A Survey on Multiobjective Evolutionary Algorithms for the Solution of the Portfolio Optimization Problem and Other Finance and Economics Applications. IEEE Trans Evol Computat, 2013, 17: 321-344 CrossRef Google Scholar

[41] Metaxiotis K, Liagkouras K. Multiobjective Evolutionary Algorithms for Portfolio Management: A comprehensive literature review. Expert Syst Appl, 2012, 39: 11685-11698 CrossRef Google Scholar

[42] Markowitz H. Portfolio selection. J Financ, 1952, 7: 77--91. Google Scholar

[43] Fieldsend J E, Matatko J, Peng M. Cardinality constrained portfolio optimisation. In: Proceedings of International Conference on Intelligent Data Engineering and Automated Learning, 2004. 788--793. Google Scholar

[44] Anagnostopoulos K P, Mamanis G. A portfolio optimization model with three objectives and discrete variables. Comput Operations Res, 2010, 37: 1285-1297 CrossRef Google Scholar

[45] Ruiz-Torrubiano R, Suarez A. Hybrid Approaches and Dimensionality Reduction for Portfolio Selection with Cardinality Constraints. IEEE Comput Intell Mag, 2010, 5: 92-107 CrossRef Google Scholar

[46] Cesarone F, Scozzari A, Tardella F. A new method for mean-variance portfolio optimization with cardinality constraints. Ann Oper Res, 2013, 205: 213-234 CrossRef Google Scholar

[47] Zitzler E, Thiele L, Laumanns M. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans Evol Computat, 2003, 7: 117-132 CrossRef Google Scholar

  • Figure A1

    (Color online) Solution procedures of conventional EAs and Mucard. The red circles are the real optima; the other circles are the objective values of the EA individuals. (a1) Initialization and evolution direction of conventional EAs; (a2) final result of conventional EAs; (b1) initialization and evolution direction of Mucard; (b2) evolution of Mucard;protect łinebreak (b3) final results of Mucard.

  • Table 1   Configurations of the two algorithms compared in this study
    Settings SITATION GA Mucard
    Representation Set Set
    Crossover Uniform crossover RRR operator
    Mutation Greedy interchange Greedy interchange
    Repair Yes No
    Reproduction selection Tournament Tournament
    Survival selection Elitist Crowding distance operator
  • Table A1   Multiplication factors of the average results with different running settings and different numbers of selected sites on each dataset. The values highlighted in bold font are plotted in Figure 3
    $p$ KöerkelGalv ao100Galv ao150
    A B C A B CA B C
    10 0.74 0.98 0.95 0.82 0.99 1.00 0.83 1.00 1.00
    110.800.980.940.821.001.000.831.001.00
    12 0.76 0.980.94 0.82 1.00 1.00 0.81 1.001.00
    130.740.980.930.82 1.001.00 0.81 1.00 1.00
    140.76 0.98 0.93 0.83 1.00 1.00 0.811.001.00
    150.72 1.000.93 0.83 1.00 1.00 0.831.001.00
    160.780.980.92 0.83 1.00 1.00 0.82 1.00 1.00
    170.76 0.99 0.93 0.87 1.00 1.00 0.81 1.00 0.99
    18 0.77 0.99 0.94 0.85 1.00 1.000.80 1.00 0.99
    190.78 0.99 0.930.87 1.00 1.00 0.81 0.99 0.99
    20 0.78 0.980.920.87 1.00 1.00 0.810.990.99

    A: setting (20, 1) to setting (20, 100); B: setting (20, 100) to setting (220, 100); C: setting (20, 100) to setting (20, 1100).

  • Table A2   Multiplication factors of the standard deviations for different running settings and different numbers of selected sites on each dataset. The values highlighted in bold are plotted in Figure 3
    $p$ KöerkelGalv ao100Galv ao150
    A B C A B CA B C
    10 0.12 0.49 0.68 0.33 r
    0.10 0.52 0.09 1.11 0.71
    11 0.08 1.31 0.41 0.13 0.10 0.41 0.07 1.12 1.13
    12 0.11 0.720.62 0.370.38 0.360.07 0.85 0.81
    130.07 0.87 0.53 0.18 0.14 1.02 0.13 0.77 0.64
    140.07 0.66 0.34 0.08 0.04 0.16 0.20 0.41 0.24
    15 0.12 0.87 0.40 0.06 0.22 0.06 0.07 0.93 0.69
    16 0.18 0.46 0.26 0.04 0.34 0.42 0.08 0.71 1.16
    17 0.16 0.96 0.58 0.03 1.522.40 0.24 0.51 0.56
    18 0.16 0.81 0.90 0.02 2.09 1.67 0.18 0.70 0.70
    190.22 0.82 0.61 0.03 1.10 0.86 0.15 1.21 1.01
    20 0.26 0.40 0.60 0.09 0.75 0.36 0.31 0.91 0.73

    A: setting (20, 1) to setting (20, 100); B: setting (20, 100) to setting (220, 100); C: setting (20, 100) to setting (20, 1100).

  • Table 2   Comparison of the mean percentage deviation errors between Mucard and the algoriTheorem in . The small values in the first three rows are favorable
    Port1 Port2 Port3 Port4 Port5
    Row 1 0.01097 0.025240.01108 0.01933 0.00796
    Row 2 0.01560 0.036160.01680 0.033650.01066
    Row 3 0.010950.024640.007380.016720.00504
    Row 4 0.004630.010920.00573 0.014320.00270
    Row 5 $-$0.00002$-$0.00060$-$0.00369 $-$0.00260$-$0.00292

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备17057255号       京公网安备11010102003388号