In practise, it is often desirable to provide the decision-maker with a rich set of diverse solutions of decent quality instead of just a single solution. In this paper we study evolutionary diversity optimization for the knapsack problem (KP). Our goal is to evolve a population of solutions that all have a profit of at least (1 - ε) · OPT, where OPT is the value of an optimal solution. Furthermore, they should differ in structure with respect to an entropy-based diversity measure. To this end we propose a simple (μ + 1)-EA with initial approximate solutions calculated by a well-known FPTAS for the KP. We investigate the effect of different standard mutation operators and introduce biased mutation and crossover which puts strong probability on flipping bits of low and/or high frequency within the population. An experimental study on different instances and settings shows that the proposed mutation operators in most cases perform slightly inferior in the long term, but show strong benefits if the number of function evaluations is severely limited.

In the last few decades, evolutionary algorithms were successfully applied numerous times for creating Boolean functions with good cryptographic properties. Still, the applicability of such approaches was always limited as the cryptographic community knows how to construct suitable Boolean functions with deterministic algebraic constructions. Thus, evolutionary results so far helped to increase the confidence that evolutionary techniques have a role in cryptography, but at the same time, the results themselves were seldom used.

This paper considers a novel problem using evolutionary algorithms to improve Boolean functions obtained through algebraic constructions. To this end, we consider a recent generalization of Hidden Weight Boolean Function construction, and we show that evolutionary algorithms can significantly improve the cryptographic properties of the functions. Our results show that the genetic algorithm performs by far the best of all the considered algorithms and improves the nonlinearity property in all Boolean function sizes. As there are no known algebraic techniques to reach the same goal, we consider this application a step forward in accepting evolutionary algorithms as a powerful tool in the cryptography domain.

Generating diverse populations of high quality solutions has gained interest as a promising extension to the traditional optimization tasks. We contribute to this line of research by studying evolutionary diversity optimization for two of the most prominent permutation problems, namely the Traveling Salesperson Problem (TSP) and Quadratic Assignment Problem (QAP). We explore the worst-case performance of a simple mutation-only evolutionary algorithm with different mutation operators, using an established diversity measure. Theoretical results show most mutation operators for both problems ensure production of maximally diverse populations of sufficiently small size within cubic expected run-time. We perform experiments on QAPLIB instances in unconstrained and constrained settings, and reveal much more optimistic practical performances. Our results should serve as a baseline for future studies.

We propose a novel surrogate-assisted Evolutionary Algorithm for solving expensive combinatorial optimization problems. We integrate a surrogate model, which is used for fitness value estimation, into a state-of-the-art P3-like variant of the Gene-Pool Optimal Mixing Algorithm (GOMEA) and adapt the resulting algorithm for solving non-binary combinatorial problems. We test the proposed algorithm on an ensemble learning problem. Ensembling several models is a common Machine Learning technique to achieve better performance. We consider ensembles of several models trained on disjoint subsets of a dataset. Finding the best dataset partitioning is naturally a combinatorial non-binary optimization problem. Fitness function evaluations can be extremely expensive if complex models, such as Deep Neural Networks, are used as learners in an ensemble. Therefore, the number of fitness function evaluations is typically limited, necessitating expensive optimization techniques. In our experiments we use five classification datasets from the OpenML-CC18 benchmark and Support-vector Machines as learners in an ensemble. The proposed algorithm demonstrates better performance than alternative approaches, including Bayesian optimization algorithms. It manages to find better solutions using just several thousand fitness function evaluations for an ensemble learning problem with up to 500 variables.

Symbolic regression aims to hypothesize a functional relationship involving explanatory variables and one or more dependent variables, based on examples of the desired input-output behavior. Genetic programming is a meta-heuristic commonly used in the literature to achieve this goal. Even though Symbolic Regression is sometimes associated with the potential of generating interpretable expressions, there is no guarantee that the returned function will not contain complicated constructs or even bloat. The Interaction-Transformation (IT) representation was recently proposed to alleviate this issue by constraining the search space to expressions following a simple and comprehensive pattern. In this paper, we resort to Simulated Annealing to search for a symbolic expression using the IT representation. Simulated Annealing exhibits an intrinsic ability to escape from poor local minima, which is demonstrated here to yield competitive results, particularly in terms of generalization, when compared with state-of-the-art Symbolic Regression techniques, that depend on population-based meta-heuristics, and committees of learning machines.

Computing diverse sets of high-quality solutions has gained increasing attention among the evolutionary computation community in recent years. It allows practitioners to choose from a set of high-quality alternatives. In this paper, we employ a population diversity measure, called the high-order entropy measure, in an evolutionary algorithm to compute a diverse set of high-quality solutions for the Traveling Salesperson Problem. In contrast to previous studies, our approach allows diversifying segments of tours containing several edges based on the entropy measure. We examine the resulting evolutionary diversity optimisation approach precisely in terms of the final set of solutions and theoretical properties. Experimental results show significant improvements compared to a recently proposed edge-based diversity optimisation approach when working with a large population of solutions or long segments.

