Run-length distribution (RLD) Analysis

[abeham]

Run-length distributions give insight into the required algorithmic effort (in terms of function evaluations or wall-clock time) for reaching a certain target.

The empirical cumulative distribution function (ECDF) can be calculated from several runs of an optimization algorithm. From a first-hit graph several targets will be defined in the objective function and it will be measured when a target is hit by an algorithm. The proportion of all these hits forms the distribution.

Design issues:

• Algorithm Execution time is hard to obtain (similar problem with the introduction of terminators)
  • The precision of execution time from the algorithm is not good enough (~200ms)
• Adding EvaluatedMoves and EvaluatedSolutions is complicated by different cost factors
  • Some algorithms/operators count evaluated solution-equivalents instead
  • Integer is sometimes too small to hold the amount of evaluated moves for long runs / big problems
• Analyzers depend on BestAverageWorstQualityAnalyzer being run before them
  • Arguably, best-so-far quality and execution time are results that the algorithm itself should provide and not an analyzer
  • Quality progress chart should be calculated in a separate analyzer
• ISingleObjectiveHeuristicOptimizationProblem specifies MaximizationParameter as an IParameter instead of an IValueParameter<BoolValue>
• Which parameters in a run characterize the algorithm instance?
  • E.g. Seed does not characterize the instance
  • Analyzers do not characterize the instance, but some "analyzers" may modify penalties
• ResultCollection contains Result objects, but RunCollection.Results contains only the items
  • The Result objects are always in the way, they should be removed

[abeham]

r12764:

• branched relevant plugins
• added analyzer to calculate quality vs evaluation first-hit graph
• (also added results parameter)

[abeham]

r12766: forgot to commit

[abeham]

r12771:

• Added run collection view
• Changed name of analyzers
• Modified algorithms to include Execution Time as a result

Logscaling is still an issue

[abeham]

r12774: minor improvements

[abeham]

r12803: worked on RLD analysis

• started implementation of IRRRun
• renamed view from ECDF to RLD
• reverted algorithms (execution time)
• changed per clock analyzer

[abeham]

r12804:

• worked on IRRestarter (early abort still troublesome)
• Updated RLD view to allow defining targets
• Attempting to handle maximization/minimization

Fun detail:

• HeuristicLab.Analysis references HeuristicLab.Optimization
• HeuristicLab.Optimization.Views references HeuristicLab.Analysis.Views

IRRestarter is currently placed in HeuristicLab.Analysis, its view in HeuristicLab.Optimization.Views.

[abeham]

r12805: fixed error due to removed resx file

[abeham]

r12806: added options to add results based on targets or budgets

[abeham]

r12808:

• added ability to plot curves for multiple targets at once
• fixed bug in IndexedDataTableView regarding log-scaling
• added result that counts restarts
• fixed bugs in IRRestarter
• Set LineWidth = 2 in analyzers for chart
• fixed bugs in RLD view

[abeham]

r12813:

• Added calculation of RTs, RTus, FEs, FEus and prune runs in alg before every restart
• merged changes from trunk

[abeham]

r12822: if multiple targets are plotted, the same color is used for each group

[abeham]

r12825:

• removed output of RTs, RTus, ...
• added 2nd row to charts that state restarts until a target was achieved
• added option to include or exclude solution results

[abeham]

r12826: omitting empty series

[abeham]

r12831: updated to trunk

[abeham]

r12834: Changed analyzer to always output last value (even if quality is equal)

[abeham]

r12838: updated RLD analysis view

• Added analysis by cost
• Prepared tab for output of ERT tables

[abeham]

r12841:

• Added calculation of ERT results tables
• Added grouping by problem to avoid having different problems in one graph
• Some restructuring to avoid duplicate code

[abeham]

r12856: Added AlgorithmIterator instead of IRRestarter

• AlgorithmIterator implements IAlgorithm whereas IRRestarter implemented only IOptimizer
• Deriving from Algorithm leads to better design

[abeham]

r12859: Renamed AlgorithmIterator to IteratedAlgorithm

[abeham]

r12862: modified EngineAlgorithm to clear log on prepare

[abeham]

r12864:

• fixed bug in iterated algorithm
• changed RLD view to use % deviation as targets
• RLD view now always groups by problem

[abeham]

r12865:

• Added label on last data point
• Changed target in cost view to display as ratio to best-known or best found

[abeham]

r12888:

• Some bug fixes

[abeham]

r12890: fixed a bug in the iterated algorithm

[abeham]

r12939: fixed calculation of ERT table when a certain group doesn't contain any runs of a certain problem

[abeham]

r12956: Extracted class that calculates ERT values from runs

[abeham]

r13475: updated from trunk, worked on okb connection for downloading knowledge base

[abeham]

r13736: fixed analysis for runs that terminated earlier than others

[abeham]

r13737:

• removed IRRestarter (replaced by IteratedAlgorithm)
• removed cut-off estimation view (didn't work satisfactorily)

[abeham]

r13738: fixed bug in IteratedAlgorithm (exception when problem is loaded, but no algorithm set)

[abeham]

r14035:

• Fixed bug that occurs when runs of unequal length are aggregated over multiple problem instances

[abeham]

r14058: Refactored ResultsParameter