Efficient Parallel Genetic Algorithm for Perturbed Substructure Optimization in Complex Network

• URL: http://arxiv.org/abs/2412.20980v1
• Date: Mon, 30 Dec 2024 14:32:39 GMT
• Title: Efficient Parallel Genetic Algorithm for Perturbed Substructure Optimization in Complex Network
• Authors: Shanqing Yu, Meng Zhou, Jintao Zhou, Minghao Zhao, Yidan Song, Yao Lu, Zeyu Wang, Qi Xuan,
• Abstract summary: Genetic algorithm (GA) has shown significant performance and potentiality on perturbed substructure (PSSO) This paper is the first to present the GA-based PSSO Acceleration framework (GAPA)
• Score: 12.03018614511266
• License:
• Abstract: Evolutionary computing, particularly genetic algorithm (GA), is a combinatorial optimization method inspired by natural selection and the transmission of genetic information, which is widely used to identify optimal solutions to complex problems through simulated programming and iteration. Due to its strong adaptability, flexibility, and robustness, GA has shown significant performance and potentiality on perturbed substructure optimization (PSSO), an important graph mining problem that achieves its goals by modifying network structures. However, the efficiency and practicality of GA-based PSSO face enormous challenges due to the complexity and diversity of application scenarios. While some research has explored acceleration frameworks in evolutionary computing, their performance on PSSO remains limited due to a lack of scenario generalizability. Based on these, this paper is the first to present the GA-based PSSO Acceleration framework (GAPA), which simplifies the GA development process and supports distributed acceleration. Specifically, it reconstructs the genetic operation and designs a development framework for efficient parallel acceleration. Meanwhile, GAPA includes an extensible library that optimizes and accelerates 10 PSSO algorithms, covering 4 crucial tasks for graph mining. Comprehensive experiments on 18 datasets across 4 tasks and 10 algorithms effectively demonstrate the superiority of GAPA, achieving an average of 4x the acceleration of Evox. The repository is in https://github.com/NetAlsGroup/GAPA.

Related papers

• EvoGP: A GPU-accelerated Framework for Tree-based Genetic Programming [8.571010338499422]
  Tree-based Genetic Programming (TGP) is a key evolutionary algorithm widely used in symbolic regression, feature engineering, and scientific modeling. To address these challenges, we introduce EvoGP, a comprehensive GPU-accelerated TGP framework. We show that EvoGP achieves up to a 140.89x speedup over the state-of-the-art TGP implementation.
  arXiv  Detail & Related papers  (2025-01-21T07:42:54Z)
• GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
  We present a Graph Diffusion-based Solution Generation (GDSG) method. This approach is designed to work with suboptimal datasets while converging to the optimal solution large probably. We build GDSG as a multi-task diffusion model utilizing a Graph Neural Network (GNN) to acquire the distribution of high-quality solutions.
  arXiv  Detail & Related papers  (2024-12-11T11:13:43Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• The FAIRy Tale of Genetic Algorithms [1.0957528713294875]
  We have extended Findable, Accessible, Interoperable and Reusable (FAIR) data principles to enable Genetic and reusability of algorithms. We have presented an overview of methodological developments and variants of GA that makes it challenging to reproduce or even find the right source. This work can be extended to numerous machine learning algorithms/methods.
  arXiv  Detail & Related papers  (2023-04-29T11:36:09Z)
• Genetically Modified Wolf Optimization with Stochastic Gradient Descent for Optimising Deep Neural Networks [0.0]
  This research aims to analyze an alternative approach to optimizing neural network (NN) weights, with the use of population-based metaheuristic algorithms. A hybrid between Grey Wolf (GWO) and Genetic Modified Algorithms (GA) is explored, in conjunction with Gradient Descent (SGD) This algorithm allows for a combination between exploitation and exploration, whilst also tackling the issue of high-dimensionality.
  arXiv  Detail & Related papers  (2023-01-21T13:22:09Z)
• Evolving Pareto-Optimal Actor-Critic Algorithms for Generalizability and Stability [67.8426046908398]
  Generalizability and stability are two key objectives for operating reinforcement learning (RL) agents in the real world. This paper presents MetaPG, an evolutionary method for automated design of actor-critic loss functions.
  arXiv  Detail & Related papers  (2022-04-08T20:46:16Z)
• Surrogate-Assisted Genetic Algorithm for Wrapper Feature Selection [4.89253144446913]
  We propose a novel multi-stage feature selection framework utilizing multiple levels of approximations, or surrogates. Our experiments show that SAGA can arrive at near-optimal solutions three times faster than a wrapper GA, on average.
  arXiv  Detail & Related papers  (2021-11-17T12:33:18Z)
• ES-Based Jacobian Enables Faster Bilevel Optimization [53.675623215542515]
  Bilevel optimization (BO) has arisen as a powerful tool for solving many modern machine learning problems. Existing gradient-based methods require second-order derivative approximations via Jacobian- or/and Hessian-vector computations. We propose a novel BO algorithm, which adopts Evolution Strategies (ES) based method to approximate the response Jacobian matrix in the hypergradient of BO.
  arXiv  Detail & Related papers  (2021-10-13T19:36:50Z)
• Fractal Structure and Generalization Properties of Stochastic Optimization Algorithms [71.62575565990502]
  We prove that the generalization error of an optimization algorithm can be bounded on the complexity' of the fractal structure that underlies its generalization measure. We further specialize our results to specific problems (e.g., linear/logistic regression, one hidden/layered neural networks) and algorithms.
  arXiv  Detail & Related papers  (2021-06-09T08:05:36Z)
• Population network structure impacts genetic algorithm optimisation performance [0.0]
  Genetic algorithm (GA) is a search method that optimises a population of solutions by simulating natural evolution. Social networks can condition the likelihood that two individuals mate. We introduce the Networked Genetic Algorithm (NGA) to evaluate how various random and scale-free population networks influence the optimisation performance of GAs.
  arXiv  Detail & Related papers  (2021-04-09T09:06:04Z)
• EOS: a Parallel, Self-Adaptive, Multi-Population Evolutionary Algorithm for Constrained Global Optimization [68.8204255655161]
  EOS is a global optimization algorithm for constrained and unconstrained problems of real-valued variables. It implements a number of improvements to the well-known Differential Evolution (DE) algorithm. Results prove that EOSis capable of achieving increased performance compared to state-of-the-art single-population self-adaptive DE algorithms.
  arXiv  Detail & Related papers  (2020-07-09T10:19:22Z)

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.