Runtime Analyses of NSGA-III on Many-Objective Problems

• URL: http://arxiv.org/abs/2404.11433v2
• Date: Thu, 18 Apr 2024 08:09:35 GMT
• Title: Runtime Analyses of NSGA-III on Many-Objective Problems
• Authors: Andre Opris, Duc-Cuong Dang, Frank Neumann, Dirk Sudholt,
• Abstract summary: We present the first runtime analyses of NSGA-III on the popular many-objective benchmark problems mLOTZ, mOMM, and mCOCZ. We show how these parameters should be scaled with the problem dimension, the number of objectives and the fitness range. To our knowledge, these are the first runtime analyses for NSGA-III for more than 3 objectives.
• Score: 10.955844285189372
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: NSGA-II and NSGA-III are two of the most popular evolutionary multi-objective algorithms used in practice. While NSGA-II is used for few objectives such as 2 and 3, NSGA-III is designed to deal with a larger number of objectives. In a recent breakthrough, Wietheger and Doerr (IJCAI 2023) gave the first runtime analysis for NSGA-III on the 3-objective OneMinMax problem, showing that this state-of-the-art algorithm can be analyzed rigorously. We advance this new line of research by presenting the first runtime analyses of NSGA-III on the popular many-objective benchmark problems mLOTZ, mOMM, and mCOCZ, for an arbitrary constant number $m$ of objectives. Our analysis provides ways to set the important parameters of the algorithm: the number of reference points and the population size, so that a good performance can be guaranteed. We show how these parameters should be scaled with the problem dimension, the number of objectives and the fitness range. To our knowledge, these are the first runtime analyses for NSGA-III for more than 3 objectives.

Related papers

• A Crowding Distance That Provably Solves the Difficulties of the NSGA-II in Many-Objective Optimization [13.277972583315051]
  Recent theoretical works have shown that the NSGA-II can have enormous difficulties to solve problems with more than two objectives. We use the insights of these previous work to define a variant of the crowding distance, called truthful crowding distance. We show that this algorithm can solve the many-objective versions of the OneMinMax, COCZ, LOTZ, and OJZJ$_k$ problems.
  arXiv  Detail & Related papers  (2024-07-25T01:09:58Z)
• Near-Tight Runtime Guarantees for Many-Objective Evolutionary Algorithms [10.165640083594573]
  We prove near-tight runtime guarantees for SEMO, global SEMO, and SMS-EMOA algorithms on classic benchmarks. This is the first time that such tight bounds are proven for many-objective uses of these MOEAs.
  arXiv  Detail & Related papers  (2024-04-19T09:46:59Z)
• HKNAS: Classification of Hyperspectral Imagery Based on Hyper Kernel Neural Architecture Search [104.45426861115972]
  We propose to directly generate structural parameters by utilizing the specifically designed hyper kernels. We obtain three kinds of networks to separately conduct pixel-level or image-level classifications with 1-D or 3-D convolutions. A series of experiments on six public datasets demonstrate that the proposed methods achieve state-of-the-art results.
  arXiv  Detail & Related papers  (2023-04-23T17:27:40Z)
• Runtime Analysis for the NSGA-II: Proving, Quantifying, and Explaining the Inefficiency For Many Objectives [16.904475483445452]
  The NSGA-II is one of the most prominent algorithms to solve multi-objective optimization problems. We show that the NSGA-II is less effective for larger numbers of objectives.
  arXiv  Detail & Related papers  (2022-11-23T16:15:26Z)
• A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III) [9.853329403413701]
  The Non-dominated Sorting Genetic Algorithm II (NSGA-II) is the most prominent multi-objective evolutionary algorithm for real-world applications. We provide the first mathematical runtime analysis of the NSGA-III, a refinement of the NSGA-II aimed at better handling more than two objectives.
  arXiv  Detail & Related papers  (2022-11-15T15:10:36Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  We study the OOD generalization of neural algorithmic reasoning tasks. The goal is to learn an algorithm from input-output pairs using deep neural networks.
  arXiv  Detail & Related papers  (2022-11-01T18:33:20Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• Shape-constrained Symbolic Regression with NSGA-III [0.0]
  Shape-constrained symbolic regression (SCSR) allows to include prior knowledge into data-based modeling. This paper presents a mutlicriterial approach to minimize the approximation error as well as the constraint violations. Explicitly the two algorithms NSGA-II and NSGA-III are implemented and compared against each other in terms of model quality and runtime.
  arXiv  Detail & Related papers  (2022-09-28T06:10:34Z)
• Target-Aware Object Discovery and Association for Unsupervised Video Multi-Object Segmentation [79.6596425920849]
  This paper addresses the task of unsupervised video multi-object segmentation. We introduce a novel approach for more accurate and efficient unseen-temporal segmentation. We evaluate the proposed approach on DAVIS$_17$ and YouTube-VIS, and the results demonstrate that it outperforms state-of-the-art methods both in segmentation accuracy and inference speed.
  arXiv  Detail & Related papers  (2021-04-10T14:39:44Z)
• PC-RGNN: Point Cloud Completion and Graph Neural Network for 3D Object Detection [57.49788100647103]
  LiDAR-based 3D object detection is an important task for autonomous driving. Current approaches suffer from sparse and partial point clouds of distant and occluded objects. In this paper, we propose a novel two-stage approach, namely PC-RGNN, dealing with such challenges by two specific solutions.
  arXiv  Detail & Related papers  (2020-12-18T18:06:43Z)
• A Global Benchmark of Algorithms for Segmenting Late Gadolinium-Enhanced Cardiac Magnetic Resonance Imaging [90.29017019187282]
  " 2018 Left Atrium Challenge" using 154 3D LGE-MRIs, currently the world's largest cardiac LGE-MRI dataset. Analyse of the submitted algorithms using technical and biological metrics was performed. Results show the top method achieved a dice score of 93.2% and a mean surface to a surface distance of 0.7 mm.
  arXiv  Detail & Related papers  (2020-04-26T08:49:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.