# MEEF: A Minimum-Elimination-Escape Function Method for Multimodal Optimization Problems

Authors: Lei Fan; Yuping Wang; Xiyang Liu; Liping Jia
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Auxiliary function methods provide us effective and practical ideas to solve multimodal optimization
problems. However, improper parameter settings often cause troublesome effects which might lead to the
failure of finding global optimal solutions. In this paper, a minimum-elimination-escape function method is
proposed for multimodal optimization problems, aiming at avoiding the troublesome “Mexican hat” effect and
reducing the influence of local optimal solutions. In the proposed method, the minimum-elimination function
is constructed to decrease the number of local optimum first. Then, a minimum-escape function is proposed
based on the minimum-elimination function, in which the current minimal solution will be converted to the
unique global maximal solution of the minimum-escape function. The minimum-escape function is insensitive
to its unique but easy to adopt parameter. At last, an minimum-elimination-escape function method is designed
based on these two functions. Experiments on 19 widely used benchmarks are made, in which influences of
the parameter and different initial points are analyzed. Comparisons with 11 existing methods indicate that
the performance of the proposed algorithm is positive and effective.


---

## Body

## 1. Introduction

Global optimization plays a significant role in many fields, for example, science, economics, and engineering. A global optimization problem can be formulated as follows:(1)min⁡x∈Dfx,where x∈Rn, D={x∣ai≤xi≤bi,i=1~n}, and f(x) is considered to be multimodal and continuously differentiable in this paper.Early research on single modal global optimization problems had gained many results. However, these achievements cannot solve multimodal global optimization problems (GOPs) effectively. Multimodal optimization problems are difficult to solve for the existing of many local optimal solutions, which often make the optimization algorithms trap into local optimum. More and more attention has been paid for multimodal optimization. As the main tasks of a solution algorithm, finding global optimal solutions of multimodal problems with small computational cost should avoid trapping into local optimal solutions. Deterministic algorithms are developed to deal with these difficulties and the literature review on this work can be referred to [1]. Auxiliary function method, as a kind of deterministic method, provides us an effective and practical idea to jump out from local optimal solutions, for example, filled function method (FFM) [2–7], tunneling method [8], basin-hopping method [9], sequential convexification method (SCM) [10], and cut-peak function method [11], and so forth. Auxiliary function is a transformed objective function that constructs a path from one of the local minimizers of the original objective function to another lower local minimizer [4]. Filled function method [2] is such an approach for multimodal problems to find the global minimal solutions, in which the filled function is constructed to help jump from one local optimal solution to another better one. However, this kind method is sensitive to its parameters. Improper settings often brings about “Mexican hat” effect [12], which might make the algorithm fail in finding global optimal solutions.In this paper, a minimum-elimination function is constructed to eliminate the solutions worse than the best solution found so far. Using this function, the local optimal solutions can be decreased. Thus, the number of the local optimal solutions can be reduced significantly. However, flattened by the minimum-elimination function, much information of the original optimization problems might be eliminated. Hence, the optimization algorithms still have difficulties to solve the problems. Hence, we proposed a minimum-escape function based on the minimum-elimination function, which can help the algorithm find the better solutions. Converted by minimum-escape function, there will be only one global maximum. Therefore, this function can provide search algorithms directions away from the best solutions found so far and it can help the search algorithms avoid revisiting or trapping into the local minimal solutions that had been found. In this way, the troublesome “Mexican hat” effect can be avoided effectively.The remainder of this paper is organized as follows: Section2 introduces the motivation of this paper. Section 3 is dedicated to explaining the proposed minimum-elimination-escape function in detail. Section 4 gives the minimum-elimination-escape function method for multimodal problems. Experiments on the performance of the proposed algorithm are shown in Section 5. Finally, conclusions on this paper are drawn in Section 6.


## 2. Motivation

### 2.1. “Mexican Hat” Effect

When solving multimodal optimization problems, auxiliary function methods can jump out the local optimal solutions with the help of the tailor-made auxiliary functions. For many auxiliary function methods, for example, filled function method [2] and stretching function method [13], improper parameter settings often cause an unwilling phenomenon called “Mexican hat” effect [12]. As shown in Figures 1 and 2, this effect often introduces some troublesome local minimum for the auxiliary functions, which might make the search algorithm trap into local optimal solutions and leads to failure of finding global optimal solutions. This troublesome effect often introduces great additional complexity. It can be seen vividly that the local minimum of the auxiliary functions in Figures 1 and 2 can not help the optimization methods jump out from the local minimum of the original functions. In this case, the endless loops will be brought about for the optimization methods, which makes the optimization process failure.Figure 1
“Mexican hat” effect in filled functions.Figure 2
“Mexican hat” effect in stretching functions.“Mexican hat” effect had been discussed in [12] in detail. Many efforts have been directed towards avoiding this unwilling phenomenon [11, 14]. The cut-peak function method [11] is such an auxiliary function method that can avoid “Mexican hat” effect. However, the cut-peak function method has its disadvantages on losing global optima during searching process.


### 2.2. Lost Global Optima

Although the cut-peak function method has advantage on keeping the best solutions found so far, it will lose the global optimal solutions especially at the end of the searching process. In [11], the cut-peak function is suggested as follows:(2)wr,x∗,x=fx∗-f0r,x-x∗,where x∗ is the best solution found so far, r is a positive parameter, and f0(r,·) was given two concrete examples as follows: (3)f0r,t=rt21+t2orf0r,t=r1-e-t2.Then, a choice function is constructed to find better solutions as follows: (4)Fr,x∗,x=min⁡fx,wr,x∗,x.When the parameterr is properly adjusted, the choice function (4) can keep the original function values of some better solutions unchanged and can find the better solutions easily. However, there are two cases that may lead to the failure of finding global optimal solutions. One case is that if the distance between the best solutions found so far and other local optimal solutions is too large, it will be of great difficulty to adopt the parameter r. The other case is that if the parameter r was larger than a certain value, all the solutions that are better than x∗ will be ignored, which will lead to failure in finding global optimal solutions. In particular, if the function values of the local optimal solution and the global optimal solution have little difference, the global optimal solution will be lost with very high probability. It is very difficult to adopt r. So as to illustrate the influence of r obviously, we use the same example as [11], in which the objective function is f(x)=-exsin(2πx), where x∈[0,4]. It is supposed that the best solution found so far is x∗=1.275. The cut-peak function at x∗ is constructed as w(r,x∗,x)=f(x∗)-(rx-x∗2/(1+x-x∗2)) and the parameter r is set to be 5 and 30, respectively. From Figure 3, one can see vividly that the cut-peak function can keep the basins better than x∗ unchanged when r=5. However, when r=30, there is no better basin that can be kept for the cut-peak function. It can be deduced easily that the smaller the parameter r is, the more better basins will be kept. Huang et al. proposed a revised cut-peak function in [15].Figure 3
Cut-peak function. The dotted line indicates the original function, the solid lines in gray and black indicate the cut-peak function withr=5 and r=30, respectively.Although the cut-peak function can successfully avoid the “Mexican hat” effect, its performance is influenced significantly by its parameterr. What is more, it needs much computational cost to adopt the parameter. Therefore, we will design a new parameter-insensitive auxiliary function which can avoid the unwilling “Mexican hat” effect in this paper.


## 2.1. “Mexican Hat” Effect

When solving multimodal optimization problems, auxiliary function methods can jump out the local optimal solutions with the help of the tailor-made auxiliary functions. For many auxiliary function methods, for example, filled function method [2] and stretching function method [13], improper parameter settings often cause an unwilling phenomenon called “Mexican hat” effect [12]. As shown in Figures 1 and 2, this effect often introduces some troublesome local minimum for the auxiliary functions, which might make the search algorithm trap into local optimal solutions and leads to failure of finding global optimal solutions. This troublesome effect often introduces great additional complexity. It can be seen vividly that the local minimum of the auxiliary functions in Figures 1 and 2 can not help the optimization methods jump out from the local minimum of the original functions. In this case, the endless loops will be brought about for the optimization methods, which makes the optimization process failure.Figure 1
“Mexican hat” effect in filled functions.Figure 2
“Mexican hat” effect in stretching functions.“Mexican hat” effect had been discussed in [12] in detail. Many efforts have been directed towards avoiding this unwilling phenomenon [11, 14]. The cut-peak function method [11] is such an auxiliary function method that can avoid “Mexican hat” effect. However, the cut-peak function method has its disadvantages on losing global optima during searching process.


