Minimization of Keane’s Bump Function by the Repulsive Particle Swarm

and the Differential Evolution Methods

 

SK Mishra

Department of Economics

North-Eastern Hill University

Shillong (India)

 

I. Introduction: Andy Keane (1994) designed the “bump” function to test the performance of (constrained) optimization methods. The optimization problem of Keane’s bump function may be presented (Keane, 1994) as follows:

 

subject to:

Fig.-1: Keane’s Bump Function in 2 Dimensions	A visual appreciation of Keane’s two-dimensional (m=2) bump function may be obtained from the graphical presentation (Fig.-1; Hacker et al., 2002). As the dimension (m) grows larger, the optimum value of the function becomes more and more difficult to obtain. Keane (1994) observed that for m=20 the value of min[f(x)] could be about -0.76 and for m=50 it could be about -0.835 but did not know this to be the case.               Keane’s bump function is considered as a standard benchmark for nonlinear constrained optimization. It is highly multi-modal and its optimum is located at the non-linear constrained boundary. Emmerich (2005, p. 116) noted that the true minimum of this function is unknown. Using their various hybridized Genetic Algorithms Hacker et al. (2002) obtained min[f(x)] = -0.365 for a 2-dimensional and -0.6737 for a 10-dimensional Keane’s problem. They also found that the Genetic Algorithms (without hybridization) perform worse than their hybridized Genetic Algorithms.
Source: Hacker, Eddy and Lewis (2002)

 

II. The Objectives of this Paper: We intend in this paper to optimize Keane’s function of different dimensions by the Repulsive Particle Swarm (RPS) and the Differential Evolution (DE) methods of global optimization. Our RPS is endowed with intensive local search ability. Similarly, our DE uses the most recent (available) formulation of crossover scheme suggested by Kenneth Price. We have developed our own computer programs in FORTRAN. Our programs have yielded very good results for quite varied and difficult problems (Mishra, 2006 (a, b & c)). Programs are available on request*.

 

III. Results and Discussion: First we obtain min[f(x)] for the two-dimensional (m=2) Keane’s problem. We have DE min[(f)] =  -0.364979746;  g₁(x) = -1.11022302E-016 and   g₂(x) = -11.9306415 for x₁ = 1.60086044  and x₂ = 0.468498055. Against this, RPS min[(f)] =  -0.364979123;  g₁(x) =  -3.82208509E-007; g₂(x) = -11.9310703 for x₁ = 1.60025376  and  x₂ = 0.468675907. These results are comparable with the optimum value obtained by Hacker et al. The DE results are marginally better than the RPS results.

 

Emmerich (2005, p. 118) obtained about -0.6 as the minimum value of the 10-dimensional Keane problem. Hacker et al.  report to have obtained  min[f(x)] = -0.6737. We have obtained the DE min[(f)] = -0.747310362;  g₁(x) = -2.2849167E-011 and  g₂(x) = -58.5724568 for x given in Table-1(a). Against these we obtained by RPS method min[(f)] = -0.747309014;  g₁(x) =  -4.64514816E-009;  and g₂(x)  = -58.5732418  for x given in Table-1(b). Again, the DE performs better than the RPS.

 

 

 

 

            For the 10-dimensional problem, evidently, our results are much better than those obtained by Hacker et al. by their hybridized Genetic Algorithm, which, in themselves are better than the (pure) Genetic algorithm results. They have not presented the values taken on by the decision variables (x). However, the values of x in our results indicate, first, that  . This particular observation is very important, although it is just a conjecture. A sub-optimal solution would not have such a sequence. Secondly, we conjecture that the values form two clusters with almost the same number of members.

 

            For the 15-dimensional Keane’s problem we have DE min[(f)] = -0.781647601;  g₁(x) =  -5.18851406E-010; g₂(x) =  -88.5890866. The decision variables take on the following values given in Table-2(a).  Against these values of DE we have RPS min[(f)] = -0.778452035;  g₁(x) =  -1.42940888E-005; g₂(x) =  -88.6245989 for  x given in Table-2(b) below. The RPS results are inferior to the DE results. The noted sequence is not given by the RPS results. The values of x₇ and x₈ have broken the said sequence.

 

 

 

For the 20-dimensional Keane’s problem we have DE min[(f)] = -0.803619104;  g₁(x) =  -4.95659069E-012; g₂(x) =  -119.067416. The decision variables take on the following values given in Table-3(a).  We obtain the RPS min[(f)] = -0.785263489; g₁(x) =   -2.13415866E-005; g₂(x) =    -117.548076 for the values of x given in Table-3(b).

 

 

 

            We note that the DE results obey the observed rule of sequence while the RPS results, which are sub-optimal, do not obey the said rule. We also note that while Keane (1994) observed that for m=20 the value of min[f(x)] could be about -0.76, we obtain DE min[(f)] = -0.803619104. This result is surely better than the one envisaged by Keane. However, Ong and Keane (2003, p. 12) and Ong et al. (2005 ?) mention that the minimal value obtained by them is approximately –0.81. If it is so, we have not been able to obtain the minimum value of the function. Keane in his personal letter (email dated 4.5.2007) informed the author that the best value for m=20 known to him till date is -0.803619104.

 

 

 For the 30-dimensional Keane’s problem we have DE min[(f)] = -0.818056222;  g₁(x) =  -1.90829275E-009; g₂(x) =   -177.357354. The decision variables take on the values given in Table-4. The RPS results are grossly sub-optimal and hence we do not present them.

 

