MLO Contact : Joshua Knowles
Approximation algorithms, which are methods that deliver solutions guaranteed in the worst case to be no more than a fixed amount epsilon away from optimal, are well-known in single-objective optimization. In multiobjective optimization, the concept of approximation must be extended in two ways: to cover vector fitness values; and, to cover sets. Thanks to work by Yannakakis and Papadimitriou, and by Laumanns et al, we have the notions of an epsilon-approximation set and an epsilon-Pareto approximation set, which are alternative types of approximation to a Pareto optimal set. In ongoing work (that dates back to some of my PhD studies in 1999 onwards), I am investigating what types of algorithm give guaranteed approximation to a Pareto front, and with what type of convergence. I am particularly interested in the case where the epsilon value is not selected a priori by the user, but is adapted during optimization to give the closest possible approximation. In recent work with López-Ibáñez and Laumanns, we were able to characterize both theoretically and empirically the approximation and convergence properties of several of the most common archiving algorithms used in multiobjective optimization. Two of the currently best methods are hypervolume-based archiving[3,5], and archiving based on a hierarchical, adaptive grid.
- C. H. Papadimitriou, M. Yannakakis. The complexity of tradeoffs, and optimal access of web sources. FOCS, 2000.
- M Laumanns, L Thiele, K Deb, E. Zitzler. Combining convergence and diversity in evolutionary multiobjective optimization. Evolutionary computation, 10(3): 263--282, 2002.
- J. Knowles. Local-search and hybrid evolutionary algorithms for Pareto optimization. PhD thesis, University of Reading, 2002.
- M. López-Ibáñez, J. Knowles, M. Laumanns. On sequential online archiving of objective vectors. Evolutionary Multi-Criterion Optimization, LNCS 6576: 46-60, 2011.
- J. Knowles, D. Corne. Properties of an adaptive archiving algorithm for storing nondominated vectors. IEEE Transactions on Evolutionary Computation, 7(2):100-116, 2003.
- M. Laumanns, R. Zenklusen. Stochastic convergence of random search methods to fixed size Pareto front approximations. European Journal of Operational Research 213(2): 414-421, 2011.