newsletter of the ACM Special Interest Group on Genetic and Evolutionary Computation
Welcome to the Summer 2021 issue of the SIGEvolution newsletter! We start with overviews of two recently published research articles. The first, related to our cover image, describes a system for generating images from music as an inspiration for the creative process, where a genetic algorithm is part of the system. The second contribution describes a graph-based tool for analyzing and visualizing the behavior of any type of single objective metaheuristic, including evolutionary algorithms. We continue with a summary of EvoSTAR 2021, the leading European event in evolutionary and nature-inspired algorithms. We then highlight recent awards and news relevent to our community. The issue concludes by announcing a number of exciting events and calls for submissions.
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.
A Computational Creativity Approach From Music to Images
Our system generates abstract images from music that serve as inspiration for the creative process. We developed one of many possible approaches for a cross-domain association between the musical and visual domains, by extracting features from MIDI music files and associating them to visual characteristics. The associations were lead by the authors' aesthetic preferences and some experimentation. Three different approaches were pursued, two with direct or random associations and a third using a genetic algorithm that considers music and color theory while searching for better results. The resulting images were evaluated through online surveys, which confirmed that not only they were abstract, but also that there was a relationship with the music that served as the basis for the association process. Moreover, the majority of the participants ranked highest the images improved with the genetic algorithm. This newsletter contribution summarises the full version of the article, which was presented at EvoMUSART 2021 (10th International Conference on Artificial Intelligence in Musc, Sound, Art and Design).
Our main contribution is the development of a system that exhibits creative behavior by generating abstract images inspired by musical artifacts. We define abstract images as visual artifacts that do not reflect or convey anything "concrete" or "real". Throughout the development of our system, we went through several phases, from research on music theory to the study of color harmonies, shape assembling, and image generation techniques. In order to improve the aesthetic value of the generated images, and to search for better results, we also investigated genetic algorithms, implementing one from scratch.
Our final system outputs three different images in response to each musical input. The first, called the Random image, was generated assigning a random shape and texture to each instrument found on the music file. The second, called the Associated image, was generated assigning a predefined association between musical instruments and respective shapes. The third version, called the Genetic image, results from the genetic algorithm, which receives the two previous versions to seed the initial population.
Four pairs of music and respective images were evaluated through online surveys. The evaluation had good results since the majority of the participants consider the images to be abstract. Moreover, regardless of the version, the participants believe that there is a relationship between the images and the music.
Our approach lies in the association of the music melody with the image foreground, and the music harmony with the image background. In turn, the music rhythm is associated with the size of the image elements, as well as with the overall luminosity of the image background.
Having defined our system's high-level associations, we then needed to obtain the image elements from the music structure. We started with the foreground. Many different associations could be established, even random ones. We decided to overlap the chromatic scale and the color wheel - where each pitch from the chromatic scale is associated with one, and only one hue from the color wheel, as depicted in Figure 1. The note's octave, which represents how high or low a note is, gives us how light or dark a color is. Finally, the saturation of the color is determined by the volume of the note.
Figure 1. Overlapping the chromatic circle and the RGB color wheel.
Figure 2. Overlapping the circle of fifths and the RGB color wheel.
Table 1. One possible shape association for each instrument family.
We needed an association to define the shape of each visual element. One possible association between instrument families and geometrical shapes is represented in Table 1. This association is based only on our perception, a mapping between instruments and shapes with a perfect rationale is hard to achieve. We consider two approaches for the output images. First, a random shape and texture are applied to each instrument found in the music sheet. Second, the associations presented in Table 1 are assigned.
Time signatures, plus information about tempo, are associated with the note duration to define the size of elements. The position of each element in the foreground is related to the music offset (the elements' relative location in the music).
An analysis of the music measures (single units of time featuring a specific number of beats played at a particular tempo) was conducted to obtain their most likely tonality key to associate with characteristics of the background. Having a set of tonality keys belonging to the music harmony, we decided to overlap the circle of fifths and the color wheel, as depicted in Figure 2. Since each measure harmony is composed of chords, we decided to get both the volume and each tonic note, to retrieve its octave. The volume is associated with the color saturation, while the octave defines the color lightness, thus establishing a possible analogy between chords and colors.
Our approach for the image background considers each measure as a vertical stripe that is placed sequentially from left to right following the sequential way of writing a musical sheet in western countries. Therefore, having the measure's respective color, the background consists of equally sized vertical stripes, whose position is mapped from the measure's offset.
Having the image foreground and background from the music melody, harmony, and the respective rhythm as described above, we obtained the first two image versions: Random and Associated images.
To generate our third image version, we implemented a standard genetic algorithm where individuals are images characterized by their elements' position, color, and sizes as well as the musical notes that gave rise to them. The initial population is seeded with both the Random and Associated images, and versions of them with shuffled element positions. The fitness function is based on color harmonies between nearest elements, as well as visual perceptions of color, the location of elements in the canvas, and their shape distributions. More details can be found in the original article.
Results and Evaluation
Our evaluation considered excerpts from four classical music pieces of different periods (from Baroque to Modernism). The complete dataset and results can be found at https://luisaleixo.github.io.
Our results indicate that users prefer the Genetic images. We also found that participants prefer the Associated images over the Random images. Figure 3 display the Genetic images used in the evaluation process.
Handel - Concerto No. 1.
Handel - The Royal Fireworks Suite.
Mozart - Symphony No. 40.
Stravinsky - The Firebird.
Figure 3. Genetic images used in the evaluation process.
Inspired by the algorithmic way of processing music and image, the main objective of this work was to develop a system that exhibits creative behavior through inter-domain associations, by generating abstract images inspired by music. Our approach was based on relationships between the music harmony, melody, and rhythm; and visual elements that refer to both the image background and foreground.
Three types of images were generated from each input music file: Random, Associated, and Genetic. The Random image was generated by assigning a random shape and texture to each instrument found in the musical composition. The Associated image was generated by assigning a predefined association between instruments and respective shapes. The Genetic image was the result of running a genetic algorithm with an initial population seeded by the other two types of images.
Our evaluation indicates that the majority of the participants considered the generated images to be abstract, and believe that they have a connection with the music that served as the basis for the inspiration process. Moreover, the majority liked the presented images, indicating a preference for the Genetic images. We consider that these results are favorable since they go in line with our goals.
Acknowledgments. This work was supported by FCT project UIDB/50021/2020.
This article summarizes our recent journal paper entitled "Search trajectory networks: A tool for analysing and visualising the behaviour of metaheuristics", where we propose a graph-based, data-driven modeling tool (STNs) to visualize and analyze the dynamics of any type of metaheuristic (evolutionary, swarm-based or single-point).
Our tool allows the direct visual comparison of the trajectories of two or three algorithms when solving instances of continuous or discrete optimization problems. We shared our datasets and scripts for constructing, analyzing, and visualizing the network models in a GitHub repository: STNs.
Complex networks are a versatile tool for analyzing the structure and dynamics of complex systems in nature, society, and technology. We argue that understanding the behavior of metaheuristics is a complex open problem and that STNs can help to fill this gap.
Search Trajectory Networks (STNs)
In order to define a network model, we need to specify the nodes and edges. The relevant definitions are given below.
Representative solution: A solution to the optimization problem at a given time step that represents the status of the search algorithm (e.g. best in the population in a given iteration, incumbent solution for single point metaheuristics)
Location: A non-empty subset of solutions that results from a predefined partitioning of the search space.
Nodes (N): Locations of the corresponding representative solutions in a search process.
Trajectory: A sequence of locations representing the best solution in the population over time.
Edges (E): Directed, connecting two consecutive locations in the search trajectory.
STN: Directed graph STN = (N, E), with nodes N and edges E as defined above.
One strength of STNs is that there is no need for additional sampling or data gathering methods. Instead, the data to construct the models are collected from a number of runs of the metaheuristics under study. Once the STN models for a set of algorithm-instance pairs are constructed, we can proceed to merge the STNs of different algorithms for a given problem instance. We call this the merged STN model.
To illustrate the concept of an STN and how it is constructed, we provide a simple example in continuous optimization, where the search space can be visualized alongside the STN. The Schwefel 2.26 benchmark function in two dimensions is used, whose fitness landscape is multi-modal and multi-funneled. Figure 1 illustrates a merged STN representing the search process of two metaheuristics: iterated local search (ILS), a single-point method, and differential evolution (DE) a population-based method.
Apart from visualizing the network models, a set of quantitive metrics can be computed. The most basic metrics are the number of nodes and edges, but a variety of other metrics could be calculated such as the degree distribution, length of paths, community structure, and centrality of nodes, to name a few. To keep things simple we propose five straightforward network metrics to assess the global structure of the trajectories, and thus bring insight into the difficulty of the instances and the behavior of the metaheuristics modeled. These metrics are:
nodes: Total number of nodes.
nbest: Number of nodes with the best-found evaluation.
nend: Number of nodes at the end of trajectories (other than those with the best evaluation).
nshared: Number of nodes visited by more than one algorithm.
best-strength: Normalised incoming strength (weighted degree) of the best node(s).
Table 1 shows the values of these metrics for the illustrative example discussed.
The ntotal metric indicates that DE has longer trajectories than ILS, which may be a sign of a wider exploration of the search space.
The higher value of best-strength for the DE STN in comparison to the ILS STN indicates that DE is more likely to reach the best solution for this instance.
Continuous Optimization Case Study
The continuous optimization problems considered are single-objective, static, bound-constrained, multivariate minimization problems. A sample of five minimization benchmark functions (Michalewicz, Quadric, Rana, Salomon, and Schwefel 2.26) with different characteristics were chosen in our study. Three metaheuristics were implemented: particle swarm optimization (PSO), differential evolution (DE), and iterated local search (ILS).
A location is a non-empty subset of solutions that results from a predefined partitioning of the search space. The continuous search space was partitioned into discrete hypercubes of a predefined size, defining a location as a hypercube of solutions. A partition factor parameter (PF) was used to partition the space into hypercubes with sides of length 10^PF . For example, if PF = -1, then the solution space was divided into hypercubes of length 0.1 and each location (node in the STN) was equivalent to one of these hypercubes.
More details can be found in the full article. Here, we show and briefly discuss the merged STN models for the Rana benchmark function with three values of the partition factor parameter (Fig. 2). The Rana function has variables in the range [-512, 512], and our study considers a 3-dimensional function. On this instance, PSO, DE, and ILS achieved success rates of 0%, 80%, and 40%, respectively.
The STNs with both fine and medium partitioning show that all except two of the DE runs (in orange) converged on the location of the best solution (which in this case contains the global optimum), corresponding with the reported success rate of 80%. Likewise, four ILS trajectories converge on the global optimum, corresponding with the 40% success rate. As can be seen from the STN with fine partitioning, none of the PSO trajectories (in green) reach the best location, corresponding to the 0% success rate. For the medium partitioning, three of the PSO trajectories join the STN connected component containing the best location; one of the PSO trajectories reaches the best location with this search space partitioning (a hypercube of length 10). The different partition levels allow us to inspect the search process at different levels of granularity.
Combinatorial Optimization Case Study
We selected the p-median problem, a classic facility location problem. In the p-median problem, the goal is to locate p facilities among n > p demand points. After locating the facilities, each demand point is allocated to the closest facility. The objective is to locate the p facilities such that the sum of the distances (travel costs) is minimized. Five instances of increasing difficulty (pmed6, ..., pmed10) were selected from the OR Library. Three metaheuristics were implemented: an ant colony optimization (ACO) approach, a biased random key genetic algorithm (BRKGA), and an iterated local search (ILS) method.
In the continuous domain, search spaces were partitioned into discrete hypercubes of a predefined length, defining a location as a hypercube of solutions. This cannot be done for discrete spaces. For discrete spaces, locations can be associated with individual solutions, that is without search space partitioning. However, it is still desirable to coarsen the search space in order to appreciate the trajectories at different levels of granularity. Therefore, we propose a partitioning scheme based on the solutions traversed by the search trajectories. The idea is to group as a single location all solutions sharing the same value in some variables while ignoring (removing) other variables. This reduces the number of locations and thus coarsens the search space. Intuitively, the less variability we find in the values taken by a decision variable (position) in the solutions (trajectory data), the higher should be the chance to remove this variable for the purpose of partitioning. The variability in the values of a decision variable can be covered by a measure from information theory (Shannon entropy).
More details can be found in the full article. Here, we show and briefly discuss the merged STN models for the pmed9 instance with no search space partitioning, and two different levels of search space partitioning (Fig. 3). On this instance, ACO, BRKGA, and ILS achieved success rates of 0%, 0%, and 100%, respectively.
The STN with no partitioning shows no overlap between the trajectories of either the same algorithm or different algorithms. Some trajectories of BRKGA (orange) show cycling (oscillation) between solutions, observed as the larger nodes and thicker edges. The only successful algorithm for pmed9 is ILS; we can observe the 10 ILS runs converging to 10 different optimal solutions (red nodes). The medium partitioning STN model is similar to the no partitioning model, apart from some larger nodes (indicating cycles) appearing in the ACO (green) and BRKGA (orange) trajectories. In contrast, the coarse partitioning STN model shows that all ILS runs are attracted by the same location (large red node), which indicates that most original optimal solutions are similar in solution space. The coarse partitioning model also shows shared locations visited by more than one algorithm (light gray nodes), as well as additional cycling behavior and interconnections of the BRKGA trajectories. What seemed to be wide exploratory behavior from BRKGA (larger trajectories) in the no partitioning model proves, after coarsening, to represent movements within reduced areas of the search space.
We argue that STNs are an accessible tool to analyze and visualize the behavior of any type of metaheuristic. Creating the models does not require additional sampling techniques, instead, data are collected from a set of runs of the studied metaheuristics. STNs provide insight into the convergence behavior of algorithms and their performance differences. They allow us to observe and quantify which portions of the search space attract the process and thus act as traps in the way of locating the best solution. We can also identify frequently traversed areas of the search space by a given algorithm or set of algorithms, as well as the existence of cycling (oscillating) behavior. We argue that this information gives new insights into understanding the dynamics of metaheuristics, and thus can be used to improve their design and to inform the selection of the most suitable algorithm for a given problem.
By providing the source code and example datasets for generating and analyzing the models (STNs repository), we hope that this tool will benefit the research communities in metaheuristics and evolutionary algorithms.
EvoStar 2021 was held on April 7th-9th 2021, and started with a clear sunny day (well, at least in some parts of the world). In 2020, like most conferences, EvoStar was held online, with the hope that in 2021 it would be possible for participants to come together in Sevilla, Spain, and enjoy a live conference. However, due to the restrictions still in place, this was not possible, and EvoStar 2021 was, once again, an online conference.
In total, EvoStar 2021 received 213 paper submissions, with 84 being accepted as long talks and 29 as short talks. EvoStar also received 11 late-breaking abstracts. The submissions were authored by a total of 572 authors from 46 countries (Fig. 1). Concerning participation, it had more than 234 attendees!
The conference started with a heartwarming welcome by SPECIES President Marc Schoenauer. Afterward, the parallel sessions of each conference started. The first day had sessions from EuroGP, EvoMUSART, EvoCOP and EvoApplications. The day ended with the best paper session of EvoMUSART.
In the afternoon after the sessions, we had our first plenary invited talk, entitled "Recombination, Parallelism, and the Future of Combinatorial Evolutionary Computation" by Darrell Whitley, from Colorado State University, USA. In his inspiring talk, Darrell presented new insights about recombination operators and how they can be used to empower search methods for combinatorial optimization problems.
In the evening, the participants joined the gather.town platform for the virtual poster session. In this platform, each participant controls a character (that can be customized), which was placed in a virtual conference venue. The venue was open-world, in the sense that you could see all the participants, and if you wanted to chat with someone you just had to get close to their avatar, and you would be asked permission to start a video conversation. The posters were attached to the virtual walls with their authors eager to share their work! In spite of being a virtual place, people had some fun!
The second day of the conference started with parallel sessions from EvoMUSART, EvoCOP, and the best paper presentation from EvoApplications. Right after lunch, we had the best paper session for EvoCOP, and we ended the day with the best paper session for EuroGP.
The last day started early (in Seville local time), with a networking session. Afterward, we had the 3 final parallel sessions, one from EvoMUSART and 2 from EvoApplications.
After a quick break, we had our second Plenary Invited Talk, entitled: "How the architecture of hyperastronomically large genotype spaces shapes evolutionary dynamics" by Susanna Manrubia, from the Spanish National Centre for Biotechnology (CSIC). She gave a motivational talk on how genotype-phenotype maps partition the space of sequences into complex genotype networks, and how this is essential to further understand and update evolutionary theory.
Then came the time for the closing session chaired by Anna Esparcia-Alcázar, Vice-President of SPECIES and EvoStar Coordinator. She started by presenting the EvoStar Award for Outstanding Contribution to Evolutionary Computation, which was granted to Conor Ryan, from University of Limerick, Ireland, and Juan Romero from the University of A Coruña, Spain.
Thereafter, we proceeded with the awards for the best papers of each conference:
EuroGP: Towards incorporating Human Knowledge in Fuzzy Pattern Tree Evolution by Aidan Murphy, Grainne Murphy, Douglas Mota Dias, Jorge Amaral, Enrique Naredo, and Conor Ryan
EvoApplications: Towards Feature-Based Performance Regression Using Trajectory Data by Anja Jankovic, Tome Eftimov and Carola Doerr
EvoCOP: Hybridization of Racing Methods with Evolutionary Operators for Simulation Optimization of Traffic Lights Programs by Christian Cintrano, Javier Ferrer, Manuel López-Ibáñez and Enrique Alba
EvoMUSART: Identification of Pure Painting Pigment using Machine Learning algorithms by Ailin Chen, Rui Jesus and Marcia Vilarigues.
Finally, it was time for the Best Student Poster Award which, amongst tough competition, was granted to Aidan Murphy.
Congratulations to all the winners!
In the days following the conference, we sent a satisfaction survey to all the attendees and collected 83 replies. The comments were mostly very positive, and the participants rated the Evostar 2021 Experience a stunning 4.55 / 5 Stars.
Awards and News
Software Engineering Rising Star
Federica Sarro, an active young professor in the field of search-based software engineering (SBSE), has been awarded the 2021 IEEE Technical Council on Software Engineering’s Rising Star Award for "her high-impact, industrially relevant research o predictive modeling for software engineering. In parallel to her research excellence, she has also made substantial contributions to the training of a large cohort of students, and to the development of improved curricula in support of this training".
Federica Sarro is a member of the Computer Science Department at University College London (UCL), an important driving force behind SBSE. Evolutionary algorithms, specially multi-objective EAs and genetic programming, are key tools for SBSE. Well done Federica!
2021 ACM SIGEVO Election Results
The results of the 2021 elections for ACM SIGs (special interest groups) have now been published. Congratulations to the active members of our community who have been elected to serve on the SIGEVO (interest group on genetic and evolutionary computation) executive committee for the term of 1st July 2021- 30th June 2027:
Emma Hart, Edinburgh Napier University, Scotland, UK
Gisele L. Pappa, Federal University of Minas Gerais, Brazil
Juergen Branke, University of Warwick, England, UK
Andrew M. Sutton, University of Minnesota Duluth, USA
Gabriela Ochoa, University of Stirling, Scotland, UK
Bing Xue, Victoria University of Wellington, Canada.
TELO Inaugural Issue
We are happy to report that the first issue has just been published online. All papers will be freely available for a limited time, so have a look! We hope that you find this journal a valuable asset for our community and will submit some of your future work there.
Computational intelligence is a part of daily life for almost everyone, whether or not they see the computation taking place just behind their screen. As a consequence, researchers and developers in computational intelligence constantly face new and more complex optimization and learning problems. Evolutionary computation plays an important role in this area. TELO aims to be home to the whole evolutionary computation community, including related areas such as evolutionary machine learning, population-based methods, Bayesian optimization and swarm intelligence. TELO welcomes papers that make solid contributions to theory, method and applications.
For further information and to submit your manuscript, please visit the TELO homepage.
Genetic and Evolutionary Computation Conference
GECCO 2021 will be held as an online event, 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.
Foundations of Genetic Algorithms
FOGA 2021 will be held from September 6th to September 8th as a virtual event, initially planned to be 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.
Calls for Papers
Special Issue on Benchmarking Sampling-Based Optimization Heuristics: Methodology and Software
IEEE Transactions on Evolutionary Computation
The goal of this special issue is to provide an overview of state-of-the-art software packages, methods, and data sets that facilitate sound benchmarking of evolutionary algorithms and other optimization techniques. By providing an overview of today's benchmarking landscape, new synergies will be laid open, helping the community to converge towards higher compatibility between tools, towards better reproducibility and replicability of our research, better use of resources, and, ultimately, towards higher standards in our benchmarking practices.
We welcome submissions on the following topics:
Submission deadline: August 31, 2021
Tentative publication date: Summer 2022
Manuscripts should be prepared according to the Information for Authors section of the journal, and submissions should be made through the journal submission website, by selecting the Manuscript Type "BENCH Special Issue Papers'" and clearly adding "Benchmarking Special Issue Paper" to the comments to the Editor-in-Chief.
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 a developer of a piece of EC software, and 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
Sub-editor: James McDermott
Associate Editors: Emma Hart, Una-May O'Reilly, Nadarajen Veerapen, and Darrell Whitley