Population network structure impacts genetic algorithm optimisation performance

• URL: http://arxiv.org/abs/2104.04254v1
• Date: Fri, 9 Apr 2021 09:06:04 GMT
• Title: Population network structure impacts genetic algorithm optimisation performance
• Authors: Aymeric Vie
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A genetic algorithm (GA) is a search method that optimises a population of solutions by simulating natural evolution. Good solutions reproduce together to create better candidates. The standard GA assumes that any two solutions can mate. However, in nature and social contexts, social networks can condition the likelihood that two individuals mate. This impact of population network structure over GAs performance is unknown. Here we introduce the Networked Genetic Algorithm (NGA) to evaluate how various random and scale-free population networks influence the optimisation performance of GAs on benchmark functions. We show evidence of significant variations in performance of the NGA as the network varies. In addition, we find that the best-performing population networks, characterised by intermediate density and low average shortest path length, significantly outperform the standard complete network GA. These results may constitute a starting point for network tuning and network control: seeing the network structure of the population as a parameter that can be tuned to improve the performance of evolutionary algorithms, and offer more realistic modelling of social learning.

Related papers

• RW-NSGCN: A Robust Approach to Structural Attacks via Negative Sampling [10.124585385676376]
  Graph Neural Networks (GNNs) have been widely applied in various practical scenarios, such as predicting user interests and detecting communities in social networks. Recent studies have shown that graph-structured networks often contain potential noise and attacks, in the form of topological perturbations and weight disturbances. We propose a novel method: Random Walk Negative Sampling Graph Conal Network (RW-NSGCN). Specifically, RW-NSGCN integrates the Random Walk with Restart (RWR) and PageRank algorithms for negative sampling and employs a Determinantal Point Process (DPP)-based GCN for convolution operations.
  arXiv  Detail & Related papers  (2024-08-13T06:34:56Z)
• MAGNOLIA: Matching Algorithms via GNNs for Online Value-to-go Approximation [48.32178376038614]
  We introduce a graph neural network (GNN) approach that emulates the problem'sly-complex optimal online algorithm. We show empirically that this GNN returns high-weight matchings across a variety of tasks.
  arXiv  Detail & Related papers  (2024-06-10T01:39:04Z)
• Simulation-based optimization of a production system topology -- a neural network-assisted genetic algorithm [0.0]
  A novel approach is presented for topology optimization of production systems using a genetic algorithm (GA) An extension to the GA is presented in which a neural network functions as a surrogate model for simulation. Both approaches are effective at finding the optimal solution in industrial settings.
  arXiv  Detail & Related papers  (2024-02-02T15:52:10Z)
• Improving genetic algorithms performance via deterministic population shrinkage [9.334663477968027]
  This paper presents an empirical study on the possible benefits of a Simple Variable Population Sizing scheme on the performance of Genetic Algorithms (GAs) It consists in decreasing the population for a GA run following a predetermined schedule, configured by a speed and a severity parameter. Results show several combinations of speed-severity where SVPS-GA preserves the solution quality while improving performances, by reducing the number of evaluations needed for success.
  arXiv  Detail & Related papers  (2024-01-22T17:05:16Z)
• Degree-based stratification of nodes in Graph Neural Networks [66.17149106033126]
  We modify the Graph Neural Network (GNN) architecture so that the weight matrices are learned, separately, for the nodes in each group. This simple-to-implement modification seems to improve performance across datasets and GNN methods.
  arXiv  Detail & Related papers  (2023-12-16T14:09:23Z)
• 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)
• Multi-agent Reinforcement Learning with Graph Q-Networks for Antenna Tuning [60.94661435297309]
  The scale of mobile networks makes it challenging to optimize antenna parameters using manual intervention or hand-engineered strategies. We propose a new multi-agent reinforcement learning algorithm to optimize mobile network configurations globally. We empirically demonstrate the performance of the algorithm on an antenna tilt tuning problem and a joint tilt and power control problem in a simulated environment.
  arXiv  Detail & Related papers  (2023-01-20T17:06:34Z)
• Relation Embedding based Graph Neural Networks for Handling Heterogeneous Graph [58.99478502486377]
  We propose a simple yet efficient framework to make the homogeneous GNNs have adequate ability to handle heterogeneous graphs. Specifically, we propose Relation Embedding based Graph Neural Networks (RE-GNNs), which employ only one parameter per relation to embed the importance of edge type relations and self-loop connections.
  arXiv  Detail & Related papers  (2022-09-23T05:24:18Z)
• Genetic-algorithm-optimized neural networks for gravitational wave classification [0.0]
  We propose a new method for hyperparameter optimization based on genetic algorithms (GAs) We show that the GA can discover high-quality architectures when the initial hyper parameter seed values are far from a good solution. Using genetic algorithm optimization to refine an existing network should be especially useful if the problem context changes.
  arXiv  Detail & Related papers  (2020-10-09T03:14:20Z)
• Policy-GNN: Aggregation Optimization for Graph Neural Networks [60.50932472042379]
  Graph neural networks (GNNs) aim to model the local graph structures and capture the hierarchical patterns by aggregating the information from neighbors. It is a challenging task to develop an effective aggregation strategy for each node, given complex graphs and sparse features. We propose Policy-GNN, a meta-policy framework that models the sampling procedure and message passing of GNNs into a combined learning process.
  arXiv  Detail & Related papers  (2020-06-26T17:03:06Z)

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.