Meta-Optimisation of Migration Topologies in Multi-Objective Evolutionary Algorithms

Erlank, J. (2007). Meta-Optimisation of Migration Topologies in Multi-Objective Evolutionary Algorithms. Student dissertation for The Open University module M801 MSc in Software Development Research Dissertation.

DOI: https://doi.org/10.21954/ou.ro.0001605d

Abstract

Multi-objective evolutionary algorithms use a population-based approach and the principles of evolution to find Pareto-optimal solutions to problems with multiple competing objectives. Unlike single-objective problems, in which there is often only one optimal solution (for example a global minimum for a given function), a multi-objective problem will have a set of Pareto-optimal solutions, all of which are equally optimal in the sense that they represent different trade-offs between competing objectives; and therefore no one solution can be said to be the best. Evolutionary algorithms (whether single- or multi-objective) frequently model solutions to a problem using a population of chromosomes, each of which represents a single encoded solution. These chromosomes are then subjected to repeated evolutionary operators to allow the population to iterate towards one or more optimal solutions. Such operators typically include crossover (sharing genetic material between chromosomes), mutation (allowing variation within a chromosome) and selection (choosing good chromosomes from which to create the next generation). Evolutionary algorithms are also frequently implemented in parallel, and a common paradigm is to use a number of distributed sub-populations executing on different machines. In this so-called island paradigm, the migration operator is introduced. In a similar manner to biological evolution, two isolated sub-populations might diverge genetically. Migration is a process that occasionally allows genetic material to move between sub-populations. Research shows that this process may have a beneficial impact on the genetic diversity of both sub-populations, thus improving the overall quality of the results. The way in which genetic material moves between sub-populations is dictated by the links between the sub-populations (termed the migration topology). In addition to the benefits, there is also a cost to migration: solutions must be distributed over a network or between running processes. One class of problem that can be solved using an evolutionary algorithm is that of network optimisation in particular the problem of finding an optimal topology of a network given certain criteria. Such problems can involve single or multiple objectives, depending on how the problem is defined. In this research I combine the concepts of network optimisation, migration topologies, diversity and cost; and examine the effectiveness of a multi-objective evolutionary algorithm in finding a Pareto-optimal migration topology for itself. In this way, an identical multi-objective algorithm is applied at both the problem domain-level and the meta-level. That is, the multi-objective algorithm searches for Pareto-optimal migration topologies for a selected domain problem which is itself being solved by a parallel distributed version of the same algorithm. To the best of my knowledge, this is a novel application of the same algorithm in this way; and demonstrates the generality of such algorithms. The primary hypothesis is therefore that it is possible to find such Pareto-optimal topologies using the same algorithm at two levels. The results obtained support this hypothesis.

Viewing alternatives

Metrics

Item Actions

Export