Search

Feature selection is the process of choosing, or removing, features to obtain the most informative feature subset of minimal size. Such subsets are used to improve performance of machine learning algorithms and enable human understanding of the results. Approaches to feature selection in literature exploit several optimization algorithms. Multi-objective methods also have been proposed, minimizing at the same time the number of features and the error. While most approaches assess error resorting to the average of a stochastic K-fold cross-validation, comparing averages might be misleading. In this paper, we show how feature subsets with different average error might in fact be non-separable when compared using a statistical test. Following this idea, clusters of non-separable optimal feature subsets are identified. The performance in feature selection can thus be evaluated by verifying how many of these optimal feature subsets an algorithm is able to identify. We thus propose a multi-objective optimization approach to feature selection, EvoFS, with the objectives to i. minimize feature subset size, ii. minimize test error on a 10-fold cross-validation using a specific classifier, iii. maximize the analysis of variance value of the lowest-performing feature in the set. Experiments on classification datasets whose feature subsets can be exhaustively evaluated show that our approach is able to always find the best feature subsets. Further experiments on a high-dimensional classification dataset, that cannot be exhaustively analyzed, show that our approach is able to find more optimal feature subsets than state-of-the-art feature selection algorithms.

Digital collectible card games are not only a growing part of the video game industry, but also an interesting research area for the field of computational intelligence. This game genre allows researchers to deal with hidden information, uncertainty and planning, among other aspects. This paper proposes the use of evolutionary algorithms (EAs) to develop agents who play a card game, Hearthstone, by optimizing a data-driven decision-making mechanism that takes into account all the elements currently in play. Agents feature self-learning by means of a competitive coevolutionary training approach, whereby no external sparring element defined by the user is required for the optimization process. One of the agents developed through the proposed approach was runner-up (best 6%) in an international Hearthstone Artificial Intelligence (AI) competition. Our proposal performed remarkably well, even when it faced state-of-the-art techniques that attempted to take into account future game states, such as Monte-Carlo Tree search. This outcome shows how evolutionary computation could represent a considerable advantage in developing AIs for collectible card games such as Hearthstone.

Industrial manipulators are robots used to replace humans in dangerous or repetitive tasks. Also, these devices are often used for applications where high precision and accuracy is required. The increase of backlash caused by wear, that is, the increase of the amount by which teeth space exceeds the thickness of gear teeth, might be a significant problem, that could lead to impaired performances or even abrupt failures. However, maintenance is difficult to schedule because backlash cannot be directly measured and its effects only appear in closed loops. This paper proposes a novel technique, based on an Evolutionary Algorithm, to estimate the increase of backlash in a robot joint transmission. The peculiarity of this method is that it only requires measurements from the motor encoder. Experimental evaluation on a real-world test case demonstrates the effectiveness of the approach.

International audience

In machine learning a coreset is defined as a subset of the training set using which an algorithm obtains performances similar to what it would deliver if trained over the whole original data. Advantages of coresets include improving training speed and easing human understanding. Coreset discovery is an open line of research as limiting the training might also impair the quality of the result. Differently, virtual points, here called archetypes, might be far more informative for a machine learning algorithm. Starting from this intuition, a novel evolutionary approach to archetype set discovery is presented: starting from a population seeded with candidate coresets, a multi-objective evolutionary algorithm is set to modify them and eventually create archetype sets, to minimize both number of points in the set and classification error. Experimental results on popular benchmarks show that the proposed approach is able to deliver results that allow a classifier to obtain lower error and better ability of generalizing on unseen data than state-of-the-art coreset discovery techniques.

When a machine learning algorithm is able to obtain the same performance given a complete training set, and a small subset of samples from the same training set, the subset is termed coreset. As using a coreset improves training speed and allows human experts to gain a better understanding of the data, by reducing the number of samples to be examined, coreset discovery is an active line of research. Often in literature the problem of coreset discovery is framed as i. single-objective, attempting to find the candidate coreset that best represents the training set, and ii. independent from the machine learning algorithm used. In this work, an approach to evolutionary coreset discovery is presented. Building on preliminary results, the proposed approach uses a multi-objective evolutionary algorithm to find compromises between two conflicting objectives, i. minimizing the number of samples in a candidate coreset, and ii. maximizing the accuracy of a target classifier, trained with the coreset, on the whole original training set. Experimental results on popular classification benchmarks show that the proposed approach is able to identify candidate coresets with better accuracy and generality than state-of-the-art coreset discovery algorithms found in literature.

