1. Random walk’s correlation function for multi-objective NK landscapes and quadratic assignment problem
- Author
-
Madalina M. Drugan
- Subjects
Discrete mathematics ,Polynomial ,021103 operations research ,Control and Optimization ,Computational complexity theory ,Quadratic assignment problem ,Covariance matrix ,Applied Mathematics ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,Random walk ,01 natural sciences ,Computer Science Applications ,Computational Theory and Mathematics ,Correlation function ,010201 computation theory & mathematics ,Discrete Mathematics and Combinatorics ,Laplacian matrix ,Eigenvalues and eigenvectors ,Mathematics - Abstract
The random walk’ correlation matrix of multi-objective combinatorial optimization problems utilizes both local structure and general statistics of the objective functions. Reckoning time of correlation, or the random walk of lag 0, is quadratic in problem size L and number of objectives D. The computational complexity of the correlation coefficients of mNK is $$O(D^2 K^2 L)$$ , and of mQAP is $$O(D^2 L^2)$$ , where K is the number of interacting bits. To compute the random walk of a lag larger than 0, we employ a weighted graph Laplacian that associates a mutation operator with the difference in the objective function. We calculate the expected objective vector of a neighbourhood function and the eigenvalues of the corresponding transition matrix. The computational complexity of random walk’s correlation coefficients is polynomial with the problem size L and the number of objectives D. The computational effort of the random walks correlation coefficients of mNK is $$O(2^K L D^2)$$ , whereas of mQAP is $$O(L^6 D^2)$$ . Numerical examples demonstrate the utilization of these techniques.
- Published
- 2019