An Enhanced Differential Grouping Method for Large-Scale Overlapping Problems

• URL: http://arxiv.org/abs/2404.10515v1
• Date: Tue, 16 Apr 2024 12:38:03 GMT
• Title: An Enhanced Differential Grouping Method for Large-Scale Overlapping Problems
• Authors: Maojiang Tian, Mingke Chen, Wei Du, Yang Tang, Yaochu Jin,
• Abstract summary: We propose a two-stage enhanced grouping method for large-scale overlapping problems, called OEDG. In the first stage, OEDG employs a grouping method based on the finite differences principle to identify all subcomponents and shared variables. In the second stage, we propose two grouping refinement methods, called subcomponent union detection (SUD) and subcomponent detection (SD), to enhance and refine the grouping results.
• Score: 23.17606455044122
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large-scale overlapping problems are prevalent in practical engineering applications, and the optimization challenge is significantly amplified due to the existence of shared variables. Decomposition-based cooperative coevolution (CC) algorithms have demonstrated promising performance in addressing large-scale overlapping problems. However, current CC frameworks designed for overlapping problems rely on grouping methods for the identification of overlapping problem structures and the current grouping methods for large-scale overlapping problems fail to consider both accuracy and efficiency simultaneously. In this article, we propose a two-stage enhanced grouping method for large-scale overlapping problems, called OEDG, which achieves accurate grouping while significantly reducing computational resource consumption. In the first stage, OEDG employs a grouping method based on the finite differences principle to identify all subcomponents and shared variables. In the second stage, we propose two grouping refinement methods, called subcomponent union detection (SUD) and subcomponent detection (SD), to enhance and refine the grouping results. SUD examines the information of the subcomponents and shared variables obtained in the previous stage, and SD corrects inaccurate grouping results. To better verify the performance of the proposed OEDG, we propose a series of novel benchmarks that consider various properties of large-scale overlapping problems, including the topology structure, overlapping degree, and separability. Extensive experimental results demonstrate that OEDG is capable of accurately grouping different types of large-scale overlapping problems while consuming fewer computational resources. Finally, we empirically verify that the proposed OEDG can effectively improve the optimization performance of diverse large-scale overlapping problems.

Related papers

• COMPOSE: Hypergraph Cover Optimization for Multi-view 3D Human Pose Estimation [58.47973015036709]
  3D pose estimation from sparse multi-views is a critical task for action recognition, sports analysis, and human-robot interaction.<n>We propose COMPOSE, a novel framework that formulates multi-view pose correspondence matching as a hypergraph problem.<n> COMPOSE achieves improvements of up to 23% in average precision over previous optimization-based methods and up to 11% over self-supervised end-to-end learned methods.
  arXiv  Detail & Related papers  (2026-01-14T18:50:17Z)
• Accelerating Spectral Clustering under Fairness Constraints [56.865810822418744]
  We present a new efficient method for fair spectral clustering (Fair SC) by casting the Fair SC problem within the difference of convex functions (DC) framework.<n>We show that each associated subproblem can be solved efficiently, resulting in higher computational efficiency compared to prior work.
  arXiv  Detail & Related papers  (2025-06-09T18:46:27Z)
• A Novel Two-Phase Cooperative Co-evolution Framework for Large-Scale Global Optimization with Complex Overlapping [8.839347987566336]
  We propose a novel two-phase cooperative co-evolution framework to address large-scale global optimization problems with complex overlapping. An effective method for decomposing overlapping problems, grounded in their mathematical properties, is embedded within the framework. Extensive experiments demonstrate that the algorithm instantiated within our framework significantly outperforms existing algorithms.
  arXiv  Detail & Related papers  (2025-03-23T13:21:11Z)
• A Composite Decomposition Method for Large-Scale Global Optimization [30.040728803996256]
  The efficiency and accuracy of the grouping stage significantly impact the performance of the optimization process. This article proposes a composite separability grouping (CSG) method, seamlessly integrating the general separability grouping (GSG) method. CSG achieves more accurate variable grouping with lower computational complexity compared to GSG and state-of-the-art DG series designs.
  arXiv  Detail & Related papers  (2024-03-02T12:12:04Z)
