Variable mesh optimization for continuous optimization problems

Abstract

Population-based meta-heuristics are algorithms that can obtain very good results for complex continuous optimization problems in a reduced amount of time. These search algorithms use a population of solutions to maintain an acceptable diversity level during the process, thus their correct distribution is crucial for the search. This paper introduces a new population meta-heuristic called “variable mesh optimization” (VMO), in which the set of nodes (potential solutions) are distributed as a mesh. This mesh is variable, because it evolves to maintain a controlled diversity (avoiding solutions too close to each other) and to guide it to the best solutions (by a mechanism of resampling from current nodes to its best neighbour). This proposal is compared with basic population-based meta-heuristics using a benchmark of multimodal continuous functions, showing that VMO is a competitive algorithm.

1 Introduction

Many real-world problems (advanced engineering design, data analysis, financial planning, risk management, scientific modelling, etc.) may be formulated as parameter optimization problems with variables in continuous domains, continuous optimization problems. Over the past few years, increasing interest has arisen in solving these kinds of problems (Lozano et al. 2011; Herrera and Lozano 2005; Michalewicz and Siarry 2008).

In recent years, a new family of search and optimization algorithms has been used to solve this kind of problem that does not offer a guarantee of locating an optimal solution, but gives satisfactory results for a much larger range of these problems. These algorithms extend basic heuristic methods by including them in an iterative framework to increase their exploration capabilities. This group of advanced approximate algorithms has been given the name of meta-heuristics and an overview of various existing methods is found in Glover and Kochenberger (2003). Meta-heuristics have proven to be highly useful for approximately solving difficult optimization problems in practice, because they may obtain good solutions in a reduced amount of time. Real-coded genetic algorithms (GAs) (Herrera et al. 1998), particle swarm optimization (PSO) (Kennedy and Eberhart 1995), estimation of distribution algorithms (EDAs), scatter search (SS) (Laguna and Martí 2003) and difference evolution (DE) (Storn and Price 1997) are, among others, examples of the population-based meta-heuristics (PMHs). This term, PMHs, is used to group the meta-heuristics that use a solution set (called population) in each algorithm iteration.

PMHs introduce different ways of exploring the search space. They present powerful communication or cooperation mechanisms (depending on the context) to converge the population toward promissory areas of the search space. This type of meta-heuristics implements several mechanisms to introduce diversity into the population and consequently makes a better exploration of different regions of the domain space possible, obtaining very good results in continuous search spaces (Lozano et al. 2011).

Another element that has a strong influence over the population search is the influence of the best solutions over the remainder. In real coded genetic algorithms (Herrera et al. 1998), the best individuals have a greater probability of survival and of having influence over the offspring; and, in other algorithms, the remaining solutions are oriented to the best ones directly, as in PSO (Kennedy and Eberhart 1995) or, more indirectly, as in DE (Storn and Price 1997; Brest et al. 2007).

With these two facts in mind, we come up with a new PMH called variable mesh optimization (VMO) for real parameter optimization. This model introduces a new mechanism to explore the search space, by creating more solutions around the most promising regions of the mesh. Another mechanism is used to foment population diversity by selecting the best representatives of the mesh for the next iteration. In this algorithm, the population is represented by a set of nodes (potential solutions) that are initially distributed as a mesh, using a uniform distribution. The search process developed by the VMO meta-heuristic can be described by two operations:

• Expansion: this mechanism explores around the best solutions found, by creating new nodes between each node of the mesh and its best neighbour, and around the external borders of the mesh.

• Contraction: this clearing process removes all nodes that are too close to others with best fitness. The aim is to maintain the population size and to foment mesh diversity.

We study, based on experimental work, the influence of its different components, showing that the ideas underlying this technique can lead to successful results. Then, we compare the performance of the VMO with other basic PMHs with multimodal functions on continuous domains, showing that VMO is a competitive model.

