2023 [ nach oben ]

Friedrich, Tobias; Kötzing, Timo; Radhakrishnan, Aishwarya; Schiller, Leon; Schirneck, Martin; Tennigkeit, Georg; Wietheger, Simon Crossover for Cardinality Constrained OptimizationACM Transactions on Evolutionary Learning and Optimization 2023: 1–32
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
To understand better how and why crossover can benefit constrained optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1-bits allowed in the length-\(n\) bit string (i.e., a cardinality constraint). We investigate the natural translation of the OneMax test function to this setting, a linear function where \(B\) bits have a weight of \(1+ 1/n\) and the remaining bits have a weight of \(1\). Friedrich et al. [TCS 2020] gave a bound of \(\Theta(n^2)\) for the expected running time of the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping a \(1\) and a \(0\) simultaneously. The experimental literature proposes balanced operators, preserving the number of 1-bits, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as for classic bit mutation. Crossover together with a simple island model gives running times of \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming-distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution, we present an extensive analysis of different balanced crossover operators from the literature.
@article{friedrich2023crossover, abstract = {To understand better how and why crossover can benefit constrained optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1-bits allowed in the length-\(n\) bit string (i.e., a cardinality constraint). We investigate the natural translation of the OneMax test function to this setting, a linear function where \(B\) bits have a weight of \(1+ 1/n\) and the remaining bits have a weight of \(1\). Friedrich et al. [TCS 2020] gave a bound of \(\Theta(n^2)\) for the expected running time of the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping a \(1\) and a \(0\) simultaneously. The experimental literature proposes balanced operators, preserving the number of 1-bits, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as for classic bit mutation. Crossover together with a simple island model gives running times of \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming-distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution, we present an extensive analysis of different balanced crossover operators from the literature.}, author = {Friedrich, Tobias and Kötzing, Timo and Radhakrishnan, Aishwarya and Schiller, Leon and Schirneck, Martin and Tennigkeit, Georg and Wietheger, Simon}, journal = {ACM Transactions on Evolutionary Learning and Optimization}, keywords = {aishwaryaradhakrishnan georgtennigkeit leonschiller martinschirneck simonwietheger telo timokoetzing tobiasfriedrich year2023}, pages = {1-32}, title = {Crossover for Cardinality Constrained Optimization}, volume = 3, year = 2023 }