## 2.2. Lost Global Optima

Although the cut-peak function method has advantage on keeping the best solutions found so far, it will lose the global optimal solutions especially at the end of the searching process. In [11], the cut-peak function is suggested as follows:(2)wr,x∗,x=fx∗-f0r,x-x∗,where x∗ is the best solution found so far, r is a positive parameter, and f0(r,·) was given two concrete examples as follows: (3)f0r,t=rt21+t2orf0r,t=r1-e-t2.Then, a choice function is constructed to find better solutions as follows: (4)Fr,x∗,x=min⁡fx,wr,x∗,x.When the parameterr is properly adjusted, the choice function (4) can keep the original function values of some better solutions unchanged and can find the better solutions easily. However, there are two cases that may lead to the failure of finding global optimal solutions. One case is that if the distance between the best solutions found so far and other local optimal solutions is too large, it will be of great difficulty to adopt the parameter r. The other case is that if the parameter r was larger than a certain value, all the solutions that are better than x∗ will be ignored, which will lead to failure in finding global optimal solutions. In particular, if the function values of the local optimal solution and the global optimal solution have little difference, the global optimal solution will be lost with very high probability. It is very difficult to adopt r. So as to illustrate the influence of r obviously, we use the same example as [11], in which the objective function is f(x)=-exsin(2πx), where x∈[0,4]. It is supposed that the best solution found so far is x∗=1.275. The cut-peak function at x∗ is constructed as w(r,x∗,x)=f(x∗)-(rx-x∗2/(1+x-x∗2)) and the parameter r is set to be 5 and 30, respectively. From Figure 3, one can see vividly that the cut-peak function can keep the basins better than x∗ unchanged when r=5. However, when r=30, there is no better basin that can be kept for the cut-peak function. It can be deduced easily that the smaller the parameter r is, the more better basins will be kept. Huang et al. proposed a revised cut-peak function in [15].Figure 3
Cut-peak function. The dotted line indicates the original function, the solid lines in gray and black indicate the cut-peak function withr=5 and r=30, respectively.Although the cut-peak function can successfully avoid the “Mexican hat” effect, its performance is influenced significantly by its parameterr. What is more, it needs much computational cost to adopt the parameter. Therefore, we will design a new parameter-insensitive auxiliary function which can avoid the unwilling “Mexican hat” effect in this paper.


## 3. Minimum-Elimination-Escape Function

The proposed minimum-elimination-escape function in this section consists of minimum-elimination function and minimum-escape function. The minimum-elimination function is constructed to eliminate the solutions worse than the best solutions found so far, aiming to reduce the influence of local optimal solutions. Then, a minimum-escape function is proposed to transform the minimum found so far to the unique global maximum. Also, the minimum-escape function can lead optimization algorithms to explore the region far away from the best solutions found so far. The properties of the proposed minimum-elimination-escape function are also analyzed in this section.


### 3.1. Minimum-Elimination Function

Local optimal solutions have great impact on the performance of an optimization algorithm, especially when there were a large number of local optimal solutions which often leads to the failure of finding global optimal solutions. To some degree, decreasing the number of local optimal solutions is a simple and effective way of reducing the complexity of the problem. Therefore, the minimum-elimination function is constructed here to eliminate the solutions worse than the best solutions found so far. In this way, the number of local optimal solutions can be reduced, which will be much helpful to the optimization algorithms.The minimum-elimination function is constructed as follows:(5)Sx,x∗=fx∗+121--1sign(fx-fx∗)fx∗-fx,where f(x) is the original objective function, x∗ is the best solution found so far and changing with generation, and sign(y) is defined as follows: (6)signy=1,y>0-1,y=00,y<0.It is obvious that, for∀x∈D, the minimum-elimination function has the following two properties:(i)
S(x,x∗)=f(x∗) if f(x)>f(x∗),(ii)
S(x,x∗)=f(x) if f(x)<f(x∗). In other words, only when the better solution was found, the value of S(x,x∗) changed. These two properties can be intuitively illustrated by smoothing a function of one variable as an example in Figure 4, where the dashed line in Figure 4 represents the original function and the black solid line represents the minimum-elimination smoothing function. Here, the example function is taken as f(x)=x+10sin(5x)-7sin(4x), where x∈[0,10]. The minimum-elimination function is generated at the solution x∗=4.816.Figure 4
2D example: minimum-elimination function at the current best solutionx∗. The black solid line indicates the minimum-elimination function S(x,x∗); the dotted line indicates the original function f(x).Flattened by the minimum-elimination function,GP can be converted to the following problem:(7)FGPmin⁡x∈DSx,x∗,where x∗ is the best solution found so far. The flattened GP is denoted as FGP for convenience. It is obvious that GP and FGP share the same global optima. And FGP has fewer local minima than GP. However, after being flattened by the minimum-elimination smoothing function, there will exist much plane in FGP, so that much mathematical information will be lost.


### 3.2. Minimum-Escape Function

As mentioned above, FGP loses much information and contains many flatlands which are very difficult to be managed for an algorithm. Improper handling often brings about additional complexity for solving FGP. One important issue is to design suitable strategies of searching the field far away from the best solutions found so far, aiming to find better solutions or basins. Therefore, a minimum-escape function is proposed to deal with the flatlands, which is designed at the best solutionx∗ found so far as follows:(8)Px,x∗,γ=Sx,x∗-γx-x∗2,where the unique parameter γ>0.Figures5–8 show the properties of the minimum-escape function vividly. Among these figures, one can have intuitive impression of the proposed functions. In Figures 4 and 5, a 2-dimensional example was employed. Figures 6 to 8 illustrate the performance of the minimum-elimination smoothing function on the multimodal function and the performance of the proposed minimum-escape function on the smoothed function. It can be seen vividly from these 3D figures that flattened by the minimum-elimination function, much plane and holes are left. By the constructed function (8), the flattened function will be transformed to an arch-like function with x∗ as its unique global maximal point. From Figures 5 and 8, we can see obviously that the holes still exist in the slope of the minimum-escape functions. These holes may be the same holes of the flattened functions, which are the basins (A basin [16] of f(x) at an isolated minimizer x1∗ is a connected to domain B1 which contains x1∗ and in which starting from any point the steepest descent trajectory of f(x) converges to x1∗ but outside which the steepest descent trajectory of f(x) does not converge to x1∗) of S(x,x∗), which are also the basins of f(x) where the better local optimal solutions locate. Therefore, the aim of the algorithm is to find these holes. We can imagine that a water-drop on this vault will slide down along any direction due to the influence of gravity. Its track might go through some of these holes. Motivated by this phenomenon, we considered that a method can be employed as gravity to guide the search process to find the holes, and another method can be used to find the local optimum. In the following subsection, the properties of the proposed function will be analyzed in detail.Figure 5
2D example: minimum-escape function for the flattened problem (FGP) at the current best solutionx∗.Figure 6
3D example: original function.Figure 7
3D example: flattened by the minimum-elimination function at the current best solutionx∗.Figure 8
3D example: minimum-escape function for the flattened problem (FGP) at the current best solutionx∗.


### 3.3. Properties of Minimum-Escape Function

