In this paper, we attempt a deeper understanding of the relative performance of two state-of-the-art metaheuristic solvers for the capacitated vehicle routing problem (CVRP). To this end, we employ a novel CVRP instance generator to expand the set of CVRP instances used to assess heuristics. This generator modifies existing problem instances using the outliers of node clusters to produce relevant new CVRP instances. We consider a large number of features to characterise each problem instance, and propose to use mixture discriminant analysis (MDA) to obtain both a low dimensional representation of the instance space and a classifier of algorithm performance. MDA has not been previously used in instance space analysis, and as a supervised dimension reduction method has the advantage that the tasks of dimension reduction and classification are handled in a unified framework (rather than two separate steps). The resulting predictive models perform as well as more complex classifiers that involve more tuning parameters and are computationally more expensive (like support vector machines). Our analysis highlights that the performance comparison between the two CVRP metaheuristics is nuanced and the best algorithm depends on the time budget, as well as certain key characteristics of the problem instance.

In this paper we study the algorithm selection problem and instance space analysis for solving Sudoku puzzles with metaheuristic algorithms. We formulate Sudoku as a combinatorial optimisation problem and implement four local-search metaheuristics to solve the problem instances. A feature space is constructed and instance space analysis (ISA) methodology is applied to this problem for the first time. The aim is to use ISA to determine how these features affect the performance of the algorithms and how they can be used for automated algorithm selection. We also consider algorithm selection using multinomial logistic regression models with$l_{1}-\mathbf{penalty}$for comparison. Different algorithm performance metrics are considered and we found that the choice of these metrics affected whether the use of ISA was worthwhile. We found that when the performance of metaheuristic solvers is similar, predicting whether an algorithm will perform “well” is also useful.

Abstract Spectral-based subspace clustering methods have proved successful in many challenging applications such as gene sequencing, image recognition, and motion segmentation. In this work, we first propose a novel spectral-based subspace clustering algorithm that seeks to represent each point as a sparse convex combination of a few nearby points. We then extend the algorithm to a constrained clustering and active learning framework. Our motivation for developing such a framework stems from the fact that typically either a small amount of labelled data are available in advance; or it is possible to label some points at a cost. The latter scenario is typically encountered in the process of validating a cluster assignment. Extensive experiments on simulated and real datasets show that the proposed approach is effective and competitive with state-of-the-art methods.

Subspace clustering is a growing field of unsupervised learning that has gained much popularity in the computer vision community. Applications can be found in areas such as motion segmentation and face clustering. It assumes that data originate from a union of subspaces, and clusters the data depending on the corresponding subspace. In practice, it is reasonable to assume that a limited amount of labels can be obtained, potentially at a cost. Therefore, algorithms that can effectively and efficiently incorporate this information to improve the clustering model are desirable. In this paper, we propose an active learning framework for subspace clustering that sequentially queries informative points and updates the subspace model. The query stage of the proposed framework relies on results from the perturbation theory of principal component analysis, to identify influential and potentially misclassified points. A constrained subspace clustering algorithm is proposed that monotonically decreases the objective function subject to the constraints imposed by the labelled data. We show that our proposed framework is suitable for subspace clustering algorithms including iterative methods and spectral methods. Experiments on synthetic data sets, motion segmentation data sets, and Yale Faces data sets demonstrate the advantage of our proposed active strategy over state-of-the-art.

In this paper we consider the problem of clustering collections of very short texts using subspace clustering. This problem arises in many applications such as product categorisation, fraud detection, and sentiment analysis. The main challenge lies in the fact that the vectorial representation of short texts is both high-dimensional, due to the large number of unique terms in the corpus, and extremely sparse, as each text contains a very small number of words with no repetition. We propose a new, simple subspace clustering algorithm that relies on linear algebra to cluster such datasets. Experimental results on identifying product categories from product names obtained from the US Amazon website indicate that the algorithm can be competitive against state-of-the-art clustering algorithms.

We introduce a kernel formulation of the recently proposed minimum density hyperplane approach to clustering. This enables the identification of clusters that are not linearly separable in the input space by mapping them into a feature space. This mapping also extends the applicability of the minimum density hyperplane to datasets whose features are not necessarily continuous. The location of minimum density hyperplanes involves the optimisation of a non-convex objective function. In the feature space, the dimensionality of the optimisation problem is n, where n is the number of observations. We further propose an approximation method that can substantially reduce the dimensionality of the search space, avoiding searching over dimensions which are unlikely to contain useful information for clustering. Experimental results suggest that the proposed approach is capable of producing high quality partitions across a number of benchmark datasets.

Associating distinct groups of objects (clusters) with contiguous regions of high probability density (high-density clusters), is central to many statistical and machine learning approaches to the classification of unlabelled data. We propose a novel hyperplane classifier for clustering and semi-supervised classification which is motivated by this objective. The proposed minimum density hyperplane minimises the integral of the empirical probability density function along it, thereby avoiding intersection with high density clusters. We show that the minimum density and the maximum margin hyperplanes are asymptotically equivalent, thus linking this approach to maximum margin clustering and semi-supervised support vector classifiers. We propose a projection pursuit formulation of the associated optimisation problem which allows us to find minimum density hyperplanes efficiently in practice, and evaluate its performance on a range of benchmark data sets. The proposed approach is found to be very competitive with state of the art methods for clustering and semi-supervised classification.

