Idempotent Boolean functions form a highly structured subclass of Boolean functions that is closely related to rotation symmetry under a normal-basis representation and to invariance under a fixed linear map in a polynomial basis. These functions are attractive as candidates for cryptographic design, yet their additional algebraic constraints make the search for high nonlinearity substantially more difficult than in the unconstrained case. In this work, we investigate evolutionary methods for constructing highly nonlinear idempotent Boolean functions for dimensions n = 5 up to n = 12 using a polynomial basis representation with canonical primitive polynomials. Our results show that the problem of evolving idem-potent functions is difficult due to the disruptive nature of crossover and mutation operators. Next, we show that idempotence can be enforced by encoding the truth table on orbits, yielding a compact genome of size equal to the number of distinct squaring orbits.

The unrelated parallel machines scheduling problem is an important and challenging problem with significant industrial relevance. This paper addresses a specific variant involving precedence constraints between jobs and the requirement of additional resources for job execution. The problem is NP-hard, and practical solution approaches are therefore predominantly heuristic. In dynamic scheduling environments, dispatching rules (DRs) represent one of the most effective and widely used heuristic approaches. A DR consists of a schedule generation scheme (SGS) and a priority function (PF). The manual design of high-quality DRs is difficult and time-consuming, making the problem well suited for hyper-heuristic and evolutionary approaches. In this work, genetic programming (GP) is employed to automatically evolve the PF component of DRs. Additionally, several problem-specific SGSs are proposed and evaluated. The evolved DRs are compared against adapted state-of-the-art DRs from the literature. The results show that the proposed GP-based approach enables the automated generation of high-quality DRs, outperforming manually designed heuristics for the considered problem.

Routing policies (RPs) are simple heuristics used to solve the electric vehicle routing problem, suitable for large or dynamic problems.Designing efficient RPs is difficult, because of which researchers started applying genetic programming (GP) for their automated development.For GP to be able to generate efficient RPs, it must be supplied with appropriate building blocks, i.e., functions and problem features, to construct the solution.This study investigates the selection of appropriate function nodes to construct RPs.The experiments demonstrate that the best results are obtained when using the most simple arithmetic operators enhanced with some additional operators.

Efficient container handling in maritime ports represents an important issue in transportation of various goods, since most is being carried out by the sea. As such, various optimisation methods have been utilised to determine the best possible sequence of handling containers in container yards, in order to increase the throughput. One type of methods used for solving such problems are relocation rules (RRs), simple constructive heuristics that determine how the containers need to be rearranged in the yard while they are being retrieved. However, such heuristics are hard to design manually, which prompted the application of various hyper-heuristic methods. Although hyper-heuristics can design new and well performing heuristics, they still suffer from certain issues. For example, a single heuristic can hardly perform well in all possible situations, which can result in poor solutions. To resolve this issue, it is possible to combine such individual heuristics in ensembles, in which RRs jointly perform their decisions. In that way, even if a single RR performs a poor decisions, the other RRs in the ensemble can compensate for that so that in the end the ensemble still achieves a good overall solution. The goal of this study is to investigate how combining RRs into competitive ensembles can increase their performance in comparison to individual RRs and other ensemble types. The results demonstrate that the ensembles used in this study result in a significantly higher performance compared to individual RRs.

Abstract The Bin Packing Problem (BPP) is a well-known NP-hard problem with numerous real-world applications. This study focuses on minimizing waste and maximum lateness in a one-dimensional version of the BPP, which is particularly relevant in industrial contexts. The goal is to develop a constructive heuristic algorithm that can be adapted to various situations. We model the BPP as a Deterministic Markov Decision Process with discrete state and action spaces, where policies are represented by arithmetic expressions involving state variables. This approach allows for a clearer explanation of the decision process, in contrast to other methods like neural networks. To evolve these policies, we use Genetic Programming (GP). Trained on a set of BPP instances, the resulting policies are effective for solving new, unseen instances. In the experimental study, we explore different GP settings, including varying sets of symbols. The results reveal valuable insights about the importance of state variables, indicating that a smaller selection of them may yield the best results. The evolved policies are compared with an exact method from the literature, achieving similar outcomes but with significantly less computational time.

