Artificial immune systems can beat evolutionary algorithms in combinatorial optimisation

Artificial immune systems (AIS) are randomised search heuristics that can be applied to any kind of optimisation problem just like evolutionary algorithms (EAs). Unlike EAs their inception stems from a different natural paradigm: the immune system of vertebrates instead of natural evolution. While AIS proved to be highly efficient in several application areas, so far for no classic optimisation problem it could be rigorously proven that AIS outperform EAs. We consider the B-Cell Algorithm (BCA) as an example of an artificial immune system and compare its performance with that of the (1+1) EA on a classic combinatorial optimisation problem, interval scheduling. We show that for the natural binary encoding both heuristics are not able to efficiently find an optimal solution for all instances. The (1+1) EA has exponential expected optimisation time and the BCA may never find an optimal solution. However, we also show that a natural preprocessing changes the situation dramatically. If we remove beforehand all intervals strictly containing another one, then the BCA always finds an optimal solution in polynomial expected optimisation time. The (1+1) EA remains inefficient in the worst case, still having exponential expected optimisation time. It can, however, find a 2-approximation of an optimal solution very quickly.