Fitness landscape analysis provides insights into optimization problems, informing algorithms' design and identifying properties that influence performance. While understanding global landscape structure is critical, tools for analyzing and visualizing multi-objective, high-dimensional optimization problems remain limited. Recent models, such as Pareto local optima solution networks (PLOS-nets), primarily focus on small instances and binary representations, posing challenges for extension to more complex domains. To address this gap, we introduce mo-LON/D, a decomposition-based local optima network model for multi-objective landscapes. This model partitions a multi-objective problem into scalar sub-problems, constructs standard single-objective local optima networks (LONs) for each, and integrates them via a graph union. We validate mo-LON/D on fully enumerated bi-objective ρmnk-landscapes and contrast its structural features against PLOS-nets both visually and quantitatively. Despite the inherent sampling involved in scalarization, our results indicate that mo-LON/D offers comparable explanatory power (and even higher correlations) with respect to the performance of state-of-the-art algorithms. By harnessing established sampling techniques from single-objective research, mo-LON/D could potentially provide a scalable framework for characterizing complex multi-objective landscapes.

Local Optima Networks (LON)s have been used extensively to understand the global structure of optimisation problems and to study algorithm behaviour. The central idea is to compress the search space into a graph object capturing the local optima along with information on their basins of attraction and the connections between them. This enables the visualisation of high dimensional search spaces, and the extraction of metrics for characterising and contrasting different problem instances. In this paper we extend the canonical LON definition to encompass search spaces with constraints. We use a well-known pairwise comparison operator for constrained problems, and capture the features of the constraint violation landscape that present a challenge for such an operator, such as infeasible local traps. The concept of a constrained LON is illustrated through a range of problem instances. Most problems in the context of real-world applications have constraints. By including the notion of feasibility and constraint violation into the definition of LONs, it becomes possible to use this powerful analysis tool on a much wider range of real-world problems.

This study introduces novel tunable benchmark test problems for continuous box-constrained multimodal optimization (MMO). It first introduces a new approach to control the non-uniformity of distribution of global minima, a notable challenge in MMO. Then, it builds upon an existing procedure to create composite functions in which the severity of two distinguishable groups of MMO challenges can be controlled: i) challenges shared with global optimization (GO), such as ill-conditioning, and ii) challenges specific to MMO, such as non-uniform distribution of global minima. Eight new scalable and tunable MMO functions are then proposed, based on which a test suite of 16 continuous MMO test problems is suggested. This test suite is designed to be i) comprehensive, which means they simulate most, if not all, prominent challenges associated with MMO, ii) discriminating, which means test problems can disclose the gap between the performance of diverse MMO methods, and iii) illuminating, which means test problems can reveal and compare strengths and weaknesses of MMO methods. The code of these problems is made available in two different programming languages to encourage its adoption by the research community.

Abstract The adversarial attack can force a CNN-based model to produce an incorrect output by craftily manipulating human-imperceptible input. Exploring such perturbations can help us gain a deeper understanding of the vulnerability of neural networks, and provide robustness to deep learning against miscellaneous adversaries. Despite extensive studies focusing on the robustness of image, audio, and NLP, works on adversarial examples of visual object tracking—especially in a black-box manner—are quite lacking. In this paper, we propose a novel adversarial attack method to generate noises for single object tracking under black-box settings, where perturbations are merely added on initialized frames of tracking sequences, which is difficult to be noticed from the perspective of a whole video clip. Specifically, we divide our algorithm into three components and exploit reinforcement learning for localizing important frame patches precisely while reducing unnecessary computational queries overhead. Compared to existing techniques, our method requires less time to perturb videos, but to manipulate competitive or even better adversarial performance. We test our algorithm in both long-term and short-term datasets, including OTB100, VOT2018, UAV123, and LaSOT. Extensive experiments demonstrate the effectiveness of our method on three mainstream types of trackers: discrimination, Siamese-based, and reinforcement learning-based trackers. We release our attack tool, DIMBA, via GitHub https://github.com/TrustAI/DIMBA for use by the community.

No abstract available.

The ACM Proceedings of the ACM on Measurement and Analysis of Computing Systems (POMACS) focuses on the measurement and performance evaluation of computer systems and operates in close collaboration with the ACM Special Interest Group SIGMETRICS. All ...

