Global view-based selection mechanism for many-objective evolutionary algorithms
Authors: 
Yanan Sun, Gary G. Yen, Zhang YiAuthors Info & Claims
Pages 427 - 434
Abstract
In traditional many-objective evolutionary algorithms (MaOEAs), solutions survived to the next generation are individually selected which leads to the favorable quality upon the population composed of these selected solutions not necessarily to be gained. However, MaOEAs which are widely used in solving many-objective optimization problems (MaOPs) are considerably preferred due to their population-based nature. In this paper, a global view-based selection mechanism has been proposed to concern the quality of the selected solutions from a global prospective, which is capable of simultaneously facilitating the performance of the entire selected solutions. Indeed, the proposed selection mechanism is equivalent to solve a linear assignment problem whose cost matrix is constructed by the entries concurrently measuring the convergence and diversity of each solution. In addition, this design principle is also utilized for the mating selection to guarantee the convergence and diversity of the selected parents to generate promising offspring. As a case study, the proposed global view-based selection mechanism is integrated into NSGA-III (i.e., GS-NSGA-III). To validate the proposed selection mechanism, extensive experiments are performed by GS-NSGA-III against four state-of-the-art MaOEAs over 8-, 10-, and 15-objective DTLZ1-DTLZ7 test problems. The results measured by the selected performance metric reveal that GS-NSGA-III shows considerable competitiveness in addressing MaOPs.
References
[1]
M. Farina and P. Amato, “On the optimal solution definition for many-criteria optinization problems,” in Proceedings of the NAFIPS-FLINT international conference, 2002, pp. 233–238.
[2]
R.J. Lygoe, M. Cary, and P.J. Fleming, “A real-world application of a many-objective optimisation complexity reduction process,” in Evolutionary Multi-Criterion Optimization. Springer, 2013, pp. 641–655.
[3]
O. Chikumbo, E. Goodman, and K. Deb, “Approximating a multidimensional pareto front for a land use management problem: A modified moea with an epigenetic silencing metaphor,” in Evolutionary Computation (CEC), 2012 IEEE Congress on. IEEE, 2012, pp. 1–9.
[4]
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, “A fast and elitist multiobjective genetic algorithm: Nsga-ii,” Evolutionary Computation, IEEE Transactions on, vol. 6, no. 2, pp. 182–197, 2002.
[5]
E. Zitzler, M. Laumanns, L. Thiele, E. Zitzler, E. Zitzler, L. Thiele, and L. Thiele, “Spea2: Improving the strength pareto evolutionary algorithm,” 2001.
[6]
Y. Sun, G.G. Yen, H. Mao, and Z. Yi, “Manifold dimension reduction based clustering for multi-objective evolutionary algorithm,” in Evolutionary Computation (CEC), 2016 IEEE Congress on. IEEE, 2016, pp. 3785–3792.
[7]
J. Knowles and D. Corne, “Quantifying the effects of objective space dimension in evolutionary multiobjective optimization,” in Evolutionary multi-criterion optimization. Springer, 2007, pp. 757–771.
[8]
R.C. Purshouse and P.J. Fleming, “On the evolutionary optimization of many conflicting objectives,” Evolutionary Computation, IEEE Transactions on, vol. 11, no. 6, pp. 770–784, 2007.
[9]
C.M. Fonseca and P.J. Fleming, “Multiobjective optimization and multiple constraint handling with evolutionary algorithms. i. a unified formulation,” Systems, Man and Cybernetics, Part A: Systems and Humans, IEEE Transactions on, vol. 28, no. 1, pp. 26–37, 1998.
[10]
T. Wagner, N. Beume, and B. Naujoks, “Pareto-, aggregation-, and indicator-based methods in many-objective optimization,” in Evolutionary multi-criterion optimization. Springer, 2007, pp. 742–756.
[11]
K. Deb and H. Jain, “An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: Solving problems with box constraints,” Evolutionary Computation, IEEE Transactions on, vol. 18, no. 4, pp. 577–601, 2014.
[12]
Y. Yuan, H. Xu, B. Wang, and X. Yao, “A new dominance relation-based evolutionary algorithm for many-objective optimization,” IEEE Transactions on Evolutionary Computation, vol. 20, no. 1, pp. 16–37, 2016.
[13]
R. Cheng, Y. Jin, M. Olhofer, and B. Sendhoff, “A reference vector guided evolutionary algorithm for many-objective optimization,” IEEE Transactions on Evolutionary Computation, vol. 20, no. 5, pp. 773–791, 2016.
[14]
Q. Zhang and H. Li, “Moea/d: A multiobjective evolutionary algorithm based on decomposition,” Evolutionary Computation, IEEE Transactions on, vol. 11, no. 6, pp. 712–731, 2007.
[15]
Y. Yuan, H. Xu, B. Wang, B. Zhang, and X. Yao, “Balancing convergence and diversity in decomposition-based many-objective optimizers,” IEEE Transactions on Evolutionary Computation, vol. 20, no. 2, pp. 180–198, 2016.
[16]
Z. Wang, Q. Zhang, M. Gong, and A. Zhou, “A replacement strategy for balancing convergence and diversity in moea/d,” in 2014 IEEE Congress on Evolutionary Computation (CEC). IEEE, 2014, pp. 2132–2139.
[17]
M. Laumanns, L. Thiele, K. Deb, and E. Zitzler, “Combining convergence and diversity in evolutionary multiobjective optimization,” Evolutionary computation, vol. 10, no. 3, pp. 263–282, 2002.
[18]
F. di Pierro, S.-T. Khu, and D.A. Savic, “An investigation on preference order ranking scheme for multiobjective evolutionary optimization,” IEEE Transactions on Evolutionary Computation, vol. 11, no. 1, pp. 17–45, 2007.
[19]
G. Wang and H. Jiang, “Fuzzy-dominance and its application in evolutionary many objective optimization,” in Computational Intelligence and Security Workshops, 2007. CISW 2007. International Conference on. IEEE, 2007, pp. 195–198.
[20]
Z. He, G.G. Yen, and J. Zhang, “Fuzzy-based pareto optimality for many-objective evolutionary algorithms,” IEEE Transactions on Evolutionary Computation, vol. 18, no. 2, pp. 269–285, 2014.
[21]
S. Yang, M. Li, X. Liu, and J. Zheng, “A grid-based evolutionary algorithm for many-objective optimization,” IEEE Transactions on Evolutionary Computation, vol. 17, no. 5, pp. 721–736, 2013.
[22]
H. Trautmann, G. Rudolph, C. Dominguez-Medina, and O. Schütze, “Finding evenly spaced pareto fronts for three-objective optimization problems,” in EVOLVE-A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation II. Springer, 2013, pp. 89–105.
[23]
C.A. Rodríguez Villalobos and C.A. Coello Coello, “A new multiobjective evolutionary algorithm based on a performance assessment indicator,” in Proceedings of the 14th annual conference on Genetic and evolutionary computation. ACM, 2012, pp. 505–512.
[24]
H. Ishibuchi, H. Masuda, Y. Tanigaki, and Y. Nojima, “Modified distance calculation in generational distance and inverted generational distance,” in International Conference on Evolutionary Multi-Criterion Optimization. Springer, 2015, pp. 110–125.
[25]
M. Emmerich, N. Beume, and B. Naujoks, “An emo algorithm using the hypervolume measure as selection criterion,” in International Conference on Evolutionary Multi-Criterion Optimization. Springer, 2005, pp. 62–76.
[26]
C. Igel, N. Hansen, and S. Roth, “Covariance matrix adaptation for multi-objective optimization,” Evolutionary computation, vol. 15, no. 1, pp. 1–28, 2007.
[27]
J. Bader and E. Zitzler, “Hype: An algorithm for fast hypervolume-based many-objective optimization,” Evolutionary computation, vol. 19, no. 1, pp. 45–76, 2011.
[28]
H.W. Kuhn, “The hungarian method for the assignment problem,” Naval researchlogistics quarterly, vol. 2, no. 1–2, pp. 83–97, 1955.
[29]
J. Munkres, “Algorithms for the assignment and transportation problems,” Journal of the society for industrial and applied mathematics, vol. 5, no. 1, pp. 32–38, 1957.
[30]
I. Das and J.E. Dennis, “Normal-boundary intersection: A new method for generating the pareto surface in nonlinear multicriteria optimization problems,” SIAM Journal on Optimization, vol. 8, no. 3, pp. 631–657, 1998.
[31]
S.F. Adra and P.J. Fleming, “Diversity management in evolutionary many-objective optimization,” IEEE Transactions on Evolutionary Computation, vol. 15, no. 2, pp. 183–195, 2011.
[32]
K. Deb and D.E. Goldberg, “An investigation of niche and species formation in genetic function optimization,” in Proceedings of the 3rd international conference on genetic algorithms. Morgan Kaufmann Publishers Inc., 1989, pp. 42–50.
[33]
K. Deb and R.B. Agrawal, “Simulated binary crossover for continuous search space,” Complex Systems, vol. 9, no. 3, pp. 1–15, 1994.
[34]
K. Deb, Multi-objective optimization using evolutionary algorithms. John Wiley & Sons, 2001, vol. 16.
[35]
B.L. Miller and D.E. Goldberg, “Genetic algorithms, tournament selection, and the effects of noise,” Complex systems, vol. 9, no. 3, pp. 193–212, 1995.
[36]
F. Bourgeois and J.-C. Lassalle, “An extension of the munkres algorithm for the assignment problem to rectangular matrices,” Communications of the ACM, vol. 14, no. 12, pp. 802–804, 1971.
[37]
J.A.M. Berenguer and C.A.C. Coello, “Evolutionary many-objective optimization based on kuhn-munkres algorithm,” in International Conference on Evolutionary Multi-Criterion Optimization. Springer, 2015, pp. 3–17.
[38]
K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, Scalable test problems for evolutionary multiobjective optimization. Springer, 2005.
[39]
P.A. Bosman and D. Thierens, “The balance between proximity and diversity in multiobjective evolutionary algorithms,” Evolutionary Computation, IEEE Transactions on, vol. 7, no. 2, pp. 174–188, 2003.
[40]
R.G. Steel, D.JH Dickey et al., Principles and procedures of statistics a biometrical approach. WCB/McGraw-Hill, 1997, no. 519.5 S813 1997.
[41]
H. Karshenas, R. Santana, C. Bielza, and P. Larranaga, “Multiobjective estimation of distribution algorithm based on joint modeling of objectives and variables,” Evolutionary Computation, IEEE Transactions on, vol. 18, no. 4, pp. 519–542, 2014.
[42]
S. Huband, P. Hingston, L. Barone, and L. While, “A review of multiobjective test problems and a scalable test problem toolkit,” Evolutionary Computation, IEEE Transactions on, vol. 10, no. 5, pp. 477–506, 2006.
Index Terms
- Global view-based selection mechanism for many-objective evolutionary algorithms
Index terms have been assigned to the content through auto-classification.
Recommendations
Many-Objective Evolutionary Algorithms Based on Coordinated Selection Strategy
Selection strategy, including mating selection and environmental selection, is a key ingredient in the design of evolutionary multiobjective optimization algorithms. Existing approaches, which have shown competitive performance in low-dimensional ...
Many-objective E-dominance dynamical evolutionary algorithm based on adaptive grid
In evolutionary multi-objective optimization, achieving a balance between convergence speed and population diversity remains a challenging topic especially for many-objective optimization problems (MaOPs). To accelerate convergence toward the Pareto ...
Optimization of sensor selection problem in IoT systems using opposition-based learning in many-objective evolutionary algorithms
AbstractIn the Internet of Things (IoT) systems, physical objects are connected to each other through sensor devices that serve multiple functionalities. The sensor selection is known to be an NP-hard problem. Thus, Evolutionary Algorithms (...
Graphical abstractDisplay Omitted
Highlights- The sensor selection is considered as a many-objective problem with 5 objectives.
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Jun 2017
2814 pages
Copyright © 2017.
Publisher
IEEE Press
Publication History
Published: 05 June 2017
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024