Several diseases involve complex interplay between an infection and the body's defences. Concerning AIDS, for example, this corresponds to developments in the immune system's responses and the HIV virus' counter-responses. Treatment for such diseases involves, at specific times, delivery of an agent that inhibits the infection. We hypothesise that: given a credible model of the combined dynamics of infection and response, the timing and quantities involved in treatment can be valuably investigated using that model. In particular, we investigate searching for optimised treatment plans with an evolutionary algorithm (EA). Our test case is a cellular automaton (CA) model of HTV dynamics, extended to incorporate HAART therapy (a favoured HTV treatment).An EA is wrapped around this model, and searches for treatments that maximally delay onset of AIDS, given certain constraints. We find that significant improvements over default HAART strategy are readily discovered in this way. © Springer-Verlag Berlin Heidelberg 2006.