| On 2005-10-06 at 15:00:00 (Brussels Time) |
Abstract
There are two general strategies for solving a combinatorial optimisation problem: exact and approximate. Exact methods accurately exploit the structure of the problem but are tractable only up to a certain size; approximation or heuristic methods are tractable for very large problems but may possibly be led into a bad solution. A question that arises is, Can knowledge of the problem structure gained from exact methods be used on large-scale problems by heuristic methods? This talk will present a framework for integrating such structural knowledge into the Ant Colony System metaheuristic, where the structure is determined through the notion of kernelization from the field of parameterized complexity; this can be seen as a kind of template for ACS. We give experimental results using vertex cover as the problem instance, and show that this notion of template improves performance beyond previously defined ACS algorithms for this problem.
Keywords
Ant Colony Optimization, Combinatorial Optimization Problems, Parameterized Complexity
