GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference

Full Citation in the ACM Digital Library

SESSION: Real world applications

A genetic algorithm approach to virtual topology design for multi-layer communication networks

  • Uwe Bauknecht

The core networks of current telecommunication infrastructures are typically engineered as multi-layer networks. The uppermost layer is defined by the virtual topology, which determines the logical connections between core network routers. This topology is realized by optical paths in the lower layer, which is defined by optical fiber connections between network nodes. Minimizing the hardware cost incurred by these optical paths for a given set of traffic demands is a common combinatorial optimization problem in network planning, often approached by Mixed-Integer Linear Programming. However, increasing network densities and the introduction of additional constraints will impact tractability of future network problems.

In order to provide a more scalable method, we suggest a Genetic Algorithm-based approach that optimizes the virtual topology and subsequently derives the remaining parameters from it. Our genetic encoding utilizes a combination of spanning trees and augmentation links to quickly form meaningful topologies. We compare the results of our approach to known linear programming solutions in simple scenarios and to a competing heuristic based on Simulated Annealing in large-scale problems.

Evolutionary minimization of traffic congestion

  • Maximilian Böther
  • Leon Schiller
  • Philipp Fischbeck
  • Louise Molitor
  • Martin S. Krejca
  • Tobias Friedrich

Traffic congestion is a major issue that can be solved by suggesting drivers alternative routes they are willing to take. This concept has been formalized as a strategic routing problem in which a single alternative route is suggested to an existing one. We extend this formalization and introduce the Multiple-Routes problem, which is given a start and destination and aims at finding up to n different routes that the drivers strategically disperse over, minimizing the overall travel time of the system.

Due to the NP-hard nature of the problem, we introduce the Multiple-Routes evolutionary algorithm (MREA) as a heuristic solver. We study several mutation and crossover operators and evaluate them on real-world data of Berlin, Germany. We find that a combination of all operators yields the best result, improving the overall travel time by a factor between 1.8 and 3, in the median, compared to all drivers taking the fastest route. For the base case n = 2, we compare our MREA to the highly tailored optimal solver by Bläsius et al. [ATMOS 2020] and show that, in the median, our approach finds solutions of quality at least 99.69% of an optimal solution while only requiring 40 % of the time.

Accelerated evolutionary induction of heterogeneous decision trees for gene expression-based classification

  • Marcin Czajkowski
  • Krzysztof Jurczuk
  • Marek Kretowski

Decision trees (DTs) are popular techniques in the field of eXplainable Artificial Intelligence. Despite their effectiveness in solving various classification problems, they are not compatible with modern biological data generated with high-throughput technologies. This work aims to combine evolutionary induced DT with a recently developed concept designed directly for gene expression data, called Relative eXpression Analysis (RXA). We propose a new solution, termed Evolutionary Heterogeneous Decision Tree (EvoHDTree), which uses both classical univariate and bivariate tests that focus on the relative ordering and weight relationships between the genes in the splitting nodes. The search for the decision tree structure, node representation, and splits is performed globally by the evolutionary algorithm.

To meet the huge computational demands, we enriched our solution with more than a dozen specialized variants of recombination operators, GPU-computed local search components, OpenMP parallelization, and built-in gene ranking to improve evolutionary convergence. Experiments performed on cancer-related gene expression-based data show that the proposed solution finds accurate and much simpler interactions between genes. Importantly, the patterns discovered by EvoHDTree are easy to understand and to some extent supported by biological evidence in the literature.

Zeroth-order optimizer benchmarking for 3D performance capture: a real-world use case analysis

  • Alexandros Doumanoglou
  • Petros Drakoulis
  • Kyriaki Christaki
  • Nikolaos Zioulis
  • Vladimiros Sterzentsenko
  • Antonis Karakottas
  • Dimitrios Zarpalas
  • Petros Daras