For the 40-dimensional Keane’s problem we have DE min[(f)] =  -0.826624404;  g₁(x) =  -4.67459549E-009; g₂(x) =    -237.241084. The decision variables take on the following values given in Table-5. The RPS results are grossly sub-optimal and hence we do not present them.

 

 

 Optimization of the 50-dimensional Keane’s problem was problematic. We had to do some fine-tuning of the DE parameters and some trial and error too. Finally, [for RX1=0.5, RX2=0.7 and F =0.05: these are detailed out in the DE program written by us] we have DE min[(f)] =  -0.83078783;  g₁(x) = -2.55134022E-008; g₂(x) =  -297.149824. The decision variables take on the following values given in Table-6. The RPS results are grossly sub-optimal and hence we do not present them

 

 

Keane (1994) mentioned that for m=50 min[(f)] could be around –0.835. The number obtained by us is  -0.83078783 (and the decision variables satisfy the sequence noted earlier). We cannot claim that the sequence conjectured by us provides the necessary and sufficient condition for optimality of values taken on by the decision variables, although the condition appears to be necessary. Keane in his personal letter (email dated 4.5.2007) informed the author that the best value known to him for m=50 till date is: -0.835262348.

IV. A Useful Application of Our Conjecture: Now we make an attempt to (possibly) take advantage of our conjecture on the pattern exhibited by the values of decision variable so far. That is: . Before every function evaluation we arrange the values of the decision variables in a descending order and then evaluate the Keane’s function (and the constraints). We find, to our pleasant surprise, that it works well and gives a new minimum (for m=50), which is very close to the value () envisaged by Keane. Now, after incorporating our conjecture in the computation, we obtain: DE min[(f)] = -0.834985126 and g₁(x) = -9.86513138E-009; g₂(x) =  -294.382754. The decision variables take on the values given in Table-7. The RPS results are close to the DE results, but sub-optimal. The RPS min[(f)]= -0.83181972; g₁(x)= -3.97261395E-05; g₂(x) = -292.704914.

 

 

It has been mentioned earlier that Ong and Keane (2003, p. 12) and Ong et al. (2005 ?) report that the minimal value obtained by them is approximately –0.81 (for m=20). With the success experience due to incorporating our conjecture (in case of m=50) we are tempted to re-compute the min[(f)] for m=20. However, we have not been able to obtain any better results (than  -0.803619104, reported earlier).

 

For m=60, we obtain DE min[(f)] =  -0.835835669;  g₁(x) = -6.7704109E-010; g₂(x) = -352.652189. The decision variables take on the following values given in Table-8(a). In this case, however, the RPS results are better than the DE results. We obtain RPS min[(f)] = -0.837746743. The values of the decision variables are given in Table-8(b).

 

 

 

Finally we have run DE to optimize the Keane function for m=100. We would also like to mention that we used 4321 as the initial seed for generating the random numbers; population size = 1000; pcross=0.9; fact=0.05 and 5677 as the second random number seed in the DE subroutine. These inputs/parameters are defined in our computer program. We also used our conjecture to arrange x in a descending order   We obtained DE min[(f)] = -0.844219651;, g₁(x) = -2.51972313E-008; g₂(x) =   -586.659534. Values of x are presented in Table-9(a) below.

 

 

We have run the RPS with random seed=7337. The RPS min[(f)] = -0.84246233;  g₁(x) = -0.000523752645; g₂(x) =  -587.939518, which is inferior to the DE min[(f)]. The values of x are presented in Table-9(b). It appears that arranging the values of decision variables in descending order affects the performance of the DE as well as the RPS unpredictably, although it is difficult to generalize such an observation. Further, we do not claim that for m=100 our DE results are the best, although one may note that Liu and Lewis (2002) obtained –0.84421 and  –0.8448539 for m=200 and m=1000 respectively. Our results for m=100 (min(f) = -0.844219651) is smaller than Liu-Lewis’ –0.84421 for m=200, which is anomalous.  Thus, Liu-Lewis’ min(f) for m=200  is grossly sub-optimal.

 

 

