Publications‎ > ‎

International Conference Publications

The DU Map: A Visualization to Gain Insights into Genotype-Phenotype Mapping and Diversity

posted Apr 20, 2017, 5:52 AM by Eric Medvet   [ updated Apr 20, 2017, 5:52 AM ]

  • 8th annual workshop on Visualisation in Genetic and Evolutionary Computation (VizGEC), 2017, Berlin (Germany), to appear
  • Eric Medvet, Tea Tušar
The relation between diversity and genotype to phenotype mapping has been the focus of several studies. In those Evolutionary Algorithms (EAs) where the genotype is a sequence of symbols, the contribution of each of those symbols in determining the phenotype may vary greatly, possibly being null. In the latter case, the unused portions of the genotype may host a large amount of the population diversity. However, reasoning on coarse-grained measures makes it hard to validate such a claim and, more in general, to gain insights into the interactions between genotype-phenotype mapping and diversity. In this paper, we propose a novel visualization which summarizes in a single, compact heat map (the DU map), three kinds of information: (a) how diverse are the genotypes in the population at the level of single symbols; (b) if and to what degree each individual symbol in the genotype contributes to the phenotype; (c) how the two previous measures vary during the evolution. We experimentally verify the usefulness of the DU map w.r.t. its primary goal and, more broadly, when used to analyze different EA design options. We apply it to Grammatical Evolution (GE) as it constitutes an ideal testbed for the DU map, due to the availability of different mapping functions.

Evolvability in Grammatical Evolution

posted Mar 22, 2017, 3:30 AM by Eric Medvet   [ updated Mar 22, 2017, 3:32 AM ]

  • ACM Genetic and Evolutionary Computation Conference (GECCO), 2017, Berlin (Germany), to appear
  • Eric Medvet, Fabio Daolio, Danny Tagliapietra
Evolvability is a measure of the ability of an Evolutionary Algorithm (EA) to improve the fitness of an individual when applying a genetic operator. Other than the specific problem, many aspects of the EA may impact on the evolvability, most notably the genetic operators and, if present, the genotype-phenotype mapping function. Grammatical Evolution (GE) is an EA in which the mapping function plays a crucial role since it allows to map any binary genotype into a program expressed in any user-provided language, defined by a context-free grammar. While GE mapping favored a successful application of GE to many different problems, it has also been criticized for scarcely adhering to the variational inheritance principle, which itself may hamper GE evolvability. In this paper, we experimentally study GE evolvability in different conditions, that is, problems, mapping functions, genotype sizes, and genetic operators. Results suggest that there is not a single factor determining GE evolvability: in particular, the mapping function alone does not deliver better evolvability regardless of the problem. Instead, GE redundancy, which itself is the result of the combined effect of several factors, has a strong impact on the evolvability.

Hierarchical Grammatical Evolution

posted Mar 22, 2017, 3:28 AM by Eric Medvet   [ updated Mar 31, 2017, 6:57 AM ]

  • ACM Genetic and Evolutionary Computation Conference (GECCO), 2017, Berlin (Germany), to appear
  • Eric Medvet
We present Hierarchical Grammatical Evolution (HGE) and its variant WHGE, two novel genotype-phenotype mapping procedures to be used in the Grammatical Evolution (GE) framework. HGE/WHGE are designed to exhibit better variational inheritance than standard GE without imposing any constraint on the structure of the genotype nor on the genetic operators. Our proposal considers the phenotype as a hierarchy of non-terminal expansions and is based on two key ideas: (i) the closer the non-terminal to be expanded to the root of the hierarchy, the larger the genotype substring determining its expansion, and
(ii) upon expansion, a non-terminal divides its genotype substring among the resulting non-terminals. We experimentally evaluate our proposals on a set of benchmark problems and show that for the majority of them WHGE outperforms GE (and its variant piGE).

An Effective Diversity Promotion Mechanism in Grammatical Evolution

posted Mar 22, 2017, 3:23 AM by Eric Medvet   [ updated Mar 22, 2017, 3:23 AM ]

  • ACM Genetic and Evolutionary Computation Conference (GECCO), 2017, Berlin (Germany), to appear
  • Eric Medvet, Alberto Bartoli, Giovanni Squillero
Grammatical Evolution is an Evolutionary Algorithm which can evolve programs in any language described by a context-free grammar. A sequence of bits (the genotype) is transformed into a string of the language (the phenotype) by means of a mapping function, and eventually into a fitness value. Unfortunately, the flexibility brought by the mapping is also likely to introduce non-locality phenomena, reduce diversity, and consequently hamper the effectiveness of the algorithm. In this paper, we propose a novel technique for promoting diversity, able to  operate on three different levels: genotype, phenotype, and fitness. The technique is quite general, independent both from the specific problem being tackled and from other components of the evolutionary algorithm, such as genotype-phenotype mapping, selection criteria, and genetic operators. We experimentally demonstrate its efficacy in a wide range of conditions and from different points of view. The results also confirm the preponderant importance of the phenotype-level analyses in diversity promotion.

Road Traffic Rules Synthesis using Grammatical Evolution

posted Jan 11, 2017, 1:59 PM by Eric Medvet   [ updated Apr 6, 2017, 3:12 AM ]

We consider the problem of the automatic synthesis of road traffic rules, motivated by a future scenario in which human and machine-based drivers will coexist on the roads: in that scenario, current road rules may be either unsuitable or inefficient. We approach the problem using Grammatical Evolution (GE). To this end, we propose a road traffic model which includes concepts amenable to be regulated (e.g., lanes, intersections) and which allows drivers to temporarily evade traffic rules when there are no better alternatives. In our GE framework, each individual is a set of rules and its fitness is a weighted sum of traffic efficiency and safety, as resulting from a number of simulations where all drivers are subjected to the same rules. Experimental results show that our approach indeed generates rules leading to a safer and more efficient traffic than enforcing no rules or rules similar to those currently used.

