Programme

There will be 11 talks over the day. Each talk has 25 minutes allocated: 20 mins talk + 5 minutes Q+A. We also have a poster session during lunch break.

Schedule

10:00-10:30 Registration and refreshments

10:00-10:35 Welcome

10:35-12:15 Session 1

12:15-13:15 Lunch and posters

13:15-14:55 Session 2

14:55-15:15 Break

15:15-16:30 Session 3

16:30-18:00 Informal discussions

Session 1

10:35-11:00 Evolving Robust Policies for Community Energy System Management - to be presented at GECCO 2019

Emma Hart, Edinburgh Napier University

Community energy systems (CESs) are shared energy systems in which multiple communities generate and consume energy from renewable resources. At regular time intervals, each participating community decides whether to self-supply, store, trade, or sell their energy to others in the scheme or back to the grid according to a predefined policy which all participants abide by. The objective of the policy is to maximise average satisfaction across the entire CES while minimising the number of unsatisfied participants.

We propose a multi-class, multi-tree genetic programming approach to evolve a set of specialist policies that are applicable to specific conditions, relating to abundance of energy, asymmetry of generation, and system volatility. Results show that the evolved policies significantly outperform a default handcrafted policy. Additionally, we evolve a \textit{generalist} policy and compare its performance to specialist ones, finding that the best generalist policy can equal the performance of specialists in many scenarios. We claim that our approach can be generalised to any multi-agent system solving a common-pool resource allocation problem that requires the design of a suitable operating policy.

11:00-11:25 A Hybrid Metaheuristic Approach to a Real World Employee Scheduling Problem - to be presented at GECCO 2019

Kenneth Reid, University of Stirling

Employee scheduling problems are of critical importance to large businesses. These problems are hard to solve due to large numbers of conflicting constraints. While many approaches address a subset of these constraints, there is no single approach for simultaneously addressing all of them. We hybridise ‘Evolutionary Ruin & Stochastic Recreate’ and ‘Variable Neighbourhood Search’ metaheuristics to solve a real world instance of the employee scheduling problem to near optimality. We compare this with Simulated Annealing, exploring the algorithm configuration space using the irace software package to ensure fair comparison. The hybrid algorithm generates schedules that reduce unmet demand by over 28% compared to the baseline. All data used, where possible, is either directly from the real world engineer scheduling operation of around 25,000 employees, or synthesised from a related distribution where data is unavailable.

11:25-11:50 Comparative Analysis of Two Asynchronous Parallelization Variants for a Multi-Objective Coevolutionary Solver - presented at CEC 2019 (Parallel and Distributed Algorithms Track)

Ciprian Zavoianu, Robert Gordon University

We describe and compare two steady state asynchronous parallelization variants for DECMO2++, a recently proposed multi-objective coevolutionary solver that generally displays a robust run-time convergence behavior. The two asynchronous variants were designed as trade-offs that maintain only two of the three important synchronized interactions / constraints that underpin the (generation- based) DECMO2++ coevolutionary model. A thorough performance evaluation on a test set that aggregates 31 standard benchmark problems shows that while both parallelization options are able to generally preserve the competitive convergence behavior of the baseline coevolutionary solver, the better parallelization choice is to prioritize accurate run-time search adaptation decisions over the ability to perform equidistant fitness sharing.

11:50-12:15 A Hexagonal Cell Automaton Model to Imitate Physarum Polycephalum Competitive Behaviour; A Physarum-Inspired Competition Algorithm for Solving Discrete Multi-Objective Optimization Problems - to be presented at ALIFE 2019 & GECCO 2019

Abubakr Awad, University of Aberdeen