From Figures4 to 8, it can be seen that the minimum-escape function has the following properties:(1)
x∗ is the unique global maximum of P(x,x∗,γ), and P(x∗,x∗,γ)=f(x∗);(2)
P(x,x∗,γ) has no stationary points in the region S1={x∣f(x)≥f(x∗), x∈D/{x∗}};(3)
ifx∗ is not a global minimizer of f(x), then P(x,x∗,γ) can distinguish the better solution than x∗.To illustrate the properties of the proposed minimum-escape function, we choosex∗ as the reference point and generate the following function as a discrimination function: (9)Jx,x∗,γ=Px,x∗,γ-Px∗,x∗,γx-x∗2x≠x∗γx=x∗.To some degree, J(x,x∗,γ) can be regarded as the slop of P(x,x∗,γ) at x according to the reference point x∗ with x-x∗2. J(x,x∗,γ) can help us understand the properties of P(x,x∗,γ) and also can be used to estimate whether the obtained solutions are better than x∗.Proposition 1.
Iff(x) is continuous, then both S(x,x∗) and P(x,x∗,γ) are continuous.Proposition 2.
Suppose thatx∗ is the best solution found so far. Then, x∗ is the unique global maximizer of P(x,x∗,γ).Proof.
For∀x∈D,(10)Px,x∗,γ=Sx,x∗-γx-x∗2≤f(x∗)-γx-x∗2≤fx∗.
Assume that there exists another pointy≠x∗, such that, for any x∈D, P(x,x∗,γ)≤P(y,x∗,γ). While (11)Py,x∗,γ=Sy,x∗-γy-x∗2≤fx∗-γy-x∗2<fx∗=Px∗,x∗,γ,thus ∃x∗∈D, such that P(y,x∗,γ)<P(x,x∗,γ), which conflicts with the assumption.
Therefore,x∗ is the unique global maximizer of P(x,x∗,γ).Proposition 3.
For∀x∈D, J(x,x∗,γ)≥γ.Proof.
For∀x∈D, it can be concluded from formula (8) that S(x,x∗)≤S(x∗,x∗)=f(x∗). Therefore, for x=x∗, it is obvious that J(x∗,x∗,γ)=γ. For x≠x∗, (12)Jx,x∗,γ=Px∗,x∗,γ-Px,x∗,γx∗-x2=Sx∗,x∗-Sx,x∗x∗-x2+γ≥γ.Proposition 4.
For∀x∈D, (13)fx<fx∗⟺Jx,x∗,γ>γfx≥fx∗⟺Jx,x∗,γ=γ.Proof.
For∀x∈D, if x=x∗, it is obvious that f(x)=f(x∗)⇔J(x,x∗,γ)=γ holds; if x≠x∗, then (14)fx<fx∗⟺Sx,x∗<Sx∗,x∗⟺P(x,x∗,γ)+γx∗-x2<Px∗,x∗,γ⟺Px∗,x∗,γ-Px,x∗,γ>γx∗-x2⟺Px∗,x∗,γ-Px,x∗,γx∗-x2>γ⟺Jx,x∗,γ>γ,fx≥fx∗⟺Sx,x∗=Sx∗,x∗⟺Px,x∗,γ+γx∗-x2=Px∗,x∗,γ⟺Px∗,x∗,γ-Px,x∗,γx∗-x2=γ⟺Jx,x∗,γ=γ.Following Proposition4, it is obvious that better solutions are with larger slop than worse solutions.Denote(15)S0=x∣Jx,x∗,γ=γ,x∈D,S0′=x∣fx≥fx∗,x∈DS1=x∣Jx,x∗,γ>γ,x∈D,S1′=x∣fx<fx∗,x∈D.Then, (16)S0∩S1=S0′∩S1′=ΦS0∪S1=S0′∪S1′=DS0=S0′,S1=S1′.Proposition 5.
Suppose thatB1⊂S1 is a basin of S(x,x∗) and x1∗ is the minimizer in B1, then (17)Jx1∗,x∗,γ=max⁡x∈B1Jx,x∗,γ.Proof.
Follow thatS1=S1′, B1⊂S1′. Consider ∀x∈B1, S(x∗,x∗)>S(x,x∗)≥S(x1∗,x∗), (18)Jx,x∗,γ=Sx∗,x∗-Sx,x∗+γx∗-x2x∗-x2=Sx∗,x∗-Sx,x∗x∗-x2+γ≤Sx∗,x∗-Sx1∗,x∗x∗-x2+γ=Jx1∗,x∗,γ.
Therefore,(19)Jx1∗,x∗,γ=max⁡x∈B1Jx,x∗,γ.According to Proposition5, one might conclude that if x~∗ is the global minimizer of S(x,x∗), then J(x~∗,x∗,γ)=max⁡x∈S1⁡{J(x,x∗,γ)} holds. Unfortunately, this conclusion does not always hold. We will give a counter example to show that the point x~∗, which satisfies J(x~∗,x∗,γ)=max⁡x∈S1⁡{J(x,x∗,γ)}, is not the global minimizer of S(x,x∗). Here, we still use the example function in this section, where x∈[0,10] and the best point is x∗=7.102. In Figure 9, we denote the basins as A and B, which are surrounded by Ellipses A and B, respectively. From Figure 9, it can be seen vividly that the global minimum is included in A, and B is an ordinary basin worse than the global minimum. What is unusual is that J(x,x∗,γ) does not achieve its global maximum at the global minimum of f(x) but achieves its global maximum at a local minimum of f(x) in B. It might seem strange. Next, we will discuss the reason of this strange phenomenon.Figure 9
Minmum-escape function at the best solutionx∗. The dot-line indicates the original function f(x); the black and blue solid line indicate P(x,x∗,γ) and J(x,x∗,γ), respectively.For the convenience of analyzing this phenomenon, the domain of the original problem is expanded toRn and the objective function is supposed to be an uniformly continuous function, which satisfies that, for ∀x∈Rn, ∃M>0 such that |f(x)|≤M. Under this assumption, we can get the following theorems.Proposition 6.
If∃M>0, such that, for ∀x, |f(x)|≤M holds, then (20)limx→∞Jx,x∗,γ=γ.Proof.
Consider(21)limx→+∞Jx,x∗,γ=limx→+∞Px∗,x∗,γ-Px,x∗,γx∗-x2=γ+limx→+∞Sx∗,x∗-Sx,x∗x∗-x2=γ.Proposition 7.
Forx1,x2∈S1, suppose that x1≠x2 and x∗-x12<x∗-x22; if f(x1)=f(x2), then (22)Jx1,x∗,γ>Jx2,x∗,γ.Proof.
Iff(x1)=f(x2), then S(x1,x∗)=S(x2,x∗) and P(x1,x∗,γ)>P(x2,x∗,γ)>γ hold. Then (23)Jx1,x∗,γ=Px∗,x∗,γ-Px1,x∗,γx∗-x12=Px∗,x∗,γ-Px2,x∗,γx∗-x12>Px∗,x∗,γ-Px2,x∗,γx∗-x22=Jx2,x∗,γ.Propositions6 and 7 can explain why this strange phenomenon occurs. Proposition 6 means that, for ∀x∈S1, the further away from x∗, J(x,x∗,γ) will be closer to γ. If x is sufficient far away from x∗, then the value of J(x,x∗,γ) is so close to γ that its variation will be tiny. From Proposition 7, we can infer that the closer a basin is to x∗, the greater J(x,x∗,γ) will change. If a local minimum  x^ is closer to the reference point x∗ than the global minimum x~∗ then J(x^,x∗,γ)>J(x~∗,x∗,γ) might take place.From Propositions1, 2, and 4, it can be seen that the designed minimum-elimination function can efficiently eliminate the solutions worse than the best one found so far. In this way, the original problem can be converted to another global optimization problem sharing the same global optimum, which will be good for solution algorithm to avoid trapping into local minimum. The current best solution can be converted to the global maximizer by the designed minimum-escape function. During the search process, the best solution found so far will not be visited twice. The designed minimum-escape function can help the solution algorithm to explore the whole domain by reducing the objective function value in proportion to the distance to the best solution found so far. And Proposition 4 provides a method to estimate whether the point is better than the current best solution.Estimating the parameterγ is another issue. In most existing auxiliary function methods, estimating parameters is an important and hard task. However, the parameter γ in the proposed function is not sensitive and can be adopted easily. In general, when x∗ is the best solution found so far, the search will go away from x∗. However, when the search goes to a point x far away from x∗ (usually x is away from x∗ in order to jump out the current basin), the main problem arisen will be that γx-x∗ is too large to result in arithmetic overflow. So γ should be small in order to avoid this phenomenon. Thus, in the proposed algorithm, it will be no problem when γ is taken not too large. In this paper, the parameter γ is suggested to be taken in (0,1]. In experiments, the influence of parameter γ will be tested.


## 3.1. Minimum-Elimination Function

