Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints
- PDF / 615,528 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 90 Downloads / 168 Views
Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints Feng Shi1 · Martin Schirneck2 · Tobias Friedrich2 · Timo Kötzing2 · Frank Neumann3
Received: 31 August 2017 / Accepted: 3 May 2018 © Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract Rigorous 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. Keywords Evolutionary algorithm · Runtime analysis · Reoptimization time · Dynamic constraint · Uniform constraint
A preliminary version of this work was presented at the 2017 Genetic and Evolutionary Computation Conference (GECCO) [18].
B
Feng Shi [email protected]
1
School of Information Science and Engineering, Central South University, Changsha, Hunan, People’s Republic of China
2
Hasso Plattner Institute, Potsdam, Germany
3
School of Computer Science, The University of Adelaide, Adelaide, Australia
123
Algorithmica
1 Introduction Evolutionary computation has been widely used in practice to solve problems that arise in various domains in engineering and economics. To understand evolutionary computing techniques also on a theoretical basis, rigorous runtime analysis has become a major approach over the last 20 years [1,10,17]. In this area the class of linear pseudoBoolean functions plays a crucial role. The first such analysis aimed at the classical (1+1) evolutionary algorithm, (1+1) EA, on the simplest linear function OneMax (maximize the number of 1-bits in a bit string) [15]. Since then the runtime of the (1+1) EA on the class of all linear functions has become a hot issue, and various proof techniques have been developed. While inferring the asymptotic runtime, a deep understanding of the internal mechanisms of the (1+1) EA has been gained. This has led to the famous (n log n) bound [6]. More detailed studies later pushed the insights even further and revealed the leading constants [5,12,19]. We are now interested in the behaviors of nature-inspired algorithms on constrained problems. That means, only search points satisfying a certain condition are considered as solutions to the problem. Various constraint handlin
Data Loading...
