Convergence of simple genetic algorithms for the two-bit problem

Area of Science:

• Computer Science
• Computational Biology
• Optimization Theory

Background:

• Genetic algorithms (GAs) are powerful optimization tools inspired by natural biological systems.
• A key theoretical challenge in GAs is understanding GA-convergence: conditions for convergence and optimality of the converged point.

Purpose of the Study:

• To mathematically and rigorously solve GA-convergence issues for a simplified GA model.
• To analyze convergence conditions and the optimality of convergence points for the two-bit problem (TBP).

Main Methods:

• The study focuses on a simplified GA with natural selection and recombination operators.
• The optimization problem analyzed is the two-bit problem (TBP).
• Mathematical rigor is applied to derive theoretical results.

Main Results:

• Specific conditions for GA convergence on a single point were identified, aligning with prior experimental findings.
• Novel mathematical proof demonstrates whether the GA convergence point is optimal for the TBP.
• Results offer a foundation for generalizing to n-bit problems with mutation.

Conclusions:

• The paper provides a rigorous mathematical solution to fundamental GA-convergence problems for the TBP.
• The findings contribute new theoretical knowledge to both genetic algorithms and population genetics.
• This work paves the way for extending these solutions to more complex optimization problems.