Programme

Schedule

09:30 – 10:00 Registration / Coffee

10:00 – 10:15 Welcome / Introduction

10:15 – 12:00 Session 1

12:00 – 13:00 Lunch / Poster Session

13:00 – 14:45 Session 2

14:45 – 15:15 Coffee

15:15 – 17:00 Session 3

17:00 – 18:00 Networking / Refreshments

Session 1 (10:00 – 12:00)

10:15 – 10:40 Engineering Sustainable and Adaptive Systems in Dynamic and Unpredictable Environments - to be presented at ISOLA 2018

Jeremy Pitt, Imperial College London/Edinburgh Napier University

In an open multi-agent system embedded in a dynamic and unpredictable environment, the general problem is for the agents to select, modify and apply a set of conventional, mutually agreed rules in order to achieve some 'mission'. However, everything is mutable: the environment can change (and changes can be fast/slow and radical/incremental), the agents can change (in numbers and capabilities), the mission can change, and the rules themselves can change (or rather, be changed). The challenge then, is to how to engineer systems that can operate -- sustainably -- under such conditions. In this talk, we outline an approach to this problem based on the integration of two hitherto separate approaches to self-organisation: electronic institutions and evolutionary computation.

10:40 – 11:05 Can justice be fair when it is blind? How social network structures can promote or prevent the evolution of despotism - to be presented at ALIFE 2018

Simon Powers, Edinburgh Napier University

Hierarchy is an efficient way for a group to organize, but often goes along with inequality that benefits leaders. To control despotic behaviour, followers can assess leaders' decisions by aggregating their own and their neighbours' experience, and in response challenge despotic leaders. But in hierarchical social networks, this interactional justice can be limited by (i) the high influence of a small clique who are treated better, and (ii) the low connectedness of followers. Here we study how the connectedness of a social network affects the co-evolution of despotism in leaders and tolerance to despotism in followers. We simulate the evolution of a population of agents, where the influence of an agent is its number of social links. Whether a leader remains in power is controlled by the overall satisfaction of group members, as determined by their joint assessment of the leader’s behaviour. We demonstrate that centralization of a social network around a highly influential clique greatly increases the level of despotism. This is because the clique is more satisfied, and their higher influence spreads their positive opinion of the leader throughout the network. Finally, our results suggest that increasing the connectedness of followers limits despotism while maintaining hierarchy.

11:05 – 11:30 Towards In Vivo Genetic Programming: Evolving Boolean Networks to Determine Cell States - presented at EuroGP 2018

Michael Lones, Heriot-Watt University

Within the genetic programming community, there has been growing interest in the use of computational representations motivated by gene regulatory networks (GRNs). It is thought that these representations capture useful biological properties, such as evolvability and robustness, and thereby support the evolution of complex computational behaviours. However, computational evolution of GRNs also opens up opportunities to go in the opposite direction: designing programs that could one day be implemented in biological cells. In this paper, we explore the ability of evolutionary algorithms to design Boolean networks, abstract models of GRNs suitable for refining into synthetic biology implementations, and show how they can be used to control cell states within a range of executable models of biological systems.

11:30 – 11:55 Past Visions of Artificial Futures: One Hundred and Fifty Years under the Spectre of Evolving Machines - to be presented at ALIFE 2018

Tim Taylor, Independent / Associate of University of York and University of London

The influence of Artificial Intelligence (AI) and Artificial Life (ALife) technologies upon society, and their potential to fundamentally shape the future evolution of humankind, are topics very much at the forefront of current scientific, governmental and public debate. While these might seem like very modern concerns, they have a long history that is often disregarded in contemporary discourse. Insofar as current debates do acknowledge the history of these ideas, they rarely look back further than the origin of the modern digital computer age in the 1940s–50s. In this paper we explore the earlier history of these ideas. We focus in particular on the idea of self-reproducing and evolving machines, and the potential implications for our own species. We show that discussion of these topics arose in the 1860s, within a decade of the publication of Darwin’s The Origin of Species, and attracted increasing interest from scientists, novelists and the general public in the early 1900s. After introducing the relevant work from this period, we categorise the various visions presented by these authors of the future implications of evolving machines for humanity. We suggest that current debates of the co-evolution of society and technology can be enriched by a proper appreciation of the long history of the ideas involved.

Lunch / Poster Session 12:00 – 13:00

A Novel Similarity-based Mutant Vector Generation Strategy for Differential Evolution - to be presented at GECCO 2018

Emma Hart, Edinburgh Napier University