International audience; Background: Agri-food is one of the most important sectors of the industry in Europe and potentially a major contributor to the global warming. Sustainability issues in this context pose a huge challenge for several reasons: the variety of considered scales, the number of disciplines involved, the uncertainties, the out-of-equilibrium states, the complex quantitative and qualitative factors, the normative issues and the availability of data. Although important insight and breakthroughs have been attained in different scientific domains, an overarching and integrated analysis of these complex problems have yet to be realized.Scope and Approach: This context creates huge opportunities for research in interaction with mathematical programming, integrative models and decision-support tools. The paper propose a computational viewpoint including questions of holistic approach, multiscale reconstruction and optimization. Some directions are discussed.Key Findings and Conclusions: Several research questions based on a mathematical programming framework are emerging: how can such a framework manage uncertainty, cope with complex qualitative and quantitative information essential for social and environmental considerations, encompass diverse scales in space and time, cope with a multivariable dynamic environment and with scarcity of data. Moreover, how can it deal with different perspectives, types of models, research goals and data produced by conceptually disjoint scientific disciplines, ranging from physics and physiology to sociology and ethics? Building models is essential, but highly difficult; it will need a strong iterative interaction combining computational intensive methods, formal reasoning and the experts of the different fields. Some future research directions are proposed, involving all those dimensions: mathematical resilience, human-machine interactive learning and optimization techniques. (C) 2015 Elsevier Ltd. All rights reserved.

International audience; VALIS is an effective and robust classification algorithm with a focus on understandability. Its name stems from Vote-ALlocating Immune System, as it evolves a population of artificial antibodies that can bind to the input data, and performs classification through a voting process. In the beginning of the training, VALIS generates a set of random candidate antibodies; at each iteration, it selects the most useful ones to produce new candidates, while the least, are discarded; the process is iterated until a user-defined stopping condition. The paradigm allows the user to get a visual insight of the learning dynamics, helping to supervise the process, pinpoint problems, and tweak feature engineering. VALIS is tested against nine state-of-the-art classification algorithms on six popular benchmark problems; results demonstrate that it is competitive with well-established black-box techniques, and superior in specific corner cases.

International audience; Collectible card games have been among the most popular and profitable products of the entertainment industry since the early days of Magic: The GatheringTM in the nineties. Digital versions have also appeared, with HearthStone: Heroes of WarCraftTM being one of the most popular. In Hearthstone, every player can play as a hero, from a set of nine, and build his/her deck before the game from a big pool of available cards, including both neutral and hero-specific cards. This kind of games offers several challenges for researchers in artificial intelligence since they involve hidden information, unpredictable behaviour, and a large and rugged search space. Besides, an important part of player engagement in such games is a periodical input of new cards in the system, which mainly opens the door to new strategies for the players. Playtesting is the method used to check the new card sets for possible design flaws, and it is usually performed manually or via exhaustive search; in the case of Hearthstone, such test plays must take into account the chosen hero, with its specific kind of cards. In this paper, we present a novel idea to improve and accelerate the playtesting process, systematically exploring the space of possible decks using an Evolutionary Algorithm (EA). This EA creates HearthStone decks which are then played by an AI versus established human-designed decks. Since the space of possible combinations that are play-tested is huge, search through the space of possible decks has been shortened via a new heuristic mutation operator, which is based on the behaviour of human players modifying their decks. Results show the viability of our method for exploring the space of possible decks and automating the play-testing phase of game design. The resulting decks, that have been examined for balancedness by an expert player, outperform human-made ones when played by the AI; the introduction of the new heuristic operator helps to improve the obtained solutions, and basing the study on the whole set of heroes shows its validity through the whole range of decks.

One of the most relevant problems in social networks is influence maximization, that is the problem of finding the set of the most influential nodes in a network, for a given influence propagation model. As the problem is NP-hard, recent works have attempted to solve it by means of computational intelligence approaches, for instance Evolutionary Algorithms. However, most of these methods are of limited applicability for real-world large-scale networks, for two reasons: on the one hand, they require a large number of candidate solution evaluations to converge; on the other hand, each evaluation is computationally expensive in that it needs a considerable number of Monte Carlo simulations to obtain reliable values. In this work, we consider a possible solution to such limitations, by evaluating a surrogate-assisted Multi-Objective Evolutionary Algorithm that uses an approximate model of influence propagation (instead of Monte Carlo simulations) to find the minimum-sized set of most influential nodes. Experiments carried out on two social networks datasets suggest that approximate models should be carefully considered before using them in influence maximization approaches, as the errors induced by these models are in some cases too big to benefit the algorithmic performance.