Slime mould (Physarum) may not have brains, but they are capable of solving many significant and challenging problems. Existing models for studying the intelligent behaviour of Physarum have overlooked its foraging behaviour under competitive settings. In this research, we propose a new model based on Cellular Automata (CA) and Reaction Diffusion (RD) system, where multiple Physarum interact with each other and with their environment. The novelty of our model is that the Physarum has six neighbours at equidistant (hexagonal CA), furthermore, we have extended the model to 3D and multi-dimensional CA grid. The growth of Physarum is determined by the balance between attraction force towards food resources (determined by mass and quality) and repulsion forces between competing Physarum according to their power (mass) and hunger motivation. To validate this model, numerical experiments were conducted. Physarum with more mass succeeded in engulfing a larger number of food resources with high quality in shorter time (number of iteration). It also occupied larger area of the grid (territory) and excluded its competitors. We also conducted empirical analysis to compare the time complexity between the hexagonal and Moore neighbourhood, and it showed that hexagonal neighbourhood is more efficient than Moore in terms of computational cost. To the best of our knowledge, we are the first to present Physarum in competition mathematical model and the algorithms inspired from such a model has demonstrated its promising performance in solving several real world problems such as mobile wireless sensor networks, and discrete multi objective optimization problems.

Many real-world problems can be naturally formulated as discrete multi-objective optimization (DMOO) problems. In this research we propose a novel bio-inspired Physarum competition algorithm (PCA) to tackle DMOO problems by modelling the Physarum discrete motility over a hexagonal cellular automaton. Our algorithm is based on the chemo-attraction forces towards food resources (Objective Functions) and the repulsion negative forces between the competing Physarum. Numerical experimental work clearly demonstrated that our PCA algorithm had the best performance for the spread indicator against three state-of-the-art evolutionary algorithms, and its effectiveness in terms of commonly used metrics. These results have indicated the superiority of PCA in exploring the search space and keeping diversity, this makes PCA a promising algorithm for solving DMOO problems.

Posters

Limitations of benchmark sets and landscape features for algorithm selection and performance prediction - to be presented at GECCO 2019

Benjamin Lacroix, Robert Gordon University

Benchmark sets and landscape features are used to test algorithms and to train models to perform algorithm selection or configuration. These approaches are based on the assumption that algorithms have similar performances on problems with similar feature sets. In this paper, we test different configurations of differential evolution (DE) against the BBOB set. We then use the landscape features of those problems and a case base reasoning approach for DE configuration selection. We show that, although this method obtains good results for BBOB problems, it fails to select the best configurations when facing a new set of optimisation problems with a distinct array of landscape features. This demonstrates the limitations of the BBOB set for algorithm selection. Moreover, by examination of the relationship between features and algorithm performance, we show that there is no correlation between the feature space and the performance space. We conclude by identifying some important open questions raised by this work.

Introducing the Dynamic Customer Location-Allocation Problem - presented at CEC 2019

Reginald Ankrah, Robert Gordon University

In this paper, we introduce a new stochastic Location-Allocation Problem which assumes the movement of customers over time. We call this new problem Dynamic Customer Location-Allocation Problem (DC-LAP). The problem is based on the idea that customers will change locations over a defined horizon and these changes have to be taken into account when establishing facilities to service customers demands. We generate 1440 problem instances by varying the problem parameters of movement rate which determines the possible number of times a customer will change locations over the defined period, the number of facilities and the number of customers.

We propose to analyse the characteristics of the instances generated by testing a search algorithm using the stochastic dynamic evaluation (based on the replication of customer movement scenarios) and a deterministic static evaluation (based on the assumption that customer will not move over time).

We show that the dynamic approach obtains globally better results, but the performances are highly related to the parameters of the problem.

Crowd-sourcing the Sounds of Places with a Web-Based Evolutionary Algorithm - to be presented at GECCO 2019

Sandy Brownlee, University of Stirling

The sounds we associate with particular places are tightly interwoven with our memories and sense of belonging. We describe a platform designed to assist in gathering the sounds a group of people associate with a place. A web-based evolutionary algorithm, with human-in-the-loop fitness evaluations, ranks and recombines sounds to find collections that the group rates as familiar. An experiment covering four geographical locations shows that the process does indeed find sounds deemed familiar by participants.