The container relocation problem (CRP) in shipping terminals is becoming increasingly important due to the growing amount of transferred goods. Until now, the most commonly investigated problem variant has been the offline CRP, in which the order in which the containers need to be retrieved is known beforehand. However, in many real-world situations this is not the case, which is modelled using the online CRP variant. In this variant, not all information is available from the beginning, but rather, it becomes available as the problem is being solved. Unfortunately, many traditional metaheuristic solution methods can not be applied to such a problem variant, which prompts the application of problem-specific heuristics called relocation rules (RRs). However, RRs are challenging to design manually, which prompted the application of genetic programming (GP) to design them automatically. Since GP was used only to design RRs for the offline problem variant, we apply GP to design relocation rules for the online variant in this study. The performance of GP is investigated under different levels of information availability to measure its performance. The results demonstrate that GP can evolve RRs that perform better than existing manually designed ones. Furthermore, the results show that in certain cases, rules generated for one level of information availability perform well for other levels, demonstrating that the evolved rules exhibit a good generalisation capability.

Automated design of heuristics with genetic programming (G P) has, in recent years, become an intensively researched research area. One of the most recent applications of this methodology is to generate relocation rules (RRs) for the container relocation problem (CRP). CRP is an important combinatorial optimisation problem that is found in ship ter-minals and warehouses. RRs are simple constructive heuristic methods that provide a good solution quickly, thus representing an alternative to computationally expensive exact or metaheuris-tic methods. Even though the RRs designed by GP provide an improvement over existing manually designed rules, they have limited performance. An efficient way to improve the performance of RRs generated by GP is to use ensemble learning. In this study, we apply ensemble learning on RRs generated by GP for CRP to improve the performance of individual rules. We investigate how different ensemble sizes and combination methods affect the quality of the results, as well as which rules are selected to form ensembles. The experimental study shows that ensembles constructed out of automatically designed RRs significantly improve performance compared to the individual rules.

Abstract In recent years, the growing interest in environmental sustainability has led to Electric Vehicle Routing Problems (EVRPs) attracting more and more attention. EVRPs involve the use of electric vehicles, which have additional constraints, such as range and recharging time, compared to conventional Vehicle Routing Problems (VRPs). The complexity and dynamic nature of solving VRPs often lead to the introduction of Routing Policies (RPs), simple heuristics that incrementally build routes. However, manually designing efficient RPs proves to be a challenging and time-consuming task. Therefore, there is a pressing need to explore the application of hyper-heuristics, in particular Genetic Programming (GP), to automatically generate new RPs. Since this method has not yet been investigated in the literature in the context of EVRPs, this study explores the applicability of GP to automatically generate new RPs for EVRP. To this end, three RP variants (serial, semiparallel, and parallel) are introduced in this study, along with a set of domain-specific terminal nodes to optimise three criteria: the number of vehicles, energy consumption, and total tardiness. The experimental analysis shows that the serial variant performs best in terms of energy consumption and number of vehicles, while the parallel variant is most effective in minimising the total tardiness. A comprehensive analysis of the proposed method is conducted to determine its convergence properties and the impact of the proposed terminal nodes on performance and to describe several generated RPs. The results show that the automatically generated RPs perform commendably compared to traditional methods such as metaheuristics and exact methods, which usually require significantly more runtime. More specifically, depending on the scenario in which they are used, the generated RPs achieve results that are about 20%-37% worse compared to the best known results for the number of vehicles in almost negligible time, in just some milliseconds.

Dynamic multi-objective (MO) scheduling problems are encountered in various real-world situations. Due to dynamic events that occur in such problems, one has to resort to using simple constructive heuristics, called dispatching rules (DRs), when tackling them. Since DRs are difficult to design manually there is a lack of existing DRs suitable for solving MO problems. Due to that reason, genetic programming has successfully been applied to evolve DRs specifically for solving MO problems. The process of evolving new DRs is computationally expensive, requiring a significant amount of time to obtain DRs of good quality. For that reason it is worth investigating inwhich ways the convergence of algorithms could be improved. One option is to use DRs previously evolved for optimising individual criteria to initialise the starting population when optimising a MO problem. The goal of this study is to investigate how such an initialisation strategy affects the performance of NSGA-II and NSGA-III when evolving DRs for MO problems. Therefore, 8 MO unrelated machines scheduling problems, containing between 2 and 5 criteria, are considered. The obtained results demonstrate that using previously evolved DRs for single objective optimisation leads to a faster convergence, and in many cases significantly better results.

