Publications‎ > ‎

International Conference Publications

GOMGE: Gene-pool Optimal Mixing on Grammatical Evolution

posted May 15, 2018, 5:41 AM by Eric Medvet   [ updated May 15, 2018, 5:54 AM ]

  • 15th International Conference on Parallel Problem Solving from Nature (PPSN), 2018, Coimbra (Portugal), to appear
  • Eric Medvet, Alberto Bartoli, Andrea De Lorenzo, Fabiano Tarlao
Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) is a recent Evolutionary Algorithm (EA) in which the interactions among parts of the solution (i.e., the linkage) are learned and exploited in a novel variation operator. We present GOMGE, the extension of GOMEA to Grammatical Evolution (GE), a popular EA based on an indirect representation which may be applied to any problem whose solutions can be described using a context-free grammar (CFG). GE is a general approach that does not require the user to tune the internals of the EA to fit the problem at hand: there is hence the opportunity for benefiting from the potential of GOMEA to automatically learn and exploit the linkage. We apply the proposed approach to three variants of GE differing in the representation (original GE, SGE, and WHGE) and incorporate in GOMGE two specific improvements aimed at coping with the high degeneracy of those representations. We experimentally assess GOMGE and show that, when coupled with WHGE and SGE, it is clearly beneficial to both effectiveness and efficiency, whereas it delivers mixed results with the original GE.

Selfish vs. Global Behavior Promotion in Car Controller Evolution

posted Apr 12, 2018, 1:46 AM by Eric Medvet   [ updated Apr 12, 2018, 1:47 AM ]

  • 1st GECCO Workshop on Decomposition Techniques in Evolutionary Optimization (DTEO), 2018, Kyoto (Japan), to appear
  • Jacopo Talamini, Giovanni Scaini, Eric Medvet, Alberto Bartoli
We consider collective tasks to be solved by simple agents synthesized automatically by means of neuroevolution. We investigate whether driving neuroevolution by promoting a form of selfish behavior, i.e., by optimizing a fitness index that synthesizes the behavior of each agent independent of any other agent, may also result in optimizing global, system-wide properties. We focus  on a specific and challenging task, i.e., evolutionary synthesis of agent as car controller for a road traffic scenario. Based on an extensive simulation-based analysis, our results indicate that even by optimizing the behavior of each single agent, the resulting system-wide performance is comparable to the performance resulting from optimizing the behavior of the system as a whole. Furthermore, agents evolved with a fitness promoting selfish behavior appear to lead to a system that is globally more robust with respect to the presence of unskilled agents.

Exploring the Application of GOMEA to Bit-string GE

posted Apr 12, 2018, 12:10 AM by Eric Medvet   [ updated Apr 12, 2018, 12:11 AM ]

  • ACM Genetic and Evolutionary Computation Conference (GECCO), 2018, Kyoto (Japan), to appear
  • Eric Medvet, Alberto Bartoli, Andrea De Lorenzo
We explore the application of GOMEA, a recent method for discovering and exploiting the model for a problem in the form of linkage, to Grammatical Evolution (GE). GE employs an indirect representation based on familiar bit-string genotypes and is applicable to any problem where the solutions may be described using a context-free grammar, which hence greatly favors its wide adoption. Being general purpose, the representation of GE raises the opportunity for benefiting from the potential of GOMEA to automatically discover and exploit the linkage. We analyze experimentally the application of GOMEA to two bit-string-based variants of GE representation (the original representation and the recent WHGE) and show that GOMEA is clearly beneficial when coupled to WHGE, whereas it delivers no significant advantages when coupled with GE.

On the Automatic Design of a Representation for Grammar-based Genetic Programming

posted Dec 27, 2017, 3:31 AM by Eric Medvet   [ updated Apr 12, 2018, 12:08 AM ]