International audience; Cancer diagnosis is currently undergoing a paradigm shift with the incorporation of molecular biomarkers as part of routine diagnostic panel. This breakthrough discovery directs researches to examine the role of microRNA in cancer, since its deregulation is often associated with almost all human tumors. Such differences frequently recur in tumor-specific microRNA signatures, which are helpful to diagnose tissue of origin and tumor subtypes. Nonetheless, the resulting classification problem is far from trivial, as there are hundreds of microRNA types, and tumors are non-linearly correlated to the presence of several overexpressions. In this paper, we propose to apply an evolutionary optimized convolutional neural network classifier to this complex task. The presented approach is compared against 21 state-of-the-art classifiers, on a real-world dataset featuring 8129 patients, for 29 different classes of tumors, using 1046 different biomarkers. As a result of the comparison, we also present a meta-analysis on the dataset, identifying the classes on which the collective performance of the considered classifiers is less effective, and thus possibly singling out types of tumors for which biomarker tests might be less reliable.

International audience; Reducing the effort required by humans in countering malware is of utmost practical value. We describe a scalable, semi-supervised framework to dig into massive data sets of Android applications and identify new malware families. Until 2010, the industrial standard for the detection of malicious applications has been mainly based on signatures; as each tiny alteration in malware makes them ineffective, new signatures are frequently created - a task that requires a considerable amount of time and resources from skilled experts. The framework we propose is able to automatically cluster applications in families and suggest formal rules for identifying them with 100% recall and quite high precision. The families are used either to safely extend experts' knowledge on new samples or to reduce the number of applications requiring thorough analyses. We demonstrated the effectiveness and the scalability of the approach running experiments on a database of 1.5 million Android applications. In 2018, the framework has been successfully deployed on Koodous, a collaborative anti-malware platform.

Inspiring metaphors play an important role in the beginning of an investigation, but are less important in a mature research field as the real phenomena involved are understood. Nowadays, in evolutionary computation, biological analogies should be taken into consideration only if they deliver significant advantages.

One of the most notable features of collectible card games is deckbuilding, that is, defining a personalized deck before the real game. Deckbuilding is a challenge that involves a big and rugged search space, with different and unpredictable behaviour after simple card changes and even hidden information. In this paper, we explore the possibility of automated deckbuilding: a genetic algorithm is applied to the task, with the evaluation delegated to a game simulator that tests every potential deck against a varied and representative range of human-made decks. In these preliminary experiments, the approach has proven able to create quite effective decks, a promising result that proves that, even in this challenging environment, evolutionary algorithms can find good solutions.

Genetic Improvement is an evolutionary-based technique. Despite its relatively recent introduction, several successful applications have been already reported in the scientific literature: it has been demonstrated able to modify the code complex programs without modifying their intended behavior; to increase performance with regards to speed, energy consumption or memory use. Some results suggest that it could be also used to correct bugs, restoring the software’s intended functionalities. Given the novelty of the technique, however, instances of Genetic Improvement so far rely upon ad-hoc, language-specific implementations. In this paper, we propose a general framework based on the software engineering’s idea of mutation testing coupled with Genetic Programming, that can be easily adapted to different programming languages and objective. In a preliminary evaluation, the framework efficiently optimizes the code of the md5 hash function in C, Java, and Python.

International audience; The iterated prisoner’s dilemma is a famous model of cooperation and conflict in game theory. Its origin can be traced back to the Cold War, and countless strategies for playing it have been proposed so far, either designed by hand or automatically generated by computers. In the 2000s, scholars started focusing on adaptive players, that is, able to classify their opponent’s behavior and adopt an effective counter-strategy. The player presented in this paper, pushes such idea even further: it builds a model of the current adversary from scratch, without relying on any pre-defined archetypes, and tweaks it as the game develops using an evolutionary algorithm; at the same time, it exploits the model to lead the game into the most favorable continuation. Models are compact non-deterministic finite state machines; they are extremely efficient in predicting opponents’ replies, without being completely correct by necessity. Experimental results show that such player is able to win several one-toone games against strong opponents taken from the literature, and that it consistently prevails in round-robin tournaments of different sizes.

This short paper contains an extended list of references to diversity preservation methodologies, classified following the taxonomy presented in a previous publication. The list has been updated according to the contributions sent to the workshop "Measuring and Promoting Diversity in Evolutionary Computation", held during the conference GECCO 2016.

Chapitre 11; The use of anti-virus software has become something of an act of faith. A recent study showed that more than 80 % of all personal computers have anti-virus software installed. However, the protection mechanisms in place are far less effective than users would expect. Malware analysis is a classical example of cat-and-mouse game: as new anti-virus techniques are developed, malware authors respond with new ones to thwart analysis. Every day, anti-virus companies analyze thousands of malware that has been collected through honeypots, hence they restrict the research to only already existing viruses. This article describes a novel method for malware obfuscation based an evolutionary opcode generator and a special ad-hoc packer. The results can be used by the security industry to test the ability of their system to react to malware mutations.

