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.
International Journal of High Performance Computing and Networking, 2018 Vol.12 No.3, pp.307 - 313
Available online: 25 Sep 2018 *Full-text access for editors Access for subscribers Purchase this article Comment on this article