Portfolio configurators tune an algorithm's parameters to produce a portfolio of parameterisations, with complementary strengths on different problem instances. However, as the portfolio size increases, the marginal contribution of each additional configuration decreases, making portfolio configuration computationally expensive. We propose a hybrid racing method that combines statistical testing (to early eliminate poorly performing configurations) and successive halving (which progressively allocates more resources to promising configurations by discarding fractions of the configuration candidate set in rounds). We connect greedy portfolio configuration approaches to the theory of submodular function optimisation, which implies an approximation ratio of 1 − 1/e for the problem in idealised form. We experimentally compare the hybrid method with pure statistical racing and pure successive halving, on algorithm configuration benchmarks from the literature. We show that the proposed hybrid racing method achieves portfolios with performance matching those configured on the full evaluation data, while usually using roughly 5% of the runs of a full evaluation, and that the method is more efficient than pure statistical racing or successive halving for portfolio configuration. Our experiments demonstrate that adaptive elimination strategies can significantly improve the efficiency of portfolio configuration methods.

This paper presents a comprehensive empirical investigation into the interactions between various randomization techniques in Deep Neural Networks (DNNs) and their impact on learning performance. It is well-established that injecting randomness into the training process of DNNs, through various approaches, at different stages, is often beneficial for reducing overfitting and improving generalization. Nonetheless, the interactions between randomness techniques such as weight noise, dropout, and many others remain poorly understood. Consequently, it is challenging to determine which methods can be effectively combined to optimize DNN performance. To address this issue, we categorize the existing randomness techniques into four key types: injection of noise/randomness at the data, model structure, optimization or learning stage. We use this classification to identify gaps in the current coverage of potential mechanisms for the introduction of randomness, leading to proposing two new techniques: adding noise to the loss function and random masking of the gradient updates. In our empirical study, we employ a Particle Swarm Optimizer (PSO) for hyperparameter optimization (HPO) to explore the space of possible configurations to determine where and how much randomness should be injected to maximize DNN performance. We assess the impact of various types and levels of randomness for DNN architectures across standard computer vision benchmarks: MNIST, FASHION-MNIST, CIFAR10, and CIFAR100. Across more than 30 000 evaluated configurations, we perform a detailed examination of the interactions between randomness techniques and their combined impact on DNN performance. Our findings reveal that randomness through data augmentation and in weight initialization are the main contributors to performance improvement. Additionally, correlation analysis demonstrates that different optimizers, such as Adam and Gradient Descent with Momentum, prefer distinct types of randomization during the training process. A GitHub repository with the complete implementation and generated dataset is available1.

Multiview data analysis provides an effective means to integrate the distinct information sources which are inherent to many applications. Data clustering in a multiview setting specifically aims to identify the most appropriate grouping for a collection of entities, where those entities (or their relationships) can be described from multiple perspectives. Leveraging recent advances in multiobjective clustering, we propose a new evolutionary method to tackle this challenge. Designed around a flexible and unbiased solution representation, together with strategies based on the minimum spanning tree and neighborhood relations, our algorithm optimizes multiple objectives simultaneously to effectively explore the space of candidate tradeoffs between the data views. Through a series of experiments, we investigate the suitability of our proposal in the context of a bioinformatics application, clustering of plausible protein structures, and a diverse set of synthetic problems. The specific case of two data views is considered in this article. The evaluation with respect to a variety of reference approaches demonstrates the effectiveness of our method in discovering high-quality partitions in a multiview setting. Robustness against unreliable data sources and the ability to automatically determine the number of clusters are additional advantages evidenced by the results obtained.

Comprehensive benchmarking of clustering algorithms is rendered difficult by two key factors: 1) the elusiveness of a unique mathematical definition of this unsupervised learning approach and 2) dependencies between the generating models or clustering criteria adopted by some clustering algorithms and indices for internal cluster validation. Consequently, there is no consensus regarding the best practice for rigorous benchmarking, and whether this is possible at all outside the context of a given application. Here, we argue that synthetic datasets must continue to play an important role in the evaluation of clustering algorithms, but that this necessitates constructing benchmarks that appropriately cover the diverse set of properties that impact clustering algorithm performance. Through our framework, HAWKS, we demonstrate the important role evolutionary algorithms play to support flexible generation of such benchmarks, allowing simple modification and extension. We illustrate two possible uses of our framework: 1) the evolution of benchmark data consistent with a set of hand-derived properties and 2) the generation of datasets that tease out performance differences between a given pair of algorithms. Our work has implications for the design of clustering benchmarks that sufficiently challenge a broad range of algorithms, and for furthering insight into the strengths and weaknesses of specific approaches.

