GARS

Yang Chen, Jinglu Hu, Kotaro Hirasawa, Songnian Yu2007 · DOI

TL;DR

This paper introduces GARS, a novel Genetic Algorithm (GA) designed to combat premature convergence and enhance global optimization. By reserving potentially valuable "building block" genetic material from less fit individuals and employing a uniqueness-based selection, GARS significantly improves solution quality and convergence speed on complex problems.

What Problem Does This Paper Address?

Genetic Algorithms (GAs) are powerful optimization tools inspired by natural evolution, widely used for complex problems with many local optima. However, a major hurdle in applying GAs to real-world, large-scale problems is "premature convergence." This occurs when the GA gets stuck in a suboptimal solution too early in the search process, often because the population loses diversity. The paper argues that this loss of diversity stems from the "survival of the fittest" principle, which can prematurely discard individuals that, while currently less fit, might hold crucial genetic information (building blocks) for future, better solutions. Existing methods to prevent this often come with significant drawbacks, such as increased computational cost or limited effectiveness.

Methods

The core innovation presented is the Genetic Algorithm with Reserve Selection (GARS). GARS modifies the standard GA selection process by segmenting the population into two parts:

  • Non-Reserved Area (NRA): This functions similarly to a conventional GA, focusing on exploiting good-quality individuals to quickly approach local optima.
  • Reserved Area (RA): This is the novel component. A portion of the population is specifically set aside to preserve individuals that might not be currently fit but could contain valuable "building blocks." These individuals are selected not based on their fitness, but on their uniqueness.

The uniqueness is measured using a modified "crowding distance" metric, which estimates how isolated an individual is within the fitness landscape. This ensures that even less fit individuals with distinct genetic profiles are retained. Furthermore, the genetic operators (crossover and mutation) are applied with higher probability (set to one) in the Reserved Area to encourage the activation of these potentially valuable building blocks in a new environment. The paper also details a flowchart illustrating the GARS process, highlighting the two-stage evolution of NRA and RA.

Datasets

The paper evaluates GARS on several standard benchmark problems:

  • Multimodal Function Optimization: Two specific functions, f(x) and g(x), are used to test the algorithm's ability to find global optima in landscapes with multiple minima/maxima.
  • Traveling Salesman Problem (TSP): Instances from the TSPLIB library (specifically tsp225, kroA200, and ch130) are used to evaluate performance on a classic combinatorial optimization problem.
  • Multiple Sequence Alignment (MSA): Biological sequences from the SRS database are used to assess GARS's effectiveness on a complex bioinformatics problem.

No new datasets were introduced; the focus was on applying GARS to existing, well-recognized benchmarks.

Key Insights and Ideas

  • The "Building Block" Dilemma: The paper compellingly argues that the "survival of the fittest" can be detrimental to global optimization by prematurely discarding potentially crucial genetic material.
  • Uniqueness as a Selection Criterion: Shifting selection from pure fitness to individual uniqueness in the reserved area is a clever way to maintain diversity and preserve underrepresented genetic information.
  • Two-Stage Evolution for Balance: The separation of the population into an exploitation-focused NRA and an exploration-focused RA allows for a better balance between convergence speed and global search.
  • Empirical Evidence for Robustness: The consistent improvements across diverse problem types (continuous optimization, combinatorial optimization, and bioinformatics) suggest GARS is a robust approach.

Key Results

GARS demonstrated significant improvements over conventional GAs:

  • Multimodal Function Optimization: GARS achieved much higher precision, with error rates of 1.69% and 0.40% compared to 14.14% and 7.79% for the conventional GA on the f(x) and g(x) functions, respectively.
  • Traveling Salesman Problem (TSP): GARS showed a performance improvement of 11.92%, 13.96%, and 15.71% over the conventional GA for the tested TSP instances.
  • Multiple Sequence Alignment (MSA): GARS converged more quickly and found better alignments, with a more stable convergence curve compared to the conventional GA. The paper also highlights a reduced gene loss in evolution after reservation.

Limitations and Future Work

  • Limitations: The paper acknowledges that the reserve size is a parameter that needs to be tuned. While GARS shows improved performance, the exact theoretical underpinnings of why building blocks are preserved and activated are left for future work.
  • Future Work: The authors propose several avenues:
  • Experimentally investigating the impact of different reserve sizes on performance.
  • Conducting a quantitative theoretical analysis of the building block hypothesis and GARS's mechanism.
  • Combining GARS with other effective optimization methods to create hybrid solutions.
  • Applying GARS to a wider range of complex problems.

Summary updated

Abstract

This paper investigates how genetic algorithms (GAs) can be improved to solve large-scale and complex problems more efficiently. First of all, we review premature convergence, one of the challenges confronted with when applying GAs to real-world problems. Next, some of the methods now available to prevent premature convergence and their intrinsic defects are discussed. A qualitative analysis is then done on the cause of premature convergence that is the loss of building blocks hosted in less-fit individuals during the course of evolution. Thus, we propose a new improver - GAs with Reserve Selection (GARS), where a reserved area is set up to save potential building blocks and a selection mechanism based on individual uniqueness is employed to activate the potentials. Finally, case studies are done in a few standard problems well known in the literature, where the experimental results demonstrate the effectiveness and robustness of GARS in suppressing premature convergence, and also an enhancement is found in global optimization capacity.
BibTeX
@misc{chen2007gars,
  author = {Yang Chen and Jinglu Hu and Kotaro Hirasawa and Songnian Yu},
  title = {{GARS}},
  year = {2007},
  doi = {10.1145/1276958.1277188},
}
Figure