Nowadays we witness a miniaturisation trend in the semiconductor industry backed up by groundbreaking discoveries and designs in nanoscale characterisation and fabrication. To facilitate the trend and produce ever smaller, faster and cheaper computing devices, the size of nanoelectronic devices is now reaching the scale of atoms or molecules - a technical goal undoubtedly demanding for novel devices. Following the trend, we explore an unconventional route of implementing reservoir computing on a single protein molecule and introduce neuromorphic connectivity with a small-world networking property. We have chosen Izhikevich spiking neurons as elementary processors, corresponding to the atoms of verotoxin protein, and its molecule as a `hardware' architecture of the communication networks connecting the processors. We apply on a single readout layer, various training methods in a supervised fashion to investigate whether the molecular structured Reservoir Computing (RC) system is capable to deal with machine learning benchmarks. We start with the Remote Supervised Method, based on Spike-Timing-Dependent-Plasticity, and carry on with linear regression and scaled conjugate gradient back-propagation training methods. The RC network is evaluated as a proof-of-concept on the handwritten digit images from the standard MNIST and the extended MNIST datasets and demonstrates acceptable classification accuracies in comparison with other similar approaches.

Hypergraph partitioning (HGP) is an NP-hard problem that occurs in many computer science applications where it is necessary to reduce large problems into a number of smaller, computationally tractable subproblems. Current techniques use a multilevel approach wherein an initial partitioning is performed after compressing the hypergraph to a predetermined level. This level is typically chosen to produce very coarse hypergraphs in which heuristic algorithms are fast and effective. This paper presents a novel memetic algorithm which remains effective on larger initial hypergraphs. This enables the exploitation of information that can be lost during coarsening and results in improved final solution quality. We use this algorithm to present an empirical analysis of the space of possible initial hypergraphs in terms of its searchability at different levels of coarsening. We find that the best results arise at coarsening levels unique to each hypergraph. Based on this, we introduce an adaptive scheme that stops coarsening when the rate of information loss in a hypergraph becomes nonlinear and show that this produces further improvements. The results show that we have identified a valuable role for evolutionary algorithms within the current state-of-the-art HGP framework.

People are not infallible consistent “oracles”: their confidence in decision-making may vary significantly between tasks and over time. We have previously reported the benefits of using an interface and algorithms that explicitly captured and exploited users’ confidence: error rates were reduced by up to 50% for an industrial multi-class learning problem; and the number of interactions required in a design-optimisation context was reduced by 33%. Having access to users’ confidence judgements could significantly benefit intelligent interactive systems in industry, in areas such as intelligent tutoring systems and in health care. There are many reasons for wanting to capture information about confidence implicitly . Some are ergonomic, but others are more “social”—such as wishing to understand (and possibly take account of) users’ cognitive state without interrupting them. We investigate the hypothesis that users’ confidence can be accurately predicted from measurements of their behaviour. Eye-tracking systems were used to capture users’ gaze patterns as they undertook a series of visual decision tasks, after each of which they reported their confidence on a 5-point Likert scale. Subsequently, predictive models were built using “conventional” machine learning approaches for numerical summary features derived from users’ behaviour. We also investigate the extent to which the deep learning paradigm can reduce the need to design features specific to each application by creating “gaze maps”—visual representations of the trajectories and durations of users’ gaze fixations—and then training deep convolutional networks on these images. Treating the prediction of user confidence as a two-class problem (confident/not confident), we attained classification accuracy of 88% for the scenario of new users on known tasks, and 87% for known users on new tasks. Considering the confidence as an ordinal variable, we produced regression models with a mean absolute error of ≈0.7 in both cases. Capturing just a simple subset of non-task-specific numerical features gave slightly worse, but still quite high accuracy (e.g., MAE ≈ 1.0). Results obtained with gaze maps and convolutional networks are competitive, despite not having access to longer-term information about users and tasks, which was vital for the “summary” feature sets. This suggests that the gaze-map-based approach forms a viable, transferable alternative to handcrafting features for each different application. These results provide significant evidence to confirm our hypothesis, and offer a way of substantially improving many interactive artificial intelligence applications via the addition of cheap non-intrusive hardware and computationally cheap prediction algorithms.

Surrogate-assisted Optimisation has proven success in the continuous domain, but only recently begun to be explored for other representations, in particular permutations. The use of Gaussian kernel-based models has been proposed, but only tested on small problems. This case study considers much larger instances, in the experimental setting of a real-world ordering problem. We also investigate whether creating models using different distance metrics generates a diverse ensemble. Results demonstrate the following effects of use to other researchers: (i) Numerical instability in matrix inversion is a factor across all metrics, regardless of algorithm used. The likelihoood increases significantly once the models are parameterised using evolved solutions as well as the initial random population; (ii) This phase transition is also observed in different indicators of model quality. For example, predictive accuracy typically decreases once models start to include data from evolved samples. We explain this transition in terms of the distribution of samples and Gaussian kernel basis of the models; (iii) Measures of how well models predict rank-orderings are less affected; (iv) Benchmark comparisons show that using surrogate models decreases the number of evaluations required to find good solutions, without affecting quality.

Early lifecycle software design is an intensely human activity in which design scale and complexity can place a high cognitive load on the software designer. Recently, the use of evolutionary search has been suggested to yield insights in the nature of software engineering problems generally, and so we have applied dynamic evolutionary computation using self-adaptive mutation to the object-oriented software design search space. Using three design problem instances of varying scale and complexity, initial investigations of the discrete search landscape reveal a redundancy in genotype-to-phenotype mapping enabling flexible and effective exploration. In further experiments, mutation probabilities and population diversity are observed to significantly increase in the face of increasing problem scale, but not for increasing complexity (in problems of the same scale). Based on these findings, we conclude that design problem scale rather than complexity has an effect on the software design process, emphasizing the role of decomposition as a design technique.

In this paper Ant Colony Optimisation (ACO) is applied in the field of Statistical Disclosure Control (SDC) for the first time. It has been applied to a permutation problem found in Cell Suppression. ACO has successfully improved the suppression patterns created to protect published statistical tables but when compared to using the Genetic Algorithm (GA) it has not performed as well. It has however performed well enough to merit further investigation into its use in SDC. In particular research into how to construct a distance matrix for the Cell Suppression Problem (CSP) may both improve the performance of ACO when it is applied in that field and provide further insight into SDC.

Recent research has demonstrated that the problem of class modelling within early cycle object orientated software engineering can be successfully tackled by posing it as a search problem to be tackled with meta-heuristics. This "Search Based Software Engineering" approach has been illustrated using both Evolutionary Algorithms and Ant Colony Optimisation to perform the underlying search. Each has been shown to display strengths and weaknesses - both in terms of how easily "standard" algorithms can be applied to the domain, and of optimisation performance. This paper extends that work by considering the effect of incorporating Local Search. Specifically we examine the hypothesis that within a memetic framework the choice of global search heuristic does not significantly affect search performance, freeing the decision to be made on other more subjective factors.

Among the most promising and active research areas in heuristic optimisation is the field of adaptive memetic algorithms (AMAs). These gain much of their reported robustness by adapting the probability with which each of a set of local improvement operators is applied, according to an estimate of their current value to the search process. This paper addresses the issue of how the current value should be estimated. Assuming the estimate occurs over several applications of a meme, we consider whether the extreme or mean improvements should be used, and whether this aggregation should be global, or local to some part of the solution space. To investigate these issues, we use the well-established COMA framework that coevolves the specification of a population of memes (representing different local search algorithms) alongside a population of candidate solutions to the problem at hand. Two very different memetic algorithms are considered: the first using adaptive operator pursuit to adjust the probabilities of applying a fixed set of memes, and a second which applies genetic operators to dynamically adapt and create memes and their functional definitions. For the latter, especially on combinatorial problems, credit assignment mechanisms based on historical records, or on notions of landscape locality, will have limited application, and it is necessary to estimate the value of a meme via some form of sampling. The results on a set of binary encoded combinatorial problems show that both methods are very effective, and that for some problems it is necessary to use thousands of variables in order to tease apart the differences between different reward schemes. However, for both memetic algorithms, a significant pattern emerges that reward based on mean improvement is better than that based on extreme improvement. This contradicts recent findings from adapting the parameters of operators involved in global evolutionary search. The results also show that local reward schemes outperform global reward schemes in combinatorial spaces, unlike in continuous spaces. An analysis of evolving meme behaviour is used to explain these findings.

Statistical disclosure control is the collective name for a range of tools used by data providers such as government departments to protect the confidentiality of individuals or organizations. When the published tables contain magnitude data such as turnover or health statistics, the preferred method is to suppress the values of certain cells. Assigning a cost to the information lost by suppressing any given cell creates the “cell suppression problem.” This consists of finding the minimum cost solution which meets the confidentiality constraints. Solving this problem simultaneously for all of the sensitive cells in a table is NP-hard and not possible for medium to large sized tables. In this paper, we describe the development of a heuristic tool for this problem which hybridizes linear programming (to solve a relaxed version for a single sensitive cell) with a genetic algorithm (to seek an order for considering the sensitive cells which minimizes the final cost). Considering a range of real-world and representative “artificial” datasets, we show that the method is able to provide relatively low cost solutions for far larger tables than is possible for the optimal approach to tackle. We show that our genetic approach is able to significantly improve on the initial solutions provided by existing heuristics for cell ordering, and outperforms local search. This approach is then extended and applied to large statistical tables with over 200000 cells.

This paper looks at the real world problem of statistical disclosure control. National Statistics Agencies are required to publish detailed statistics and simultaneously guarantee the confidentiality of the contributors. When published statistical tables contain magnitude data such as turnover or health statistics the preferred method is to suppress the values of cells which may reveal confidential information. However suppressing these 'primary' cells alone will not guarantee protection due the presence of margin (row/column) totals and therefore other 'secondary' cells must also be suppressed. A previously developed algorithm that hybridizes linear programming with a genetic algorithm has been shown to protect tables with up to 40,000 cells, however Statistical Agencies are often required to protect tables with over 100,000 cells.

The choice of mutation rate is a vital factor in the success of any genetic algorithm (GA), and for permutation representations this is compounded by the availability of several alternative mutation operators. It is now well understood that there is no one "optimal choice"; rather, the situation changes per problem instance and during evolution. This paper examines whether this choice can be left to the processes of evolution via self-adaptation, thus removing this nontrivial task from the GA user and reducing the risk of poor performance arising from (inadvertent) inappropriate decisions. Self-adaptation has been proven successful for mutation step sizes in the continuous domain, and for the probability of applying bitwise mutation to binary encodings; here we examine whether this can translate to the choice and parameterisation of mutation operators for permutation encodings. We examine one method for adapting the choice of operator during runtime, and several different methods for adapting the rate at which the chosen operator is applied. In order to evaluate these algorithms, we have used a range of benchmark TSP problems. Of course this paper is not intended to present a state of the art in TSP solvers; rather, we use this well known problem as typical of many that require a permutation encoding, where our results indicate that self-adaptation can prove beneficial. The results show that GAs using appropriate methods to self-adapt their mutation operator and mutation rate find solutions of comparable or lower cost than algorithms with "static" operators, even when the latter have been extensively pretuned. Although the adaptive GAs tend to need longer to run, we show that is a price well worth paying as the time spent finding the optimal mutation operator and rate for the nonadaptive versions can be considerable. Finally, we evaluate the sensitivity of the self-adaptive methods to changes in the implementation, and to the choice of other genetic operators and population models. The results show that the methods presented are robust, in the sense that the performance benefits can be obtained in a wide range of host algorithms.

Statistical Disclosure Control is the collective name for a range of tools that data providers such as government departments use to protect the confidentiality of individuals or organizations. When the published tables contain magnitude data such as turnover or health statistics, the preferred method is to suppress the values of certain cells. Assigning a cost to the information lost by suppressing any given cell creates the "Cell Suppression Problem". This consists of finding the minimum cost solution which meets the confidentiality constraints. Solving this problem simultaneously for all of the sensitive cells in a table is NP-hard and not possible for medium to large sized tables. In this paper, we describe the development of a heuristic tool for this problem which hybridizes Linear Programming (to solve a relaxed version for a single sensitive cell) with a Genetic Algorithm (to seek an order for considering the sensitive cells which minimizes the final cost). Considering a range of real-world and representative "artificial" datasets, we show that the method is able to provide relatively low cost solutions for far larger tables than is possible for the optimal approach to tackle. We show that our genetic approach is able to significantly improve on the initial solutions provided by existing heuristics for cell ordering, and outperforms local search.

This paper considers on a number of issues that arise when a trainable machine vision system learns directly from humans. We contrast this to the “normal” situation where machine learning (ML) techniques are applied to a “cleaned” data set which is considered to be perfectly labeled with complete accuracy. This paper is done within the context of a generic system for the visual surface inspection of manufactured parts; however, the issues treated are relevant not only to wider computer vision applications such as medical image screening but also to classification more generally. Many of the issues we consider arise from the nature of humans themselves: They will be not only internally inconsistent but also will often not be completely confident about their decisions, particularly if they are making decisions rapidly. People will also often differ systematically from each other in the decisions they make. Other issues may arise from the nature of the process, which may require the ML to have the capacity for real-time online adaptation in response to users' input. Because of this, it may be that the users cannot always provide input to a consistent level of detail. We describe how all of these issues may be tackled within a coherent methodology. By using a range of classifiers trained on data sets from a compact disc imprint production process, we present results which demonstrate that training methods designed to take proper consideration of these issues may actually lead to improved performance.

Adaptive Memetic Algorithms couple an evolutionary algorithm with a number of local search heuristics for improving the evolving solutions. They are part of a broad family of meta-heuristics which maintain a set of local search operators applying them at different stages of the search. This creates a need to make decisions about which operator to use when. Several different schemes have been proposed, but most of them assume there is a fixed set of predefined operators. This makes them unsuitable for use within the broader context of adaptive learning systems where the set of available operators can change over time. Here we investigate a range of different schemes, and propose a novel method for estimating an operator's current utility, which is shown to avoid some of the problems of noise inherent in simpler schemes. Results on arange of combinatorial optimisation problems show that algorithms embodying this mechanism locate the global optimum more reliably, without a significant computational overhead compared to the simpler schemes.

Steady State models of Evolutionary Algorithms are widely used, yet surprisingly little attention has been paid to the effects arising from different replacement strategies. This paper explores the use of mathematical models to characterise the selection pressures arising in a selection-only environment. The first part brings together models for the behaviour of seven different replacement mechanisms and provides expressions for various proposed indicators of Evolutionary Algorithm behaviour. Some of these have been derived elsewhere, and are included for completeness, but the majority are new to this paper. These theoretical indicators are used to compare the behaviour of the different strategies. The second part of this paper examines the practical relevance of these indicators as predictors for algorithms' relative performance in terms of optimisation time and reliability. It is not the intention of this paper to come up with a "one size fits all" recommendation for choice of replacement strategy. Although some strategies may have little to recommend them, the relative ranking of others is shown to depend on the intended use of the algorithm to be implemented, as reflected in the choice of performance metrics.

Coevolving memetic algorithms are a family of metaheuristic search algorithms in which a rule-based representation of local search (LS) is coadapted alongside candidate solutions within a hybrid evolutionary system. Simple versions of these systems have been shown to outperform other nonadaptive memetic and evolutionary algorithms on a range of problems. This paper presents a rationale for such systems and places them in the context of other recent work on adaptive memetic algorithms. It then proposes a general structure within which a population of LS algorithms can be evolved in tandem with the solutions to which they are applied. Previous research started with a simple self-adaptive system before moving on to more complex models. Results showed that the algorithm was able to discover and exploit certain forms of structure and regularities within the problems. This "metalearning" of problem features provided a means of creating highly scalable algorithms. This work is briefly reviewed to highlight some of the important findings and behaviors exhibited. Based on this analysis, new results are then presented from systems with more flexible representations, which, again, show significant improvements. Finally, the current state of, and future directions for, research in this area is discussed.

The nearest-neighbor (NN) classifier has long been used in pattern recognition, exploratory data analysis, and data mining problems. A vital consideration in obtaining good results with this technique is the choice of distance function, and correspondingly which features to consider when computing distances between samples. In this paper, a new ensemble technique is proposed to improve the performance of NN classifier. The proposed approach combines multiple NN classifiers, where each classifier uses a different distance function and potentially a different set of features (feature vector). These feature vectors are determined for each distance metric using Simple Voting Scheme incorporated in Tabu Search (TS). The proposed ensemble classifier with different distance metrics and different feature vectors (TS-DF/NN) is evaluated using various benchmark data sets from UCI Machine Learning Repository. Results have indicated a significant increase in the performance when compared with various well-known classifiers. Furthermore, the proposed ensemble method is also compared with ensemble classifier using different distance metrics but with same feature vector (with or without Feature Selection (FS)).

A rapidly emerging model in the field of adaptive computing is the symbiosis of human expertise with evolutionary algorithms for user controlled and directed search. The two aspects in any EA are the selection of individuals to reproduce based on some measure of their quality or fitness and the application of variation operators to produce new solutions. In the context of interactive evolution, these aspects are compounded by the need for rapid convergence to prevent user fatigue and to provide the user some control over the generation of new solutions. Elsewhere, in the work of the authors (2004), we have examined different policies for best incorporating the user into the evaluation and selection process. In this paper, we explore the hypothesis that user assigned fitness represents a source of information that can be used to control the variation process: effectively to broaden the search if none of the current solutions is promising, or focus the search and improve convergence speed in the vicinity of a good solution. The main aims of this study, therefore, are to analyse the advantages of using a user directed adaptive mutation strategy over fixed mutation step sizes in terms of time to converge and robustness of the resulting solution. We present results showing a qualitatively different type of search process can be obtained by using the user assigned fitness to control the nature of the mutation process. There is also a synergy between user-based selection and fitness-based mutation control which out performs either system on its own.

September 01 2004 Editorial Introduction Special Issue on Memetic Algorithms In Special Collection: CogNet W.E. Hart, W.E. Hart Search for other works by this author on: This Site Google Scholar N. Krasnogor, N. Krasnogor Search for other works by this author on: This Site Google Scholar J. E. Smith J. E. Smith Search for other works by this author on: This Site Google Scholar Author and Article Information W.E. Hart Guest Editor N. Krasnogor Guest Editor J. E. Smith Online Issn: 1530-9304 Print Issn: 1063-6560 © 2004 Massachusetts Institute of Technology2004 Evolutionary Computation (2004) 12 (3): v–vi. https://doi.org/10.1162/1063656041775009 Cite Icon Cite Permissions Share Icon Share Facebook Twitter LinkedIn MailTo Views Icon Views Article contents Figures & tables Video Audio Supplementary Data Peer Review Search Site Citation W.E. Hart, N. Krasnogor, J. E. Smith; Editorial Introduction Special Issue on Memetic Algorithms. Evol Comput 2004; 12 (3): v–vi. doi: https://doi.org/10.1162/1063656041775009 Download citation file: Ris (Zotero) Reference Manager EasyBib Bookends Mendeley Papers EndNote RefWorks BibTex toolbar search Search Dropdown Menu toolbar search search input Search input auto suggest filter your search All ContentAll JournalsEvolutionary Computation Search Advanced Search This content is only available as a PDF. © 2004 Massachusetts Institute of Technology2004 Article PDF first page preview Close Modal You do not currently have access to this content.

We present results from analyses of fitness landscapes of the HP model of protein structure prediction problems. The work concentrates on those issues that are likely to impact on the effectiveness of evolutionary search of those landscapes, such as massive multimodality, degeneracy, and the presence of large regions corresponding to physically infeasible solutions. In the light of previous researcher's experience, and of our experimental results, we conclude by suggesting some characteristics that successful operators and parameters should possess.

This paper presents and examines the behaviour of a system whereby the rules governing local search within a memetic algorithm are co-evolved alongside the problem representation. We describe the rationale for such a system, and then describe the implementation of a simple version in which the evolving rules are encoded as (condition:action) patterns applied to problem representation. We investigate the behaviour of the algorithm on a suite of test problems, and show considerable performance improvements over a simple genetic algorithm, a memetic algorithm using a fixed neighbourhood function, and a similar memetic algorithm which uses random rules, i.e. with the learning mechanisms disabled. Analysis of these results enables us to draw some conclusions about the way that even the simplified system is able to discover and exploit certain forms of structure and regularities if these exist within the problem space. We show that this "meta-learning" of problem features provides a means of creating highly scalable algorithms for some types of problems. We further demonstrate that in the absence of this kind of exploitable patterns, the use of continually evolving neighbourhood functions for the local search operators adds robustness to the memetic algorithm in a manner similar to variable neighbourhood search. Finally we draw some initial conclusions about the way in which this meta-learning takes place, via examination of the use of different pivot rules and pairing strategies between the population of solution and the population of rules.

We present a coevolutionary learning-optimisation approach to protein structure prediction which uses a memetic algorithm as its underlying search method. Instance-specific knowledge can be learned, stored and applied by the system in the form of a population of rules. These rules determine the neighbourhoods used by the local search process, which is applied to each member of the coevolving population of candidate solutions. A generic coevolutionary framework is proposed for this approach, and then the implementation of a simple self-adaptive instantiation is described. A rule defining the local search's move operator is encoded as a {condition : action} pair and added to the genotype of each individual. It is demonstrated that the action of mutation and crossover on the patterns encoded in these rules, coupled with the action of selection on the resultant phenotypes is sufficient to permit the discovery and propagation of knowledge about the instance being optimised. The algorithm is benchmarked against a simple genetic algorithm, a memetic algorithm using a fixed neighbourhood function, and a similar memetic algorithm which uses random (rather than evolved) rules and shows significant improvements in terms of the ability to locate optimum configurations using Dill's HP model. It is shown that this "metalearning" of problem features provides a means of creating highly scaleable algorithms.