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; g1(x) = -1.11022302E-016 and g2(x) = -11.9306415 for x1 = 1.60086044 and x2 = 0.468498055. Against this, RPS min[(f)] = -0.364979123; g1(x) = -3.82208509E-007; g2(x) = -11.9310703 for x1 = 1.60025376 and x2 = 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; g1(x) = -2.2849167E-011 and g2(x) = -58.5724568 for x given in Table-1(a). Against these we obtained by RPS method min[(f)] = -0.747309014; g1(x) = -4.64514816E-009; and g2(x) = -58.5732418 for x given in Table-1(b). Again, the DE performs better than the RPS.
|
Table-1(a). Values of Decision Variables of Keane (m=10) obtained by DE |
||||
|
3.123889470 |
3.069156770 |
3.014282390 |
2.957588300 |
1.466044830 |
|
0.368057943 |
0.363481530 |
0.359121133 |
0.354952823 |
0.350967972 |
|
Table-1(b). Values
of Decision Variables of Keane (m=10) obtained by RPS |
||||
|
3.124165150 |
3.068864800 |
3.015470120 |
2.955911380 |
1.465639690 |
|
0.367340008 |
0.363605407 |
0.358758758 |
0.354977899 |
0.352024977 |
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; g1(x) = -5.18851406E-010; g2(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; g1(x) = -1.42940888E-005; g2(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 x7 and x8 have broken the said sequence.
|
Table-2(a). Values
of Decision Variables of Keane (m=15) obtained by DE |
||||
|
3.146293070 |
3.106145430 |
3.066581520 |
3.026848660 |
2.986415340 |
|
2.944612650 |
1.432725200 |
0.414056148 |
0.409743392 |
0.405635026 |
|
0.401726913 |
0.397869284 |
0.394212294 |
0.390652961 |
0.387395467 |
|
Table-2(b). Values
of Decision Variables of Keane (m=15) obtained by RPS |
||||
|
3.147885830 |
3.107285280 |
3.067863320 |
3.027769080 |
2.986310220 |
|
2.947132220 |
0.418950619 |
1.373826510 |
0.413106309 |
0.406717883 |
|
0.403270323 |
0.399151233 |
0.394427081 |
0.391056701 |
0.390648466 |
For the 20-dimensional Keane’s problem we have DE min[(f)] = -0.803619104; g1(x) = -4.95659069E-012; g2(x) = -119.067416. The decision variables take on the following values given in Table-3(a). We obtain the RPS min[(f)] = -0.785263489; g1(x) = -2.13415866E-005; g2(x) = -117.548076 for the values of x given in Table-3(b).
|
Table-3(a). Values of Decision Variables of Keane (m=20) obtained by DE |
||||
|
3.162462120 |
3.128331570 |
3.094791700 |
3.061449390 |
3.027931110 |
|
2.993829330 |
2.958666990 |
2.921839070 |
0.494829273 |
0.488358755 |
|
0.482312620 |
0.476648099 |
0.471293545 |
0.466228022 |
0.461417418 |
|
0.456836629 |
0.452460752 |
0.448267681 |
0.444248266 |
0.440381976 |
|
Table-3(b). Values of Decision Variables of Keane (m=20) obtained by RPS |
||||
|
3.151484020 |
3.119328890 |
3.086598240 |
3.053529180 |
3.021145250 |
|
2.985534770 |
2.949188660 |
2.911211960 |
0.418488616 |
2.821296710 |
|
0.410584741 |
0.405855243 |
0.399953254 |
0.398307630 |
0.394483277 |
|
0.391179683 |
0.388534529 |
0.383874458 |
0.382995909 |
0.378349313 |
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.
|
Table-4. Values of Decision Variables of Keane (m=30) obtained by DE |
||||
|
3.168225530 |
3.146211650 |
3.124531090 |
3.102979710 |
3.081823620 |
|
3.060544800 |
3.039195590 |
3.017679840 |
2.995636850 |
2.973543750 |
|
2.950666480 |
2.927562460 |
2.903088710 |
0.440434895 |
0.437505191 |
|
0.435103340 |
0.432460693 |
0.429815709 |
0.427295405 |
0.424698735 |
|
0.422641158 |
0.420028735 |
0.417678117 |
0.415577752 |
0.413108742 |
|
0.410869231 |
0.408999549 |
0.406826514 |
0.405042008 |
0.402869708 |
For the 30-dimensional Keane’s problem we have DE min[(f)] = -0.818056222; g1(x) = -1.90829275E-009; g2(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; g1(x) = -4.67459549E-009; g2(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.
|
Table-5. Values of Decision Variables of Keane (m=40) obtained by DE |
||||
|
3.176402220 |
3.159781680 |
3.143267960 |
3.126970650 |
3.110958340 |
|
3.094833420 |
3.078715320 |
3.062493030 |
3.046925820 |
3.030744620 |
|
3.014489370 |
2.998191690 |
2.981676650 |
2.964750240 |
2.947671240 |
|
2.930427940 |
2.912463350 |
0.455727042 |
0.453400834 |
0.451294809 |
|
0.448984473 |
0.446911098 |
0.444660768 |
0.442769918 |
0.440588651 |
|
0.438735980 |
0.436742512 |
0.435131699 |
0.433072143 |
0.431025920 |
|
0.429591143 |
0.427762652 |
0.425920239 |
0.424344581 |
0.422578191 |
|
0.420945959 |
0.419335333 |
0.417769877 |
0.416132722 |
0.414726294 |
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; g1(x) = -2.55134022E-008; g2(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
|
Table-6. Values of Decision Variables of Keane (m=50) obtained by DE |
||||
|
2.984331850 |
2.970850220 |
2.957100110 |
2.943168300 |
2.929067060 |
|
2.914580720 |
0.465266845 |
0.463396171 |
0.461448453 |
0.459610933 |
|
0.457759997 |
0.456007425 |
0.454318803 |
0.452430869 |
0.450861344 |
|
0.449163331 |
0.447302715 |
0.445867968 |
0.444297375 |
0.442654703 |
|
0.440993800 |
0.439496353 |
0.438148497 |
0.436730303 |
0.435083505 |
|
0.433749816 |
0.432327620 |
0.430812420 |
0.429525278 |
0.428145716 |
|
0.426877925 |
0.425525920 |
0.424203890 |
0.422892481 |
0.421473178 |
|
2.984331850 |
2.970850220 |
2.957100110 |
2.943168300 |
2.929067060 |
|
2.914580720 |
0.465266845 |
0.463396171 |
0.461448453 |
0.459610933 |
|
0.457759997 |
0.456007425 |
0.454318803 |
0.452430869 |
0.450861344 |
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 g1(x) = -9.86513138E-009; g2(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; g1(x)= -3.97261395E-05; g2(x) = -292.704914.
|
Table-7. Values of Decision Variables of Keane (m=50) obtained by DE |
||||
|
6.281881470 |
3.165864960 |
3.152419640 |
3.139117420 |
3.125910180 |
|
3.112937380 |
3.099820120 |
3.086810400 |
3.073914590 |
3.060912370 |
|
3.047946650 |
3.034998900 |
3.021821370 |
3.008627600 |
2.995345870 |
|
2.982032700 |
2.968429500 |
2.954671080 |
2.940647550 |
2.926380720 |
|
2.911877500 |
0.454055821 |
0.452282938 |
0.450327194 |
0.448694221 |
|
0.446908360 |
0.445253680 |
0.443532095 |
0.441920750 |
0.440236963 |
|
0.438736885 |
0.437136832 |
|||