We present a new algorithm for efficiently solving expensive multi-and many-objective, black-box optimisation problems by interactively incorporating the preferences of an external decision maker. We define a novel acquisition function which combines the maximin distance to the summary attainment front with a set of aspirational objective-space target points chosen by the decision maker. This drives an exploitative multi-surrogate model to quickly converge to solutions favourable to the decision maker, without relying on surrogate posterior uncertainty estimates or arbitrary objective weighting.

Visualizing the search behavior of a series of points or populations in their native domain is critical in understanding biases and attractors in an optimization process. Distance-based many-objective optimization test problems have been developed to facilitate visualization of search behavior in a 2-D design space with arbitrarily many objective functions. Previous works have proposed a few commonly seen problem characteristics into this problem framework, such as the definition of disconnected Pareto sets and dominance resistant regions of the design space. The authors’ previous work has advanced this research further by providing a problem generator to automatically create user-defined problem instances featuring any combination of these problem features as well as newly introduced ones, such as landscape discontinuities, varying objective ranges, and neutrality. This work makes a number of additional contributions including the proposal of an enhanced, open-source feature-rich problem generator that can create user-defined problem instances exhibiting a range of problem features—some of which are newly introduced here or form extensions of existing features. A comprehensive validation of the problem generator is also provided using popular multiobjective optimization algorithms, and some problem generator settings to create instances exhibiting different challenges for an optimizer are identified.

Efficient methods for optimising expensive black-box problems with multiple objectives can often themselves become prohibitively expensive as the number of objectives is increased. We propose an infill criterion based on the distance to the summary attainment front which does not rely on the expensive hypervolume or expected improvement computations, which are the principal causes of poor dimensional scaling in current state-of-the-art approaches. By evaluating performance on the well-known Walking Fish Group problem set, we show that our method delivers similar performance to the current state-of-the-art. We further show that methods based on surrogate mean predictions are more often than not superior to the widely used expected improvement, suggesting that the additional exploration produced by accounting for the uncertainty in the surrogate's prediction of the optimisation landscape is often unnecessary and does not aid convergence towards the Pareto front.

Batch Bayesian optimisation (BO) is a successful technique for the optimisation of expensive black-box functions. Asynchronous BO can reduce wallclock time by starting a new evaluation as soon as another finishes, thus maximising resource utilisation. To maximise resource allocation, we develop a novel asynchronous BO method, AEGiS (Asynchronous $\epsilon$-Greedy Global Search) that combines greedy search, exploiting the surrogate’s mean prediction, with Thompson sampling and random selection from the approximate Pareto set describing the trade-off between exploitation (surrogate mean prediction) and exploration (surrogate posterior variance). We demonstrate empirically the efficacy of AEGiS on synthetic benchmark problems, meta-surrogate hyperparameter tuning problems and real-world problems, showing that AEGiS generally outperforms existing methods for asynchronous BO. When a single worker is available performance is no worse than BO using expected improvement.

It is particularly challenging for evolutionary algorithms to quickly converge to the Pareto front in large-scale multiobjective optimization. To tackle this problem, this article proposes a large-scale multiobjective evolutionary algorithm assisted by some selected individuals generated by directed sampling (DS). At each generation, a set of individuals closer to the ideal point is chosen for performing a DS in the decision space, and those nondominated ones of the sampled solutions are used to assist the reproduction to improve the convergence in evolutionary large-scale multiobjective optimization. In addition, elitist nondominated sorting is adopted complementarily for environmental selection with a reference vector-based method in order to maintain diversity of the population. Our experimental results show that the proposed algorithm is highly competitive on large-scale multiobjective optimization test problems with up to 5000 decision variables compared to five state-of-the-art multiobjective evolutionary algorithms.

The performance of acquisition functions for Bayesian optimisation to locate the global optimum of continuous functions is investigated in terms of the Pareto front between exploration and exploitation. We show that Expected Improvement (EI) and the Upper Confidence Bound (UCB) always select solutions to be expensively evaluated on the Pareto front, but Probability of Improvement is not guaranteed to do so and Weighted Expected Improvement does so only for a restricted range of weights. We introduce two novel -greedy acquisition functions. Extensive empirical evaluation of these together with random search, purely exploratory, and purely exploitative search on 10 benchmark problems in 1 to 10 dimensions shows that -greedy algorithms are generally at least as effective as conventional acquisition functions (e.g., EI and UCB), particularly with a limited budget. In higher dimensions, -greedy approaches are shown to have improved performance over conventional approaches. These results are borne out on a real-world computational fluid dynamics optimisation problem and a robotics active learning problem. Our analysis and experiments suggest that the most effective strategy, particularly in higher dimensions, is to be mostly greedy, occasionally selecting a random exploratory solution.