The vehicle routing problem (VRP) is one of the most interesting NP-Hard problems due to the multitude of applications in the real world. This work tracks a VRP with zone-based prices inwhich each customer belongs to a particular zone, and the goal is to maximize the profit. The particularity of this VRP variant is that the provider needs to determine the prices for each zone and routes for all vehicles. However, depending on the selected zone prices, only a subset of customers will have to be visited. In this work, we propose a novel route generation scheme (RGS) that considers both decisions simultaneously. The RGS is guided by a priority function (PF), which determines the next customer to visit. Since designing efficient PFs manually is a difficult and time-consuming task, hyper-heuristic methods, specifically genetic programming (GP), have been used in this study to generate them automatically. Furthermore, to test the performance of the generated PFs, a genetic algorithm is also used to exploit the RGS to construct the solution. The experimental analysis shows that the evolved heuristics provide reasonable quality solutions quickly, in contrast with the current state-of-the-art. Furthermore, GP produces better results than GA for some problem instances.

Evolvability refers to the ability of an individual genotype (solution) to produce offspring with mutually diverse phenotypes. Recent research has demonstrated that divergent search methods, particularly novelty search, promote evolvability by implicitly creating selective pressure for it. The main objective of this paper is to provide a novel perspective on the relationship between neuroevolutionary divergent search and evolvability. In order to achieve this, several types of walks from the literature on fitness landscape analysis are first adapted to this context. Subsequently, the interplay between neuroevolutionary divergent search and evolvability under varying amounts of evolutionary pressure and under different diversity metrics is investigated. To this end, experiments are performed on Fetch Pick and Place, a robotic arm task. Moreover, the performed study in particular sheds light on the structure of the genotype-phenotype mapping (the behavior landscape). Finally, a novel definition of evolvability that takes into account the evolvability of offspring and is appropriate for use with discretized behavior spaces is proposed, together with a Markov-chain-based estimation method for it.

Priority rules are one of the most common and popular approaches to real-time scheduling. Over the last decades, several methods have been developed to generate rules automatically. In addition, it has been shown that combining rules into ensembles is better than using a single rule in many cases. In this paper, we analyze different ways to create and use ensembles previously developed through genetic programming. In our study, we classify ensembles as either collaborative or coordinated, depending on how the rules are used. In the first case, all the rules contribute to the creation of the same solution, while in the second case, each rule works independently on its own solution, and the best of them is selected as the solution of the ensemble. We found that each method has its own strengths and weaknesses, which leads us to use them in combination. Based on this hypothesis, we developed new methods to design and combine collaborative and coordinated ensembles and evaluated these methods for the One Machine Scheduling Problem with time-varying capacity and minimization of total tardiness. The results of the experimental study provided interesting insights into the use of ensembles and showed that our proposals outperform previous methods.

Abstract The Travelling Salesman Problem (TSP) is a well-known optimisation problem that has been widely studied over the last century. As a result, a variety of exact and approximate algorithms have been proposed in the literature. When it comes to solving large instances in real-time, greedy algorithms guided by priority rules represent the most common approach, being the nearest neighbour (NN) heuristic one of the most popular rules. NN is quite general but it is too simple and so it may not be the best choice in some cases. Alternatively, we may design more sophisticated heuristics considering the particular features of families of instances. To do that, we have to consider problem attributes other than the proximity of the next city to build priority rules. However, this process may not be easy for humans and so it is often addressed by some learning procedure. In this regard, hyper-heuristics as Genetic Programming (GP) stands as one of the most popular approaches. Furthermore, a single heuristic, even being good in average, may not be good for a number of instances of a given set. For this reason, the use of ensembles of heuristics is often a good alternative, which raises the problem of building ensembles from a given set of heuristic rules. In this paper, we study the application of two kinds of ensembles to the TSP. Given a set of TSP instances having similar characteristics, we firstly exploit a GP to build a set of heuristics involving a number of problem attributes, and then we build ensembles combining these heuristics by means of a Genetic Algorithm (GA). The experimental study provided valuable insights into the construction and utilisation of single rules and ensembles. It clearly demonstrated that the performance of ensembles justifies the time invested when compared to using individual heuristics.