Local optimal solutions have great impact on the performance of an optimization algorithm, especially when there were a large number of local optimal solutions which often leads to the failure of finding global optimal solutions. To some degree, decreasing the number of local optimal solutions is a simple and effective way of reducing the complexity of the problem. Therefore, the minimum-elimination function is constructed here to eliminate the solutions worse than the best solutions found so far. In this way, the number of local optimal solutions can be reduced, which will be much helpful to the optimization algorithms.The minimum-elimination function is constructed as follows:(5)Sx,x∗=fx∗+121--1sign(fx-fx∗)fx∗-fx,where f(x) is the original objective function, x∗ is the best solution found so far and changing with generation, and sign(y) is defined as follows: (6)signy=1,y>0-1,y=00,y<0.It is obvious that, for∀x∈D, the minimum-elimination function has the following two properties:(i)
S(x,x∗)=f(x∗) if f(x)>f(x∗),(ii)
S(x,x∗)=f(x) if f(x)<f(x∗). In other words, only when the better solution was found, the value of S(x,x∗) changed. These two properties can be intuitively illustrated by smoothing a function of one variable as an example in Figure 4, where the dashed line in Figure 4 represents the original function and the black solid line represents the minimum-elimination smoothing function. Here, the example function is taken as f(x)=x+10sin(5x)-7sin(4x), where x∈[0,10]. The minimum-elimination function is generated at the solution x∗=4.816.Figure 4
2D example: minimum-elimination function at the current best solutionx∗. The black solid line indicates the minimum-elimination function S(x,x∗); the dotted line indicates the original function f(x).Flattened by the minimum-elimination function,GP can be converted to the following problem:(7)FGPmin⁡x∈DSx,x∗,where x∗ is the best solution found so far. The flattened GP is denoted as FGP for convenience. It is obvious that GP and FGP share the same global optima. And FGP has fewer local minima than GP. However, after being flattened by the minimum-elimination smoothing function, there will exist much plane in FGP, so that much mathematical information will be lost.


## 3.2. Minimum-Escape Function

As mentioned above, FGP loses much information and contains many flatlands which are very difficult to be managed for an algorithm. Improper handling often brings about additional complexity for solving FGP. One important issue is to design suitable strategies of searching the field far away from the best solutions found so far, aiming to find better solutions or basins. Therefore, a minimum-escape function is proposed to deal with the flatlands, which is designed at the best solutionx∗ found so far as follows:(8)Px,x∗,γ=Sx,x∗-γx-x∗2,where the unique parameter γ>0.Figures5–8 show the properties of the minimum-escape function vividly. Among these figures, one can have intuitive impression of the proposed functions. In Figures 4 and 5, a 2-dimensional example was employed. Figures 6 to 8 illustrate the performance of the minimum-elimination smoothing function on the multimodal function and the performance of the proposed minimum-escape function on the smoothed function. It can be seen vividly from these 3D figures that flattened by the minimum-elimination function, much plane and holes are left. By the constructed function (8), the flattened function will be transformed to an arch-like function with x∗ as its unique global maximal point. From Figures 5 and 8, we can see obviously that the holes still exist in the slope of the minimum-escape functions. These holes may be the same holes of the flattened functions, which are the basins (A basin [16] of f(x) at an isolated minimizer x1∗ is a connected to domain B1 which contains x1∗ and in which starting from any point the steepest descent trajectory of f(x) converges to x1∗ but outside which the steepest descent trajectory of f(x) does not converge to x1∗) of S(x,x∗), which are also the basins of f(x) where the better local optimal solutions locate. Therefore, the aim of the algorithm is to find these holes. We can imagine that a water-drop on this vault will slide down along any direction due to the influence of gravity. Its track might go through some of these holes. Motivated by this phenomenon, we considered that a method can be employed as gravity to guide the search process to find the holes, and another method can be used to find the local optimum. In the following subsection, the properties of the proposed function will be analyzed in detail.Figure 5
2D example: minimum-escape function for the flattened problem (FGP) at the current best solutionx∗.Figure 6
3D example: original function.Figure 7
3D example: flattened by the minimum-elimination function at the current best solutionx∗.Figure 8
3D example: minimum-escape function for the flattened problem (FGP) at the current best solutionx∗.


## 3.3. Properties of Minimum-Escape Function