Bayesian optimisation is a popular surrogate model-based approach for optimising expensive black-box functions. Given a surrogate model, the next location to expensively evaluate is chosen via maximisation of a cheap-to-query acquisition function. We present an ϵ-greedy procedure for Bayesian optimisation in batch settings in which the black-box function can be evaluated multiple times in parallel. Our ϵ-shotgun algorithm leverages the model's prediction, uncertainty, and the approximated rate of change of the landscape to determine the spread of batch solutions to be distributed around a putative location. The initial target location is selected either in an exploitative fashion on the mean prediction, or - with probability ϵ - from elsewhere in the design space. This results in locations that are more densely sampled in regions where the function is changing rapidly and in locations predicted to be good (i.e. close to predicted optima), with more scattered samples in regions where the function is flatter and/or of poorer quality. We empirically evaluate the ϵ-shotgun methods on a range of synthetic functions and two real-world problems, finding that they perform at least as well as state-of-the-art batch methods and in many cases exceed their performance.

Many data structures have been developed over the last two decades for the storage and efficient update of unconstrained sets of mutually non-dominating solutions. Typically, analysis has been provided in the original works for these data structures in terms of worst/average case complexity performance. Often, however, other aspects such as rebalancing costs of underlying data structures, cache sizes, etc., can also significantly affect behaviour. Empirical performance comparison has often (but not always) been limited to run-time comparison with a basic linear list. No comprehensive comparison between the different specialised data structures proposed in the last two decades has thus far been undertaken. We take significant strides in addressing this here. Eight data structures from the literature are implemented within the same overarching open source Java framework. We additionally highlight and rectify some errors in published work --- and offer additional efficiency gains. Run-time performances are compared and contrasted, using data sequences embodying a number of different characteristics. We show that in different scenarios different data structures are preferable, and that those with the lowest big O complexity are not always the best performing. We also find that performance profiles can vary drastically with computational architecture, in a non-linear fashion.

The hypervolume (or S-metric) is a widely used quality measure employed in the assessment of multi- and many-objective evolutionary algorithms. It is also directly integrated as a component in the selection mechanism of some popular optimisers. Exact hypervolume calculation becomes prohibitively expensive in real-time applications as the number of objectives increases and/or the approximation set grows. Assuch, Monte Carlo (MC) sampling is often used to estimate its value rather than exactly calculating it. This estimation is inevitably subject to error. As standard with Monte Carlo approaches, the standard error decreases with the square root of the number of MC samples. We propose a number of real-time hypervolume estimation methods for unconstrained archives --- principally for use in real-time convergence analysis. Furthermore, we show how the number of domination comparisons can be considerably reduced by exploiting incremental properties of the approximated Pareto front. In these methods the estimation error monotonically decreases over time for (i) a capped budget of samples per algorithm generation and (ii) a fixed budget of dedicated computation time per optimiser generation for new MC samples. Results are provided using an illustrative worst-case scenario with rapid archive growth, demonstrating the orders-of-magnitude of speed-up possible.

In optimiser analysis and design it is informative to visualise how a search point/population moves through the design space over time. Visualisable distance-based many-objective optimisation problems have been developed whose design space is in two-dimensions with arbitrarily many objective dimensions. Previous work has shown how disconnected Pareto sets may be formed, how problems can be projected to and from arbitrarily many design dimensions, and how dominance resistant regions of design space may be defined. Most recently, a test suite has been proposed using distances to lines rather than points. However, active use of visualisable problems has been limited. This may be because the type of problem characteristics available has been relatively limited compared to many practical problems (and non-visualisable problem suites). Here we introduce the mechanisms required to embed several widely seen problem characteristics in the existing problem framework. These include variable density of solutions in objective space, landscape discontinuities, varying objective ranges, neutrality, and non-identical disconnected Pareto set regions. Furthermore, we provide an automatic problem generator (as opposed to hand-tuned problem definitions). The flexibility of the problem generator is demonstrated by analysing the performance of popular optimisers on a range of sampled instances.

