Publications | Theory of Evolutionary Computation @UoB

2024

A Self-adaptive Coevolutionary Algorithm
Mario Alejandro Hevia Fajardo, Erik Hemberg, Jamal Toutouh, Una-May O’Reilly, and Per Kristian Lehre

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2024

Abs Bib

Coevolutionary algorithms are helpful computational abstractions of adversarial behavior and they demonstrate multiple ways that populations of competing adversaries influence one another. We introduce the ability for each competitor’s mutation rate to evolve through self-adaptation. Because dynamic environments are frequently addressed with self-adaptation, we set up dynamic problem environments to investigate the impact of this ability. For a simple bilinear problem, a sensitivity analysis of the adaptive method’s parameters reveals that it is robust over a range of multiplicative rate factors, when the rate is changed up or down with equal probability. An empirical study determines that each population’s mutation rates converge to values close to the error threshold. Mutation rate dynamics are complex when both populations adapt their rates. Large scale empirical self-adaptation results reveal that both reasonable solutions and rates can be found. This addresses the challenge of selecting ideal static mutation rates in coevolutionary algorithms. The algorithm’s payoffs are also robust. They are rarely poor and frequently they are as high as the payoff of the static rate to which they converge. On rare runs, they are higher.
@inproceedings{hevia_fajardo_self-adaptive_2024, address = {New York, NY, USA}, author = {Hevia Fajardo, Mario Alejandro and Hemberg, Erik and Toutouh, Jamal and O'Reilly, Una-May and Lehre, Per Kristian}, booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3638529.3654132}, isbn = {9798400704949}, month = jul, note = {}, pages = {841--849}, publisher = {Association for Computing Machinery}, series = {{GECCO} '24}, title = {A {Self}-adaptive {Coevolutionary} {Algorithm}}, url = {https://dl.acm.org/doi/10.1145/3638529.3654132}, urldate = {2024-10-04}, year = {2024}, }
The SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary Algorithms
Duc-Cuong Dang, and Per Kristian Lehre

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2024

Abs Bib

While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang et al. (2021) introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs. However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy.We generalise the previous work to a complete hierarchy for all pseudo-Boolean functions. The hierarchy is consistent with existing results for the runtime of EAs. The hardest part of the hierarchy consists of problems satisfying the No Free Lunch theorem. The easiest part contains well-known theoretical benchmark problems, easy for EAs. The intermediary parts contain instances of NP-hard problems. Problem classes where local optima sparsity exceed fitness valley density are shown to have exponential black-box complexity. We study how random perturbations of a function can change its classification. E.g, randomly perturbing search points in OneMax with constant probability leads to a problem class that can still be optimised efficiently with appropriately tuned non-elitist EAs.
@inproceedings{dang_slo_2024, address = {New York, NY, USA}, author = {Dang, Duc-Cuong and Lehre, Per Kristian}, booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3638529.3654221}, isbn = {9798400704949}, month = jul, note = {}, pages = {1551--1559}, publisher = {Association for Computing Machinery}, series = {{GECCO} '24}, title = {The {SLO} {Hierarchy} of pseudo-{Boolean} {Functions} and {Runtime} of {Evolutionary} {Algorithms}}, url = {https://dl.acm.org/doi/10.1145/3638529.3654221}, urldate = {2024-10-04}, year = {2024}, }
Runtime Analysis of Coevolutionary Algorithms on a Class of Symmetric Zero-Sum Games
Alistair Benford, and Per Kristian Lehre

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2024

Abs Bib

A standard aim in game theory is to find a pure or mixed Nash equilibrium. For strategy spaces too large for a Nash equilibrium to be computed classically, this can instead be approached using a co-evolutionary algorithm. How to design coevolutionary algorithms which avoid pathological behaviours (such as cycling or forgetting) on challenging games is then a crucial open problem.We argue that runtime analysis can provide insight and inform the design of more powerful and reliable algorithms for this purpose. To this end, we consider a class of symmetric zero-sum games for which the role of population diversity is pivotal to an algorithm’s success. We prove that a broad class of algorithms which do not utilise a population have superpolynomial runtime for this class. In the other direction we prove that, with high probability, a coevolutionary instance of the univariate marginal distribution algorithm finds the unique Nash equilibrium in time O(n(log n)2).Together, these results demonstrate the importance of generating diverse search points for evolving better strategies. The corresponding proofs develop several techniques that may benefit future analysis of estimation of distribution and coevolutionary algorithms.
@inproceedings{benford_runtime_2024, address = {New York, NY, USA}, author = {Benford, Alistair and Lehre, Per Kristian}, booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3638529.3654216}, isbn = {9798400704949}, month = jul, note = {}, pages = {1542--1550}, publisher = {Association for Computing Machinery}, series = {{GECCO} '24}, title = {Runtime {Analysis} of {Coevolutionary} {Algorithms} on a {Class} of {Symmetric} {Zero}-{Sum} {Games}}, url = {https://dl.acm.org/doi/10.1145/3638529.3654216}, urldate = {2024-10-04}, year = {2024}, }
Bicriteria Optimisation of Average and Worst-Case Performance Using Coevolutionary Algorithms
Alistair Benford, Markus Olhofer, Tobias Rodemann, and Per Kristian Lehre

In 2024 IEEE Congress on Evolutionary Computation (CEC), Jun 2024

Abs Bib

A common aim in real-world optimisation problems is to seek a solution offering highest performance on expected scenarios, but at the same time guaranteeing an at least acceptable performance on worst-case scenarios. Competitive coevolution evolves a population of solutions alongside a population of difficult scenarios in order to find so-called robust solutions. However, solutions with maximal worst-case performance often exhibit poor performance on more typical scenarios. Existing coevolutionary approaches generally favour such solutions over ones which sacrifice only a small amount of average performance for an almost as large gain in worst-case performance, despite the latter being favourable in most practical applications. We present a new coevolutionary algorithm which treats average performance and worst-case performance as two objectives of a bicriteria optimisation problem and seeks the corresponding Pareto front. Such an algorithm enables the discovery of solutions with strong performance in both of these metrics, which would otherwise be rejected if optimising for only one. Our algorithm constitutes the first coevolutionary approach to this solution concept. We also provide experimental results on the performance of this algorithm on the design of smart controllers for the management of energy flow between buildings, renewable energy sources, and electric vehicles.
@inproceedings{benford_bicriteria_2024, author = {Benford, Alistair and Olhofer, Markus and Rodemann, Tobias and Lehre, Per Kristian}, booktitle = {2024 {IEEE} {Congress} on {Evolutionary} {Computation} ({CEC})}, doi = {10.1109/CEC60901.2024.10611909}, keywords = {Electric vehicles, Evolutionary computation, Measurement, Pareto optimization, Renewable energy sources, Sociology, Statistics}, month = jun, note = {}, pages = {1--8}, title = {Bicriteria {Optimisation} of {Average} and {Worst}-{Case} {Performance} {Using} {Coevolutionary} {Algorithms}}, url = {https://ieeexplore.ieee.org/document/10611909/?arnumber=10611909}, urldate = {2024-10-04}, year = {2024}, }
Runtime Analysis of Competitive Co-evolutionary Algorithms for Maximin Optimisation of a Bilinear Function
Per Kristian Lehre

Algorithmica, Apr 2024

Abs Bib

Co-evolutionary algorithms have a wide range of applications, such as in hardware design, evolution of strategies for board games, and patching software bugs. However, these algorithms are poorly understood and applications are often limited by pathological behaviour, such as loss of gradient, relative over-generalisation, and mediocre objective stasis. It is an open challenge to develop a theory that can predict when co-evolutionary algorithms find solutions efficiently and reliable. This paper provides a first step in developing runtime analysis for population-based competitive co-evolutionary algorithms. We provide a mathematical framework for describing and reasoning about the performance of co-evolutionary processes. To illustrate the framework, we introduce a population-based co-evolutionary algorithm called PDCoEA, and prove that it obtains a solution to a bilinear maximin optimisation problem in expected polynomial time. Finally, we describe settings where PDCoEA needs exponential time with overwhelmingly high probability to obtain a solution.
@article{lehre_runtime_2024, author = {Lehre, Per Kristian}, doi = {10.1007/s00453-024-01218-3}, issn = {1432-0541}, journal = {Algorithmica}, keywords = {Co-evolutionary algorithms, Evolutionary computation, Game theory, Runtime analysis}, language = {en}, month = apr, note = {}, title = {Runtime {Analysis} of {Competitive} {Co}-evolutionary {Algorithms} for {Maximin} {Optimisation} of a {Bilinear} {Function}}, url = {https://doi.org/10.1007/s00453-024-01218-3}, urldate = {2024-05-13}, year = {2024}, }
More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain Environments
Per Kristian Lehre, and Xiaoyu Qin

Algorithmica, Feb 2024

Abs Bib

Real-world applications often involve “uncertain” objectives, i.e., where optimisation algorithms observe objective values as a random variables with positive variance. In the past decade, several rigorous analysis results for evolutionary algorithms (EAs) on discrete problems show that EAs can cope with low-level uncertainties, i.e. when the variance of the uncertain objective value is small, and sometimes even benefit from uncertainty. Previous work showed that a large population combined with a non-elitist selection mechanism is a promising approach to handle high levels of uncertainty. However, the population size and the mutation rate can dramatically impact the performance of non-elitist EAs, and the optimal choices of these parameters depend on the level of uncertainty in the objective function. The performance and the required parameter settings for non-elitist EAs in some common objective-uncertainty scenarios are still unknown. We analyse the runtime of non-elitist EAs on two classical benchmark problems OneMax and LeadingOnes in in the one-bit, the bitwise, the Gaussian, and the symmetric noise models, and the dynamic binary value problem (DynBV). Our analyses are more extensive and precise than previous analyses of non-elitist EAs. In several settings, we prove that the non-elitist EAs outperform the current state-of-the-art results. Furthermore, we provide more precise guidance on how to choose the mutation rate, the selective pressure, and the population size as a function of the level of uncertainty.
@article{lehre_more_2024, author = {Lehre, Per Kristian and Qin, Xiaoyu}, doi = {10.1007/s00453-022-01044-5}, issn = {1432-0541}, journal = {Algorithmica}, month = feb, note = {}, number = {2}, pages = {396--441}, title = {More {Precise} {Runtime} {Analyses} of {Non}-elitist {Evolutionary} {Algorithms} in {Uncertain} {Environments}}, url = {https://doi.org/10.1007/s00453-022-01044-5}, volume = {86}, year = {2024}, }
Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms
Per Kristian Lehre, and Shishen Lin

In Proceedings of the Thirty-ThirdInternational Joint Conference on Artificial Intelligence, Aug 2024

Abs Bib

Runtime analysis, as a branch of the theory of AI, studies how the number of iterations algorithms take before finding a solution (its runtime) depends on the design of the algorithm and the problem structure. Drift analysis is a state-of-the-art tool for estimating the runtime of randomised algorithms, such as evolutionary and bandit algorithms. Drift refers roughly to the expected progress towards the optimum per iteration. This paper considers the problem of deriving concentration tail-bounds on the runtime/regret of algorithms. It provides a novel drift theorem that gives precise exponential tail-bounds given positive, weak, zero and even negative drift. Previously, such exponential tail bounds were missing in the case of weak, zero, or negative drift.
@inproceedings{lehre_concentration_2024, address = {Jeju, South Korea}, author = {Lehre, Per Kristian and Lin, Shishen}, booktitle = {Proceedings of the {Thirty}-{ThirdInternational} {Joint} {Conference} on {Artificial} {Intelligence}}, doi = {10.24963/ijcai.2024/767}, isbn = {978-1-956792-04-1}, language = {en}, month = aug, note = {}, pages = {6940--6948}, publisher = {International Joint Conferences on Artificial Intelligence Organization}, title = {Concentration {Tail}-{Bound} {Analysis} of {Coevolutionary} and {Bandit} {Learning} {Algorithms}}, url = {https://www.ijcai.org/proceedings/2024/767}, urldate = {2024-11-18}, year = {2024}, }

No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation

Per Kristian Lehre, and Shishen Lin

In To appear Proceedings of Conference on Neural Information Processing Systems, Aug 2024

Bib

@inproceedings{lehre_no_2024,
  author = {Lehre, Per Kristian and Lin, Shishen},
  booktitle = {To appear {Proceedings} of {Conference} on {Neural} {Information} {Processing} {Systems}},
  note = {},
  title = {No {Free} {Lunch} {Theorem} and {Black}-{Box} {Complexity} {Analysis} for {Adversarial} {Optimisation}},
  year = {2024},
}

Ranking Diversity Benefits Coevolutionary Algorithms on an Intransitive Game

Mario Alejandro Hevia Fajardo, and Per Kristian Lehre

In Parallel Problem Solving from Nature – PPSN XVIII, Aug 2024

Abs Bib

Competitive coevolutionary algorithms (CoEAs) often encounter so-called coevolutionary pathologies particularly cycling behavior, which becomes more pronounced for games where there is no clear hierarchy of superiority among the possible strategies (intransitive games). In order to avoid these pathologies and ensure an efficient optimisation, it has been suggested that it is critical to choose a good evaluation environment (set of solutions used for evaluation).

@inproceedings{hevia_fajardo_ranking_2024,
  address = {Cham},
  author = {Hevia Fajardo, Mario Alejandro and Lehre, Per Kristian},
  booktitle = {Parallel {Problem} {Solving} from {Nature} – {PPSN} {XVIII}},
  doi = {10.1007/978-3-031-70071-2_14},
  editor = {Affenzeller, Michael and Winkler, Stephan M. and Kononova, Anna V. and Trautmann, Heike and Tušar, Tea and Machado, Penousal and Bäck, Thomas},
  isbn = {978-3-031-70071-2},
  keywords = {Archives, Competitive coevolution, Maximin optimisation, Runtime analysis},
  language = {en},
  note = {},
  pages = {213--229},
  publisher = {Springer Nature Switzerland},
  title = {Ranking {Diversity} {Benefits} {Coevolutionary} {Algorithms} on an {Intransitive} {Game}},
  year = {2024},
}

Overcoming Binary Adversarial Optimisation with Competitive Coevolution

Per Kristian Lehre, and Shishen Lin

In Parallel Problem Solving from Nature – PPSN XVIII, Aug 2024

Abs Bib

Co-evolutionary algorithms (CoEAs), which pair candidate designs with test cases, are frequently used in adversarial optimisation, particularly for binary test-based problems where designs and tests yield binary outcomes. The effectiveness of designs is determined by their performance against tests, and the value of tests is based on their ability to identify failing designs, often leading to more sophisticated tests and improved designs. However, CoEAs can exhibit complex, sometimes pathological behaviours like disengagement. Through runtime analysis, we aim to rigorously analyse whether CoEAs can efficiently solve test-based adversarial optimisation problems in an expected polynomial runtime.
@inproceedings{lehre_overcoming_2024, address = {Cham}, author = {Lehre, Per Kristian and Lin, Shishen}, booktitle = {Parallel {Problem} {Solving} from {Nature} – {PPSN} {XVIII}}, doi = {10.1007/978-3-031-70071-2_8}, editor = {Affenzeller, Michael and Winkler, Stephan M. and Kononova, Anna V. and Trautmann, Heike and Tušar, Tea and Machado, Penousal and Bäck, Thomas}, isbn = {978-3-031-70071-2}, keywords = {Adversarial Optimisation, Competitive Coevolution, Theory of Computation}, language = {en}, note = {}, pages = {117--132}, publisher = {Springer Nature Switzerland}, title = {Overcoming {Binary} {Adversarial} {Optimisation} with {Competitive} {Coevolution}}, year = {2024}, }
Analysis of a Pairwise Dominance Coevolutionary Algorithm with Spatial Topology
Mario Hevia Fajardo, Per Kristian Lehre, Jamal Toutouh, Erik Hemberg, and Una-May O’Reilly

In Genetic Programming Theory and Practice XX, Aug 2024

Abs Bib

Competitive coevolutionary algorithms are used to model adversarial dynamics. The diversity of the adversarial populations can be changed with a spatial topology. To achieve more clarity in how a spatial topology impacts performance and complexity we introduce a spatial topology to a pairwise dominance coevolutionary algorithm named PDCoEA. The new algorithm is called STPDCoEA. We use a methodology for consistent algorithm comparison to empirically study the impact of topology, problem, and mutation rates on the dynamics and payoffs in STPDCoEA. We compare records of multi-run dynamics on three problems and observe that the spatial topology impacts the performance and diversity.
@incollection{hevia_fajardo_analysis_2024, address = {Singapore}, author = {Hevia Fajardo, Mario and Lehre, Per Kristian and Toutouh, Jamal and Hemberg, Erik and O’Reilly, Una-May}, booktitle = {Genetic {Programming} {Theory} and {Practice} {XX}}, editor = {Winkler, Stephan and Trujillo, Leonardo and Ofria, Charles and Hu, Ting}, isbn = {978-981-9984-13-8}, language = {en}, note = {}, pages = {19--44}, publisher = {Springer Nature}, title = {Analysis of a {Pairwise} {Dominance} {Coevolutionary} {Algorithm} with {Spatial} {Topology}}, url = {https://doi.org/10.1007/978-981-99-8413-8_2}, urldate = {2024-05-02}, year = {2024}, }

2023

Runtime Analysis of a Co-Evolutionary Algorithm: Overcoming Negative Drift in Maximin-Optimisation
Mario Alejandro Hevia Fajardo, Per Kristian Lehre, and Shishen Lin

In Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Aug 2023

Abs Bib

Co-evolutionary algorithms have found several applications in game-theoretic applications and optimisation problems with an adversary, particularly where the strategy space is discrete and exponentially large, and where classical game-theoretic methods fail. However, the application of co-evolutionary algorithms is difficult because they often display pathological behaviour, such as cyclic behaviour and evolutionary forgetting. These challenges have prevented the broad application of co-evolutionary algorithms. We derive, via rigorous mathematical methods, bounds on the expected time of a simple co-evolutionary algorithm until it discovers a Maximin-solution on the pseudo-Boolean Bilinear problem. Despite the intransitive nature of the problem leading to a cyclic behaviour of the algorithm, we prove that the algorithm obtains the Maximin-solution in expected O(n1.5) time. However, we also show that the algorithm quickly forgets the Maximin-solution and moves away from it. These results in a large total regret of Θ(Tn1.5) after T iterations. Finally, we show that using a simple archive solves this problem reducing the total regret significantly. Along the way, we present new mathematical tools to compute the expected time for co-evolutionary algorithms to obtain a Maximin-solution. We are confident that these tools can help further advance runtime analysis in both co-evolutionary and evolutionary algorithms.
@inproceedings{hevia_fajardo_runtime_2023, address = {New York, NY, USA}, author = {Hevia Fajardo, Mario Alejandro and Lehre, Per Kristian and Lin, Shishen}, booktitle = {Proceedings of the 17th {ACM}/{SIGEVO} {Conference} on {Foundations} of {Genetic} {Algorithms}}, doi = {10.1145/3594805.3607132}, isbn = {9798400702020}, keywords = {Competitive coevolution, Maximin Optimisation, Runtime analysis}, month = aug, note = {}, pages = {73--83}, publisher = {Association for Computing Machinery}, series = {{FOGA} '23}, shorttitle = {Runtime {Analysis} of a {Co}-{Evolutionary} {Algorithm}}, title = {Runtime {Analysis} of a {Co}-{Evolutionary} {Algorithm}: {Overcoming} {Negative} {Drift} in {Maximin}-{Optimisation}}, url = {https://dl.acm.org/doi/10.1145/3594805.3607132}, urldate = {2024-05-02}, year = {2023}, }
Self-adjusting Population Sizes for Non-elitist Evolutionary Algorithms: Why Success Rates Matter
Mario Alejandro Hevia Fajardo, and Dirk Sudholt

Algorithmica, Jul 2023

Abs Bib

Evolutionary algorithms (EAs) are general-purpose optimisers that come with several parameters like the sizes of parent and offspring populations or the mutation rate. It is well known that the performance of EAs may depend drastically on these parameters. Recent theoretical studies have shown that self-adjusting parameter control mechanisms that tune parameters during the algorithm run can provably outperform the best static parameters in EAs on discrete problems. However, the majority of these studies concerned elitist EAs and we do not have a clear answer on whether the same mechanisms can be applied for non-elitist EAs. We study one of the best-known parameter control mechanisms, the one-fifth success rule, to control the offspring population size \{}lambda \∈the non-elitist \\{(1,}lambda )}\\ EA. It is known that the \\{(1,}lambda )}\\ EA has a sharp threshold with respect to the choice of \{}lambda \\where the expected runtime on the benchmark function OneMax changes from polynomial to exponential time. Hence, it is not clear whether parameter control mechanisms are able to find and maintain suitable values of \{}lambda \\. For OneMax we show that the answer crucially depends on the success rate s (i. e. a one-\\(s+1)\\-th success rule). We prove that, if the success rate is appropriately small, the self-adjusting \\{(1,}lambda )}\\ EA optimises OneMax in O(n) expected generations and \Ø(n }log n)\\expected evaluations, the best possible runtime for any unary unbiased black-box algorithm. A small success rate is crucial: we also show that if the success rate is too large, the algorithm has an exponential runtime on OneMax and other functions with similar characteristics.
@article{hevia_fajardo_self-adjusting_2023, author = {Hevia Fajardo, Mario Alejandro and Sudholt, Dirk}, doi = {10.1007/s00453-023-01153-9}, issn = {1432-0541}, journal = {Algorithmica}, keywords = {Evolutionary algorithms, Non-elitism, Parameter control, Runtime analysis, Theory}, language = {en}, month = jul, note = {}, shorttitle = {Self-adjusting {Population} {Sizes} for {Non}-elitist {Evolutionary} {Algorithms}}, title = {Self-adjusting {Population} {Sizes} for {Non}-elitist {Evolutionary} {Algorithms}: {Why} {Success} {Rates} {Matter}}, url = {https://doi.org/10.1007/s00453-023-01153-9}, urldate = {2023-07-25}, year = {2023}, }
Self-adaptation Can Help Evolutionary Algorithms Track Dynamic Optima
Per Kristian Lehre, and Xiaoyu Qin

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2023

Abs Bib

Real-world optimisation problems often involve dynamics, where objective functions may change over time. Previous studies have shown that evolutionary algorithms (EAs) can solve dynamic optimisation problems. Additionally, the use of diversity mechanisms, populations, and parallelisation can enhance the performance of EAs in dynamic environments if appropriate parameter settings are utilised. Self-adaptation, which encodes parameters in genotypes of individuals and allows them to evolve together with solutions, can help configure parameters of EAs. This parameter control mechanism has been proved to effectively handle a static problem with unknown structure. However, the benefit of self-adaptation on dynamic optimisation problems remains unknown. We consider a tracking dynamic optima problem, the so-called Dynamic Substring Matching (DSM) problem, which requires algorithms to successively track a sequence of structure-changing optima. Our analyses show that mutation-based EAs with a fixed mutation rate have a negligible chance of tracking these dynamic optima, while the self-adaptive EA tracks them with an overwhelmingly high probability. Furthermore, we provide a level-based theorem with tail bounds, which bounds the chance of the algorithm finding the current optima within a given evaluation budget. Overall, self-adaptation is promising for tracking dynamic optima.
@inproceedings{lehre_self-adaptation_2023, address = {New York, NY, USA}, author = {Lehre, Per Kristian and Qin, Xiaoyu}, booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3583131.3590494}, isbn = {9798400701191}, keywords = {dynamic optimisation, evolutionary algorithms, self-adaptation}, month = jul, note = {}, pages = {1619--1627}, publisher = {Association for Computing Machinery}, series = {{GECCO} '23}, title = {Self-adaptation {Can} {Help} {Evolutionary} {Algorithms} {Track} {Dynamic} {Optima}}, url = {https://dl.acm.org/doi/10.1145/3583131.3590494}, urldate = {2024-05-10}, year = {2023}, }
Runtime Analysis with Variable Cost
Per Kristian Lehre, and Andrew M. Sutton

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2023

Abs Bib

The usual approach in runtime analysis is to derive estimates on the number of fitness function evaluations required by a method until a suitable element of the search space is found. One justification for this is that in real applications, fitness evaluation often contributes the most computational effort. A tacit assumption in this approach is that this effort is uniform and static across the search space. However, this assumption often does not hold in practice: some candidates may be far more expensive to evaluate than others. This might occur, for example, when fitness evaluation requires running a simulation or training a machine learning model. Despite the availability of a wide range of benchmark functions coupled with various runtime performance guarantees, the runtime analysis community currently lacks a solid perspective of handling variable fitness cost. Our goal with this paper is to argue for incorporating this perspective into our theoretical toolbox. We introduce two models of handling variable cost: a simple non-adaptive model together with a more general adaptive model. We prove cost bounds in these scenarios and discuss the implications for taking into account costly regions in the search space.
@inproceedings{lehre_runtime_2023, address = {New York, NY, USA}, author = {Lehre, Per Kristian and Sutton, Andrew M.}, booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3583131.3590432}, isbn = {9798400701191}, keywords = {adaptive strategies, runtime analysis, variable cost model}, month = jul, note = {}, pages = {1611--1618}, publisher = {Association for Computing Machinery}, series = {{GECCO} '23}, title = {Runtime {Analysis} with {Variable} {Cost}}, url = {https://dl.acm.org/doi/10.1145/3583131.3590432}, urldate = {2024-05-10}, year = {2023}, }
Analysis of a Pairwise Dominance Coevolutionary Algorithm And DefendIt
Per Kristian Lehre, Mario Alejandro Hevia Fajardo, Jamal Toutouh, Erik Hemberg, and Una-May O’Reilly

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2023

Abs Bib

While competitive coevolutionary algorithms are ideally suited to model adversarial dynamics, their complexity makes it difficult to understand what is happening when they execute. To achieve better clarity, we introduce a game named DefendIt and explore a previously developed pairwise dominance coevolutionary algorithm named PDCoEA. We devise a methodology for consistent algorithm comparison, then use it to empirically study the impact of population size, the impact of relative budget limits between the defender and attacker, and the impact of mutation rates on the dynamics and payoffs. Our methodology provides reliable comparisons and records of run and multi-run dynamics. Our supplementary material also offers enticing and detailed animations of a pair of players’ game moves over the course of a game of millions of moves matched to the same run’s populations’ payoffs.
@inproceedings{lehre_analysis_2023, address = {New York, NY, USA}, author = {Lehre, Per Kristian and Hevia Fajardo, Mario Alejandro and Toutouh, Jamal and Hemberg, Erik and O'Reilly, Una-May}, booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3583131.3590411}, isbn = {9798400701191}, keywords = {co-evolution, cyber security, evolutionary algorithms}, month = jul, note = {}, pages = {1027--1035}, publisher = {Association for Computing Machinery}, series = {{GECCO} '23}, title = {Analysis of a {Pairwise} {Dominance} {Coevolutionary} {Algorithm} {And} {DefendIt}}, url = {https://dl.acm.org/doi/10.1145/3583131.3590411}, urldate = {2023-07-21}, year = {2023}, }
How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems
Mario Alejandro Hevia Fajardo, and Per Kristian Lehre

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2023

Abs Bib

Competitive co-evolutionary algorithms (CoEAs) do not rely solely on an external function to assign fitness values to sampled solutions. Instead, they use the aggregation of outcomes from interactions between competing solutions allowing to rank solutions and make selection decisions. This makes CoEAs a useful tool for optimisation problems that have intrinsically interactive domains. Over the past decades, many ways to aggregate the outcomes of interactions have been considered. At the moment, it is unclear which of these is the best choice. Previous research is fragmented and most of the fitness aggregation methods (fitness measures) proposed have only been studied empirically. We argue that a proper understanding of the dynamics of CoEAs and their fitness measures can only be achieved through rigorous analysis of their behaviour. In this work we make a step towards this goal by using runtime analysis to study two commonly used fitness measures. We show a dichotomy in the behaviour of a (1, Λ) CoEA when optimising a Bilinear problem. The algorithm finds a Nash equilibrium efficiently if the worst interaction is used as a fitness measure but it takes exponential time w.o.p. if the average of all interactions is used instead.
@inproceedings{hevia_fajardo_how_2023, address = {New York, NY, USA}, author = {Hevia Fajardo, Mario Alejandro and Lehre, Per Kristian}, booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3583131.3590506}, isbn = {9798400701191}, keywords = {competitive coevolution, maximin optimisation, runtime analysis}, month = jul, note = {}, pages = {1593--1601}, publisher = {Association for Computing Machinery}, series = {{GECCO} '23}, title = {How {Fitness} {Aggregation} {Methods} {Affect} the {Performance} of {Competitive} {CoEAs} on {Bilinear} {Problems}}, url = {https://dl.acm.org/doi/10.1145/3583131.3590506}, urldate = {2023-07-21}, year = {2023}, }
Is CC-(1+1) EA More Efficient than (1+1) EA on Separable and Inseparable Problems?
Per Kristian Lehre, and Shishen Lin

In 2023 IEEE Congress on Evolutionary Computation (CEC), Jul 2023

Abs Bib

Many Real-world optimisation tasks are increasingly large-scale optimisation (LSO) problems. Cooperative co-evolutionary algorithms (CoEAs), which involve more than two populations and utilise the divide-and-conquer approach, have been introduced to solve LSO problems more efficiently. However, the behaviour of cooperative CoEAs is not fully understood because the interactions between two or more populations make analysis challenging. Runtime analysis has improved the under-standing of traditional EAs. We argue that using runtime analysis of CoEAs could provide helpful insights, e.g., how their expected runtime depends on alaorithmic design decisions. In this paper, we show that the expected optimisation time of the basic cooperative co-evolutionary (1+1) EA (CC-(1+1) EA) on linear functions is }Theta(nłog n). This solves an open conjecture by (Jansen and Wiegand, 2004). Moreover, empirical analysis is conducted on two more complicated problems: NK − LANDSCAPE and k-MAXSAT problems. Our results show that the CC-(1+1) EA perform similarly to the (1+1) EA on these problems. However, adjusting block length allows us to optimise its performance on the NK − LANDSCAPE problem. Our results provide a more precise bound for the expected runtime of CC-(1+1) EA and a more detailed empirical analysis of its behaviour on more complicated inseparable problems.
@inproceedings{lehre_is_2023, author = {Lehre, Per Kristian and Lin, Shishen}, booktitle = {2023 {IEEE} {Congress} on {Evolutionary} {Computation} ({CEC})}, doi = {10.1109/CEC53210.2023.10254149}, keywords = {Benchmark testing, Concentration Inequality, Cooperative Co-Evolutionary Algorithms, Evolutionary computation, Large-scale Optimisation, Partitioning algorithms, Runtime, Runtime Analysis, Sociology, Statistics, Tail}, month = jul, note = {}, pages = {1--9}, title = {Is {CC}-(1+1) {EA} {More} {Efficient} than (1+1) {EA} on {Separable} and {Inseparable} {Problems}?}, url = {https://ieeexplore.ieee.org/document/10254149}, urldate = {2024-05-02}, year = {2023}, }
Theoretical and Empirical Analysis of Parameter Control Mechanisms in the (1 + (λ, λ)) Genetic Algorithm
Mario Alejandro Hevia Fajardo, and Dirk Sudholt

ACM Transactions on Evolutionary Learning and Optimization, Jan 2023

Abs Bib

The self-adjusting (1 + (λ, λ)) GA is the best known genetic algorithm for problems with a good fitness-distance correlation as in OneMax. It uses a parameter control mechanism for the parameter λ that governs the mutation strength and the number of offspring. However, on multimodal problems, the parameter control mechanism tends to increase λ uncontrollably. We study this problem for the standard Jumpk benchmark problem class using runtime analysis. The self-adjusting (1 + (λ, λ)) GA behaves like a (1 + n) EA whenever the maximum value for λ is reached. This is ineffective for problems where large jumps are required. Capping λ at smaller values is beneficial for such problems. Finally, resetting λ to 1 allows the parameter to cycle through the parameter space. We show that resets are effective for all Jumpk problems: the self-adjusting (1 + (λ, λ)) GA performs as well as the (1 + 1) EA with the optimal mutation rate and evolutionary algorithms with heavy-tailed mutation, apart from a small polynomial overhead. Along the way, we present new general methods for translating existing runtime bounds from the (1 + 1) EA to the self-adjusting (1 + (λ, λ)) GA. We also show that the algorithm presents a bimodal parameter landscape with respect to λ on Jumpk. For appropriate n and k, the landscape features a local optimum in a wide basin of attraction and a global optimum in a narrow basin of attraction. To our knowledge this is the first proof of a bimodal parameter landscape for the runtime of an evolutionary algorithm on a multimodal problem.
@article{hevia_fajardo_theoretical_2023, author = {Hevia Fajardo, Mario Alejandro and Sudholt, Dirk}, doi = {10.1145/3564755}, issn = {2688-299X}, journal = {ACM Transactions on Evolutionary Learning and Optimization}, keywords = {Parameter control, evolutionary algorithms, parameter landscape, runtime analysis, theory}, month = jan, note = {}, number = {4}, pages = {13:1--13:39}, title = {Theoretical and {Empirical} {Analysis} of {Parameter} {Control} {Mechanisms} in the (1 + (λ, λ)) {Genetic} {Algorithm}}, url = {https://doi.org/10.1145/3564755}, urldate = {2023-05-17}, volume = {2}, year = {2023}, }

Self-Adaptation Can Improve the Noise-Tolerance of Evolutionary Algorithms

Per Kristian Lehre, and Xiaoyu Qin

In Proceedings of the 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Jan 2023

Bib

@inproceedings{lehre_self-adaptation_2023_343,
  address = {Potsdam, Germany},
  author = {Lehre, Per Kristian and Qin, Xiaoyu},
  booktitle = {Proceedings of the 17th {ACM}/{SIGEVO} {Conference} on {Foundations} of {Genetic} {Algorithms}},
  copyright = {All rights reserved},
  keywords = {Evolutionary algorithms, noisy optimisation, self-adaptation},
  note = {},
  pages = {105--116},
  publisher = {Association for Computing Machinery},
  series = {{FOGA} '23},
  title = {Self-{Adaptation} {Can} {Improve} the {Noise}-{Tolerance} of {Evolutionary} {Algorithms}},
  year = {2023},
}

Self-Adaptation Can Help Evolutionary Algorithms Track Dynamic Optima

Per Kristian Lehre, and Xiaoyu Qin

In Proceedings of the Genetic and Evolutionary Computation Conference, Jan 2023

Bib

@inproceedings{lehre_self-adaptation_2023_358,
  author = {Lehre, Per Kristian and Qin, Xiaoyu},
  booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}},
  copyright = {All rights reserved},
  keywords = {dynamic optimisation, evolutionary algorithms, self-adaptation},
  note = {},
  pages = {1619--1627},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '23},
  title = {Self-{Adaptation} {Can} {Help} {Evolutionary} {Algorithms} {Track} {Dynamic} {Optima}},
  year = {2023},
}

2022

Hard problems are easier for success-based parameter control
Mario Alejandro Hevia Fajardo, and Dirk Sudholt

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2022

Abs Bib Talk PDF

Recent works showed that simple success-based rules for self-adjusting parameters in evolutionary algorithms (EAs) can match or outperform the best fixed parameters on discrete problems. Non-elitism in a (1, λ) EA combined with a self-adjusting of spring population size λ outperforms common EAs on the multimodal Cliff problem. However, it was shown that this only holds if the success rate λ that governs self-adjustment is small enough. Otherwise, even on OneMax, the self-adjusting (1, λ) EA stagnates on an easy slope, where frequent successes drive down the of spring population size. We show that self-adjustment works as intended in the absence of easy slopes. We define everywhere hard functions, for which successes are never easy to find and show that the self-adjusting (1, λ) EA is robust with respect to the choice of success rates λ. We give a general fitness-level upper bound on the number of evaluations and show that the expected number of generations is at most [EQUATION] where d is the number of non-optimal fitness values and [EQUATION] is the smallest probability of finding an improvement from a non-optimal search point. We discuss implications for the everywhere hard function LeadingOnes and a new class OneMaxBlocks of everywhere hard functions with tunable difficulty.
@inproceedings{hevia_fajardo_hard_2022, address = {New York, NY, USA}, author = {Hevia Fajardo, Mario Alejandro and Sudholt, Dirk}, booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3512290.3528781}, isbn = {978-1-4503-9237-2}, keywords = {drift analysis, non-elitism, parameter control, runtime analysis, theory}, month = jul, note = {}, pages = {796--804}, publisher = {Association for Computing Machinery}, series = {{GECCO} '22}, title = {Hard problems are easier for success-based parameter control}, url = {https://doi.org/10.1145/3512290.3528781}, urldate = {2023-05-17}, year = {2022}, }

Fast Non-Elitist Evolutionary Algorithms with Power-Law Ranking Selection

Duc-Cuong Dang, Anton Eremeev, Per Kristian Lehre, and Xiaoyu Qin

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2022

Bib

@inproceedings{dang_fast_2022,
  address = {Boston, Massachusetts},
  author = {Dang, Duc-Cuong and Eremeev, Anton and Lehre, Per Kristian and Qin, Xiaoyu},
  booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}},
  keywords = {local optima, power-law ranking, runtime analysis, selection},
  note = {},
  pages = {1372--1380},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '22},
  title = {Fast {Non}-{Elitist} {Evolutionary} {Algorithms} with {Power}-{Law} {Ranking} {Selection}},
  year = {2022},
}

Self-Adaptation via Multi-Objectivisation: A Theoretical Study

Per Kristian Lehre, and Xiaoyu Qin

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2022

Bib

@inproceedings{lehre_self-adaptation_2022,
  address = {Boston, Massachusetts},
  author = {Lehre, Per Kristian and Qin, Xiaoyu},
  booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}},
  keywords = {evolutionary algorithms, multi-modal functions, self-adaptation},
  note = {},
  pages = {1417--1425},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '22},
  title = {Self-{Adaptation} via {Multi}-{Objectivisation}: {A} {Theoretical} {Study}},
  year = {2022},
}

Runtime Analysis of Competitive Co-Evolutionary Algorithms for Maximin Optimisation of a Bilinear Function

Per Kristian Lehre

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2022

Bib

@inproceedings{lehre_runtime_2022,
  address = {Boston, Massachusetts},
  author = {Lehre, Per Kristian},
  booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}},
  keywords = {co-evolution, runtime analysis},
  note = {},
  pages = {1408--1416},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '22},
  title = {Runtime {Analysis} of {Competitive} {Co}-{Evolutionary} {Algorithms} for {Maximin} {Optimisation} of a {Bilinear} {Function}},
  year = {2022},
}

Self-adaptation via Multi-objectivisation: An Empirical Study

Xiaoyu Qin, and Per Kristian Lehre

In Parallel Problem Solving from Nature – PPSN XVII, Jul 2022

Bib

@inproceedings{qin_self-adaptation_2022,
  author = {Qin, Xiaoyu and Lehre, Per Kristian},
  booktitle = {Parallel {Problem} {Solving} from {Nature} – {PPSN} {XVII}},
  editor = {Rudolph, Günter and Kononova, Anna V. and Aguirre, Hernán and Kerschke, Pascal and Ochoa, Gabriela and Tušar, Tea},
  note = {},
  pages = {308--323},
  publisher = {Springer International Publishing},
  title = {Self-adaptation via {Multi}-objectivisation: {An} {Empirical} {Study}},
  year = {2022},
}

2021

Runtime Analyses of the Population-Based Univariate Estimation of Distribution Algorithms on LeadingOnes
Per Kristian Lehre, and Phan Trung Hai Nguyen

Algorithmica, Oct 2021

Abs Bib

We perform rigorous runtime analyses for the univariate marginal distribution algorithm (UMDA) and the population-based incremental learning (PBIL) Algorithm on LeadingOnes. For the UMDA, the currently known expected runtime on the function is \\{}mathcal {O}}}left( n}lambda }log }lambda +n^2}right)\\under an offspring population size \{}lambda =}Omega (}log n)\\and a parent population size \{}mu }le }lambda /(e(1+}delta ))\\for any constant \{}delta \textgreater0\\(Dang and Lehre, GECCO 2015). There is no lower bound on the expected runtime under the same parameter settings. It also remains unknown whether the algorithm can still optimise the LeadingOnes function within a polynomial runtime when \{}mu }ge }lambda /(e(1+}delta ))\\. In case of the PBIL, an expected runtime of \\{}mathcal {O}}(n^{2+c})\\holds for some constant \\c }in (0,1)\\(Wu, Kolonko and Möhring, IEEE TEVC 2017). Despite being a generalisation of the UMDA, this upper bound is significantly asymptotically looser than the upper bound of \\{}mathcal {O}}}left( n^2}right)\\of the UMDA for \{}lambda =}Omega (}log n)}cap {}mathcal {O}}}left( n/}log n}right)\\. Furthermore, the required population size is very large, i.e., \{}lambda =}Omega (n^{1+c})\\. Our contributions are then threefold: (1) we show that the UMDA with \{}mu =}Omega (}log n)\\and \{}lambda }le }mu e^{1-}varepsilon }/(1+}delta )\\for any constants \{}varepsilon }in (0,1)\\and \\0\textless}delta }le e^{1-}varepsilon }-1\\requires an expected runtime of \\e^{}Omega (}mu )}\\on LeadingOnes, (2) an upper bound of \\{}mathcal {O}}}left( n}lambda }log }lambda +n^2}right)\\is shown for the PBIL, which improves the current bound \\{}mathcal {O}}}left( n^{2+c}}right)\\by a significant factor of \{}Theta (n^{c})\ and (3) we for the first time consider the two algorithms on the LeadingOnes function in a noisy environment and obtain an expected runtime of \\{}mathcal {O}}}left( n^2}right)\\for appropriate parameter settings. Our results emphasise that despite the independence assumption in the probabilistic models, the UMDA and the PBIL with fine-tuned parameter choices can still cope very well with variable interactions.
@article{lehre_runtime_2021, author = {Lehre, Per Kristian and Nguyen, Phan Trung Hai}, doi = {10.1007/s00453-021-00862-3}, issn = {1432-0541}, journal = {Algorithmica}, month = oct, note = {}, number = {10}, pages = {3238--3280}, title = {Runtime {Analyses} of the {Population}-{Based} {Univariate} {Estimation} of {Distribution} {Algorithms} on {LeadingOnes}}, url = {https://doi.org/10.1007/s00453-021-00862-3}, volume = {83}, year = {2021}, }
Self-adjusting offspring population sizes outperform fixed parameters on the cliff function
Mario Alejandro Hevia Fajardo, and Dirk Sudholt

In Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Sep 2021

Abs Bib

In the discrete domain, self-adjusting parameters of evolutionary algorithms (EAs) has emerged as a fruitful research area with many runtime analyses showing that self-adjusting parameters can out-perform the best fixed parameters. Most existing runtime analyses focus on elitist EAs on simple problems, for which moderate performance gains were shown. Here we consider a much more challenging scenario: the multimodal function Cliff, defined as an example where a (1, λ) EA is effective, and for which the best known upper runtime bound for standard EAs is O(n25). We prove that a (1, λ) EA self-adjusting the offspring population size λ using success-based rules optimises Cliff in O(n) expected generations and O(n log n) expected evaluations. Along the way, we prove tight upper and lower bounds on the runtime for fixed λ (up to a logarithmic factor) and identify the runtime for the best fixed λ as nη for η ≈ 3.9767 (up to sub-polynomial factors). Hence, the self-adjusting (1, λ) EA outperforms the best fixed parameter by a factor of at least n2.9767 (up to sub-polynomial factors).
@inproceedings{hevia_fajardo_self-adjusting_2021, address = {New York, NY, USA}, author = {Hevia Fajardo, Mario Alejandro and Sudholt, Dirk}, booktitle = {Proceedings of the 16th {ACM}/{SIGEVO} {Conference} on {Foundations} of {Genetic} {Algorithms}}, doi = {10.1145/3450218.3477306}, isbn = {9781450383523}, keywords = {drift analysis, multimodal optimisation, non-elitism, parameter control, runtime analysis}, month = sep, note = {}, pages = {1--15}, publisher = {Association for Computing Machinery}, series = {{FOGA} '21}, title = {Self-adjusting offspring population sizes outperform fixed parameters on the cliff function}, url = {https://doi.org/10.1145/3450218.3477306}, urldate = {2023-05-17}, year = {2021}, }
Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter
Mario Alejandro Hevia Fajardo, and Dirk Sudholt

In Proceedings of the Genetic and Evolutionary Computation Conference, Jun 2021

Abs Bib Talk PDF

Recent theoretical studies have shown that self-adjusting mechanisms can provably outperform the best static parameters in evolutionary algorithms on discrete problems. However, the majority of these studies concerned elitist algorithms and we do not have a clear answer on whether the same mechanisms can be applied for non-elitist algorithms. We study one of the best-known parameter control mechanisms, the one-fifth success rule, to control the offspring population size λ in the non-elitist (1, λ) EA. It is known that the (1, λ) EA has a sharp threshold with respect to the choice of λ where the runtime on OneMax changes from polynomial to exponential time. Hence, it is not clear whether parameter control mechanisms are able to find and maintain suitable values of λ. We show that the answer crucially depends on the success rate s (i. e. a one-(s + 1)-th success rule). We prove that, if the success rate is appropriately small, the self-adjusting (1, λ) EA optimises OneMax in O(n) expected generations and O(n log n) expected evaluations. A small success rate is crucial: we also show that if the success rate is too large, the algorithm has an exponential runtime on OneMax.
@inproceedings{hevia_fajardo_self-adjusting_2021_485, address = {New York, NY, USA}, author = {Hevia Fajardo, Mario Alejandro and Sudholt, Dirk}, booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3449639.3459338}, isbn = {9781450383509}, keywords = {drift analysis, evolutionary algorithms, non-elitism, parameter control, runtime analysis, theory}, month = jun, note = {}, pages = {1151--1159}, publisher = {Association for Computing Machinery}, series = {{GECCO} '21}, shorttitle = {Self-adjusting population sizes for non-elitist evolutionary algorithms}, title = {Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter}, url = {https://dl.acm.org/doi/10.1145/3449639.3459338}, urldate = {2023-05-17}, year = {2021}, }

Escaping Local Optima with Non-Elitist Evolutionary Algorithms

Duc-Cuong Dang, Anton Eremeev, and Per Kristian Lehre

In Proceedings of the AAAI Conference on Artificial Intelligence, May 2021

Bib

@inproceedings{dang_escaping_2021,
  author = {Dang, Duc-Cuong and Eremeev, Anton and Lehre, Per Kristian},
  booktitle = {Proceedings of the {AAAI} {Conference} on {Artificial} {Intelligence}},
  month = may,
  note = {},
  pages = {12275--12283},
  title = {Escaping {Local} {Optima} with {Non}-{Elitist} {Evolutionary} {Algorithms}},
  volume = {35},
  year = {2021},
}

Non-Elitist Evolutionary Algorithms Excel in Fitness Landscapes with Sparse Deceptive Regions and Dense Valleys

Duc-Cuong Dang, Anton Eremeev, and Per Kristian Lehre

In Proceedings of the Genetic and Evolutionary Computation Conference, May 2021

Bib

@inproceedings{dang_non-elitist_2021,
  address = {Lille, France},
  author = {Dang, Duc-Cuong and Eremeev, Anton and Lehre, Per Kristian},
  booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}},
  keywords = {elitism, fitness landscape analysis, runtime analysis},
  note = {},
  pages = {1133--1141},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '21},
  title = {Non-{Elitist} {Evolutionary} {Algorithms} {Excel} in {Fitness} {Landscapes} with {Sparse} {Deceptive} {Regions} and {Dense} {Valleys}},
  year = {2021},
}

More Precise Runtime Analyses of Non-Elitist EAs in Uncertain Environments

Per Kristian Lehre, and Xiaoyu Qin

In Proceedings of the Genetic and Evolutionary Computation Conference, May 2021

Bib

@inproceedings{lehre_more_2021,
  address = {Lille, France},
  author = {Lehre, Per Kristian and Qin, Xiaoyu},
  booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}},
  keywords = {dynamic optimisation, noisy optimisation, non-elitist evolutionary algorithms, runtime analysis, uncertain environments},
  note = {},
  pages = {1160--1168},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '21},
  title = {More {Precise} {Runtime} {Analyses} of {Non}-{Elitist} {EAs} in {Uncertain} {Environments}},
  year = {2021},
}

Tail bounds on hitting times of randomized search heuristics using variable drift analysis

P. K. Lehre, and C. Witt

Combinatorics, Probability and Computing, May 2021

Bib

@article{lehre_tail_2021,
  author = {Lehre, P. K. and Witt, C.},
  journal = {Combinatorics, Probability and Computing},
  note = {},
  number = {4},
  pages = {550--569},
  title = {Tail bounds on hitting times of randomized search heuristics using variable drift analysis},
  volume = {30},
  year = {2021},
  publisher = {Cambridge University Press}
}

2020

On the choice of the parameter control mechanism in the (1+(λ, λ)) genetic algorithm
Mario Alejandro Hevia Fajardo, and Dirk Sudholt

In Proceedings of the 2020 Genetic and Evolutionary Computation Conference, Jun 2020

Abs Bib

The self-adjusting (1 + (λ, λ)) GA is the best known genetic algorithm for problems with a good fitness-distance correlation as in OneMax. It uses a parameter control mechanism for the parameter λ that governs the mutation strength and the number of offspring. However, on multimodal problems, the parameter control mechanism tends to increase λ uncontrollably. We study this problem and possible solutions to it using rigorous runtime analysis for the standard Jumpk benchmark problem class. The original algorithm behaves like a (1+n) EA whenever the maximum value λ = n is reached. This is ineffective for problems where large jumps are required. Capping λ at smaller values is beneficial for such problems. Finally, resetting λ to 1 allows the parameter to cycle through the parameter space. We show that this strategy is effective for all Jumpk problems: the (1 + (λ, λ)) GA performs as well as the (1 + 1) EA with the optimal mutation rate and fast evolutionary algorithms, apart from a small polynomial overhead. Along the way, we present new general methods for bounding the runtime of the (1 + (λ, λ)) GA that allows to translate existing runtime bounds from the (1 + 1) EA to the self-adjusting (1 + (λ, λ)) GA. Our methods are easy to use and give upper bounds for novel classes of functions.
@inproceedings{hevia_fajardo_choice_2020, address = {New York, NY, USA}, author = {Hevia Fajardo, Mario Alejandro and Sudholt, Dirk}, booktitle = {Proceedings of the 2020 {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3377930.3390200}, isbn = {9781450371285}, keywords = {parameter control, runtime analysis, theory}, month = jun, note = {}, pages = {832--840}, publisher = {Association for Computing Machinery}, series = {{GECCO} '20}, title = {On the choice of the parameter control mechanism in the (1+(λ, λ)) genetic algorithm}, url = {https://doi.org/10.1145/3377930.3390200}, urldate = {2023-05-17}, year = {2020}, }

Parallel Black-Box Complexity With Tail Bounds

Per Kristian Lehre, and Dirk Sudholt

IEEE Transactions on Evolutionary Computation, Jun 2020

Bib

@article{lehre_parallel_2020,
  author = {Lehre, Per Kristian and Sudholt, Dirk},
  journal = {IEEE Transactions on Evolutionary Computation},
  note = {},
  number = {6},
  pages = {1010--1024},
  title = {Parallel {Black}-{Box} {Complexity} {With} {Tail} {Bounds}},
  volume = {24},
  year = {2020},
}

Self-Adaptation in Nonelitist Evolutionary Algorithms on Discrete Problems With Unknown Structure

Brendan Case, and Per Kristian Lehre

IEEE Transactions on Evolutionary Computation, Jun 2020

Bib

@article{case_self-adaptation_2020,
  author = {Case, Brendan and Lehre, Per Kristian},
  journal = {IEEE Transactions on Evolutionary Computation},
  note = {},
  number = {4},
  pages = {650--663},
  title = {Self-{Adaptation} in {Nonelitist} {Evolutionary} {Algorithms} on {Discrete} {Problems} {With} {Unknown} {Structure}},
  volume = {24},
  year = {2020},
}

2019

An empirical evaluation of success-based parameter control mechanisms for evolutionary algorithms
Mario Alejandro Hevia Fajardo

In Proceedings of the Genetic and Evolutionary Computation Conference, Jul 2019

Abs Bib

Success-based parameter control mechanisms for Evolutionary Algorithms (EA) change the parameters every generation based on the success of the previous generation and the current parameter value. In the last years there have been proposed several mechanisms of success-based parameter control in the literature. The purpose of this paper is to evaluate and compare their sequential optimisation time and parallelisation on different types of problems. The geometric mean of the sequential and parallel optimisation times is used as a new metric to evaluate the parallelisation of the EAs capturing the trade off between both optimisation times. We perform an empirical study comprising of 9 different algorithms on four benchmark functions. From the 9 algorithms eight algorithms were taken from the literature and one is a modification proposed here. We show that the modified algorithms has a 20% faster sequential optimisation time than the fastest known GA on OneMax. Additionally we show the benefits of success-based parameter control mechanisms for NP-hard problems and using the proposed metric we also show that success-based offspring population size mechanisms are outperformed by static choices in parallel EAs.
@inproceedings{hevia_fajardo_empirical_2019, address = {New York, NY, USA}, author = {Hevia Fajardo, Mario Alejandro}, booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}}, doi = {10.1145/3321707.3321858}, isbn = {9781450361118}, keywords = {empirical study, genetic algorithms, parameter control, parameter selection, success-based}, month = jul, note = {}, pages = {787--795}, publisher = {Association for Computing Machinery}, series = {{GECCO} '19}, title = {An empirical evaluation of success-based parameter control mechanisms for evolutionary algorithms}, url = {https://doi.org/10.1145/3321707.3321858}, urldate = {2023-05-17}, year = {2019}, }
Level-Based Analysis of the Univariate Marginal Distribution Algorithm
Duc-Cuong Dang, Per Kristian Lehre, and Phan Trung Hai Nguyen

Algorithmica, Feb 2019

Abs Bib

Estimation of Distribution Algorithms (EDAs) are stochastic heuristics that search for optimal solutions by learning and sampling from probabilistic models. Despite their popularity in real-world applications, there is little rigorous understanding of their performance. Even for the Univariate Marginal Distribution Algorithm (UMDA)—a simple population-based EDA assuming independence between decision variables—the optimisation time on the linear problem OneMax was until recently undetermined. The incomplete theoretical understanding of EDAs is mainly due to the lack of appropriate analytical tools. We show that the recently developed level-based theorem for non-elitist populations combined with anti-concentration results yield upper bounds on the expected optimisation time of the UMDA. This approach results in the bound \{}mathcal {O}}left( n}lambda }log }lambda +n^2}right) \\on the LeadingOnes and BinVal problems for population sizes \{}lambda \textgreater}mu =}varOmega (}log n)\ where \{}mu \\and \{}lambda \\are parameters of the algorithm. We also prove that the UMDA with population sizes \{}mu }in }mathcal {O}}left( }sqrt{n}}right) }cap }varOmega (}log n)\\optimises OneMax in expected time \{}mathcal {O}}left( }lambda n}right) \ and for larger population sizes \{}mu =}varOmega (}sqrt{n}}log n)\ in expected time \{}mathcal {O}}left( }lambda }sqrt{n}}right) \\. The facility and generality of our arguments suggest that this is a promising approach to derive bounds on the expected optimisation time of EDAs.
@article{dang_level-based_2019, author = {Dang, Duc-Cuong and Lehre, Per Kristian and Nguyen, Phan Trung Hai}, doi = {10.1007/s00453-018-0507-5}, issn = {1432-0541}, journal = {Algorithmica}, month = feb, note = {}, number = {2}, pages = {668--702}, title = {Level-{Based} {Analysis} of the {Univariate} {Marginal} {Distribution} {Algorithm}}, url = {https://doi.org/10.1007/s00453-018-0507-5}, volume = {81}, year = {2019}, }

Runtime Analysis of the Univariate Marginal Distribution Algorithm under Low Selective Pressure and Prior Noise

Per Kristian Lehre, and Phan Trung Hai Nguyen

In Proceedings of the Genetic and Evolutionary Computation Conference, Feb 2019

Bib

@inproceedings{lehre_runtime_2019,
  address = {Prague, Czech Republic},
  author = {Lehre, Per Kristian and Nguyen, Phan Trung Hai},
  booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}},
  keywords = {leadingones, noisy optimisation, running time analysis, theory, univariate marginal distribution algorithm},
  note = {},
  pages = {1497--1505},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '19},
  title = {Runtime {Analysis} of the {Univariate} {Marginal} {Distribution} {Algorithm} under {Low} {Selective} {Pressure} and {Prior} {Noise}},
  year = {2019},
}