Chapitre 5; Several machine learning paradigms have been applied to financial forecasting, attempting to predict the market’s behavior, with the final objective of profiting from trading shares. While anticipating the performance of such a complex system is far from trivial, this issue becomes even harder when the investors do not have large amounts of money available. In this paper, we present an evolutionary portfolio optimizer for the management of small budgets. The expected returns are modeled resorting to Multi-layer Perceptrons, trained on past market data, and the portfolio composition is chosen by approximating the solution to a multi-objective constrained problem. An investment simulator is then used to measure the portfolio performance. The proposed approach is tested on real-world data from Milan stock exchange, exploiting information from January 2000 to June 2010 to train the framework, and data from July 2010 to August 2011 to validate it. The presented tool is finally proven able to obtain a more than satisfying profit for the considered time frame.

In the past decades, different evolutionary optimization methodologies have been proposed by scholars and exploited by practitioners, in a wide range of applications. Each paradigm shows distinctive features, typical advantages, and characteristic disadvantages; however, one single problem is shared by almost all of them: the "lack of speciation". While natural selection favors variations toward greater divergence, in artificial evolution candidate solutions do homologize. Many authors argued that promoting diversity would be beneficial in evolutionary optimization processes, and that it could help avoiding premature convergence on suboptimal solutions. The paper surveys the research in this area up to mid 2010s, it re-orders and re-interprets different methodologies into a single framework, and proposes a novel three-axis taxonomy. Its goal is to provide the reader with a unifying view of the many contributions in this important corpus, allowing comparisons and informed choices. Characteristics of the different techniques are discussed, and similarities are highlighted; practical ways to measure and promote diversity are also suggested. (C) 2015 Elsevier Inc. All rights reserved.

In many optimization processes, the fitness or the considered measure of goodness for the candidate solutions presents uncertainty, that is, it yields different values when repeatedly measured, due to the nature of the evaluation process or the solution itself. This happens quite often in the context of computational intelligence in games, when either bots behave stochastically, or the target game possesses intrinsic random elements, but it shows up also in other problems as long as there is some random component. Thus, it is important to examine the statistical behavior of repeated measurements of performance and, more specifically, the statistical distribution that better fits them. This work analyzes four different problems related to computational intelligence in videogames, where Evolutionary Computation methods have been applied, and the evaluation of each individual is performed by playing the game, and compare them to other problem, neural network optimization, where performance is also a statistical variable. In order to find possible patterns in the statistical behavior of the variables, we track the main features of its distributions, skewness and kurtosis. Contrary to the usual assumption in this kind of problems, we prove that, in general, the values of two features imply that fitness values do not follow a normal distribution; they do present a certain common behavior that changes as evolution proceeds, getting in some cases closer to the standard distribution and in others drifting apart from it. A clear behavior in this case cannot be concluded, other than the fact that the statistical distribution that fitness variables follow is affected by selection in different directions, that parameters vary in a single generation across them, and that, in general, this kind of behavior will have to be taken into account to adequately address uncertainty in fitness in evolutionary algorithms.

Predicting the market’s behavior to profit from trading stocks is far from trivial. Such a task becomes even harder when investors do not have large amounts of money available, and thus cannot influence this complex system in any way. Machine learning paradigms have been already applied to financial forecasting, but usually with no restrictions on the size of the investor’s budget. In this paper, we analyze an evolutionary portfolio optimizer for the management of limited budgets, dissecting each part of the framework, discussing in detail the issues and the motivations that led to the final choices. Expected returns are modeled resorting to artificial neural networks trained on past market data, and the portfolio composition is chosen by approximating the solution to a multi-objective constrained problem. An investment simulator is eventually used to measure the portfolio performance. The proposed approach is tested on real-world data from New York’s, Milan’s and Paris’ stock exchanges, exploiting data from June 2011 to May 2014 to train the framework, and data from June 2014 to July 2015 to validate it. Experimental results demonstrate that the presented tool is able to obtain a more than satisfying profit for the considered time frame.

Graphical abstractDisplay Omitted HighlightsWe used cooperative co-evolutionary to analyse routing in Delay-Tolerant Networks.We applied the method to two urban-scale network scenarios: Venice and San Francisco.We ran extensive experiments on large networks running First Contact protocol.We found groups of strong colluding attackers able to reduce the data delivery rate. In novel forms of the Social Internet of Things, any mobile user within communication range may help routing messages for another user in the network. The resulting message delivery rate depends both on the users' mobility patterns and the message load in the network. This new type of configuration, however, poses new challenges to security, amongst them, assessing the effect that a group of colluding malicious participants can have on the global message delivery rate in such a network is far from trivial. In this work, after modeling such a question as an optimization problem, we are able to find quite interesting results by coupling a network simulator with an evolutionary algorithm. The chosen algorithm is specifically designed to solve problems whose solutions can be decomposed into parts sharing the same structure. We demonstrate the effectiveness of the proposed approach on two medium-sized Delay-Tolerant Networks, realistically simulated in the urban contexts of two cities with very different route topology: Venice and San Francisco. In all experiments, our methodology produces attack patterns that greatly lower network performance with respect to previous studies on the subject, as the evolutionary core is able to exploit the specific weaknesses of each target configuration.

