GARA: A novel approach to Improve Genetic Algorithms' Accuracy and Efficiency by Utilizing Relationships among Genes

Zhaoning Shi, Meng Xiang, Zhaoyang Hai, Xiabi Liu, Yan PeiarXiv 2024 · arXiv · OpenReview

Abstract

Genetic algorithms have played an important role in engineering optimization. Traditional GAs treat each gene separately. However, biophysical studies of gene regulatory networks revealed direct associations between different genes. It inspires us to propose an improvement to GA in this paper, Gene Regulatory Genetic Algorithm (GRGA), which, to our best knowledge, is the first time to utilize relationships among genes for improving GA's accuracy and efficiency. We design a directed multipartite graph encapsulating the solution space, called RGGR, where each node corresponds to a gene in the solution and the edge represents the relationship between adjacent nodes. The edge's weight reflects the relationship degree and is updated based on the idea that the edges' weights in a complete chain as candidate solution with acceptable or unacceptable performance should be strengthened or reduced, respectively. The obtained RGGR is then employed to determine appropriate loci of crossover and mutation operators, thereby directing the evolutionary process toward faster and better convergence. We analyze and validate our proposed GRGA approach in a single-objective multimodal optimization problem, and further test it on three types of applications, including feature selection, text summarization, and dimensionality reduction. Results illustrate that our GARA is effective and promising.

Introduction

In a standard Genetic Algorithm (GA), the "loci" (positions) for crossover and mutation are typically chosen at random. While this promotes diversity, it ignores a fundamental biological reality: genes rarely work in isolation. In nature, genes exist in complex regulatory networks where one gene might trigger another, or a sequence of enzymes must act in a specific order to produce a result, such as the synthesis of adrenaline from L-Tyrosine.

Biological inspiration: gene regulation in flower development and the metabolic pathway for adrenaline synthesis.

When a traditional GA randomly cuts a high-performing "chromosome," it often disrupts these local interactive sequences, effectively destroying the "building blocks" of a good solution. This leads to inefficient searches, as the algorithm must repeatedly rediscover beneficial combinations it previously broke apart. The Gene Regulatory Genetic Algorithm (GRGA) bridges this gap by incorporating bio-inspired gene relationships into the mathematical framework of GAs.

Methodology: The Gene Regulatory Genetic Algorithm (GRGA)

The core innovation of this work is the Relationship Graph representing Gene Regulation (RGGR). This structure models the solution space as a directed multipartite graph where each node represents a possible gene value at a specific position, and the edges represent the relationship between adjacent genes.

The GRGA process overview, showing how individuals are mapped to the RGGR to guide crossover and mutation.

Dynamic Weighting and Guided Operators

Unlike a static graph, the RGGR "learns" during the evolutionary process. If an individual solution has high fitness, the weights of the edges (gene-to-gene transitions) within that individual are increased. Conversely, if fitness is low, the weights are decreased. This weighting system then guides the genetic operators:

  • Crossover: Instead of a random midpoint, the algorithm calculates a selection probability for each locus based on the RGGR. It prefers to "cut" at points where the gene relationships are weakest, preserving strong functional blocks.
  • Mutation: Mutation is directed toward gene positions that have weak correlations with their neighbors, rather than changing genes that are already part of a "proven" sequence.

To maintain computational efficiency, the authors employ a first-order Markov assumption, meaning a gene's fitness contribution is primarily influenced by its immediate predecessor in the sequence.

Experimental Results

The authors validated GRGA across four distinct domains: synthetic optimization (Shubert function), feature selection, text summarization (DUC 2005/2007), and dimensionality reduction (UCI datasets).

  • Faster Convergence: On the Shubert function, GRGA began significantly outperforming standard GAs after just 10 generations, reaching higher final fitness levels.
  • Efficiency Gains: In feature selection tasks, GRGA-enhanced algorithms were 32.19% faster than their predecessors while maintaining or slightly improving accuracy.
  • Superior Summarization: On the DUC datasets, GRGA improved average ROUGE scores by approximately 0.5% and converged to high-accuracy solutions much faster than the baseline.
  • Broad Applicability: In dimensionality reduction tests, the GRGA-enhanced model outperformed the standard GDR algorithm in over 66% of the tested datasets.

Conclusion and Future Work

GRGA represents a significant shift from treating chromosomes as a "bag of genes" to treating them as "regulatory networks." By utilizing a self-organizing guidance system (the RGGR), the algorithm autonomously identifies and protects local structures that work well.

The primary limitation is the current first-order Markov assumption. Future work will explore extending the RGGR to consider relationships between non-adjacent genes (higher-order Markov chains) and developing more native handling for continuous variables within the framework.

Summary updated

Abstract

Genetic algorithms have played an important role in engineering optimization. Traditional GAs treat each gene separately. However, biophysical studies of gene regulatory networks revealed direct associations between different genes. It inspires us to propose an improvement to GA in this paper, Gene Regulatory Genetic Algorithm (GRGA), which, to our best knowledge, is the first time to utilize relationships among genes for improving GA's accuracy and efficiency. We design a directed multipartite graph encapsulating the solution space, called RGGR, where each node corresponds to a gene in the solution and the edge represents the relationship between adjacent nodes. The edge's weight reflects the relationship degree and is updated based on the idea that the edges' weights in a complete chain as candidate solution with acceptable or unacceptable performance should be strengthened or reduced, respectively. The obtained RGGR is then employed to determine appropriate loci of crossover and mutation operators, thereby directing the evolutionary process toward faster and better convergence. We analyze and validate our proposed GRGA approach in a single-objective multimodal optimization problem, and further test it on three types of applications, including feature selection, text summarization, and dimensionality reduction. Results illustrate that our GARA is effective and promising.
BibTeX
@misc{shi2024gara,
  author = {Zhaoning Shi and Meng Xiang and Zhaoyang Hai and Xiabi Liu and Yan Pei},
  title = {{GARA: A novel approach to Improve Genetic Algorithms' Accuracy and Efficiency by Utilizing Relationships among Genes}},
  year = {2024},
  eprint = {2404.18955},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2404.18955},
}
Figure