The Importance of Proper Diversity Management in Evolutionary Algorithms for Combinatorial Optimization

Abstract

Premature convergence is one of the most important recurrent drawbacks of Evolutionary Algorithms and other metaheuristics. As a result, several methods to alleviate this problem have been devised. One alternative is to explicitly control the diversity of the population. In this chapter, a recently proposed survivor selection strategy is incorporated into a memetic algorithm and analyzed using three different combinatorial optimization problems. This strategy is based on adopting multi-objective concepts for solving single-objective problems by considering the contribution to diversity as an explicit objective. Additionally, it incorporates the principle of adapting the balance between exploration and exploitation to the different stages of the optimization by taking into account the stopping criterion and elapsed time. These new methods provide important benefits when compared to more mature methods that rely on different principles to delay convergence of the population. Additionally, new best-known solutions are generated for several instances of the problems, thus providing proofs of the considerable benefits and robustness yielded by the schemes that incorporate this novel replacement strategy.

1 Introduction

Evolutionary Algorithms (eas) are probably the most widely used population-based metaheuristics, having been successfully applied to many different problems [12] and in many different fields of optimization, such as in multi-objective optimization [8], combinatorial optimization [9] and continuous optimization [53]. In spite of the large number of different areas where they have been applied, designing a proper ea usually involves many difficult design decisions [5]. Many efforts have been made and advances achieved to automate the creation of components and selection of parameters of eas with the aim of facilitating their design [26]. However, applying these approaches to automatically design state of the art schemes with ad-hoc operators suitable to the problems at hand is not yet a reality. Among the difficulties that the designers of eas might encounter, the appearance of premature convergence is probably one of the most frequent drawbacks [10]. Premature convergence arises when all the population members are located in a small region of the search space that differs from the region containing the optimal solution, and the genetic operators and components included in the ea do not allow escaping from this region. Thus, it is closely related to the management of diversity in the population. In fact, many studies have shown that maintaining a diverse population offers a way to alleviate the problems related to premature convergence [10]. However, a population that is too diverse might prevent exploitation, resulting in poor-quality solutions. For this reason, Mahfoud coined the concept of useful diversity [31] to refer to those amounts of diversity that result in proper solutions.

In the literature, several different ways of alleviating the problem of premature convergence have been devised [40]. In the 90s, most proposals for alleviating premature convergence were focused on modifying the parent selection scheme. The reason is that at the time, most of the schemes were generational methods, so the main source of selection pressure was the parent selection. However, it was soon discovered that trying to alleviate this drawback by only taking into account parent selection was not enough [4]. In subsequent years, most eas incorporated the use of a replacement phase that abandoned, at least partially, the initial generational replacement methods. Many authors discovered the possibility of incorporating methods to alleviate the premature convergence problem into this phase [10]. Note that, even when the generational replacement methods were more popular, some authors had already taken this choice into account [30]. However, with the popularization of elitism and other kinds of replacement strategies, the number of schemes that adopted these principles grew enormously [27, 35, 54].

One important aspect of premature convergence is that it completely depends on the amount of time and/or generations that is granted to the executions of the ea, i.e. its stopping criterion. For instance, a specific ea might be executed to solve a given problem for one hour and it might yield promising results. However, when executed for 24 h, it might converge prematurely after 4 h, for instance, and then the results would not be as good as expected for such a long execution. While the above discussion is quite logical and not too surprising, it is perhaps more surprising that most of the methods that have been proposed to alleviate the premature convergence drawback do not take into account the stopping criterion set by the user to alter their internal operation. This means that, depending on the stopping criterion, different parametrizations might be required. As a result, for each different stopping criterion, the user must study the effect of the different parameters and tune them accordingly. An example of this is the Restricted Tournament Selection [14] (rts) method, which is one of the most popular methods to delay the convergence of eas. It incorporates a parameter that can be used to alter the balance between exploration and intensification. However, the loss of diversity, and consequently the balance between exploration and exploitation, does not depend solely on this parameter, meaning that each problem requires an analysis of the implications of using different parametrizations, and that different parameter values should be used for each problem and for each stopping criterion.

The basic principle of the the diversity-preservation techniques that affect the replacement phase is that by diversifying the survivors, more exploration can be induced. The reason for this is two-fold. First, if the diversity of a given population is large, it means that several regions of the search space are maintained. Second, most crossover operators tend to be more explorative when distant individuals are involved [13]. However, the most popular proposals that try to maintain proper diversity by altering the replacement phase do not take into account the stopping criterion set by the user, which is an important drawback. In fact, to our knowledge, our recent proposal [52] (multi_dyn) is the first replacement strategy designed to alleviate the premature convergence drawback by taking into account the stopping criterion and elapsed time or generations to select the survivors of the population. Note that the principle of relating survivor selection to the stopping criterion can be done in several ways. Thus, one of the aims behind the development of multi_dyn is to show that using this principle is helpful and can yield quite important benefits. Specifically, multi_dyn combines the idea of transforming a single-objective problem into a multi-objective one by considering diversity as an explicit objective, with the idea of adapting the balance induced between exploration and exploitation to the various optimization stages.

