Abstract
Estimation of Distribution Algorithms (EDAs) for permutation-based combinatorial optimization have traditionally relied on probability models designed for ordering and ranking problems. However, these models often fail to capture the structural nuances of matching and assignment problems, such as the Quadratic Assignment Problem (QAP). This paper introduces a novel approach using Doubly Stochastic Matrices (DSMs) as the underlying probability model. By leveraging the Birkhoff-von Neumann theorem, the proposed DSM-PS algorithm treats permutations as matrices rather than sequences. Experimental results on the QAPLIB benchmark suite demonstrate that DSM-PS significantly outperforms state-of-the-art order-based models in terms of accuracy and convergence.
Introduction
In the field of combinatorial optimization, permutation problems are generally categorized into two distinct types: ordering (ranking) problems and matching (assignment) problems. Ordering problems, such as job scheduling, involve finding an optimal sequence. In contrast, matching problems, such as the Quadratic Assignment Problem (QAP), involve pairing elements from two sets—for example, assigning $n$ facilities to $n$ locations.
Despite this distinction, most existing evolutionary algorithms, particularly Estimation of Distribution Algorithms (EDAs), utilize probability models like the Plackett-Luce or Mallows models. These models are mathematically biased toward finding a "consensus ranking," assuming an inherent best position for each item. In matching problems, however, there is no natural sequence; the relationship is spatial and relational. This paper addresses this structural mismatch by proposing the use of Doubly Stochastic Matrices (DSMs) to represent the search space in EDAs.
Methodology
The DSM Representation
A Doubly Stochastic Matrix is a square matrix where every row and every column sums to 1.0. The authors' approach is grounded in the Birkhoff-von Neumann theorem, which states that any DSM can be expressed as a convex combination (a weighted average) of permutation matrices. This allows the DSM to serve as a continuous proxy for the discrete set of all possible permutations, providing a more flexible and accurate representation for assignment-based search spaces.
Learning and Smoothing
To integrate DSMs into the EDA framework, the authors developed a smoothed learning process. Rather than simply averaging the best-performing permutations found in a generation—which could lead to "zero probability" for unobserved but potentially optimal assignments—the algorithm incorporates a smoothing factor ($\alpha$). This adds a small amount of uniform noise to the matrix, ensuring the algorithm maintains sufficient exploration and avoids premature convergence.
Sampling Strategies
Transforming a continuous DSM back into a discrete permutation is a critical step. The authors evaluated three distinct sampling strategies:
- Probabilistic Sampling (PS): A stochastic method that selects rows and columns based on their respective weights.
- Algebraic Sampling (AS): A faster method utilizing matrix-vector multiplication and random keys to project the DSM onto a permutation.
- Geometric Sampling (GS): A method based on the Birkhoff decomposition of the matrix into its constituent permutations.
Experimental Results
The researchers evaluated the DSM-based EDAs using 12 instances from the Taillard set in the QAPLIB library, with problem sizes ranging from $n=15$ to $n=100$. These benchmarks are widely regarded as some of the most challenging instances of the Quadratic Assignment Problem.
Performance Comparison
The DSM-PS algorithm was compared against three state-of-the-art competitors: Mallows-Cayley, Mallows-Kendall, and Plackett-Luce models. The results were definitive:
- Accuracy: DSM-PS achieved the lowest Median Relative Deviation (MRD) across all 12 benchmark instances. In several cases, the accuracy of DSM-PS was double that of the next best competitor.
- Statistical Significance: Bayesian performance analysis indicated a nearly 100% probability that DSM-PS is the superior algorithm for these matching-type problems.
- Convergence Behavior: While traditional EDAs often struggled to converge or became trapped in local optima, visual analysis confirmed that DSM-PS progressively refined its samples toward high-quality solutions over time.
Discussion and Insights
The primary insight of this research is that representation is paramount. By treating permutations as matrices rather than vectors, the DSM model preserves the essential item-to-position relationships of assignment problems without imposing an artificial sequence. Among the sampling methods, Probabilistic Sampling (PS) proved most effective, as it more accurately captures the complex probability distribution inherent in the DSM compared to the faster but less precise Algebraic Sampling.
Limitations
Despite its superior accuracy, the DSM approach faces computational challenges. The current implementation is significantly slower than traditional models, partly due to the $O(n^2)$ complexity of the PS sampling method and the overhead of matrix operations. Additionally, the algorithm's performance is sensitive to the smoothing factor and selection pressure, which currently require heuristic tuning.
Conclusion
This paper demonstrates that Doubly Stochastic Matrices provide a powerful and theoretically sound framework for solving matching-based permutation problems. The DSM-PS algorithm sets a new benchmark for accuracy on QAP instances. Future work will focus on optimizing the computational efficiency of matrix sampling and exploring the application of DSMs as probabilistic crossover operators in standard Genetic Algorithms.
Summary updated