newsletter of the ACM Special Interest Group on Genetic and Evolutionary Computation
Welcome to the Autumn 2020 issue of the SIGEvolution newsletter! Our cover, by W.B (Bill) Langdon, shows consecutive populations in a generational genetic programming run. The image is part of Bill's contribution to this issue describing a memory efficient crossover operator for generational genetic programming . We continue with an overview by Erik Goodman of the 2020 Hummies awards where the human-competitive winners ranged from coordination of space satellites and mobile robots, to the analysis of genomic data. Our next article by Manuel López-Ibáñez covers the first SIGEVO best dissertation award, created in 2019 to recognize excellent thesis research by doctoral candidates in the field of evolutionary computing. We then celebrate the achievements of two members of our community, Edmund K. Burke and Mark Harman, who were elected this year as Fellows of the UK Royal Academy of Engineering. We follow with an overview of forthcoming evolutionary computation conferences this Autumn as well as the first 2021 calls for papers.
As ever, please get in touch if you would like to contribute an article for a future issue or have suggestions for the newsletter.
Gabriela Ochoa, Editor.
About the cover
A contribution from Bill Langdon, this image illustrates crossover in genetic programming. In generational schemes, the current population (on the left) is completely replaced by the next population (on the right). The area of red dots is proportional to the number of children it will be a parent of in the next generation. Small white dots are infertile. The first contributing article in this issue describes how to avoid simultaneously storing both populations, in order to achieve a memory efficient crossover.
A full version of the article can be found in the arXiv:
C++ code snippets from a multi-core parallel memory-efficient crossover for genetic programming are given here . They may be adapted for separate generation evolutionary algorithms where large chromosomes or small RAM require no more than M + 2 × nthreads simultaneously active individuals. This article summarises the full version at: arXiv 2009.10460.
Generational can be as Memory Efficient as Steady State
It has been known for a long time that in conventional genetic algorithms using two parent crossover only M + 2 individuals need to be simultaneously stored for non-overlapping generations of M individuals. Indeed this is true of generational Evolutionary Computation (EC) in general. (Steady state GAs, GPs and (μ + λ)-ES Evolution Strategies use overlapping generations, Figure 1.) Nonetheless the widespread availability of large RAM computers and compact coding of individual chromosomes seems to have led to the M+2 limit being forgotten and the widespread use of inefficient computer implementations with separate new and old populations, each requiring storage for M individuals. Recent work with enormous trees or large populations has prompted renewed interest in ensuring that generational implementations are as efficient as steady state implementations. (For example, see email discussion on GeneticProgramming@groups.io 5-7 September 2020.)
Minimal Memory Generational EC Algorithms
In their 1999 book (GP3) Koza et al. (pages 1044-1045) divide the current population into four classes, according to how many children they have: 0, 1, 2, more than 2. The new population is created in this priority order (0, 1, 2, 2+). Our algorithm is slightly simpler. Since Andy Singleton's GPquick uses crossover which creates one child (rather than two), this allows the “2” and “more than 2” classes to be combined into a class “two or more” (2+). We then follow GP3 except (to allow crossovers in parallel) we allocate up to two free slots per thread (rather than an extra two).
At the start of the new generation, the parent population are assigned into classes 0, 1 and 2+. All the parents without children (class 0) are deleted. The children to be created are assigned into class 1 or 2+, according to the minimum class of their (two) parents. I.e. if either parent is in class 1, the new child is placed in class 1, otherwise class 2+. With rapid parallel fitness evaluation, the cost of crossover can be significant, therefore both crossover and fitness evaluation are done by parallel threads. Note the operations in the next paragraph are also done in parallel.
Figure 1: In steady state Evolutionary Algorithms (e.g. μ + 1) parents are selected from the current population, their offspring created and inserted into the current population (red). To keep the population size constant, the same number of individuals (white) is removed from the population. Many strategies are available for selecting parents and for selecting whom to remove from the population.
Creation and testing of new individuals then starts with the class 1 individuals. Each time a new individual has been created, it is removed from the data structures for both its parents. If it has a class 1 parent, removing it will mean that that parent now no longer has any children to be processed and so is deleted. Removing it from a class 2+ parent, may mean the parent still has two or more children to be processed, so it stays in class 2+ or it may now only have one child to be created, in which case the child is moved to class 1. Class 1 children (i.e. with one or more class 1 parent) are created before those with two class 2+ parents.
Due to variations in thread timings, there can be small variations in memory usage between otherwise identical runs. To be efficient our implementation assumes: 1) run time is dominated by crossover and fitness evaluation (excluding gathering debug/performance statistics, they can be 99.9% of the cost of large GP experiments), 2) the number of cores is small compared to the population size (M) and 3) individual evaluation times are similar. Indeed in practice on long runs it is efficient even with very different tree evaluation times, e.g. obtaining a seven-fold speedup on an eight core CPU.
Acknowledgement: I would like to thank Thomas H. Westerdale, Ernesto Costa, Craig Shelden, David Oranchak, Kevin Sim, John Koza, Simon Waite and Gabriel Kronberger.
The 17th Annual Human-Competitive Results Awards were held as part of GECCO 2020, July 8-12, 2020. AKA the “Humies,” this competition annually awards $10,000 in cash prizes for computational results that are deemed to be competitive with results produced by human beings, but are generated automatically by computer. This year, like the rest of GECCO, the final presentations by the entrants in the competition could not be done as planned in Cancun, Mexico, but were instead made as videos shown during a virtual GECCO session. An advantage of this is that the presentations are all available on both the GECCO site and for the general public at the Humies website, www.human-competitive.org, so anyone can watch them.
The competition, sponsored by John Koza (who is widely acknowledged as the “Father of Genetic Programming”) solicits papers published within the last year that describe work fulfilling one or more of eight criteria, including such features as winning a regulated competition against humans or other programs, producing results that are publishable in their own right, not because they were created by a computer program, patentability, and other criteria described in full on the Humies website. This year’s judges for the competition were Wolfgang Banzhaf, Erik Goodman, Una-May O’Reilly, Lee Spector and Darrell Whitley. After reviewing their entry forms and the papers submitted, the judges invited 10-minute videos to be submitted by all eight finalists. As usual, after also viewing the videos, the judges wanted to give awards to many of the entries, but the final result was the following three awards:
The Gold and a $5,000 prize was awarded to a team including Lake Singh, William Whittecar, Marc DiPrinzio and Matthew Ferringer from The Aerospace Corporation, Jonathan Herman from UC Davis, and Patrick Reed from Cornell. Their paper, entitled “Low cost satellite constellations for nearly continuous global coverage,” was published in the prestigious journal Nature Communications in January, 2020. They used the Blue Waters petascale supercomputer at UIUC and the BORG multiobjective evolutionary algorithm to perform their search. Their goals included not only minimizing the number of satellites needed to provide nearly continuous global coverage, but also minimizing the amount of propellant in the satellites needed to maintain stable orbits for many years. Their 4-satellite constellations harness energy from nonlinear orbital perturbation forces (e.g., Earth’s geopotential, gravitational effects of the sun and moon, and solar radiation pressure) to reduce their propellant and maintenance costs. Including all of these factors strongly increases the computation time needed to evaluate each set of orbits, making the use of the petascale supercomputer necessary. Given that prior stable constellations of orbits required five satellites to maintain nearly continuous global coverage, and the large reduction in onboard propellant needed to maintain stable orbits, the savings in launch costs of these new constellations will be very large.
The Silver Award and $3,000 went to Marlen Meza-Sánchez, Eddie Clemente and María del Carmen Rodríguez-Liñán, of CONACYT-TecNM/I.T. Ensenada, (Baja California, Mexico) for their entry, presented in two papers, “Family of controllers based on sector non-linear functions: an application for first-order dynamical systems” and “Synthetic-analytic behavior-based control framework: Constraining velocity in tracking for nonholonomic wheeled mobile robots.” In the first paper, they introduced the use of sector non-linear functions for closed-loop control, instead of the traditional PID controller family, proving their asymptotic stability in the sense of Lyapunov. In the second paper, they use GP to derive families of controllers with proven Lyapunov stability for a more general class of controlled systems, demonstrating the effectiveness of controllers found by GP in controlling nonholonomic mobile robots.
The Bronze Award and $2,000 went to Ekaterina Noskova, Vladimir Ulyantsev, and Pavel Dobrynin of ITMO University (St. Petersburg), Klaus-Peter Koepfli of Smithsonian Conservation Biology Institute, and Stephen O’Brien of Nova Southeastern University (Ft. Lauderdale) for their paper, “GADMA: Genetic algorithm for inferring demographic history of multiple populations from allele frequency spectrum data,” published in GigaScience, 9(30), March, 2020. Traditionally, allele frequency spectrum data are analyzed for times of population increase, splits, and migration by using maximum likelihood methods to estimate parameters of a model hypothesized by the researcher. In this paper, a genetic algorithm is used to generate and parameterize the model, free of the biases of the researcher. They demonstrated that they generate models with higher maximum likelihoods than human-generated models, and they have already applied their method in analyzing human population splits, migrations, and periods of population growth that differ from the earlier models. If you’re a fan of “23 and Me,” you’d probably enjoy their video or paper!
See any of the finalists’ videos at www.human-competitive.org. And start preparing your own best human-competitive work for the 2021 Humies competition at GECCO in July! Any questions? Contact me, Erik Goodman, firstname.lastname@example.org.
ACM SIGEVO Best Dissertation Award 2020
by Manuel López-Ibáñez, University of Málaga, Spain
The SIGEVO Best Dissertation Award was created in 2019 to recognize excellent thesis research by doctoral candidates in the field of evolutionary computing. Doctoral dissertation awards are given by other Special Interest Groups of ACM, such as SIGCOMM, SIGKDD, SIGARCH and others. The SIGEVO Best Dissertation Award will be given annually to a maximum of 1 winner and a maximum of 2 honorable mentions. The award presentation will take place at the awards ceremony of GECCO. The award carries a monetary value of $1,000 contributed by SIGEVO to be awarded to the winner. The award winner and honorable mentions will each receive a plaque.
Dissertations are reviewed by a selection committee for technical depth and significance of the research contribution, potential impact on the field of evolutionary computing, and quality of presentation. This year, the members of the selection committee were:
Anne Auger, Inria, CMAP Ecole Polytechnique, IP Paris, France
Francisco Chicano, University of Málaga, Spain
Kenneth De Jong, George Mason University, USA
Jonathan Fieldsend, University of Exeter, UK
Manuel López-Ibáñez, University of Málaga, Spain
Gabriela Ochoa, University of Stirling, UK
The committee received and reviewed 7 nominations this year, in topics as diverse as neuroevolution, theory of evolutionary algorithms and estimation-of-distribution algorithms, multi- and many-objective optimization, and evolutionary robotics.
With the following citation from the selection committee:
“Taking inspiration from recent advances in neuroscience and biological models of neural networks, this dissertation covers the evolution of neural function, structure, and learning in Artificial Neural Networks (ANNs). The work presented here demonstrates the ability of Evolutionary Computation methods to improve ANNs. The ideas proposed here contribute new insights to the fields of Evolutionary Computation, Neuroevolution and Deep Learning.”
With the following citation from the selection committee:
"This dissertation provides fundamental insights for the theoretical analysis of estimation-of-distribution of algorithms (EDAs), which is an area of runtime analysis that has seen moderate progress so far. The analysis proves desirable properties of some EDAs that should inform future theoretical and empirical work. These results suggest key insights in the different behavior of EDAs and Evolution Strategies.”
With the following citation from the selection committee:
“This dissertation studies the application of multi-objective mixed-integer evolutionary algorithms to the domain of the spatial design optimization of buildings. Informed by real-world requirements, the work covers all stages of algorithm development from solution representation, algorithm design and analysis, and the extraction of knowledge from the results of optimization.”
New Fellows of the UK Royal Academy of Engineering
The Academy's Fellowship represents the UK best engineering researchers, innovators, entrepreneurs, business and industry leaders. Election to the Academy is by invitation only; about 50 Fellows are elected each year by peer review from nominations made by existing Fellows. They are distinguished by the title Fellow of the Royal Academy of Engineering and the postnominal FREng.
The new 2020 fellows include two academics and leaders with substantial contributions to genetic and evolutionary computation.
Professor Edmund Burke FREng
Deputy Vice-Chancellor, University of Leicester
For his contributions and high impact research into decision support methodologies for real-world complex environments, bridging the gap between scientific research and industrial practice. His work lies at the interface of Operational Research and Computer science and ranges hyper-heuristics, evolutionary algorithms, metaheuristics and exact methods applied to timetabling, scheduling and packing problems, among others.
Professor Mark Harman FREng
Research Scientist, Facebook
Mark is recognised as the founder of Search Based Software Engineering, with substantial research and leadership contributions this field over decades. His research is applied by many companies and his recent move to Facebook lead to the deployment of Sapienz, an automatic software test design system that directly impacts over two billion people world-wide. Facebook Engineering offers a wider coverage of Marks' achievements.
Forthcoming Evolutionary Computation Conferences
The organizing committee has decided to hold ANTS 2020 as an online conference. Dates: October 26-28, 2020. ANTS 2020 gives researchers in swarm intelligence the opportunity to meet, to present their latest research, and to discuss current developments and applications. Swarm intelligence is the discipline that deals with the study of self-organizing processes both in nature and in artificial systems. Recently, algorithms and methods inspired by these models have been proposed to solve difficult problems in many domains.
The BIOMA 2020 format will be entirely virtual. Dates: November 17- 20 2020. BIOMA is a key conference specifically focusing on bioinspired optimization methods and their applications. This international conference provides an opportunity to the global research community in bioinspired optimization to discuss recent research results and develop new ideas and collaborations in a friendly and relaxed atmosphere.
Call for papers
The Genetic and Evolutionary Computation Conference, GECCO 2021, will take place in Lille, July 10-14, 2021. GECCO presents the latest high-quality results in genetic and evolutionary computation since 1999. Topics include: genetic algorithms, genetic programming, ant colony optimization and swarm intelligence, complex systems (artificial life, robotics, evolvable hardware, generative and developmental systems, artificial immune systems), digital entertainment technologies and arts, evolutionary combinatorial optimization and metaheuristics, evolutionary machine learning, evolutionary multiobjective optimization, evolutionary numerical optimization, real world applications, search-based software engineering, theory and more.
Workshop proposals: November 5, 2020
Tutorial proposals: November 5, 2020
Notification of workshop and tutorial acceptance: December 3, 2020
Abstract submission: January 28, 2021
Full paper submission: February 4, 2021
Poster-only submission: February 4, 2021
Notification of paper acceptance: March 26, 2021
GECCO 2021 Conference: July 10-14, 2021
In April 2021 EvoStar is comprised of four co-located conferences run each spring at different locations throughout Europe. These events arose out of workshops originally developed by EvoNet, the Network of Excellence in Evolutionary Computing, established by the Information Societies Technology Programme of the European Commission, and they represent a continuity of research collaboration stretching back over 20 years.
EvoStar is organised by SPECIES, the Society for the Promotion of Evolutionary Computation in Europe and its Surroundings. This non-profit academic society is committed to promoting evolutionary algorithmic thinking, with the inspiration of parallel algorithms derived from natural processes. It provides a forum for information and exchange.
The four conferences include
EuroGP 24th European Conference on Genetic Programming
EvoApplications 24th European Conference on the Applications of Evolutionary and bio-inspired Computation
EvoCOP 21st European Conference on Evolutionary Computation in Combinatorial Optimisation
EvoMUSART 10th International Conference (and 15th European event) on Evolutionary and Biologically Inspired Music, Sound, Art and Design
Submission deadline: November 1, 2020.
Conference: 7 to 9 April 2021.
In September 2021 the 16th edition of FOGA will take place at the Vorarlberg University of Applied Sciences in Dornbirn, Austria.
The conference series aims at advancing the understanding of the working principles behind Evolutionary Algorithms and related Randomized Search heuristics. FOGA is a premier event to discuss advances in the theoretical foundations of these algorithms, corresponding frameworks suitable to analyze them, and different aspects of comparing algorithm performance.
Topics of interest include, but are not limited to: Run time analysis; Mathematical tools suitable for the analysis of search heuristics, Fitness landscapes and problem difficulty; Configuration and selection of algorithms, heuristics, operators, and parameters; Stochastic and dynamic environments, noisy evaluations; Constrained optimization; Problem representation; Complexity theory for search heuristics; Multi-objective optimization; Benchmarking; Connections between black-box optimization and machine learning.
FOGA 2021 invites submissions covering the entire spectrum of work, ranging from rigorously derived mathematical results to carefully designed empirical studies.
Submission deadline: April 30, 2021
Author rebuttal phase: June 1 - 7, 2021
Notification of acceptance: June 20, 2021
Camera-ready submission: July 14, 2021
Early-registration deadline: July 14, 2021
Conference dates: September 6 to September 8, 2021
About this Newsletter
SIGEVOlution is the newsletter of SIGEVO, the ACM Special Interest Group on Genetic and Evolutionary Computation. To join SIGEVO, please follow this link: [WWW]
We solicit contributions in the following categories:
Art: Are you working with Evolutionary Art? We are always looking for nice evolutionary art for the cover page of the newsletter.
Short surveys and position papers: We invite short surveys and position papers in EC and EC related areas. We are also interested in applications of EC technologies that have solved interesting and important problems.
Software: Are you are a developer of an EC software and you wish to tell us about it? Then, send us a short summary or a short tutorial of your software.
Lost Gems: Did you read an interesting EC paper that, in your opinion, did not receive enough attention or should be rediscovered? Then send us a page about it.
Dissertations: We invite short summaries, around a page, of theses in EC-related areas that have been recently discussed and are available online.
Meetings Reports: Did you participate in an interesting EC-related event? Would you be willing to tell us about it? Then, send us a summary of the event.
Forthcoming Events: If you have an EC event you wish to announce, this is the place.
News and Announcements: Is there anything you wish to announce, such as an employment vacancy? This is the place.
Letters: If you want to ask or to say something to SIGEVO members, please write us a letter!
Suggestions: If you have a suggestion about how to improve the newsletter, please send us an email.
Contributions will be reviewed by members of the newsletter board. We accept contributions in plain text, MS Word, or Latex, but do not forget to send your sources and images.
Enquiries about submissions and contributions can be emailed to email@example.com
All the issues of SIGEVOlution are also available online at: www.sigevolution.org
Notice to contributing authors to SIG newsletters
By submitting your article for distribution in the Special Interest Group publication, you hereby grant to ACM the following non-exclusive, perpetual, worldwide rights:
to publish in print on condition of acceptance by the editor
to digitize and post your article in the electronic version of this publication
to include the article in the ACM Digital Library
to allow users to copy and distribute the article for noncommercial, educational or research purposes
However, as a contributing author, you retain copyright to your article and ACM will make every effort to refer requests for commercial use directly to you.
Editor: Gabriela Ochoa
Associate Editors: Emma Hart, James McDermott, Una-May O'Reilly and Darrell Whitley
Design & Layout: Gabriela Ochoa