• Modeling the Q-Diversity in a Min-max Play Game for Robust Optimization [61.39201891894024]
  Group distributionally robust optimization (group DRO) can minimize the worst-case loss over pre-defined groups. We reformulate the group DRO framework by proposing Q-Diversity. Characterized by an interactive training mode, Q-Diversity relaxes the group identification from annotation into direct parameterization.
  arXiv  Detail & Related papers  (2023-05-20T07:02:27Z)
• AGRO: Adversarial Discovery of Error-prone groups for Robust Optimization [109.91265884632239]
  Group distributionally robust optimization (G-DRO) can minimize the worst-case loss over a set of pre-defined groups over training data. We propose AGRO -- Adversarial Group discovery for Distributionally Robust Optimization. AGRO results in 8% higher model performance on average on known worst-groups, compared to prior group discovery approaches.
  arXiv  Detail & Related papers  (2022-12-02T00:57:03Z)
• Cooperative coevolutionary hybrid NSGA-II with Linkage Measurement Minimization for Large-scale Multi-objective optimization [3.274290296343038]
  We propose a variable grouping method based on cooperative coevolution for large-scale multi-objective problems (LSMOPs) For the sub-problem optimization stage, a hybrid NSGA-II with a Gaussian sampling operator based on an estimated convergence point is proposed.
  arXiv  Detail & Related papers  (2022-08-29T08:18:15Z)
• Late Fusion Multi-view Clustering via Global and Local Alignment Maximization [61.89218392703043]
  Multi-view clustering (MVC) optimally integrates complementary information from different views to improve clustering performance. Most of existing approaches directly fuse multiple pre-specified similarities to learn an optimal similarity matrix for clustering. We propose late fusion MVC via alignment to address these issues.
  arXiv  Detail & Related papers  (2022-08-02T01:49:31Z)
• Incremental Recursive Ranking Grouping for Large Scale Global Optimization [2.8360662552057323]
  In Large Scale Global Optimization (LSGO), problems are high-dimensional. It was shown effective to decompose LSGO problems into subproblems and optimize them separately. Many state-of-the-art decomposition strategies are derived from Differential Grouping (DG). We propose Incremental Recursive Ranking Grouping (IRRG) that does not suffer from this flaw.
  arXiv  Detail & Related papers  (2022-06-08T21:16:42Z)
• Semi-supervised Domain Adaptive Structure Learning [72.01544419893628]
  Semi-supervised domain adaptation (SSDA) is a challenging problem requiring methods to overcome both 1) overfitting towards poorly annotated data and 2) distribution shift across domains. We introduce an adaptive structure learning method to regularize the cooperation of SSL and DA.
  arXiv  Detail & Related papers  (2021-12-12T06:11:16Z)
• Manifold Interpolation for Large-Scale Multi-Objective Optimization via Generative Adversarial Networks [12.18471608552718]
  Large-scale multiobjective optimization problems (LSMOPs) are characterized as involving hundreds or even thousands of decision variables and multiple conflicting objectives. Previous research has shown that these optimal solutions are uniformly distributed on the manifold structure in the low-dimensional space. In this work, a generative adversarial network (GAN)-based manifold framework is proposed to learn the manifold and generate high-quality solutions.
  arXiv  Detail & Related papers  (2021-01-08T09:38:38Z)
• AP-Loss for Accurate One-Stage Object Detection [49.13608882885456]
  One-stage object detectors are trained by optimizing classification-loss and localization-loss simultaneously. The former suffers much from extreme foreground-background imbalance due to the large number of anchors. This paper proposes a novel framework to replace the classification task in one-stage detectors with a ranking task.
  arXiv  Detail & Related papers  (2020-08-17T13:22:01Z)
• Detached Error Feedback for Distributed SGD with Random Sparsification [98.98236187442258]
  Communication bottleneck has been a critical problem in large-scale deep learning. We propose a new distributed error feedback (DEF) algorithm, which shows better convergence than error feedback for non-efficient distributed problems. We also propose DEFA to accelerate the generalization of DEF, which shows better bounds than DEF.
  arXiv  Detail & Related papers  (2020-04-11T03:50:59Z)
• An Eigenspace Divide-and-Conquer Approach for Large-Scale Optimization [9.501723707464432]
  Divide-and-conquer (DC) evolutionary algorithms have achieved notable success in dealing with large-scale optimization problems. This study proposes an eigenspace divide-and-conquer (EDC) approach.
  arXiv  Detail & Related papers  (2020-04-05T07:29:44Z)

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.