ThRaSH Seminars Series

About ThRaSH

Randomized search heuristics such as stochastic gradient methods, simulated annealing, evolutionary algorithms, stochastic neural networks for optimization, ant colony and swarm optimization, and the cross-entropy method are frequently used across many scientific communities. They have been successfully applied in various domains, both for combinatorial and numerical optimization. Despite their success in practice, proving that such algorithms satisfy certain performance guarantees is still a difficult and widely open problem.

The mission of the theory of randomized search heuristics (ThRaSH) seminar series is to contribute to the theoretical understanding of randomized search heuristics, in particular of their computational complexity. The aim is to stimulate interactions within the research field and between people from different disciplines working on randomized algorithms. The primary focus is on discussing recent ideas and detecting challenging topics for future work, rather than on the presentation of final results.

Steering Committee (Alphabetic order)

Talks in Autumn/Winter 2024

When? On Tuesday at 15:00 CE(S)T. This is UTC 13:00 for 22th October and UTC 14:00 after that.

Where? Here is a permanent zoom link.

Mailing list? Subscribe to the seminar mailing list here. If you want to get all the ThRaSH-related news, subscribe to this list as well.

Organizers: Andre Opris and Per Kristian Lehre.

Schedule

Abstracts of the talks

22 October 2024

First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2) — Shengjie Ren, School of Artificial Intelligence, Nanjing University, China

Evolutionary algorithms (EAs) have emerged as a predominant approach for addressing multi-objective optimization problems. However, the theoretical foundation of multi-objective EAs (MOEAs), particularly the fundamental aspects like running time analysis, remains largely underexplored. Existing theoretical studies mainly focus on basic MOEAs, with little attention given to practical MOEAs. Recently, researchers have begun to examine practical MOEAs, e.g., NSGA-II/III, MOEA/D, and SMS-EMOA. However, the running time analysis of Strength Pareto Evolutionary Algorithm 2 (SPEA2), one of the most popular MOEAs, has not been touched.

In this talk, we will present the first theoretical analysis of the running time for SPEA2 on three commonly studied multi-objective optimization problems: m-OneMinMax, m-LeadingOnesTrailingZeroes, and m-OneJumpZeroJump. We show that SPEA2 achieves expected running times of O(µn min{mlog(n)}, O(µn2), and O(µnkmin{mn,3m/2}) for these problems respectively, where m is the number of objectives, and µ is the population size. The proofs are accomplished through general theorems which are also applicable for analyzing the expected running time of other MOEAs on these problems, and thus can be helpful for future theoretical analysis of MOEAs.

29 October 2024

Runtime Analysis of Coevolutionary Algorithms on a Class of Symmetric Zero-Sum Games — Alistair Benford, School of Computer Science, University of Birmingham, UK

Coevolutionary algorithms (CoEAs) have a natural application to game playing. While this application has been extensively studied empirically, corresponding runtime analyses so far apply to only a few settings, leaving great potential for further theoretical investigation. Many games, whether enjoyed by human players or describing real-world competition, are symmetric (rules apply the same to all players) and zero-sum (one player's gain is another's loss).

With a view to advancing theoretical analysis of CoEAs, 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 UMDA finds the unique Nash equilibrium in time O(n(log(n))2). Together, these results indicate the importance of generating diverse search points for evolving better strategies.

In this talk we present these results, and additionally consider further runtime analysis for the performance of CoEAs on impartial combinatorial games.

5 November 2024

Finding the Hidden Subset in Hidden Subset Problems — Jon Rowe, University of Birmingham, UK

A hidden subset is defined on n bits, embedded in N bits (where N is typically much larger than n). The remaining N-n bits are neutral and do not affect the fitness of a string. There exist evolutionary algorithms which find an optimal string in time that depends only on n and not on N for certain hidden subset problems. However, there seems to be no way for the algorithm to know when it has found the solution, nor can the relevant bits be identified once it has done so. We address this problem by running log(N) copies of the algorithm in parallel and taking a vote for the value in each bit position. Along the way, we prove a couple of lemmas of potentially broad application. The first gives an easy way of obtaining a bound on the time taken for a number of parallel runs of a process to complete. The second states that the probability a (1+1)EA, with any mutation scheme, produces an incorrect bit value, for weakly monotonic functions with a unique optimum, is no greater than 1/2, at each time step.

12 November 2024

Overcoming Binary Adversarial Optimisation with Competitive Coevolution — Shishen Lin, School of Computer Science, University of Birmingham, UK

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 expected polynomial runtime. This paper carries out the first rigorous runtime analysis of the (1,λ)CoEA for binary test-based adversarial optimisation problems. In particular, we introduce a binary test-based benchmark problem called "Diagonal Problem" and initiate the first runtime analysis of this competitive CoEA on this problem. The mathematical analysis shows that the (1,λ)CoEA can efficiently find an ε-approximation to the optimal solution of the "Diagonal Problem", i.e. in expected polynomial time assuming sufficiently low mutation rates and a large offspring population size. On the other hand, the standard (1,λ)EA fails to find an ε-approximation to the optimal solution of the "Diagonal Problem" in polynomial time. This illustrates the potential of coevolution for solving binary adversarial optimisation problems.