International audience; The complexity of cell phones is continually increasing, with regards to both hardware and software parts. As many complex devices, their components are usually designed and verified separately by specialized teams of engineers and programmers. However, even if each isolated part is working flawlessly, it often happens that bugs in one software application arise due to the interaction with other modules. Those software misbehaviors become particularly critical when they affect the residual battery life, causing power dissipation. An automatic approach to detect power-affecting software defects is proposed. The approach is intended to be part of a qualifying verification plan and complete human expertise. Motorola, always at the forefront of researching innovations in the product development chain, experimented the approach on a mobile phone prototype during a partnership with Politecnico di Torino. Software errors unrevealed by all human-designed tests have been detected by the proposed framework, two out of three critical from the power consumption point of view, thus enabling Motorola to further improve its verification plans. Details of the tests and experimental results are presented.

Chapitre 4; The idea of exploiting Global Sensitivity Analysis (GSA) to make Evolutionary Algorithms more effective seems very attractive: intuitively, a probabilistic analysis can prove useful to a stochastic optimisation technique. GSA, that gathers information about the behaviour of functions receiving some inputs and delivering one or several outputs, is based on computationally-intensive stochastic sampling of a parameter space. Nevertheless, efficiently exploiting information gathered from GSA might not be so straightforward. In this paper, we present three mono- and multi-objective counterexamples to prove how naively combining GSA and EA may mislead an optimisation process.

A malicious botnet is a collection of compromised hosts coordinated by an external entity. The malicious software, or malware, that infect the systems are its basic units and they are responsible for its global behavior. Anti Virus software and Intrusion Detection Systems detect botnets by analyzing network and files, looking for signature and known behavioral patterns. Thus, the malware hiding capability is a crucial aspect. This paper describes a new obfuscation mechanism based on evolutionary algorithms: an evolutionary core is embedded in the malware to generate a different, optimized hiding strategy for every single infection. Such always-changing, hard-to-detect malware can be used by security industries to stress the analysis methodologies and to test the ability to react to malware mutations. This research is the first step in a more ambitious research project, where a whole botnet, composed of different malware and Anti Virus software, is analyzed as a prey-predator ecosystem.

Wireless sensor network (WSN) routing protocols, e.g., the Collection Tree Protocol (CTP), are designed to adapt in an ad-hoc fashion to the quality of the environment. WSNs thus have high internal dynamics and complex global behavior. Classical techniques for performance evaluation (such as testing or verification) fail to uncover the cases of extreme behavior which are most interesting to designers. We contribute a practical framework for performance evaluation of WSN protocols. The framework is based on multi-objective optimization, coupled with protocol simulation and evaluation of performance factors. For evaluation, we consider the two crucial functional and non-functional performance factors of a WSN, respectively: the ratio of data delivery from the network (DDR), and the total energy expenditure of the network (COST). We are able to discover network topological configurations over which CTP has unexpectedly low DDR and/or high COST performance, and expose full Pareto fronts which show what the possible performance tradeoffs for CTP are in terms of these two performance factors. Eventually, Pareto fronts allow us to bound the state space of the WSN, a fact which provides essential knowledge to WSN protocol designers.

Chapitre 3; Symbolic regression has many successful applications in learning free-form regular equations from data. Trying to apply the same approach to differential equations is the logical next step: so far, however, results have not matched the quality obtained with regular equations, mainly due to additional constraints and dependencies between variables that make the problem extremely hard to tackle. In this paper we propose a new approach to dynamic systems learning. Symbolic regression is used to obtain a set of first-order Eulerian approximations of differential equations, and mathematical properties of the approximation are then exploited to reconstruct the original differential equations. Advantages of this technique include the de-coupling of systems of differential equations, that can now be learned independently ; the possibility of exploiting established techniques for standard symbolic regression, after trivial operations on the original dataset; and the substantial reduction of computational effort, when compared to existing ad-hoc solutions for the same purpose. Experimental results show the efficacy of the proposed approach on an instance of the Lotka-Volterra model.

This short paper proposes two different ways for exploiting an evolutionary algorithm to devise malware: the former targeting heuristic-based anti-virus scanner; the latter optimizing a Trojan attack. An extended internal on the same the subject can be downloaded from http://www.cad.polito.it/downloads/

