Random walk’s correlation function for multi-objective NK landscapes and quadratic assignment problem

Madalina M. Drugan ()
Additional contact information
Madalina M. Drugan: ITLearns.Online

Journal of Combinatorial Optimization, 2019, vol. 38, issue 4, No 14, 1213-1262

Abstract: 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)$$ O ( D 2 K 2 L ) , and of mQAP is $$O(D^2 L^2)$$ 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)$$ O ( 2 K L D 2 ) , whereas of mQAP is $$O(L^6 D^2)$$ O ( L 6 D 2 ) . Numerical examples demonstrate the utilization of these techniques.

Keywords: Random walk; Multi-objective optimization; Neighbourhood function; Graph Laplacian; Matrix theory (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-019-00445-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:38:y:2019:i:4:d:10.1007_s10878-019-00445-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-019-00445-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().