Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel framework for genetic algorithms that integrates optimization-guided mutation and recombination operators, moving away from traditional random approaches. By formulating the optimization process as a query-complexity problem within the context of reinforcement learning, the authors demonstrate that certain optimization challenges necessitate the use of generation, mutation, and recombination to achieve solutions. The results reveal that while these advanced operators enhance solution quality, they also incur significantly higher computational costs, highlighting a trade-off between solution improvement and efficiency.
Optimization-guided genetic algorithms can significantly enhance solution quality, but at the cost of increased computational complexity.
Recent work in ML applies genetic algorithms at inference time to iteratively improve solutions to optimization problems. The basic mutation and recombination operators involved are qualitatively different from those studied classically. Mutations are no longer random; an ML algorithm mutates a solution with the goal of improving an objective. Similarly, recombination is not based on random collages of parent solutions. Instead, it is an ML optimization-based operator whose goal is to synthesize improved solutions from its inputs. Thus, these mutation and recombination operators are more likely to improve the objective, but their computational cost is much higher. We introduce a general model of genetic algorithms and formulating optimization in this model as a query-complexity problem, using the language of reinforcement learning. We then study specialized models. We show that some optimization problems require generation, mutation, and recombination to be solved. We then obtain qualitatively tight algorithms for a family of problems within this framework that captures the nontrivial role of diversity in the solution pool, a key feature of practical ML genetic algorithms.