# Quadratic speedup of global search using a biased crossover of two good solutions

arXiv: https://arxiv.org/abs/2111.07680 · HTML: https://mlsanity.com/paper/2111.07680/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 59 references that are in the map.
- First posted on arXiv 15 Nov 2021.

## Builds on (most cited first, 5 of 5)

- [Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm](https://mlsanity.com/paper/1712.01815/) (2017)
- [Deep Neuroevolution: Genetic Algorithms Are a Competitive Alternative for Training Deep Neural Networks for Reinforcement Learning](https://mlsanity.com/paper/1712.06567/) (2017)
- [Deep Reinforcement Learning using Genetic Algorithm for Parameter Optimization](https://mlsanity.com/paper/1905.04100/) (2019)
- [Dimensionality reduction to maximize prediction generalization capability](https://mlsanity.com/paper/2003.00470/) (2020)
- [On the achievability of blind source separation for high-dimensional nonlinear source mixtures](https://mlsanity.com/paper/1808.00668/) (2018)

## Abstract (arXiv)

The minimisation of cost functions is crucial in various optimisation fields. However, identifying their global minimum remains challenging owing to the huge computational cost incurred. This work analytically expresses the computational cost to identify an approximate global minimum for a class of cost functions defined under a high-dimensional discrete state space. Then, we derive an optimal global search scheme that minimises the computational cost. Mathematical analyses demonstrate that a combination of the gradient descent algorithm and the selection and crossover algorithm--with a biased crossover weight--maximises the search efficiency. Remarkably, its computational cost is of the square root order in contrast to that of the conventional gradient descent algorithms, indicating a quadratic speedup of global search. We corroborate this proposition using numerical analyses of the travelling salesman problem. The simple computational architecture and minimal computational cost of the proposed scheme are highly desirable for biological organisms and neuromorphic hardware.