Real-world optimization problems are often subject to several constraints which are expensive to evaluate in terms of cost or time. Although a lot of effort is devoted to make use of surrogate models for expensive optimization tasks, not many strong surrogate-assisted algorithms can address the challenging constrained problems. Efficient Global Optimization (EGO) is a Kriging-based surrogate-assisted algorithm. It was originally proposed to address unconstrained problems and later was modified to solve constrained problems. However, these type of algorithms still suffer from several issues, mainly: (1) early stagnation, (2) problems with multiple active constraints and (3) frequent crashes. In this work, we introduce a new EGO-based algorithm which tries to overcome these common issues with Kriging optimization algorithms. We apply the proposed algorithm on problems with dimension d ≤ 4 from the G-function suite [16] and on an airfoil shape example.

The allocation of university staff to teaching exhibits a range of often competing objectives. We illustrate the use of an augmented version of NSGA-III to undertake the seven-objective optimisation of this problem, to find a trade-off front for a university department using real world data. We highlight its use in decision-making, and compare solutions identified to an actual allocation made prior to the availability of the optimisation tool. The criteria we consider include minimising the imbalance in workload distribution among staff; minimising the average load; minimising the maximum peak load; minimising the staff per module; minimising staff dissatisfaction with teaching allocations; and minimising the variation from the previous year's allocation (allocation churn). We derive mathematical forms for these various criteria, and show we can determine the maximum possible values for all criteria and the minimum values for most exactly (with lower bounds on the remaining criteria). For many of the objectives, when considered in isolation, an optimal solution may be obtained rapidly. We demonstrate the advantage of utilising such extreme solutions to drastically improve the optimisation efficiency in this many-objective optimisation problem. We also identify issues that NSGA-III can experience due to selection between generations.

Many multi-objective optimisation problems incorporate computationally or financially expensive objective functions. State-of-the-art algorithms therefore construct surrogate model(s) of the parameter space to objective functions mapping to guide the choice of the next solution to expensively evaluate. Starting from an initial set of solutions, an infill criterion - a surrogate-based indicator of quality - is extremised to determine which solution to evaluate next, until the budget of expensive evaluations is exhausted. Many successful infill criteria are dependent on multi-dimensional integration, which may result in infill criteria that are themselves impractically expensive. We propose a computationally cheap infill criterion based on the minimum probability of improvement over the estimated Pareto set. We also present a range of set-based scalarisation methods modelling hypervolume contribution, dominance ratio and distance measures. These permit the use of straightforward expected improvement as a cheap infill criterion. We investigated the performance of these novel strategies on standard multi-objective test problems, and compared them with the popular SMS-EGO and ParEGO methods. Unsurprisingly, our experiments show that the best strategy is problem dependent, but in many cases a cheaper strategy is at least as good as more expensive alternatives.

An underlying problem in genetic programming (GP) is how to ensure sufficient useful diversity in the population during search. Having a wide range of diverse (sub)component structures available for recombination and/or mutation is important in preventing premature converge. We propose two new fitness disaggregation approaches that make explicit use of the information in the test cases (i.e., program semantics) to preserve diversity in the population. The first method preserves the best programs which pass each individual test case, the second preserves those which are non-dominated across test cases (multi-objectivisation). We use these in standard GP, and compare them to using standard fitness sharing, and using standard (aggregate) fitness in tournament selection. We also examine the effect of including a simple anti-bloat criterion in the selection mechanism. We find that the non-domination approach, employing anti-bloat, significantly speeds up convergence to the optimum on a range of standard Boolean test problems. Furthermore, its best performance occurs with a considerably smaller population size than typically employed in GP.

Mesh network topologies are becoming increasingly popular in battery-powered wireless sensor networks, primarily because of the extension of network range. However, multihop mesh networks suffer from higher energy costs, and the routing strategy employed directly affects the lifetime of nodes with limited energy resources. Hence when planning routes there are trade-offs to be considered between individual and system-wide battery lifetimes. We present a multiobjective routing optimisation approach using hybrid evolutionary algorithms to approximate the optimal trade-off between the minimum lifetime and the average lifetime of nodes in the network. In order to accomplish this combinatorial optimisation rapidly, our approach prunes the search space using k-shortest path pruning and a graph reduction method that finds candidate routes promoting long minimum lifetimes. When arbitrarily many routes from a node to the base station are permitted, optimal routes may be found as the solution to a well-known linear program. We present an evolutionary algorithm that finds good routes when each node is allowed only a small number of paths to the base station. On a real network deployed in the Victoria & Albert Museum, London, these solutions, using only three paths per node, are able to achieve minimum lifetimes of over 99% of the optimum linear program solution's time to first sensor battery failure.

