[ quantlib-Patches-3582579 ] Differential Evolution improvement

[SourceForge.net]

Patches item #3582579, was opened at 2012-11-01 15:38
Message generated for change (Tracker Item Submitted) made by fenixcitizen
You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=312740&aid=3582579&group_id=12740

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: None
Group: None
Status: Open
Resolution: None
Priority: 5
Private: No
Submitted By: Mateusz Kapturski (fenixcitizen)
Assigned to: Nobody/Anonymous (nobody)
Summary: Differential Evolution improvement

Initial Comment:
Hi All,
I have come across the new implementation of Differential Evolution that appeared in QuantLib HEAD source code recently. I decided to improve it slightly. I took performance very seriously as the DE implementation should be light in order to avoid unnecessary time overhead.

The most significant change is that I use DiffEvolConfiguration object that defines the behavior of the algorithm. The reason is that it makes the implementation more flexible. There are dozens of DE variants... I tried to be in line with current QuantLib optimization interface.

Important changes:
1) DE Optimizer consumes configuration object that defines its behavior - as I mentioned, the number of variations of the DE algorithm is huge. This approach makes it possible to extend the implementations in the future.
2) Constraints that define search space are not the part of the algorithm itself - this is why additional upperBound and lowerBound functions were added to Constraint object. NonhomogeneousBoundaryConstraint to define box constraints was added too. The other aspect is if the bounds are going to be valid for emerging populations - practical advise is that it should as for certain parameters, new populations seem to diverge. On the other hand, it adds some additional overhead. General observation is that it is always possible to improve performance for a given objective function. One needs to find appropriate DE configuration only.
3) I added three different crossover types: normal, binomial and exponential (the name for the first crossover type comes from the fact that assuming binomial crossover, the number of mutants taken into account in a given population converges in distribution to normal variable for growing problem size)
4) There are 6 methods available in this implementation. However, it is possible to go further and implement various base element types, differences of a given size, various weights distributions for the differences etc. Implemented approaches are the most common used in practice as the more complicated recombination procedure, the higher computation cost is.
5) For ModFourthDeJong objective function as I was able to find a point for which the objective function value is 8.86549 which is significantly lower than 12.3724219287 :
DE type:    bestMemberWithJitter
Crossover type:    normal
Apply Bounds:    true
CrossoverProb:    0.25
NumOfPopulationMembers:    500
PrintFullInfo:    false
StepsizeWeight:    0.2
MaxIterations
Point: [ 0.299015; 0.352861; -0.0306954; -0.349516; 0.202407; 0.111475; 0.0783742; -0.0640798; 0.284987; -0.00386122; 0.134481; -0.174184; -0.0188605; 0.217705; 0.0557937; 0.176954; -0.0757169; 0.219995; -0.079788; -0.142831; -0.129607; 0.135615; -0.152286; 0.0420379; -0.193061; 0.0582583; -0.0617313; -0.238126; -0.11224; -0.069721 ]
Objective function value: 8.86549
However, this is the best result only. Usually, the algorithm was stuck in several local minimas - most of them in [10;15] range. Further investigation is needed.
6) I have problem with Griewangk function too. I am not able to find fully successful method although the objective function value oscillated around 0.1 which is not bad. It needs to be verified.

I find the bestMemberWithJitter method the most successful and this is the only reason I set it as default method to be used. Hope it helps. I am happy to answer your questions. In case my patch does not work properly, please use changed files directly.

Kind regards,
Mateusz Kapturski

----------------------------------------------------------------------

You can respond by visiting:
https://sourceforge.net/tracker/?func=detail&atid=312740&aid=3582579&group_id=12740

------------------------------------------------------------------------------
LogMeIn Central: Instant, anywhere, Remote PC access and management.
Stay in control, update software, and manage PCs from one command center
Diagnose problems and improve visibility into emerging IT issues
Automate, monitor and manage. Do more in less time with Central
http://p.sf.net/sfu/logmein12331_d2d
_______________________________________________
QuantLib-dev mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/quantlib-dev