interactive evolution
A set of commonly used algorithms for complex optimisation tasks are derived from the field of evolutionary computation (EC). Evolutionary Algorithms are a class of stochastic population-based search heuristics loosely modelled on Darwinian Evolution and genetics. Each member of a population is a set of parameters required to construct a candidate solution together with a scalar “fitness” value, which reflects some measure of the quality of that solution. Stochastic processes of selection of parents (with a bias towards “fitter” individuals), recombination of parents (whereby parts of two or more parents are mixed at random to produce a new solution), mutation of the resultant offspring (whereby with low probability random changes are made to the parameters) and finally replacement of the parents by the new set of offspring, are iteratively applied to the population. Over time, drawing on the analogy of natural evolution, the fittest solutions determine the subsequent population of solutions, each generation comprising new individuals which are more suited to achieving the required task, until a satisfactory level of performance is achieved. A full description can be found in [Eiben and Smith, 2003] . The main groups of evolutionary algorithms that fall under the umbrella of evolutionary computation include genetic algorithms [Holland 1992] , genetic programming [Koza 1992] and evolution strategies [Beyer and Schwefel, 2002]. This is now a mature technology, which has been successfully applied in a wide range of problem domains.
Interactive evolution involves the allocation of the fitness value for a candidate solution by a human, as opposed to being calculated by a pre-determined mathematical model. The field of interactive evolution has been expanding into numerous and varied application areas since Dawkins introduced the evolution of “biomorphs” using subjective selection [Dawkins 1987]. In reviewing the literature, applications using “interactive evolution” were found to range from generating Jazz solos [Biles 1994] to personalising hearing aid characteristics [Takagi et al. 1999] and manufacturing plant design optimisation [ Brintrup 2007]. In his review paper, Takagi [Takagi 2001] divides research based on interactive evolution in three major fields - artistic, engineering and educational, and lists a vast range of references demonstrating the scope of this idea.
Human expertise is exploited in terms of its unparalleled creativity and ability for pattern recognition.
Interactive evolution is particularly appropriate for the optimisation of a quality metric which is difficult to mathematically define and possibly subject to change over a period of time, but can be assigned by a human on the basis of tacit expert knowledge. However, the reliance on human guidance and judgment to direct and control the search creates both the potential weaknesses and strengths. On one hand, human assessment tends to have a component of subjectivity and non-linearity of focus over time. Hence including a human in the loop introduces a need for rapid convergence to prevent the interactive process from becoming tedious for the human participant. At the same time the ability to maneuver the search interactively can potentially be exploited as a powerful strategy for adapting an otherwise naive evolutionary algorithm.
This approach has been successfully used for the interactive evolution of robust algorithms for the segmentation of images - See List of Publications.
Top