From Figures4 to 8, it can be seen that the minimum-escape function has the following properties:(1)
x∗ is the unique global maximum of P(x,x∗,γ), and P(x∗,x∗,γ)=f(x∗);(2)
P(x,x∗,γ) has no stationary points in the region S1={x∣f(x)≥f(x∗), x∈D/{x∗}};(3)
ifx∗ is not a global minimizer of f(x), then P(x,x∗,γ) can distinguish the better solution than x∗.To illustrate the properties of the proposed minimum-escape function, we choosex∗ as the reference point and generate the following function as a discrimination function: (9)Jx,x∗,γ=Px,x∗,γ-Px∗,x∗,γx-x∗2x≠x∗γx=x∗.To some degree, J(x,x∗,γ) can be regarded as the slop of P(x,x∗,γ) at x according to the reference point x∗ with x-x∗2. J(x,x∗,γ) can help us understand the properties of P(x,x∗,γ) and also can be used to estimate whether the obtained solutions are better than x∗.Proposition 1.
Iff(x) is continuous, then both S(x,x∗) and P(x,x∗,γ) are continuous.Proposition 2.
Suppose thatx∗ is the best solution found so far. Then, x∗ is the unique global maximizer of P(x,x∗,γ).Proof.
For∀x∈D,(10)Px,x∗,γ=Sx,x∗-γx-x∗2≤f(x∗)-γx-x∗2≤fx∗.
Assume that there exists another pointy≠x∗, such that, for any x∈D, P(x,x∗,γ)≤P(y,x∗,γ). While (11)Py,x∗,γ=Sy,x∗-γy-x∗2≤fx∗-γy-x∗2<fx∗=Px∗,x∗,γ,thus ∃x∗∈D, such that P(y,x∗,γ)<P(x,x∗,γ), which conflicts with the assumption.
Therefore,x∗ is the unique global maximizer of P(x,x∗,γ).Proposition 3.
For∀x∈D, J(x,x∗,γ)≥γ.Proof.
For∀x∈D, it can be concluded from formula (8) that S(x,x∗)≤S(x∗,x∗)=f(x∗). Therefore, for x=x∗, it is obvious that J(x∗,x∗,γ)=γ. For x≠x∗, (12)Jx,x∗,γ=Px∗,x∗,γ-Px,x∗,γx∗-x2=Sx∗,x∗-Sx,x∗x∗-x2+γ≥γ.Proposition 4.
For∀x∈D, (13)fx<fx∗⟺Jx,x∗,γ>γfx≥fx∗⟺Jx,x∗,γ=γ.Proof.
For∀x∈D, if x=x∗, it is obvious that f(x)=f(x∗)⇔J(x,x∗,γ)=γ holds; if x≠x∗, then (14)fx<fx∗⟺Sx,x∗<Sx∗,x∗⟺P(x,x∗,γ)+γx∗-x2<Px∗,x∗,γ⟺Px∗,x∗,γ-Px,x∗,γ>γx∗-x2⟺Px∗,x∗,γ-Px,x∗,γx∗-x2>γ⟺Jx,x∗,γ>γ,fx≥fx∗⟺Sx,x∗=Sx∗,x∗⟺Px,x∗,γ+γx∗-x2=Px∗,x∗,γ⟺Px∗,x∗,γ-Px,x∗,γx∗-x2=γ⟺Jx,x∗,γ=γ.Following Proposition4, it is obvious that better solutions are with larger slop than worse solutions.Denote(15)S0=x∣Jx,x∗,γ=γ,x∈D,S0′=x∣fx≥fx∗,x∈DS1=x∣Jx,x∗,γ>γ,x∈D,S1′=x∣fx<fx∗,x∈D.Then, (16)S0∩S1=S0′∩S1′=ΦS0∪S1=S0′∪S1′=DS0=S0′,S1=S1′.Proposition 5.
Suppose thatB1⊂S1 is a basin of S(x,x∗) and x1∗ is the minimizer in B1, then (17)Jx1∗,x∗,γ=max⁡x∈B1Jx,x∗,γ.Proof.
Follow thatS1=S1′, B1⊂S1′. Consider ∀x∈B1, S(x∗,x∗)>S(x,x∗)≥S(x1∗,x∗), (18)Jx,x∗,γ=Sx∗,x∗-Sx,x∗+γx∗-x2x∗-x2=Sx∗,x∗-Sx,x∗x∗-x2+γ≤Sx∗,x∗-Sx1∗,x∗x∗-x2+γ=Jx1∗,x∗,γ.
Therefore,(19)Jx1∗,x∗,γ=max⁡x∈B1Jx,x∗,γ.According to Proposition5, one might conclude that if x~∗ is the global minimizer of S(x,x∗), then J(x~∗,x∗,γ)=max⁡x∈S1⁡{J(x,x∗,γ)} holds. Unfortunately, this conclusion does not always hold. We will give a counter example to show that the point x~∗, which satisfies J(x~∗,x∗,γ)=max⁡x∈S1⁡{J(x,x∗,γ)}, is not the global minimizer of S(x,x∗). Here, we still use the example function in this section, where x∈[0,10] and the best point is x∗=7.102. In Figure 9, we denote the basins as A and B, which are surrounded by Ellipses A and B, respectively. From Figure 9, it can be seen vividly that the global minimum is included in A, and B is an ordinary basin worse than the global minimum. What is unusual is that J(x,x∗,γ) does not achieve its global maximum at the global minimum of f(x) but achieves its global maximum at a local minimum of f(x) in B. It might seem strange. Next, we will discuss the reason of this strange phenomenon.Figure 9
Minmum-escape function at the best solutionx∗. The dot-line indicates the original function f(x); the black and blue solid line indicate P(x,x∗,γ) and J(x,x∗,γ), respectively.For the convenience of analyzing this phenomenon, the domain of the original problem is expanded toRn and the objective function is supposed to be an uniformly continuous function, which satisfies that, for ∀x∈Rn, ∃M>0 such that |f(x)|≤M. Under this assumption, we can get the following theorems.Proposition 6.
If∃M>0, such that, for ∀x, |f(x)|≤M holds, then (20)limx→∞Jx,x∗,γ=γ.Proof.
Consider(21)limx→+∞Jx,x∗,γ=limx→+∞Px∗,x∗,γ-Px,x∗,γx∗-x2=γ+limx→+∞Sx∗,x∗-Sx,x∗x∗-x2=γ.Proposition 7.
Forx1,x2∈S1, suppose that x1≠x2 and x∗-x12<x∗-x22; if f(x1)=f(x2), then (22)Jx1,x∗,γ>Jx2,x∗,γ.Proof.
Iff(x1)=f(x2), then S(x1,x∗)=S(x2,x∗) and P(x1,x∗,γ)>P(x2,x∗,γ)>γ hold. Then (23)Jx1,x∗,γ=Px∗,x∗,γ-Px1,x∗,γx∗-x12=Px∗,x∗,γ-Px2,x∗,γx∗-x12>Px∗,x∗,γ-Px2,x∗,γx∗-x22=Jx2,x∗,γ.Propositions6 and 7 can explain why this strange phenomenon occurs. Proposition 6 means that, for ∀x∈S1, the further away from x∗, J(x,x∗,γ) will be closer to γ. If x is sufficient far away from x∗, then the value of J(x,x∗,γ) is so close to γ that its variation will be tiny. From Proposition 7, we can infer that the closer a basin is to x∗, the greater J(x,x∗,γ) will change. If a local minimum  x^ is closer to the reference point x∗ than the global minimum x~∗ then J(x^,x∗,γ)>J(x~∗,x∗,γ) might take place.From Propositions1, 2, and 4, it can be seen that the designed minimum-elimination function can efficiently eliminate the solutions worse than the best one found so far. In this way, the original problem can be converted to another global optimization problem sharing the same global optimum, which will be good for solution algorithm to avoid trapping into local minimum. The current best solution can be converted to the global maximizer by the designed minimum-escape function. During the search process, the best solution found so far will not be visited twice. The designed minimum-escape function can help the solution algorithm to explore the whole domain by reducing the objective function value in proportion to the distance to the best solution found so far. And Proposition 4 provides a method to estimate whether the point is better than the current best solution.Estimating the parameterγ is another issue. In most existing auxiliary function methods, estimating parameters is an important and hard task. However, the parameter γ in the proposed function is not sensitive and can be adopted easily. In general, when x∗ is the best solution found so far, the search will go away from x∗. However, when the search goes to a point x far away from x∗ (usually x is away from x∗ in order to jump out the current basin), the main problem arisen will be that γx-x∗ is too large to result in arithmetic overflow. So γ should be small in order to avoid this phenomenon. Thus, in the proposed algorithm, it will be no problem when γ is taken not too large. In this paper, the parameter γ is suggested to be taken in (0,1]. In experiments, the influence of parameter γ will be tested.


## 4. Solution Algorithm

Based on the strategies described above, we design a new minimum-elimination-escape function method, named MEEF for short. In the proposed method, the search process is divided into global search and local search. The gradient-free descent method is employed here to do global search and the gradient-based descent method is employed to do local search. Using gradient-free descent methods can accelerate the speed of finding a better solution, and inaccuracy line searching methods are suggested. The gradient-based descent methods can ensure that the found better solution can be improved to the precise local optima. In the proposed method, Amijo method is employed, and BFGS method is employed to update the found solution.The executable algorithm MEEF is designed as Algorithm8.Algorithm 8.
Minimum-Elimination-Escape Function Method (MEEF)(1)
Given initial pointx0, preset the parameter γ>0. Let i=0.(2)
Start fromxi and use a gradient-based descent method to minimize the original objective function till a local minimum x∗ is obtained; if stop condition is satisfied, stop; otherwise, go to Step 3.(3)
Construct the minimum-escape functionP(x,x∗,γ) according to (8) with respect to x∗ in Step 2. Randomly generate K uniformly distributed vectors ek(k=1~K) on the unit ball; j=0.(4)
Considerj=j+1. Start from x∗ and use a gradient-free method along with direction ej, if there exists a point x′ such that J(x′,x∗,γ)>γ, i=i+1, xi=x′, then go to Step 5; else, go to Step 4.


## 5. Numerical Experiments and Comparison

### 5.1. Benchmark Problems

We choose 19 standard benchmark problems from [3] to [17] to test the performance of the designed algorithms, which are listed in the appendix. In these selected test problems, the dimensions are from 2 to 30. It is needed to point out that although f9 and f10 are almost the same, both of these two test problems were reserved for comprehensive comparison with other methods.


### 5.2. Experimental Settings

In experiments, the algorithm was set as follows.(i)
The Amijo line search method was employed as a gradient-free method to do global search in Step 4, and the BFGS method was taken as a gradient-based method to do the local search in Step 2.(ii)
In Amijo method, the initial step lengthα is adopted as α=max⁡1≤i≤n⁡{Ui-Li}×1.0e-4, where n is the dimension of the problems and L, U are the lower bound and upper bound, respectively.(iii)
The parameterγ=1.0e-4. When analyzing the influence of γ, γ is taken as 1.0e-4 and 1.0e-9, respectively.(iv)
Number of direction vectorsK=2n, where n is the dimension of the problems.(v)
Selection of initial points. In analysis of the influence of parameterγ and initial points, the initial points in experiments are chosen as listed in Tables 2, 3, 4, and 7. In comparison with other methods, the initial point is generated randomly for each test problem.(vi)
Stopping criterion: when|fobtain-fglobal|≤1.0e-10 holds, where fobtain is the function value obtained by our algorithm and fglobal is the known global optimal function value of the test functions, the execution of the algorithm is stopped.


### 5.3. Experimental Results and Comparisons

The proposed algorithm MEEF is essentially a random search method. Its performance needs to be analyzed in different aspects. For an auxiliary function method, its performance is often influenced by its parameters and initial points, which should not be avoided. In numerical experiments, the influences of the parameterγ and the initial points are tested first. Then, comparisons between MEEF and other methods are made.In each of Table2 to Table 8, P represents the related benchmark problem used in this paper, D the dimension of the benchmark problem, FE the number of function evaluations, fmean the mean function value, fbest the best function value, fstd the standard deviation of function value, Succ the ratio of successful runs, and “—” no result reported.


#### 5.3.1. Influence of Parameterγ

