Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/113404
Citations
Scopus Web of Science® Altmetric
?
?
Full metadata record
DC FieldValueLanguage
dc.contributor.authorShi, F.en
dc.contributor.authorSchirneck, M.en
dc.contributor.authorFriedrich, T.en
dc.contributor.authorKötzing, T.en
dc.contributor.authorNeumann, F.en
dc.date.issued2019en
dc.identifier.citationAlgorithmica, 2019; 81(2):1-30en
dc.identifier.issn0178-4617en
dc.identifier.issn1432-0541en
dc.identifier.urihttp://hdl.handle.net/2440/113404-
dc.description.abstractRigorous runtime analysis is a major approach towards understanding evolutionary computing techniques, and in this area linear pseudo-Boolean objective functions play a central role. Having an additional linear constraint is then equivalent to the NP-hard Knapsack problem, certain classes thereof have been studied in recent works. In this article, we present a dynamic model of optimizing linear functions under uniform constraints. Starting from an optimal solution with respect to a given constraint bound, we investigate the runtimes that different evolutionary algorithms need to recompute an optimal solution when the constraint bound changes by a certain amount. The classical (1+1) EA and several population-based algorithms are designed for that purpose, and are shown to recompute efficiently. Furthermore, a variant of the (1+(λ,λ)) GA for the dynamic optimization problem is studied, whose performance is better when the change of the constraint bound is small.en
dc.description.statementofresponsibilityFeng Shi, Martin Schirneck, Tobias Friedrich, Timo Kötzing, Frank Neumannen
dc.language.isoenen
dc.publisherSpringeren
dc.rights© Springer Science+Business Media, LLC, part of Springer Nature 2018en
dc.subjectEvolutionary algorithm; Runtime analysis; Reoptimization time; Dynamic constraint; Uniform constrainten
dc.titleReoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraintsen
dc.typeJournal articleen
dc.identifier.rmid0030088745en
dc.identifier.doi10.1007/s00453-018-0451-4en
dc.relation.granthttp://purl.org/au-research/grants/arc/DP140103400en
dc.relation.granthttp://purl.org/au-research/grants/arc/DP160102401en
dc.identifier.pubid421657-
pubs.library.collectionComputer Science publicationsen
pubs.library.teamDS05en
pubs.verification-statusVerifieden
pubs.publication-statusPublisheden
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.