Extending the black-box complexity framework, we consider multistage stochastic optimisation problems under recourse. Such problems ask for a solution to an optimisation problem under uncertainty, where once the uncertainty is (partially) observed, in one or more stages, a stage-by-stage set of 'recourse' actions may be applied to repair the solution. These problems have been studied in the optimisation literature for decades, and applications include multistage portfolio investment, routing under uncertainty, and (dynamic) rescheduling. To facilitate rigorous complexity analysis of these problems in a black-box setting, we develop a precise, broad framework enabling us to describe what information is exchanged between the black-box and the optimisation algorithm, and what solution concept is used. To illustrate the power of the technique, we develop runtime bounds for evolutionary algorithms applied to stochastic optimisation problems with recourse. The theoretical results are complemented by experiments.

We address the challenging problem of multiobjective optimization via stochastic simulation over a discrete design space. We consider the setting where objective functions are expensive black-box simulations corrupted by heteroscedastic noise, and the decision space is usually too large for exhaustive enumeration. Existing methods often struggle to balance three competing needs: scalable surrogate modeling on discrete domains, principled handling of simulation noise (specifically regarding the uncertainty of the current best solution), and efficient navigation of the multiobjective landscape. Our proposed framework extends the single-objective Complete Expected Improvement acquisition function to the bi-objective case. Our contribution is threefold: (1) we employ Gaussian Markov Random Field surrogates to exploit the integer lattice structure; (2) we use ParEGO-style scalarizations but restrict them to linear to preserve the Gaussianity of the posterior, allowing us to derive a closed-form scalarized acquisition function that explicitly accounts for the covariance between the candidate solution and the noisy incumbent. (3) To maximize this acquisition function, we integrate a discrete Genetic Algorithm with specialized local and jump mutation operators as the inner optimizer. We benchmark our approach against an adaptation of state-of-the-art methods on noisy variants of standard test functions, showing faster early convergence while retaining computational tractability.

To ensure empirical evaluation of multi- and many-objective evolutionary algorithms, researchers perform benchmarking across test problems and algorithms. Due to the volume of performance data and the heterogeneity of problem characteristics, analyzing results becomes complex and prone to misinterpretation. Performance profiles have proven effective for visualizing and interpreting such results; however, they do not account for the relative difficulty or importance of individual problems and may overweight easy or less informative cases, potentially obscuring distinctions between algorithm performance. In this work, we address this limitation by extending the classical performance profile approach with a difficulty-aware weighting scheme that emphasizes more challenging problems. Weights can be assigned either a priori, based on problem characteristics such as the number of objectives or decision variables, or a posteriori, based on computational effort. We define and prove key mathematical properties of classical performance profiles, including local and global stability, and show that these properties extend to the proposed weighted formulation. By employing a difficulty-aware weighting scheme, the approach biases aggregation toward higher-dimensional instances, enabling a more discriminative assessment of scalability, robustness, and performance. The advantages of the weighted approach are demonstrated through experiments with algorithms applied to problem sets with numbers of objectives.