This paper is organized as follows: In Sect. 2, a detailed description of the VMO is given, emphasizing the expansion and contraction processes of the mesh. In Sect. 3, the experimental framework and the statistical tests used to validate the experimental results are presented. In Sect. 4, we analyse the behaviour of several VMO components. In Sect. 5, the proposed model is compared with others, to ascertain whether its innovative design is conducive to the outperformance of other PMHs. Finally, in Sect. 6, we present the main conclusions and suggest future work.

2 Variable mesh optimization

VMO is a PMH in which the population is distributed as a mesh. This mesh is composed of P nodes $(n_1, n_2 ,\ldots, n_P)$ that represent solutions in the search space. Each node is coded as a vector of M floating point numbers, $n_i = (v_1^i, v_2^i, \ldots, v_M^i) = v_j^i,\; j = 1, \ldots, M$ that represent the solution to the optimization problem. In the search process developed by VMO, two operations are executed: the expansion and contraction processes. Both processes introduce a suitable balance between exploration and diversity for the VMO algorithm. In following subsections, these operators are described in detail, and in Fig. 1 the global algorithm is presented, using the parameters explained in Table 1.

Fig. 1

Steps to apply the VMO algorithm

Table 1 Parameters of the VMO algorithm

2.1 Mesh expansion operation

The algorithm develops the expansion process by moving the population through the search space. For this action, new nodes are obtained, using the current population of each iteration, according to the following steps:

• Step 1. (Initial mesh generation) The initial population for the first algorithm iteration is composed of P nodes that are randomly generated with uniform distribution.

• Step 2. (Nodes generation towards local extremes in the neighbourhood) The first kind of exploration conducted in VMO is carried out in the neighbourhood of each node (n _i ). The neighbourhood of n _i is composed of the k nodes closest (in terms of distance) to it. The best node (fitness) in the neighbourhood is selected as the local extreme (n ^* _i ). Only when n ^* _i is better than n _i , a new node is generated between n _i and $n_{i^{*}}$. For this reason, in this step Z new nodes are created, where Z ≤ P − 1.

To detect the neighbourhood of the i-th node, we used the euclidean distance (see Eq. 1)

$$ D_{\rm euclidian}(n_{1}, n_{2})=\sqrt{\sum_{j=1}^{M}(v_{j}^{1}-v_{j}^{2})^{2}} $$

(1)

The new nodes (n _z ) are calculated using the function F defined by Eq. 2

$$ n_z=F(n_i,n_i^*,Pr(n_i,n_i^*)) $$

(2)

where Pr is the near factor and represents the relation between the fitness of the current node and its local extreme. This factor is calculated by Eq. 3. It takes a value in the range [0, 1], higher when better fitness has n _i .

$$ Pr(n_i,n_i^{*})=\frac{1}{1+|\hbox{fitness}(n_i)-\hbox{fitness}(n_i^*)|} $$

(3)

The function F can be described in different ways. For this study, the components v ^z _j of the new nodes n _z are calculated by Eq. 4:

