The mathematical theory of viability, developed to formalize problems related to natural and social phenomena, investigates the evolution of dynamical systems under constraints. A main objective of this theory is to design control laws to keep systems inside viable domains. Control laws are traditionally defined as rules, based on the current position in the state space with respect to the boundaries of the viability kernel. However, finding these boundaries is a computationally expensive procedure, feasible only for trivial systems. We propose an approach based on Genetic Programming (GP) to discover control laws for viability problems in analytic form. Such laws could keep a system viable without the need of computing its viability kernel, facilitate communication with stakeholders, and improve explainability. A candidate set of control rules is encoded as GP trees describing equations. Evaluation is noisy, due to stochastic sampling: initial conditions are randomly drawn from the state space of the problem, and for each, a system of differential equations describing the system is solved, creating a trajectory. Candidate control laws are rewarded for keeping viable as many trajectories as possible, for as long as possible. The proposed approach is evaluated on established benchmarks for viability and delivers promising results.

Experts in different domains rely increasingly on simulation models of complex processes to reach insights, make decisions, and plan future projects. These models are often used to study possible trade-offs, as experts try to optimise multiple conflicting objectives in a single investigation. Understanding all the model intricacies, however, is challenging for a single domain expert. We propose a simple approach to support multiple experts when exploring complex model results. First, we reduce the model exploration space, then present the results on a shared interactive surface, in the form of a scatterplot matrix and linked views. To explore how multiple experts analyse trade-offs using this setup, we carried out an observational study focusing on the link between expertise and insight generation during the analysis process. Our results reveal the different exploration strategies and multi-storyline approaches that domain experts adopt during trade-off analysis, and inform our recommendations for collaborative model exploration systems.

We evaluate and analyse a framework for evolutionary visual exploration (EVE) that guides users in exploring large search spaces. EVE uses an interactive evolutionary algorithm to steer the exploration of multidimensional data sets toward two-dimensional projections that are interesting to the analyst. Our method smoothly combines automatically calculated metrics and user input in order to propose pertinent views to the user. In this article, we revisit this framework and a prototype application that was developed as a demonstrator, and summarise our previous study with domain experts and its main findings. We then report on results from a new user study with a clearly predefined task, which examines how users leverage the system and how the system evolves to match their needs. While we previously showed that using EVE, domain experts were able to formulate interesting hypotheses and reach new insights when exploring freely, our new findings indicate that users, guided by the interactive evolutionary algorithm, are able to converge quickly to an interesting view of their data when a clear task is specified. We provide a detailed analysis of how users interact with an evolutionary algorithm and how the system responds to their exploration strategies and evaluation patterns. Our work aims at building a bridge between the domains of visual analytics and interactive evolution. The benefits are numerous, in particular for evaluating interactive evolutionary computation (IEC) techniques based on user study methodologies.

Abstract We present an Evolutionary Visual Exploration (EVE) system that combines visual analytics with stochastic optimisation to aid the exploration of multidimensional datasets characterised by a large number of possible views or projections. Starting from dimensions whose values are automatically calculated by a PCA, an interactive evolutionary algorithm progressively builds (or evolves) non‐trivial viewpoints in the form of linear and non‐linear dimension combinations, to help users discover new interesting views and relationships in their data. The criteria for evolving new dimensions is not known a priori and are partially specified by the user via an interactive interface: (i) The user selects views with meaningful or interesting visual patterns and provides a satisfaction score. (ii) The system calibrates a fitness function (optimised by the evolutionary algorithm) to take into account the user input, and then calculates new views. Our method leverages automatic tools to detect interesting visual features and human interpretation to derive meaning, validate the findings and guide the exploration without having to grasp advanced statistical concepts. To validate our method, we built a prototype tool (EvoGraphDice) as an extension of an existing scatterplot matrix inspection tool, and conducted an observational study with five domain experts. Our results show that EvoGraphDice can help users quantify qualitative hypotheses and try out different scenarios to dynamically transform their data. Importantly, it allowed our experts to think laterally, better formulate their research questions and build new hypotheses for further investigation.