V. Minimization of Keane Function with Odd Number of Variables: Do the properties of Keane problem depend on whether its dimension is odd or oddly chosen? We have (arbitrarily) chosen some odd numbers; 17, 23, 27, 35, 43 and 47 to study the behavior of Keane function. We have ignored small dimensions like 3, 7, etc. For m=5 we have DE min[(f)=-0.634448687, g₁(x) = -4.4408921E-016, g₂(x) =-28.4863914 for x = (3.07581932,  2.99199522,  1.47579373,  0.236691358,  0.233308996). A perusal of the following tables - 10 (a, b) through 15 (a, b) - reveals that it is not so. Hence, we conclude that the minimum values of the problem monotonously decline with the increase in the dimension of Keane problem.

 

 

 

 

 

 

 

 

 

 

 

 

 

VI. Conclusion: A not-so-exhaustive survey of literature on optimization of Keane’s               function suggests us that many researchers avoid mentioning the values of objective function, constraints and decision variables that they obtained in their works. They mention that the program, method or algorithm used by them was repeated so-and-so many times. However, they have hesitated to mention the range – the upper and the lower limits – within which they had obtained their results. Measures like mean, median or standard deviation only blur the findings and perhaps conceal much more than they reveal.  If Emmerich (2005) is right in stating that the true minima of Keane’s function for different dimensions are unknown, it is required that the research efforts of each of us are recorded clearly, accurately and with necessary details so that the next research worker knows what his (or her) efforts are yielding. In this paper we have provided the details to set the records right. A summary of our results is presented in Table-16.

Table-16. Minimum Values of Keane’s Function of Different Dimensions Obtained in this Study Dim Min[f(x)] Dim Min[f(x)] Dim Min[f(x)] Dim Min[f(x)] 2 -0.36498 17 -0.79151 30 -0.81806 47 -0.83330 5 -0.63445 20 -0.80362 35 -0.82528 50 -0.83499 10 -0.74731 23 -0.81004 40 -0.82662 60 -0.83775 15 -0.78165 27 -0.81694 43 -0.83226 100 -0.84422

We also conjectured that values of the decision variables diminish with the increasing index, that is,  and they form two distinct clusters with almost equal number of members. These regularities indicate whether   the function could attain a minimum or (at least) has reached

close to the minimum. They may also be exploited to seek the minimum values of the function.  The Differential Evolution (DE)  program (developed by us) has gone a long way to obtain the optimum (if so!) results. Application of the Particle Swarm optimization program (developed by us) has clearly failed to minimize Keane’s function of any considerable size, without arranging the variable values in a descending order. On ordering the variable values, the RPS results are comparable with those of the DE. The DE also needed ordering of variable values to perform when the size of the problem was larger. Our two findings are notable: (i) Keane’s envisaged min(f) = -0.835 for 50-dimensional problem is realizable by the RPS as well as the DE; (ii)  Liu-Lewis’ min(f) = -0.84421 for 200-dimensional problem is grossly sub-optimal.

 

            Finally, although Keane disfavors ordering of variables to obtain a minimum (since such ‘tricks’ lead to over-estimation of the efficiency of an optimizing program), such a trick, nonetheless, gives us new lower bounds of the function that might stimulate further improvements in different optimization procedures. We hold that our investigation should have two objectives: (a) obtaining the most efficient optimizers; (b) obtaining new lower bounds of the function for different dimensions.

 

References

 

• Emmerich, MTM: Single- and Multi-objective Evolutionary Design Optimization Assisted by Gaussian Random Field Metamodels, Dissertation for Doctoral Degree in Natural Sciences, University of Dortmund, Dortmund. 2005. 
• Hacker, KA, Eddy, J and Lewis, KE: “Efficient Global Optimization using Hybrid Genetic Algorithms,” in 9^th AIAA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, Atlanta, Georgia, 4-6 September 2002.
• Keane, AJ:  “Bump: A Hard(?)  Problem” http://www.soton.ac.uk/~ajk/bump.html, 1994.
• Keane, AJ: "Experiences with optimizers in structural design," in Parmee, IC (ed) Proceedings of the 1st Conf. on Adaptive Computing in Engineering Design and Control, University of Plymouth, UK, pp. 14-27, 1994.
• Liu, P and Lewis, MJ: “Communication Aspects of an Asynchronous Parallel Evolutionary Algorithm”, Proceedings of the Third International Conference on Communications in Computing (CIC 2002), pp. 190-195, Las Vegas, NV, June 24-27, 2002. http://grid.cs.binghamton.edu/papers/LiuAPEAComm_CIC.pdf
• Mishra, SK (a): "Global Optimization by Particle Swarm Method: A Fortran Program" (August 1, 2006). Available at SSRN: http://ssrn.com/abstract=921504
• Mishra, SK (b): "Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions" (September 30, 2006). Available at SSRN: http://ssrn.com/abstract=933827
• Mishra, SK (c): "Performance of Differential Evolution and Particle Swarm Methods on Some Relatively Harder Multi-Modal Benchmark Functions" (October 13, 2006). Available at SSRN: http://ssrn.com/abstract=937147
• Ong, YS and Keane, AJ:  “Meta-Lamarckian Learning in Memetic Algorithms” http://ntu-cg.ntu.edu.sg/ysong/journal/IEEE_EC_Ysong2003.pdf, 2003.
• Ong, YS,  Lim, MH, Zhu, N and Wong, KW: “Classification of Adaptive Memetic Algorithms: A Comparative Study”, Un-dated (possibly written in 2005) working paper,    http://ntu-cg.ntu.edu.sg/ysong/journal/AdaptiveMA.pdf