For an auxiliary function method, the parameters often influence its performance significantly. Sometimes, improper parameters might inccrease the complexity of the original problems and affect the global search of the algorithm [14]. In order to analyze the influence of parameter γ, we took different values for parameter γ from the suggested interval and used the same initial points in the numerical experiments. Tables 2 and 3 show the results of MEEF using the same initial points with parameter γ=1.0e-4 and 1.0e-9, respectively.From Tables2 and 3, it can be seen obviously that MEEF can find the optimal or close-to-optimal solutions for all test problems with different parameter value. Comparing the results listed in Tables 2 and 3, one can find that, with different parameter value, the MEEF can obtain almost the same results using the same function evaluations. This indicates that taking from the suggested interval, the parameter γ has no big influence for MEEF.


#### 5.3.2. Influence of Initial Points

As well known, the initial point plays an important role for a deterministic optimization method. Auxiliary function methods are a kind of optimization methods which execute deterministic methods repeatedly on the transformed objective function and/or the original objective function to find the global optima of the problems. Thus, It is inevitable that the initial point influences the performance of an auxiliary function method. For another reason, MEEF is essentially a random search method; the initial point might have more influence on its performance. In the experiments, we use different initial points to test their influence. Table4 shows the results of MEEF on the test problems starting from different initial points. From Table 4, we can find that MEEF can find optimal or close-to-optimal solutions for all test problems. Comparing the results listed in Tables 2 and 4, the influence brought by initial points is mainly on the number of function evaluations. At this point, it is reasonable and appears to be very similar to deterministic methods. However, for f17, when the initial point was far away from the global optimal solution, it will take much computational cost and time cost to reach the stopping condition. Sometimes, MEEF failed in finding close-to-optimal solution for f17.Table7 shows the results of MEEF on f16 and f19 with dimension from 2 to 50 starting from different initial points. From same initial points, the number of function evaluations increases with dimension of the problem, which validates intuitionistic deduction on the relationship between function dimension and the number of function evaluations.


#### 5.3.3. Comparisons

For comparison, Ge’s Fill Function method (FF) [3], Levy’s Tunneling function method (Tun) [8], Wang’s auxiliary function method (NAF) [14], the Cut-Peak function method (C-P) [11], SCM method [10], TRUST method [18], Multilevel Single Linkage method (MSL) [19], Diffusion Equation method (DE) [20], Ma’s filled function method (PFFF) [21], and Wei’s filled function methods (NFFA [22] and NFFM [23]) are selected. These methods can find the optimal or close-to-optimal solutions effectively. The results of these methods reported in the related literature are used directly for a comparison. Table 5 presents the results obtained by the proposed algorithm and the compared methods.From Table5 we can see that our algorithm outperforms NFFM, NFFA, PFFF, and the cut-peak function method. Comparing the results listed in Tables 2 and 3 with the results of C-P method reported in [11], NFFA in [22] and NFFM in [23], it can be seen that MEEF can find better solutions using much fewer function evaluations starting from different initial points for all test problems. Also, the termination precision of MEEF is much higher than that of both C-P methods, NFFA and NFFM.So as to compare with NFFA in detail, we executed our proposed method MEEF onf14 with different dimensions according to [22]. The comparison results are shown in Table 6. Table 6 shows vividly that MEEF can find the close-to-optimal solutions of f14 successfully for all dimensions in experiments. The precision of the results obtained by MEEF is much higher than that of NFFA. However, when the dimension is more than 12, the function evaluation numbers of MEEF are lager than NFFA, which shows that NFFA outperforms MEEF. It is worth mentioning that the stopping precision of NFFA is set to be 1.0e-3, which is much larger than that of MEEF. Also, NFFA cannot obtain the approximate optimal solutions successfully in each run. What is more, the parameter of NFFA was needed to be adjusted according to dimensions and problems as reported in [22]. MEEF does not need to adjust its parameter specially. Thus, it is easy to conclude that MEEF outperforms NFFA over stability and validity.Compared with Wang’s auxiliary function method NAF, MEEF outperforms this method onf3, f7, and f10 from Table 5. However, from Table 8, it can be seen obviously that MEEF outperforms NAF on f16 and f19 with dimension from 2 to 50.From Table5, one can see that the performance of MEEF equals that of SCM. But for f13, MEEF could find the global optimal solution successfully, and SCM failed. For other methods, MEEF has much better performance.Since only the number of function evaluations of the methods listed in Table5 is reported in the related papers, we compared the number of function evaluations with that of the methods listed in Table 5. From Tables 2, 4, and 5, it can be seen obviously that the proposed algorithm outperforms the compared method in Table 5. Compared with Wang’s method, the proposed method uses fewer function evaluations on f2, f7, f9, f10~13. The proposed method outperforms SCM except f1. And the proposed method outperforms other methods on function evaluations of the problems listed in Table 5.Numerical experiments on the problemsf16 and f19 with dimensions from 2 to 50 were made by Zhu et al. [10] and Wang et al. [14] to evaluate the performance of their methods. In this paper, we do the same experimental settings for f16 and f19 as in [10, 14] to fair comparison, and the results can be found in Tables 7 and 8. In experiments, the proposed algorithm was executed with two different initial points for each of f16 and f19 and terminated when |fobtain-fglobal|<1.0e-10 holds. The final obtained solutions and numbers of function evaluations are recorded in Table 7. For f16, it can be seen vividly that the influence of initial points is obvious not only on the number of function evaluations but also on the precision of the results. During the experiments on f16, our algorithm could obtain the global optimum starting with other different initial points. For f19, it can be seen from Table 7 that both numbers of function evaluations and obtained solutions are with no great difference for MEEF starting with two selected initial points. However, it should be pointed out that MEEF can find the global solution with the preset precision with 90% success in 30 runs when the initial points were taken as x0=(50,…,50) and x0=(100,…,100). This indicates that the performance of MEEF on f19 is influenced by the initial points greatly.In the following experiments, the precision forf19 was set to be 1.0×10-1 which was the same as that of NAF [14], and the initial points were taken randomly. From Table 8, it can be seen that MEEF outperforms other 4 methods on the number of function evaluations obviously form f16. But for f19, the comparison results seem to be a little complex. MEEF uses fewer function evaluations than NAF in 15 test cases. From Table 8, it can be seen that SCM seems to have better performance than MEEF on f19. It should be pointed out that in [10], the precision of the obtained results was not mentioned. Thus, we can not judge which one has better performance. For the tunneling function method [8], only 4 test cases were executed without any solution precision. We can not do comprehensive comparison.


#### 5.3.4. A Phenomenon for Discussion

Careful readers might find a strange phenomenon in Table8. That is the number of function evaluations of SCM and NAF on f16 and f19 does not present promptly increasing trend with the increasing of the dimension. The number of function evaluations varies greatly. For example, for f19, NAF uses 14956 function evaluations to obtain the global solution with the preset precision when the problem dimension is 21. While the number of function evaluations is down sharply to 93 when the dimension is 22. This phenomenon is against our intuitive idea that the number of function evaluations increases with the dimension of the problem. In traditional opinion, the higher the dimension is, the more local optimum there will be which will take much computational cost. It might be a strange and interesting topic that why this unreasonable phenomenon happened.


## 5.1. Benchmark Problems

We choose 19 standard benchmark problems from [3] to [17] to test the performance of the designed algorithms, which are listed in the appendix. In these selected test problems, the dimensions are from 2 to 30. It is needed to point out that although f9 and f10 are almost the same, both of these two test problems were reserved for comprehensive comparison with other methods.


## 5.2. Experimental Settings

In experiments, the algorithm was set as follows.(i)
The Amijo line search method was employed as a gradient-free method to do global search in Step 4, and the BFGS method was taken as a gradient-based method to do the local search in Step 2.(ii)
In Amijo method, the initial step lengthα is adopted as α=max⁡1≤i≤n⁡{Ui-Li}×1.0e-4, where n is the dimension of the problems and L, U are the lower bound and upper bound, respectively.(iii)
The parameterγ=1.0e-4. When analyzing the influence of γ, γ is taken as 1.0e-4 and 1.0e-9, respectively.(iv)
Number of direction vectorsK=2n, where n is the dimension of the problems.(v)
Selection of initial points. In analysis of the influence of parameterγ and initial points, the initial points in experiments are chosen as listed in Tables 2, 3, 4, and 7. In comparison with other methods, the initial point is generated randomly for each test problem.(vi)
Stopping criterion: when|fobtain-fglobal|≤1.0e-10 holds, where fobtain is the function value obtained by our algorithm and fglobal is the known global optimal function value of the test functions, the execution of the algorithm is stopped.