Visualization of large and complex datasets is a research challenge, especially in frameworks like industrial design, decision making and visual analytics. Interactive Evolution, used not only as an optimisation tool, but also as an exploration tool may provide some versatile solutions to this challenge. This paper presents an attempt in this direction with the EvoGraphDice prototype, developed on top of GraphDice, a general purpose visualization freeware for multidimensional visualization based on scatterplot matrices. EvoGraphDice interactively evolves compound additional dimensions, that provide new viewpoints on a multidimensional dataset. Compound dimensions are linear combination of terms based on the initial data dimensions, they are initialised with a Principal Component Analysis (PCA), and modified progressively by the interactive evolution process. Various interactions are available to the user, either in a transparent way, via a capture of mouse-clicks, or in a fully controlled manner, where the user has the opportunity to modify or include his own compound dimension in the evolved population, control the search space, or do some interactive queries. EvoGraphDice is tested on a synthetic dataset of dimension 6, where a known dependency is rediscovered via interactive manipulation. A second example is presented, based on a real dataset of dimension 13, provided by an industrial partner. Our experiments prove the potential of this interactive approach, and allow us to sketch future directions of development for the EvoGraphDice prototype.

We propose a cooperative-coevolution - Parisian trend - algorithm, IMPEA (Independence Model based Parisian EA), to the problem of Bayesian networks structure estimation. It is based on an intermediate stage which consists of evaluating an independence model of the data to be modelled. The Parisian cooperative coevolution is particularly well suited to the structure of this intermediate problem, and allows to represent an independence model with help of a whole population, each individual being an independence statement, i.e. a component of the independence model. Once an independence model is estimated, a Bayesian network can be built. This two level resolution of the complex problem of Bayesian network structure estimation has the major advantage to avoid the difficult problem of direct acyclic graph representation within an evolutionary algorithm, which causes many troubles related to constraints handling and slows down algorithms. Comparative results with a deterministic algorithm, PC, on two test cases (including the Insurance BN benchmark), prove the efficiency of IMPEA, which provides better results than PC in a comparable computation time, and which is able to tackle more complex issues than PC.

This paper describes a speciation method that allows an evolutionary process to learn several robot behaviors using a single execution. Species are created in behavioral space in order to promote the discovery of different strategies that can solve the same navigation problem. Candidate neurocontrollers are grouped into species based on their corresponding behavior signature, which represents the traversed path of the robot within the environment.Behavior signatures are encoded using character strings and are compared using the string edit distance. The proposed approach is better suited for an evolutionary robotics problem than speciating in objective or topological space. Experimental comparison with the NEAT method confirms the usefulness of the proposal.

In this paper, a multiobjective (MO) learning approach to image feature extraction is described, where Pareto-optimal interest point (IP) detectors are synthesized using genetic programming (GP). IPs are image pixels that are unique, robust to changes during image acquisition, and convey highly descriptive information. Detecting such features is ubiquitous to many vision applications, e.g. object recognition, image indexing, stereo vision, and content based image retrieval. In this work, candidate IP operators are automatically synthesized by the GP process using simple image operations and arithmetic functions. Three experimental optimization criteria are considered: 1) the repeatability rate; 2) the amount of global separability between IPs; and 3) the information content captured by the set of detected IPs. The MO-GP search considers Pareto dominance relations between candidate operators, a perspective that has not been contemplated in previous research devoted to this problem. The experimental results suggest that IP detection is an illposed problem for which a single globally optimum solution does not exist. We conclude that the evolved operators outperform and dominate, in the Pareto sense, all previously man-made designs.

