Abstract: The problem of damage identification using minimum test data is studied in this work. Data sparsity in damage identification applications commonly results in inverse problems that are mathematically ill-posed (e.g. non-unique solutions). Although solution non-uniqueness may be addressed by performing multiple tests on a structure, it is not trivial to decide which tests to carry out given that actual physical testing is costly. This problem is addressed in this work through a new co-evolutionary algorithm that interactively searches for damage scenarios and optimum physical tests. The algorithm is composed of two stages: the estimation phase, which searches for damage scenarios that can predict current physical tests, and the exploration phase, which searches for tests that increase the level of information about the damaged system. The feasibility of the methodology is demonstrated using numerical examples.