2024 [ nach oben ]

Harder, Jonathan Gadea; Kötzing, Timo; Li, Xiaoyue; Radhakrishnan, Aishwarya; Ruff, Janosch Run Time Bounds for Integer-Valued OneMax FunctionsGenetic and Evolutionary Computation Conference (GECCO ’24) 2024
[ BibTeX ] [ DOI ] [ Download ]
 
@conference{2024bounds, author = {Harder, Jonathan Gadea and Kötzing, Timo and Li, Xiaoyue and Radhakrishnan, Aishwarya and Ruff, Janosch}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO '24)}, keywords = {sys:relevantfor:ae aishwaryaradhakrishnan gecco janoschruff jonathangadeaharder timokoetzing xiaoyueli year2024}, title = {Run Time Bounds for Integer-Valued OneMax Functions}, year = 2024 }

Li, Xiaoyue; Kötzing, Timo Algorithm Performance Comparison for Integer-Valued OneMaxGenetic and Evolutionary Computation Conference (GECCO ’24 Companion) 2024: 407–410
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Recently, several continuous-domain optimizers have been employed to solve mixed-integer black box optimization (MI-BBO) problems by adjusting them to handle the discrete variables as well. In this work we want to compare how these adjusted algorithms perform on purely discrete variables when compared with algorithms designed to handle discrete domains. We use the algorithm RLS from the literature, which was analyzed theoretically on a specific problem class. We experimentally optimize the parameters a and b for further analysis. Second, we make a comprehensive comparison of RLS with algorithms from the continuous domain on a generalization of OneMax to Z. We find that RLS shows better performance on this discrete benchmark functions than the other algorithms. Overall, these results show that adaptations of continuous algorithms are not suited for MI-BBO problems, and that research combining the strengths of both approaches is more promising.
@inproceedings{li2024algorithm, abstract = {Recently, several continuous-domain optimizers have been employed to solve mixed-integer black box optimization (MI-BBO) problems by adjusting them to handle the discrete variables as well. In this work we want to compare how these adjusted algorithms perform on purely discrete variables when compared with algorithms designed to handle discrete domains. We use the algorithm RLS from the literature, which was analyzed theoretically on a specific problem class. We experimentally optimize the parameters a and b for further analysis. Second, we make a comprehensive comparison of RLS with algorithms from the continuous domain on a generalization of OneMax to Z. We find that RLS shows better performance on this discrete benchmark functions than the other algorithms. Overall, these results show that adaptations of continuous algorithms are not suited for MI-BBO problems, and that research combining the strengths of both approaches is more promising.}, address = {New York, NY, USA}, author = {Li, Xiaoyue and Kötzing, Timo}, booktitle = {Proceedings of the Genetic and Evolutionary Computation Conference Companion}, journal = {Genetic and Evolutionary Computation Conference (GECCO ’24 Companion)}, keywords = {comparison gecco performance timokoetzing xiaoyueli year2024}, month = {July}, pages = {407–410}, publisher = {Association for Computing Machinery}, series = {GECCO '24 Companion}, title = {Algorithm Performance Comparison for Integer-Valued OneMax}, year = 2024 }

2023 [ nach oben ]

Li, Xiaoyue; Kötzing, Timo Experimental Analyses of Crossover on JumpGenetic and Evolutionary Computation Conference (GECCO) 2023
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
While it is mathematically proven that the \((\mu+1)\) GA optimizes \(\mathrm{jump}_{k}\) efficiently for low crossover probabilities, theory research still struggles with the analysis of crossover-based optimization for high crossover probabilities on this key test function. Research in this area has improved our understanding of crossover in general, in particular regarding the emergence of diversity, the crucial ingredient for successful optimization with genetic algorithms. In this paper we study the optimizing process after the \((\mu+1)\) GA has reached the plateau of \(\mathrm{jump}_{k}\). We are interested in (a) the stationary distribution of the algorithm on the plateau (when ignoring the optimum) and (b) the dynamics of the stationary distribution. We experimentally show that the \((\mu+1)\) GA achieves 10\% complementary pairs if \(\mu = 10 \cdot k\), unless \(n\) is very small. Regarding the dynamics, we show samples of how bit positions gain and lose individuals with a \(0\) at that position.
@inproceedings{friedrich2023analysis, abstract = {While it is mathematically proven that the \((\mu+1)\) GA optimizes \(\mathrm{jump}_{k}\) efficiently for low crossover probabilities, theory research still struggles with the analysis of crossover-based optimization for high crossover probabilities on this key test function. Research in this area has improved our understanding of crossover in general, in particular regarding the emergence of diversity, the crucial ingredient for successful optimization with genetic algorithms. In this paper we study the optimizing process after the \((\mu+1)\) GA has reached the plateau of \(\mathrm{jump}_{k}\). We are interested in (a) the stationary distribution of the algorithm on the plateau (when ignoring the optimum) and (b) the dynamics of the stationary distribution. We experimentally show that the \((\mu+1)\) GA achieves 10\% complementary pairs if \(\mu = 10 \cdot k\), unless \(n\) is very small. Regarding the dynamics, we show samples of how bit positions gain and lose individuals with a \(0\) at that position.}, author = {Li, Xiaoyue and Kötzing, Timo}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {gecco timokoetzing xiaoyueli year2023}, title = {Experimental Analyses of Crossover on Jump}, year = 2023 }

2022 [ nach oben ]

Baguley, Samuel; Friedrich, Tobias; Timo, Kötzing; Li, Xiaoyue; Pappik, Marcus; Zeif, Ziena Analysis of a Gray-Box Operator for Vertex CoverGenetic and Evolutionary Computation Conference (GECCO) 2022: 1363–1371
[ Abstract ] [ BibTeX ] [ URL ] [ DOI ] [ Download ]
 
Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size \(n\). Regarding the path we prove that, for a particular initial configuration, the (1+1) EA takes in expectation \(\Theta(n^4)\) iterations while the modification reduces this to \(\Theta(n^3)\), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability \(1-1/2^{\Omega(n^\xi)}\) for every positive constant \(\xi < 1\), which improves the known probability of \(1-1/\)poly\((n)\) for the (1+1) EA.
@inproceedings{baguley2022analysis, abstract = {Combinatorial optimization problems are a prominent application area of evolutionary algorithms, where the (1+1) EA is one of the most investigated. We extend this algorithm by introducing some problem knowledge with a specialized mutation operator which works under the assumption that the number of 1s of a solution is critical, as frequently happens in combinatorial optimization. This slight modification increases the chance to correct wrongly placed bits while preserving the simplicity and problem independence of the (1+1) EA. As an application of our algorithm we examine the vertex cover problem on certain instances, where we show that it leads to asymptotically better runtimes and even finds with higher probability optimal solutions in comparison with the usual (1+1) EA. Precisely, we compare the performance of both algorithms on paths and on complete bipartite graphs of size \(n\). Regarding the path we prove that, for a particular initial configuration, the (1+1) EA takes in expectation \(\Theta(n^4)\) iterations while the modification reduces this to \(\Theta(n^3)\), and present experimental evidence that such a configuration is reached. Concerning the complete bipartite graph our modification finds the optimum in polynomial time with probability \(1-1/2^{\Omega(n^\xi)}\) for every positive constant \(\xi < 1\), which improves the known probability of \(1-1/\)poly\((n)\) for the (1+1) EA.}, author = {Baguley, Samuel and Friedrich, Tobias and Timo, Kötzing and Li, Xiaoyue and Pappik, Marcus and Zeif, Ziena}, booktitle = {Genetic and Evolutionary Computation Conference (GECCO)}, keywords = {sys:relevantfor:ae gecco marcuspappik samuelbaguley timokoetzing tobiasfriedrich xiaoyueli year2022 zienazeif}, pages = {1363&ndash;1371}, title = {Analysis of a Gray-Box Operator for Vertex Cover}, year = 2022 }