The mutant vector generation strategy is an essential component of Differential Evolution (DE), introduced to promote diversity, resulting in exploration of novel areas of the search space. However, it is also responsible for promoting intensification, to improve those solutions located in promising regions. In this paper we introduce a novel similarity-based mutant vector generation strategy for DE with the goal of inducing a suitable balance between exploration and exploitation, adapting its behaviour depending on the current state of the search. In order to achieve this balance, the strategy considers similarities among individuals in terms of their Euclidean distance in the decision space. A variant of DE incorporating the novel mutant vector generation strategy is compared to well-known explorative and exploitative adaptive DE variants. An experimental evaluation performed on a well-known suite of large-scale continuous problems shows that the new DE algorithm that makes use of the similarity-based approach provides better performance in comparison to the explorative and exploitative DE variants for a wide range of the problems tested, demonstrating the ability of the new component to properly balance exploration and exploitation.

Performance Analysis of GA and PBIL Variants for Real-World Location-Allocation Problems - to be presented at CEC 2018

Reginald Ankrah, Robert Gordon University

The Uncapacitated Location-Allocation problem (ULAP) is a major optimisation problem concerning the determination of the optimal location of facilities and the allocation of demand to them. In this paper, we present two novel problem variants of Non-Linear ULAP motivated by a real-world problem from the telecommunication industry: Uncapacitated Location-Allocation Resilience problem (ULARP) and Uncapacitated Location-Allocation Resilience problem with Restrictions (ULARPR). Problem sizes ranging from 16 to 100 facilities by 50 to 10000 demand points are considered. To solve the problems, we explore the components and configurations of four Genetic Algorithms selected from the ULAP literature. We aim to understand the contribution each choice makes to the GA performance and so hope to design an Optimal GA configuration for the novel problems. We also conduct comparative experiments with Population-Based Incremental Learning (PBIL) Algorithm on ULAP.

We show the effectiveness of PBIL and GA with parameter set: random and heuristic initialisation, tournament and fined\_grained tournament selection, uniform crossover and bitflip mutation in solving the proposed problems.

Mutual Information Iterated Local Search: A Wrapper-Filter Hybrid for Feature Selection in Brain Computer Interfaces - presented at EvoStar 2018

Jason Adair, University of Stirling

Brain Computer Interfaces provide a very challenging classification task due to small numbers of instances, large numbers of features, non-stationary problems, and low signal-to-noise ratios. Feature Selection (FS) is a promising solution to help mitigate these effects. Wrapper FS methods are typically found to outperform filter FS methods, but reliance on cross-validation accuracies can be misleading due to over-fitting. We propose a filter-wrapper hybrid based on Iterated Local Search and Mutual Information, and show that it can provide more reliable solutions, where the solutions are better able to generalise to unseen data.

Routes to Open-Endedness in Evolutionary Systems - to be presented at ALIFE 2018

Tim Taylor, Independent / Associate of University of York and University of London

In this paper I identify different routes by which open-endedness (OE) can be introduced into the design and implementation of an evolutionary system. I begin by presenting a definition of three different kinds of open-endedness. My treatment of the topic utilises the approach recently proposed by Banzhaf et al. (2016), although the ideas presented in the rest of the paper are not rigidly tied to this approach. Banzhaf and colleagues make the distinction between scientific models, which are “descriptive models of part of the existing world”, and engineering models (including software design models), which are “prescriptive or normative models of a system to be built in the world” (Banzhaf et al., 2016, p. 135). One of the main aims of their paper was to develop a descriptive scientific (meta-)model to illustrate their definitions of open-endedness. They express the hope that “such a definition of OE in terms of models and meta-models will help the design of normative engineering models for implementing ALife” (Banzhaf et al., 2016, p. 136).

The aim of the current contribution is to make progress towards exactly that goal—the development of an engineering model to guide the design and implementation of artificial evolutionary systems that possess the capacity for various kinds of open-endedness. Having clarified what I mean by open-endedness, I then introduce a formalism for describing the key processes that must be present in any evolutionary system. The formalism makes explicit some important dependencies and interrelationships that are otherwise easy to overlook. Equipped with the necessary preliminaries, I then utilise the formalism to identify the various routes by which the three kinds of open-endedness can be accommodated in the design of an evolutionary system.

Optimisation and Illumination of a Real-world Workforce Scheduling and Routing Application via Map-Elites - to be presented at PPSN 2018

Neil Urquhart, Edinburgh Napier University

Workforce Scheduling and Routing Problems (WSRP) are very common in many practical domains, and usually have a number of objectives. Illumination algorithms such as Map-Elites (ME) have recently gained traction in application to design problems, in providing multiple diverse solutions as well as illuminating the solution space in terms of user-defined characteristics, but typically require significant computational effort to produce the solution archive. We investigate whether ME can provide an effective approach to solving WSRP, a repetitive problem in which solutions have to be produced quickly and often. The goals of the paper are two-fold. The first is to evaluate whether ME can provide solutions of competitive quality to an Evolutionary Algorithm (EA) in terms of a single objective function, and the second to examine its ability to provide a repertoire of solutions that maximise user choice. We find that very small computational budgets favour the EA in terms of quality, but ME outperforms the EA at larger budgets, provides a more diverse array of solutions, and lends insight to the end-user.