Synthetic datasets play an important role in evaluating clustering algorithms, as they can help shed light on consistent biases, strengths, and weaknesses of particular techniques, thereby supporting sound conclusions. Despite this, there is a surprisingly small set of established clustering benchmark data, and many of these are currently handcrafted. Even then, their difficulty is typically not quantified or considered, limiting the ability to interpret algorithmic performance on these datasets. Here, we introduce HAWKS, a new data generator that uses an evolutionary algorithm to evolve cluster structure of a synthetic data set. We demonstrate how such an approach can be used to produce datasets of a pre-specified difficulty, to trade off different aspects of problem difficulty, and how these interventions directly translate into changes in the clustering performance of established algorithms.

A key consideration in developing optimization approaches for data clustering is choice of a suitable encoding. Existing encodings strike different trade-offs between model and search complexity, limiting the applicability to data sets with particular properties or to problems of moderate size. Recent research has introduced an additional hyperparameter to directly govern the encoding granularity in the multi-objective clustering algorithm MOCK. Here, we investigate adapting this important hyperparameter during run-time. In particular, we consider a number of different trigger mechanisms to control the timing of changes to this hyperparameter and strategies to rapidly explore the newly "opened" search space resulting from this change. Experimental results illustrate distinct performance differences between the approaches tested, which can be explained in light of the relative importance of initialization, crossover and mutation in MOCK. The most successful strategies meet the clustering performance achieved for an optimal (a priori) setting of the hyperparameter, at a ~40% reduction of computational expense.

Computational structural biology is an important, growing research area that includes diverse problems, such as protein structure prediction, computational molecular assembly, and computer-assisted drug design problems, that include protein-ligand binding, protein-protein, protein-RNA, and protein-DNA docking, as well as computer assisted wet-laboratory structure resolving problems, like registration, reconstruction, and refinement. The focus of this special section is on the application of non-linear optimization to problems in structural biology, thus turning the spotlight on a growing area of interdisciplinary research that brings together expertise in meta-heuristic optimization and computational structural biology. The five articles included in this section provide a glimpse of the diversity of work in this area, highlighting the adaptation and use of a variety of state-of-the-art meta-heuristics for a range of problems linked to the wider area of structural biology.

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.

Ensemble methods for clustering take a collection of input partitions, produced for the same data set, and generate an ensemble partition that tries to preserve the information carried in this collective. Acceptance of the resulting partition(s) by decision makers can be a problem, due to the inherent complexity of ensemble techniques, and the associated lack of intuition on how a consensus has been derived from the original set of input partitions. This problem is exacerbated in multi-objective ensemble techniques, which generate a set of non-dominated consensus partitions. In this context, the selection of a final candidate clustering may require additional insight into the relationships between non-dominated output partitions. In this manuscript, we describe the first prototype of a novel visualization tool, CVis, which has been developed as a general tool to provide insight into the relationship between any set of partitions of a given data set. We proceed to demonstrate the specific use of this tool in understanding the relationship between the sets of input, the sets of outputs, and the input-output relationships for the multi-objective ensemble technique MOCLE. We discuss how the interlinked analysis of such sets of partitions can shed light onto the functioning, and the strengths and limitations of a particular ensemble technique. In particular, the tool facilitates the visual analysis of the level of support identified for individual consensus clusters, which is helpful in explaining final solutions to a decision maker.

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.

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.

MOTIVATION: Studying biological systems, not just at an individual component level but at a system-wide level, gives us great potential to understand fundamental functions and essential biological properties. Despite considerable advances in the topological analysis of metabolic networks, inadequate knowledge of the enzyme kinetic rate laws and their associated parameter values still hampers large-scale kinetic modelling. Furthermore, the integration of gene expression and protein levels into kinetic models is not straightforward. RESULTS: The focus of our research is on streamlining the construction of large-scale kinetic models. A novel software tool was developed, which enables the generation of generic rate equations for all reactions in a model. It encompasses an algorithm for estimating the concentration of proteins for a reaction to reach a particular steady state when kinetic parameters are unknown, and two robust methods for parameter estimation. It also allows for the seamless integration of gene expression or protein levels into a reaction and can generate equations for both transcription and translation. We applied this methodology to model the yeast glycolysis pathway; our results show that the behaviour of the system can be accurately described using generic kinetic equations. AVAILABILITY AND IMPLEMENTATION: The software tool, together with its source code in Java, is available from our project web site at http://www.bioinf.manchester.ac.uk/schwartz/grape CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

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.

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

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.

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.

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/.