previous day
all days

View: session overviewtalk overview

09:00-10:00 Session 11

Early poster session

10:00-11:30 Session 12A: EvoAPPS 10 Deep Bioinspired Algorithms

Deep Bioinspired Algorithms

Location: Room A
Evolving Instinctive Behaviour in Resource-Constrained Autonomous Agents Using Grammatical Evolution

ABSTRACT. Recent developments in the miniaturization of hardware have facilitated the use of robots or mobile sensory agents in many applications such as exploration of GPS-denied, hardly accessible unknown environments. This includes underground resource exploration and water pollution monitoring. One problem in scaling-down robots is that it puts significant emphasis on power consumption due to the limited energy available online. Furthermore, the design of adequate controllers for such agents is challenging as representing the system mathematically is difficult due to complexity. In that regard, Evolutionary Algorithms (EA) is a suitable choice for developing the controllers. However, the solution space for evolving those controllers is relatively large because of the wide range of the possible tunable parameters available on the hardware, in addition to the numerous number of objectives which appear on different design levels. A recently-proposed method, dubbed as Instinct Evolution Scheme (IES), offered a way to limit the solution space in these cases. This scheme uses Behavior Trees (BTs) to represent the robot behaviour in a modular, re-usable and intelligible fashion. In this paper, we improve upon the original IES by using Grammatical evolution (GE) to implement a full BT evolution model integratable with IES. A special emphasis is put on minimizing the complexity of the BT generated by GE. To test the scheme, we consider an environment exploration task on a virtual environment. Results show 85% correct reactions to environment stimuli and a decrease in relative complexity to 4.7%. Finally, the evolved BT is represented in an if-else on-chip compatible format.

An Adversarial Optimization Approach for the Development of Robust Controllers

ABSTRACT. Due to increasing popularity of electric vehicles there is rising demand for smart controller solutions that optimize the flow of energy between buildings and electric vehicles. Simple rule-based controllers are (often manually) developed and tuned for specific use case scenarios, for example a specific building, mobility usage patterns and country-specific regulations. However, it is often very difficult to correctly anticipate the exact conditions the controller has to work on so that a high performance under worst-case conditions is a very important target. In this work we use an adversarial optimization approach in order to find both challenging scenarios and controller parameterizations that perform well in those scenarios. We can show that in comparison to a standard controller, our approach can find challenging scenarios for a standard controller and controllers that outperform the baseline on those worst-case scenarios

Fake news detection using time series and user features classification

ABSTRACT. In a scenario where more and more individuals use online social network platforms as an instrument to propagate news without any control, it is necessary to design and implement new methods and techniques that guarantee the veracity of the disseminated news. In this paper, we propose a method to classify true and false news, commonly known as fake news, which exploits time series-based features extracted from the evolution of news, and features from the users involved in the news spreading. Applying our methodology over a real Twitter dataset of precategorized true and false news, we have obtained an accuracy of 84.61% in 10-fold cross-validation, and proved experimentally that all the selected features are relevant for this classification task.

10:00-11:30 Session 12B: EvoCOP 4

Best Paper Session

Location: Room B
Dynamic Compartmental Models for Large Multi-objective Landscapes and Performance Estimation

ABSTRACT. Dynamic Compartmental Models are linear models inspired by epidemiology models to study Multi- and Many-Objective Evolutionary Algorithms dynamics. So far they have been tested on small MNK-Landscapes problems with 20 variables and used as a tool for algorithm analysis, algorithm comparison, and algorithm configuration assuming that the Pareto optimal set is known. In this paper, we introduce a new set of features based only on when non-dominated solutions are found in the population, relaxing the assumption that the Pareto optimal set is known in order to use Dynamic Compartment Models on larger problems. We also propose an auxiliary model to estimate the hypervolume from the features of population dynamics that measures the changes of new non-dominated solutions in the population. The new features are tested by studying the population changes on the Adaptive ε-Sampling ε-Hood while solving 30 instances of a 3 objective, 100 variables MNK-landscape problem. We also discuss the behavior of the auxiliary model and the quality of its hypervolume estimations.

A Beam Search Approach to the Traveling Tournament Problem

