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

Authors: Xiaoyun Xia; Langping Tang; Xue Peng

Addresses: College of Mathematics Physics and Information Engineering, Jiaxing University, Jiaxing Zhejiang 314001, China; School of Information Engineering, Jiangxi University of Science and Technology, Ganzhou, China ' College of Medical Information Engineering, Guangdong Pharmaceutical University, Guangzhou, China ' Department of Computer Science, Guangdong Polytechnic Normal University, Guangzhou, China

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.

Keywords: artificial immune system; somatic contiguous hypermutations; multiprocessor scheduling problem; MSP; runtime analysis.

DOI: 10.1504/IJHPCN.2018.094950

International Journal of High Performance Computing and Networking, 2018 Vol.12 No.3, pp.307 - 313

Received: 09 May 2016
Accepted: 30 Aug 2016
Published online: 28 Sep 2018 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article