Finding Boolean functions suitable for cryptographic primitives is a complex combinatorial optimization problem, since they must satisfy several properties to resist cryptanalytic attacks, and the space is very large, which grows super exponentially with the number of input variables. Recent research has focused on the study of Boolean functions that satisfy properties on restricted sets of inputs due to their importance in the development of the FLIP stream cipher. In this paper, we consider one such property, perfect balancedness, and investigate the use of Genetic Programming (GP) and Genetic Algorithms (GA) to construct Boolean functions that satisfy this property along with a good nonlinearity profile. We formulate the related optimization problem and define two encodings for the candidate solutions, namely the truth table and the weightwise balanced representations. Somewhat surprisingly, the results show that GA with the weightwise balanced representation outperforms GP with the classical truth table phenotype in finding highly nonlinear Weightwise Perfectly Balanced (WPB) functions. This is in stark contrast to previous findings on the evolution of balanced Boolean functions, where GP always performs best.

Finding balanced, highly nonlinear Boolean functions is a difficult problem where it is not known what nonlinearity values are possible to be reached in general. At the same time, evolutionary computation is successfully used to evolve specific Boolean function instances, but the approach cannot easily scale for larger Boolean function sizes. Indeed, while evolving smaller Boolean functions is almost trivial, larger sizes become increasingly difficult, and evolutionary algorithms perform suboptimally.

Dynamic scheduling problems are important optimisation problems with many real-world applications. Since in dynamic scheduling not all information is available at the start, such problems are usually solved by dispatching rules (DRs), which create the schedule as the system executes. Recently, DRs have been successfully developed using genetic programming. However, a single DR may not efficiently solve different problem instances. Therefore, much research has focused on using DRs collaboratively by forming ensembles. In this paper, a novel ensemble collaboration method for dynamic scheduling is proposed. In this method, DRs are applied independently at each decision point to create a simulation of the schedule for all currently released jobs. Based on these simulations, it is determined which DR makes the best decision and that decision is applied. The results show that the ensembles easily outperform individual DRs for different ensemble sizes. Moreover, the results suggest that it is relatively easy to create good ensembles from a set of independently evolved DRs.

Dynamic online scheduling is a difficult problem which commonly appears in the real world. This is because the decisions have to be performed in a small amount of time using only currently available incomplete information. In such cases dispatching rules (DRs) are the most commonly used methods. Since designing them manually is a difficult task, this process has been successfully automatised by using genetic programming (GP). The quality of the evolved rules depends on the problem instances that are used during the training process. Previous studies demonstrated that careful selection of problem instances on which the solutions should be evaluated during evolution improves the performance of the generated rules. This paper examines the application of the ε-lexicase selection to the design of DRs for the unrelated machines scheduling. This selection offers a better solution diversity since the individuals are selected based on a smaller subset of instances, which leads to the creation of DRs that perform well on the selected instances. The experiments demonstrate that this type of selection can significantly improve the results for the Roulette Wheel and Elimination GP variants, while achieving the same performance as the Steady State Tournament GP. Furthermore, the ε-lexicase based algorithms have a better convergence rate, which means that the increased diversity in the population has a positive effect on the evolution process.

Substitution boxes (S-boxes) are nonlinear mappings that represent one of the core parts of many cryptographic algorithms (ciphers). If S-box does not possess good properties, a cipher would be susceptible to attacks. To design suitable S-boxes, we can use heuristics as it allows significant freedom in the selection of required cryptographic properties. Unfortunately, with heuristics, one is seldom sure how good a trade-off between cryptographic properties is reached or if optimizing for one property optimizes implicitly for another property. In this paper, we consider what is to the best of our knowledge, the most detailed analysis of trade-offs among S-box cryptographic properties. More precisely, we ask questions if one property is optimized, what is the worst possible value for some other property, and what happens if all properties are optimized. Our results show that while it is possible to reach a large variety of possible solutions, optimizing for a certain property would commonly result in good values for other properties. In turn, this suggests that a single-objective approach should be a method of choice unless some precise values for multiple properties are needed.