A long-standing problem in Evolutionary Computation consists in how to choose an appropriate representation for the solutions. In this work we investigate the feasibility of synthesizing a representation automatically, for the large class of problems whose solution spaces can be defined by a context-free grammar. We propose a framework based on a form of meta-evolution in which individuals are candidate representations expressed with an ad hoc language that we have developed to this purpose. Individuals compete and evolve according to an evolutionary search aimed at optimizing such representation properties as redundancy, locality, uniformity of redundancy.
We assessed experimentally three variants of our framework on established benchmark problems and compared the resulting representations to human-designed representations commonly used (e.g., classical Grammatical Evolution). The results are promising in the sense that the evolved representations indeed exhibit better properties than the human-designed ones. Furthermore, while those improved properties do not result in a systematic improvement of search effectiveness, some of the evolved representations do improve search effectiveness over the human-designed baseline.

Impact of Code Obfuscation on Android Malware Detection based on Static and Dynamic Analysis

posted Nov 22, 2017, 8:43 AM by Eric Medvet   [ updated Feb 9, 2018, 6:21 AM ]

The huge diffusion of malware in mobile platform is plaguing users. New malware proliferates at a very fast pace: as a matter of fact, to evade the signature-based mechanism implemented in current antimalware, the application of trivial obfuscation techniques to existing malware is sufficient. In this paper, we show how the application of several morphing techniques affects the effectiveness of two widespread malware detection approaches based on Machine Learning coupled respectively with static and dynamic analysis. We demonstrate experimentally that dynamic analysis-based detection performs equally well in evaluating obfuscated and non-obfuscated malware. On the other hand, static analysis-based detection is more accurate on non-obfuscated samples but is greatly negatively affected by obfuscation: however, we also show that this effect can be mitigated by using obfuscated samples also in the learning phase.

VizMal: A Visualization Tool for Analyzing the Behavior of Android Malware

posted Nov 22, 2017, 8:38 AM by Eric Medvet   [ updated May 3, 2018, 2:26 AM ]

Malware signature extraction is currently a manual and a time-consuming process. As a matter of fact, security analysts have to manually inspect samples under analysis in order to find the malicious behavior. From research side, current literature is lacking of methods focused on the malicious behavior localization: designed approaches basically mark an entire application as malware or non-malware (i.e., take a binary decision) without knowledge about the malicious behavior localization inside the analysed sample. In this paper, with the twofold aim of assisting the malware analyst in the inspection process and of pushing the research community in malicious behavior localization, we propose VizMal, a tool for visualizing the dynamic trace of an Android application which highlights the portions of the application which look potentially malicious. VizMal performs a detailed analysis of the application activities showing for each second of the execution whether the behavior exhibited is legitimate or malicious. The analyst may hence visualize at a glance when at to which degree an application execution looks malicious.

A Language for UAV Traffic Rules in an Urban Environment and Decentralized Scenario

posted Sep 1, 2017, 4:02 AM by Eric Medvet   [ updated Oct 13, 2017, 5:48 AM ]

  • IEEE International Conference on Tools with Artificial Intelligence (ICTAI), 2017, Boston (Massachusetts, US), to appear
  • Giuseppe Lombardi, Eric Medvet, Alberto Bartoli
Unmanned Aerial Vehicles (UAVs) are becoming increasingly popular and the amount of UAV traffic in urban environments will largely increase in the future, due to profitable tasks which are particularly suited to UAVs, e.g., parcel delivery and surveillance, in particular in the context of smart cities. Trying to ensure the traffic safety and efficiency by acting on the UAV controller alone might be challenging, since the set of involved players (regulators, manufacturers, business users) is large and diversified. In this work, we address this problem by proposing a language for defining rules suitable for UAV traffic which can be enforced in a decentralized way by the UAVs themselves, without any need for communication and regardless of the UAV navigation algorithm. The language allows to express realistic rules, such as "when cruising, keep a minimum altitude", concisely and such that they can be processed online by each single UAV basing on its perception of the nearby environment. We experimentally validate the ability of our proposal to impact on the UAV traffic efficiency and safety by performing a large number of simulations with and without a set of realistic rules.

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 Jul 21, 2017, 5:11 AM ]

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 Jul 7, 2017, 9:11 AM ]

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 Jul 21, 2017, 5:15 AM ]

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).

1-10 of 64