When is the immune inspired B-cell algorithm superior to the (1+1) evolutionary algorithm?. (2018) - Xia, Xiaoyun; Tang, Langping; Peng, Xue
There exist many experimental investigations of artificial immune systems (AIS), and it has been shown that the AIS is useful and efficient for many real-world optimisation problems. However, we know little about that whether the AIS can outperform the traditional evolutionary algorithms on some optimisation problems in theory. This work rigorously proved that a simple AIS called the B-cell algorithm (BCA) with somatic contiguous hypermutations can efficiently optimise two instances of the multiprocessor scheduling problem in expected polynomial runtime, whereas the local search algorithms and the (1+1) evolutionary algorithm ((1+1) EA) using only one individual in the search space and with standard bit mutation are highly inefficient. This work is helpful for gaining insight into the idea there exists no algorithm which is efficient for all specific problems.