National audience; Obtaining reliable in-silico food models is fundamental for a better understanding of these systems. The complex phenomena involved in these real-world processes reflect in the intricate structure of models, so that thoroughly exploring their behaviour and, for example, finding meaningful correlations between variables, become a relevant challenge for the experts. In this paper, we present a methodology based on visualisation and evolutionary computation to assist experts during model exploration. The proposed approach is tested on an established model of milk gel structures, and we show how experts are eventually able to find a correlation between two parameters, previously considered independent. Reverse-engineering the final outcome, the emergence of such a pattern is proved by physical laws underlying the oil-water interface colonisation. It is interesting to notice that, while the present work is focused on milk gel modelling, the proposed methodology can be straightforwardly generalised to other complex physical phenomena. Industrial relevance: Sustainability is nowadays at the heart of industrial requirements. The development of mathematical approaches should facilitate common approaches to risk/benefit assessment and nutritional quality in food research and industry. These models will enhance knowledge on process-structure-property relationships from the molecular to macroscopic level, and facilitate the creation of in-silico simulators with functional and nutritional properties. The stochastic optimisation techniques (evolutionary algorithms) employed in these works allow the users to thoroughly explore the systems: when coupled with visualisation, they make it possible to provide the experts with a restricted set of significant data, helping them to highlight eventual issues or possible improvements in the model. With regard to the complexity of the food systems and dynamics, the challenge of the mathematical approaches is to realise a complete dynamic description of food processing. In order to reach this objective, it is mandatory to use innovative strategies, exploiting the most recent advances in cognitive and complex system sciences. (C) 2014 Elsevier Ltd. All rights reserved.

This paper presents a genotype-level distance metric for Genetic Programming (GP) based on the symmetric difference concept: first, the information contained in individuals is expressed as a set of symbols (the content of each node, its position inside the tree, and recurring parent-child structures); then, the difference between two individuals is computed considering the number of elements belonging to one, but not both, of their symbol sets.

Editors: Legrand, P., Corsini, M.-M., Hao, J.-K., Monmarché, N., Lutton, E., Schoenauer, M. (Eds.)Editors: Legrand, P., Corsini, M.-M., Hao, J.-K., Monmarché, N., Lutton, E., Schoenauer, M. (Eds.); International audience; In this paper we present a study based on an evolutionary framework to explore what would be a reasonable compromise between interaction and automated optimisation in finding possible solutions for a complex problem, namely the learning of Bayesian network structures, an NP-hard problem where user knowledge can be crucial to distinguish among solutions of equal fitness but very different physical meaning. Even though several classes of complex problems can be effectively tackled with Evolutionary Computation, most possess qualities that are difficult to directly encode in the fitness function or in the individual's genotype description. Expert knowledge can sometimes be used to integrate the missing information, but new challenges arise when searching for the best way to access it: full human interaction can lead to the well-known problem of user-fatigue, while a completely automated evolutionary process can miss important contributions by the expert. For our study, we developed a GUI-based prototype application that lets an expert user guide the evolution of a network by alternating between fully-interactive and completely automatic steps. Preliminary user tests were able to show that despite still requiring some improvements with regards to its efficiency, the proposed approach indeed achieves its goal of delivering satisfying results for an expert user.

Defining a distance measure over the individuals in the population of an Evolutionary Algorithm can be exploited for several applications, ranging from diversity preservation to balancing exploration and exploitation. When individuals are encoded as strings of bits or sets of real values, computing the distance between any two can be a straightforward process; when individuals are represented as trees or linear graphs, however, quite often the user must resort to phenotype-level problem-specific distance metrics. This paper presents a generic genotype-level distance metric for Linear Genetic Programming: the information contained by an individual is represented as a set of symbols, using n-grams to capture significant recurring structures inside the genome. The difference in information between two individuals is evaluated resorting to a symmetric difference. Experimental evaluations show that the proposed metric has a strong correlation with phenotype-level problem-specific distance measures in two problems where individuals represent string of bits and Assembly-language programs, respectively.

Chapter 11; International audience; Bayesian networks are graphical statistical models that represent inference between data. For their effectiveness and versatility, they are widely adopted to represent knowledge in different domains. Several research lines address the NP-hard problem of Bayesian network structure learning starting from data: over the years, the machine learning community delivered effective heuristics, while different Evolutionary Algorithms have been devised to tackle this complex problem. This paper presents a Memetic Algorithm for Bayesian network structure learning, that combines the exploratory power of an Evolutionary Algorithm with the speed of local search. Experimental results show that the proposed approach is able to outperform state-of-the-art heuristics on two well-studied benchmarks.

