Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Optimization Landscapes: A Topological Approach to Understanding Permutation-based Optimization Problems
KTH, School of Computer Science and Communication (CSC), Computational Science and Technology (CST).
Aalto University.
KTH, School of Computer Science and Communication (CSC), Computational Science and Technology (CST).ORCID iD: 0000-0002-1498-9062
(English)Manuscript (preprint) (Other academic)
Abstract [en]

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.

National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-193729OAI: oai:DiVA.org:kth-193729DiVA: diva2:1033961
Note

QC 20161011

Available from: 2016-10-10 Created: 2016-10-10 Last updated: 2016-10-11Bibliographically approved
In thesis
1. Visual Analysis of Multidimensional Data for Biomechanics and HCI
Open this publication in new window or tab >>Visual Analysis of Multidimensional Data for Biomechanics and HCI
2016 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Multidimensional analysis is performed in many scientific fields.Its main tasks involve the identification of correlations between data dimensions,the investigation of data clusters, and the identification of outliers. Visualization techniques often help in getting a better understanding. In this thesis, we present our work on improving visual multidimensional analysis by exploiting the semantics of the data and enhancing the perception of existing visualizations. Firstly, we exploit the semantics of the data by creating new visualizations which present visual encodings specifically tailoredto the analyzed dimensions. We consider the resulting visual analysis to be more intuitive for the user asit provides a more easily understandable idea of the data. In this thesis we concentrate on the visual analysis of multidimensional biomechanical data for Human-Computer Interaction (HCI).To this end, we present new visualizations tackling the specific features of different aspectsof biomechanical data such as movement ergonomics, leading to a more intuitive analysis. Moreover, by integrating drawings or sketches of the physical setup of a case study as new visualizations, we allow for a fast and effective case-specific analysis. The creation of additional visualizations for communicating trends of clusters of movements enables a cluster-specific analysis which improves our understanding of postures and muscular co-activation.Moreover, we create a new visualization which addresses the specificity of the multidimensional data related to permutation-based optimization problems. Each permutation of a given set of n elements represents a point defined in an n-dimensional space. Our method approximates the topologyof the problem-related optimization landscape inferring the minima basins and their properties and visualizing them organized in a quasi-landscape. We show the variability of the solutions in a basin using heat maps generated from permutation matrices.Furthermore, we continue improving our visual multidimensional analysis by enhancing the perceptual encoding of existing well-known multidimensional visualizations. We focus on Parallel Coordinates Plots (PCP) and its derivative Continuous Parallel Coordinates (CPC). The main perceptual issues of PCP are visual clutter and overplotting which hamper the recognition of patterns in large data sets. In this thesis, we present an edge-bundling method for PCP which uses density-based clustering for each dimension. This reduces clutter and provides a faster overview of clusters and trends. Moreover, it allows for a fast rendering of the clustered lines using polygons. Furthermore, we present the first bundling approach for Continuous Parallel Coordinates where classic edge-bundling fails due to the absence of lines. Our method performs a deformation of the visualization space of CPC leading to similar results as those obtained through classic edge-bundling.Our work involved 10 HCI case studies and helped to establisha new research methodology in this field. This led to publications in internationally peer-reviewed journals and conference proceedings.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2016. 60 p.
Series
TRITA-CSC-A, ISSN 1653-5723 ; 2016:27
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-193713 (URN)978-91-7729-154-1 (ISBN)
Public defence
2016-11-17, VIC Visualization Studio, Lindstedtsvägen 7, floor 4, room 4450., Stockholm, 11:36 (English)
Opponent
Supervisors
Note

QC 20161011

Available from: 2016-10-11 Created: 2016-10-10 Last updated: 2016-10-11Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Palmas, GregorioWeinkauf, Tino
By organisation
Computational Science and Technology (CST)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 137 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf