# Optimization by Pairwise Linkage Detection, Incremental Linkage Set, and Restricted / Back Mixing: DSMGA-II

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2018.

## Built on by (most cited first, 9 of 9)

- [On Revealing the Hidden Problem Structure in Real-World and Theoretical Problems Using Walsh Coefficient Influence](https://mlsanity.com/paper/2504.13949/) (2025)
- [Availability of Perfect Decomposition in Statistical Linkage Learning for Unitation-based Function Concatenations](https://mlsanity.com/paper/2503.17397/) (2025)
- [Mining Potentially Explanatory Patterns via Partial Solutions](https://mlsanity.com/paper/2404.04388/) (2024)
- [Iterated Local Search with Linkage Learning](https://mlsanity.com/paper/2410.01583/) (2024)
- [Moving between high-quality optima using multi-satisfiability characteristics in hard-to-solve Max3Sat instances](https://mlsanity.com/paper/2504.11864/) (2025)
- [Seeking and leveraging alternative variable dependency concepts in gray-box-elusive bimodal land-use allocation problems](https://mlsanity.com/paper/2504.11882/) (2025)
- [A Memetic Algorithm based on Variational Autoencoder for Black-Box Discrete Optimization with Epistasis among Parameters](https://mlsanity.com/paper/2504.21338/) (2025)
- [Limited Perfect Monotonical Surrogates constructed using low-cost recursive linkage discovery with guaranteed output](https://mlsanity.com/paper/2604.11524/) (2026)
- [Obtaining Partition Crossover masks using Statistical Linkage Learning for solving noised optimization problems with hidden variable dependency structure](https://mlsanity.com/paper/2604.11862/) (2026)

## Abstract (arXiv)

This paper proposes a new evolutionary algorithm, called DSMGA-II, to efficiently solve optimization problems via exploiting problem substructures. The proposed algorithm adopts pairwise linkage detection and stores the information in the form of dependency structure matrix (DSM). A new linkage model, called the incremental linkage set, is then constructed by using the DSM. Inspired by the idea of optimal mixing, the restricted mixing and the back mixing are proposed. The former aims at efficient exploration under certain constrains. The latter aims at exploitation by refining the DSM so as to reduce unnecessary evaluations. Experimental results show that DSMGA-II outperforms LT-GOMEA and hBOA in terms of number of function evaluations on the concatenated/folded/cyclic trap problems, NK-landscape problems with various degrees of overlapping, 2D Ising spin-glass problems, and MAX-SAT. The investigation of performance comparison with P3 is also included.