Evolution of a Functionally Diverse Swarm via a Novel Decentralised Quality-Diversity Algorithm - to be presented at GECCO 2018

Andreas Steyven, Edinburgh Napier University

The presence of functional diversity within a group has been demonstrated to lead to greater robustness, higher performance and increased problem-solving ability in a broad range of studies that includes insect groups, human groups and swarm robotics. Evolving group diversity however has proved challenging within Evolutionary Robotics, requiring reproductive isolation and careful attention to population size and selection mechanisms. To tackle this issue, we introduce a novel, decentralised, variant of the MAP-Elites illumination algorithm which is hybridised with a well-known distributed evolutionary algorithm (mEDEA). The algorithm simultaneously evolves multiple diverse behaviours for multiple robots, with respect to a simple token-gathering task. Each robot in the swarm maintains a local archive defined by two pre-specified functional traits which is shared with robots it come into contact with. We investigate four different strategies for sharing, exploiting and combining local archives and compare results to mEDEA. Experimental results show that in contrast to previous claims, it is possible to evolve a functionally diverse swarm without geographical isolation, and that the new method outperforms mEDEA in terms of the diversity, coverage and precision of the evolved swarm.

On the Synthesis of Perturbative Heuristics for Multiple Combinatorial Optimisation Domains - to be presented at PPSN 2018

Christopher Stone, Edinburgh Napier University

Hyper-heuristic frameworks, although intended to be cross-domain at the highest level, rely on a set of domain-specific low-level heuristics at lower levels. For some domains, there is a lack of available heuristics, while for novel problems, no heuristics might exist. We address this issue by introducing a novel method, applicable in multiple domains, that constructs new low-level heuristics for a domain. The method uses grammatical evolution to construct iterated local search heuristics: it can be considered cross-domain in that the same grammar can evolve heuristics in multiple domains without requiring any modification, assuming that solutions are represented in the same form. We evaluate the method using benchmarks from the travelling-salesman (TSP) and multi-dimensional knapsack (MKP) domain. Comparison to existing methods demonstrates that the approach generates low-level heuristics that outperform heuristic methods for TSP and are competitive for MKP.

Session 2 (13:00 – 14:45)

13:00 – 13:25 Iterated racing algorithm for simulation-optimisation of maintenance planning - to be presented at WCCI 2018

Benjamin Lacroix, Robert Gordon University

The purpose of this paper is two fold. First, we present a set of benchmark problems for maintenance optimisation called VMELight. This model allows the user to define the number of components in the system to maintain and a number of customisable parameters such as the failure distribution of the components, the spare part stock level and every costs associated with the preventive and corrective maintenances, unavailability and spare parts. From this model, we create a benchmark of 175 optimisation problems across different dimensions. This benchmark allows us to test the idea of using an iterated racing algorithm called IRACE based on the Friedman statistical test, to reduce the number of simulations needed to compare solutions in the population. We assess different population size and truncation rate to show that those parameters can have a strong influence on the performance of the algorithm.

13:25 – 13:50 An Analysis of Indirect Optimisation Strategies for Scheduling - to be presented at WCCI 2018

John McCall, Robert Gordon University

By incorporating domain knowledge, simple greedy procedures can be defined to generate reasonably good solutions to many optimisation problems. However, such solutions are unlikely to be optimal and their quality often depends on the way the decision variables are input to the greedy method. Indirect optimisation uses meta-heuristics to optimise the input of the greedy decoders. As the performance and the runtime differ across greedy methods and meta-heuristics, deciding how to split the computational effort between the two sides of the optimisation is not trivial and can significantly impact the search.

In this paper, an artificial scheduling problem is presented along with five greedy procedures, using varying levels of domain information. A methodology to compare different indirect optimisation strategies is presented using a simple Hill Climber, a Genetic Algorithm and a population-based Local Search. By assessing all combinations of meta-heuristics and greedy procedures on a range of problem instances with different properties, experiments show that encapsulating problem knowledge within greedy decoders may not always prove successful and that simpler methods can lead to comparable results as advanced ones when combined with meta-heuristics that are adapted to the problem. However, the use of efficient greedy procedures reduces the relative difference between meta-heuristics.

13:50 – 14:15 Balancing the Diversification-Intensification Trade-off Using Mixtures of Probability Models - to be presented at CEC 2018

Joan Alza, Robert Gordon University