December 01 2008 Editorial Introduction to the Special Issue on Evolutionary Computer Vision In Special Collection: CogNet S. Cagnoni, S. Cagnoni Guest Editor Search for other works by this author on: This Site Google Scholar E. Lutton, E. Lutton Guest Editor Search for other works by this author on: This Site Google Scholar G. Olague G. Olague Guest Editor Search for other works by this author on: This Site Google Scholar Author and Article Information S. Cagnoni Guest Editor E. Lutton Guest Editor G. Olague Guest Editor Online Issn: 1530-9304 Print Issn: 1063-6560 © 2008 by the Massachusetts Institute of Technology2008 Evolutionary Computation (2008) 16 (4): 437–438. https://doi.org/10.1162/evco.2008.16.4.437 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 S. Cagnoni, E. Lutton, G. Olague; Editorial Introduction to the Special Issue on Evolutionary Computer Vision. Evol Comput 2008; 16 (4): 437–438. doi: https://doi.org/10.1162/evco.2008.16.4.437 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. © 2008 by the Massachusetts Institute of Technology2008 Article PDF first page preview Close Modal You do not currently have access to this content.

This paper presents a method for object recognition, novel object detection, and estimation of the most salient object within a set. Objects are sampled using a scale invariant region detector, and each region is characterized by the subset of texture and color descriptors selected by a Genetic Algorithm (GA). Using multiple views of an object, and multiple regions per view, objects are modeled using mixtures of Gaussians, where each object represents a possible class for a particular image region. Given a set of objects, the GA learns a corresponding Gaussian Mixture Models (GMM) for each object in the set employing a one vs. all training scheme. Thence, given an input image where interest regions are detected, if a large majority of the regions are classified as regions of object O then it is assumed that said object appears in the imaged scene. The GA’s fitness function promotes: 1) a high classification accuracy, 2) the selection of a minimal subset of descriptors, and 3) a high separation among models. The separation between two GMMs is computed using a weighted version of Fisher’s linear discriminant, which is also used to estimate the most “salient” object among the set of modeled objects. Object recognition and novel object detection are done using confidence-based classification. Hence, when a non-modeled object is sampled, the detected regions are thereby identified as belonging to an unseen object and a new GMM is trained accordingly. Experimental results on the COIL-100 data set confirm the soundness of the approach.

We present a theoretical and experimental analysis of the influence of the local irregularity of the fitness function on the behavior of an (1+1)ES. Previous work on this subject suggests that the performance of an EA strongly depends on the irregularity of the fitness function. Several irregularity measures have been derived for discrete search spaces, in order to numerically characterize this type of difficulty for EA. These characterizations are mainly based on Holder exponents. Previous studies used however a global characterization of fitness regularity (the global Holder exponent), with experimental validations being conducted on test functions with uniform regularity. This work is extended here in two ways: Results are now stated for continuous search spaces, and pointwise instead of global irregularity is considered. In addition, we present a way to modify the genetic topology to accommodate for variable regularity: the mutation radius, which controls the size of the neighbourhood of a point, is allowed to vary according to the local irregularity of the fitness function. These results are explained through a simple theoretical analysis which gives a relation between the pointwise Holder exponent and the optimal mutation radius. Several questions connected to on-line measurements and usage of regularity in EAs are raised.

We present a new bio-inspired approach applied to a problem of stereo image matching. This approach is based on an artificial epidemic process, which we call the infection algorithm. The problem at hand is a basic one in computer vision for 3D scene reconstruction. It has many complex aspects and is known as an extremely difficult one. The aim is to match the contents of two images in order to obtain 3D information that allows the generation of simulated projections from a viewpoint that is different from the ones of the initial photographs. This process is known as view synthesis. The algorithm we propose exploits the image contents in order to produce only the necessary 3D depth information, while saving computational time. It is based on a set of distributed rules, which propagate like an artificial epidemic over the images. Experiments on a pair of real images are presented, and realistic reprojected images have been generated.

Interactive evolutionary algorithms (IEA) often suffer from what is called the "user bottleneck". In this paper, we propose and analyze a method to limit the user interactions, while still providing sufficient informations for the EA to converge. The method has been currently developed on a multifractal image denoising application: a multifractal denoising method is adapted to complex images, but depends on a set of parameters that are quite difficult to tune by hand. A simple IEA has been developed for this purpose in a previous work. We now experiment an approximation of the user judgment, via a "fitness map", that helps to reduce the number of user-interactions. The method is easily extensible to other interactive, or computationally expensive, evolutionary schemes.