International audience; Cooperative co-evolution algorithms (CCEA) are a thriving sub-field of evolutionary computation. This class of algorithms makes it possible to exploit more efficiently the artificial Darwinist scheme, as soon as an optimisation problem can be turned into a co-evolution of interdependent sub-parts of the searched solution. Testing the efficiency of new CCEA concepts, however, it is not straightforward: while there is a rich literature of benchmarks for more traditional evolutionary techniques, the same does not hold true for this relatively new paradigm. We present a benchmark problem designed to study the behavior and performance of CCEAs, modeling a search for the optimal placement of a set of lamps inside a room. The relative complexity of the problem can be adjusted by operating on a single parameter. The fitness function is a trade-off between conflicting objectives, so the performance of an algorithm can be examined by making use of different metrics. We show how three different cooperative strategies, Parisian Evolution, Group Evolution and AllopatricGroup Evolution, can be applied to the problem. Using a Classical Evolution approach as comparison, we analyse the behavior of each algorithm in detail, with respect to the size of the problem.

Chapter 22; International audience; Bayesian networks are stochastic models, widely adopted to encode knowledge in several fields. One of the most interesting features of a Bayesian network is the possibility of learning its structure from a set of data, and subsequently use the resulting model to perform new predictions. Structure learning for such models is a NP-hard problem, for which the scientific community developed two main approaches: score-and-search metaheuristics, often evolutionary-based, and dependency-analysis deterministic algorithms, based on stochastic tests. State-of-the-art solutions have been presented in both domains, but all methodologies start from the assumption of having access to large sets of learning data available, often numbering thousands of samples. This is not the case for many real-world applications, especially in the food processing and research industry. This paper proposes an evolutionary approach to the Bayesian structure learning problem, specifically tailored for learning sets of limited size. Falling in the category of score-and-search techniques, the methodology exploits an evolutionary algorithm able to work directly on graph structures, previously used for assembly language generation, and a scoring function based on the Akaike Information Criterion, a well-studied metric of stochastic model performance. Experimental results show that the approach is able to outperform a state-of-the-art dependency-analysis algorithm, providing better models for small datasets.

The increasing complexity of products and processes leads directly to the growing intricacy of the problems and issues the industrial world is facing. More and more often, traditional computational techniques prove unable to cope with real world situations, either because the time needed to reach an optimal solution is not compatible with the frantic development processes of a company, or because the modeling of complex systems to the degree of precision needed is unfeasible.Evolutionary Algorithms (EA) comprehend a wide class of stochastic bio-inspired optimization techniques, firstly developed by J. H. Holland, L. J. Fogel, I. Rechenberg and H.Schwefel during the late 1960s and early 70s. Over the course of the last 35 years, EAs demonstrated their effectiveness in an extended variety of problems, ranging from airfoil design to credit card fraud detection. The industrial world, however, is still reluctant to introduce these powerful techniques into real procedures, mainly due to the sensation of insufficient controllability, scarce repeatability of the results, and the lack of experts with deep knowledge of both EAs and modern industrial needs. This book presents different case studies of EAs successfully applied to real world problems, hopefully showing the untapped potential of these techniques in various industrial fields.Chapter 1 comprehends a description of typical complex industrial problems, a brief history of EAs, a comparison with traditional methods, and a discussion on the application of evolutionary techniques to real world problems.Chapter 2 presents what is meant to be a surely incomplete, but extremely useful list of resources relevant for further elaboration and understanding of the multi-faceted world of EAs. The first section groups industrial problems related to the verification of hardware and software working prototypes.The case study presented in chapter 3 deals with the software verification of a whole operative system and all applications running on a mobile phone prototype. The chapter focus specifically on the problems concerning the application of an EA to a “needle in a haystack” kind of problem; on how to make the EA perform; and on how EAs can complete human expertise in the software verification field. The activity is carried out in cooperation with Motorola Research Labs, Torino, Italy.The verification of microprocessors is a growing field of study, mainly because design capability outperforms current verification techniques. Most studies on the correct behavior of a microprocessor are thus run on working prototypes, in the attempt to locate critical paths by making the device fail its computations. [br/]In chapter 4, an EA-based method to identify critical speed-paths in a multi-core microprocessor, exceeding the performance of state-of-the-art stress tests, is described. The second section presents a collection of real-world case studies pertaining design and reliability.The design of an antenna array is the topic of chapter 5. When devising such a complex system, often manual or automatic optimization methods do not yield satisfactory results, being either too labour-intensive or unsuitable for some specific class of problems. When an evolutionary algorithm is used to optimize parameters of the antenna array, the results show that these techniques are able to obtain better results than both manual and automatic approaches.In chapter 6, an EA-based technique to lengthen the lifespan of electronic noses, complex olfactory sensor arrays, is presented. Sensor arrays are affected by the drift problem, a degenerative error in the measurements, hard to model and predict. The proposed solution is to dynamically adjust the sensor readings with a state-of-the art Evolutionary Strategy proves to be effective. The experience is performed with the collaboration of Sensor CNR-INFM Lab, Brescia, Italy.Chapter 7 tackles the problem of automatically devising online test sets for microprocessor-based systems. While existing manufacturing test set can be used for this purpose, several additional constraints must be considered for an online application, including test length, duration, and intrusiveness. The proposed methodology, here applied to an Intel 8051 microcontroller, exploits an EA to create online test sets starting from tests devised by the anufacturer. The third section introduces results obtained through the application of EAs to test generation problems for hardware and circuits.Chapter 8 concerns the study of path delay faults in electronic devices, misbehaviors where a device produces a correct result without conforming to time specifications. Devising test to uncover the presence of these faults is challenging, exspecially when only a high-level description of the device is provided. To tackle this problem, where the ideal result is a set of equally feasible solutions, a Multi-Objective Evolutionary Algorithm (MOEA) is employed.In chapter 9, EAs are applied to the field of Software-Based Self Testing (SBST), an established test technique for various hardware architectures. SBST’s principle is to apply a suitable series of stimuli to the device under test, comparing the produced output to the expected one. Finding a minimal set of stimuli to thoroughly excite a device is not a trivial problem: EAs prove successful once again, showing that the proposed methodology is effective on a wide range of hardware peripherals.Chapter 10 deals again with stimuli generation for SBST, this time tackling a much more complex system, such as a microprocessor pipeline. Using a high-level representation of the target device, and a dynamically built Finite State Machine (FSM), fault coverage of the candidate stimuli are evaluated without resorting to time-expensive simulations on low-level models. Experimental results show that the evolved test obtains a nearly complete fault coverage against the targeted fault model.

