RealInterval Comparison Notes
This is just the square of a vector:
f(x) = ∑i=1,…,n xi 2
the global minimum is at f(x) = 0 with xi = 0. We'll use a 4-dimensional search range (that is n = 4), from -5 to 5 for each of the variables.
f:=[:x| |v| v:=x asDhbVector . v*v].
origin:= #(-5 -5 -5 -5).
range:=#(10 10 10 10).
optimizer:= AnotherGeneticOptimizer function: f minimumValues:
origin maximumValues: origin negated.
[guess:= optimizer evaluate]timeToRun .--> "0:00:00:02.015"
guess."-->
#(-2.867469461007151e-8 1.7320647733718805e-8 -1.2319136720066947e-8 6.709597192528431e-9)"
f value:guess."-->1.3190227729101297e-15"
guess abs sum /2."-->3.2512038128192844e-8"
a:= -5 hull:5.
searchrange := IntervalBox with: a with: a with: a with: a.
f value: searchrange.
minimizer := SkelboeMoore1 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 3.25e-8.
[r := minimizer evaluate]timeToRun ."-->0:00:00:00.328"
minimizer iterations."-->1807"
r."-->an Array(an IntervalBox([-1.862645149230957e-8,1.862645149230957e-8] [-1.862645149230957e-8,1.862645149230957e-8] [-1.862645149230957e-8,1.862645149230957e-8] [-1.862645149230957e-8,1.862645149230957e-8]) [0.0,1.3877787807814457e-15])"
r first midPoint."-->#(0.0 0.0 0.0 0.0)"
minimizer := SkelboeMoore2 function: f box: searchrange.
minimizer desiredPrecision: 1.387e-15.
minimizer maximumIterations:4000.
[r := minimizer evaluate]timeToRun ."-->0:00:00:00.408"
minimizer iterations."-->1823"
r."-->an Array(an IntervalBox([-9.313225746154785e-9,9.313225746154785e-9] [-1.862645149230957e-8,1.862645149230957e-8] [-1.862645149230957e-8,1.862645149230957e-8] [-1.862645149230957e-8,1.862645149230957e-8]) [0.0,1.1275702593849246e-15])"
r first midPoint. "-->#(0.0 0.0 0.0 0.0)"SkelboeMoore1 and SkelboeMoore2 are both about 5 times faster.
Also known as Rosenbrock’s valley:
f(x) = ∑i=1,…,n-1 [ 100 * (xi+1 - xi2 )2 + ( 1 - xi )2 ]
the global minimum is at f(x) = 0 with xi = 1. We'll use a 2-dimensional search range, from -2.048 to 2.048 for each of the variables.
f:=[:x| (x overlappingPairsCollect: [:f :s|
(s - f squared)squared *100 + (1-f)squared])sum ].
origin:= #(-2.048 -2.048 ).
range:=#( 4.096 4.096 ).
optimizer:= AnotherGeneticOptimizer function: f minimumValues: origin
maximumValues: origin negated.
[guess:= optimizer evaluate]timeToRun ."-->0:00:00:00.923"
guess."-->#(1.0000000121579553 1.0000000476606248)"
f value:guess."-->5.4645382770042096e-14"
a:= origin first hull: origin first negated.
searchrange := IntervalBox with: a with: a.
f value: searchrange.
minimizer := SkelboeMoore1 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 1e-8.
[r := minimizer evaluate]timeToRun ."-->0:00:00:00.243"
minimizer iterations."-->713"
r."-->an Array(an IntervalBox([0.9999999771454293,1.0000000081315226] [0.9999999513236855,1.0000000184602207]) [0,1.820035044933464e-14])"
f value: r first midPoint."-->6.901444485893116e-17"
minimizer := SkelboeMoore2 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 1.8e-14.
[r := minimizer evaluate]timeToRun ."-->0:00:00:00.097"
minimizer iterations."-->176"
r. "-->an Array(an IntervalBox([0.9999999926384758,1.0000000081315226] an IntervalUnion([0.9999999823097782,1.0000000184602207])) [0,1.77441415932797e-14])"
r first midPoint."-->#(1.0000000003849991 1.0000000003849994)"while SkelboeMoore1 is about 3 times faster, SkelboeMoore2 is 9 times faster.
de jongs third function is a step function where the range is originally constrained. i use an unconstrained version so that AnotherGeneticOptimizer can deal with it, since i have not yet updated it, so it can deal with constrained ranges (well, that wouldn't be too difficult).
f(x) = ∑i=1,…,n ( ⌊xi⌋ + 0.5 )2
the global minimum for n = 2 is at f(x) = 0.5 with -1 ≤ xi < 1. We'll use a search range from -5 to 5 for each of the variables.
f:=[:x| (x floor + 0.5)squared sum ].
origin:= #(-5 -5 ).
range:=#( 10 10 ).
optimizer.
optimizer:= AnotherGeneticOptimizer function: f minimumValues:
origin maximumValues: origin negated.
[guess:= optimizer evaluate]timeToRun ."-->0:00:00:03.914"
guess. "-->#(-0.03498052353142299 -0.6435518817571543)"
f value:guess. "-->0.5"
a:= -5 hull: 5.
searchrange := IntervalBox with: a with: a.
minimizer := SkelboeMoore1 function: f box: searchrange.
[r := minimizer evaluate]timeToRun . "-->0:00:00:03.407"
minimizer precision. -->"0.078125"
r. "--> an Array(an IntervalBox(
an IntervalUnion([-1.051120519067143,1.051120519067143])
an IntervalUnion([-1.051120519067143,1.051120519067143]))
an IntervalUnion([0.5,0.5]u[2.5,2.5]u[4.5,4.5]))"
"needs almost the same time and the result is not too good but ok,
as the real result would be [-1,1] per var."
f value: r first midPoint. "-->0.5"
minimizer := SkelboeMoore2 function: f box: searchrange.
[r := minimizer evaluate]timeToRun ."-->0:00:00:00.86"
minimizer iterations."-->1"
"runs into a bug here, does not work"SkelboeMoore1 works satisfactory here. Its advantage here is that it could also deal with De Jong's original third function. Its result would be much better and faster, if the algo would take the supremum into account, but this would be only necessary for functions that have these plateaus, insofar its a bit special and not implemented. SkelboeMoore2 runs into a bug, because its termination criterion is the width of the f(x) value, not of the x value, as in SkelboeMoore1. If f(x) is a big number or a union of several numbers, it will always stop as the width of a number is 0. This bug is not repaired as the solution that does not slow down the algo is not necessarily obvious to me.
De Jongs fourth function has some strong randomness in it:
f(x) = ∑i=1,…,n i xi4 + gauss(0,1)
the global minimum is at f(x) = 0 with xi = 0.
normalD := DhbNormalDistribution new:0 sigma:1.
f:=[:x|(x withIndexCollect: [:a :i|i*(a raisedToInteger: 4)])sum + normalD random].
origin:= #(-1.28 -1.28 ).
range:=#( 2.56 2.56 ).
optimizer:= AnotherGeneticOptimizer function: f minimumValues: origin
maximumValues: origin negated.
[guess:= optimizer evaluate]timeToRun .
"0:00:00:00.351"
guess.
"#(0.21972933819726376 -0.2864751138775032)"
a:= -1.28 hull: 1.28.
searchrange := IntervalBox with: a with: a.
f value: searchrange."-->
[-0.15221997850644106,7.90084370149356]"
"[0.11061722507744078,8.163680905077442]"
"[-1.2966107293731808,6.75645295062682]"
minimizer := SkelboeMoore1 function: f box: searchrange.
minimizer evaluate."-->Error"
minimizer := SkelboeMoore2 function: f box: searchrange.
minimizer evaluate."-->Error"While AnotherGeneticOptimizer finds a solution that is not good at all, but not completely nonsensical, the SkelboeMoore algos can't deal with this sort of problem. But that doesn't matter. In this case one would use an algo especially geared towards that kind of problem anyway.
De Jongs fifth function, Schwefel's Foxholes, has has quite a few strong local minima. We will use it in rewritten form (according to http://www.robertmarks.org/Classes/ENGR5358/Papers/functions.pdf p29):
f(x) = (0.0002 + ∑i= -2,…,2 ∑j= -2,…,2 [5 (i +2) + j + 3 + (x1 - 16 j)6 + (x2 - 16 j)6]-1)-1
the global minimum is at f(x) = 1 with xi = -32.
f:=[:x| |x1 x2| x1:=x at:1. x2:=x at:2. 1/(( (-2 to:2) collect:
[:i| ((-2 to:2) collect:[:j| 1/( 5*(i+2) + j +3 +
((x1 - (16 * j) )raisedToInteger: 6 ) +
((x2 - (16 * i) )raisedToInteger: 6 ) ) ])sum])sum + 0.002)].
origin:= #(-65.536 -65.536 ).
range:=#( 131.072 131.072 ).
optimizer:= AnotherGeneticOptimizer function: f minimumValues:
origin maximumValues: origin negated.
[guess:= optimizer evaluate]timeToRun ."-->0:00:00:02.958"
guess."-->#(-31.97833404964612 -31.978332757260088)"
f value: #(-32 -32). "-->0.998003838818649"
f value:guess. "--> 0.9980038377944489"
"with some floating point errors one can get obviously a better result than the theoretically
correct result!"
a:= origin first hull: origin first negated.
searchrange := IntervalBox with: a with: a.
f value: searchrange."-->an IntervalUnion([Float infinity negated,-0.17702160008513756]u
[0.10560792534692837,Float infinity])"
minimizer := SkelboeMoore1 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 1.8e-14.
[r := minimizer evaluate]timeToRun . "-->0:00:00:12.891"
r. "-->an Array(an IntervalBox(an IntervalUnion([-34.77920898381455,-28.77443539555614]u
[-16.384,-13.77724686751686]u[-2.048,2.048]u[13.77724686751686,17.866878691987583]u
[29.724707643398535,33.85015923576761]) an IntervalUnion([-34.77920898381455,-28.77443539555614]u
[-16.384,-15.024194243865335]u[-14.702256742425455,-14.078929290219339]u
[-2.048,-1.7221558584396075]u[0.0,2.048]u[14.078929290219339,15.024194243865335]u
[30.04838848773067,30.37559398536619])) an IntervalUnion(
[Float infinity negated,-0.7311593972136178]u[0.39506789004256104,Float infinity]))"
"there are still many foxholes not yet eliminated! although it took longer to calc the result than
with AnotherGeneticOptimizer!"
Smalltalk garbageCollect .
minimizer maximumIterations:80000.
minimizer desiredPrecision: 1e-8.
[r := minimizer evaluate]timeToRun ."-->0:00:03:50.759"
minimizer iterations."-->80000 still not enough iterations!"
r ."-->an Array(an IntervalBox(an IntervalUnion([-31.979779260237546,-31.976439345216924])
an IntervalUnion([-31.979779260237546,-31.976481620442428]))
[0.9980038377842791,0.9980038378216218])
only the correct foxhole remains and at least better than -32 now, using the floating point error
in the calculation and it needed quite some time!"
f value: r first midPoint."-->0.9980038377947585 good but not as good as AnotherGeneticOptimizer!"
Smalltalk garbageCollect .
minimizer := SkelboeMoore2 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 1e-8.
[r := minimizer evaluate]timeToRun ."-->0:00:00:10.569"
r."-->an Array(an IntervalBox(an IntervalUnion([-65.536,-27.55449373503372]u[-2.048,-1.024]u
[0.0,16.384]u[30.04838848773067,30.706362517263155]u[33.485525767098096,33.85015923576761]) [-65.536,65.536]) an IntervalUnion(
[Float infinity negated,-0.2501652822944642]u[0.19994055251785167,Float infinity])) same problem
here, but the setting of the parameters is more difficult here as SkelboeMoore2 does not return a
good result if the desiredPrecision is not reached!"
"let's try this:"
minimizer maximumIterations:80000.
minimizer desiredPrecision: 1e-5.
[r := minimizer evaluate]timeToRun ."-->0:00:01:14.341"
minimizer desiredPrecision."-->true"
minimizer iterations."-->28456"
r."-->an Array(an IntervalBox(an IntervalUnion([-32.12559483373621,-31.87109436140444])
an IntervalUnion([-32.12559483373621,-31.87109436140444]))
[0.9980008002654404,0.9980137438888393]) only the correct foxhole remains!"
f value: r first midPoint."-->0.9980038387250595 also ok, but not directly comparable to
SkelboeMoore1 as this calc here was faster with less iterations and the adjustments to make things
comparable are not so easy to make (iow i'm getting bored, if i have to wait 4 minutes for a result)."The conclusion here seems to be that the unoptimized SkelboeMoore algos can clearly deal with that sort of problem but AnotherGeneticOptimizer is better here.
A function with many widespread local minima regularly distributed:
f(x) = 1/4000 * ∑i= 1,…,n xi2 - ∏i= 1,…,n cos(xi / i½) + 1
the global minimum is at f(x) = 0 with xi = 0.
f:=[:x| x squared sum / 4000- ((x withIndexCollect:
[ :xi :i| (xi / i sqrt)cos]) reduce:[:a :b|a*b]) + 1].
origin:= #(-600 -600).
optimizer:= AnotherGeneticOptimizer function: f minimumValues:
origin maximumValues: origin negated.
optimizer chromosomeManager populationSize: 100."because this is a difficult problem
for AnotherGeneticOptimizer"
[guess:= optimizer evaluate]timeToRun . "-->0:00:00:04.992"
guess. "-->#(5.361599676733506e-9 -6.4261490805127236e-9)"
f value:guess. "-->5.551115123125783e-16"
a:= -600 hull: 600.
searchrange := IntervalBox with: a with: a.
f value: searchrange.
minimizer := SkelboeMoore1 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 1e-9.
[r := minimizer evaluate]timeToRun ."-->0:00:00:02.474"
minimizer iterations. "-->2563"
r."-->an Array(an IntervalBox([-1.0913936421275139e-8,1.0913936421275139e-8]
[-1.5279510989785194e-8,1.5279510989785194e-8]) [0.0,2.220446049250313e-16])"
f value: r first midPoint."-->0.0"
minimizer := SkelboeMoore2 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 1e-16.
[r := minimizer evaluate]timeToRun ."-->Error, obviously a bug that i should repair!
but one can lower the desiredPrecision:"
minimizer desiredPrecision: 1e-15.
[r := minimizer evaluate]timeToRun .
"0:00:00:00.177"
minimizer iterations.
"275"
r. "-->an Array(an IntervalBox([-3.4924596548080444e-8,3.4924596548080444e-8] [-3.4924596548080444e-8,3.4924596548080444e-8]) [0,8.881784197001252e-16])"
f value: r first midPoint. "-->0.0"SkelboeMoore1 is only a tiny bit faster but its difficult enough that in SkelboeMoore2 a bug becomes visible.
This is a serious problem for AnotherGeneticOptimizer.
f(x) = [1 - | sin( π (x1 - 2)) sin( π (x2 - 2)) / ( π2 (x1 - 2) (x2 - 2)) |5 ] [ 2 + (x1 - 7)2 + 2(x2 - 7)2]
the global minimum is at f(x) = 0 with xi = 2.
f:=[:x| |x1 x2| x1:=x at:1. x2:=x at:2.( 1 - ( ( ((x1 - 2) * Float pi)sin * ((x2 - 2) * Float pi)sin /(Float pi squared *(x1 - 2)*(x2 - 2)) )abs raisedToInteger: 5)) * (2 + (x1 - 7) squared + (2 * (x2 -7)squared)) ].
origin:= #(0 0 ). range:=#( 14 14 ).
optimizer:= AnotherGeneticOptimizer function: f minimumValues: origin maximumValues: range.
optimizer chromosomeManager populationSize: 700.
[optimizer evaluate]timeToRun ."-->0:00:05:43.314"
optimizer result."-->#(1.9999999363957663 1.99999996523846)"
f value:optimizer result. "-->3.291256213404666e-12"
Smalltalk garbageCollect.
a:= 0 hull: 14.
searchrange := IntervalBox with: a with: a.
f value: searchrange.
minimizer := SkelboeMoore1 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 1e-7.
[r := minimizer evaluate]timeToRun ."-->0:00:00:02.476"
minimizer iterations."-->4000"
r."-->an Array(an IntervalBox(an IntervalUnion([0,14]) an IntervalUnion([0,14])) [Float infinity negated,125.00363557275263])"
"this seems to be unsolvable by SkelboeMoore1"
minimizer := SkelboeMoore2 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 1e-7.
[r := minimizer evaluate]timeToRun ."-->ZeroDivide Error"With the ZeroDivideError there is obviously a problem in the definition of the function (i found the definition in http://infinity77.net/global_optimization/test_functions_nd_D.html and http://arxiv.org/pdf/1308.4008.pdf). But even if i correct that definition (the first part seems to consist of two sinc functions), SkelboeMoore2 does of course not produce the ZeroDivideError anymore, but can't solve the problem. Hence this is obviously unsolvable by SkelboeMoore1 and SkelboeMoore2, only AnotherGeneticOptimizer can solve this with some difficulty. This probably shows again a bug in the implementation of these algos.
This function has 5 dimensions:
f(x) = ∑i= 1,…,24 ( x1 x2ti tanh( x3 ti + sin( x4 ti ) ) cos( ti ex5 ) - yi
with ti = 0.1 (i -1) and yi = 53.81 ( 1.27ti ) tanh( 3.012 ti + sin( 2.13 ti ) ) cos( e0.507 ti )
the global minimum is at f(x) = 0 with x = #(53.81 1.27 3.012 2.13 0.507).
Smalltalk garbageCollect.
ti:=[:x| x -1* 0.1 ] .
yi:=[:i| 53.81 * (1.27 raisedTo: (ti value: i)) * (3.012 *
(ti value: i)+ (2.13 *(ti value: i) )sin ) tanh *
(0.507 exp * (ti value: i))cos].
f :=[:x| |xc| xc:=x collect: [:i|i<0 ifTrue: [i negated ] ifFalse: [i]].
( (1 to: 24)collect: [:i|
(((xc at:2)raisedTo: (ti value: i))* (xc at:1)*( (xc at:3)*
(ti value: i) + ((xc at:4)*(ti value: i))sin )tanh *
( (xc at:5)exp *(ti value: i))cos - (yi value: i))squared ])sum ].
":this is a box-bounded problem, hence i simply mapped negative values
onto its positive ones."
origin:= #(0 0 0 0 0).
range:= #(60 60 60 60 60).
optimizer:= AnotherGeneticOptimizer function: f minimumValues: origin
maximumValues: range .
"because this problem has 5 dimensions we need a higher populationSize:"
optimizer chromosomeManager populationSize: 600.
optimizer maximumIterations: 200.
[guess:= optimizer evaluate]timeToRun .
"0:00:06:05.623"
guess abs."-->
#(53.80998706028019 1.27000023412256 3.011997318848195 64.96185931891377 0.5070000183116602)"
f value:guess ."8.824585842106288e-10""the minimum is at 0 with x = #(53.81, 1.27, 3.012, 2.13, 0.507).
but with repeated evaluations it often gets stuck in local minima.
iow the algo definitively has serious problems with this function.
eg i usually get a result like this:"
guess abs. "#(53.80999863690706 1.2700000173122075 3.012001866954813
64.96185121607915 4.113682216435432)"
f value:guess . "5.498009373365465e-13 which btw is better than the first result"
Smalltalk garbageCollect.
a:= 0 hull: 60.
searchrange := IntervalBox with: a with: a with: a with: a with: a.
"i have to change the interval extension here as the original wouldnt work here:"
f :=[:xc|
( (1 to: 24)collect: [:i|
(((xc at:2)raisedTo: (ti value: i))* (xc at:1)*( (xc at:3)*
(ti value: i) + ((xc at:4)*(ti value: i))sin )tanh *
( (xc at:5)exp *(ti value: i))cos - (yi value: i))squared ])sum ].
f value: searchrange.
"[0.0,9.73830595946239e11]" "[1961.9931311297173,1.22626910667596e7]"f value:(1 hull: 3).
minimizer := SkelboeMoore1 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 0.11.
[r := minimizer evaluate]timeToRun "0:00:00:37.762"
minimizer iterations."-->4000"
r. "an Array(an IntervalBox(an IntervalUnion([0,60]) an IntervalUnion([0,60]) an IntervalUnion([0,60]) an IntervalUnion([0,60]) [0,60]) [0.0,Float infinity])"
"this seems to be unsolvable by SkelboeMoore1"
minimizer := SkelboeMoore2 function: f box: searchrange.
minimizer maximumIterations:4000.
minimizer desiredPrecision: 1.
[r := minimizer evaluate]timeToRun ."-->Error, again obviously a bug"Hence the two SkelboeMoore algos can't solve this and again a bug becomes visible a second time.
I came upon a very simple 1-dimensional function, where SkelboeMoore has interestingly much more difficulties than AnotherGeneticOptimizer:
f(x) = sin(2 * x) / (0.5 + x2)
g:=[ :x||z|z:=x first. (2 * z) sin / (0.5 + z squared) ].
"i had to to make the detour via 'z:=x first' because AnotherGeneticOptimizer only accepts arrays
as argument of the block"
origin:= #(-4 ).
range:=#( 4 ).
optimizer:= AnotherGeneticOptimizer function: g minimumValues:
origin maximumValues: range.
[r1:=optimizer evaluate]timeToRun. "-->0:00:00:01.688"
r1."-->#(-0.4925702391621137)"
g value:r1. "-->-1.12216697951661"
f:=[ :x| (2 * x) sin / (0.5 + x squared) ].
s:=SkelboeMoore1 function: f box: (-4 hull:4).
s maximumIterations: 80000.
[r:=s evaluate]timeToRun. "--> 0:00:00:18.958"
r. "-->an Array([-0.4925926918559801,-0.4925384838921135]
[-1.1221669820286915,-1.1221669719435268])"
f value: r first midPoint."--> -1.1221669794354276"
"even with 's maximumIterations: 80000' and a much longer calculation time it only
comes halfway near to the precision of AnotherGeneticOptimizer (compare the f & g results)
and AnotherGeneticOptimizer regularly produces this good result!"
s:=SkelboeMoore2 function: f box: (-4 hull:4).
s maximumIterations: 80000.
s desiredPrecision:1e-8.
[r:=s evaluate]timeToRun. "-->0:00:00:18.851"
r."-->an Array([-0.49260199251728815,-0.4925384838921135]
[-1.1221669833033856,-1.1221669719433065])"
s iterations. "60273"
f value: r first midPoint. "-1.1221669795166098"
"This result has almost the same precision as AnotherGeneticOptimizer, but it also needs more time!
and btw if you set the desiredPrecision to low - or the maximumIterations for SkelboeMoore1 - you
will get an IntervalUnion with several intermediate results not yet thrown away."All in all one can say that for simpler problems the SkelboeMoore algos are usually, but not always, faster. SkelboeMoore2 is generally faster than SkelboeMoore1 but more difficult to use (more sensitive to the setting of parameters). With difficult problems the results are more or less a draw. Some difficult problems show in some cases obvious bugs in my implementation and some bugs are perhaps not so simple to eliminate and its not probable that eliminating all bugs would really make SkelboeMoore faster than AnotherGeneticOptimizer in those cases. And whether eliminating some bugs would make more problems solvable for SkelboeMoore is also not 100% obvious. For the time being I don't want to look into these things any further. Somehow boring, although it is fine that this documents some bugs.
Back to Examples