×

Diversity based selection for many-objective evolutionary optimisation problems with constraints. (English) Zbl 1475.90136

Summary: The paper introduces a novel many-objective evolutionary method, with a diversity-based selection operator and aims to fill the “gaps” in the Pareto Front approximation and to increase its spread. It shows, that guiding the evolution process towards the least explored parts of a space increases overall diversity, but can also lead to increased convergence. A set of experiments is carried out on a many-objective Multi-Skill Resource-Constrained Project Scheduling Problem and a bi-objective Travelling Thief Problem. Both of those problems comprise two interwoven subproblems. Separate optimal solutions to the subproblems do not guarantee the optimal solution to the entire problem. Moreover, it shows that the existing diversity mechanism does not work well in combinatorial spaces, where the domain of each objective has a different size. The results indicate that a novel selection operator circumvents this issue. A set of Quality Measures is used to describe the desirable features of Pareto Front approximation: convergence, uniformity, and spread. The experiments are followed by a set of visualizations. Along with a set of Quality Measures, they give an insight into the characteristics of the method. The paper is concluded by a thorough theoretical analysis and possible directions for future work.

MSC:

90C59 Approximation methods and heuristics in mathematical programming

Software:

HypE; MOEA/D
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Myszkowski, Paweł B.; Skowroński, Marek E.; Podlodowski, Łukasz, Novel heuristic solutions for multi-skill resource-constrained project scheduling problem, (2013 Fed. Conf. on Computer Science and Information Systems (2013), IEEE)
[2] Myszkowski, PawełB.; Skowroński, Marek E.; Sikora, Krzysztof, A new benchmark dataset for multi-skill resource-constrained project scheduling problem. 2015 Fed, (2015 Conf. on Computer Science and Inf. Systems (FedCSIS) (2015), IEEE)
[3] Zheng, Huan-yu; Wang, Ling; Zheng, Xiao-long, Teaching-learning-based optimisation algorithm for multi-skill resource constrained project scheduling problem, Soft. Comput., 21, 6, 1537-1548 (2017)
[4] Dai, Huafeng; Cheng, Wenming; Guo, Peng, An improved Tabu search for multi-skill resource-constrained project scheduling problems under step-deterioration, Arabian J. Sci. Eng., 43, 6, 3279-3290 (2018)
[5] Myszkowski, PawełB., Hybrid differential evolution and greedy algorithm (DEGR) for solving multi-skill resource-constrained project scheduling problem, Appl. Soft Comput., 62, 1-14 (2018)
[6] Wang, Ling; Zheng, Xiao-long, A knowledge-guided multi-objective fruit fly optimisation algorithm for the multi-skill resource constrained project scheduling problem, Swarm Evol. Comput., 38, 54-63 (2018)
[7] Nemati-Lafmejani, Reza; Davari-Ardakani, Hamed; Najafzad, Hamid, Multi-mode resource constrained project scheduling and contractor selection: Mathematical formulation and metaheuristic algorithms, Appl. Soft Comput., 81, Article 105533 pp. (2019)
[8] Bonyadi, Mohammad Reza; Michalewicz, Zbigniew; Barone, Luigi, The travelling thief problem: The first step in the transition from theoretical problems to realistic problems, (2013 IEEE Congress on Evolutionary Computation (2013), IEEE)
[9] Polyakovskiy, Sergey, A comprehensive benchmark set and heuristics for the traveling thief problem, (Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (2014), ACM)
[10] Polyakovskiy, Sergey; Neumann, Frank, Packing while traveling: Mixed integer programming for a class of nonlinear knapsack problems, (International Conference on AI and OR Techniques in Constriant Programming for Combinatorial optimisation Problems (2015), Springer: Springer Cham) · Zbl 1459.90187
[11] Wagner, Markus. Stealing items more efficiently with ants: a swarm intelligence approach to the travelling thief problem (extended version), International Conference on Swarm Intelligence, 2016.
[12] Martins, Marcella SR, HSEDA: a heuristic selection approach based on estimation of distribution algorithm for the travelling thief problem, (Proceedings of the Genetic and Evolutionary Computation Conference (2017), ACM)
[13] Yafrani, El, Mohamed A hyperheuristic approach based on low-level heuristics for the travelling thief problem, Genet. Program Evolvable Mach., 19, 1-2, 121-150 (2018)
[14] Blank, Julian; Deb, Kalyanmoy; Mostaghim, Sanaz, Solving the Bi-objective Traveling Thief Problem with Multi-objective Evolutionary Algorithms, (Inter. Conf. on Evolutionary Multi-Criterion optimisation (2017), Springer: Springer Cham)
[15] Wu, Junhua, Evolutionary computation plus dynamic programming for the bi-objective travelling thief problem, (Proceedings of the Genetic and Evolutionary Computation Conference (2018), ACM)
[16] He, Zhenan; Yen, Gary G.; Zhang, Jun, Fuzzy-based Pareto optimality for many-objective evolutionary algorithms, IEEE Trans. Evol. Comput., 18, 2, 269-285 (2013)
[17] Zhang, Qingfu; Li, Hui, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731 (2007)
[18] Bader, Johannes; Zitzler, Eckart, HypE: An algorithm for fast hypervolume-based many-objective optimization, Evol. Comput., 19, 1, 45-76 (2011)
[19] Rostami, Shahin; Neri, Ferrante, A fast hypervolume driven selection mechanism for many-objective optimisation problems, Swarm Evol. Comput., 34, 50-67 (2017)
[20] Yang, Cuie, Two-stage assortative mating for multi-objective multifactorial evolutionary optimization, (2017 IEEE 56th Annual Conference on Decision and Control (CDC) (2017), IEEE)
[21] Tang, Zedong; Gong, Maoguo, Adaptive multifactorial particle swarm optimisation, CAAI Trans. Intell. Technol., 4, 1, 37-46 (2019)
[22] Laszczyk, Maciej; Myszkowski, PawełB., Improved selection in evolutionary multi-objective optimisation of Multi-Skill Resource-Constrained project scheduling problem, Inf. Sci., 481, 412-431 (2019) · Zbl 1443.90184
[23] Laszczyk, Maciej; Myszkowski, PawełB., Survey of quality measures for multi-objective optimisation. Construction of complementary set of multi-objective quality measures, Swarm Evol. Comput. (2019)
[24] Marti, Luis; Segredo, Eduardo; Hart, Emma, Impact of selection methods on the diversity of many-objective Pareto set approximations, Procedia Computer Sci., 112, 844-853 (2017)
[25] Talukder, A. K.M.; Deb, Kalyanmoy; Rahnamayan, Shahryar, Maintaining diversity in the bounded pareto-set: A case of opposition based solution generation scheme, (Proceedings of the 2016 on Genetic and Evolutionary Computation Conference Companion (2016), ACM)
[26] Lin, Dong, Niching pareto ant colony optimisation algorithm for bi-objective path finding problem, IEEE Access, 6, 21184-21194 (2018)
[27] Cheng, Ran, Model-based evolutionary algorithms: a short survey, Complex Intell. Syst., 4, 4, 283-292 (2018)
[28] Martins, Jean P.; Delbem, Alexandre CB, Pairwise independence and its impact on Estimation of Distribution Algorithms, Swarm Evol. Comput., 27, 80-96 (2016)
[29] Martins, Jean P.; Delbem, Alexandre CB, Multimodality and the linkage-learning difficulty of additively separable functions, (Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (2014))
[30] Luong, Ngoc Hoang; La Poutré, Han; Bosman, Peter AN, Multi-objective gene-pool optimal mixing evolutionary algorithms, (Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (2014))
[31] Luong, Ngoc Hoang; La Poutré, Han; Bosman, Peter A. N., Multi-objective Gene-pool optimal mixing evolutionary algorithm with the interleaved multi-start scheme, Swarm Evol. Comput., 40, 238-254 (2018)
[32] Zhang, Qingfu; Li, Hui, MOEA/D: A multiobjective evolutionary algorithm based on decomposition, IEEE Trans. Evol. Comput., 11, 6, 712-731 (2007)
[33] Ishibuchi, Hisao; Doi, Ken; Nojima, Yusuke, On the effect of normalization in MOEA/D for multi-objective and many-objective optimization, Complex Intell. Syst., 3, 4, 279-294 (2017)
[34] Li, Juan, Solving the uncertain multi-objective multi-stage weapon target assignment problem via MOEA/D-AWA, (2016 IEEE Congress on Evolutionary Computation (CEC) (2016), IEEE)
[35] Yuan, Yuan, A new dominance relation-based evolutionary algorithm for many-objective optimization, IEEE Trans. Evol. Comput., 20, 1, 16-37 (2015)
[36] Nayeem, Muhammad Ali; Islam, Md Monirul; Yao, Xin, Solving transit network design problem using many-objective evolutionary approach, IEEE Trans. Intell. Transp. Syst., 20, 10, 3952-3963 (2018)
[37] Seada, Haitham, Kalyanmoy Deb. U-NSGA-III: A unified evolutionary algorithm for single, multiple, and many-objective optimization. COIN report 2014022 (2014). · Zbl 1409.90175
[38] Zhang, Xingyi, A decision variable clustering-based evolutionary algorithm for large-scale many-objective optimization, IEEE Trans. Evol. Comput., 22, 1, 97-112 (2016)
[39] Jiang, Shouyong; Yang, Shengxiang, A strength Pareto evolutionary algorithm based on reference direction for multiobjective and many-objective optimization, IEEE Trans. Evol. Comput., 21, 3, 329-346 (2017)
[40] Domingos, Pedro M., A few useful things to know about machine learning, Commun. acm, 55, 10, 78-87 (2012)
[41] Hartmann, Sonke; Briskorn, Dirk, A survey of variants and extensions of the resource-constrained project scheduling problem, Eur. J. Operational Res., 207, 1, 1-14 (2010) · Zbl 1205.90123
[42] Konstantinidis, Andreas; Pericleous, Savvas; Charalambous, Christoforos, Meta-Lamarckian learning in multi-objective optimization for mobile social network search, Appl. Soft Comput., 67, 70-93 (2018)
[43] Lopes, Luiz Gustavo, Dias Robust parameter optimization based on multivariate normal boundary intersection, Computers Ind. Eng., 93, 55-66 (2016)
[44] Cao, Yongtao; Smucker, Byran J.; Robinson, Timothy J., On using the hypervolume indicator to compare Pareto fronts: Applications to multi-criteria optimal experimental design, J. Stat. Planning Inference, 160, 60-74 (2015) · Zbl 1311.62115
[45] Lopez-Ibanez, M.; Paquete, L.; Stutzle, T., Exploratory analysis of stochastic local search algorithms in biobjective optimization, Exp. Methods Anal. Optimization Algorithms, 209-222 (2010) · Zbl 1208.90154
[46] Durairaj, M.; Sudharsun, D.; Swamynathan, N., Analysis of process parameters in wire EDM with stainless steel using single objective Taguchi method and multi objective grey relational grade, Procedia Eng., 64, 868-877 (2013)
[47] Ishibuchi, Hisao; Akedo, Naoya; Nojima, Yusuke, Behavior of multiobjective evolutionary algorithms on many-objective knapsack problems, IEEE Trans. Evol. Comput., 19, 2, 264-283 (2014)
[48] Ishibuchi, Hisao; Akedo, Naoya; Nojima, Yusuke, A study on the specification of a scalarizing function in MOEA/D for many-objective knapsack problems, (International Conference on Learning and Intelligent Optimization (2013), Springer: Springer Berlin, Heidelberg)
[49] Ishibuchi, Hisao, Naoya Akedo, Yusuke Nojima, [www_content] Traveling Thief Competition (Conference GECCO 2019) Homepage, https://www.egr.msu.edu/coinlab/blankjul/gecco19-thief/.
[50] Ishibuchi, Hisao, Naoya Akedo, Yusuke Nojima, [www_content] iMOPSE project homepage – http://imopse.ii.pwr.wroc.pl/.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.