## 5.3. Experimental Results and Comparisons

The proposed algorithm MEEF is essentially a random search method. Its performance needs to be analyzed in different aspects. For an auxiliary function method, its performance is often influenced by its parameters and initial points, which should not be avoided. In numerical experiments, the influences of the parameterγ and the initial points are tested first. Then, comparisons between MEEF and other methods are made.In each of Table2 to Table 8, P represents the related benchmark problem used in this paper, D the dimension of the benchmark problem, FE the number of function evaluations, fmean the mean function value, fbest the best function value, fstd the standard deviation of function value, Succ the ratio of successful runs, and “—” no result reported.


### 5.3.1. Influence of Parameterγ

For an auxiliary function method, the parameters often influence its performance significantly. Sometimes, improper parameters might inccrease the complexity of the original problems and affect the global search of the algorithm [14]. In order to analyze the influence of parameter γ, we took different values for parameter γ from the suggested interval and used the same initial points in the numerical experiments. Tables 2 and 3 show the results of MEEF using the same initial points with parameter γ=1.0e-4 and 1.0e-9, respectively.From Tables2 and 3, it can be seen obviously that MEEF can find the optimal or close-to-optimal solutions for all test problems with different parameter value. Comparing the results listed in Tables 2 and 3, one can find that, with different parameter value, the MEEF can obtain almost the same results using the same function evaluations. This indicates that taking from the suggested interval, the parameter γ has no big influence for MEEF.


### 5.3.2. Influence of Initial Points

As well known, the initial point plays an important role for a deterministic optimization method. Auxiliary function methods are a kind of optimization methods which execute deterministic methods repeatedly on the transformed objective function and/or the original objective function to find the global optima of the problems. Thus, It is inevitable that the initial point influences the performance of an auxiliary function method. For another reason, MEEF is essentially a random search method; the initial point might have more influence on its performance. In the experiments, we use different initial points to test their influence. Table4 shows the results of MEEF on the test problems starting from different initial points. From Table 4, we can find that MEEF can find optimal or close-to-optimal solutions for all test problems. Comparing the results listed in Tables 2 and 4, the influence brought by initial points is mainly on the number of function evaluations. At this point, it is reasonable and appears to be very similar to deterministic methods. However, for f17, when the initial point was far away from the global optimal solution, it will take much computational cost and time cost to reach the stopping condition. Sometimes, MEEF failed in finding close-to-optimal solution for f17.Table7 shows the results of MEEF on f16 and f19 with dimension from 2 to 50 starting from different initial points. From same initial points, the number of function evaluations increases with dimension of the problem, which validates intuitionistic deduction on the relationship between function dimension and the number of function evaluations.


### 5.3.3. Comparisons

For comparison, Ge’s Fill Function method (FF) [3], Levy’s Tunneling function method (Tun) [8], Wang’s auxiliary function method (NAF) [14], the Cut-Peak function method (C-P) [11], SCM method [10], TRUST method [18], Multilevel Single Linkage method (MSL) [19], Diffusion Equation method (DE) [20], Ma’s filled function method (PFFF) [21], and Wei’s filled function methods (NFFA [22] and NFFM [23]) are selected. These methods can find the optimal or close-to-optimal solutions effectively. The results of these methods reported in the related literature are used directly for a comparison. Table 5 presents the results obtained by the proposed algorithm and the compared methods.From Table5 we can see that our algorithm outperforms NFFM, NFFA, PFFF, and the cut-peak function method. Comparing the results listed in Tables 2 and 3 with the results of C-P method reported in [11], NFFA in [22] and NFFM in [23], it can be seen that MEEF can find better solutions using much fewer function evaluations starting from different initial points for all test problems. Also, the termination precision of MEEF is much higher than that of both C-P methods, NFFA and NFFM.So as to compare with NFFA in detail, we executed our proposed method MEEF onf14 with different dimensions according to [22]. The comparison results are shown in Table 6. Table 6 shows vividly that MEEF can find the close-to-optimal solutions of f14 successfully for all dimensions in experiments. The precision of the results obtained by MEEF is much higher than that of NFFA. However, when the dimension is more than 12, the function evaluation numbers of MEEF are lager than NFFA, which shows that NFFA outperforms MEEF. It is worth mentioning that the stopping precision of NFFA is set to be 1.0e-3, which is much larger than that of MEEF. Also, NFFA cannot obtain the approximate optimal solutions successfully in each run. What is more, the parameter of NFFA was needed to be adjusted according to dimensions and problems as reported in [22]. MEEF does not need to adjust its parameter specially. Thus, it is easy to conclude that MEEF outperforms NFFA over stability and validity.Compared with Wang’s auxiliary function method NAF, MEEF outperforms this method onf3, f7, and f10 from Table 5. However, from Table 8, it can be seen obviously that MEEF outperforms NAF on f16 and f19 with dimension from 2 to 50.From Table5, one can see that the performance of MEEF equals that of SCM. But for f13, MEEF could find the global optimal solution successfully, and SCM failed. For other methods, MEEF has much better performance.Since only the number of function evaluations of the methods listed in Table5 is reported in the related papers, we compared the number of function evaluations with that of the methods listed in Table 5. From Tables 2, 4, and 5, it can be seen obviously that the proposed algorithm outperforms the compared method in Table 5. Compared with Wang’s method, the proposed method uses fewer function evaluations on f2, f7, f9, f10~13. The proposed method outperforms SCM except f1. And the proposed method outperforms other methods on function evaluations of the problems listed in Table 5.Numerical experiments on the problemsf16 and f19 with dimensions from 2 to 50 were made by Zhu et al. [10] and Wang et al. [14] to evaluate the performance of their methods. In this paper, we do the same experimental settings for f16 and f19 as in [10, 14] to fair comparison, and the results can be found in Tables 7 and 8. In experiments, the proposed algorithm was executed with two different initial points for each of f16 and f19 and terminated when |fobtain-fglobal|<1.0e-10 holds. The final obtained solutions and numbers of function evaluations are recorded in Table 7. For f16, it can be seen vividly that the influence of initial points is obvious not only on the number of function evaluations but also on the precision of the results. During the experiments on f16, our algorithm could obtain the global optimum starting with other different initial points. For f19, it can be seen from Table 7 that both numbers of function evaluations and obtained solutions are with no great difference for MEEF starting with two selected initial points. However, it should be pointed out that MEEF can find the global solution with the preset precision with 90% success in 30 runs when the initial points were taken as x0=(50,…,50) and x0=(100,…,100). This indicates that the performance of MEEF on f19 is influenced by the initial points greatly.In the following experiments, the precision forf19 was set to be 1.0×10-1 which was the same as that of NAF [14], and the initial points were taken randomly. From Table 8, it can be seen that MEEF outperforms other 4 methods on the number of function evaluations obviously form f16. But for f19, the comparison results seem to be a little complex. MEEF uses fewer function evaluations than NAF in 15 test cases. From Table 8, it can be seen that SCM seems to have better performance than MEEF on f19. It should be pointed out that in [10], the precision of the obtained results was not mentioned. Thus, we can not judge which one has better performance. For the tunneling function method [8], only 4 test cases were executed without any solution precision. We can not do comprehensive comparison.


### 5.3.4. A Phenomenon for Discussion

Careful readers might find a strange phenomenon in Table8. That is the number of function evaluations of SCM and NAF on f16 and f19 does not present promptly increasing trend with the increasing of the dimension. The number of function evaluations varies greatly. For example, for f19, NAF uses 14956 function evaluations to obtain the global solution with the preset precision when the problem dimension is 21. While the number of function evaluations is down sharply to 93 when the dimension is 22. This phenomenon is against our intuitive idea that the number of function evaluations increases with the dimension of the problem. In traditional opinion, the higher the dimension is, the more local optimum there will be which will take much computational cost. It might be a strange and interesting topic that why this unreasonable phenomenon happened.


## 5.3.1. Influence of Parameterγ