In this chapter, this novel method and some other more mature schemes are incorporated into a memetic algorithm following a common framework, and they are tested on three complex combinatorial optimization problems. The main aim of this paper is to show the generality and robustness of multi_dyn. This is done by incorporating this method into this common framework and testing it with three different problems. The first one is the Sudoku, which is an NP-Complete problem [56] that has been recently used extensively as a way of measuring the abilities of different optimization frameworks [7, 25]. Second, the results for a two-dimensional packing problem (2dpp) that was proposed in a contest at the Genetic and Evolutionary Computation Conference are also shown.¹ Note that this was the only problem used in [52]. In this chapter, the experimentation is extended with the aim of further improving the results obtained and to better validate our scheme against other variants. Finally, a variant of the Frequency Assignment Problem [22] (fap), which is known to be an NP-hard optimization problem, is also considered. While the main contribution is to show the robustness and generality of multi_dyn, the state of the art in the application of metaheuristics to the problems addressed in this chapter is also improved upon. In fact, new best-known solutions are attained for some well-known instances of these problems. Particularly, since a large number of different methods have been proposed in the case of the fap, further improving the results obtained for publicly available instances is quite a remarkable achievement.

This chapter is organized as follows. Section 2 presents a summary of the methods designed to alleviate the premature convergence drawback in eas. Our novel replacement strategy is discussed in Sect. 3. A memetic algorithm that is used to test several ways of delaying the convergence of the population, is presented in Sect. 4. In this last section, the mathematical definition of the three problems tested, as well as the way of integrating them with the memetic algorithm, is also provided. Section 5 is devoted to our experimental validation. Finally, our conclusions and future work are presented in Sect. 6.

2 Control of Premature Convergence in Evolutionary Algorithms

Premature convergence is one of the most typical issues that appears in the application of eas to complex problems. This has resulted in a large number of techniques being devised to deal with this drawback [40]. In this section, a brief introduction to the most popular schemes is given. In order to classify the different proposals, a taxonomy was proposed in [10]. The methods are classified in base of the component of the ea that they modify. Some of the most popular schemes fall into the following categories: selection-based, population-based, crossover/mutation-based, fitness-based, and replacement-based. These schemes modify the parent selection, the population model, the variation phase, the way of establishing the individual’s fitness, and the replacement strategy respectively. Additionally, schemes are referred to as uniprocess-driven approaches when a single component is modified, whereas the term multiprocess-driven is used to refer to those schemes that act over more than one component. In this section, some of the most popular general techniques designed for addressing premature convergence are reviewed and the components that are modified are specified. Many of these schemes are used to show the benefits of the novel proposals presented in this chapter. In such cases, some additional details such as the parameters required by them are specified. The reader is referred to [10, 40] and to the original papers of each scheme for further details.

Most of the initial approaches were selection-based schemes based on explicitly controlling the selection pressure of the parent selection phase [12]. However, it was found both theoretically and experimentally that these kinds of schemes were not able to preserve diversity in the long term, meaning additional measures were required for the most complex problems [4]. Thus, currently when these schemes are used, they are usually combined with other strategies that rely on additional mechanisms to delay convergence.

The population-based schemes alter the panmictic population model of typical eas. eas with structured populations, such as the island-based model or the cellular schemes, have gained popularity in recent years [2]. In these schemes, individuals can only by recombined with a subset of the population. Most of these schemes were proposed as a mean of parallelizing metaheuristics [2]. However, practitioners soon discovered that structured populations have important implications on the way of managing the diversity. Specifically, since the amount of interactions between individuals are diminished, the convergence is usually delayed. Methods based on the infusion technique are also quite popular approaches categorized as population-based. In these schemes some new individuals are inserted in the population when some conditions appear. For instance, a partial restart of the population might me done after a fixed period or when some event related to the loss of diversity occur [11]. The saw-tooth genetic algorithm (saw-tooth ga) [20] is a popular scheme that applies this principle. Specifically, this scheme uses a variable population size and periodic partial reinitialization of the population in the shape of a saw-tooth function. In order to adapt the scheme to the particular needs of the problem, two different parameters are used: the period (P) and the amplitude (D) of a saw-tooth function. This function is used to manage the dynamic population size and to trigger the partial reinitializations.

In the group of the crossover/mutation-based schemes, the approaches that impose some mating restrictions are one of the most popular [25]. These schemes follow some principles that are quite similar to those applied in the island-based schemes. Specifically, some restrictions on the interactions between individuals are also imposed. However, in these cases, the features of the individuals that are taken into account to establish the restrictions differ from those used in the structured populations. For instance, in the cross generational elitist selection, Heterogeneous recombination, Cataclysmic mutation scheme (chc), the recombination of too close individuals is avoided. Note that chc includes additional modifications, such as the use of a highly disruptive crossover operator and the a reinitialization process through the application of special mutation. Finally, in other cases the variation stage is modified with the aim of better controlling the balance between exploration and exploitation in a problem-specific way. For instance, in [42] several complementary genetic operators are considered simultaneously in an effort to adapt the variation phase to the needs of the different optimization stages. However, since this kind of control depends on the problem, on the features of the genetic operators and on the stopping criterion set by the user, adapting this scheme to different problems is a complex task.

In the fitness-based schemes, the way of calculating the fitness of each individual is altered. Probably, the fitness sharing scheme is the most popular proposal of this group. Fitness sharing reduces the fitness of individuals placed in densely populated regions. Specifically, the fitness of each individual is normalized depending on the number of individuals in its region, which is defined via the parameter $\sigma$. Thus, the fitness of any individual is affected by any other individual whose distance is not larger than $\sigma$. The clearing strategy (clr) [41] is as an extension of fitness sharing and it alters both the fitness assignment procedure and the replacement selection phase. In the clearing procedure the individuals are grouped into niches—defined via the parameter $\sigma$—and the resources of a niche are attributed to the best W elements in each niche. Moreover, the winners of each niche are copied to the next population, so the best members of the selected regions are preserved. Note that if too many niches are detected, this might lead to large immobilization of the population. As a result, Petrowsky proposed discarding the winners with a fitness lower than the mean [41], which is the alternative used in this chapter. Note that the clearing procedure is categorized as a fitness-based scheme in [10]. However, since it also affects the replacement phase it might be categorized as a multiprocess-driven hybrid method. Finally, methods based on multiobjectivization [19, 51] use simultaneously several fitness functions. In some cases, one of the fitness function is the original one that must be optimized. However, decomposing the original function in several functions, and using each of them as a fitness function to optimize is also a plausible choice.

