Reevaluating immune-inspired hypermutations using the fixed budget perspective

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • Aberystwyth University

Abstract

Different studies have theoretically analyzed the performance of artificial immune systems in the context of optimization. It has been noted that, in comparison with evolutionary algorithms and local search, hypermutations tend to be inferior on typical example functions. These studies have used the expected optimization time as performance criterion and cannot explain why artificial immune systems are popular in spite of these proven drawbacks. Recently, a different perspective for theoretical analysis has been introduced, concentrating on the expected performance within a fixed time frame instead of the expected time needed for optimization. Using this perspective we reevaluate the performance of somatic contiguous hypermutations and inverse fitness-proportional hypermutations in comparison with random local search on one well-known example function in which a random local search is known to be efficient and much more efficient than these hypermutations with respect to the expected optimization time. We prove that, depending on the choice of the initial search point, hypermutations can by far outperform random local search in a given time frame. This insight helps to explain the success of seemingly inefficient mutation operators in practice. Moreover, we demonstrate how one can benefit from these theoretically obtained insights by designing more efficient hybrid search heuristics.

Details

Original languageEnglish
Article number6879426
Pages (from-to)674-688
Number of pages15
JournalIEEE Transactions on Evolutionary Computation
Volume18
Issue number5
Publication statusPublished - 1 Oct 2014

Keywords

  • Algorithm design and analysis, computational complexity, computational intelligence, heuristic algorithms