Comparison and selection of exact and heuristic algorithms

Authors/Editors

Research Areas

Publication Details

Output type: Other

Author list: Perez J, Pazos RA, Frausto J, Rodriguez G, Cruz L, Fraire H, Mutula M

Publisher: Springer

Publication year: 2004

Volume number: 3045

Start page: 415

End page: 424

Number of pages: 10

ISBN: 3-540-22057-7

ISSN: 0302-9743

Languages: English-Great Britain (EN-GB)

Abstract

The traditional approach for comparing heuristic algorithms uses well-known statistical tests for meaningfully relating the empirical performance of the algorithms and concludes that one outperforms the other. In contrast, the method presented in this paper, builds a predictive model of the algorithms behavior using functions that relate performance to problem size, in order to define dominance regions. This method generates first a representative sample of the algorithms performance, then using a common and simplified regression analysis determines performance functions, which are finally incorporated into an algorithm selection mechanism. For testing purposes, a set of same-class instances of the database distribution problem was solved using an exact algorithm (Branch&Bound) and a heuristic algorithm (Simulated Annealing). Experimental results show that problem size affects differently both algorithms, in such a way that there exist regions where one algorithm is more efficient than the other.

Keywords

No matching items found.

Documents