As the methods for evolutionary multiobjective optimization (EMO) mature and are applied to a greater number of real-world problems, there has been gathering interest in the effect of uncertainty and noise on multiobjective optimization, specifically how algorithms are affected by it, how to mitigate its effects, and whether some optimizers are better suited to dealing with it than others. Here we address the problem of uncertain evaluation, in which the uncertainty can be modeled as an additive noise in objective space. We develop a novel algorithm, the rolling tide evolutionary algorithm (RTEA), which progressively improves the accuracy of its estimated Pareto set, while simultaneously driving the front toward the true Pareto front. It can cope with noise whose characteristics change as a function of location (both design and objective), or which alter during the course of an optimization. Four state-of-the-art noise-tolerant EMO algorithms, as well as four widely used standard EMO algorithms, are compared to RTEA on 70 instances of ten continuous space test problems from the CEC'09 multiobjective optimization test suite. Different instances of these problems are generated by modifying them to exhibit different types and intensities of noise. RTEA seems to provide competitive performance across both the range of test problems used and noise types.

We present a new multi-modal evolutionary opti-miser, the niching migratory multi-swarm optimiser (NMMSO), which dynamically manages many particle swarms. These sub-swarms are concerned with optimising separate local modes, and employ measures to allow swarm elements to migrate away from their parent swarm if they are identified as being in the vicinity of a separate peak, and to merge swarms together if they are identified as being concerned with the same peak. We employ coarse peak identification to facilitate the mode identification required. Swarm members are not constrained to particular sub-regions of the parameter space, however members are initialised in the vicinity of a swarm's local mode estimate. NMMSO is shown to cope with a range of problem types, and to produce results competitive with the state-of-the-art on the CEC 2013 multi-modal optimisation competition test problems, providing new benchmark results in the field.

In many multi-objective problems the objective values assigned to a particular design can change during the course of an optimisation. This may be due to dynamic changes in the problem itself, or updates to estimated objectives in noisy problems. In these situations, designs which are non-dominated at one time step may become dominated later not just because a new and better solution has been found, but because the existing solution's performance has degraded. Likewise, a dominated solution may later be identified as non-dominated because its objectives have comparatively improved. We propose management algorithms based on recording single "guardian dominators" for each solution which allow rapid discovery and updating of the non-dominated subset of solutions evaluated by an optimiser. We examine the computational complexity of our proposed approach, and compare the performance of different ways of selecting the guardian dominators.

Mesh network topologies are becoming increasingly popular in battery powered wireless sensor networks, primarily due to the extension of network range and resilience against routing failures. However, multi-hop mesh networks suffer from higher energy costs, and the routing strategy directly affects the lifetime of nodes with limited energy sources. Hence while planning routes there are trade-offs to be considered between individual and system-wide battery lifetimes. We present a novel multi-objective routing optimisation approach using evolutionary algorithms to approximate the optimal trade-off between minimum lifetime and the average lifetime of nodes in the network. In order to accomplish this combinatorial optimisation rapidly and thus permit dynamic optimisation for self-healing networks, our approach uses novel $k$-shortest paths based search space pruning in conjunction with a new edge metric, which associates the energy cost at a pair of nodes with the link between them. We demonstrate our solution on a real network, deployed in the Victoria \& Albert Museum, London. We show that this approach provides better trade-off solutions in comparison to the minimum energy option, and how a combination of solutions over the lifetime of the network can enhance the overall minimum lifetime.