Session 2

13:15-13:40 Being a leader or being the leader: The evolution of institutionalised hierarchy - to be presented at ALIFE 2019

Cedric Perret, Edinburgh Napier University

Human social hierarchy has the unique characteristic of existing in two forms. Firstly, as an informal hierarchy where leaders and followers are implicitly defined by their personal characteristics, and secondly, as an institutional hierarchy where leaders and followers are explicitly appointed by group decision. Although both forms can reduce the time spent in organising collective tasks, institutional hierarchy imposes additional costs. It is therefore natural to question why it emerges at all. The key difference lies in the fact that institutions can create hierarchy with only a single leader, which is unlikely to occur in unregulated informal hierarchy. To investigate if this difference can affect group decision-making and explain the evolution of institutional hierarchy, we first build an opinion-formation model that simulates group decision making. We show that in comparison to informal hierarchy, a single-leader hierarchy reduces (i) the time a group spends to reach consensus, (ii) the variation in consensus time, and (iii) the rate of increase in consensus time as group size increases. We then use this model to simulate the cost of organising a collective action which produces resources, and integrate this into an evolutionary model where individuals can choose between informal or institutional hierarchy. Our results demonstrate that groups evolve preferences towards institutional hierarchy, despite the cost of creating an institution, as it provides a greater organisational advantage which is less affected by group size and inequality.

13:40-14:05 Algorithm Selection Using Deep Learning Without Feature Extraction - to be presented at GECCO 2019

Mohamad Alissa, Edinburgh Napier University

We propose a novel technique for algorithm-selection which adopts a deep-learning approach, specifically a Recurrent-Neural Network with Long-Short-Term-Memory (RNN-LSTM). In contrast to the majority of work in algorithm-selection, the approach does not need any features to be extracted from the data but instead relies on the temporal data sequence as input. A large case-study in the domain of 1-d bin packing is undertaken in which instances can be solved by one of four heuristics. We first evolve a large set of new problem instances that each have a clear "best solver" in terms of the heuristics considered. An RNN-LSTM is trained directly using the sequence data describing each instance to predict the best-performing heuristic. Experiments conducted on small and large problem instances with item sizes generated from two different probability distributions are shown to achieve between 7% to 11% improvement over the single best solver (SBS) (i.e. the single heuristic that achieves the best performance over the instance set) and 0% to 2% lower than the virtual best solver (VBS), i.e the perfect mapping.

14:05-14:30 On the Definition of Dynamic Permutation Problems under Landscape Rotation - to be presented at GECCO 2019 - Evolutionary Computation for Permutation Problems (Workshop)

Joan Alza, Robert Gordon University

Dynamic optimisation problems (DOPs) are optimisation problems that change over time. Typically, DOPs have been defined as a sequence of static problems, and the dynamism has been inserted into existing static problems using different techniques. In the case of dynamic permutation problems, this process has been usually done by the rotation of the landscape. This technique modifies the encoding of the problem and maintains its structure over time. Commonly, the changes are performed based on the previous state, recreating a concatenated changing problem. However, despite its simplicity, our intuition is that, in general, the landscape rotation may induce severe changes that lead to problems whose resemblance to the previous state is limited, if not null. Therefore, the problem should not be classified as a DOP, but as a sequence of unrelated problems. In order to test this, we consider the flow shop scheduling problem (FSSP) as a case study and the rotation technique that relabels the encoding of the problem according to a permutation. We compare the performance of two versions of the state-of-the-art algorithm for that problem on a wide experimental study: an adaptive version that benefits from the previous knowledge and a restarting version. Conducted experiments confirm our intuition and reveal that, surprisingly, it is preferable to restart the search when the problem changes even for some slight rotations. Consequently, the use of the rotation technique to recreate dynamic permutation problems is revealed in this work

