Abstract Numerous metaheuristic search algorithms have been developed due to their effectiveness in solving optimization problems. This has created a need for systematic approaches to classify and compare them to understand their search behaviors better and guide the selection of appropriate algorithms for specific problems. However, common approaches in the literature rely mainly on the theoretical aspects of these algorithms, often not considering how similar algorithms perform in practice. To address this gap, we propose a general framework for analyzing the empirical similarity of metaheuristics using clustering techniques. The framework groups algorithm instances based on their performance profiles and then analyzes the distribution of algorithmic components and parameters across these groups. This approach provides a performance-driven perspective on metaheuristic similarity by grouping algorithm instances with similar performance while also offering insights into how specific algorithmic components and parameters relate to those performance behaviors. To illustrate the framework, we present a baseline implementation and case study involving 36 Particle Swarm Optimization instances, each defined by different combinations of algorithmic components and parameters. Through this case study, the framework identifies clusters based on different performance behaviors and then analyzes the distribution of the algorithmic components and parameters across clusters, revealing component-performance links. These results suggest that the proposed framework offers a structured basis for understanding empirical similarity among metaheuristics, provides a complementary perspective to theoretical classifications, and supports ongoing efforts to map the algorithm design space.

Multi-Niche Constraint Satisfaction problems are common in applications of evolutionary computation for industrial design, where the optimization algorithm is used as a preparatory step for prototype generation. In this context, we want an optimization algorithm that generates a set of diverse solutions that satisfy multiple design constraints. In this paper, we investigate the use of Lexicase-DE (Lex-DE) an algorithm recently proposed for the Multi-Task optimization problem, to solve a Multi-Niche Constraint Satisfaction problem using a surrogate function from a real world design application. We also attempt to enhance the Lex-DE with two modifications from the niching literature: Multiple Population and Niching Constraints, but our experiments indicate that lexicase selection by itself already provides enough diversity for this particular application.

In this study, we use Genetic Programming (GP) to compose new optimization benchmark functions. Optimization benchmarks have the important role of showing the differences between evolutionary algorithms, making it possible for further analysis and comparisons. We show that the benchmarks generated by GP are able to differentiate algorithms better than human-made benchmark functions. The fitness measure of the GP is the Wasserstein distance of the solutions found by a pair of optimizers. Additionally, we use MAP-Elites to both enhance the search power of the GP and also illustrate how the difference between optimizers changes by various landscape features. Our approach provides a novel way to automate the design of benchmark functions and to compare evolutionary algorithms.

This paper presents two new Genotypic Diversity Metrics (GDMs) for estimating the diversity of populations in real-coded, multi-modal optimization problems. The two techniques introduced are the Minimum Individual Distance (DMID) and Radius Diversity (DRaD). The design of these two metrics focuses on the relative position of the solutions in the population. This choice addresses problems observed in traditional diversity measures regarding their behavior as the number of optima increases in a multi-modal problem. The proposed metrics are evaluated on four different experiments, which investigate the metrics' theoretical and practical properties. Experimental results reveal several abnormal behaviors of the Pairwise Distance Metric (Dpw), while showing that the proposed metrics perform in a more stable and intuitive way as the number of optima in the problem increases. These results recommend the metrics' use for developing and evaluating optimization meta-heuristics

The performance of multiobjective evolutionary algorithms (MOEAs) varies across problems, making it hard to develop new algorithms or apply existing ones to new problems. To simplify the development and application of new multiobjective algorithms, there has been an increasing interest in their automatic design from their components. These automatically designed metaheuristics can outperform their human-developed counterparts. However, it is still unknown what are the most influential components that lead to performance improvements. This study specifies a new methodology to investigate the effects of the final configuration of an automatically designed algorithm. We apply this methodology to a tuned Multiobjective Evolutionary Algorithm based on Decomposition (MOEA/D) designed by the iterated racing (irace) configuration package on constrained problems of 3 groups: (1) analytical real-world problems, (2) analytical artificial problems and (3) simulated real-world. We then compare the impact of the algorithm components in terms of their Search Trajectory Networks (STNs), the diversity of the population, and the anytime hypervolume values. Looking at the objective space behavior, the MOEAs studied converged before half of the search to generally good HV values in the analytical artificial problems and the analytical real-world problems. For the simulated problems, the HV values are still improving at the end of the run. In terms of decision space behavior, we see a diverse set of the trajectories of the STNs in the analytical artificial problems. These trajectories are more similar and frequently reach optimal solutions in the other problems.

