Maintaining Diversity in Genetic Search

Michael L. MauldinAAAI 1984

Abstract

This paper addresses the "premature convergence" problem in genetic algorithms (GAs), where populations become too homogeneous and stall in local optima. We introduce a "k-bit decreasing uniqueness" constraint that requires new individuals to maintain a minimum Hamming distance from the existing population. Experimental results on DeJong’s benchmark functions show that this mechanism prevents stagnation and significantly improves global search performance, particularly when combined with traditional crowding factors.

Introduction

Genetic Algorithms (GAs) are robust optimization tools inspired by natural selection. However, their effectiveness is often limited by premature convergence. When a few high-fitness individuals dominate the population early in the search, the gene pool loses diversity. Since crossover—the primary search operator—relies on combining different genetic material, a homogeneous population causes the search to stall. While mutation can reintroduce variety, it is often insufficient to escape deep local optima.

Methods: The Uniqueness Constraint

To combat this, we propose a k-bit decreasing uniqueness constraint. This mechanism acts as a filter for new offspring:

  1. Hamming Distance Check: Every new individual is compared against the current population. If its Hamming distance (the number of differing bit positions) to any existing member is less than a threshold $k$, it is rejected or mutated.
  2. Linear Decay: To allow the algorithm to transition from broad exploration to fine-grained exploitation, $k$ starts high (sampling the space on a coarse grid) and decreases linearly to 1 bit over the course of the trials.

This approach was compared against standard GA (Holland’s $R_1$), DeJong’s Crowding Factor, random search, and hill-climbing.

Experimental Results

The algorithms were evaluated using DeJong’s five test functions, covering challenges such as multi-modality, noise, and high dimensionality. Each configuration was tested over 5,000 trials.

Performance comparison of search algorithms over 5,000 trials.

As illustrated in Figure 1, the standard GA ($R_1$) improves rapidly at first but plateaus around 1,000 trials. In contrast, the uniqueness-based methods (u4, u8, u12) continue to find better solutions throughout the entire run. The 12-bit uniqueness constraint (u12) achieved the most significant depth in search, effectively avoiding the local traps that caught the baseline methods.

Global performance metrics across on-line, off-line, and best-found solutions.

The quantitative summary in Figure 2 highlights the trade-offs involved. Maintaining diversity improves off-line performance (the best solution found) but can degrade on-line performance (the average fitness of all trials) because the algorithm is forced to explore less optimal regions. For instance, Uniqueness 12 bits achieved a "Best" score of -5.267 compared to Holland $R_1$’s -0.207. Interestingly, the hybrid "Crowding 4 + Uniq 12" approach offered a compelling middle ground, achieving a strong "Best" score of -5.046 while maintaining a much better "On-line" average (9.447) than the pure 12-bit uniqueness method (50.447).

Conclusion

The decreasing uniqueness constraint effectively manages the exploration-exploitation trade-off in genetic search. By explicitly preventing premature convergence, it allows GAs to navigate complex, multi-modal landscapes that trap traditional methods. Future work will explore the application of this constraint to real-valued representations using Euclidean distance and its utility in dynamic, time-varying environments.

Summary updated

BibTeX
@inproceedings{mauldin1984maintaining,
  author = {Michael L. Mauldin},
  title = {{Maintaining Diversity in Genetic Search}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1984},
}
Figure