Fast Immune System Inspired Hypermutation Operators for Combinatorial Optimisation

dc.contributor.authorÇörüş, Doğan
dc.contributor.authorOliveto, Pietro Simone
dc.contributor.authorYazdani, Donya
dc.date.accessioned2021-05-15T13:01:24Z
dc.date.available2021-05-15T13:01:24Z
dc.date.issued2021
dc.description.abstractVarious studies have shown that immune system inspired hypermutation operators can allow artificial immune systems (AIS) to be very efficient at escaping local optima of multimodal optimisation problems. However, this efficiency comes at the expense of considerably slower runtimes during the exploitation phase compared to standard evolutionary algorithms. We propose modifications to the traditional ‘hypermutations with mutation potential’ (HMP) that allow them to be efficient at exploitation as well as maintaining their effective explorative characteristics. Rather than deterministically evaluating fitness after each bit-flip of a hypermutation, we sample the fitness function stochastically with a ‘parabolic’ distribution. This allows the ‘stop at first constructive mutation’ (FCM) variant of HMP to reduce the linear amount of wasted function evaluations when no improvement is found to a constant. The stochastic distribution also allows the removal of the FCM mechanism altogether as originally desired in the design of the HMP operators. We rigorously prove the effectiveness of the proposed operators for all the benchmark functions where the performance of HMP is rigorously understood in the literature. We validate the gained insights to show linear speed-ups for the identification of high quality approximate solutions to classical NP-Hard problems from combinatorial optimisation. We then show the superiority of the HMP operators to the traditional ones in an analysis of the complete standard Opt-IA AIS, where the stochastic evaluation scheme allows HMP and ageing operators to work in harmony. Through a comparative performance study of other ‘fast mutation’ operators from the literature, we conclude that a power-law distribution for the parabolic evaluation scheme is the best compromise in black-box scenarios where little problem knowledge is available.en_US
dc.identifier.citation8
dc.identifier.doi10.1109/TEVC.2021.3068574en_US
dc.identifier.issn1089-778Xen_US
dc.identifier.issn1089-778X
dc.identifier.scopus2-s2.0-85103248909en_US
dc.identifier.scopusqualityQ1
dc.identifier.urihttps://hdl.handle.net/20.500.12469/4022
dc.identifier.wosWOS:000702556400016en_US
dc.identifier.wosqualityQ1
dc.institutionauthorÇörüş, Doğanen_US
dc.language.isoenen_US
dc.publisherInstitute of Electrical and Electronics Engineers Inc.en_US
dc.relation.journalIEEE Transactions on Evolutionary Computationen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectAgingen_US
dc.subjectArtificial immune systemsen_US
dc.subjectArtificial intelligenceen_US
dc.subjectBenchmark testingen_US
dc.subjectHypermutationen_US
dc.subjectImmune systemen_US
dc.subjectOptimizationen_US
dc.subjectRuntimeen_US
dc.subjectRuntime analysis.en_US
dc.subjectStandardsen_US
dc.titleFast Immune System Inspired Hypermutation Operators for Combinatorial Optimisationen_US
dc.typeArticleen_US
dspace.entity.typePublication
relation.isAuthorOfPublication7342534c-06be-40f2-9933-f1249a97ad3a
relation.isAuthorOfPublication.latestForDiscovery7342534c-06be-40f2-9933-f1249a97ad3a

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
09385420.pdf
Size:
1.1 MB
Format:
Adobe Portable Document Format
Description: