Ordering and Visualisation of Many-objective Populations
Walker, David J.
Thesis or dissertation
University of Exeter
In many everyday tasks it is necessary to compare the performance of the individuals in a population described by two or more criteria, for example comparing products in order to decide which is the best to purchase in terms of price and quality. Other examples are the comparison of universities, countries, the infrastructure in a telecommunications network, and the candidate solutions to a multi- or many-objective problem. In all of these cases, visualising the individuals better allows a decision maker to interpret their relative performance. This thesis explores methods for understanding and visualising multi- and many-criterion populations. Since people cannot generally comprehend more than three spatial dimensions the visualisation of many-criterion populations is a non-trivial task. We address this by generating visualisations based on the dominance relation which defines a structure in the population and we introduce two novel visualisation methods. The first method explicitly illustrates the dominance relationships between individuals as a graph in which individuals are sorted into Pareto shells, and is enhanced using many-criterion ranking methods to produce a finer ordering of individuals. We extend the power index, a method for ranking according to a single criterion, into the many-criterion domain by defining individual quality in terms of tournaments. The second visualisation method uses a new dominance-based distance in conjunction with multi-dimensional scaling, and we show that dominance can be used to identify an intuitive low-dimensional mapping of individuals, placing similar individuals close together. We demonstrate that this method can visualise a population comprising a large number of criteria. Heatmaps are another common method for presenting high-dimensional data, however they suffer from a drawback of being difficult to interpret if dissimilar individuals are placed close to each other. We apply spectral seriation to produce an ordering of individuals and criteria by which the heatmap is arranged, placing similar individuals and criteria close together. A basic version, computing similarity with the Euclidean distance, is demonstrated, before rank-based alternatives are investigated. The procedure is extended to seriate both the parameter and objective spaces of a multi-objective population in two stages. Since this process describes a trade-off, favouring the ordering of individuals in one space or the other, we demonstrate methods that enhance the visualisation by using an evolutionary optimiser to tune the orderings. One way of revealing the structure of a population is by highlighting which individuals are extreme. To this end, we provide three definitions of the “edge” of a multi-criterion mutually non-dominating population. All three of the definitions are in terms of dominance, and we show that one of them can be extended to cope with many-criterion populations. Because they can be difficult to visualise, it is often difficult for a decision maker to comprehend a population consisting of a large number of criteria. We therefore consider criterion selection methods to reduce the dimensionality with a view to preserving the structure of the population as quantified by its rank order. We investigate the efficacy of greedy, hill-climber and evolutionary algorithms and cast the dimension reduction as a multi-objective problem.
David J. Walker, Richard M. Everson, and Jonathan E. Fieldsend. Visualisation and ordering of many-objective populations. In IEEE Congress on Evolutionary Computation (CEC 2010), pages 3664–3671, CCIB, Barcelona, Spain, July 2010.
D. J. Walker, R. M. Everson, and J. E. Fieldsend. Ordering multi-objective populations with the power index. In 2010 Postgraduate Conference for Computing: Applications and Theory (PCCAT 2010), pages 12–18, Exeter, Devon, UK, June 2010. University of Exeter.
D. J. Walker, R. M. Everson, and J. E. Fieldsend. Rank-based dimension reduction for many-criteria populations. In Proceedings of the 13th annual conference on Genetic and evolutionary computation, GECCO ’11, pages 107–108, New York, NY, USA, 2011. ACM.
K. McClymont, D. Walker, E. Keedwell, R. Everson, J. Fieldsend, D. Savic, and M. Randall-Smith. Novel methods for ranking district metered areas for water distribution network maintenance scheduling. In CCWI 2011, Exeter, 2011.
D. J. Walker, R. M. Everson, and J. E. Fieldsend. Visualising many-objective populations. In Proceedings of the 3rd Workshop on Visualisation in Genetic and Evolutionary Computation (VizGEC 2012) at GECCO 2012, Philadelphia, 2012.
D. J. Walker, R. M. Everson, and J. E. Fieldsend. Visualising Mutually Non-dominating Solution Sets in Many-objective Optimisation. IEEE Transactions on Evolutionary Computation, (in press).
R. M. Everson, D. J. Walker, and J. E. Fieldsend. Edges of Mutually Non-dominating Sets In Proceedings of the 15th annual conference on Genetic and evolutionary computation, GECCO ’13, (in press), New York, NY, USA, 2013. ACM.
Fieldsend, Jonathan E.
Everson, Richard M.
PhD in Computer Science