Hello everyone,
I have recently opted for the COCO framework for comparing and analysing continuous algorithms to deeply analyse an algorithm I am working on.
The paper of Hansen et al. (coco: performance assessment) was of great help for understanding the rationale of the adopted result analysis procedure in the case of a mult-algorithm comparison. However, some details remain still unrevealed, hence:
1. Could anyone cite some references talking about the categories of functions cited in the benchmarks, namely: separable fcts, moderate fcts, ill-conditioned fcts, multi-modal fcts, weakly structured multi-modal fcts ?
2. The three types of graphs, offered when comparing only two algorithms, have not been presented in the above-mentioned reference, see attached file.
Hence, I would be really thankful for any clarifications.
Dear Amer Draa,
I’ve used the BBOB functions in several of my papers, although I never used the COCO tools for comparison and analysis. I also had my doubts about some of the functions’ characteristics, especially with the adequate/weak global structure (the other ones I could understand from the benchmark description). I even asked directly to Hansen, but I received no answer.
In case it helps, here are some of the papers where we used the BBOB functions. Although we don’t describe the functions’ characteristics, we frequently attempt to analyze the behavior/performance of several algorithms based on these properties.
Conference Paper Multi-swarm hybrid for multi-modal optimization
Conference Paper Differential Evolution with Thresheld Convergence
Conference Paper Minimum Population Search – Lessons from building a heuristi...
Conference Paper Extending Minimum Population Search towards Large Scale Glob...
Hi,
As part of my phd thesis, i use the BBOB test bench.
Considering the problem classes of the BBOB test bench:
- Separable functions consider functions that can be expressed by a composition of functions one one given variable, suggesting that each variable can be optimized independently. Taking the sphere function, each variable have same amount of information, also for the rastrigin functions in the separable classes
- Considering the weakly or high conditioning classes it refers to the quasi positive Hessian matrix of the function suggesting that a higher conditioning results in a more difficult problem as the gradient would be more difficult to be approximated.
- Multi modal classes with global structures are based on modified multi modal functions with a convex structure that can be exhibited during the search, in contrast of multi modal classes for which no structures can be identified hence suggesting that the function is generated seem to be like a gaussian noise.
About the Performance assessement: you can read [1] and [2] where i introduces the ERT expected runtime which is the performance of my choice for my research:
as it refers to the probability to reach a quality in a given budget of time (expressed in number of evaluations)
About the ECDF graph, empirical cumulative distribution function: after t trials (runs) of your algorithm on different instances of one given function: we consider different target value, and look at the number of evaluation needed to reach the given target value ( 10-1, 10-2, ..., 10-8) and for each target we look at the number of runs that reached the given target. This is a cumulative distribution, then when you observe it reach 100%, it means that all runs reached the best target value, let say 10-8. The problem functions is aggregated by classes and by dimensions such that you can observe if your algorithm as some better disposition to solve one class.
[1] Belkhir, N., Dréo, J., Savéant, P., & Schoenauer, M. (2015, October). Parameter Setting for Multicore CMA-ES with Large Populations. In International Conference on Artificial Evolution (Evolution Artificielle) (pp. 109-122). Springer International Publishing.
[2] Belkhir, N., Dréo, J., Savéant, P., & Schoenauer, M. (2016, September). Feature Based Algorithm Configuration: A Case Study with Differential Evolution. In International Conference on Parallel Problem Solving from Nature (pp. 156-166). Springer International Publishing.
Don't hesitate to contact me if you need any help. My main research topic is continuous black box optimization, within the TAO team ( same team of authors of the BBOB/COCO testbench )
Hi Nacim,
I want to generate ECDF plots myself using the data I am storing in .dat file. Can you put some light on how to the log10 Fevals/dim vs proportion of trails graph plotted?
Hi,
As mentionned Amer Draa you can directly use the coco platform to generate the figures. However, if you want to reproduce similar plots:
Given n independent run: for each target value (Fopt + a numerical precision) in the file you have the number of call of the objective function needed to reach this target value.
The ECDF is the proportion of solved instances+target values, then for each point in the plot, this is the number of runs one target value.
If you need any help to re implement this, tell me.
Thank you Amer Draa and Nacim Belkhir I have few doubts about plotting teh ECDF graphs myself because I want to calculate the area under the ECDF graph. How is bootstrapping helping to plot ECDF graphs for bbob functions? http://numbbo.github.io/coco-doc/perf-assessment/: Is formulae under motivation used for plotting? If yes, how do I estimate ps?
In my understanding, for a problem I need function evaluations per target (51 target). I read in documentation that uniformly distributed targets are considered to plot ECDF graph. How is a smooth graph generated?
It would be helpful if you can help understanding the process of plotting ECDF graphs
Thank you.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Algorithms