On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs Might Help

Per Kristian Lehre, and Phan Trung Hai Nguyen

In Proceedings of the 15th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Feb 2019

Bib

@inproceedings{lehre_limitations_2019,
  address = {Potsdam, Germany},
  author = {Lehre, Per Kristian and Nguyen, Phan Trung Hai},
  booktitle = {Proceedings of the 15th {ACM}/{SIGEVO} {Conference} on {Foundations} of {Genetic} {Algorithms}},
  keywords = {deception, deceptive leading blocks, epistasis, running time analysis, theory, univariate marginal distribution algorithm},
  note = {},
  pages = {154--168},
  publisher = {Association for Computing Machinery},
  series = {{FOGA} '19},
  title = {On the {Limitations} of the {Univariate} {Marginal} {Distribution} {Algorithm} to {Deception} and {Where} {Bivariate} {EDAs} {Might} {Help}},
  year = {2019},
}

2018

Escaping Local Optima Using Crossover With Emergent Diversity

Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton

IEEE Transactions on Evolutionary Computation, Feb 2018

Bib

@article{dang_escaping_2018,
  author = {Dang, Duc-Cuong and Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Lehre, Per Kristian and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew M.},
  journal = {IEEE Transactions on Evolutionary Computation},
  note = {},
  number = {3},
  pages = {484--497},
  title = {Escaping {Local} {Optima} {Using} {Crossover} {With} {Emergent} {Diversity}},
  volume = {22},
  year = {2018},
}

Level-Based Analysis of the Population-Based Incremental Learning Algorithm

Per Kristian Lehre, and Phan Trung Hai Nguyen

In Parallel Problem Solving from Nature – PPSN XV, Feb 2018

Bib

@inproceedings{lehre_level-based_2018,
  author = {Lehre, Per Kristian and Nguyen, Phan Trung Hai},
  booktitle = {Parallel {Problem} {Solving} from {Nature} – {PPSN} {XV}},
  editor = {Auger, Anne and Fonseca, Carlos M. and Lourenço, Nuno and Machado, Penousal and Paquete, Luís and Whitley, Darrell},
  note = {},
  pages = {105--116},
  publisher = {Springer International Publishing},
  title = {Level-{Based} {Analysis} of the {Population}-{Based} {Incremental} {Learning} {Algorithm}},
  year = {2018},
}

Theory Driven Design of Efficient Genetic Algorithms for a Classical Graph Problem
Dogan Corus, and Per Kristian Lehre

In Recent Developments in Metaheuristics, Feb 2018

Abs Bib

This paper presents a principled way of designing a genetic algorithm which can guarantee a rigorously proven upper bound on its optimization time. The shortest path problem is selected to demonstrate how level-based analysis, a general purpose analytical tool, can be used as a design guide. We show that level-based analysis can also ease the experimental burden of finding appropriate parameter settings. Apart from providing an example of theory-driven algorithmic design, we also provide the first runtime analysis of a non-elitist population-based evolutionary algorithm for both the single-source and all-pairs shortest path problems.
@incollection{corus_theory_2018, author = {Corus, Dogan and Lehre, Per Kristian}, booktitle = {Recent {Developments} in {Metaheuristics}}, copyright = {All rights reserved}, isbn = {978-3-319-58252-8 978-3-319-58253-5}, language = {en}, note = {}, pages = {125--140}, publisher = {Springer, Cham}, series = {Operations {Research}/{Computer} {Science} {Interfaces} {Series}}, title = {Theory {Driven} {Design} of {Efficient} {Genetic} {Algorithms} for a {Classical} {Graph} {Problem}}, url = {https://link.springer.com/chapter/10.1007/978-3-319-58253-5_8}, urldate = {2018-03-11}, year = {2018}, doi = {10.1007/978-3-319-58253-5_8} }

2017

Populations Can Be Essential in Tracking Dynamic Optima
Duc-Cuong Dang, Thomas Jansen, and Per Kristian Lehre

Algorithmica, Jun 2017

Abs Bib

Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic optimisation because a large population can contain different solutions that may be useful in the future. However, rigorous theoretical demonstrations for how populations in dynamic optimisation can be essential are sparse and restricted to special cases. This paper provides theoretical explanations of how populations can be essential in evolutionary dynamic optimisation in a general and natural setting. We describe a natural class of dynamic optimisation problems where a sufficiently large population is necessary to keep track of moving optima reliably. We establish a relationship between the population-size and the probability that the algorithm loses track of the optimum.
@article{dang_populations_2017, author = {Dang, Duc-Cuong and Jansen, Thomas and Lehre, Per Kristian}, doi = {10.1007/s00453-016-0187-y}, issn = {1432-0541}, journal = {Algorithmica}, month = jun, note = {}, number = {2}, pages = {660--680}, title = {Populations {Can} {Be} {Essential} in {Tracking} {Dynamic} {Optima}}, url = {https://doi.org/10.1007/s00453-016-0187-y}, volume = {78}, year = {2017}, }

Improved Runtime Bounds for the Univariate Marginal Distribution Algorithm via Anti-Concentration

Per Kristian Lehre, and Phan Trung Hai Nguyen

In Proceedings of the Genetic and Evolutionary Computation Conference, Jun 2017

Bib

@inproceedings{lehre_improved_2017,
  address = {Berlin, Germany},
  author = {Lehre, Per Kristian and Nguyen, Phan Trung Hai},
  booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference}},
  keywords = {estimation of distribution algorithms, level-based analysis, runtime analysis},
  note = {},
  pages = {1383--1390},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '17},
  title = {Improved {Runtime} {Bounds} for the {Univariate} {Marginal} {Distribution} {Algorithm} via {Anti}-{Concentration}},
  year = {2017},
}

Level-Based Analysis of Genetic Algorithms and Other Search Processes

D. Corus, D. C. Dang, A. V. Eremeev, and P. K. Lehre

IEEE Transactions on Evolutionary Computation, Jun 2017

Abs Bib

Understanding how the time complexity of evolutionary algorithms (EAs) depend on their parameter settings and characteristics of fitness landscapes is a fundamental problem in evolutionary computation. Most rigorous results were derived using a handful of key analytic techniques, including drift analysis. However, since few of these techniques apply effortlessly to population-based EAs, most time complexity results concern simple EAs, such as the (1+1) EA. We present the level-based theorem, a new technique tailored to population-based processes. It applies to any non-elitist process where offspring are sampled independently from a distribution depending only on the current population. Given conditions on this distribution, our technique provides upper bounds on the expected time until the process reaches a target state. The technique is demonstrated on pseudo-Boolean functions, the sorting problem, and approximation of optimal solutions in combinatorial optimisation. The conditions of the theorem are often straightforward to verify, even for Genetic Algorithms and Estimation of Distribution Algorithms which were considered highly non-trivial to analyse. The proofs for the example applications are available in the supplementary materials. Finally, we prove that the theorem is nearly optimal for the processes considered: Given the information the theorem requires about the process, a much tighter bound cannot be proved.
@article{corus_level-based_2017, author = {Corus, D. and Dang, D. C. and Eremeev, A. V. and Lehre, P. K.}, copyright = {All rights reserved}, doi = {10.1109/TEVC.2017.2753538}, issn = {1089-778X}, journal = {IEEE Transactions on Evolutionary Computation}, note = {}, number = {99}, pages = {1--1}, title = {Level-{Based} {Analysis} of {Genetic} {Algorithms} and {Other} {Search} {Processes}}, volume = {PP}, year = {2017}, }

2016

Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information
Duc-Cuong Dang, and Per Kristian Lehre

Algorithmica, Jul 2016

Abs Bib

Although widely applied in optimisation, relatively little has been proven rigorously about the role and behaviour of populations in randomised search processes. This paper presents a new method to prove upper bounds on the expected optimisation time of population-based randomised search heuristics that use non-elitist selection mechanisms and unary variation operators. Our results follow from a detailed drift analysis of the population dynamics in these heuristics. This analysis shows that the optimisation time depends on the relationship between the strength of the selective pressure and the degree of variation introduced by the variation operator. Given limited variation, a surprisingly weak selective pressure suffices to optimise many functions in expected polynomial time. We derive upper bounds on the expected optimisation time of non-elitist evolutionary algorithms (EA) using various selection mechanisms, including fitness proportionate selection. We show that EAs using fitness proportionate selection can optimise standard benchmark functions in expected polynomial time given a sufficiently low mutation rate. As a second contribution, we consider an optimisation scenario with partial information, where fitness values of solutions are only partially available. We prove that non-elitist EAs under a set of specific conditions can optimise benchmark functions in expected polynomial time, even when vanishingly little information about the fitness values of individual solutions or populations is available. To our knowledge, this is the first runtime analysis of randomised search heuristics under partial information.
@article{dang_runtime_2016, author = {Dang, Duc-Cuong and Lehre, Per Kristian}, doi = {10.1007/s00453-015-0103-x}, issn = {1432-0541}, journal = {Algorithmica}, month = jul, note = {}, number = {3}, pages = {428--461}, title = {Runtime {Analysis} of {Non}-elitist {Populations}: {From} {Classical} {Optimisation} to {Partial} {Information}}, url = {https://doi.org/10.1007/s00453-015-0103-x}, volume = {75}, year = {2016}, }

Self-adaptation of Mutation Rates in Non-elitist Populations

Duc-Cuong Dang, and Per Kristian Lehre

In Parallel Problem Solving from Nature – PPSN XIV, Jul 2016

Bib

@inproceedings{dang_self-adaptation_2016,
  author = {Dang, Duc-Cuong and Lehre, Per Kristian},
  booktitle = {Parallel {Problem} {Solving} from {Nature} – {PPSN} {XIV}},
  editor = {Handl, Julia and Hart, Emma and Lewis, Peter R. and López-Ibáñez, Manuel and Ochoa, Gabriela and Paechter, Ben},
  note = {},
  pages = {803--813},
  publisher = {Springer International Publishing},
  title = {Self-adaptation of {Mutation} {Rates} in {Non}-elitist {Populations}},
  year = {2016},
}

Limits to Learning in Reinforcement Learning Hyper-heuristics

Fawaz Alanazi, and Per Kristian Lehre

In Evolutionary Computation in Combinatorial Optimization, Jul 2016

Bib

@inproceedings{alanazi_limits_2016,
  author = {Alanazi, Fawaz and Lehre, Per Kristian},
  booktitle = {Evolutionary {Computation} in {Combinatorial} {Optimization}},
  editor = {Chicano, Francisco and Hu, Bin and García-Sánchez, Pablo},
  note = {},
  pages = {170--185},
  publisher = {Springer International Publishing},
  title = {Limits to {Learning} in {Reinforcement} {Learning} {Hyper}-heuristics},
  year = {2016},
}

A Parameterised Complexity Analysis of Bi-level Optimisation with Evolutionary Algorithms

Dogan Corus, Per Kristian Lehre, Frank Neumann, and Mojgan Pourhassan

Evolutionary Computation, Jul 2016

Bib

@article{corus_parameterised_2016,
  author = {Corus, Dogan and Lehre, Per Kristian and Neumann, Frank and Pourhassan, Mojgan},
  journal = {Evolutionary Computation},
  note = {},
  number = {1},
  pages = {183--203},
  title = {A {Parameterised} {Complexity} {Analysis} of {Bi}-level {Optimisation} with {Evolutionary} {Algorithms}},
  volume = {24},
  year = {2016},
}

Escaping Local Optima with Diversity Mechanisms and Crossover

Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton

In Proceedings of the Genetic and Evolutionary Computation Conference 2016, Jul 2016

Bib

@inproceedings{dang_escaping_2016,
  author = {Dang, Duc-Cuong and Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Lehre, Per Kristian and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew M.},
  booktitle = {Proceedings of the {Genetic} and {Evolutionary} {Computation} {Conference} 2016},
  note = {},
  pages = {645--652},
  publisher = {Association for Computing Machinery},
  shorttitle = {{GECCO} '16},
  title = {Escaping {Local} {Optima} with {Diversity} {Mechanisms} and {Crossover}},
  year = {2016},
}

Emergence of Diversity and Its Benefits for Crossover in Genetic Algorithms

Duc-Cuong Dang, Tobias Friedrich, Timo Kötzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton

In Parallel Problem Solving from Nature – PPSN XIV, Jul 2016

Bib

@inproceedings{dang_emergence_2016,
  author = {Dang, Duc-Cuong and Friedrich, Tobias and Kötzing, Timo and Krejca, Martin S. and Lehre, Per Kristian and Oliveto, Pietro S. and Sudholt, Dirk and Sutton, Andrew M.},
  booktitle = {Parallel {Problem} {Solving} from {Nature} – {PPSN} {XIV}},
  editor = {Handl, Julia and Hart, Emma and Lewis, Peter R. and López-Ibáñez, Manuel and Ochoa, Gabriela and Paechter, Ben},
  note = {},
  pages = {890--900},
  publisher = {Springer International Publishing},
  title = {Emergence of {Diversity} and {Its} {Benefits} for {Crossover} in {Genetic} {Algorithms}},
  year = {2016},
}

2015

Toward a unifying framework for evolutionary processes

Tiago Paixão, Golnaz Badkobeh, Nick Barton, Doğan Çörüş, Duc-Cuong Dang, Tobias Friedrich, Per Kristian Lehre, Dirk Sudholt, Andrew M. Sutton, and Barbora Trubenová

Journal of Theoretical Biology, Jul 2015

Bib

@article{paixao_toward_2015,
  author = {Paixão, Tiago and Badkobeh, Golnaz and Barton, Nick and Çörüş, Doğan and Dang, Duc-Cuong and Friedrich, Tobias and Lehre, Per Kristian and Sudholt, Dirk and Sutton, Andrew M. and Trubenová, Barbora},
  journal = {Journal of Theoretical Biology},
  keywords = {Evolution, Evolutionary computation, Mathematical modelling, Population genetics},
  note = {},
  pages = {28--43},
  title = {Toward a unifying framework for evolutionary processes},
  volume = {383},
  year = {2015},
}

Black-Box Complexity of Parallel Search with Distributed Populations

Golnaz Badkobeh, Per Kristian Lehre, and Dirk Sudholt

In Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, Jul 2015

Bib

@inproceedings{badkobeh_black-box_2015,
  address = {Aberystwyth, United Kingdom},
  author = {Badkobeh, Golnaz and Lehre, Per Kristian and Sudholt, Dirk},
  booktitle = {Proceedings of the 2015 {ACM} {Conference} on {Foundations} of {Genetic} {Algorithms} {XIII}},
  keywords = {black-box complexity, cellular evolutionary algorithms, island models, query complexity, runtime analysis, structured populations, theory},
  note = {},
  pages = {3--15},
  publisher = {Association for Computing Machinery},
  series = {{FOGA} '15},
  title = {Black-{Box} {Complexity} of {Parallel} {Search} with {Distributed} {Populations}},
  year = {2015},
}

Efficient Optimisation of Noisy Fitness Functions with Population-Based Evolutionary Algorithms

Duc-Cuong Dang, and Per Kristian Lehre

In Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, Jul 2015

Bib

@inproceedings{dang_efficient_2015,
  address = {Aberystwyth, United Kingdom},
  author = {Dang, Duc-Cuong and Lehre, Per Kristian},
  booktitle = {Proceedings of the 2015 {ACM} {Conference} on {Foundations} of {Genetic} {Algorithms} {XIII}},
  keywords = {noisy optimisation, non-elitism, runtime analysis},
  note = {},
  pages = {62--68},
  publisher = {Association for Computing Machinery},
  series = {{FOGA} '15},
  title = {Efficient {Optimisation} of {Noisy} {Fitness} {Functions} with {Population}-{Based} {Evolutionary} {Algorithms}},
  year = {2015},
}

Simplified Runtime Analysis of Estimation of Distribution Algorithms

Duc-Cuong Dang, and Per Kristian Lehre

In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, Jul 2015

Bib

@inproceedings{dang_simplified_2015,
  address = {Madrid, Spain},
  author = {Dang, Duc-Cuong and Lehre, Per Kristian},
  booktitle = {Proceedings of the 2015 {Annual} {Conference} on {Genetic} and {Evolutionary} {Computation}},
  keywords = {estimation of distribution algorithms, level-based analysis, runtime analysis},
  note = {},
  pages = {513--518},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '15},
  title = {Simplified {Runtime} {Analysis} of {Estimation} of {Distribution} {Algorithms}},
  year = {2015},
}

Populations Can Be Essential in Dynamic Optimisation

Duc-Cuong Dang, Thomas Jansen, and Per Kristian Lehre

In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, Jul 2015

Bib

@inproceedings{dang_populations_2015,
  address = {Madrid, Spain},
  author = {Dang, Duc-Cuong and Jansen, Thomas and Lehre, Per Kristian},
  booktitle = {Proceedings of the 2015 {Annual} {Conference} on {Genetic} and {Evolutionary} {Computation}},
  keywords = {dynamic optimization, population-based algorithm, runtime analysis},
  note = {},
  pages = {1407--1414},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '15},
  title = {Populations {Can} {Be} {Essential} in {Dynamic} {Optimisation}},
  year = {2015},
}

2014

Level-Based Analysis of Genetic Algorithms and Other Search Processes

Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev, and Per Kristian Lehre

In Parallel Problem Solving from Nature – PPSN XIII, Jul 2014

Bib

@inproceedings{corus_level-based_2014,
  author = {Corus, Dogan and Dang, Duc-Cuong and Eremeev, Anton V. and Lehre, Per Kristian},
  booktitle = {Parallel {Problem} {Solving} from {Nature} – {PPSN} {XIII}},
  editor = {Bartz-Beielstein, Thomas and Branke, Jürgen and Filipič, Bogdan and Smith, Jim},
  note = {},
  pages = {912--921},
  publisher = {Springer International Publishing},
  title = {Level-{Based} {Analysis} of {Genetic} {Algorithms} and {Other} {Search} {Processes}},
  year = {2014},
}

Unbiased Black-Box Complexity of Parallel Search

Golnaz Badkobeh, Per Kristian Lehre, and Dirk Sudholt

In Parallel Problem Solving from Nature – PPSN XIII, Jul 2014

Bib

@inproceedings{badkobeh_unbiased_2014,
  author = {Badkobeh, Golnaz and Lehre, Per Kristian and Sudholt, Dirk},
  booktitle = {Parallel {Problem} {Solving} from {Nature} – {PPSN} {XIII}},
  editor = {Bartz-Beielstein, Thomas and Branke, Jürgen and Filipič, Bogdan and Smith, Jim},
  note = {},
  pages = {892--901},
  publisher = {Springer International Publishing},
  title = {Unbiased {Black}-{Box} {Complexity} of {Parallel} {Search}},
  year = {2014},
}

Refined Upper Bounds on the Expected Runtime of Non-Elitist Populations from Fitness-Levels

Duc-Cuong Dang, and Per Kristian Lehre

In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, Jul 2014

Bib

@inproceedings{dang_refined_2014,
  address = {Vancouver, BC, Canada},
  author = {Dang, Duc-Cuong and Lehre, Per Kristian},
  booktitle = {Proceedings of the 2014 {Annual} {Conference} on {Genetic} and {Evolutionary} {Computation}},
  keywords = {drift analysis, fitness-levels, non-elitism, runtime analysis},
  note = {},
  pages = {1367--1374},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '14},
  title = {Refined {Upper} {Bounds} on the {Expected} {Runtime} of {Non}-{Elitist} {Populations} from {Fitness}-{Levels}},
  year = {2014},
}

Evolution under Partial Information

Duc-Cuong Dang, and Per Kristian Lehre

In Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation, Jul 2014

Bib

@inproceedings{dang_evolution_2014,
  address = {Vancouver, BC, Canada},
  author = {Dang, Duc-Cuong and Lehre, Per Kristian},
  booktitle = {Proceedings of the 2014 {Annual} {Conference} on {Genetic} and {Evolutionary} {Computation}},
  keywords = {non-elitism, partial evaluation, runtime analysis},
  note = {},
  pages = {1359--1366},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '14},
  title = {Evolution under {Partial} {Information}},
  year = {2014},
}

Runtime analysis of the (1+1) EA on computing unique input output sequences

Per Kristian Lehre, and Xin Yao

Information Sciences, Jul 2014

Bib

@article{lehre_runtime_2014,
  author = {Lehre, Per Kristian and Yao, Xin},
  journal = {Information Sciences},
  keywords = {Conformance testing, Evolutionary algorithms, Finite state machines, Random search, Runtime analysis, Unique input output sequences},
  note = {},
  pages = {510--531},
  title = {Runtime analysis of the (1+1) {EA} on computing unique input output sequences},
  volume = {259},
  year = {2014},
}

Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift

Per Kristian Lehre, and Carsten Witt

In Algorithms and Computation, Jul 2014

Bib

@inproceedings{lehre_concentrated_2014,
  author = {Lehre, Per Kristian and Witt, Carsten},
  booktitle = {Algorithms and {Computation}},
  editor = {Ahn, Hee-Kap and Shin, Chan-Su},
  note = {},
  pages = {686--697},
  publisher = {Springer International Publishing},
  title = {Concentrated {Hitting} {Times} of {Randomized} {Search} {Heuristics} with {Variable} {Drift}},
  year = {2014},
}

Runtime analysis of selection hyper-heuristics with classical learning mechanisms

Fawaz Alanazi, and Per Kristian Lehre

In 2014 IEEE Congress on Evolutionary Computation (CEC), Jul 2014

Bib

@inproceedings{alanazi_runtime_2014,
  author = {Alanazi, Fawaz and Lehre, Per Kristian},
  booktitle = {2014 {IEEE} {Congress} on {Evolutionary} {Computation} ({CEC})},
  note = {},
  pages = {2515--2523},
  title = {Runtime analysis of selection hyper-heuristics with classical learning mechanisms},
  year = {2014},
}

2013

A Runtime Analysis of Simple Hyper-Heuristics: To Mix or Not to Mix Operators

Per Kristian Lehre, and Ender Özcan

In Proceedings of the Twelfth Workshop on Foundations of Genetic Algorithms XII, Jul 2013

Bib

@inproceedings{lehre_runtime_2013,
  address = {Adelaide, Australia},
  author = {Lehre, Per Kristian and Özcan, Ender},
  booktitle = {Proceedings of the {Twelfth} {Workshop} on {Foundations} of {Genetic} {Algorithms} {XII}},
  keywords = {hyper-heuristics, runtime analysis, stochastic local search},
  note = {},
  pages = {97--104},
  publisher = {Association for Computing Machinery},
  series = {{FOGA} {XII} '13},
  title = {A {Runtime} {Analysis} of {Simple} {Hyper}-{Heuristics}: {To} {Mix} or {Not} to {Mix} {Operators}},
  year = {2013},
}

The Generalized Minimum Spanning Tree Problem: A Parameterized Complexity Analysis of Bi-Level Optimisation

Dogan Corus, Per Kristian Lehre, and Frank Neumann

In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation, Jul 2013

Bib

@inproceedings{corus_generalized_2013,
  address = {Amsterdam, The Netherlands},
  author = {Corus, Dogan and Lehre, Per Kristian and Neumann, Frank},
  booktitle = {Proceedings of the 15th {Annual} {Conference} on {Genetic} and {Evolutionary} {Computation}},
  keywords = {bi-level optimisation, combinatorial optimisation, evolutionary algorithms, sage-d12-PerKristian, sage-d12-translate-possible, sage-ec},
  note = {},
  pages = {519--526},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '13},
  title = {The {Generalized} {Minimum} {Spanning} {Tree} {Problem}: {A} {Parameterized} {Complexity} {Analysis} of {Bi}-{Level} {Optimisation}},
  year = {2013},
}

Finite First Hitting Time Versus Stochastic Convergence in Particle Swarm Optimisation

Per Kristian Lehre, and Carsten Witt

In Advances in Metaheuristics, Jul 2013

Bib

@incollection{lehre_finite_2013,
  author = {Lehre, Per Kristian and Witt, Carsten},
  booktitle = {Advances in {Metaheuristics}},
  editor = {Di Gaspero, Luca and Schaerf, Andrea and Stützle, Thomas},
  note = {},
  pages = {1--20},
  publisher = {Springer New York},
  title = {Finite {First} {Hitting} {Time} {Versus} {Stochastic} {Convergence} in {Particle} {Swarm} {Optimisation}},
  year = {2013},
}

Theoretical Advances in Evolutionary Dynamic Optimization

Philipp Rohlfshagen, Per Kristian Lehre, and Xin Yao

In Evolutionary Computation for Dynamic Optimization Problems, Jul 2013

Abs Bib

The field of evolutionary dynamic optimization is concerned with the study and application of evolutionary algorithms to dynamic optimization problems: a significant number of new algorithms have been proposed in recent years that are designed specifically to overcome the limitations faced by traditional algorithms in the dynamic domain. Subsequently, a wealth of empirical studies have been published that evaluate the performance of these algorithms on a variety of benchmark problems. However, very few theoretical results have been obtained during this time. This relative lack of theoretical findings makes it difficult to fully assess the strengths and weaknesses of the individual algorithms. In this chapter we provide a review of theoretical advances in evolutionary dynamic optimization. In particular, we argue the importance of theoretical results, highlight the challenges faced by theoreticians and summarise the work that has been done to date. We subsequently identify relevant directions for future research.
@incollection{rohlfshagen_theoretical_2013, author = {Rohlfshagen, Philipp and Lehre, Per Kristian and Yao, Xin}, booktitle = {Evolutionary {Computation} for {Dynamic} {Optimization} {Problems}}, copyright = {©2013 Springer-Verlag Berlin Heidelberg}, editor = {Yang, Shengxiang and Yao, Xin}, isbn = {978-3-642-38415-8 978-3-642-38416-5}, language = {en}, note = {}, number = {490}, pages = {221--240}, publisher = {Springer Berlin Heidelberg}, series = {Studies in {Computational} {Intelligence}}, title = {Theoretical {Advances} in {Evolutionary} {Dynamic} {Optimization}}, urldate = {2015-03-07}, year = {2013}, }

2012

On the Impact of Mutation-Selection Balance on the Runtime of Evolutionary Algorithms

Per Kristian Lehre, and Xin Yao

IEEE Transactions on Evolutionary Computation, Apr 2012

Bib

@article{lehre_impact_2012,
  author = {Lehre, Per Kristian and Yao, Xin},
  copyright = {All rights reserved},
  doi = {10.1109/TEVC.2011.2112665},
  issn = {1089-778X},
  journal = {IEEE Transactions on Evolutionary Computation},
  keywords = {sage-bg, sage-d12-PerKristian, sage-d12-translate-possible, sage-ec, sage-model-non-elitist-ea, sage-model-population-based-ea, sage-perf-runtime},
  month = apr,
  note = {},
  number = {2},
  pages = {225--241},
  title = {On the {Impact} of {Mutation}-{Selection} {Balance} on the {Runtime} of {Evolutionary} {Algorithms}},
  volume = {16},
  year = {2012},
}

Black-Box Search by Unbiased Variation

Per Kristian Lehre, and Carsten Witt

Algorithmica, Apr 2012

Bib

@article{lehre_black-box_2012,
  author = {Lehre, Per Kristian and Witt, Carsten},
  copyright = {All rights reserved},
  issn = {0178-4617},
  journal = {Algorithmica},
  keywords = {sage-bg, sage-d12-PerKristian, sage-d12-translate-possible, sage-ec, sage-method-blackbox},
  note = {},
  number = {4},
  pages = {623--642},
  title = {Black-{Box} {Search} by {Unbiased} {Variation}},
  volume = {64},
  year = {2012},
}

2011

Crossover can be constructive when computing unique input–output sequences
Per Kristian Lehre, and Xin Yao

Soft Computing, Sep 2011

Abs Bib

Unique input–output (UIO) sequences have important applications in conformance testing of finite state machines (FSMs). Previous experimental and theoretical research has shown that evolutionary algorithms (EAs) can compute UIOs efficiently on many FSM instance classes, but fail on others. However, it has been unclear how and to what degree EA parameter settings influence the runtime on the UIO problem. This paper investigates the choice of acceptance criterion in the (1 + 1) EA and the use of crossover in the \\(}mu+1)\\Steady State Genetic Algorithm. It is rigorously proved that changing these parameters can reduce the runtime from exponential to polynomial for some instance classes of the UIO problem.
@article{lehre_crossover_2011, author = {Lehre, Per Kristian and Yao, Xin}, doi = {10.1007/s00500-010-0610-2}, issn = {1433-7479}, journal = {Soft Computing}, month = sep, note = {}, number = {9}, pages = {1675--1687}, title = {Crossover can be constructive when computing unique input–output sequences}, url = {https://doi.org/10.1007/s00500-010-0610-2}, volume = {15}, year = {2011}, }

Faster Black-Box Algorithms through Higher Arity Operators

Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Per Kristian Lehre, Markus Wagner, and Carola Winzen

In Proceedings of the 11th Workshop Proceedings on Foundations of Genetic Algorithms, Sep 2011

Bib

@inproceedings{doerr_faster_2011,
  address = {Schwarzenberg, Austria},
  author = {Doerr, Benjamin and Johannsen, Daniel and Kötzing, Timo and Lehre, Per Kristian and Wagner, Markus and Winzen, Carola},
  booktitle = {Proceedings of the 11th {Workshop} {Proceedings} on {Foundations} of {Genetic} {Algorithms}},
  keywords = {black-box complexity, pseudo-boolean optimization, runtime analysis, theory},
  note = {},
  pages = {163--172},
  publisher = {Association for Computing Machinery},
  series = {{FOGA} '11},
  title = {Faster {Black}-{Box} {Algorithms} through {Higher} {Arity} {Operators}},
  year = {2011},
}

Non-Uniform Mutation Rates for Problems with Unknown Solution Lengths

Stephan Cathabard, Per Kristian Lehre, and Xin Yao

In Proceedings of the 11th Workshop Proceedings on Foundations of Genetic Algorithms, Sep 2011

Bib

@inproceedings{cathabard_non-uniform_2011,
  address = {Schwarzenberg, Austria},
  author = {Cathabard, Stephan and Lehre, Per Kristian and Yao, Xin},
  booktitle = {Proceedings of the 11th {Workshop} {Proceedings} on {Foundations} of {Genetic} {Algorithms}},
  keywords = {fsm testing, mutation operator, runtime analysis, search-based software testing, unique input-output sequences, variable-length solutions},
  note = {},
  pages = {173--180},
  publisher = {Association for Computing Machinery},
  series = {{FOGA} '11},
  title = {Non-{Uniform} {Mutation} {Rates} for {Problems} with {Unknown} {Solution} {Lengths}},
  year = {2011},
}

Fitness-Levels for Non-Elitist Populations

Per Kristian Lehre

In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, Sep 2011

Bib

@inproceedings{lehre_fitness-levels_2011,
  address = {Dublin, Ireland},
  author = {Lehre, Per Kristian},
  booktitle = {Proceedings of the 13th {Annual} {Conference} on {Genetic} and {Evolutionary} {Computation}},
  keywords = {evolutionary algorithms, runtime analysis},
  note = {},
  pages = {2075--2082},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '11},
  title = {Fitness-{Levels} for {Non}-{Elitist} {Populations}},
  year = {2011},
}

2010

Negative Drift in Populations

Per Kristian Lehre

In Parallel Problem Solving from Nature, PPSN XI, Sep 2010

Bib

@inproceedings{lehre_negative_2010,
  author = {Lehre, Per Kristian},
  booktitle = {Parallel {Problem} {Solving} from {Nature}, {PPSN} {XI}},
  editor = {Schaefer, Robert and Cotta, Carlos and Ko{\textbackslash}lodziej, Joanna and Rudolph, Günter},
  note = {},
  pages = {244--253},
  publisher = {Springer Berlin Heidelberg},
  title = {Negative {Drift} in {Populations}},
  year = {2010},
}

Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutation

Stefan Kratsch, Per Kristian Lehre, Frank Neumann, and Pietro Simone Oliveto

In Parallel Problem Solving from Nature, PPSN XI, Sep 2010

Bib

@inproceedings{kratsch_fixed_2010,
  author = {Kratsch, Stefan and Lehre, Per Kristian and Neumann, Frank and Oliveto, Pietro Simone},
  booktitle = {Parallel {Problem} {Solving} from {Nature}, {PPSN} {XI}},
  editor = {Schaefer, Robert and Cotta, Carlos and Ko{\textbackslash}lodziej, Joanna and Rudolph, Günter},
  note = {},
  pages = {204--213},
  publisher = {Springer Berlin Heidelberg},
  title = {Fixed {Parameter} {Evolutionary} {Algorithms} and {Maximum} {Leaf} {Spanning} {Trees}: {A} {Matter} of {Mutation}},
  year = {2010},
}

Black-Box Search by Unbiased Variation

Per Kristian Lehre, and Carsten Witt

In Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, Sep 2010

Bib

@inproceedings{lehre_black-box_2010,
  address = {Portland, Oregon, USA},
  author = {Lehre, Per Kristian and Witt, Carsten},
  booktitle = {Proceedings of the 12th {Annual} {Conference} on {Genetic} and {Evolutionary} {Computation}},
  keywords = {black-box complexity, runtime analysis},
  note = {},
  pages = {1441--1448},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '10},
  title = {Black-{Box} {Search} by {Unbiased} {Variation}},
  year = {2010},
}

Ant Colony Optimization and the Minimum Cut Problem

Timo Kötzing, Per Kristian Lehre, Frank Neumann, and Pietro Simone Oliveto

In Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, Sep 2010

Bib

@inproceedings{kotzing_ant_2010,
  address = {Portland, Oregon, USA},
  author = {Kötzing, Timo and Lehre, Per Kristian and Neumann, Frank and Oliveto, Pietro Simone},
  booktitle = {Proceedings of the 12th {Annual} {Conference} on {Genetic} and {Evolutionary} {Computation}},
  keywords = {ant colony optimization, min-cut},
  note = {},
  pages = {1393--1400},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '10},
  title = {Ant {Colony} {Optimization} and the {Minimum} {Cut} {Problem}},
  year = {2010},
}

On the Effect of Populations in Evolutionary Multi-Objective Optimisation

Oliver Giel, and Per Kristian Lehre

Evolutionary Computation, Sep 2010

Bib

@article{giel_effect_2010,
  author = {Giel, Oliver and Lehre, Per Kristian},
  copyright = {All rights reserved},
  doi = {http://dx.doi.org/10.1162/EVCO_a_00013},
  journal = {Evolutionary Computation},
  note = {},
  number = {3},
  pages = {335--356},
  title = {On the {Effect} of {Populations} in {Evolutionary} {Multi}-{Objective} {Optimisation}},
  volume = {18},
  year = {2010},
}

2009

Runtime analysis of search heuristics on software engineering problems
Per Kristian Lehre, and Xin Yao

Frontiers of Computer Science in China, Mar 2009

Abs Bib

Many software engineering tasks can potentially be automated using search heuristics. However, much work is needed in designing and evaluating search heuristics before this approach can be routinely applied to a software engineering problem. Experimental methodology should be complemented with theoretical analysis to achieve this goal. Recently, there have been significant theoretical advances in the runtime analysis of evolutionary algorithms (EAs) and other search heuristics in other problem domains. We suggest that these methods could be transferred and adapted to gain insight into the behaviour of search heuristics on software engineering problems while automating software engineering.
@article{lehre_runtime_2009, author = {Lehre, Per Kristian and Yao, Xin}, doi = {10.1007/s11704-009-0006-6}, issn = {1673-7466}, journal = {Frontiers of Computer Science in China}, month = mar, note = {}, number = {1}, pages = {64--72}, title = {Runtime analysis of search heuristics on software engineering problems}, url = {https://doi.org/10.1007/s11704-009-0006-6}, volume = {3}, year = {2009}, }

On the Impact of the Mutation-Selection Balance on the Runtime of Evolutionary Algorithms

Per Kristian Lehre, and Xin Yao

In Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithms, Mar 2009

Bib

@inproceedings{lehre_impact_2009,
  address = {Orlando, Florida, USA},
  author = {Lehre, Per Kristian and Yao, Xin},
  booktitle = {Proceedings of the {Tenth} {ACM} {SIGEVO} {Workshop} on {Foundations} of {Genetic} {Algorithms}},
  keywords = {branching processes, evolutionary algorithms, runtime analysis},
  note = {},
  pages = {47--58},
  publisher = {Association for Computing Machinery},
  series = {{FOGA} '09},
  title = {On the {Impact} of the {Mutation}-{Selection} {Balance} on the {Runtime} of {Evolutionary} {Algorithms}},
  year = {2009},
}

Theoretical analysis of rank-based mutation - combining exploration and exploitation

Pietro S. Oliveto, Per Kristian Lehre, and Frank Neumann

In 2009 IEEE Congress on Evolutionary Computation, Mar 2009

Bib

@inproceedings{oliveto_theoretical_2009,
  author = {Oliveto, Pietro S. and Lehre, Per Kristian and Neumann, Frank},
  booktitle = {2009 {IEEE} {Congress} on {Evolutionary} {Computation}},
  note = {},
  pages = {1455--1462},
  title = {Theoretical analysis of rank-based mutation - combining exploration and exploitation},
  year = {2009},
}

When is an estimation of distribution algorithm better than an evolutionary algorithm?

Tianshi Chen, Per Kristian Lehre, Ke Tang, and Xin Yao

In 2009 IEEE Congress on Evolutionary Computation, Mar 2009

Bib

@inproceedings{chen_when_2009,
  author = {Chen, Tianshi and Lehre, Per Kristian and Tang, Ke and Yao, Xin},
  booktitle = {2009 {IEEE} {Congress} on {Evolutionary} {Computation}},
  note = {},
  pages = {1470--1477},
  title = {When is an estimation of distribution algorithm better than an evolutionary algorithm?},
  year = {2009},
}

Dynamic Evolutionary Optimisation: An Analysis of Frequency and Magnitude of Change

Philipp Rohlfshagen, Per Kristian Lehre, and Xin Yao

In Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation, Mar 2009

Bib

@inproceedings{rohlfshagen_dynamic_2009,
  address = {Montreal, Québec, Canada},
  author = {Rohlfshagen, Philipp and Lehre, Per Kristian and Yao, Xin},
  booktitle = {Proceedings of the 11th {Annual} {Conference} on {Genetic} and {Evolutionary} {Computation}},
  keywords = {dynamic evolutionary computation, evolutionary algorithms, runtime analysis},
  note = {},
  pages = {1713--1720},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '09},
  title = {Dynamic {Evolutionary} {Optimisation}: {An} {Analysis} of {Frequency} and {Magnitude} of {Change}},
  year = {2009},
}

2008

Theoretical Runtime Analyses of Search Algorithms on the Test Data Generation for the Triangle Classification Problem

Andrea Arcuri, Per Kristian Lehre, and Xin Yao

In 2008 IEEE International Conference on Software Testing Verification and Validation Workshop, Mar 2008

Bib

@inproceedings{arcuri_theoretical_2008,
  author = {Arcuri, Andrea and Lehre, Per Kristian and Yao, Xin},
  booktitle = {2008 {IEEE} {International} {Conference} on {Software} {Testing} {Verification} and {Validation} {Workshop}},
  note = {},
  pages = {161--169},
  title = {Theoretical {Runtime} {Analyses} of {Search} {Algorithms} on the {Test} {Data} {Generation} for the {Triangle} {Classification} {Problem}},
  year = {2008},
}

Crossover Can Be Constructive When Computing Unique Input Output Sequences

Per Kristian Lehre, and Xin Yao

In Simulated Evolution and Learning, Mar 2008

Bib

@incollection{lehre_crossover_2008,
  author = {Lehre, Per Kristian and Yao, Xin},
  booktitle = {Simulated {Evolution} and {Learning}},
  copyright = {©2008 Springer Berlin Heidelberg},
  isbn = {978-3-540-89693-7 978-3-540-89694-4},
  language = {en},
  note = {},
  number = {5361},
  pages = {595--604},
  publisher = {Springer Berlin Heidelberg},
  series = {Lecture {Notes} in {Computer} {Science}},
  title = {Crossover {Can} {Be} {Constructive} {When} {Computing} {Unique} {Input} {Output} {Sequences}},
  urldate = {2015-02-16},
  year = {2008},
}

2007

Phenotypic complexity and local variations in neutral degree

Per Kristian Lehre, and Pauline C. Haddow

Biosystems, Mar 2007

Bib

@article{lehre_phenotypic_2007,
  author = {Lehre, Per Kristian and Haddow, Pauline C.},
  journal = {Biosystems},
  keywords = {Artificial development, Evolutionary computation, Genotype-phenotype mappings, Lindenmayer-systems, Neutrality, Phenotypic complexity},
  note = {},
  number = {2},
  pages = {233--242},
  title = {Phenotypic complexity and local variations in neutral degree},
  volume = {87},
  year = {2007},
}

The genotypic complexity of evolved fault-tolerant and noise-robust circuits

Morten Hartmann, Pauline C. Haddow, and Per Kristian Lehre

Biosystems, Mar 2007

Bib

@article{hartmann_genotypic_2007,
  author = {Hartmann, Morten and Haddow, Pauline C. and Lehre, Per Kristian},
  journal = {Biosystems},
  keywords = {Complexity, EHW, Evolution, Fault-tolerance, Noise, Robust},
  note = {},
  number = {2},
  pages = {224--232},
  title = {The genotypic complexity of evolved fault-tolerant and noise-robust circuits},
  volume = {87},
  year = {2007},
}

Runtime analysis of (1+1) EA on computing unique input output sequences

Per Kristian Lehre, and Xin Yao

In Proceedings of 2007 IEEE Congress on Evolutionary Computation (CEC 2007), Mar 2007

Bib

@inproceedings{lehre_runtime_2007,
  author = {Lehre, Per Kristian and Yao, Xin},
  booktitle = {Proceedings of 2007 {IEEE} {Congress} on {Evolutionary} {Computation} ({CEC} 2007)},
  copyright = {All rights reserved},
  doi = {10.1109/CEC.2007.4424703},
  note = {},
  pages = {1882--1889},
  publisher = {IEEE Press},
  title = {Runtime analysis of (1+1) {EA} on computing unique input output sequences},
  year = {2007},
}

2006

Aetiology-specific patterns in end-stage heart failure patients identified by functional annotation and classification of microarray data

Vidar Beisvag, Per Kristian Lehre, Herman Midelfart, Halfdan Aass, Odd Geiran, Arne Kristian Sandvik, Astrid Lægreid, Jan Komorowski, and Øyvind Ellingsen

European Journal of Heart Failure, Mar 2006

Bib

@article{beisvag_aetiology-specific_2006,
  author = {Beisvag, Vidar and Lehre, Per Kristian and Midelfart, Herman and Aass, Halfdan and Geiran, Odd and Sandvik, Arne Kristian and Lægreid, Astrid and Komorowski, Jan and Ellingsen, Øyvind},
  journal = {European Journal of Heart Failure},
  keywords = {cardiomyopathy, classification, coronary artery disease, functional annotation, gene expression},
  note = {},
  number = {4},
  pages = {381--389},
  title = {Aetiology-specific patterns in end-stage heart failure patients identified by functional annotation and classification of microarray data},
  volume = {8},
  year = {2006},
}

Accessibility and Runtime Between Convex Neutral Networks

Per Kristian Lehre, and Pauline C. Haddow

In Simulated Evolution and Learning, Mar 2006

Bib

@inproceedings{lehre_accessibility_2006,
  author = {Lehre, Per Kristian and Haddow, Pauline C.},
  booktitle = {Simulated {Evolution} and {Learning}},
  editor = {Wang, Tzai-Der and Li, Xiaodong and Chen, Shu-Heng and Wang, Xufa and Abbass, Hussein and Iba, Hitoshi and Chen, Guo-Liang and Yao, Xin},
  note = {},
  pages = {734--741},
  publisher = {Springer Berlin Heidelberg},
  title = {Accessibility and {Runtime} {Between} {Convex} {Neutral} {Networks}},
  year = {2006},
}

On the Effect of Populations in Evolutionary Multi-Objective Optimization

Oliver Giel, and Per Kristian Lehre

In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, Mar 2006

Bib

@inproceedings{giel_effect_2006,
  address = {Seattle, Washington, USA},
  author = {Giel, Oliver and Lehre, Per Kristian},
  booktitle = {Proceedings of the 8th {Annual} {Conference} on {Genetic} and {Evolutionary} {Computation}},
  keywords = {evolutionary algorithms, multi-objective optimization, runtime analysis},
  note = {},
  pages = {651--658},
  publisher = {Association for Computing Machinery},
  series = {{GECCO} '06},
  title = {On the {Effect} of {Populations} in {Evolutionary} {Multi}-{Objective} {Optimization}},
  year = {2006},
}

Complexity and Geometry in Artificial Development

Per Kristian Lehre

Mar 2006

Bib

@phdthesis{lehre_complexity_2006,
  address = {Trondheim, Norway},
  author = {Lehre, Per Kristian},
  copyright = {All rights reserved},
  note = {},
  school = {Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Computer and Information Science},
  title = {Complexity and {Geometry} in {Artificial} {Development}},
  type = {{PhD}},
  year = {2006},
}

2005

The Genotypic complexity of Evolved Fault-tolerant and Noise-robust Circuits

Morten Hartmann, Per Kristian Lehre, and Pauline C. Haddow

In Sixth International Workshop on Information Processing in Cells and Tissues (IPCAT2005), Sep 2005

Bib

@inproceedings{hartmann_genotypic_2005,
  address = {York, UK},
  author = {Hartmann, Morten and Lehre, Per Kristian and Haddow, Pauline C.},
  booktitle = {Sixth {International} {Workshop} on {Information} {Processing} in {Cells} and {Tissues} ({IPCAT2005})},
  copyright = {All rights reserved},
  month = sep,
  note = {},
  title = {The {Genotypic} complexity of {Evolved} {Fault}-tolerant and {Noise}-robust {Circuits}},
  year = {2005},
}

Evolved digital circuits and genome complexity

M. Hartmann, P.K. Lehre, and P.C. Haddow

In 2005 NASA/DoD Conference on Evolvable Hardware (EH’05), Sep 2005

Bib

@inproceedings{hartmann_evolved_2005,
  author = {Hartmann, M. and Lehre, P.K. and Haddow, P.C.},
  booktitle = {2005 {NASA}/{DoD} {Conference} on {Evolvable} {Hardware} ({EH}'05)},
  note = {},
  pages = {79--86},
  title = {Evolved digital circuits and genome complexity},
  year = {2005},
}

Accessibility between neutral networks in indirect genotype-phenotype mappings

P.K. Lehre, and P.C. Haddow

In 2005 IEEE Congress on Evolutionary Computation, Sep 2005

Bib

@inproceedings{lehre_accessibility_2005,
  author = {Lehre, P.K. and Haddow, P.C.},
  booktitle = {2005 {IEEE} {Congress} on {Evolutionary} {Computation}},
  note = {},
  pages = {419--426 Vol.1},
  title = {Accessibility between neutral networks in indirect genotype-phenotype mappings},
  volume = {1},
  year = {2005},
}

Phenotypic Complexity and Local Variations in Neutral Degree

Per Kristian Lehre, and Pauline C Haddow

In Proceedings of the Sixth International Workshop on Information Processing in Cells and Tissues (IPCAT2005), Sep 2005

Bib

@inproceedings{lehre_phenotypic_2005,
  author = {Lehre, Per Kristian and Haddow, Pauline C},
  booktitle = {Proceedings of the {Sixth} {International} {Workshop} on {Information} {Processing} in {Cells} and {Tissues} ({IPCAT2005})},
  copyright = {All rights reserved},
  note = {},
  title = {Phenotypic {Complexity} and {Local} {Variations} in {Neutral} {Degree}},
  year = {2005},
}

2004

Development and Complexity-Based Fitness Function Modifiers

Per Kristian Lehre, and Morten Hartmann

In Proceedings of Workshop on Learning and Regeneration in Developmental Systems (GECCO 2004), Sep 2004

Bib

@inproceedings{lehre_development_2004,
  author = {Lehre, Per Kristian and Hartmann, Morten},
  booktitle = {Proceedings of {Workshop} on {Learning} and {Regeneration} in {Developmental} {Systems} ({GECCO} 2004)},
  copyright = {All rights reserved},
  note = {},
  title = {Development and {Complexity}-{Based} {Fitness} {Function} {Modifiers}},
  year = {2004},
}

2003

Developmental mappings and phenotypic complexity

P.K. Lehre, and P.C. Haddow

In The 2003 Congress on Evolutionary Computation, 2003. CEC ’03., Sep 2003

Bib

@inproceedings{lehre_developmental_2003,
  author = {Lehre, P.K. and Haddow, P.C.},
  booktitle = {The 2003 {Congress} on {Evolutionary} {Computation}, 2003. {CEC} '03.},
  note = {},
  pages = {62--68 Vol.1},
  title = {Developmental mappings and phenotypic complexity},
  volume = {1},
  year = {2003},
}