Mathematical perspective on genetic algorithms with optimization guided operators

• URL: http://arxiv.org/abs/2606.12279v1
• Date: Wed, 10 Jun 2026 16:18:36 GMT
• Title: Mathematical perspective on genetic algorithms with optimization guided operators
• Abstract summary: Recent work in ML applies genetic algorithms at inference time to iteratively improve solutions to optimization problems.<n>We introduce a general model of genetic algorithms and formulating optimization in this model as a query-complexity problem.<n>We show that some optimization problems require generation, mutation, and recombination to be solved.
• Score: 11.520406711750757
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Learnable Evolutionary Multi-Objective Combinatorial Optimization via Sequence-to-Sequence Model [43.53359509358102]
  SeqMO is a learnable multi-objective optimization method that integrates sequence-to-sequence models with evolutionary algorithms.<n>Our approach divides approximate solution sets based on objective values' distance to the Pareto front, and establishes mapping relationships between solutions by minimizing objective vector angles in the target space.<n> Experiments on the multi-objective travel salesman problem and the multi-objective assignment problem verify the effectiveness of the algorithm.
  arXiv  Detail & Related papers  (2024-12-09T01:46:58Z)
• Genetic Engineering Algorithm (GEA): An Efficient Metaheuristic Algorithm for Solving Combinatorial Optimization Problems [1.8434042562191815]
  Genetic Algorithms (GAs) are known for their efficiency in solving optimization problems. This paper proposes a new metaheuristic algorithm called the Genetic Engineering Algorithm (GEA) that draws inspiration from genetic engineering concepts.
  arXiv  Detail & Related papers  (2023-09-28T13:05:30Z)
• Polynomial-time Solver of Tridiagonal QUBO, QUDO and Tensor QUDO problems with Tensor Networks [41.94295877935867]
  We present a quantum-inspired tensor network algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization problems.<n>We also solve the more general quadratic unconstrained discrete optimization problems with one-neighbor interactions in a lineal chain.
  arXiv  Detail & Related papers  (2023-09-19T10:45:15Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Discovering Attention-Based Genetic Algorithms via Meta-Black-Box Optimization [13.131971623143622]
  We discover entirely new genetic algorithms in a data-driven fashion. We parametrize selection and mutation rate adaptation as cross- and self-attention modules. The learned algorithm can be applied to previously unseen optimization problems, search dimensions & evaluation budgets.
  arXiv  Detail & Related papers  (2023-04-08T12:14:15Z)
• On a class of geodesically convex optimization problems solved via Euclidean MM methods [50.428784381385164]
  We show how a difference of Euclidean convexization functions can be written as a difference of different types of problems in statistics and machine learning. Ultimately, we helps the broader broader the broader the broader the broader the work.
  arXiv  Detail & Related papers  (2022-06-22T23:57:40Z)
• Neural Improvement Heuristics for Graph Combinatorial Optimization Problems [49.85111302670361]
  We introduce a novel Neural Improvement (NI) model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each.
  arXiv  Detail & Related papers  (2022-06-01T10:35:29Z)
• Optimizer Amalgamation [124.33523126363728]
  We are motivated to study a new problem named Amalgamation: how can we best combine a pool of "teacher" amalgamations into a single "student" that can have stronger problem-specific performance? First, we define three differentiable mechanisms to amalgamate a pool of analyticals by gradient descent. In order to reduce variance of the process, we also explore methods to stabilize the process by perturbing the target.
  arXiv  Detail & Related papers  (2022-03-12T16:07:57Z)
• Enhanced Innovized Repair Operator for Evolutionary Multi- and Many-objective Optimization [5.885238773559015]
  "Innovization" is a task of learning common relationships among some or all of the Pareto-optimal (PO) solutions in optimisation problems. Recent studies have shown that a chronological sequence of non-dominated solutions also possess salient patterns that can be used to learn problem features. We propose a machine-learning- (ML-) assisted modelling approach that learns the modifications in design variables needed to advance population members towards the Pareto-optimal set.
  arXiv  Detail & Related papers  (2020-11-21T10:29:15Z)
• AdaLead: A simple and robust adaptive greedy search algorithm for sequence design [55.41644538483948]
  We develop an easy-to-directed, scalable, and robust evolutionary greedy algorithm (AdaLead) AdaLead is a remarkably strong benchmark that out-competes more complex state of the art approaches in a variety of biologically motivated sequence design challenges.
  arXiv  Detail & Related papers  (2020-10-05T16:40:38Z)
• Genetic optimization algorithms applied toward mission computability models [0.3655021726150368]
  Genetic algorithms are computations based and low cost to compute. We describe our genetic optimization algorithms to a mission-critical and constraints-aware problem.
  arXiv  Detail & Related papers  (2020-05-27T00:45:24Z)
• Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem [0.0]
  This paper characterizes and discusses devolutionary genetic algorithms and evaluates their performances in solving the minimum labeling Steiner tree (MLST) problem. We define devolutionary algorithms as the process of reaching a feasible solution by devolving a population of super-optimal unfeasible solutions over time. We show how classical evolutionary concepts, such as crossing, mutation and fitness can be adapted to aim at reaching an optimal or close-to-optimal solution.
  arXiv  Detail & Related papers  (2020-04-18T13:27:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.