We present a multiobjective methodology, based on evolutionary computation, for solving the sensor planning problem for an active vision system. The application of different representation schemes, that allow to consider either fixed or variable size camera networks in a single evolutionary process, is studied. Furthermore, a novel representation of the recombination and mutation operators is brought forth. The developed methodology is incorporated into a 3D simulation environment and experimental results shown. Results validate the flexibility and effectiveness of our approach and offer new research alternatives in the field of sensor planning.

An attempt is made to apply ant colony optimization (ACO) heuristics to an E-learning problem: the pedagogic material of an online teaching Web site for high school students is modelled as a navigation graph where nodes are exercises or lessons and arcs are hypertext links. The arcs' valuation, representing the pedagogic structure and conditioning the Web site's presentation, is gradually modified through the release and evaporation of virtual pheromones that reflect the successes and failures of students roaming around the graph. A compromise is expected to emerge between the pedagogic structure as originally dictated by professors, the collective experience of the whole pool of students and the particularities of each individual. The purpose of this study conducted for Paraschool, the leading French E-learning company is twofold: enhancing the Web site by making its presentation intelligently dynamic and providing the pedagogical team with a refined auditing tool that could help it identify the strengths and weaknesses of its pedagogic choices.

The aim of this paper is to show that the common belief, in the evolutionary community, that evaluation time usually takes over 90% of the total time, is far from being always true. In fact, many real-world applications showed a much lower percentage. This raises several questions, one of them being the balance between fitness and operators computational complexity: what is the use of elaborating smart evolutionary operators to reduce the number of evaluations if as a result, the total computation time is increased?.

We present a new approach to performing molecular simulations using evolutionary algorithms. The main application is the simulation of dense amorphous polymers and the goal is to improve the efficiency of sampling, in other words to obtain valid samples from the phase state more rapidly. Our approach is based on parallel Markovian Monte Carlo simulations of the same physico-chemical system, where we optimise some Monte Carlo parameters by means of a real coded genetic algorithm.

Non-linear Iterated Function Systems (IFSs) are very powerful mathematical objects related to fractal theory, that can be used in order to generate (or model) very irregular shapes. We investigate how genetic programming techniques can be efficiently exploited in order to generate randomly or interactively artistic "fractal" 2D shapes. Two applications are presented for different types of nonlinear IFSs: interactive generation of mixed IFS attractors using a classical GP scheme; and random generation of Polar IFS attractors based on an "individual" approach of GP.

We present a deception analysis for Holder functions. Our approach uses a decomposition on the Haar basis, which reflects in a natural way the Holder structure of the function. This allows the relation of the deception, the Holder exponent, and some parameters of the genetic algorithms (GAs). These results prove that deception is connected to the irregularity of the fitness function and shed a new light on the schema theory. In addition, this analysis may assist in understanding the influence of some of the parameters on the performance of a GA.

We investigate the use of genetic algorithms (GAs) for image primitives extraction (such as segments, circles, ellipses or quadrilaterals). This approach completes the well-known Hough transform, in the sense that GAs are efficient when the Hough approach becomes too expensive in memory, i.e. when we search for complex primitives having more than 3 or 4 parameters. A GA is a stochastic technique, relatively slow, but which provides with an efficient tool to search in a high dimensional space. The philosophy of the method is very similar to the Hough transform, which is to search an optimum in a parameter space. However, we will see that the implementation is different.

We propose a method to locate three vanishing points on an image, corresponding to three orthogonal directions of the scene. This method is based on two cascaded Hough transforms. We show that, even in the case of synthetic images of high quality, a naive approach may fail, essentially because of the errors due to the limitation of the image size. We take into account these errors as well as errors due to detection inaccuracy of the image segments, and provide a method efficient, even in the case of real complex scenes.>

We propose a method to locate three vanishing points on an image corresponding to three orthogonal directions of the scene. This method is based upon the Hough Transform. With the help of a correction of errors due to the limitation of the retina, and errors due to the detection inaccuracy of the image segments, this method was improved to work on noisy images of real complex scenes.