14:30-14:55 Rigorous Performance Analysis of State-of-the-art TSP Heuristic Solvers - presented at EVOCOP 2019

Paul McMenemy, University of Stirling

Understanding why some problems are better solved by one algorithm rather than another is still an open problem, and the symmetric Travelling Salesperson Problem (TSP) is no exception. We apply three state-of-the-art heuristic solvers to a large set of TSP instances of varying structure and size, identifying which heuristics solve specific instances to optimality faster than others. The first two solvers considered are variants of the multi-trial Helsgaun's Lin-Kernighan Heuristic (a form of iterated local search), with each utilising a different form of Partition Crossover; the third solver is a genetic algorithm (GA) using Edge Assembly Crossover. Our results show that the GA with Edge Assembly Crossover is the best solver, shown to significantly outperform the other algorithms in 73% of the instances analysed. A comprehensive set of features for all instances is also extracted, and decision trees are used to identify main features which could best inform algorithm selection. The most prominent features identified a high proportion of instances where the GA with Edge Assembly Crossover performed significantly better when solving to optimality.

Session 3

15:15-15:40 Instruction-Level Design of Local Optimisers using Push GP - to be presented at GECCO 2019 (ECADA)

Michael Lones,Heriot-Watt University

This work uses genetic programming to explore the design space of local optimisation algorithms. Optimisers are expressed in the Push programming language, a stack-based language with a wide range of typed primitive instructions. The evolutionary framework provides the evolving optimisers with an outer loop and information about whether a solution has improved, but otherwise they are relatively unconstrained in how they explore optimisation landscapes. To test the utility of this approach, optimisers were evolved on four different types of continuous landscape, and the search behaviours of the evolved optimisers analysed. By making use of mathematical functions such as tangents and logarithms to explore different neighbourhoods, and also by learning features of the landscapes, it was observed that the evolved optimisers were often able to reach the optima using relatively short paths.

15:40-16:05 Comparing Encodings for Performance and Phenotypic Exploration in Evolving Modular Robots - to be presented at GECCO 2019

Frank Veenstra, Edinburgh Napier University

Advances in materials technology are accelerating our ability to evolve robots in hardware, but introduce new challenges for Evolutionary Robotics from a practical perspective. Given the time required to manufacture a robot and undertake fitness evaluations in the real world, there is a significant advantage in being able to efficiently traverse the search-space of morphologies/controllers to ensure a diverse range of fit-for-purpose robots can be produced. To address this, we compare three encodings that simultaneously evolve morphology and control of a modular robot: a direct encoding and two generative encodings---a compositional pattern producing network (CPPN) and a Lindenmayer System (L-System). We find that evolutionary progression and final performance is better in the direct encoding and the L-System than the CPPN. The generative encodings converge more quickly than the direct encoding in terms of morphological and controller diversity; in particular morphological diversity in the CPPN fixates very quickly during a run. We suggest that given that generative encodings are useful to quickly explore parts of the phenotypic space, an appropriate methodology for eventually evolving in hardware might be to first use the generative encoding for initial design, and then fine-tune these encodings using a direct representation.

16:05-16:30 Gin: Genetic Improvement Research Made Easy - to be presented at GECCO 2019

Sandy Brownlee, University of Stirling

Genetic improvement (GI) is a young field of research on the cusp of transforming software development. GI uses search to improve existing software. Researchers have already shown that GI can improve human-written code, ranging from program repair to optimising run-time, from reducing energy-consumption to the transplantation of new functionality. Much remains to be done. The cost of re-implementing GI to investigate new approaches is hindering progress. Therefore, we present Gin, an extensible and modifiable toolbox for GI experimentation, with a novel combination of features. Instantiated in Java and targeting the Java ecosystem, Gin automatically transforms, builds, and tests Java projects. Out of the box, Gin supports automated test-generation and source code profiling. We show, through examples and a case study, how Gin facilitates experimentation and will speed innovation in GI.