A Comparative Analysis of Dynamic Locality and Redundancy in Grammatical Evolution

posted Jan 11, 2017, 1:55 PM by Eric Medvet   [ updated Mar 22, 2017, 3:17 AM ]

Grammatical Evolution (GE) is an Evolutionary Algorithm which can address any problem whose solution space may be described in terms of a context-free grammar: its most salient feature is a procedure which maps genotypes to phenotypes using the grammar production rules. The search effectiveness of GE may be affected by low locality and high redundancy, which can prevent GE to comply with the basic principle that offspring should inherit some traits from their parents. Indeed, many studies previously investigated the locality and redundancy of GE as originally proposed in [Ryan et al., 1998]. In this paper, we extend those results by considering redundancy and locality during the evolution, rather than statically, hence trying to understand if and how they are influenced by the selective pressure determined by the fitness. Moreover, we consider not only the original GE formulation, but three other variants proposed later. We experimentally find that there is an interaction between locality/redundancy and other evolution-related measures, namely diversity and growth of individual size.

Segmentation of Mosaic Images based on Deformable Models using Genetic Algorithms

posted Oct 27, 2016, 1:39 AM by Eric Medvet   [ updated Oct 27, 2016, 1:39 AM ]

  • 2nd EAI International Conference on Smart Objects and Technologies for Social Good (GOODTECHS), 2016, Venezia (Italy), to appear
  • Alberto Bartoli, Gianfranco Fenu, Eric Medvet, Felice Andrea Pellegrino, Nicola Timeus
Preservation and restoration of ancient mosaics is a crucial activity for the perpetuation of cultural heritage of many countries. Such an activity is usually based on manual procedures which are typically lengthy and costly. Digital imaging technologies have a great potential in this important application domain, from a number of points of view including smaller costs and much broader functionalities. In this work, we propose a mosaic-oriented image segmentation algorithm aimed at identifying automatically the tiles composing a mosaic based solely on an image of the mosaic itself. Our proposal consists of a Genetic Algorithm, in which we represent each candidate segmentation with a set of quadrangles whose shapes and positions are modified during an evolutionary search based on multi-objective optimization. We evaluate our proposal in detail on a set of real mosaics which differ in age and style. The results are highly promising and in line with the current state-of-the-art.

Computer Vision for the Blind: a Comparison of Face Detectors in a Relevant Scenario

posted Oct 27, 2016, 1:36 AM by Eric Medvet   [ updated Dec 6, 2016, 8:26 AM ]

  • 2nd EAI International Conference on Smart Objects and Technologies for Social Good (GOODTECHS), 2016, Venezia (Italy), to appear
  • Marco De Marco, Gianfranco Fenu, Eric Medvet, Felice Andrea Pellegrino
Motivated by the aim of developing a vision-based system to assist the social interaction of blind persons, the performance of some face detectors are evaluated. The detectors are applied to manually annotated video sequences acquired by blind persons with a glass-mounted camera and a necklace-mounted one. The sequences are relevant to the specific application and demonstrate to be challenging for all the considered detectors. A further analysis is performed to reveal how the performance is affected by some features such as occlusion, rotations, size and position of the face within the frame.

Your Paper has been Accepted, Rejected, or whatever: Automatic Generation of Scientific Paper Reviews

posted Jun 28, 2016, 12:33 AM by Eric Medvet   [ updated Sep 23, 2016, 1:08 PM ]

Peer review is widely viewed as an essential step for ensuring scientific quality of a work and is a cornerstone of scholarly publishing. On the other hand, the actors involved in the publishing process are often driven by incentives which may, and increasingly do, undermine the quality of published work, especially in the presence of unethical conduits. In this work we investigate the feasibility of a tool capable of generating fake reviews for a given scientific paper automatically. While a tool of this kind cannot possibly deceive any rigorous editorial procedure, it could nevertheless find a role in several questionable scenarios and magnify the scale of scholarly frauds.
A key feature of our tool is that it is built upon a small knowledge base, which is very important in our context due to the difficulty of finding large amounts of scientific reviews. We experimentally assessed our method with tens of human subjects. We presented to these subjects a mix of genuine and machine generated reviews and we measured the ability of our proposal to actually deceive subjects judgment. The results highlight the ability of our method to produce reviews that often look credible and may subvert the decision.

"Best Dinner Ever!!!": Automatic Generation of Restaurant Reviews with LSTM-RNN

posted Jun 22, 2016, 8:30 AM by Eric Medvet   [ updated Jan 23, 2017, 2:36 AM ]

Consumer reviews are an important information resource for people and a fundamental part of everyday decision-making. Product reviews have an economical relevance which may attract malicious people to commit a review fraud, by writing false reviews. In this work, we investigate the possibility of generating hundreds of false restaurant reviews automatically and very quickly.
We propose and evaluate a method for automatic generation of restaurant reviews tailored to the desired rating and restaurant category. A key feature of our work is the experimental evaluation which involves human users. We assessed the ability of our method to actually deceive users by presenting to them sets of reviews including a mix of genuine reviews and of machine-generated reviews. Users were not aware of the aim of the evaluation and the existence of machine-generated reviews. As it turns out, it is feasible to automatically generate realistic reviews which can manipulate the opinion of the user.

1-10 of 57