NK-landscapes as test functions for evaluation of host-parasite algorithms

摘要

Previous research on host-parasite algorithms has shown that the co-evolutionary arms race is difficult to sustain when the tasks faced by hosts and parasites are heavily asymmetric. We have therefore proposed an asymmetry-handling algorithm, AHPA, with a capacity for self-adapting the allocation of generations to hosts and parasites, so that the problem asymmetry is counteracted. In this paper we discuss the need for systematic evaluation of this algorithm, so that its behaviour under varying levels of asymmetry can be studied in detail. We propose the use of Kaufmann's NK landscape model for this purpose, and show how the model can be adapted for the testing of host-parasite algorithms. Using the adapted model, we present simulation results which confirm AHPA's ability to sustain a stable arms-race under varying levels of asymmetry.