Comparative Study of Knee-Based Algorithms for Many-Objective Optimization Problems
Article Sidebar
Main Article Content
Abstract
Nowadays, most real-world optimization problems consist of many and often conflicting objectives to be optimized simultaneously. Although, many current Multi-Objective optimization algorithms can efficiently solve problems with 3 or less objectives, their performance deteriorates proportionally with the increasing of the objectives number. Furthermore, in many situations the decision maker (DM) is not interested in all trade-off solutions obtained but rather interested in a single optimum solution or a small set of those trade-offs. Therefore, determining an optimum solution or a small set of trade-off solutions is a difficult task. However, an interesting method for finding such solutions is identifying solutions in the Knee region. Solutions in the Knee region can be considered the best obtained solution in the obtained trade-off set especially if there is no preference or equally important objectives. In this paper, a pruning strategy was used to find solutions in the Knee region of Pareto optimal fronts for some benchmark problems obtained by NSGA-II, MOEA/D-DE and a promising new Multi-Objective optimization algorithm NSGA-III. Lastly, those knee solutions found were compared and evaluated using a generational distance performance metric, computation time and a statistical one-way ANOVA test.
Article Details
References
A. L. Jaimes and C. A. C. Coello, 2015, “Many-Objective Problems: Challenges and Methods”, Springer Handbook of Computational Intelligence, Springer, pp. 1033–1046.
S. Sudeng and N. Wattanapongsakorn, 2016, “A Decomposition-based Approach for Knee Solution Approximation in Multi-Objective Optimization,” 2016 IEEE Congress on Evolutionary Computation (CEC), Vancouver, BC, July 24 -29, 2016.
I. Das, 1999, “On Characterizing the ‘Knee’ of the Pareto Curve Based on Normal-Boundary Intersection,” Structural Optimization, Vol. 18, No. 2–3, pp. 107–115.
K. Deb and H. Jain, 2014, “An Evolutionary Many-Objective Optimization Algorithm Using Reference-point-based Nondominated Sorting Approach, Part I: Solving Problems with Box Constraints,” IEEE Transactions on Evolutionary Computation, Vol. 18, No. 4, pp. 577–601.
Q. Zhang and H. Li, 2007, “MOEA/D: A Multi-Objective Evolutionary Algorithm Based on Decomposition,” IEEE Transactions on Evolutionary Computation, Vol. 11, No. 6, pp. 712–731.
S. Sudeng and N. Wattanapongsakorn, 2015, “A Knee-based Multi-Objective Evolutionary Algorithm: An Extension to Network System Optimization Design Problem,” Cluster Computing, Vol. 19, No. 1, pp. 411–425.
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, 2002, “A Fast and Elitist Multi-Objective Genetic Algorithm: NSGA-II,” IEEE Transactions on Evolutionary Computation, Vol. 6, No. 2, pp. 182–197.
S. Bechikh, L. Ben Said, and K. Ghédira, 2010, “Searching for Knee Regions in Multi-Objective Optimization Using Mobile Reference Points,” Proceedings of the 2010 ACM Symposium on Applied Computing, Sierre, Switzerland, March 22 - 26, 2010, pp. 1118–1125.
S. Bechikh, L. B. Said, and K. Ghédira, 2011, “Searching for Knee Regions of the Pareto Front Using Mobile Reference Points,” Soft Computing, Vol. 15, No. 9, pp. 1807–1823.
H. Li and Q. Zhang, 2009, “Multi-Objective Optimization Problems with Complicated Pareto Sets, MOEA/D and NSGA-II,” IEEE Transactions on Evolutionary Computation, Vol. 13, No. 2, pp. 284–302.
K. Deb and J. Sundar, 2006, “Reference Point Based Multi-Objective Optimization Using Evolutionary Algorithms,” Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, Seattle, WA, USA, July 08 – 12, 2006, pp. 635–642.
K. Deb, L. Thiele, M. Laumanns, and E. Zitzler, 2002, “Scalable Multi-Objective Optimization Test Problems,” 2002 IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, HI, USA, May 12-17, 2002, pp. 825–830.
S. Huband, P. Hingston, L. Barone, and L. While, 2006, “A Review of Multi-Objective Test Problems and A Scalable Test Problem Toolkit,” IEEE Transactions on Evolutionary Computation, Vol. 10, No. 5, pp. 477–506.
J. Branke, K. Deb, H. Dierolf, and M. Osswald, 2004, “Finding Knees in Multi-Objective Optimization,” Proceedings of the 8th International Conference on Parallel Problem Solving from Nature - PPSN VIII, Birmingham, UK, September 18-22, 2004, pp. 722–731.
L. Bradstreet, L. Barone, L. While, S. Huband, and P. Hingston, 2007, “Use of the WFG Toolkit and PISA for Comparison of MOEAs,” IEEE Symposium on Computational Intelligence in Multicriteria Decision Making, Honolulu, HI, USA, April 01 – 05, 2007, pp. 382–389.
C. A. C. Coello, G. B. Lamont, and D. A. V. Veldhuizen, Eds., 2007, “MOEA Test Suites,” in Evolutionary Algorithms for Solving Multi-Objective Problems: Second Edition, Boston, MA: Springer US, pp. 175–232.
S. Mirjalili and A. Lewis, 2015, “Novel Performance Metrics for Robust Multi-Objective Optimization Algorithms,” Swarm and Evolutionary Computation, Vol. 21, pp. 1–23.
J. J. Durillo and A. J. Nebro, 2011, “jMetal: A Java Framework for Multi-Objective Optimization,” Advances in Engineering Software, Vol. 42, No. 10, pp. 760–771, Oct. 2011.
H. Seada and K. Deb, 2015, “U-NSGA-III: A Unified Evolutionary Algorithm for Single, Multiple, and Many-Objective Optimization,” COIN Report, No. 2014022.
K. Li, Research Projects [Online], Available: http://www.cs.bham.ac.uk/~likw/projects.html. [ 22-Jun-2017].
A. J. Nebro, J. J. Durillo, and M. Vergne, “Redesigning the jMetal Multi-Objective optimization framework,” Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, Madrid, Spain, July 11 - 15, 2015, pp. 1093–1100.
A. J. Nebro, J. J. Durillo, and M. Vergne, jMetal 5 Web site [Online]. Available: https://jmetal.github.io/jMetal/. [07-Aug-2017].
J. H. McDonald, “One-way anova,” Handbook of Biological Statistics. [Online]. Available: http://www.biostathandbook.com/onewayanova.html. [07-Aug-2017].
E. Zitzler and L. Thiele, “Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach,” IEEE Transactions on Evolutionary Computation, vol. 3, no. 4, pp. 257–271, Nov. 1999.
J. Maltese, B. M. Ombuki-Berman, and A. P. Engelbrecht, “Pareto-based many-objective optimization using knee points,” 2016 IEEE Congress on Evolutionary Computation (CEC), pp. 3678–3686. November 2016.
A. Zhou, B.-Y. Qu, H. Li, S.-Z. Zhao, P. N. Suganthan, and Q. Zhang, “Multiobjective evolutionary algorithms: A survey of the state of the art,” Swarm and Evolutionary Computation, vol. 1, no. 1, pp. 32–49, 2011.