Skip to main content

Research Repository

See what's under the surface

Advanced Search

Theoretical formulation and analysis of the deterministic dendritic cell algorithm

Gu, Feng; Greensmith, Julie; Aickelin, Uwe

Authors

Feng Gu

Julie Greensmith

Uwe Aickelin



Abstract

As one of the emerging algorithms in the field of artificial immune systems (AIS), the dendritic cell algorithm (DCA) has been successfully applied to a number of challenging real-world problems. However, one criticism is the lack of a formal definition, which could result in ambiguity for understanding the algorithm. Moreover, previous investigations have mainly focused on its empirical aspects. Therefore, it is necessary to provide a formal definition of the algorithm, as well as to perform runtime analyses to reveal its theoretical aspects. In this paper, we define the deterministic version of the DCA, named the dDCA, using set theory and mathematical functions. Runtime analyses of the standard algorithm and the one with additional segmentation are performed. Our analysis suggests that the standard dDCA has a runtime complexity of O(n2)O(n2) for the worst-case scenario, where n is the number of input data instances. The introduction of segmentation changes the algorithm's worst case runtime complexity to O(max(nN,nz))O(max(nN,nz)), for DC population size N with size of each segment z. Finally, two runtime variables of the algorithm are formulated based on the input data, to understand its runtime behaviour as guidelines for further development.

Journal Article Type Article
Publication Date Feb 1, 2013
Journal Biosystems
Print ISSN 0303-2647
Electronic ISSN 0303-2647
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 111
Issue 2
Pages 127-135
APA6 Citation Gu, F., Greensmith, J., & Aickelin, U. (2013). Theoretical formulation and analysis of the deterministic dendritic cell algorithm. BioSystems, 111(2), 127-135. doi:10.1016/j.biosystems.2013.01.001
DOI https://doi.org/10.1016/j.biosystems.2013.01.001
Keywords Artificial Immune Systems, Biomedical Informatics; Dendritic cell algorithm; Runtime analysis; Formulation and formalisation
Publisher URL http://www.sciencedirect.com/science/article/pii/S0303264713000063
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf
Additional Information NOTICE: this is the author’s version of a work that was accepted for publication in Biosystems. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Biosystems, 111(2), (2013), doi: 10.1016/j.biosystems.2013.01.001

Files

gu2013.pdf (361 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations

;