Finally, since the appearance of elitism and with the popularization of the inclusion of a replacement phase different from the generational replacement, several replacement-based methods have also been devised. The basic principle of these schemes is to induce larger levels of exploration in successive generations by diversifying the survivor of the population [52]. For instance, in crowding the basic principle is that offspring should replace similar individuals from the previous generation. Some of the most popular crowding methods are the following:

• In Mahfoud’s deterministic crowding [30] (detcr), each pair of parents and their corresponding offspring are paired by minimizing the sum of the distances between them. Then, each offspring survives if it is at least as good as the parent.

• Probabilistic crowding [34] (pobcr) operates similarly to detcr but it uses a non-deterministic rule to establish the winner, with each individual’s survival probability being proportional to its fitness value. Scaled variants of probabilistic crowding (spobcr) have also been devised [3].

• In adaptive generalized crowding [35] (agcr) the selection pressure is adapted to the needs of the different stages. Two different mechanisms to adapt the selection pressure were devised: a self-adaptive and an adaptive scheme. In the adaptive scheme the entropy of the population is used to alter the selection pressure. In this chapter, this latter version is the one that we have adopted.

• Restricted Tournament Selection [14] (rts) is a popular steady-state scheme in which after each new individual (C) is created, CF individuals from the current population are selected at random. Then, the best individual between C and its most similar individual in the selected set survives. In case of a tie, the offspring is preserved.

Several replacement strategies that do not rely on the principles of crowding have also been devised. In some methods, diversity maximization is considered as an objective that is combined with the original objective to calculate the fitness of each individual. However, since both objectives measure different things, such a combination is complex and problem-dependent. As a result, other ways of combining them have been proposed. For instance, in comb [54] the individuals are sorted by their contribution to diversity and by their original cost. Then, the rankings of the individuals, instead of the original objective values, are used to calculate a score using two parameters ($N_{Close}$ and $N_{Elite}$). In each step of the replacement phase, the individual with the lowest score is erased and the ranks are recalculated. This process is repeated until the desired population size is reached. The contribution-diversity replace-worst method [27] (cd/rw) also uses diversity but in a different way. cd/rw is a steady-state ea in which a new individual enters the population by replacing another one that is worse both in diversity contribution and quality. If such an individual does not exist, the replace-worst strategy (rw) is applied, i.e., the best individuals are preserved. Finally, using concepts that arise in the field of multi-objective optimization to consider both the original objective and the diversity contribution of each individual is also a plausible choice [6, 39]. In these kinds of schemes, which are usually termed diversity-based multi-objective eas [48], the diversity contribution is referred to as the auxiliary objective. Several variants of these kinds of schemes have been devised. For instance, several different ways of calculating the auxiliary objective have been proposed [51]. Among them, one of the most popular is probably the distance to the closest neighbor (dcn) metric [6], which is used in the extensions applied in this chapter. In dcn, the auxiliary objective of a given individual is calculated as its distance to the closest member in a reference set. Note that this principle can be used to modify several components of the eas. A uniprocess-driven replacement-based approach (multi) based in these principles is proposed in [49].

3 A Novel Diversity-Based Replacement Strategy

The multi_dyn replacement strategy analyzed in this chapter is an extension of the strategy presented in [49] (multi). The multi replacement strategy (Algorithm 1) operates as follows. First, the population of the previous generation and the offspring are joined. Then, the best individual—taking into account the original objective value—is selected to survive. Then, until the new population is filled with N individuals, the following steps are executed. First, each individual’s contribution to diversity is calculated. The reference set used in this calculation is the set of already selected individuals, i.e., for each pending individual, the distance to the nearest survivor already selected is taken into account. Then, considering the individuals that have not been selected, the non-dominated front is calculated. Finally, a non-dominated individual is selected at random to survive. The two most expensive steps in each iteration of the survivor selection scheme are the identification of the non-dominated individuals and the calculation of dcn. The non-dominated individuals can be identified in O(N log N), whereas the calculation of dcn depends on the problem. In each step the reference set consists of an additional individual, meaning that in each step O(N) distances are calculated. The complexity associated with calculating the distance metric depends on how the metric is defined, but in our cases they are O(V), where V is the number of variables. Since N steps are done in each generation, the complexity of the survivor selection scheme is $O(VN^2 + N^2 log N)$. Finally, we would like to remark that in every problem considered in this chapter, the time associated with the replacement phase is negligible. In every case, the much more expensive local search integrated in our schemes consumes the majority of the time.

The proposal used in this chapter (multi_dyn) [52]—see Algorithm 2—extends the multi strategy by adapting the balance between exploration and exploitation to the different optimization stages. In order to effect this adaptation, the stopping criterion, as well as the elapsed time, are used as inputs to the replacement strategy. Specifically, for shorter stopping criteria the method induces a faster reduction in diversity than for longer stopping criteria. The adaption is done by defining a dynamic penalty approach that is independent of the scale of the original objective. In this way, the effort required to adapt multi_dyn to different problems is highly reduced.

Fig. 1

Effect of the penalty approach with distance D