Friedrich, Tobias; Kötzing, Timo; Neumann, Aneta; Neumann, Frank; Radhakrishnan, Aishwarya Analysis of the (1+1) EA on LeadingOnes with ConstraintsGenetic and Evolutionary Computation Conference (GECCO ’23) 2023
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Understanding how evolutionary algorithms perform on constrained problems has gained increasing attention in recent years. In this paper, we study how evolutionary algorithms optimize constrained versions of the classical LeadingOnes problem. We first provide a run time analysis for the classical (1+1)~EA on the LeadingOnes problem with a deterministic cardinality constraint, giving $\Theta(n (n-B)\log(B) + n^2)$ as the tight bound. Our results show that the behaviour of the algorithm is highly dependent on the constraint bound of the uniform constraint. Afterwards, we consider the problem in the context of stochastic constraints and provide insights using experimental studies on how the ($\mu$+1)~EA is able to deal with these constraints in a sampling-based setting.
@inproceedings{friedrich2023analysis, abstract = {Understanding how evolutionary algorithms perform on constrained problems has gained increasing attention in recent years. In this paper, we study how evolutionary algorithms optimize constrained versions of the classical LeadingOnes problem. We first provide a run time analysis for the classical (1+1) EA on the LeadingOnes problem with a deterministic cardinality constraint, giving $\Theta(n (n-B)\log(B) + n^2)$ as the tight bound. Our results show that the behaviour of the algorithm is highly dependent on the constraint bound of the uniform constraint. Afterwards, we consider the problem in the context of stochastic constraints and provide insights using experimental studies on how the ($\mu$+1) EA is able to deal with these constraints in a sampling-based setting.}, author = {Friedrich, Tobias and Kötzing, Timo and Neumann, Aneta and Neumann, Frank and Radhakrishnan, Aishwarya}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO '23)}, keywords = {aishwaryaradhakrishnan gecco timokoetzing tobiasfriedrich year2023}, title = {Analysis of the (1+1) EA on LeadingOnes with Constraints}, year = 2023 }

2022 [ nach oben ]

Friedrich, Tobias; Kötzing, Timo; Radhakrishnan, Aishwarya; Schiller, Leon; Schirneck, Martin; Tennigkeit, Georg; Wietheger, Simon Crossover for Cardinality Constrained OptimizationGenetic and Evolutionary Computation Conference (GECCO) 2022: 1399–1407
Best Paper Award (Theory Track)
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where \(B\) bits have a weight of \(1+\varepsilon\) and the remaining bits have a weight of \(1\). The literature gives a bound of \(\Theta(n^2)\) for the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as classic bit flip mutation. Crossover and a simple island model gives \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution we analyze and discuss different balanced crossover operators from the literature.
@inproceedings{friedrich2022crossover, abstract = {In order to understand better how and why crossover can benefit optimization, we consider pseudo-Boolean functions with an upper bound \(B\) on the number of 1s allowed in the bit string (cardinality constraint). We consider the natural translation of the OneMax test function, a linear function where \(B\) bits have a weight of \(1+\varepsilon\) and the remaining bits have a weight of \(1\). The literature gives a bound of \(\Theta(n^2)\) for the (1+1) EA on this function. Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping both a 1 and a 0. The experimental literature proposes balanced operators, preserving the number of 1s, as a remedy. We show that a balanced mutation operator optimizes the problem in \(O(n \log n)\) if \(n-B = O(1)\). However, if \(n-B = \Theta(n)\), we show a bound of \(\Omega(n^2)\), just as classic bit flip mutation. Crossover and a simple island model gives \(O(n^2 / \log n)\) (uniform crossover) and \(O(n\sqrt{n})\) (3-ary majority vote crossover). For balanced uniform crossover with Hamming distance maximization for diversity we show a bound of \(O(n \log n)\). As an additional contribution we analyze and discuss different balanced crossover operators from the literature.}, author = {Friedrich, Tobias and Kötzing, Timo and Radhakrishnan, Aishwarya and Schiller, Leon and Schirneck, Martin and Tennigkeit, Georg and Wietheger, Simon}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {aishwaryaradhakrishnan gecco georgtennigkeit leonschiller martinschirneck simonwietheger timokoetzing tobiasfriedrich year2022}, note = {Best Paper Award (Theory Track)}, pages = {1399–1407}, title = {Crossover for Cardinality Constrained Optimization}, year = 2022 }

Friedrich, Tobias; Kötzing, Timo; Neumann, Frank; Radhakrishnan, Aishwarya Theoretical Study of Optimizing Rugge Landscapes with the cGAParallel Problem Solving From Nature (PPSN) 2022: 586–599
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Estimation of distribution algorithms (EDAs) provide a distribution-based approach for optimization which adapts its probability distribution during the run of the algorithm. We contribute to the theoretical understanding of EDAs and point out that their distribution approach makes them more suitable to deal with rugged fitness landscapes than classical local search algorithms. Concretely, we make the OneMax function rugged by adding noise to each fitness value. The cGA can nevertheless find solutions with \(n (1 - \epsilon )\) many 1s, even for high variance of noise. In contrast to this, RLS and the (1+1) EA, with high probability, only find solutions with \(n(1/2 + o(1)) \) many 1s, even for noise with small variance.
@inproceedings{friedrich2022theoretical, abstract = {Estimation of distribution algorithms (EDAs) provide a distribution-based approach for optimization which adapts its probability distribution during the run of the algorithm. We contribute to the theoretical understanding of EDAs and point out that their distribution approach makes them more suitable to deal with rugged fitness landscapes than classical local search algorithms. Concretely, we make the OneMax function rugged by adding noise to each fitness value. The cGA can nevertheless find solutions with \(n (1 - \epsilon )\) many 1s, even for high variance of noise. In contrast to this, RLS and the (1+1) EA, with high probability, only find solutions with \(n(1/2 + o(1)) \) many 1s, even for noise with small variance.}, author = {Friedrich, Tobias and Kötzing, Timo and Neumann, Frank and Radhakrishnan, Aishwarya}, booktitle = {Parallel Problem Solving From Nature (PPSN)}, keywords = {aishwaryaradhakrishnan frankneumann ppsn timokoetzing tobiasfriedrich year2022}, pages = {586–599}, title = {Theoretical Study of Optimizing Rugge Landscapes with the cGA}, year = 2022 }