The field of metaheuristics has a long history of finding inspiration in natural systems, starting from evolution strategies, genetic algorithms, and ant colony optimization in the second half of the 20th century. In the last decades, however, the field has experienced an explosion of metaphor-centered methods claiming to be inspired by increasingly absurd natural (and even supernatural) phenomena-several different types of birds, mammals, fish and invertebrates, soccer and volleyball, reincarnation, zombies, and gods. Although metaphors can be powerful inspiration tools, the emergence of hundreds of barely discernible algorithmic variants under different labels and nomenclatures has been counterproductive to the scientific progress of the field, as it neither improves our ability to understand and simulate biological systems nor contributes generalizable knowledge or design principles for global optimization approaches. In this article we discuss some of the possible causes of this trend, its negative consequences for the field, and some efforts aimed at moving the area of metaheuristics toward a better balance between inspiration and scientific soundness.

The GDMC AI settlement generation challenge is a procedural content generation (PCG) competition about producing an algorithm that can create a settlement in the game Minecraft. In contrast to the majority of AI competitions, the GDMC entries are evaluated by human experts on several criteria such as adaptability, functionality, evocative narrative, and visual aesthetics – all of which represent challenges to state-of-the-art PCG systems. This paper contains a collection of written experiences with this competition, by participants, judges, organizers and advisors. We asked people to reflect both on the artifacts themselves, and on the competition in general. The aim of this paper is to offer a shareable and edited collection of experiences and qualitative feedback which have the potential to push forward PCG and computational creativity, but would be lost once the individual assessments are compressed to scalar ratings. We reflect upon organizational issues for AI competitions, and discuss the future of the GDMC competition.

The performance of multiobjective algorithms varies across problems, making it hard to develop new algorithms or apply existing ones to new problems. To simplify the development and application of new multiobjective algorithms, there has been an increasing interest in their automatic design from component parts. These automatically designed metaheuristics can outperform their human-developed counterparts. However, it is still uncertain what are the most influential components leading to their performance improvement. This study introduces a new methodology to investigate the effects of the final configuration of an automatically designed algorithm. We apply this methodology to a well-performing Multiobjective Evolutionary Algorithm Based on Decomposition (MOEA/D) designed by the irace package on nine constrained problems. We then contrast the impact of the algorithm components in terms of their Search Trajectory Networks (STNs), the diversity of the population, and the hypervolume. Our results indicate that the most influential components were the restart and update strategies, with higher increments in performance and more distinct metric values. Also, their relative influence depends on the problem difficulty: not using the restart strategy was more influential in problems where MOEA/D performs better; while the update strategy was more influential in problems where MOEA/D performs the worst.

The Resource Allocation approach (RA) improves the performance of MOEA/D by maintaining a big population and updating few solutions each generation. However, most of the studies on RA generally focused on the properties of different Resource Allocation metrics. Thus, it is still uncertain what the main factors are that lead to increments in performance of MOEA/D with RA. This study investigates the effects of MOEA/D with the Partial Update Strategy (PS) in an extensive set of MOPs to generate insights into correspondences of MOEA/D with the partial update and MOEA/D with small population size and big population size. Our work undertakes an in-depth analysis of the populational dynamics behaviour considering their final approximation Pareto sets, anytime hypervolume performance, attained regions, and number of unique nondominated solutions. Our results indicate that MOEA/D with partial update progresses with the search as fast as MOEA/D with small population size and explores the search space as MOEA/D with big population size. MOEA/D with partial update can mitigate common problems related to population size choice with better convergence speed in most MOPs, as shown by the results of hypervolume and number of unique nondominated solutions, and as the anytime performance and Empirical Attainment Function indicate.