One of the keys behind the development of multi_dyn is that individuals that contribute too little to diversity should not survive regardless of their original objective value. In our approach, this principle is realized by setting the original objective of individuals that contribute too little to diversity to a very low quality value. For instance, in a minimization function the maximum number that can be represented in the data type associated with the objective function might be used, whereas in a maximization function, the minimum representable number might be considered. This is illustrated in Fig. 1. In this figure, the value D represents the minimum dcn required to avoid the penalty. Any individual whose dcn value is lower than D is penalized. As a result, the non-domination rank (shown at the left of each individual) of the penalized individuals might increase. Obviously, the penalized individuals will not belong to the non-dominated front so they will not survive, unless every pending individual has been penalized. Note that the computational complexity of the survivor selection strategy does not change due to the inclusion of the penalty method.

While the above approach is quite sensible, one of the key choices is how to set the value D. Taking into account the benefits that can be attained by adapting the balance between exploration and exploitation to the needs of the different stages of the optimization, it is clear that the value of D should vary during the optimization process. Specifically, this value should decrease as the stopping criterion is approached with the aim of inducing a higher degree of intensification. In our scheme, an initial $D_I$ value must be selected by the user. Then, a linear reduction of D is carried out in such a way that by the end of the execution, the resulting value is 0. In this chapter, the stopping criterion is set by time. Thus, if $T_{End}$ is the stopping criterion and $T_{Elapsed}$ the elapsed time, D can be calculated with (1). Note that some more complex ways of setting D have also been tested [52]; however, these methods are more complex to use and they do not provide important benefits, so the linear reduction is used in this chapter.

$$\begin{aligned} D = D_I - D_I * {{T_{Elapsed}}\over {T_{End}}} \end{aligned}$$

(1)

4 Proposals

We used a common framework to address the three different optimization problems covered in this chapter. In every problem considered, it is clear that incorporating some intensification mechanisms is quite useful. For instance, in the case of the competition of the 2dpp problem, the best three schemes used memetic algorithms, whereas the surveys provided in [29, 47] show that most of the promising schemes for the fap combine population-based and trajectory-based optimization. Additionally, in the case of Sudoku, some of the most promising schemes are also hybrid approaches [32, 43] that combine a global search with some specific mechanisms to induce additional intensification. As a result, in this chapter a memetic algorithm is used. Algorithm 3 shows the approach applied. Note that it is a fairly standard memetic algorithm, where the local search is incorporated after each individual is created, i.e. in the creation of the initial population and after the variation stage. Specifically, the local search is applied to all the offspring. Note that some schemes to balance the resources granted to the genetic and local searches have been devised [16]. In these cases, a local search is usually applied to a subset of individuals or only in some generations. For instance, one typical approach is to apply a local search to the best individuals with higher probabilities. This goes against some of the principles of our scheme since, due to the way in which the replacement is carried out, any individual kept in the population is promising, so it is important to intensify in every region that is maintained; otherwise, some regions might be abandoned prematurely. In any case, we conducted some experiments by trying to incorporate some of these ideas, but they were unsuccessful.

Note that in the problems at hand, our local search is always a stochastic hill, i.e. the neighbors of a given candidate solution are considered in a random order and only improvement movements are accepted. The local search continues until a local optimum is reached. Note that some more complex trajectory-based metaheuristics, such as tabu search or simulated annealing, can be incorporated in this step. While these schemes are promising, they are more expensive because they do not finish when a local optimum is found. Thus, more complex mechanisms for specifying the resources granted to global and local searches should be included. As a result, the application of these schemes is left for future work.

In order to test different ways of alleviating the problems associated with premature convergence, several schemes are included in Algorithm 3. In all of the problems tested, a variant that applies the multi_dyn scheme is considered, i.e. multi_dyn is selected as the survivor selection scheme. Depending on each problem, other schemes are also incorporated. The set of schemes applied and their corresponding parametrizations are given in Sect. 5 for each problem.

In order to properly adapt the previous framework to a given problem, the following components are required. First, the representation of the individuals and an associated distance metric must be given. Second, the objective function used to evaluate each individual must be established. Third, the variation stage, i.e. the crossover and mutation operators, must be selected. Finally, the neighborhood must be defined. In the following sections, we describe the components selected for each of the problems addressed in this chapter.

4.1 Sudoku

4.1.1 Problem Definition

The Sudoku puzzle is a popular logic puzzle consisting of an $N^2 \times N^2$ grid that is subdivided into $N^2$ blocks of size $N \times N$. An initial board with numbers in some cells is given and the objective is to fill the remaining cells with digits from 1 to $N^2$ such that each block, row and column can contain only one instance of each digit. The most popular variant of Sudoku involves a $9 \times 9$ grid. The reason to use so small grids is probably that since this problem is NP-Complete [56], large grids might be too complicated to be solved by hand.

In recent years, Sudoku has been widely used to test the abilities and performance of different optimization frameworks. For instance, the most popular metaheuristics have been applied to Sudoku solving [7, 17, 37]. In the particular case of eas, their basic variants can only solve simple Sudoku puzzles [33], as they face significant issues when tackling more difficult puzzles. In fact, even with the incorporation of more complex components some of these issues also appear [25, 38, 55]. In order to alleviate these drawbacks, hybrid variants and ad-hoc genetic operators have been proposed [32]. Thus, most efforts have focused on incorporating problem-specific knowledge into the design of eas. However, as the experimental validation in this chapter shows, successful simpler eas that do not incorporate ad-hoc knowledge can be designed by properly managing diversity.

4.1.2 Selected Components

