Datasets and scripts from the paper

[MLopez-Ibanez]

Hi,

I was looking at your poster in GECCO and wondering how this compares with the C code in the eaf R package. There is a R interface that pays some interface penalty but it is very easy to use:

https://mlopez-ibanez.github.io/eaf/reference/nondominated.html

It should not be hard to run on your datasets if those are available.

I also have a pure C command-line interface that is not public but I could share and make public if useful.

If these implementations are faster, it would be great to integrate them in the eaf R package!

[adbjesus]

Hi,

I quickly tested this on my computer for a few dimensions and approximate percentage of non-dominated points. I've also made sure that the output is the same for all approaches (points show up in a different order, but they match). You can see the results below where N is the number of points in the initial set of points before filtering, and the time is given in seconds. It seems like eaf and our quadratic function are on par (which makes sense since the code in eaf also seems to be quadratic). However, our other functions seem much faster.

As such I am guessing it would be useful to integrate those functions into eaf. Looking at the find_nondominated_set_ function in eaf, which seems to be the one called, I think it wouldn't be too hard to add a function with the same signature to our library, which you could then integrate in eaf. Of course you can integrate it as is if it is doable, I am not familiar with Rcpp enough to know if it is feasible or not.

I am a bit busy over the next few weeks, but if you are interested in adding this to eaf I can look into it sometime next month. One question though:

• Does the algorithm need to be stable (i.e. keep the order of the points)? I did not check if your was, but our algorithms are not stable. This is something that we probably want to look at in the future. It might have a small impact on performance, but nothing too significant.

Approximate percentage of non-dominated points - 20%

Dim	N	eaf	filterQuadD	filterDimSweep2D	filterDimSweep3D	filterDivConqD
2	1000	0.00049	0.00052	0.00022
2	5000	0.00862	0.00429	0.00051
2	10000	0.03598	0.01710	0.00119
2	50000	0.85698	0.43267	0.00715
2	100000	3.50930	2.00196	0.01971
3	1000	0.00082	0.00108		0.00036
3	5000	0.01301	0.00731		0.00080
3	10000	0.04958	0.02648		0.00166
3	50000	1.18215	0.69957		0.01103
3	100000	4.50231	2.86543		0.02419
4	1000	0.00110	0.00168			0.00072
4	5000	0.01956	0.01221			0.00444
4	10000	0.06982	0.04431			0.00978
4	50000	1.49457	0.94710			0.05775
4	100000	5.69279	3.61779			0.12399

Approximate percentage of non-dominated points - 50%

Dim	N	eaf	filterQuadD	filterDimSweep2D	filterDimSweep3D	filterDivConqD
2	1000	0.00175	0.00270	0.00023
2	5000	0.04144	0.02611	0.00054
2	10000	0.17286	0.10355	0.00111
2	50000	4.50937	3.05167	0.00814
2	100000	17.93685	12.62783	0.01668
3	1000	0.00215	0.00178		0.00053
3	5000	0.05429	0.03713		0.00111
3	10000	0.22252	0.15352		0.00233
3	50000	5.58218	4.22255		0.01308
3	100000	22.45935	17.25304		0.03080
4	1000	0.00292	0.00259			0.00095
4	5000	0.06718	0.04759			0.00521
4	10000	0.26115	0.18687			0.01083
4	50000	6.46399	4.95909			0.06704
4	100000	25.72758	19.87227			0.15002

Approximate percentage of non-dominated points - 80%

Dim	N	eaf	filterQuadD	filterDimSweep2D	filterDimSweep3D	filterDivConqD
2	1000	0.00297	0.00651	0.00008
2	5000	0.06525	0.06761	0.00049
2	10000	0.26505	0.26973	0.00099
2	50000	6.65558	7.86901	0.00651
2	100000	26.73081	32.46186	0.01532
3	1000	0.00407	0.00907		0.00059
3	5000	0.09427	0.09479		0.00122
3	10000	0.38584	0.41265		0.00260
3	50000	9.42807	10.91349		0.01552
3	100000	38.32580	46.58774		0.03386
4	1000	0.00496	0.00566			0.00121
4	5000	0.12028	0.11055			0.00585
4	10000	0.47917	0.46101			0.01379
4	50000	11.31746	12.35044			0.08107
4	100000	45.57990	52.52820			0.18423

[MLopez-Ibanez]

Hi,

Wow nice speed-up!

I have also never used C++ in an R package.

I wonder if it may be better to create a new package from scratch and make the eaf package use that new package. The eaf package currently does so much more than calculate the eaf: https://mlopez-ibanez.github.io/eaf/reference/index.html

The order is not important for filter_dominated(), but the R package provides as well a function "is_nondominated()" that returns a boolean vector, and then the order is important there to be able to build complex vectorized logical predicates.

Cheers,

Manuel.