Advertisement
Published in:
29-08-2019
Random walk’s correlation function for multi-objective NK landscapes and quadratic assignment problem
Published in: Journal of Combinatorial Optimization | Issue 4/2019
Log inActivate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.