A huge number of optimization problems, in the CAD area as well as in many other fields, require a solution composed by a set of structurally homogeneous elements. Each element tackles a subset of the original task, and they cumulatively solve the whole problem. Sub-tasks, however, have exactly the same structure, and the splitting is completely arbitrary. Even the number of sub-tasks is not known and cannot be determined a-priori. Individual elements are structurally homogeneous, and their contribution to the main solution can be evaluated separately. We propose an evolutionary algorithm able to optimize groups of individuals for solving this class of problems. An individual of the best solution may be sub-optimal when considered alone, but the set of individuals cumulatively represent the optimal group able to completely solve the whole problem. Results of preliminary experiments show that our algorithm performs better than other techniques commonly applied in the CAD field.

The incessant progress in manufacturing technology is posing new challenges to microprocessor designers. Nowadays, comprehensive verification of a chip can only be performed after tape-out, when the first silicon prototypes are available. Several activities that were originally supposed to be part of the pre-silicon design phase are migrating to this post-silicon time as well. The short paper describes a post-silicon methodology that can be exploited to devise functional failing tests. Such tests are essential to analyze and debug speed paths during verification, speed-stepping, and other critical activities. The proposed methodology is based on the Genetic Programming paradigm, and exploits a versatile toolkit named μGP. The paper demonstrates that an evolutionary algorithm can successfully tackle a significant and still open industrial problem. Moreover, it shows how to take into account complex hardware characteristics and architectural details of such complex devices.

International audience; Gas chemical sensors are strongly affected by the so-called drift, i.e., changes in sensors' response caused by poisoning and aging that may significantly spoil the measures gathered. The paper presents a mechanism able to correct drift, that is: delivering a correct unbiased fingerprint to the end user. The proposed system exploits a state-of-the-art evolutionary strategy to iteratively tweak the coefficients of a linear transformation. The system operates continuously. The optimal correction strategy is learnt without a-priori models or other hypothesis on the behavior of physical-chemical sensors. Experimental results demonstrate the efficacy of the approach on a real problem.

International audience; Mobile phones are becoming more and more complex devices, both from the hardware and from the software point of view. Consequently, their various parts are often developed separately. Each sub-system or application may be worked out by a specialized team of engineers and programmers. Frequently, bugs in one component are triggered by the complex interaction between the different applications. Those errors sometimes lead to power dissipation and other misbehaviors that lower residual battery life, a catastrophic event from the user perspective. In this paper we propose a model-based automatic approach to uncover software bugs, which is intended to complement human expertise and complete a qualifying verification plan. The system has been applied on the prototype of a Motorola mobile phone during a partnership with Politecnico di Torino. We demonstrate that our approach is effective by detecting three distinct software misbehaviours that escape all traditional tests. The paper details the methodology, tests and results.

In this paper we describe an improvement of an entropy-based diversity preservation approach for evolutionary algorithms. This approach exploits the information contained not only in the parts that compose an individual, but also in their position and relative order. We executed a set of preliminary experiments in order to test the new approach, using two different problems in which diversity preservation plays a major role in obtaining good solutions.