Optimization Landscapes: A Topological Approach to Understanding Permutation-based Optimization Problems
(English)Manuscript (preprint) (Other academic)
Permutation-based optimization problemsare a class of NP-hard combinatorial problemsrepresenting many challenges in theory and practice.Their solution spaceconsists of all permutations $n!$of a given set of $n$ elements.Hence, for many real-world problemsthe solution spaceis too largeto even just visit every solution.The quality of a solutionis described by an objective function.A good understandingof the structures and symmetriesin this data is requiredto develop and steer heuristic algorithmsand other approaches to solving the underlying problem.We present a novel topological approachto exploring the objective functionsof permutation-based optimization problems.We infer the minima basinsand their propertiesfrom descending optimization paths.To deal with noise and general oversegmentation,we introduce an approachinspired by topological simplification of scalar fields.Based on this,we construct an edge-weighted graphapproximating the distances between basins,and visualize it using a force-directed layout,which shows the basins of local and global optimaorganized in a quasi-landscape.We show the variabilityof the solutions in a basinusing heat maps generated from permutation matrices.Our method is designed to be interactiveand read its input data as a streamfrom a simultaneously running simulation.We evaluate our method using different optimization problemsfrom both theory and practice.
IdentifiersURN: urn:nbn:se:kth:diva-193729OAI: oai:DiVA.org:kth-193729DiVA: diva2:1033961
QC 201610112016-10-102016-10-102016-10-11Bibliographically approved