ABSTRACT. The well-known traveling tournament problem is a hard optimization problem in which a double round robin sports league schedule has to be constructed while minimizing the total travel distance over all teams. The teams start and end their tours at their home venues, are only allowed to play a certain maximum number of games in a row at home or away, and must not play against each other in two consecutive rounds. The latter aspects introduce also a difficult feasibility aspect. In this work, we study a beam search approach based on a recursive state space formulation. We compare different state ordering heuristics for the beam search based on lower bounds derived by means of decision diagrams. Furthermore, we introduce a randomized beam search variant that adds Gaussian noise to the heuristic value of a node for diversifying the search in order to enable a simple yet effective parallelization. In our computational study, we use randomly generated instances to compare and tune algorithmic parameters and present final results on the classical National League and circular benchmark instances. Results show that this purely construction-based method provides mostly better solutions than existing ant-colony optimization and tabu search algorithms and it comes close to the leading simulated annealing based approaches without using any local search. For two circular benchmark instances we found new best solutions for which the last improvement was twelve years ago. The presented state space formulation and lower bound techniques could also be beneficial for exact methods like A* or DFS* and may be used to guide the randomized construction in ACO or GRASP approaches.

The Univariate Marginal Distribution Algorithm Copes Well With Deception and Epistasis

ABSTRACT. In their recent work, Lehre and Nguyen (FOGA 2019) show that the univariate marginal distribution algorithm (UMDA) needs time exponential in the parent populations size to optimize the DeceivingLeadingBlocks (DLB) problem. They conclude from this result that univariate EDAs have difficulties with deception and epistasis.

In this work, we show that this negative finding is caused by an unfortunate choice of the parameters of the UMDA. When the population sizes are chosen large enough to prevent genetic drift, then the UMDA optimizes the DLB problem with high probability with at most $\lambda(\frac{n}{2} + 2 e \ln n)$ fitness evaluations. Since an offspring population size $\lambda$ of order $n \log n$ can prevent genetic drift, the UMDA can solve the DLB problem with $O(n^2 \log n)$ fitness evaluations. In contrast, for classic evolutionary algorithms no better run time guarantee than $O(n^3)$ is known, so our result rather suggests that the UMDA can cope well with deception and epistatis.

Together with the result of Lehre and Nguyen, our result for the first time rigorously proves that running EDAs in the regime with genetic drift can lead to drastic performance losses.

10:00-11:30 Session 12C: EvoAPPS 11 Games


Location: Room C
Efficient Heuristic Policy Optimisation for a Challenging Strategic Card Game

ABSTRACT. Turn-based multi-action adversarial games are challenging scenarios in which each player turn consists of a sequence of atomic actions. The order in which an AI agent runs these atomic actions may hugely impact the outcome of the turn. One of the main challenges of game artificial intelligence is to design a heuristic function to help agents to select the optimal turn to play, given a particular state of the game. In this paper, we report results using the recently developed N-Tuple Bandit Evolutionary Algorithm to tune the heuristic function parameters. For evaluation, we measure how the tuned heuristic function affects the performance of the state-of-the-art evolutionary algorithm Online Evolution Planning. The multi-action adversarial strategy card game \textit{Legends of Code and Magic} was used as a testbed. Results indicate that the N-Tuple Bandit Evolutionary Algorithm can effectively tune the heuristic function parameters to improve the performance of the agent.

Learning the Designer's Preferences to Drive Evolution

ABSTRACT. This paper presents the Designer Preference Model, a data-driven solution that pursues to learn from user generated data in a Quality-Diversity Mixed-Initiative Co-Creativity (QD MI-CC) tool, with the aims of modelling the user's design style to better assess the tool's procedurally generated content with respect to that user's preferences. Through this approach, we aim for increasing the user's agency over the generated content in a way that neither stalls the user-tool reciprocal stimuli loop nor fatigues the user with periodical suggestion handpicking. We describe the details of this novel solution, as well as its implementation in the MI-CC tool the Evolutionary Dungeon Designer. We present and discuss our findings out of the initial tests carried out, spotting the open challenges for this combined line of research that integrates MI-CC with Procedural Content Generation through Machine Learning.

EvoCluster: An Open-Source Nature-Inspired Optimization Clustering Framework in Python

ABSTRACT. EvoCluster is an open source and cross-platform framework implemented in Python which includes the most well-known and recent nature-inspired metaheuristic optimizers that are customized to perform partitional clustering tasks. The goal of this framework is to provide a user-friendly and customizable implementation of the metaheuristic based clustering algorithms which can be utilized by experienced and non-experienced users for different applications. The framework can also be used by researchers who can benefit from the implementation of the metaheuristic optimizers for their research studies. EvoCluster can be extended by designing other optimizers, including more objective functions, adding other evaluation measures, and using more data sets. The current implementation of the framework includes ten metaheristic optimizers, thirty datasets, five objective functions, and twelve evaluation measures. The source code of EvoCluster is publicly available at (http://evo-ml.com/2019/10/25/evocluster/).