The empirical first-order attainment function (EAF) is used to assess the performance of stochastic multiobjective optimisers such as multiobjective evolutionary algorithms [1]. It is an estimator for the first-order attainment function, which provides information about the location and, to some extent, the variability, of the random sets of non-dominated objective vectors produced by such optimisers when applied to given problem instances.
A program to compute the EAF from non-dominated sets of two or three-dimensional objective vectors is provided. It is a C implementation of the dimension-sweep algorithms proposed in [2]. In the two-objective case, it runs in asymptotically optimal Θ(m log m+nm) time, where m is the total number of input points and n is the number of input sets. In the three-objective case, the time complexity is O(n2m log m). An algorithm for the four-objective case is described in [3], and will be made available in a future version of this code.
Also included is a program to perform statistical hypothesis tests based on empirical first or second-order attainment functions, as described in [4]. It uses randomisation to estimate the critical value for a two-sample, two-sided Kolmogorov-Smirnov-like test at a given significance level. If the null-hypothesis can be rejected at that significance level, p-value estimates are returned as well. The two samples are implicitly assumed to have the same size.
This software is Copyright © 2011 Andreia P. Guerreiro, Carlos M. Fonseca, Manuel López-Ibáñez and Luís Paquete.
This program is free software. You can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
Appropriate reference to this software should be made when describing research in which it played a substantive role, so that it may be replicated and verified by others. The EAF computation problem and the algorithms which this software implements are described in detail in [1].
The source code is available here. Please see the documentation within for building instructions.
EAF Graphical Tools - R package for EAF visualisation
| [1] | V. Grunert da Fonseca and C. M. Fonseca, “The attainment-function approach to stochastic multiobjective optimizer assessment and comparison,” in Experimental Methods for the Analysis of Optimization Algorithms (T. Bartz-Beielstein, M. Chiarandini, L. Paquete, and M. Preuss, eds.), ch. 5, pp. 103-130, Springer Berlin Heidelberg, 2010. [ DOI ] |
| [2] | C. M. Fonseca, A. P. Guerreiro, M. López-Ibáñez, and L. Paquete, “On the computation of the empirical attainment function,” in Evolutionary Multi-Criterion Optimization. Sixth International Conference, EMO 2011 (R. H. C. Takahashi, K. Deb, E. F. Wanner, and S. Greco, eds.), vol. 6576 of Lecture Notes in Computer Science, pp. 106-120, Berlin: Springer, 2011. [ DOI | source code | .pdf ] |
| [3] | A. P. Guerreiro, “Efficient algorithms for the assessment of stochastic multiobjective optimizers,” Master's thesis, Instituto Superior Técnico, Technical University of Lisbon, Lisbon, Portugal, 2011. [ .pdf ] |
| [4] | C. M. Fonseca, V. Grunert da Fonseca, and L. Paquete, “Exploring the performance of stochastic multiobjective optimisers with the second-order attainment function,” in Evolutionary Multi-Criterion Optimization. Third International Conference, EMO 2005 (C. A. Coello Coello, A. Hernández Aguirre, and E. Zitzler, eds.), vol. 3410 of Lecture Notes in Computer Science, pp. 250-264, Berlin: Springer, 2005. [ DOI | .pdf ] |