The trade-off between diversification and intensification has been investigated recurrently in the field of evolutionary computation. Proof of this is the numerous approaches that have been devoted to finding a balance in the diversification intensification behavior of algorithms. Despite the large amount of work on this topic, dynamically adjusting such behavior is still difficult and depends on the algorithm at hand. In this paper, we focus on estimation of distribution algorithms (EDAs). Usually, research on EDAs mainly focuses on the design of probability models that either represent as best as possible the characteristics of the problem, or accurately fit the domain of the solutions. In this work, we propose implementing mixtures of probability models that permit the dynamic adjustment of the scope of the EDA. Particularly, we design a mixture model that combines two unimodal Thurstone family probability models: the Plackett-Luce model and the Bradley-Terry model. The first model tends to concentrate the probability around the mode, while the second spreads the probability more. Using a homogeneity measure on the population of solutions, we dynamically decide the ratio of solutions to sample from each model. Performed experiments on the linear ordering problem demonstrate that this research line is definitively promising.

14:15 – 14:40 Evolutionary Computing by An Ensemble framework - to be published in IEEE Transactions

Wenjun Wang, University of Aberdeen

This paper suggests an effective ensemble framework for tackling multi-objective optimization problems, by combining the ad-vantages of various evolutionary operators and selection criteria that are run on multiple populations. A simple ensemble algorithm is realized to show the actual running of our proposed framework. Two main mechanisms (competition and cooperation) are used to drive the running of ensembles. Competition is de-signed by adaptively running different evolutionary operators on multiple populations. The operator that better fits the problem’s characteristics will receive more computational resources, as re-warded by a decomposition-based credit assignment strategy. Cooperation is achieved by selecting the offspring from different populations using exclusive criteria. By this way, the promising offspring from any population can be migrated into other populations, aiming to enhance convergence or diversity. Moreover, the population update information is further exploited to build an evolutionary potentiality model, so as to guide the evolution. The experimental results show the superior performance of our pro-posed ensemble algorithms in solving most cases of a set of thirty-one test problems, which corroborates the advantages of the proposed ensemble framework.

Session 3 (15:15 – 17:00)

15:15 – 15:40 Evolution of a Functionally Diverse Swarm via a Novel Decentralised Quality-Diversity Algorithm - to be presented at GECCO 2018

Andreas Steyven, Edinburgh Napier University

15:40 – 16:05 Multifractality and Dimensional Determinism in Local Optima Networks - to be presented at GECCO 2018

Sarah Thomson, University of Stirling

We conduct a study of local optima networks (LONs) in a search space using fractal dimensions. The fractal dimension (FD) of these networks is a complexity index which assigns a non-integer dimension to an object. We propose a fine-grained approach to obtaining the FD of LONs, using the probabilistic search transitions encoded in LON edge weights. We then apply multi-fractal calculations to LONs for the first time, comparing with mono-fractal analysis. For complex systems such as LONs, the dimensionality may be different between two sub-systems and multi-fractal analysis is needed. Here we focus on the Quadratic Assignment Problem (QAP), conducting fractal analyses on sampled LONs of reasonable size for the first time. We also include fully enumerated LONs of smaller size. Our results show that local optima spaces can be multi-fractal and that valuable information regarding probabilistic self-similarity is encoded in the edge weights of local optima networks. Links are drawn between these phenomena and the performance of two competitive metaheuristic algorithms.

16:05 – 16:30 A Rolling Window with Genetic Algorithm Approach to Sorting Aircraft for Automated Taxi Routing - to be presented at GECCO 2018

Sandy Brownlee, University of Stirling

With increasing demand for air travel and overloaded airport facilities, inefficient airport taxiing operations are a significant contributor to unnecessary fuel burn and a substantial source of pollution. Although taxiing is only a small part of a flight, aircraft engines are not optimised for taxiing speed and so contribute disproportionately to the overall fuel burn. Delays in taxiing also waste scarce airport resources and frustrate passengers. Consequently, reducing the time spent taxiing is an important investment. An exact algorithm for finding shortest paths based on A* allocates routes to aircraft that maintains aircraft at a safe distance apart, has been shown to yield efficient taxi routes. However, this approach depends on the order in which aircraft are chosen for allocating routes. Finding the right order in which to allocate routes to the aircraft is a combinatorial optimization problem in itself. We apply a rolling window approach incorporating a genetic algorithm for permutations to this problem, for real-world scenarios at three busy airports. This is compared to an exhaustive approach over small rolling windows, and the conventional first-come-first-served ordering. We show that the GA is able to reduce overall taxi time with respect to the other approaches.

16:30 – 16:55 On the Synthesis of Perturbative Heuristics for Multiple Combinatorial Optimisation Domains - to be presented at PPSN 2018

Christopher Stone, Edinburgh Napier University