Problem decomposition is an important part of many state-of-the-art Evolutionary Algorithms (EAs). The quality of the decomposition may be decisive for the EA effectiveness and efficiency. Therefore, in this paper, we focus on the recent proposition of Linkage Learning based on Local Optimization (3LO). 3LO is an empirical linkage learning (ELL) technique and is proven never to report the false linkage. False linkage is one of the possible linkage defects and occurs when linkage marks two independent genes as a dependent. Although thanks to the problem decomposition quality, the use of 3LO may lead to excellent results, its main disadvantage is its high computational cost. This disadvantage makes 3LO not applicable to state-of-the-art EAs that originally employed Statistical-based Linkage Learning (SLL) and frequently update the linkage information. Therefore, we propose the Direct Linkage Empirical Discovery technique (DLED) that preserves 3LO advantages, reduces its costs, and we prove that it is precise in recognizing the direct linkage. The concept of direct linkage, which we identify in this paper, is related to the quality of the decomposition of overlapping problems. The results show that incorporating DLED in three significantly different state-of-the-art EAs may lead to promising results.

In this paper we address the Euclidean Steiner tree problem in the plane in the presence of soft and solid polygonal obstacles. The Euclidean Steiner tree problem is a well-known NP-hard problem with different applications in network design. Given a set of terminal nodes in the plane the aim is to find a shortest-length interconnection of the terminals allowing further nodes, so-called Steiner points, to be added. In many real-life scenarios there are further constraints that need to be considered. Regions in the plane that cannot be traversed or can only be traversed at a higher cost can be approximated by polygonal areas that either need to be avoided (solid obstacles) or come with a higher cost of traversing (soft obstacles). We propose a genetic algorithm that uses problem-specific representation and operators to solve this problem and show that the algorithm can solve various test scenarios of different sizes. The presented approach appears to outperform current heuristic approaches for the Steiner tree problem with soft obstacles and was evaluated on larger test instances as well.

Partition crossover (PX) is an efficient recombination operator for gray-box optimization. PX is applied in problems where the objective function can be written as a sum of subfunctions f_l(.). In PX, the variable interaction graph (VIG) is decomposed by removing vertices with common variables. Parent variables are inherited together during recombination if they are part of the same connected recombining component of the decomposed VIG. A new way of generating the recombination graph is proposed here. The VIG is decomposed by removing edges associated with subfunctions f_l(.) that have similar evaluation for combinations of variables inherited from the parents. By doing so, the partial evaluations of f_l(.) are taken into account when decomposing the VIG. This allows the use of partition crossover in continuous optimization. Results of experiments where local optima are recombined indicate that more recombining components are found. When the proposed epsilon-PX (ePX) is compared with other recombination operators in Genetic Algorithms and Differential Evolution, better performance is obtained when the epistasis degree is low.

A parallel ensemble of Genetic Algorithms for the Traveling Salesman Problem (TSP) is proposed. Different TSP solvers perform efficiently on different instance types. However, finding the best solver for all instances is challenging. A hybrid of the Mixing Genetic Algorithm (MGA) and Edge Assembly Crossover (EAX) has been shown to perform well on hard instances. The MGA uses Generalized Partition Crossover (GPX) to find the best and worst out of 2^k possible solutions, where k is a decomposition factor of two-parent tours. MGA mixes the edges without any loss of diversity in the population. The best individuals move to the top of the population. The worst individuals are filtered to the bottom of the population. Previously, MGA was applied to TSP instances with less than 4,500 vertices. In this article, various Island Model implementations of MGA are introduced to handle larger problem sizes. The island model uses two mixing policies - migration, which does not lose diversity, and replacement, which loses some population diversity. The islands are configured in two patterns - a ring and a hypercube. An ensemble running multiple versions of an hybrid of MGA and EAX algorithms yields excellent performance for problems as large as 85,900.

In Evolutionary Computation, it is informative to ask what happens when well known benchmarks and bit representations are transformed into quadratic pseudo-Boolean optimization problems. Such transforms are commonly used in quantum computing in order to reduce nonlinearity to k-bounded interactions. First we show that Gray code representations are transformed into linear encodings with quadratic constraints. Next we look at Long Path problems which are constructed so that bit flip local search requires exponential time to converge to a global or local optimum. We show that Long Path problems are similar to reflected Gray codes in both construction and complexity. Finally, a basic form of the "Needle in a haystack" problem is transformed into a problem that can be optimally solved in linear time.