Multi-objective optimisation yields an estimated Pareto front of mutually non- dominating solutions, but with more than three objectives, understanding the relationships between solutions is challenging. Natural solutions to use as landmarks are those lying near to the edges of the mutually non-dominating set. We propose four definitions of edge points for many-objective mutually non-dominating sets and examine the relations between them. The first defines edge points to be those that extend the range of the attainment surface. This is shown to be equivalent to finding points which are not dominated on projection onto subsets of the objectives. If the objectives are to be minimised, a further definition considers points which are not dominated under maximisation when projected onto objective subsets. A final definition looks for edges via alternative projections of the set. We examine the relations between these definitions and their efficacy in many dimensions for synthetic concave- and convex-shaped sets, and on solutions to a prototypical many-objective optimisation problem, showing how they can reveal information about the structure of the estimated Pareto front. We show that the "controlling dominance area of solutions" modification of the dominance relation can be effectively used to locate edges and interior points of high-dimensional mutually non-dominating sets.

Multi-objective optimisation yields an estimated Pareto front of mutually non-dominating solutions, but with more than three objectives understanding the relationships between solutions is challenging. Natural solutions to use as landmarks are those lying near to the edges of the mutually non-dominating set. We propose four definitions of edge points for many-objective mutually non-dominating sets and examine the relations between them.

The particle swarm optimisation (PSO) heuristic has been used for a number of years now to perform multi-objective optimisation, however its performance on many-objective optimisation (problems with four or more competing objectives) has been less well examined. Many-objective optimisation is well-known to cause problems for Pareto-based evolutionary optimisers, so it is of interest to see how well PSO copes in this domain, and how non-Pareto quality measures perform when integrated into PSO. Here we compare and contrast the performance of canonical PSO, using a wide range of many-objective quality measures, on a number of different parametrised test functions for up to 20 competing objectives. We examine the use of eight quality measures as selection operators for guides when truncated non-dominated archives of guides are maintained, and as maintenance operators, for choosing which solutions should be maintained as guides from one generation to the next. We find that the Controlling Dominance Area of Solutions approach performs exceptionally well as a quality measure to determine archive membership for global and local guides. As a selection operator, the Average Rank and Sum of Ratios measures are found to generally provide the best performance.

As many-objective optimization algorithms mature, the problem owner is faced with visualizing and understanding a set of mutually nondominating solutions in a high dimensional space. We review existing methods and present new techniques to address this problem. We address a common problem with the well-known heatmap visualization, since the often arbitrary ordering of rows and columns renders the heatmap unclear, by using spectral seriation to rearrange the solutions and objectives and thus enhance the clarity of the heatmap. A multiobjective evolutionary optimizer is used to further enhance the simultaneous visualization of solutions in objective and parameter space. Two methods for visualizing multiobjective solutions in the plane are introduced. First, we use RadViz and exploit interpretations of barycentric coordinates for convex polygons and simplices to map a mutually nondominating set to the interior of a regular convex polygon in the plane, providing an intuitive representation of the solutions and objectives. Second, we introduce a new measure of the similarity of solutions - the dominance distance - which captures the order relations between solutions. This metric provides an embedding in Euclidean space, which is shown to yield coherent visualizations in two dimensions. The methods are illustrated on standard test problems and data from a benchmark many-objective problem.

Short Term Conflict Alert (STCA) systems provide warnings to air traffic controllers if aircraft are in danger of becoming too close. They are complex software programs, with many inter-dependent parameters that must be adjusted to achieve the best trade-off between wanted and nuisance alerts. We describe a multi-archive evolutionary algorithm for optimising regional parameter subsets in parallel, reducing the number of evaluations required to generate an estimated Pareto optimal Receiver Operating Characteristic (ROC), showing that it provides superior results to traditional single-archived algorithms. A method of `aggressive' optimisation, designed to explore unknown parameter ranges in a `safe' manner, is shown to yield more extensive and better converged estimated Pareto fronts.

We introduce novel methods of visualising and ordering multi-and many-objective populations. We compare individuals by the probability that one will beat another in a tournament on a randomly selected objective. This defines a weighted directed graph representing the population. We introduce a novel graphical representation of the many objective population based on Pareto shells. We examine leagues, Pareto shells, preference ordering, average rank, outflow, the stationary distribution and the power index for ordering the population finding that the average rank is equivalent to outflow and that these together with the power index are generally superior. Finally, we show how to seriate objectives to enhance the interpretability of heatmap visualisations.