In the field of 3D Human Performance Capture, a high-quality 3D scan of the performer is rigged and skinned to an animatable 3D template mesh that is subsequently fitted to the captured performance's RGB-D data. Template fitting is accomplished via solving for the template's pose parameters that better explain the performance data at each recorded frame. In this paper, we challenge open implementations of zeroth-order optimizers to solve the template fitting problem in a human performance capture dataset. The objective function that we employ approximates, the otherwise costly to evaluate, 3D RMS hausdorff distance between the animated template and the 3D mesh reconstructed from the depth data (target mesh) at an individual recorded frame. We distinguish and benchmark the optimizers, in three different real-world scenarios, two of which are based on the geometric proximity of the template to the target in individual frames, while in the third one we fit the template sequentially to all target frames of the recorded sequence. Conclusions of this work can serve as a reference for future optimizer implementations and our findings can server as a baseline for future multi-objective optimization approaches. We make part of our benchmark and experiment setup publicly available (https://github.com/VCL3D/nevergrad, https://github.com/VCL3D/PerformanceCapture/releases/).

Evolutionary meta reinforcement learning for portfolio optimization

  • Myoung Hoon Ha
  • Seung-geun Chi
  • Sangyeop Lee
  • Yujin Cha
  • Moon Byung-Ro

Portfolio optimization is a control problem whose objective is to find the optimal strategy for the process of selecting the proportions of assets that can provide the maximum return. Conventional approaches formulate the problem as a single Markov decision process and apply reinforcement learning methods to provide solutions. However, it is well known that financial markets involve non-stationary processes, leading to violations of this assumption in these methods. In this work, we reformulate the portfolio optimization problem to deal with the non-stationary nature of financial markets. In our approach, we divide a long-term process into multiple short-term processes to adapt to context changes and consider the portfolio optimization problem as a multitask control problem. Thereafter, we propose an evolutionary meta reinforcement learning approach to search for an initial policy that can quickly adapt to the upcoming target tasks. We model the policies as convolutional networks that can score the match of the patterns in market data charts. Finally, we test our approach using real-world cryptographic currency data and show that it adapts well to the changes in the market and leads to better profitability.

A genetic algorithm for AC optimal transmission switching

  • Masood Jabarnejad

Optimal transmission switching (OTS) is a new practice in power systems and can improve the economics of electric power systems integrated with renewable resources such as wind. In OTS modeling binary decision variables are added to the optimal power flow (OPF) problem to represent on and off switching status of lines. This extension to alternative current optimal power flow (ACOPF) problem results in a mixed integer nonlinear program (MINLP) which is not guaranteed to be solved optimally by existing solution methods and also requires excessive computation times for large real systems. In this paper we develop a genetic algorithm (GA) for ACOPF based OTS problem. In our GA approach we benefit from the structure of power transmission network and develop a line scoring method and a graphical distance based local improvement technique to better search the solution space. We compare our proposed genetic algorithm with two greedy heuristics on test power systems with renewable resources of energy. The results show that our proposed approach finds more economic solutions especially in larger power systems.

Design of specific primer sets for SARS-CoV-2 variants using evolutionary algorithms

  • Alejandro Lopez Rincon
  • Carmina A. Perez Romero
  • Lucero Mendoza Maldonado
  • Eric Claassen
  • Johan Garssen
  • Aletta D. Kraneveld
  • Alberto Tonda

Primer sets are short DNA sequences of 18-22 base pairs, that can be used to verify the presence of a virus, and designed to attach to a specific part of a viral DNA. Designing a primer set requires choosing a region of DNA, avoiding the possibility of hybridization to a similar sequence, as well as considering its GC content and Tm (melting temperature). Coronaviruses, such as SARS-CoV-2, have a considerably large genome (around 30 thousand nucleotides) when compared to other viruses. With the rapid rise and spread of SARS-CoV-2 variants, it has become a priority to breach our lack of specific primers available for diagnosis of this new variants. Here, we propose an evolutionary-based approach to primer design, able to rapidly deliver a high-quality primer set for a target sequence of the virus variant. Starting from viral sequences collected from open repositories, the proposed approach is proven able to uncover a specific primer set for the B.1.1.7 SARS-CoV-2 variant. Only recently identified, B.1.1.7 is already considered potentially dangerous, as it presents a considerably higher transmissibility when compared to other variants.

An efficient computational approach for automatic itinerary planning on web servers

  • Zeyuan Ma
  • Hongshu Guo
  • Yinxuan Gui
  • Yue-Jiao Gong

The automatic itinerary planning service requires to generate multiple-day schedules automatically under user-specified POIs and constraints. Knowing as an NP-Hard optimization problem, the task is commonly solved by (meta-)heuristic algorithms such as the genetic algorithms (GAs). However, considering the concurrent requests received by a web server in practice, the time efficiency of the existing itinerary planners can be rather unsatisfactory. To address the issue, this paper proposes a computational approach that hybridizing a GA with the reinforcement learning (RL) technology. The benefit is that we no longer need to re-execute the GA for each new request arrived. Instead, the approach keeps the historical solutions in track and maintains a RL agent to sequentially decide how to handle each new request. Experimental results show that the proposed approach is able to stably provide high-quality solutions, while greatly reducing the average time overhead of the web server.

Continuously running genetic algorithm for real-time networking device optimization

  • Amit Mandelbaum
  • Doron Haritan
  • Natali Shechtman

Networking devices deployed in ultra-scale data centers must run perfectly and in real-time. The networking device performance is tuned using the device configuration registers. The optimal configuration is derived from the network topology and traffic patterns. As a result, it is not possible to specify a single configuration that fits all scenarios, and manual tuning is required in order to optimize the devices' performance. Such tuning slows down data center deployments and consumes massive resources. Moreover, as traffic patterns change, the original tuning becomes obsolete and causes degraded performance. This necessitates expensive retuning, which in some cases is infeasible.

In this work, we present ZTT: a continuously running Genetic Algorithm that can be used for online, automatic tuning of the networking device parameters. ZTT is adaptive, fast to respond and have low computational costs required for running on a networking device. We test ZTT in a diversity of real-world traffic scenarios and show that it is able to obtain a significant performance boost over static configurations suggested by experts. We also demonstrate that ZTT is able to outperform alternative search algorithms like Simulated Annealing and Recursive Random Search even when those are adapted to better match the task at hand.

Evaluating medical aesthetics treatments through evolved age-estimation models

  • Risto Miikkulainen
  • Elliot Meyerson
  • Xin Qiu
  • Ujjayant Sinha
  • Raghav Kumar
  • Karen Hofmann
  • Yiyang Matt Yan
  • Michael Ye
  • Jingyuan Yang
  • Damon Caiazza
  • Stephanie Manson Brown

Estimating a person's age from a facial image is a challenging problem with clinical applications. Several medical aesthetics treatments have been developed that alter the skin texture and other facial features, with the goal of potentially improving patient's appearance and perceived age. In this paper, this effect was evaluated using evolutionary neural networks with uncertainty estimation. First, a realistic dataset was obtained from clinical studies that makes it possible to estimate age more reliably than e.g. datasets of celebrity images. Second, a neuroevolution approach was developed that customizes the architecture, learning, and data augmentation hyperparameters and the loss function to this task. Using state-of-the-art computer vision architectures as a starting point, evolution improved their original accuracy significantly, eventually outperforming the best human optimizations in this task. Third, the reliability of the age predictions was estimated using RIO, a Gaussian-Process-based uncertainty model. Evaluation on a real-world Botox treatment dataset shows that the treatment has a quantifiable result: The patients' estimated age is reduced significantly compared to placebo treatments. The study thus shows how AI can be harnessed in a new role: To provide an objective quantitative measure of a subjective perception, in this case the proposed effectiveness of medical aesthetics treatments.

Multi-objective optimization of item selection in computerized adaptive testing

  • Dena F. Mujtaba
  • Nihar R. Mahapatra

Computerized-adaptive testing (CAT) is a form of assessment in which items/questions are administered based upon a test taker's ability (i.e., their estimated proficiency, such as a knowledge, skill, or personality characteristic). CAT is regularly used in psychological studies, medical exams, and standardized testing to reduce test length and improve measurement accuracy and precision. A key challenge in CAT is item selection. Past algorithms have been designed based on criteria such as item difficulty and maximum Fisher information. However, these only consider a fixed-length test, which may result in it being longer or less precise. To address this problem, we formulate a new multi-objective optimization problem to model the trade-off between test length and precision. A binary population-based genetic algorithm, NSGA-II, is used to obtain the set of Pareto-optimal solutions by maximizing precision and minimizing the number of questions. We evaluate our approach with a simulated study using four standard personality assessments. We also investigate the influence of test response types (e.g., binary versus categorical response) and number of variables (i.e., the number of possible items) on performance. The results obtained show multi-objective optimization can be used in CAT to minimize overall test length and improve measurement precision and overall accuracy.

A simple evolutionary algorithm guided by local mutations for an efficient RNA design

  • Nono S. C. Merleau
  • Matteo Smerlak

Inverse folding an RNA secondary structure of length L can be understood as searching in space S = {A, C, G, U}L, one or many RNA sequence(s) that fold(s) into that structure. Solving this problem is a prerequisite for RNA design and is still a real challenge in bio-engineering. To improve the RNA inverse folding, we investigate an evolutionary algorithm implementing local mutations taking into account the nucleotide and canonical base pair distributions. We implement our algorithm as a simple open-source python program called aRNAque1. The empirical results show that aRNAque can solve some target structures previously unsolvable by the existing evolutionary algorithms benchmarked in this work. On the two benchmark datasets, ≈ 72% of the EteRNA100 dataset (respectively ≈ 92% using the Turner1999 energy parameter sets) and ≈ 87% of the non-EteRNA100 dataset and the designed sequences are of better quality. In comparison to existing tools, our EA implementation also shows a significant computational time improvement.

Multi-objective optimization across multiple concepts: a case study on lattice structure design

  • Brandon Parker
  • Hemant Kumar Singh
  • Tapabrata Ray

Evolutionary multi-objective optimization (EMO) is often used to deal with practical problems in engineering design to identify products that exhibit the best possible compromise between multiple conflicting performance criteria. Much of the literature in EMO considers algorithmic developments and benchmarking problems involving a single concept only. However, in practice, there could be many applications where the solution of a given problem may be represented using multiple concepts, and optimizing each one of them individually to obtain the overall Pareto front may be inefficient. To address this gap, in this study, we firstly develop computer-aided models of multiple concepts for a simulation-based problem which can serve as a good application of multi-concept optimization. The problem involves the design of lattice structures with different types of unit cells (each constituting a concept), which can be customized to suit a range of real-world applications such as design of structures with minimal thermal expansion, low weight and high rigidity etc. Furthermore, we develop baseline evolutionary strategies to search across multiple concepts simultaneously. Empirical experiments show that the presented strategies are able to outperform conventional single concept-based approach. Moreover, some challenges are also uncovered which prompts the need for further developments.

MA-ABC: a memetic algorithm optimizing attractiveness, balance, and cost for capacitated Arc routing problems

  • Muhilan Ramamoorthy
  • Stephanie Forrest
  • Violet R. Syrotiuk

Services such as garbage collection, road gritting, street sweeping, and power line inspection can each be formulated as a capacitated arc routing problem (CARP). The traditional formulation of CARP has the goal of minimizing the total cost of the routes making up a solution. Recently, operators of such services require routes that are balanced and visually attractive in addition to low cost. Routes that are balanced are about equal in length and provide fair work assignments. Visually attractive routes are subjective, but they usually involve non-crossing routes that provide well defined service areas. These additional features are important because they address operational complexities that arise from using the routes in practice. This paper presents MA-ABC, a memetic algorithm to find solutions for CARP that maximize route attractiveness and balance, while minimizing total cost. A novel fitness function combines route overlap with route contiguity to assess route attractiveness. MA-ABC is the first to incorporate attractiveness in a three-objective search for heuristic solutions for CARP. Experimental results on CARP benchmark instances show that MA-ABC finds a diverse set of heuristic solutions at the Pareto front, providing a wide choice for service operators to tradeoff design objectives.

Level generation for angry birds with sequential VAE and latent variable evolution

  • Takumi Tanabe
  • Kazuto Fukuchi
  • Jun Sakuma
  • Youhei Akimoto

Video game level generation based on machine learning (ML), in particular, deep generative models, has attracted attention as a technique to automate level generation. However, applications of existing ML-based level generations are mostly limited to tile-based level representation. When ML techniques are applied to game domains with non-tile-based level representation, such as Angry Birds, where objects in a level are specified by real-valued parameters, ML often fails to generate playable levels. In this study, we develop a deep-generative-model-based level generation for the game domain of Angry Birds. To overcome these drawbacks, we propose a sequential encoding of a level and process it as text data, whereas existing approaches employ a tile-based encoding and process it as an image. Experiments show that the proposed level generator drastically improves the stability and diversity of generated levels compared with existing approaches. We apply latent variable evolution with the proposed generator to control the feature of a generated level computed through an AI agent's play, while keeping the level stable and natural.

An evolutionary multi-objective feature selection approach for detecting music segment boundaries of specific types

  • Igor Vatolkin
  • Fabian Ostermann
  • Meinard Müller

The goal of music segmentation is to identify boundaries between parts of music pieces which are perceived as entities. Segment boundaries often go along with a change in musical properties including instrumentation, key, and tempo (or a combination thereof). One can consider different types (or classes) of boundaries according to these musical properties. In contrast to existing datasets with missing specifications of changing properties for annotated boundaries, we have created a set of artificial music tracks with precise annotations for boundaries of different types. This allows for a profound analysis and interpretation of annotated and predicted boundaries and a more exhaustive comparison of different segmentation algorithms. For this scenario, we formulate a novel multi-objective optimisation task that identifies boundaries of only a specific type. The optimisation is conducted by means of evolutionary multi-objective feature selection and a novelty-based segmentation approach. Furthermore, we provide lists of audio features from non-dominated fronts which most significantly contribute to the estimation of given boundaries (the first objective) and most significantly reduce the performance of the prediction of other boundaries (the second objective).

Solving the paintshop scheduling problem with memetic algorithms

  • Wolfgang Weintritt
  • Nysret Musliu
  • Felix Winter

Finding efficient production schedules for automotive paint shops is a challenging task and several paint shop problem variants have been investigated in the past. In this work we focus on a recently introduced real-life paint shop scheduling problem appearing in the automotive supply industry where car parts, which need to be painted, are placed upon carrier devices. These carriers are placed on a conveyor belt and moved into painting cabins, where robots apply the paint. The aim is to find an optimized production schedule for the painting of car parts.

In this paper, we propose a memetic algorithm to solve this problem. An initial population is generated, followed by the constant evolution of generations. Selection, crossover, mutation, and local improvement operators are applied in each generation. We design three novel crossover operators that consider problem-specific knowledge. Finally, we carefully configure our algorithm, including automated and manual parameter tuning.

Using a set of available real-life benchmark instances from the literature, we perform an extensive experimental evaluation of our algorithm. The experimental results show that our memetic algorithm yields competitive results for small- and medium-sized instances and is able to set new upper bounds for some of the problem instances.

Heuristic strategies for solving complex interacting stockpile blending problem with chance constraints

  • Yue Xie
  • Aneta Neumann
  • Frank Neumann

The stockpile blending problem seeks to determine how many tonnages of ore that stockpiles provide and to which parcels. This scheduling model maximizes the volume of valuable material in the final production subject to resource capacities, constraints for mill machines, and customer requirements. Motivated by the uncertainty in the geologic input date which affects optimization, we consider the stockpile blending problem with uncertainty in material grades. A non-linear continuous optimization model developed here to integrate uncertain variables to optimization. We introduce chance constraints that are used to guarantee the constraint is violated with a small probability to tackle the stochastic material grades. We investigate a well-known approach in this paper, which is used to solve optimization problems over continuous space, namely the differential evolution (DE) algorithm. In the experiment section, we compare the performance of the algorithm with the deterministic model and three chance constraint models by using a synthetic benchmark. We also evaluate the effectiveness of different chance constraints.