In the case of the Sudoku problem, we have selected very straightforward components. One of the most popular representations is used [33]; specifically, an individual consists of a set of sub-chromosomes, each of which is a permutation of the numbers absent in a block. Thus, the constraints associated with the numbers given in the initial board and with the blocks are fulfilled by any individual. The fitness function is calculated as the sum of two terms: the first one is the number of repetitions that appear in the rows and columns; the second one is the number of conflicts with the numbers given in the initial board multiplied by 100. In the case of the distance metric, the Hamming distance is applied, i.e. the distance between two individuals is the number of cells that differ.

The variation scheme applies simple mutation and crossover operators. The crossover operator uniformly exchanges complete blocks between solutions [11]. The mutation operator iterates over each gene and performs a swap with another element selected at random from its corresponding sub-chromosome with probability $p_m$ [33]. Note that these operators have only been successful with easy Sudoku puzzles, so they are suitable choices to show that general and simple operators can be successfully applied by properly managing diversity. Finally, a neighbor of a candidate solution is generated by swapping two elements of a block.

4.2 Two-Dimensional Packing Problem

4.2.1 Problem Definition

The two-dimensional packing problem (2dpp) variant used in this chapter was defined in the gecco 2008 competition session. Problem instances are described by the following data:

• The sizes of a rectangular grid: X, Y.

• The maximum number that can be assigned to each grid position: M. The value assigned to each grid location is an integer in the range [0, M].

• The score associated with the appearance of each pair (a, b) where $a, b \in [0, M]$: v(a, b).

A candidate solution is generated by assigning a number to each position on the grid. Thus, the search space consists of ${(M + 1)}^{X \cdot Y}$ candidate solutions. The objective of the problem is to pack a grid so that the sum of the point scores for every pair of adjacent numbers is maximized. Two positions are considered to be adjacent if they are neighbors in the same diagonal, row, or column of the grid. A pair cannot be collected more than once. Mathematically, the objective is to find the grid G which maximizes the objective function f:

$$\begin{aligned} f = \displaystyle \sum _{a=0}^{M}{\displaystyle \sum _{b=0}^{M}{v_2(a, b)}} \end{aligned}$$

(2)

where