In the context of optimization problems, the performance of an algorithm depends on the problem. It is difficult to know a priori what algorithm (and what parameters) will perform best on a new problem. For this reason, we previously proposed a framework that uses grammatical evolution to automatically generate swarm intelligence algorithms given a training problem. However, we observed two issues that affected the results of the framework. The first issue was that sometimes the training problems are too easy, and any candidate algorithm could solve it or too difficult that no candidate algorithm could solve them. The second issue was the presence of parameters in the grammar, which causes a significant increase in the search space. In this work, we addressed those issues by investigating three training schedules in which the problems start easy and get harder over time. We also investigated whether numerical parameters should be part of the grammar. We compared these training schedules to the previous one and compared the performance of the generated algorithms against the traditional algorithms, which are DE, PSO, and CS. We found that gradually increasing the difficulty of the training problem produced algorithms that could solve more testing instances than training only in 10-D. The results suggest that a step-by-step increase in difficulty is a better approach overall. We also found that including parameters in the grammar resulted in algorithms on par with the traditional meta-heuristics. Besides, as expected, our results show that removing parameters from the grammar exhibit the worst overall performance. However, interestingly it could solve most of the testing instances within the given testing budget.

Recent studies on resource allocation suggest that some subproblems are more important than others in the context of the MOEA/D, and that focusing on the most relevant ones can consistently improve the performance of that algorithm. These studies share the common characteristic of updating only a fraction of the population at any given iteration of the algorithm. In this work, we investigate a new, more straightforward partial update strategy, in which a random subset of solutions is selected at every iteration. The performance of the MOEA/D-DE using this new resource allocation approach is compared experimentally against that of the standard MOEA/D-DE and the MOEA/D-DE with relative improvement-based resource allocation. The results indicate that using MOEA/D with this new partial update strategy results in improved HV and IGD values, and a much higher proportion of non-dominated solutions, particularly as the number of updated solutions at every iteration is reduced.

Automatically generating game levels using Procedural Content Generation (PCG) is a challenging problem because of the necessity of attending both functional and nonfunctional requirements. In the particular example of level generation for Super Mario, Machine Learning approaches, such as GANs and Reinforcement Learning, have shown promise. However, these black-box approaches usually are not explainable, and thus difficult to integrate with human designers. We propose a different level-generation system that uses a reachable graph structure, automatic detection of level structures, and formal graph grammars. A human designer can also easily add or remove structures to use the system as a level co-creation tool. An experimental analysis shows that the proposed system can generate playable and visually pleasing levels, while revealing some limitations of current approaches on platformer level generation, such as the generation of backtracking segments.

International audience

The analysis of electroencephalogram (EEG) waves is of critical importance for the diagnosis of sleep disorders, such as sleep apnea and insomnia, besides that, seizures, epilepsy, head injuries, dizziness, headaches and brain tumors. In this context, one important task is the identification of visible structures in the EEG signal, such as sleep spindles and K-complexes. The identification of these structures is usually performed by visual inspection from human experts, a process that can be error prone and susceptible to biases. Therefore there is interest in developing technologies for the automated analysis of EEG. In this paper, we propose a new Genetic Programming (GP) framework for feature construction and dimensionality reduction from EEG signals. We use these features to automatically identify spindles and K-complexes on data from the DREAMS project. Using 5 different classifiers, the set of attributes produced by GP obtained better AUC scores than those obtained from PCA or the full set of attributes. Also, the results obtained from the proposed framework obtained a better balance of Specificity and Recall than other models recently proposed in the literature. Analysis of the features most used by GP also suggested improvements for data acquisition protocols in future EEG examinations.

This paper presents a comparative study between two data mining techniques: Genetic Programming (GP) and Deep Learning (DL). This comparison will be based on the cart pole balancing problem. We also compared the results with Q-Learning (QL), a classic algorithm that is also used in hybridizations with GP an DL for reinforcement learning problems. Our results presented that GP can rival DL for this kind of problem.

We perform an experimental study about the effect of the tournament size parameter from the Tournament Selection operator. Tournament Selection is a classic operator for Genetic Algorithms and Genetic Programming. It is simple to implement and has only one control parameter, the tournament size. Even though it is commonly used, most practitioners still rely on rules of thumb when choosing the tournament size. For example, almost all works in the past 15 years use a value of 2 for the tournament size, with little reasoning behind that choice. To understand the role of the tournament size, we run a real-valued GA on 24 BBOB problems with 10, 20 and 40 dimensions. We also vary the crossover operator and the generational policy of the GA. For each combination of the above factors we observe how the quality of the final solution changes with the tournament size. Our findings do not support the indiscriminate use of tournament size 2, and recommend a more careful set up of this parameter.

