Advertisement
Published in:
2011 | OriginalPaper | Chapter
On the Analysis of the Immune-Inspired B-Cell Algorithm for the Vertex Cover Problem
Authors : Thomas Jansen, Pietro S. Oliveto, Christine Zarges
Published in: Artificial Immune Systems
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
The runtime of the immune inspired B-Cell Algorithm (BCA) for the NP-hard vertex cover problem is analysed. It is the first theoretical analysis of a nature-inspired heuristic as used in practical applications for a realistic problem. Since the performance of BCA in combinatorial optimisation strongly depends on the representation an encoding heuristic is used. The BCA outperforms mutation-based evolutionary algorithms (EAs) on instance classes that are known to be hard for randomised search heuristics (RSHs). With respect to average runtime, it even outperforms a crossover-based EA on an instance class previously used to show good performance of crossover. These results are achieved by the BCA without needing a population. This shows contiguous somatic hypermutation as an alternative to crossover without having to control population size and diversity. However, it is also proved that populations are necessary for the BCA to avoid arbitrarily bad worst case approximation ratios.