$$ v_{j}^{z} =\left\{ \begin{array}{ll} \overline{m_j},&{{\mathbf{if}}} |\overline{m_j}-v_j^{i^*}| > \xi_j\, \hbox {and}\\ & U[0, 1] \le Pr(n_i,n_i^*)\\ v_j^{i^*}+U[-\xi_j, \xi_j],&{{\mathbf{if}}} |\overline{m_j}-v_j^{i^*}| \le \xi_j\\ U[v_j^i, \overline{m_j}],&{{\mathbf{othercase}}} \end{array}\right. $$

(4)

where $\overline{m_j}=\hbox{average}(v_j^i,v_j^{i^*}), U[x, y]$ denotes a random value (uniformly) in the interval [x, y], and ξ _j defines the minimum allowed distance for each component. Its value decreases during the running of the algorithm, calculated by Eq. 5,

$$ \xi_j = \left\{\begin{array}{lll}\frac{range(a_j,b_j)}{4}&\hbox{if}& c<0.15\%C\\ \frac{range(a_j,b_j)}{8} & \hbox{if} & 0.15\%C \leq c < 0.3\%C\\ \frac{range(a_j,b_j)}{16} & \hbox{if} & 0.3\%C \leq c < 0.6\%C\\ \frac{range(a_j,b_j)}{50} & \hbox{if} & 0.6\%C\leq c < 0.8\%C\\ \frac{range(a_j,b_j)}{100} & \hbox{if} & c\geq 0.8\%C\\ \end{array}\right. $$

(5)

where C and c denote a maximum number of fitness evaluations allowed and the current number of fitness evaluations. In addition, the range(a _j , b _j ) denotes the domain amplitude (a _j , b _j ) of each component.

F function behaves as follows: in the first case, the average value between the current node and the local extreme is obtained for the j-th component. In the second case, the local extreme neighbourhood is displaced depending on a distance value for the current iteration. In the last case, a random number is generated between the average value and the current node.

Figure 2 shows an example of this step, with k = 4.

• Step 3. (Nodes generation towards the global extreme) This step is used to accelerate the algorithm convergence. For this, it explores in the direction of the node which has the best fitness of the current population, called the global extreme of the mesh (n _g ). X new nodes are generated (X = P − 1), one for each n _i towards n _g using Eq. 6.

  $$ n_x=G(n_i, n_g, Pr(n_i,n_g)) $$

  (6)

Fig. 2

Example of Step 2

In Eq. 7 we present the G function used in this work, where v ^x _j represents the values computed for each component of the new nodes n _x .

$$ v_j^x = \left\{ \begin{array}{ll} \hbox{average}(v_j^i, v_j^g), & \hbox{if}\quad U[0, 1]\leq Pr(n_i,n_g)\\ U[\hbox{average}(v_j^i,v_j^g), v_j^g], & \hbox{otherwise} \end{array}\right. $$

(7)

If there is a great difference (in fitness) between n _i and n _g , then there will be a high probability for the j-th component to take closer values to v ^g _j . In the other case, the average value is obtained.

Figure 3 shows a example of this step.

• Step 4. (Nodes generation starting from the frontier nodes of mesh) In this step, Y new nodes are created from the frontier nodes in the current population to complete the expansion process. This step is only run if the number of created nodes in the previous steps (Z + X) is lower than T, and Y = T − (Z + X) are created in this step. If Y > P, only P new nodes are created, one for each mesh node.

Fig. 3

Example of Step 3

In this step, we consider frontier nodes (n _t ). The frontier is composed of the nodes that are nearest (known as interior frontier or internal nodes, n _u ) and furthest (known as exterior frontier or external nodes, n _s ) from the point that represents the search space center. To detect these nodes, the euclidean distance is used. The nodes of the highest distance compose the set n _s and the ones with the smallest distance compose the set n _u . Starting from these sets, new nodes are created (one for each frontier node) using the function H (see Eq. 8).

$$ n_h=H(n_t, w) $$

(8)

For our study, the function H is defined by means of the Eqs. 9 and 10, where the components v ^h _j of each new node n _h are calculated depending on the frontier type:

In Eq. (9) ⌊ Y/2⌋ nodes are created, using n _s set:

$$ v_j^h = \left\{ \begin{array}{lll}v_j^s+w_j,&\hbox{if}& v_j^s > 0\\ v_j^s-w_j,&\hbox{if} & v_j^s < 0\\ \end{array}\right. $$

(9)

In Eq. (9) Y − ⌊ Y/2⌋ nodes are created, using n _u set:

$$ v_j^h = \left \{\begin{array}{lll} |v_j^u+w_j|,& \hbox{if} & v_j^u > 0\\ |v_j^u-w_j|, & \hbox{if} & v_j^u \leq 0\\ \end{array}\right. $$

(10)

where w _j represents a displacement for each component j and is calculated in a decreasing way according to Eq. 11:

$$ w_j=(w_j^0-w_j^1)\cdot \frac{C-c}{C}+w_j^1 $$

(11)

The variable w ⁰ _j represents the initial displacement and w ¹ _j its final value. In addition, the values C and c are used (see the description of Eq. 5). In order to obtain decreasing displacements w ⁰ _j  > w ¹ _j and its values are calculated as: w ⁰ _j  = range(a _j , b _j )/10 and w ¹ _j  = range(a _j , b _j )/100.

Figure 4 shows an example of this step, with Y = 4.

Fig. 4

Example of Step 4

2.2 Mesh contraction process

The contraction operation selects the nodes of the mesh that will be used as the population for the next algorithm iteration. Nodes with the best fitness are selected from among the current mesh and the new nodes created for the expansion process. In this way, it is similar to the elitist selection operators in evolutionary algorithms (Deb 2001; Herrera et al. 1998). Before the selection, a method to increase diversity in the mesh is presented to keep a minimum distance between the mesh nodes. To achieve this, an adaptive clearing operator is proposed. In the following, the contraction process is described:

• Step 5. All mesh nodes are ordered depending on their fitness (ascendant).

• Step 6. The difference between each node and their successors is calculated for each dimension. Successor nodes with any difference smaller than its corresponding ξ _j value are removed. The ξ _j value is calculated by Eq. 5. This strategy is called adaptive clearing, and finally we are left with B nodes.

• Step 7. The nodes with best fitness are selected as the population for the next iteration. If B < P then the mesh is completed with new random nodes.

This mechanism considers two important elements: the node qualities and their places in the solution space. The nodes with better fitness have a higher probability of taking part in the next population. Adaptive clearing allows the method to carry out more general explorations and eventually to reduce its frequency to focus on a smaller search space area. This element increases the method’s exploitation level and makes it stronger.

3 Experimental framework

We have carried out different experiments to assess the performance of VMO. In this section, we describe the test functions (Sect. 3.1), the statistical methods (Sect. 3.2) that were used to validate the results, and the experimental setup (Sect. 3.3).

3.1 Test functions

The test suite that we have used for the experiments consists of 20 benchmark multimodal functions chosen from the set designed for the special session on real parameter optimization organized in the 2005 IEEE congress on evolutionary computation (CEC2005) (Suganthan et al. 2005). The unimodal functions are not used for this study because these are simpler than the multimodal functions. In Suganthan et al. (2005), the complete description of the multimodal functions and their source codes can be found. The set of test functions is composed of the following functions:

• seven basic multimodal functions (F ₆–F ₁₂):

  • Shifted Rosenbrock’s function.

  • Griewank’s function, displaced and rotated without frontiers.

  • Ackley’s function, displaced and rotated with the global optimum in the frontier.

  • Rastrigin’s function, displaced.

  • Rastrigin’s function, displaced and rotated.

  • Weierstrass’ function, displaced and rotated.

  • Schwefel’s problem 2.13.

• Two expanded multimodal functions (F ₁₃ and F ₁₄).

• Eleven hybrid functions (F ₁₅–F ₂₅). Each one of them has been defined through combination of 10 out of the 14 previous functions (different in each case).

All functions were displaced to ensure that their optima can never be found in the center of the search space. In two functions, in addition, the optima cannot be found within the initialization range, and the domain of the search is not limited (the optimum is out of the initialization range).

3.2 Statistical methodology for comparisons

When a new optimization algorithm proposal is developed, it is necessary to compare it with previous approaches. Statistical analysis needs to be carried out to find significant differences among the results obtained by the studied methods. In García et al. (2009a, b), the uses of some nonparametric tests (Sheskin 2007) are presented to compare the results in computational intelligence. In particular, we have considered two alternative methods based on nonparametric tests to analyse the experimental results:

• Application of Iman and Davenport’s test (1980) and Holm’s method (1979) as post hoc procedures. The first test may be used to see whether there are significant statistical differences among the algorithms in certain groups (three or more algorithms). If differences are detected, then Holm’s test is employed to compare the best ranking algorithm (control algorithm) with the remaining ones.

• Utilization of the Wilcoxon (1945) matched-pairs signed-ranks test. With this test, the results of two algorithms may be directly compared.

Any reader interested in this topic can find additional information on the Web site http://sci2s.ugr.es/sicidm.

3.3 The experimental setup

The experiments have been developed in the two following ways:

• First, we analyse the influence of any parameters and their components on the VMO.

  • Size of mesh: VMO is tried with different sizes of the initial population to test if this has a strong influence on the quality of results.

  • Adaptive clearing operator: the influence of the adaptive clearing on the behaviour of the VMO is tested.

  • The expansion towards the frontiers (h function): the influence on the results of the exploration operator across the frontier nodes is observed.

• Then, we compare the VMO results with other algorithms from the literature.

All experiments have been carried out with dimension D = 10, D = 30 and D = 50, and the maximum number of fitness evaluations (stopping criterion) that we allowed for each algorithm is $C=10, 000 \cdot D$. The value of the k parameter used was k = 3 for all experiments and the other parameters were defined in each test suite. Each algorithm is run 25 times for each test function, and the average error of the best found solution is computed. The function error value for a solution x is defined as (f(x _j ) − f(x ^* _j )), where x ^* _j is the global optimum of the function. The results obtained in each experimental case are executed using the same test suite and are shown in Appendix as tables.

4 Internal analysis of VMO

In this section, we study the VMO’s behaviour for some internal elements: size of the initial population (Sect. 4.1), adaptive clearing operator (Sect. 4.2) and generation by means of the frontier’s nodes (Sect. 4.3).

4.1 Size of mesh

The definition of the size of the population is very important in current PMHs to obtain a high performance from these methods. For instance, in the GAs the populations must be big enough (Minetti 2005); due to the fact that not all the individuals influence the evolution of the population, a process of selection is conducted in each iteration to obtain a subgroup of the population to generate new individuals. In the specific case of the PSO (Kennedy and Eberhart 1995), use of smaller populations is recommended (Engelbrecht 2006) because all the agents change their position, directly influencing their displacement in the flock.

The process presented by the VMO is similar to PSO, in which all the population nodes are involved in the exploration. Due to this similarity, different sizes of mesh are studied: P = (8, 12, 24, 50 and 100). In all cases, the total expansion size used for these studies is $T=\frac{3}{2}P$. The results for the test functions are shown in Appendix Tables 14, 15 and 16.

To apply the nonparametric test to this case study, we present in Table 2 the average ranking of the VMO algorithm for different mesh sizes for all dimensions (the VMO(P) refers to the VMO algorithm with P population size, the best rank is presented in bold typeface). The results of Iman–Davenport’s test show that the mesh size could produce significant differences; due to this fact, the hypothesis of equality has been rejected for each dimension (see Table 3). This conclusion was obtained because the statistical test value was greater than the critical value, 2.4920 in this case.

Table 2 Ranking of the VMO algorithm for different mesh sizes for each dimension

Table 3 Results of Iman–Davenport’s test for different mesh sizes for each dimension

To continue, Holm’s test is applied to compare the configuration with the best rank in each dimension (VMO(50) for D = 10 and VMO(12) for D = 30 and D = 50), with each of the four remaining ones. For this test, the algorithms are ordered in descending order according to rank.

Table 4 contains all the computations associated with Holm’s procedure (z = (R ₀ − R _i )/SE, p value, and α/i) for a standard error for each dimension of SE = 0.5. The last column indicates whether the control algorithm performs significantly better than the corresponding algorithm (first column), in this case the equality hypothesis is rejected. This conclusion is arrived at because the p values are smaller than the corresponding α/i values. For this comparison, the results obtained with a mesh size of 50 nodes are significantly superior to three of the compared configurations (VMO(8), VMO(12) and VMO(24)) for D = 10. Only in comparison with VMO(100) are the differences insignificant. For D = 30 and D = 50, the VMO algorithm with a population size of 12 nodes obtained significantly superior results to the other mesh configurations.

Table 4 Results of the Holm’s test for each dimension with a significance value 0.05

We have applied Wilcoxon’s test to compare VMO(50) configuration with VMO(100) for D = 10. In this test, the values of R ⁻ and R ⁺ (associated with the control algorithm in comparison) are specified (the lowest ones, which correspond to the worst results, are highlighted in bold face), together with the p values computed for this test and whether the hypothesis is rejected (the p value is lower than the significance value) or not. Table 5 shows the results, showing that that VMO(50) obtained better results than VMO(100) (the R ⁺ values are higher than the R ⁻ ones). But this difference is not statistically significant (because 0.157 > 0.05). Because VMO(50) is the best mesh size, it will used in the studies for dimension 10.

Table 5 Results of Wilcoxon’s test (significance value, 0.05)

In these experiments, we can conclude that the mesh size has a relation to the dimension of the problem. For problems with a small dimension, a population size of between 50 and 100 nodes obtains good results, and for high dimensions the best results are obtained with a mesh of 12 nodes.

4.2 Adaptive clearing operator

Here, we study the effect of applying an adaptive clearing operator to the VMO algorithm. For this study, we compare the results among other clearing operators and our adaptive proposal. The results of this comparison are shown in Appendix Tables 17, 18 and 19. VMO-NC and VMO-AC represent the solutions to the algorithm, without the clearing operator and using the adaptive clearing, respectively. VMO-C1, VMO-C2, VMO-C3, VMO-C4 and VMO-C5 show the VMO solutions with the clearing operator for different constant values of the distance ($\xi_j=\frac{range(a_j, b_j)}{4},\frac{range(a_j, b_j)}{8},\frac{range(a_j, b_j)}{16},\frac{range(a_j, b_j)}{50}$ and $\frac{range(a_j, b_j)}{100}$, respectively), depending of the domain amplitude in each test function (see Eq. 6).

In Table 6, we show the mean rankings of each executed alternative for different clearing operators.

Table 6 Ranking of VMO’s algorithm with different clearing operators for each dimension

First, we apply Iman–Davenport’s test to each dimension. Table 7 shows the results, detecting statistically significant differences for each dimension. Thus, we applied Holm’s multiple comparisons test to find out which algorithm was statistically better than the others.

Table 7 Results of the Iman–Davenport’s test for different alternatives of clearing operator for each dimension

Holm’s test compares the algorithm with the best rank for each dimension VMO-AC, with each one of the other configurations, in pairs. Table 8 shows the results of Holm’s test with the significance value 0.05. We can see that there are significant differences in the majority of cases, with the exception of VMO-C3 and VMO-C2, where there are no significant differences in dimension 10.

Table 8 Results of the Holm’s test for each dimension

We have also applied Wilcoxon’s test to determine which of them presents the best behaviour. Table 9 shows the results between VMO-AC and VMO-C3, and VMO-AC and VMO-C2 for D = 10. In both cases, the differences in favour of VMO-AC (R ⁺ values are higher than R ⁻) are statistically significant. VMO-AC is the best algorithm, proving that a clearing method improves the results, and the proposed adaptive clearing method statistically improves results obtained with a fixed distance value. Thus, in the following, the VMO uses the adaptive clearing method.

Table 9 Results of Wilcoxon’s test (significance value 0.05)

4.3 Generation from the frontier nodes

This generation process explores the domain space around the frontiers of the population. For this reason, it is necessary to carry out an experimentation to determine whether the process should be applied. Then, we will present a statistical study of the experimental results shown in Table 20 in the Appendix, in which the column VMO-NF represents the algorithm VMO when the frontier’s operator is not used, and VMO-F when it is used. For this study, we use Wilcoxon’s test to compare both algorithms for each dimension.

It can clearly be seen (see Table 10) that VMO-F obtains better results than VMO-NF in all dimensions (R ⁺ values are higher than the R ⁻ ones). In addition, the statistical test indicates that these improvements are statistically significant.

Table 10 Results of Wilcoxon’s test (significance value 0.05)

In the following, the algorithm VMO will be used with the adaptive clearing operator and the nodes generation operator starting from the frontiers.

5 Comparative study with others algorithms

A comparative study is conducted between VMO and other PMHs that have a demonstrably high level of performance. These algorithms belong to evolutionary algorithms and swarm Intelligence. The local search algorithms are not used to improve the solutions. To continue, a brief description of the methods is presented:

• Steady-state genetic algorithm (SSGA) (Syswerda 1989), with an election of parents negative assortative mating (Fernandes and Rosa 2001) with N _nam  = 3., and a replacement strategy of replacing the worst.

• Linearly decreasing inertia weight in particle swarm optimization (LDWPSO) (Shi and Eberhart 1998): the algorithm PSO proposed by Shi and Ebenhart is taken into account, applying the authors’ configuration: the inertia varies from the maximum value (w _max = 0.9) to the minimum value (w _min = 0.4); the parameters c1 and c2 are equal to 2.8 and 1.3, respectively.

• Opposite differential evolution (ODE) (Rahnamayan et al. 2008): this algorithm is a DE that enforces diversity in the search, considering in the search process the opposite of each new solution created.

The parameters used in all cases were defined by the authors themselves.

We present a statistical analysis conducted over the results shown in Appendix Tables 23, 24 and 25. In this analysis, we compare VMO with other algorithms presented in this section, using Wilcoxon’s test.

According to Wilcoxon’s test results summarized in Tables 11, 12 and 13 it can be observed that:

• VMO is significantly better than the SSGA and LDWPSO for D = 10. The statistical test indicates that these improvements are statistically significant. VMO is only worse in absolute terms in relation to ODE ((R ⁺ values are lower than the R ⁻ ones)), but not in a significant way.

• VMO is statistically better than all the alternatives taken into consideration for the D = 30. The difference in respect to ODE increases.

• Finally, for dimension 50, results obtained by VMO are significantly better than all the PMHs it was compared with.

Table 11 Results of Wilcoxon’s test for D = 10

Table 12 Results of Wilcoxon’s test for D = 30

Table 13 Results of Wilcoxon’s test for D = 50

6 Conclusions

A PMH-denominated variable mesh optimization (VMO) was introduced in this paper. It includes new ways of exploring the search space:

• To use attraction towards the node with the best fitness (local extremes) on the neighbourhood of each mesh node, towards the node with the best fitness of the mesh (global extreme) and the frontiers of the mesh in the same algorithm iteration. For these exploration methods, the algorithm obtains a suitable balance between the exploitation and the exploration of the search space.

• To conduct an elitist initial population selection in each iteration, taking into account the quality and the separability between the nodes by means of a clearing operator. This mechanism introduces diversity in the population that facilitates a larger exploration of the solution space. In addition, the population contains the best representative of each zone of the explored search space.

• The clearing operator functions in an adaptive manner because it decreases the allowed distance between the nodes as the algorithm is conducted, depending on the extent of each interval. This operator causes the method to start with a high exploration level that decreases as the allowed distance during the running of the algorithm. It occurs in reverse proportion to the exploitation level of the method.

It has been shown that the proposed VMO algorithm presents a good scalability level presenting good results with dimensions 30 and 50.

The promising research line initiated with the present optimization framework based on VMO is worthy of further study. We will extend our investigation to test different mechanisms to create new nodes towards local and global extremes (for example, some operators presented in Herrera et al. 2003). Furthermore, we will study the clearing operator to regulate the diversity levels that it introduces in the mesh and to see its influence on the behaviour of the VMO algorithm.

Appendix: Results of the experiments

In this appendix, the results used for the statistical analysis for each study case are presented. Each algorithm is run 25 times for each test function, and the average error of the best found solution is computed. The function error value for a solution x is defined as (f(x _j ) − f(x ^* _j )), where x ^* _j is the global optimum of the function. The captions in the tables detail which experiment it belongs to and the dimension of the test functions used (see Tables 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25).

Table 14 Results for different mesh sizes for dimension 10

Table 15 Results for different mesh sizes for dimension 30

Table 16 Results for different mesh sizes for dimension 50

Table 17 Results for different kinds of clearing operators for dimension 10

Table 18 Results for different kinds of clearing operators for dimension 30

Table 19 Results for different kinds of clearing operators for dimension 50

Table 20 Results for the frontier’s operator for dimension 10

Table 21 Results for the frontier’s operator for dimension 30

Table 22 Results for the frontier’s operator for dimension 50

Table 23 Results of the comparison with others algorithms for dimension 10

Table 24 Results of the comparison with others algorithms for dimension 30

Table 25 Results of the comparison with others algorithms for dimension 50