Output details

Dynamic Agent Prioritisation with Penalties in Distributed Local Search

Generally, distributed local search algorithms escape local optima using a single heuristic. This paper presents DynAPP, an approach for escaping local optima which, unlike others, combines two heuristics. An extensive empirical evaluation with instances of benchmark random, meeting scheduling and graph colouring problems at the phase transition has shown not only that the approach solves more problems but also that it does so quicker than other state of the art algorithms. As local search techniques are incomplete, the fact that DynApp solves more problems is very significant, and the lower cost is a bonus. Further evaluation on iteration-bounded optimisation problems also showed that DynAPP is competitive.