In this paper, we formulate a real-world Facility Layout Problem as a constraint satisfaction problem and propose a new method with a genetic algorithm. The created layout should reflect the desires of the users of the facility such as individuality, intuition, comfortableness, and convenience. We employed a GA using Levy Flights as basis for an improved mutation operator and used an island model GA with different decoding methods for each island. The experimental results show the effectiveness of the proposed method.

In the petroleum industry, accurate oil reservoir models are crucial in the decision making process. One critical step in reservoir modeling is History Matching (HM), where the parameters of a reservoir model are adjusted in order to improve its accuracy and enhance future prediction. Recent works applied evolutionary algorithms (EAs) such as GA, DE and PSO for the HM problem, but they have been limited to classical versions of these algorithms. A significant obstacle to applying EAs to HM is that each call to the fitness function requires an expensive simulation, making it difficult to tune the control parameters for EAs in order to obtain the best performance. We apply and evaluate state-of-the-art, adaptive differential algorithms (SHADE and jDE), as well as non-adaptive evolutionary algorithms (standard DE, PSO) that have been tuned using standard black-box benchmark functions as training instances. Both of these approaches result in significant improvements compared to standard methods in the HM literature. We also apply fitness distance correlation analysis to the search space explored by our algorithms in order to better understand the landscape of the HM problem.

Many feature selection methods are based on the assumption that important features are highly correlated with their corresponding classes, but mainly uncorrelated with each other. Often, this assumption can help eliminate redundancies and produce good predictors using only a small subset of features. However, when the predictability depends on interactions between features, such methods will fail to produce satisfactory results. In this paper a method that can find important features, both independently and dependently discriminative, is introduced. This method works by performing two different types of permutation tests that classify each of the features as either irrelevant, independently predictive or dependently predictive. It was evaluated using a classifier based on an ensemble of genetic programs. The attributes chosen by the permutation tests were shown to yield classifiers at least as good as the ones obtained when all attributes were used during training - and often better. The proposed method also fared well when compared to other attribute selection methods such as RELIEFF and CFS. Furthermore, the ability to determine whether an attribute was independently or dependently predictive was confirmed using artificial datasets with known dependencies.

In this paper, we propose a PSO algorithm with transition probability based on Hamming distance for solving planar graph coloring problems. PSO was originally intended to handle only continuous optimization problems. To apply PSO to discrete problems, the standard arithmetic operators of PSO need to be redefined over discrete space. In this work, we propose a new algorithm that uses transition probability based on Hamming distance into PSO. The experimental results show that the new algorithm can get higher success rate and smaller average iterations than a Genetic Algorithm and the conventional PSO.

The Portfolio Optimization problem consists of the selection of a group of assets to a long-term fund in order to minimize the risk and maximize the return of the investment. This is a multi-objective (risk, return) resource allocation problem, where the aim is to correctly assign weights to the set of available assets, which determines the amount of capital to be invested in each asset.

The generation of profitable trading rules for Foreign Exchange (FX) investments is a difficult but popular problem. The use of Machine Learning in this problem allows us to obtain objective results by using information of the past market behavior. In this paper, we propose a Genetic Algorithm (GA) system to automatically generate trading rules based on Technical Indexes. Unlike related researches in the area, our work focuses on calculating the most appropriate trade timing, instead of predicting the trading prices.

Recently, a number of works have been done on how to use Genetic Algorithms to solve the Portfolio Optimization problem, which is an instance of the Resource Allocation problem class. Almost all these works use a similar genomic representation of the portfolio: An array, either real, where each element represents the weight of an asset in the portfolio, or binary, where each element represents the presence or absence of an asset in the portfolio.

Portfolio optimization by GA is a problem that has recently received a lot of attention. However, most works in this area have so far ignored the effects of cost on Portfolio Optimization, and haven't directly addressed the problem of portfolio management (continuous optimization of a portfolio over time). In this work, we use the Euclidean Distance between the portfolio selection in two consecutive time periods as measure of cost, and the objective sharing method to balance the goals of maximizing returns and minimizing distance over time. We also improve the GA method by adding genetic material from previous runs into the new population (seeding). We experiment our method on historical monthly data from the NASDAQ and NIKKEI indexes, and obtain a better result than pure GA, defeating the index under non-bubble market conditions.