For an auxiliary function method, the parameters often influence its performance significantly. Sometimes, improper parameters might inccrease the complexity of the original problems and affect the global search of the algorithm [14]. In order to analyze the influence of parameter γ, we took different values for parameter γ from the suggested interval and used the same initial points in the numerical experiments. Tables 2 and 3 show the results of MEEF using the same initial points with parameter γ=1.0e-4 and 1.0e-9, respectively.From Tables2 and 3, it can be seen obviously that MEEF can find the optimal or close-to-optimal solutions for all test problems with different parameter value. Comparing the results listed in Tables 2 and 3, one can find that, with different parameter value, the MEEF can obtain almost the same results using the same function evaluations. This indicates that taking from the suggested interval, the parameter γ has no big influence for MEEF.


## 5.3.2. Influence of Initial Points

As well known, the initial point plays an important role for a deterministic optimization method. Auxiliary function methods are a kind of optimization methods which execute deterministic methods repeatedly on the transformed objective function and/or the original objective function to find the global optima of the problems. Thus, It is inevitable that the initial point influences the performance of an auxiliary function method. For another reason, MEEF is essentially a random search method; the initial point might have more influence on its performance. In the experiments, we use different initial points to test their influence. Table4 shows the results of MEEF on the test problems starting from different initial points. From Table 4, we can find that MEEF can find optimal or close-to-optimal solutions for all test problems. Comparing the results listed in Tables 2 and 4, the influence brought by initial points is mainly on the number of function evaluations. At this point, it is reasonable and appears to be very similar to deterministic methods. However, for f17, when the initial point was far away from the global optimal solution, it will take much computational cost and time cost to reach the stopping condition. Sometimes, MEEF failed in finding close-to-optimal solution for f17.Table7 shows the results of MEEF on f16 and f19 with dimension from 2 to 50 starting from different initial points. From same initial points, the number of function evaluations increases with dimension of the problem, which validates intuitionistic deduction on the relationship between function dimension and the number of function evaluations.


## 5.3.3. Comparisons

For comparison, Ge’s Fill Function method (FF) [3], Levy’s Tunneling function method (Tun) [8], Wang’s auxiliary function method (NAF) [14], the Cut-Peak function method (C-P) [11], SCM method [10], TRUST method [18], Multilevel Single Linkage method (MSL) [19], Diffusion Equation method (DE) [20], Ma’s filled function method (PFFF) [21], and Wei’s filled function methods (NFFA [22] and NFFM [23]) are selected. These methods can find the optimal or close-to-optimal solutions effectively. The results of these methods reported in the related literature are used directly for a comparison. Table 5 presents the results obtained by the proposed algorithm and the compared methods.From Table5 we can see that our algorithm outperforms NFFM, NFFA, PFFF, and the cut-peak function method. Comparing the results listed in Tables 2 and 3 with the results of C-P method reported in [11], NFFA in [22] and NFFM in [23], it can be seen that MEEF can find better solutions using much fewer function evaluations starting from different initial points for all test problems. Also, the termination precision of MEEF is much higher than that of both C-P methods, NFFA and NFFM.So as to compare with NFFA in detail, we executed our proposed method MEEF onf14 with different dimensions according to [22]. The comparison results are shown in Table 6. Table 6 shows vividly that MEEF can find the close-to-optimal solutions of f14 successfully for all dimensions in experiments. The precision of the results obtained by MEEF is much higher than that of NFFA. However, when the dimension is more than 12, the function evaluation numbers of MEEF are lager than NFFA, which shows that NFFA outperforms MEEF. It is worth mentioning that the stopping precision of NFFA is set to be 1.0e-3, which is much larger than that of MEEF. Also, NFFA cannot obtain the approximate optimal solutions successfully in each run. What is more, the parameter of NFFA was needed to be adjusted according to dimensions and problems as reported in [22]. MEEF does not need to adjust its parameter specially. Thus, it is easy to conclude that MEEF outperforms NFFA over stability and validity.Compared with Wang’s auxiliary function method NAF, MEEF outperforms this method onf3, f7, and f10 from Table 5. However, from Table 8, it can be seen obviously that MEEF outperforms NAF on f16 and f19 with dimension from 2 to 50.From Table5, one can see that the performance of MEEF equals that of SCM. But for f13, MEEF could find the global optimal solution successfully, and SCM failed. For other methods, MEEF has much better performance.Since only the number of function evaluations of the methods listed in Table5 is reported in the related papers, we compared the number of function evaluations with that of the methods listed in Table 5. From Tables 2, 4, and 5, it can be seen obviously that the proposed algorithm outperforms the compared method in Table 5. Compared with Wang’s method, the proposed method uses fewer function evaluations on f2, f7, f9, f10~13. The proposed method outperforms SCM except f1. And the proposed method outperforms other methods on function evaluations of the problems listed in Table 5.Numerical experiments on the problemsf16 and f19 with dimensions from 2 to 50 were made by Zhu et al. [10] and Wang et al. [14] to evaluate the performance of their methods. In this paper, we do the same experimental settings for f16 and f19 as in [10, 14] to fair comparison, and the results can be found in Tables 7 and 8. In experiments, the proposed algorithm was executed with two different initial points for each of f16 and f19 and terminated when |fobtain-fglobal|<1.0e-10 holds. The final obtained solutions and numbers of function evaluations are recorded in Table 7. For f16, it can be seen vividly that the influence of initial points is obvious not only on the number of function evaluations but also on the precision of the results. During the experiments on f16, our algorithm could obtain the global optimum starting with other different initial points. For f19, it can be seen from Table 7 that both numbers of function evaluations and obtained solutions are with no great difference for MEEF starting with two selected initial points. However, it should be pointed out that MEEF can find the global solution with the preset precision with 90% success in 30 runs when the initial points were taken as x0=(50,…,50) and x0=(100,…,100). This indicates that the performance of MEEF on f19 is influenced by the initial points greatly.In the following experiments, the precision forf19 was set to be 1.0×10-1 which was the same as that of NAF [14], and the initial points were taken randomly. From Table 8, it can be seen that MEEF outperforms other 4 methods on the number of function evaluations obviously form f16. But for f19, the comparison results seem to be a little complex. MEEF uses fewer function evaluations than NAF in 15 test cases. From Table 8, it can be seen that SCM seems to have better performance than MEEF on f19. It should be pointed out that in [10], the precision of the obtained results was not mentioned. Thus, we can not judge which one has better performance. For the tunneling function method [8], only 4 test cases were executed without any solution precision. We can not do comprehensive comparison.


## 5.3.4. A Phenomenon for Discussion

Careful readers might find a strange phenomenon in Table8. That is the number of function evaluations of SCM and NAF on f16 and f19 does not present promptly increasing trend with the increasing of the dimension. The number of function evaluations varies greatly. For example, for f19, NAF uses 14956 function evaluations to obtain the global solution with the preset precision when the problem dimension is 21. While the number of function evaluations is down sharply to 93 when the dimension is 22. This phenomenon is against our intuitive idea that the number of function evaluations increases with the dimension of the problem. In traditional opinion, the higher the dimension is, the more local optimum there will be which will take much computational cost. It might be a strange and interesting topic that why this unreasonable phenomenon happened.


## 6. Conclusions

In this paper, a new minimum-elimination-escape function method for global optimization is proposed, which can avoid the “Mexican hat” efficiently. In the proposed method, the minimum-elimination function is constructed to eliminate the solutions worse than the best one found so far. In this way, the influence brought by the local optimum will be reduced. Flattened by the minimum-elimination function, the original problem can be transformed to another optimization problem, which shares the same global optimum with the original problem with fewer local optimum. A new minimum-escape function with one parameter is constructed for the flattened problem. The properties of minimum-escape function are analyzed theoretically. Based on the two proposed functions, a minimum-elimination-escape function method for multimodal optimization is constructed. Theoretical analysis and experimental results indicate that the minimum-elimination-escape function method is insensitive to its unique parameter, which can be set easily. In the experiments, the proposed algorithm can find the global optimal solutions of all 19 selected problems. The numerical experimental results show that the proposed algorithm can converge rapidly to the global optimum with high precision. Compared with 11 existing methods, we found that the proposed algorithm performs much more stably and effectively.



---

*Source: 782536-2015-03-30.xml*