The story goes that while working at Bell Labs in the 1950s, the mathematician and computer scientist Richard Hamming would ask colleagues, "what's the most important problem in your field?" ... and then follow up with, "so, why aren't you working on it?" Both questions have many possible answers, even for just one person at one time, but they are certainly provocative, tough and uncomfortable. In the talk, I will reflect on my personal answers at various times, some answers for evolutionary computation (EC) and evolutionary multiobjective optimization (EMO) more broadly, and for adjacent fields to EC/EMO as well as for industrial research & innovation. My particular answers (or anyone's) are almost certainly not as important as the effort behind them to grapple with the questions.

We consider whether conditions exist under which block-coordinate descent is asymptotically efficient in evolutionary multi-objective optimization, addressing an open problem. Block-coordinate descent, where an optimization problem is decomposed into k blocks of decision variables and each of the blocks is optimized (with the others fixed) in a sequence, is a technique used in some large-scale optimization problems such as airline scheduling, however its use in multi-objective optimization is less studied. We propose a block-coordinate version of GSEMO and compare its running time to the standard GSEMO algorithm. Theoretical and empirical results on a bi-objective test function, a variant of LOTZ, serve to demonstrate the existence of cases where block-coordinate descent is faster. The result may yield wider insights into this class of algorithms.

We carry out a detailed performance assessment of two interactive evolutionary multi-objective algorithms (EMOAs) using a machine decision maker that enables us to repeat experiments and study specific behaviours modeled after human decision makers (DMs). Using the same set of benchmark test problems as in the original papers on these interactive EMOAs (in up to 10 objectives), we bring to light interesting effects when we use a machine DM based on sigmoidal utility functions that have support from the psychology literature (replacing the simpler utility functions used in the original papers). Our machine DM enables us to go further and simulate human biases and inconsistencies as well. Our results from this study, which is the most comprehensive assessment of multiple interactive EMOAs so far conducted, suggest that current well-known algorithms have shortcomings that need addressing. These results further demonstrate the value of improving the benchmarking of interactive EMOAs.

We consider a new class of expensive, resource-constrained optimization problems (here arising from molecular discovery) where costs are associated with the experiments (or evaluations) to be carried out during the optimization process. In the molecular discovery problem, candidate compounds to be optimized must be synthesized in an iterative process that starts from a set of purchasable items and builds up to larger molecules. To produce target molecules, their required resources are either used from already-synthesized items in storage or produced themselves on-demand at an additional cost. Any remaining resources from the production process are stored for reuse for the next evaluations. We model these resource dependencies with a directed acyclic production graph describing the development process from granular purchasable items to evaluable target compounds. Moreover, we develop several resource-eficient algorithms to address this problem. In particular, we develop resource-aware variants of Random Search heuristics and of Bayesian Optimization and analyze their performance in terms of anytime behavior. The experimental results were obtained from a real-world molecular optimization problem. Our results suggest that algorithms that encourage exploitation by reusing existing resources achieve satisfactory results while using fewer resources overall.

Improvements to the design of interactive Evolutionary Multiobjective Algorithms (iEMOAs) are unlikely without quantitative assessment of their behaviour in realistic settings. Experiments with human decision-makers (DMs) are of limited scope due to the difficulty of isolating individual biases and replicating the experiment with enough subjects, and enough times, to obtain confidence in the results. Simulation studies may help to overcome these issues, but they require the use of realistic simulations of decision-makers. Machine decision-makers (MDMs) provide a way to carry out such simulation studies, however, studies so far have relied on simple utility functions. In this paper, we analyse and compare two state-of-the-art iEMOAs by means of a MDM that uses a sigmoid-shaped utility function. This sigmoid utility function is based on psychologically realistic models from behavioural economics, and replicates several realistic human behaviours. Our findings are that, on a variety of well-known benchmarks with two and three objectives, the two iEMOAs do not consistently recover the most-preferred points. We hope that these findings provide an impetus for more directed design and analysis of future iEMOAs.

The multiobjective realization of the data clustering problem has shown great promise in recent years, yielding clear conceptual advantages over the more conventional, single-objective approach. Evolutionary algorithms have largely contributed to the development of this increasingly active research area on multiobjective clustering. Nevertheless, the unprecedented volumes of data seen widely today pose significant challenges and highlight the need for more effective and scalable tools for exploratory data analysis. This paper proposes an improved version of the multiobjective clustering with automatic k -determination algorithm. Our new algorithm improves its predecessor in several respects, but the key changes are related to the use of an efficient, specialized initialization routine and two alternative reduced-length representations. These design components exploit information from the minimum spanning tree and redefine the problem in terms of the most relevant subset of its edges. This paper reveals that both the new initialization routine and the new solution representations not only contribute to decrease the computational overhead, but also entail a significant reduction of the search space, enhancing therefore the convergence capabilities and overall effectiveness of the method. These results suggest that the new algorithm proposed here will offer significant advantages in the realm of “big data” analytics and applications.

Various aspects of computer game design, including adaptive elements of game levels, characteristics of “bot” behavior, and player matching in multiplayer games, would ideally be sensitive to a player's skill level. Yet, while game difficulty and player learning have been explored in the context of games, there has been little work analyzing skill per se, and how this is related to the interaction of a player with the controls of the game - the player's input. To this end, we present a data set of 476 game logs from over 40 players of a first-person shooter game (Red Eclipse) as a basis of a case study. We then extract features from the keyboard and mouse input and provide an analysis in relation to skill. Finally, we show that a player's skill can be predicted using less than a minute of their keyboard presses. We suggest that the techniques used here are useful for adapting games to match players' skill levels rapidly, arguably more rapidly than solutions based on performance averaging such as TrueSkill.

Computational approaches to de novo protein tertiary structure prediction, including those based on the preeminent "fragment-assembly" technique, have failed to scale up fully to larger proteins (on the order of 100 residues and above). A number of limiting factors are thought to contribute to the scaling problem over and above the simple combinatorial explosion, but the key ones relate to the lack of exploration of properly diverse protein folds, and to an acute form of "deception" in the energy function, whereby low-energy conformations do not reliably equate with native structures. In this article, solutions to both of these problems are investigated through a multistage memetic algorithm incorporating the successful Rosetta method as a local search routine. We found that specialised genetic operators significantly add to structural diversity and that this translates well to reaching low energies. The use of a generalised stochastic ranking procedure for selection enables the memetic algorithm to handle and traverse deep energy wells that can be considered deceptive, which further adds to the ability of the algorithm to obtain a much-improved diversity of folds. The results should translate to a tangible improvement in the performance of protein structure prediction algorithms in blind experiments such as CASP, and potentially to a further step towards the more challenging problem of predicting the three-dimensional shape of large proteins.

Abstract Summary: Developing liquid chromatography tandem mass spectrometry (LC-MS/MS) analyses of (bio)chemicals is both time consuming and challenging, largely because of the large number of LC and MS instrument parameters that need to be optimized. This bottleneck significantly impedes our ability to establish new (bio)analytical methods in fields such as pharmacology, metabolomics and pesticide research. We report the development of a multi-platform, user-friendly software tool MUSCLE (multi-platform unbiased optimization of spectrometry via closed-loop experimentation) for the robust and fully automated multi-objective optimization of targeted LC-MS/MS analysis. MUSCLE shortened the analysis times and increased the analytical sensitivities of targeted metabolite analysis, which was demonstrated on two different manufacturer’s LC-MS/MS instruments. Availability and implementation: Available at http://www.muscleproject.org. Contact: [email protected] Supplementary information: Supplementary data are available at Bioinformatics online.

We introduce a model of reproduction in which the genotypephenotype (G-P) map is able to evolve. In this model, Each organism implements a G-P map, determining how the organism is encoded in its genome. Crucially, it also determines how the G-P map itself is encoded. We call these maps ‘self-encoding’. We relate this model to recent artificial life research, and back to the seminal work of John von Neumann. We simulate populations of organisms that have as their genome and G-P map the axiom and production rules of an L-system. The populations are given the task of optimizing a dynamic fitness function. Our purpose is to study whether the self-encoding property has any effect on the evolution of evolvability, and to look for other factors that lead to the evolution of G-P maps that confer evolvability. We find that evolvability does evolve, but only when we add constraints to the model.

Classifiers trained on data sets possessing an imbalanced class distribution are known to exhibit poor generalisation performance. This is known as the imbalanced learning problem. The problem becomes particularly acute when we consider incremental classifiers operating on imbalanced data streams, especially when the learning objective is rare class identification. As accuracy may provide a misleading impression of performance on imbalanced data, existing stream classifiers based on accuracy can suffer poor minority class performance on imbalanced streams, with the result being low minority class recall rates. In this paper we address this deficiency by proposing the use of the Hellinger distance measure, as a very fast decision tree split criterion. We demonstrate that by using Hellinger a statistically significant improvement in recall rates on imbalanced data streams can be achieved, with an acceptable increase in the false positive rate.

We investigate how combinations of evolutionary algorithms (portfolios) can be constructed efficiently for solving optimization problem instances drawn from a distribution. We consider selection methods ranging in intricacy and based on different principles including a technique for efficient tuning of metaheuristics, a racing algorithm. The selectors are used here to optimize instances of the Preventive Maintenance Scheduling Problem (PMSP) in power generation. Experiments show different behaviors of selectors in term of computational time needed to choose constituent algorithms and the performance of the generated portfolios at optimizing previously unseen PMSP instances. The racing selector offers a good trade-off between the computational time and the performance.

Receiver Operating Characteristics (ROC) curves represent the performance of a classifier for all possible operating conditions, i.e., for all preferences regarding the tradeoff between false positives and false negatives. The generation of a ROC curve generally involves the training of a single classifier for a given set of operating conditions, with the subsequent use of threshold-moving to obtain a complete ROC curve. Recent work has shown that the generation of ROC curves may also be formulated as a multi-objective optimization problem in ROC space: the goals to be minimized are the false positive and false negative rates. This technique also produces a single ROC curve, but the curve may derive from operating points for a number of different classifiers. This paper aims to provide an empirical comparison of the performance of both of the above approaches, for the specific case of prototype-based classifiers. Results on synthetic and real domains shows a performance advantage for the multi-objective approach.

The domain of radio astronomy is currently facing significant computational challenges, foremost amongst which are those posed by the development of the world's largest radio telescope, the Square Kilometre Array (SKA). Preliminary specifications for this instrument suggest that the final design will incorporate between 2000 and 3000 individual 15 metre receiving dishes, which together can be expected to produce a data rate of many TB/s. Given such a high data rate, it becomes crucial to consider how this information will be processed and stored to maximise its scientific utility. In this paper, we consider one possible data processing scenario for the SKA, for the purposes of an all-sky pulsar survey. In particular we treat the selection of promising signals from the SKA processing pipeline as a data stream classification problem. We consider the feasibility of classifying signals that arrive via an unlabelled and heavily class imbalanced data stream, using currently available algorithms and frameworks. Our results indicate that existing stream learners exhibit unacceptably low recall on real astronomical data when used in standard configuration, however, good false positive performance and comparable accuracy to static learners, suggests they have definite potential as an on-line solution to this particular big data challenge.

We consider optimization problems where the set of solutions available for evaluation at any given time t during optimization is some subset of the feasible space. This model is appropriate to describe many closed-loop optimization settings (i.e., where physical processes or experiments are used to evaluate solutions) where, due to resource limitations, it may be impossible to evaluate particular solutions at particular times (despite the solutions being part of the feasible space). We call the constraints determining which solutions are non-evaluable ephemeral resource constraints (ERCs). In this paper, we investigate two specific types of ERC: one encodes periodic resource availabilities, the other models commitment constraints that make the evaluable part of the space a function of earlier evaluations conducted. In an experimental study, both types of constraint are seen to impact the performance of an evolutionary algorithm significantly. To deal with the effects of the ERCs, we propose and test five different constraint-handling policies (adapted from those used to handle standard constraints), using a number of different test functions including a fitness landscape from a real closed-loop problem. We show that knowing information about the type of resource constraint in advance may be sufficient to select an effective policy for dealing with it, even when advance knowledge of the fitness landscape is limited.

We present a test suite of 23 instances of a preventive maintenance scheduling problem from the power industry, which we also make available online. The formulation of the problem and the suite are derived from real-world data collected recently. A first study of the landscape characteristics of these problem instances based on three different types of adaptive walk reveals a generally rugged landscape, with little global fitness-distance correlation. Initial results from a simple evolutionary algorithm shows indifferent performance compared to adaptive walks, suggesting that intensive local search may be an important component of a successful optimizer for this problem.

We consider an optimization scenario in which resources are required in the evaluation process of candidate solutions. The challenge we are focussing on is that certain resources have to be committed to for some period of time whenever they are used by an optimizer. This has the effect that certain solutions may be temporarily non-evaluable during the optimization. Previous analysis revealed that evolutionary algorithms (EAs) can be effective against this resourcing issue when augmented with static strategies for dealing with non-evaluable solutions, such as repairing, waiting, or penalty methods. Moreover, it is possible to select a suitable strategy for resource-constrained problems offline if the resourcing issue is known in advance. In this paper we demonstrate that an EA that uses a reinforcement learning (RL) agent, here Sarsa(λ), to learn offline when to switch between static strategies, can be more effective than any of the static strategies themselves. We also show that learning the same task as the RL agent but online using an adaptive strategy selection method, here D-MAB, is not as effective; nevertheless, online learning is an alternative to static strategies.

MOTIVATION: Directed evolution, in addition to its principal application of obtaining novel biomolecules, offers significant potential as a vehicle for obtaining useful information about the topologies of biomolecular fitness landscapes. In this article, we make use of a special type of model of fitness landscapes-based on finite state machines-which can be inferred from directed evolution experiments. Importantly, the model is constructed only from the fitness data and phylogeny, not sequence or structural information, which is often absent. The model, called a landscape state machine (LSM), has already been used successfully in the evolutionary computation literature to model the landscapes of artificial optimization problems. Here, we use the method for the first time to simulate a biological fitness landscape based on experimental evaluation. RESULTS: We demonstrate in this study that LSMs are capable not only of representing the structure of model fitness landscapes such as NK-landscapes, but also the fitness landscape of real DNA oligomers binding to a protein (allophycocyanin), data we derived from experimental evaluations on microarrays. The LSMs prove adept at modelling the progress of evolution as a function of various controlling parameters, as validated by evaluations on the real landscapes. Specifically, the ability of the model to 'predict' optimal mutation rates and other parameters of the evolution is demonstrated. A modification to the standard LSM also proves accurate at predicting the effects of recombination on the evolution.

MOTIVATION: Decoy datasets, consisting of a solved protein structure and numerous alternative native-like structures, are in common use for the evaluation of scoring functions in protein structure prediction. Several pitfalls with the use of these datasets have been identified in the literature, as well as useful guidelines for generating more effective decoy datasets. We contribute to this ongoing discussion an empirical assessment of several decoy datasets commonly used in experimental studies. RESULTS: We find that artefacts and sampling issues in the large majority of these data make it trivial to discriminate the native structure. This underlines that evaluation based on the rank/z-score of the native is a weak test of scoring function performance. Moreover, sampling biases present in the way decoy sets are generated or used can strongly affect other types of evaluation measures such as the correlation between score and root mean squared deviation (RMSD) to the native. We demonstrate how, depending on type of bias and evaluation context, sampling biases may lead to both over- or under-estimation of the quality of scoring terms, functions or methods. AVAILABILITY: Links to the software and data used in this study are available at http://dbkgroup.org/handl/decoy_sets.

The research area of evolutionary multiobjective optimization (EMO) is reaching better understandings of the properties and capabilities of EMO algorithms, and accumulating much evidence of their worth in practical scenarios. An urgent emerging issue is that the favoured EMO algorithms scale poorly when problems have "many" (e.g. five or more) objectives. One of the chief reasons for this is believed to be that, in many-objective EMO search, populations are likely to be largely composed of nondominated solutions. In turn, this means that the commonly-used algorithms cannot distinguish between these for selective purposes. However, there are methods that can be used validly to rank points in a nondominated set, and may therefore usefully underpin selection in EMO search. Here we discuss and compare several such methods. Our main finding is that simple variants of the often-overlooked "Average Ranking" strategy usually outperform other methods tested, covering problems with 5-20 objectives and differing amounts of inter-objective correlation. Copyright 2007 ACM.

This paper reviews the application of multiobjective optimization in the fields of bioinformatics and computational biology. A survey of existing work, organized by application area, forms the main body of the review, following an introduction to the key concepts in multiobjective optimization. An original contribution of the review is the identification of five distinct "contexts," giving rise to multiple objectives: These are used to explain the reasons behind the use of multiobjective optimization in each application area and also to point the way to potential future uses of the technique.

The framework of multiobjective optimization is used to tackle the unsupervised learning problem, data clustering, following a formulation first proposed in the statistics literature. The conceptual advantages of the multiobjective formulation are discussed and an evolutionary approach to the problem is developed. The resulting algorithm, multiobjective clustering with automatic k-determination, is compared with a number of well-established single-objective clustering algorithms, a modern ensemble technique, and two methods of model selection. The experiments demonstrate that the conceptual advantages of multiobjective clustering translate into practical and scalable performance benefits

A Landscape State Machine (LSM) is a Markov model describing the transition probabilities between the fitness ` levels' of an optimization problem, when a given neighbourhood (or mutation) operator is applied. Although most optimization problems cannot be modeled precisely by an LSM, an approximate LSM can always be constructed by sampling, and can be used, subsequently, in place of real fitness evaluations in order to model the performance of any search algorithm using the given neighbourhood operator. In this paper, we provide empirical evidence that (a) LSMs constructed by simulated annealing-based sampling of a problem landscape make accurate models in few evaluations; (b) LSMs can accurately rank the performance of diverse algorithms including EAs with/without niching and SA; (c) the LSM approach works on diverse problems from MAX-SAT to NKp; (d) convergence of the LSM can be used as a guide to stopping the sampling phase; and, (e) a single LSM constructed using a low mutation-rate sample is sufficient to accurately rank the performance of search algorithms run at multiples of this mutation rate.

Semi-supervised classification uses aspects of both unsupervised and supervised learning to improve upon the performance of traditional classification methods. Semi-supervised clustering, in particular, explicitly integrates both information about the data distribution and about class memberships into the clustering process. In this paper, the potential of a multiobjective formulation of the semi-supervised clustering problem is explored, and two evolutionary multiobjective approaches to the problem are outlined. Experimental results demonstrate practical performance benefits of this methodology, including an improved classification performance and an increased robustness towards annotation errors.

In previous work, we have shown that both unsupervised feature selection and the semi-supervised clustering problem can be usefully formulated as multiobjective optimization problems. In this paper, we discuss the logical extension of this prior work to cover the problem of semi-supervised feature selection. Our extensive experimental results provide evidence for the advantages of semi-supervised feature selection when both labelled and unlabelled data are available. Moreover, the particular effectiveness of a Pareto-based optimization approach can also be seen.

Ant-based clustering and sorting is a nature-inspired heuristic first introduced as a model for explaining two types of emergent behavior observed in real ant colonies. More recently, it has been applied in a data-mining context to perform both clustering and topographic mapping. Early work demonstrated some promising characteristics of the heuristic but did not extend to a rigorous investigation of its capabilities. We describe an improved version, called ATTA, incorporating adaptive, heterogeneous ants, a time-dependent transporting activity, and a method (for clustering applications) that transforms the spatial embedding produced by the algorithm into an explicit partitioning. ATTA is then subjected to the most rigorous experimental evaluation of an ant-based clustering and sorting algorithm undertaken to date: we compare its performance with standard techniques for clustering and topographic mapping using a set of analytical evaluation functions and a range of synthetic and real data collections. Our results demonstrate the ability of ant-based clustering and sorting to automatically identify the number of clusters inherent in a data collection, and to produce high quality solutions; indeed, we show that it is particularly robust for clusters of differing sizes and for overlapping clusters. The results obtained for topographic mapping are, however, disappointing. We provide evidence that the solutions generated by the ant algorithm are barely topology-preserving, and we explain in detail why results have--in spite of this--been misinterpreted (much more positively) in previous research.

This paper concerns multiobjective optimization in scenarios where each solution evaluation is financially and/or temporally expensive. We make use of nine relatively low-dimensional, nonpathological, real-valued functions, such as arise in many applications, and assess the performance of two algorithms after just 100 and 250 (or 260) function evaluations. The results show that NSGA-II, a popular multiobjective evolutionary algorithm, performs well compared with random search, even within the restricted number of evaluations used. A significantly better performance (particularly, in the worst case) is, however, achieved on our test set by an algorithm proposed herein-ParEGO-which is an extension of the single-objective efficient global optimization (EGO) algorithm of Jones et al. ParEGO uses a design-of-experiments inspired initialization procedure and learns a Gaussian processes model of the search landscape, which is updated after every function evaluation. Overall, ParEGO exhibits a promising performance for multiobjective optimization problems where evaluations are expensive or otherwise restricted in number.

The large majority of existing clustering algorithms are centered around the notion of a feature, that is, individual data items are represented by their intrinsic properties, which are summarized by (usually numeric) feature vectors. However, certain applications require the clustering of data items that are defined by exclusively extrinsic properties: only the relationships between individual data items are known (that is, their similarities or dissimilarities). This paper develops a straightforward and efficient adaptation of our existing multiobjective clustering algorithm to such a scenario. The resulting algorithm is demonstrated on a range of data sets, including a dissimilarity matrix derived from real, non-feature-based data

In previous work, the authors have introduced a novel and highly effective approach to data clustering, based on the explicit optimization of a partitioning with respect to two complementary clustering objectives (Handl, et. al., 2004, 2005). In this paper, three modifications were made to the algorithm that improved its scalability to large data sets with high dimensionality and large numbers of clusters. Specifically, new initialization and mutation schemes that enable a more efficient exploration of the search space were introduced, and the null data model that is used as a basis for selecting the most significant solution from the Pareto front was modified. The high performance of the resulting algorithm is demonstrated on a newly developed clustering test suite.

When evaluating the performance of a stochastic optimizer it is sometimes desirable to express performance in terms of the quality attained in a certain fraction of sample runs. For example, the sample median quality is the best estimator of what one would expect to achieve in 50% of runs, and similarly for other quantiles. In multiobjective optimization, the notion still applies but the outcome of a run is measured not as a scalar (i.e. the cost of the best solution), but as an attainment surface in k-dimensional space (where k is the number of objectives). In this paper we report an algorithm that can be conveniently used to plot summary attainment surfaces in any number of dimensions (though it is particularly suited for three). A summary attainment surface is defined as the union of all tightest goals that have been attained (independently) in precisely s of the runs of a sample of n runs, for any s/spl isin/1..n, and for any k. We also discuss the computational complexity of the algorithm and give some examples of its use. C code for the algorithm is available from the author.

MOTIVATION: The discovery of novel biological knowledge from the ab initio analysis of post-genomic data relies upon the use of unsupervised processing methods, in particular clustering techniques. Much recent research in bioinformatics has therefore been focused on the transfer of clustering methods introduced in other scientific fields and on the development of novel algorithms specifically designed to tackle the challenges posed by post-genomic data. The partitions returned by a clustering algorithm are commonly validated using visual inspection and concordance with prior biological knowledge--whether the clusters actually correspond to the real structure in the data is somewhat less frequently considered. Suitable computational cluster validation techniques are available in the general data-mining literature, but have been given only a fraction of the same attention in bioinformatics. RESULTS: This review paper aims to familiarize the reader with the battery of techniques available for the validation of clustering results, with a particular focus on their application to post-genomic data analysis. Synthetic and real biological datasets are used to demonstrate the benefits, and also some of the perils, of analytical clustervalidation. AVAILABILITY: The software used in the experiments is available at http://dbkweb.ch.umist.ac.uk/handl/clustervalidation/. SUPPLEMENTARY INFORMATION: Enlarged colour plots are provided in the Supplementary Material, which is available at http://dbkweb.ch.umist.ac.uk/handl/clustervalidation/.

The No-Free-Lunch (NFL) theorems hold for general multiobjective fitness spaces, in the sense that, over a space of problems which is closed under permutation, any two algorithms will produce the same set of multiobjective samples. However, there are salient ways in which NFL does not generally hold in multiobjective optimization. Previously we have shown that a 'free lunch' can arise when comparative metrics (rather than absolute metrics) are used for performance measurement. Here we show that NFL does not generally apply in multiobjective optimization when absolute performance metrics are used. This is because multiobjective optimizers usually combine a generator with an archiver. The generator corresponds to the 'algorithm' in the NFL sense, but the archiver filters the sample generated by the algorithm in a way that undermines the NFL assumptions. Essentially, if two multiobjective approaches have different archivers, their average performance may differ. We prove this, and hence show that we can say, without qualification, that some multiobjective approaches are better than others.

Many modern multiobjective evolutionary algorithms (MOEAs) store the points discovered during optimization in an external archive, separate from the main population, as a source of innovation and/or for presentation at the end of a run. Maintaining a bound on the size of the archive may be desirable or necessary for several reasons, but choosing which points to discard and which to keep in the archive, as they are discovered, is not trivial. We briefly review the state-of-the-art in bounded archiving, and present a new method based on locally maximizing the hyper-volume dominated by the archive. The new archiver is shown to outperform existing methods, on several problem instances, with respect to the quality of the archive obtained when judged using three distinct quality measures.

Search algorithms for Pareto optimization are designed to obtain multiple solutions, each offering a different trade-off of the problem objectives. To make the different solutions available at the end of an algorithm run, procedures are needed for storing them, one by one, as they are found. In a simple case, this may be achieved by placing each point that is found into an "archive" which maintains only nondominated points and discards all others. However, even a set of mutually nondominated points is potentially very large, necessitating a bound on the archive's capacity. But with such a bound in place, it is no longer obvious which points should be maintained and which discarded; we would like the archive to maintain a representative and well-distributed subset of the points generated by the search algorithm, and also that this set converges. To achieve these objectives, we propose an adaptive archiving algorithm, suitable for use with any Pareto optimization algorithm, which has various useful properties as follows. It maintains an archive of bounded size, encourages an even distribution of points across the Pareto front, is computationally efficient, and we are able to prove a form of convergence. The method proposed here maintains evenness, efficiency, and cardinality, and provably converges under certain conditions but not all. Finally, the notions underlying our convergence proofs support a new way to rigorously define what is meant by "good spread of points" across a Pareto front, in the context of grid-based archiving schemes. This leads to proofs and conjectures applicable to archive sizing and grid sizing in any Pareto optimization algorithm maintaining a grid-based archive.

Evolutionary multiobjective optimization (EMO) boasts a proliferation of algorithms and benchmark problems. We need principled ways to compare the performance of different EMO algorithms, but this is complicated by the fact that the result of an EMO run is not a single scalar value, but a collection of vectors forming a nondominated set. Various metrics for nondominated sets have been suggested. We compare several, using the framework of 'outperformance relations' (Hansen and Jaszkiewicz, 1998). This enables us to criticize and contrast a variety of published metrics, leading to some recommendations on which seem most useful in practice.

Finding minimum-weight spanning trees (MST) in graphs is a classic problem in operations research with important applications in network design. The basic MST problem can be solved efficiently, but the degree constrained and multiobjective versions are NP-hard. Current approaches to the degree-constrained single objective MST include Raidl's (2000) evolutionary algorithm (EA) which employs a direct tree encoding and associated operators, and Knowles and Corne's (2000) encoding based on a modified version of Prim's (1957) algorithm. Approaches to the multiobjective MST include various approximate constructive techniques from operations research, along with Zhou and Gen's (1999) evolutionary algorithm using a Prufer (1918) based encoding. We apply (appropriately modified) the best of recent methods for the (degree-constrained) single objective MST problem to the multiobjective MST problem, and compare with a method based on Zhou and Gen's approach. Our evolutionary computation approaches, using the different encodings, involve a new population-based variant of Knowles and Corne's PAES algorithm. We find the direct encoding to considerably outperform the Prufer encoding. We find that a simple iterated approach, based on Prim's algorithm modified for the multiobjective MST, also significantly outperforms the Prufer encoding.

A memetic algorithm for tackling multiobjective optimization problems is presented. The algorithm employs the proven local search strategy used in the Pareto archived evolution strategy (PAES) and combines it with the use of a population and recombination. Verification of the new M-PAES (memetic PAES) algorithm is carried out by testing it on a set of multiobjective 0/1 knapsack problems. On each problem instance, a comparison is made between the new memetic algorithm, the (1+1)-PAES local searcher, and the strength Pareto evolutionary algorithm (SPEA) of E. Zitzler and L. Thiele (1998, 1999).

We introduce a simple evolution scheme for multiobjective optimization problems, called the Pareto Archived Evolution Strategy (PAES). We argue that PAES may represent the simplest possible nontrivial algorithm capable of generating diverse solutions in the Pareto optimal set. The algorithm, in its simplest form, is a (1 + 1) evolution strategy employing local search but using a reference archive of previously found solutions in order to identify the approximate dominance ranking of the current and candidate solution vectors. (1 + 1)-PAES is intended to be a baseline approach against which more involved methods may be compared. It may also serve well in some real-world applications when local search seems superior to or competitive with population-based methods. We introduce (1 + lambda) and (mu + lambda) variants of PAES as extensions to the basic algorithm. Six variants of PAES are compared to variants of the Niched Pareto Genetic Algorithm and the Nondominated Sorting Genetic Algorithm over a diverse suite of six test functions. Results are analyzed and presented using techniques that reduce the attainment surfaces generated from several optimization runs into a set of univariate distributions. This allows standard statistical analysis to be carried out for comparative purposes. Our results provide strong evidence that PAES performs consistently well on a range of multiobjective optimization tasks.

Finding the degree-constrained minimum spanning tree (d-MST) of a graph is a well-studied NP-hard problem of importance in communications network design and other network-related problems. In this paper we describe some previously proposed algorithms for solving the problem, and then introduce a novel tree construction algorithm called the randomized primal method (RPM) which builds degree-constrained trees of low cost from solution vectors taken as input. RPM is applied in three stochastic iterative search methods: simulated annealing, multistart hillclimbing, and a genetic algorithm. While other researchers have mainly concentrated on finding spanning trees in Euclidean graphs, we consider the more general case of random graph problems. We describe two random graph generators which produce particularly challenging d-MST problems. On these and other problems we find that the genetic algorithm employing RPM outperforms simulated annealing and multistart hillclimbing. Our experimental results provide strong evidence that the genetic algorithm employing RPM finds significantly lower-cost solutions to random graph d-MST problems than rival methods.

Most popular evolutionary algorithms for multiobjective optimisation maintain a population of solutions from which individuals are selected for reproduction. In this paper, we introduce a simpler evolution scheme for multiobjective problems, called the Pareto archived evolution strategy (PAES). We argue that PAES may represent the simplest possible non-trivial algorithm capable of generating diverse solutions in the Pareto optimal set. The algorithm is identified as being a (1+1) evolution strategy, using local search from a population of one but using a reference archive of previously found solutions in order to identify the approximate dominance ranking of the current and candidate solution vectors. PAES is intended as a good baseline approach, against which more involved methods may be compared, and may also serve well in some real-world applications when local search seems superior to or competitive with population-based methods. The performance of the new algorithm is compared with that of a MOEA based on the niched Pareto GA on a real world application from the telecommunications field. In addition, we include results from experiments carried out on a suite of four test functions, to demonstrate the algorithm's general capability.