When is the immune inspired B-cell algorithm superior to the (1+1) evolutionary algorithm?. (2018)

• Record Type: Journal Article
• Authors: Xia, Xiaoyun; Tang, Langping; Peng, Xue
• Is Part Of: International journal of high performance computing and networking. Volume 12:Number 3(2019)
• Page Start: 307
• Page End: 313
• Publication Date: 2018
• Subjects: artificial immune system -- somatic contiguous hypermutations -- multiprocessor scheduling problem -- MSP -- runtime analysis; High performance computing -- Periodicals; Computer networks -- Periodicals; High performance computing; Periodicals; 004.05
• Languages: English
• ISSNs: 1740-0562

Abstract

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.