An active research direction in Particle Swarm Optimization (PSO) is the integration of PSO variants in adaptive, or self-adaptive schemes, in an attempt to aggregate their characteristics and their search dynamics. In this work we borrow ideas from adaptive filter theory to develop an “online” algorithm adaptation framework. The proposed framework is based on tracking the parameters of a multinomial distribution to capture changes in the evolutionary process. As such, we design a multinomial distribution tracker to capture the successful evolution movements of three PSO variants. Extensive experimental results on ten benchmark functions and comparisons with five state-of-the-art algorithms indicate that the proposed framework is competitive and very promising. On the majority of tested cases, the proposed framework achieves substantial performance gain, while it seems to identify accurately the most appropriate algorithm for the problem at hand.

Differential evolution is a very popular optimization algorithm and considerable research has been devoted to the development of efficient search operators. Motivated by the different manner in which various search operators behave, we propose a novel framework based on the proximity characteristics among the individual solutions as they evolve. Our framework incorporates information of neighboring individuals, in an attempt to efficiently guide the evolution of the population toward the global optimum, without sacrificing the search capabilities of the algorithm. More specifically, the random selection of parents during mutation is modified, by assigning to each individual a probability of selection that is inversely proportional to its distance from the mutated individual. The proposed framework can be applied to any mutation strategy with minimal changes. In this paper, we incorporate this framework in the original differential evolution algorithm, as well as other recently proposed differential evolution variants. Through an extensive experimental study, we show that the proposed framework results in enhanced performance for the majority of the benchmark problems studied.

Sensor management in information-rich and dynamic environments can be posed as a sequential action selection problem with side information. To study such problems we employ the dynamic multi-armed bandit with covariates framework. In this generalization of the multi-armed bandit, the expected rewards are time-varying linear functions of the covariate vector. The learning goal is to associate the covariate with the optimal action at each instance, essentially learning to partition the covariate space adaptively. Applications of sensor management are frequently in environments in which the precise nature of the dynamics is unknown. In such settings, the sensor manager tracks the evolving environment by observing only the covariates and the consequences of the selected actions. This creates difficulties not encountered in static problems, and changes the exploitation–exploration dilemma. We study the relationship between the different factors of the problem and provide interesting insights. The impact of the environment dynamics on the action selection problem is influenced by the covariate dimensionality. We present the surprising result that strategies that perform very little or no exploration perform surprisingly well in dynamic environments.

This paper investigates the performance of trading strategies identified through computational intelligence techniques. We focus on trading rules derived by genetic programming, as well as, generalized moving average rules optimized through differential evolution. The performance of these rules is investigated using recently proposed risk-adjusted evaluation measures and statistical testing is carried out through simulation. Overall, the moving average rules proved to be more robust, but genetic programming seems more promising in terms of generating higher profits and detecting novel patterns in the data.

The hybridization and combination of different Evolutionary Algorithms to improve the quality of the solutions and to accelerate execution is a common research practice. In this paper, we utilize Genetic Programming to evolve novel Differential Evolution operators. The genetic evolution resulted in parameter free Differential Evolution operators. Our experimental results indicate that the performance of the genetically programmed operators is comparable and in some cases is considerably better than the already existing human designed ones.

Networks of spiking neurons can perform complex non-linear computations in fast temporal coding just as well as rate coded networks. These networks differ from previous models in that spiking neurons communicate information by the timing, rather than the rate, of spikes. To apply spiking neural networks on particular tasks, a learning process is required. Most existing training algorithms are based on unsupervised Hebbian learning. In this paper, we investigate the performance of the parallel differential evolution algorithm, as a supervised training algorithm for spiking neural networks. The approach was successfully tested on well-known and widely used classification problems.

A parallel, multi-population differential evolution algorithm for multiobjective optimization is introduced. The algorithm is equipped with a domination selection operator to enhance its performance by favouring non-dominated individuals in the populations. Preliminary experimental results on widely used test problems are promising. Comparisons with the VEGA approach are provided and discussed.

Parallel processing has emerged as a key enabling technology in modern computing. Recent software advances have allowed collections of heterogeneous computers to be used as a concurrent computational resource. In this work we explore how differential evolution can be parallelized, using a ring-network topology, so as to improve both the speed and the performance of the method. Experimental results indicate that the extent of information exchange among subpopulations assigned to different processor nodes, bears a significant impact on the performance of the algorithm. Furthermore, not all the mutation strategies of the differential evolution algorithm are equally sensitive to the value of this parameter.

We present a time series forecasting methodology and applies it to generate one-step-ahead predictions for two daily foreign exchange spot rate time series. The methodology draws from the disciplines of chaotic time series analysis, clustering, artificial neural networks and evolutionary computation. In brief, clustering is applied to identify neighborhoods in the reconstructed state space of the system; and subsequently neural networks are trained to model the dynamics of each neighborhood separately. The results obtained through this approach are promising.