We describe a Bayesian framework for active learning for non-separable data, which incorporates a query density to explicitly model how new data is to be sampled. The model makes no assumption of independence between queried data-points; rather it updates model parameters on the basis of both observations and how those observations were sampled. A `hypothetical' look-ahead is employed to evaluate expected cost in the next time-step. We show the efficacy of this algorithm on the probabilistic high-low game which is a non-separable generalisation of the separable high-low game introduced by Seung et al. Our results indicate that the active Bayes algorithm performs significantly better than passive learning even when the overlap region is wide, covering over 30% of the feature space.

When optimising receiver operating characteristic (ROC) curves there is an inherent degree of uncertainty associated with the operating point evaluation of a model parameterisation x. This is due to the finite amount of training data used to evaluate the true and false positive rates of x. The uncertainty associated with any particular x can be reduced, but only at the computation cost of evaluating more data. Here we explicitly represent this uncertainty through the use of probabilistically non-dominated archives, and show how expensive ROC optimisation problems may be tackled by only evaluating a small subset of the available data at each generation of an optimisation algorithm. Illustrative results are given on data sets from the well known UCI machine learning repository.

Simulated annealing is a provably convergent optimizer for single-objective problems. Previously proposed multiobjective extensions have mostly taken the form of a single-objective simulated annealer optimizing a composite function of the objectives. We propose a multiobjective simulated annealer utilizing the relative dominance of a solution as the system energy for optimization, eliminating problems associated with composite objective functions. We also propose a method for choosing perturbation scalings promoting search both towards and across the Pareto front. We illustrate the simulated annealer's performance on a suite of standard test problems and provide comparisons with another multiobjective simulated annealer and the NSGA-II genetic algorithm. The new simulated annealer is shown to promote rapid convergence to the true Pareto front with a good coverage of solutions across it comparing favorably with the other algorithms. An application of the simulated annealer to an industrial problem, the optimization of a code-division-multiple access (CDMA) mobile telecommunications network's air interface, is presented and the simulated annealer is shown to generate nondominated solutions with an even and dense coverage that outperforms single objective genetic algorithm optimizers.

Bayesian averaging (BA) over ensembles of decision models allows evaluation of the uncertainty of decisions that is of crucial importance for safety-critical applications such as medical diagnostics. The interpretability of the ensemble can also give useful information for experts responsible for making reliable decisions. For this reason, decision trees (DTs) are attractive decision models for experts. However, BA over such models makes an ensemble of DTs uninterpretable. In this paper, we present a new approach to probabilistic interpretation of Bayesian DT ensembles. This approach is based on the quantitative evaluation of uncertainty of the DTs, and allows experts to find a DT that provides a high predictive accuracy and confident outcomes. To make the BA over DTs feasible in our experiments, we use a Markov Chain Monte Carlo technique with a reversible jump extension. The results obtained from clinical data show that in terms of predictive accuracy, the proposed method outperforms the maximum a posteriori (MAP) method that has been suggested for interpretation of DT ensembles.

Many safety related and critical systems warn of potentially dangerous events; for example, the short term conflict alert (STCA) system warns of airspace infractions between aircraft. Although installed with current technology, such critical systems may become out of date due to changes in the circumstances in which they function, operational procedures, and the regulatory environment. Current practice is to "tune," by hand, the many parameters governing the system in order to optimize the operating point in terms of the true positive and false positive rates, which are frequently associated with highly imbalanced costs. We cast the tuning of critical systems as a multiobjective optimization problem. We show how a region of the optimal receiver operating characteristic (ROC) curve may be obtained, permitting the system operators to select the operating point. We apply this methodology to the STCA system, using a multiobjective (1+1) evolution strategy, showing that we can improve upon the current hand-tuned operating point, as well as providing the salient ROC curve describing the true positive versus false positive tradeoff. We also provide results for three-objective optimization of the alert response time in addition to the true and false positive rates. Additionally, we illustrate the use of bootstrapping for representing evaluation uncertainty on estimated Pareto fronts, where the evaluation of a system is based upon a finite set of representative data.

There has been only limited discussion on the effect of uncertainty and noise in multi-objective optimization problems and how to deal with it. We address this problem by assessing the probability of dominance and maintaining an archive of solutions which are, with some known probability, mutually non-dominating. We examine methods for estimating the probability of dominance. These depend crucially on estimating the effective noise variance and we introduce a novel method of learning the variance during optimization. Probabilistic domination contours are presented as a method for conveying the confidence that may be placed in objectives that are optimized in the presence of uncertainty

For the purposes of forecasting (or classification) tasks neural networks (NNs) are typically trained with respect to Euclidean distance minimization. This is commonly the case irrespective of any other end user preferences. In a number of situations, most notably time series forecasting, users may have other objectives in addition to Euclidean distance minimization. Recent studies in the NN domain have confronted this problem by propagating a linear sum of errors. However this approach implicitly assumes a priori knowledge of the error surface defined by the problem, which, typically, is not the case. This study constructs a novel methodology for implementing multiobjective optimization within the evolutionary neural network (ENN) domain. This methodology enables the parallel evolution of a population of ENN models which exhibit estimated Pareto optimality with respect to multiple error measures. A new method is derived from this framework, the Pareto evolutionary neural network (Pareto-ENN). The Pareto-ENN evolves a population of models that may be heterogeneous in their topologies inputs and degree of connectivity, and maintains a set of the Pareto optimal ENNs that it discovers. New generalization methods to deal with the unique properties of multiobjective error minimization that are not apparent in the uni-objective case are presented and compared on synthetic data, with a novel method based on bootstrapping of the training data shown to significantly improve generalization ability. Finally experimental evidence is presented in this study demonstrating the general application potential of the framework by generating populations of ENNs for forecasting 37 different international stock indexes.

Simulated annealing (SA) is a provably convergent optimiser for single-objective (SO) problems. Previously proposed MO extensions have mostly taken the form of an SO SA optimising a composite function of the objectives. We propose an MO SA utilising the relative dominance of a solution as the system energy for optimisation, eliminating problems associated with composite objective functions. We also propose a method for choosing perturbation scalings promoting search both towards and across the Pareto front. We illustrate the SA's performance on standard test problems. The new SA is shown to promote rapid convergence to the true Pareto front with a good coverage of points across it.

Multiobjective evolutionary algorithms (MOEAs) have been the subject of numerous studies over the past 20 years. Recent work has highlighted the use of an active archive of elite, nondominated solutions to improve the optimization speed of these algorithms. However, preserving all elite individuals is costly in time (due to the linear comparison with all archived solutions needed before a new solution can be inserted into the archive). Maintaining an elite population of a fixed maximum size (by clustering or other means) alleviates this problem, but can cause retreating (or oscillitory) and shrinking estimated Pareto fronts - which can affect the efficiency of the search process. New data structures are introduced to facilitate the use of an unconstrained elite archive, without the need for a linear comparison to the elite set for every new individual inserted. The general applicability of these data structures is shown by their use in an evolution-strategy-based MOEA and a genetic-algorithm-based MOEA. It is demonstrated that MOEAs using the new data structures run significantly faster than standard, unconstrained archive MOEAs, and result in estimated Pareto fronts significantly ahead of MOEAs using a constrained archive. It is also shown that the use of an unconstrained elite archive permits robust criteria for algorithm termination to be used, and that the use of the data structure can also be used to increase the speed of algorithms using /spl epsi/-dominance methods.

In this paper, the concept of long memory systems for forecasting is developed. The pattern modelling and recognition system and fuzzy single nearest neighbour methods are introduced as local approximation tools for forecasting. Such systems are used for matching the current state of the time-series with past states to make a forecast. In the past, the PMRS system has been successfully used for forecasting the Santa Fe competition data. In this paper, we forecast the FTSE 100 and 250 financial returns indices, as well as the stock returns of five FTSE 100 companies and compare the results of the two different systems with those of exponential smoothing and random walk on seven different error measures. The results show that pattern recognition based approaches in time-series forecasting are highly accurate. Simple theoretical trading strategies are also mentioned, highlighting real applications of the system.

We study the identification of masses in digital mammograms using texture analysis. A number of texture measures are calculated for bilateral difference images showing regions of interest. The measurements are made on co-occurrence matrices in four different direction giving a total of seventy features. These features include the ones proposed by Haralick et al. (1973) and Chan et al. (1997). We study a total of 144 breast images from the MIAS database. The dimensionality of the dataset is reduced using principal components analysis (PCA), PCA components are classified using both multilayer perceptron networks using backpropagation (MLP) and radial basis functions based on Gaussian kernels (RBF). The two methods are compared on the same data across a ten fold cross-validation. The results are generated on the average recognition rate over these folds on correctly recognising masses and normal regions. Further analysis is based on the receiver operating characteristic (ROC) plots. The best results show recognition rates of 77% correct recognition and an area under the ROC curve value Az of 0.74.