$$\begin{aligned} \ \ \ v_2(a, b) = \left\{ \begin{array}{ll} 0\ &{}\quad if\ (a, b)\ are\ not\ adjacent\ in\ G\\ v(a, b) &{}\quad if\ (a, b)\ are\ adjacent\ in\ G \end{array} \right. \end{aligned}$$

(3)

Fig. 2

Assignment of the original objective function for the 2DPP

Figure 2 illustrates the assignment of the objective function of a candidate solution for a $2 \times 2$ grid. Note that although the pairs (1, 2) and (2, 1) are repeated in the grid, they are only considered once.

One of the reasons for selecting the 2dpp is that this problem was tackled by several research groups during the competition. In the competition, the best results were reported by using memetic algorithms [18, 23], results that could be further improved by taking into account the diversity of the population [44, 46]. The current best result for this problem is offered by the multi_dyn scheme [52]. The initial results obtained in [52] are extended in this chapter and new best-known solutions are found for the largest instances.

4.2.2 Selected Components

In our proposal, candidate solutions are encoded using a two-dimensional chromosome. Specifically, there are as many genes as there are cells in the grid, and each gene can take a value in the range [0, M]. A brief description of the variation operators and the definition of the neighborhood are attached. For a more comprehensive description, readers are referred to [23]. The variation stage is based on the application of crossover and mutation. Crossover is applied with probability $p_c$ and two different parameters ($min\_p_m$ and $max\_p_m$) are used to control the mutation. The crossover operator is the 2D Sub-String Crossover (ssx) [15], which is an extension of one-point crossover for two-dimensional chromosomes. The mutation operator applied is the Uniform Mutation with Domain Information (umd). First, a random number ($ap_m$) between $min\_p_m$ and $max\_p_m$ is generated. Then, each gene is mutated with a probability $ap_m$. In order to make new assignments, a random value is selected from among those that increase the objective value. If such a value does not exist, a random value between 0 and M is used.

In our proposal, Hamming distances are used to calculate the dcn value. As a result, the most distant individuals are at a distance equal to $X \times Y$. Taking this into account, relating the value of $D_I$ to the number of genes (G) seems appropriate. Particularly, in this chapter the value of $D_I$ is set to a percentage ($R_I \times 100$) of G.

The definition of neighborhood applied considers a new neighbor for each pair of adjacent grid positions (i, j) and (k, l). Each neighbor is generated by assigning the best possible values to the positions (i, j) and (k, l) while keeping intact the values in all other grid locations. A pruning procedure is applied so as to efficiently assign the best values to both locations. Finally, the fitness function is the score associated to each candidate solution, which is evaluated with Eq. (2)

4.3 Frequency Assignment Problem

4.3.1 Problem Definition

The Frequency Assignment Problem (fap) is a very popular NP-hard combinatorial optimization problem with practical applications that emerges in the deployment of networks in different environments. The fap involves different objectives, features, and constraints. This has resulted in quite a large number of different mathematical formulations being defined [1]. In recent years, the basic fap formulation has been widely expanded in order to address real-world issues [21]. For this chapter, we selected a commonly applied definition and used some popular instances inspired on realistic global system for mobile communications (gsm) networks [36]. In this definition, an instance is given by a set of transmitters, a set of constraints and the number of admissible channels. The constraints define the minimum distance allowed between the channels assigned to pairs of transmitters. When a given constraint is violated, a given penalty term associated with each constraint is added to the cost function. The objective of the problem is to find a complete assignment that minimizes this cost function.

Several different meta-heuristics have been applied to the fap [28]. Initially, in the case of the instances tackled in this chapter, some methods based on a tabu search yielded promising results [36]. Currently, the best reported results have been obtained using path relinking [22]. This successful variant of path relinking incorporates a special mechanism to preserve the population diversity.

4.3.2 Selected Components

In this problem we use a straightforward representation of candidate solutions. Specifically, the number of genes in the chromosomes is equal to the number of transmitters, and each one represents the channel assigned to a transmitter. As in previous cases, the Hamming distance was used to calculate the distance between individuals. Finally, the fitness function is just the cost associated with each candidate solution, i.e. the sum of the penalties associated with the constraints that are violated.

The genetic operators are more complex because they are ad-hoc operators for the fap. Specifically, they are extensions of the ones that were proposed in [45] for a different variant of the fap. The crossover is the Multi-Interference-based Crossover, which operates as follows. First, a transmitter t is selected at random. Then, every gene associated with a transmitter that interferes with t, including the gene that represents t, is marked. This process is repeated a number of times that is selected randomly between one and a number set by the user (R), which in this chapter is eight. However, in the subsequent iterations, instead of selecting t at random from the complete set of transmitters, it is selected, without repetition, from those that were previously marked. Finally, the parents swap the channels assigned to the transmitters that were marked to generate the offspring. The mutation operator is the Neighborhood-based Mutation. First, a transmitter t is selected randomly and it is mutated. Then, the transmitters that interfere with t are mutated with a probability $p_m$. The above step is repeated R times, but in the subsequent iterations the transceiver is randomly selected from among those that interfere with transmitters mutated in previous iterations. Thus, similarly to the crossover operator, the mutation scheme focuses on altering subsets of transmitters affected by common constraints.

Finally, a simple definition of neighborhood is used. A neighbor of a candidate solution is generated by reassigning the channel of two transmitters that might potentially have interference between them, while leaving intact the assignments of the remaining ones.

5 Experimental Validation

In this section we describe the experiments conducted with our memetic algorithm for the three different optimization problems considered, and discuss the results obtained by using a diverse set of methods to control convergence. In every problem, the memetic algorithm with the multi_dyn scheme is applied. Additionally, some of the more mature schemes described above are also tested. A subsection is included for each of the problems and in each case, the parametrizations and methods used in the comparisons are detailed.

The optimization schemes were implemented in metco (Metaheuristic-based Extensible Tool for Cooperative Optimization) [24]. The experiments were run on dual processor machines with 32Gb RAM. Since the algorithms considered in this study are stochastic, each execution was repeated 30 times. In order to compare the results (fitness and speed), a series of statistical tests that relied on a guideline similar to that applied in [52] was conducted. Specifically, the following tests were applied, assuming a significance level of 5 %. First, a Shapiro–Wilk test was applied to check whether or not the results followed a Gaussian distribution. If they did, the Levene test was used to check for the homogeneity of the variances. If the samples had equal variance, an anova test was done; if not, a Welch test was performed. For non-Gaussian distributions, the non-parametric Kruskal–Wallis test was used to test whether samples were drawn from the same distribution.

5.1 Sudoku

In the case of the Sudoku problem, the analyses were performed with 26 different puzzles.² Twenty puzzles were generated using two of the most popular web pages devoted to Sudoku [57, 58]. In the case of the Sudoku puzzles generated in [58] (tagged as SS), the hard level was used, whereas for the ones generated in [57] (tagged as SW), the evil level was selected. The three puzzles tagged as SD in [43] were also included in our set. Note that one of them is the popular AI-Escargot puzzle. Finally, the last three are now regarded as the most difficult puzzles [59]. Two of them were designed by David Filmer, whereas the last one was proposed by Arto Inkala. Note that in the Sudoku puzzle it makes no sense to compare the fitness values when the problem is not solved, i.e. it is no more valuable to obtain a candidate solution with two conflicts than one with four conflicts. Therefore, our comparisons are done based on the success rate achieved. Since the time factor is also important, the time required to solve the puzzles is also taken into account.

In every variant of our memetic algorithm, typical values for the population size (N), mutation probability ($p_m$) and crossover probability ($p_c$) were selected. Specifically, they were set to 100, 0.01 and 0.8, respectively. Additionally, the stopping criterion was set to 5 min. The following variants were tested for this problem. First, the memetic scheme was tested with two replacement strategies, the generational scheme with elitism (gen_elit) and the replace-worst strategy (rw), which did not include any special mechanism to delay convergence. In gen_elit, the best individual of the population is copied to the next generation while the rest of the population is created with the variation scheme. In rw the offspring and the previous population are joined in a set and the best N individuals survive. Additionally, seven schemes from among those previously discussed, and that incorporate mechanisms to delay convergence, were tested. They are the following: multi_dyn, clr, rts, detcr, saw-tooth GA, comb and cd/rw The parametrization of these methods is shown in Table 1. In order to select the parametrization of each scheme, some initial experiments were done with the last six puzzles selected. The parameter values that maximized the success rate were selected for the final experimentation.

Table 1 Parametrization of the methods applied in the Sudoku Problem

Table 2 Summary of the results obtained by the different tested schemes (5 min)

Table 2 shows the results obtained with each scheme in every puzzle analyzed. Specifically, it shows the success rate (SR) and the time in seconds (T) required to obtain a success rate of at least 50 %. A dash is shown in those cases where the success rate was lower than 50 %. The methods are sorted by the number of successful runs.

It is important to note that the worst schemes were the two methods that did not incorporate any mechanisms to delay convergence, which quite clearly shows the important benefits provided by any of the mechanisms that delay convergence. However, there are important differences in their behaviors. The scheme that provided the highest success rate was the multi_dyn method. The results provided by rts, comb, saw-tooth ga and clr were also quite good. In fact, they only encountered difficulties with SS4 and with the puzzles generated by Arto Inkala and David Filmer. Furthermore, they converged faster than multi_dyn in most cases, so they might be more useful than multi_dyn for the easiest Sudoku puzzles. Some analyses were carried out to compare the times required by multi_dyn and these other schemes. Among them, the best one was clr. The statistical tests confirmed that clr was faster than multi_dyn in 20 Sudoku puzzles, whereas the opposite never happened.

In light of these results and those in Table 2, it is clear that in the less challenging instances, the clr strategy provides important benefits; whereas in the most difficult puzzles, the multi_dyn method is preferred. Note that this behavior also appeared when multi_dyn was applied to the Traveling Salesman Problem [50], where the advantages were clearer when dealing with large-scale and difficult instances. Additionally, we would like to note that all the schemes were also executed by setting the stopping criterion to 30 min with the Filmer1 and Filmer2 puzzles, which are the cases where the eas encountered more difficulties. The only method that was able to obtain a 100 % success rate was multi_dyn, whereas the second best method (rts) obtained a success rate of 90 % with Filmer1 and 70 % with Filmer2. This last experiment also confirms the robustness of the multi_dyn scheme.

5.2 Two-Dimensional Packing Problem

In the case of the 2dpp, the experimentation presented in this chapter is an extension of the one developed in [52]. The most important achievement is that new best-known solutions could be obtained for the most complex instances of this problem. Some new tests that better show the benefits of multi_dyn are also included. Since one of the objectives of this chapter is to demonstrate the robustness of the multi_dyn method and its ability to perform properly in different problems with minor effort, some of the most illustrative results obtained previously for this problem are also shown. The ten instances that were created in [52] are used in our performance evaluation. They were created with a random generator that allows selecting different parameters to alter the difficulty and size of the instances created.

Table 3 Parametrization of the methods applied in the 2dpp Problem

As in the previous problem, in order to prove the proper performance of our memetic algorithm with multi_dyn, an extensive comparison with other more mature methods was carried out. In particular, the following schemes were used: cd/rw, clr, detcr, spobcr, agcr, rts, comb, rw, chc and Saw-Tooth ga. In addition, a generational scheme with elitism (gen_elit) was used. As in previous studies [44], the parameters $p_c$, $min\_p_m$ and $max\_p_m$, which are associated with the genetic operators, were set to 1, 0.1 and 0.15, respectively, while the population size was set to 50. The parametrization of the different methods is included in Table 3. In the methods where several values are used for a specific parameter, these are expressed as comma-separated values, and in order to denote the method with its specific parametrization, the name of the method is followed by the value of the parameter. For instance, clr_5 means that the parameter W is set to 5.

Table 4 Statistical comparison of every considered scheme in 24 h

Fig. 3

Evolution of the mean entropy for all of the schemes considered (gecco instance)

In our first experiment, the memetic algorithm was executed with the above schemes, as well as with the multi_dyn replacement strategy, by setting the stopping criterion to 24 h. The parameter $R_I$ in multi_dyn was set to 0.5. Additionally, the multi scheme was also executed, which is similar to multi_dyn with $R_I$ set to 0. In order to obtain a ranking of the different approaches, pairwise statistical comparisons between the 20 configurations were carried out, meaning that 190 statistical tests were done for each scheme. Table 4 shows, grouped by category, the results of these statistical tests. The groups “small”, “medium” and “large” contain three instances, while the last column (“GECCO”) refers to the instance that was used during the competition to perform the final comparisons. For each category, columns with the symbol $\uparrow$ refer to the number of cases where the model listed in each row is statistically better. The number of cases where it is worse is shown in the column with the symbol $\downarrow$. Finally, the column with the symbol $\leftrightarrow$ denotes the number of cases where the differences are not statistically significant. In addition, a score is assigned to each model that is equal to the number of cases where the model was superior minus the number of cases where the model was inferior. The superiority of the multi_dyn model is quite clear. In fact, it was superior to all the remaining models in every instance.

Fig. 4

Fitness (mean) achieved with fixed D values and with multi_dyn

In order to better understand the reasons for the superiority of multi_dyn, it is important to analyze the diversity induced by the different schemes throughout the optimization process. Figure 3 shows the evolution of the mean entropy for all of the schemes considered in the gecco instance. In the case of chc and Saw-Tooth ga, only one execution was used to acquire the data because the exact times where the restarts are triggered differ for each run, meaning that the mean of several executions is less representative of the behavior of these schemes. multi_dyn is the only model that induces a slow but continuous decrease in the entropy, meaning that it is the only scheme where the balance between exploration and exploitation is altered gradually, as expected.

In order to better show the advantages provided by the linear decrease in D, additional experiments were conducted that consider fixed values of D. Specifically, for each instance, 11 fixed values equidistributed among 0 and the number of variables of the corresponding instance were considered. Figure 4 shows, for four different instances, the mean of the fitness obtained with multi_dyn and with the schemes that consider a fixed D. In multi_dyn, $R_I$ was set to 0.6 in every instance, which proved to be quite a robust value in [52]. The advantages of using a dynamic D are quite clear. In fact, in every instance the mean value attained by multi_dyn is higher than the means obtained with any fixed value of D. Similar analyses were done with the remaining instances and in every case the statistical tests show that the results obtained by multi_dyn are superior. We also note that in the small instances, the differences are not so large. In fact, the p-values obtained when comparing the results of multi_dyn to those output by the best fixed D values are only slightly below 0.05, meaning that the benefits provided by multi_dyn are more important in the most complex instances.

Table 5 Results obtained by multi_dyn in the long-term (3 Days)

In order to see the specific mean and best values obtained by 24 h executions of the multi_dyn scheme, the readers are referred to [52]. Note that while the multi_dyn method provided the currently best-known solution for the ten instances above, it is important to analyze whether larger executions can provide additional benefits. In order to carry out this experiment, the four most complex instances were selected, i.e. the gecco instance and the ones in the large group. In this case, only the multi_dyn scheme was used and the stopping criterion was set to 3 days. Table 5 shows, for each instance, the mean, median and best of the solutions attained. In addition, it also shows the previously attained best-known solution as reported in [52]. In every instance, the best-known results could be improved substantially. For instance, in the gecco instance, the best result could be improved from 1, 039, 822, 096 to 1, 041, 931, 347, which represents a significant advance. This probably means that due to the huge search space of these instances, there is already room for improvement. Considering how the execution times of the runs carried out in this chapter are already quite long, it seems particularly important to develop parallel models capable of managing diversity in a similar way to the sequential case but in parallel environments.

5.3 Frequency Assignment Problem

In the case of the fap, the main objective was to improve all of the results obtained in literature through the application of multi_dyn. Additionally, in order to show that the benefits come from the explicit control of diversity, the gen_elit replacement phase was also used, which is probably the most popular replacement phase. In both schemes the same parametrization was considered. First, the population size, crossover probability and mutation probability were set to 50, 1 and 0.05 respectively. The R parameter, which is used in the mutation operator, was set to eight. Finally, the stopping criterion was set to 48 h. Additionally, in the case of multi_dyn, $D_i$ was set to 0.75 multiplied by the number of transmitters of the considered instance. In this chapter, a subset of the problem instances provided in [36] was used. Specifically, these are the ones whose tags start with gsm2, which are a set of instances that were created with realistic data from gsm networks. The best results obtained so far for these instances were recently compiled in [22].

Table 6 Results obtained by our memetic algorithm with multi_dyn and gen_elit in the gsm2 instances (48 h)

Table 6 shows the results obtained with our memetic algorithm using multi_dyn and gen_elit in the nine gsm2 instances. Specifically, the mean, median and best costs obtained are shown. The table also shows the previously attained best-known solution as reported in [22]. We can see that our memetic algorithm provides quite a significant improvement by applying the multi_dyn replacement strategy. In fact, new best-known frequency plans were obtained in five instances, whereas in the remaining ones, frequency plans with the same cost as the currently best-known solutions were obtained. The cases where the best known solution could be improved upon are shown in boldface. Moreover, the benefits of the multi_dyn scheme are also apparent when compared to the memetic algorithm with the gen_elit replacement strategy. In fact, the statistical tests confirm that the scheme that applies the multi_dyn replacement scheme obtained a superior performance in 7 out of the 9 instances. In the two remaining instances, both schemes attained the best known solution in every run. Thus, as with the results of the previous problems, in the case of the fap, the state of the art in the application of optimizers could be improved substantially, demonstrating once again the robustness and remarkable performance of the methods that incorporate multi_dyn as a way to control premature convergence.

6 Conclusions and Future Work

Premature convergence is one of the most studied drawbacks of eas and other population-based metaheuristics. The appearance of premature convergence and its consequences obviously depend on the specified stopping criterion. Thus, it is quite surprising that most of the methods designed to alleviate this drawback do not take into account the stopping criterion set by the users to bias the decisions made by them. multi_dyn is the first survivor selection strategy proposed that takes into account the stopping criterion and elapsed time to bias its decision with the aim of properly adapting the balance between exploration and exploitation to the needs of the different optimization stages. Specifically, it uses the contribution to diversity as an additional optimization objective and it adopts ideas from multi-objective optimization. Additionally, it uses an adaptive penalty approach to induce a higher degree of exploration in the initial phases and a higher degree of intensification in the final ones.

A fairly standard memetic algorithm is used to test the abilities of multi_dyn by applying it to three different complex optimization problems; namely, the Sudoku puzzles, the 2dpp and a variant of the fap. Note that in order to apply the multi_dyn replacement, the only additional task that the user must carry out is to define a distance metric to calculate the dissimilarity between pairs of individuals. Thus the additional effort required with respect to standard eas is minimal.

The experimental validation carried out with these three problems shows that schemes that apply the multi_dyn survivor selection strategy provide important benefits when compared to more mature methods that have been designed with the aim of delaying the convergence of the population. Furthermore, benefits with respect to some other traditional schemes, such as the gen_elit or rw methods, are even more noticeable. An important additional contribution of this chapter is that the state of the art in the application of metaheuristics to the three problems considered could be substantially improved upon. In the case of the Sudoku, three puzzles regarded as the most difficult ever designed were successfully solved for the first time with an ea. As for the 2dpp and fap, new best-known solutions were obtained for popular instances of these problems.

Several lines of future work might be explored. First, we would like to apply multi_dyn to a larger set of combinatorial problems and adopt similar principles to different fields of optimization, such as continuous optimization and multi-objective optimization. Second, we would like to make some changes to accelerate convergence in easy problems; specifically, adopting some of the ideas from saw-tooth ga to design new replacement phases seems promising. Third, replacing the simple stochastic hill-climbing with more complex trajectory-based metaheuristics seems promising. Finally, in light of the long times required to solve these problems, developing parallel schemes seems quite important. We would like to include the principles of multi_dyn in some coarse-grained models by developing distributed and centralized ways to explicitly manage diversity.