Deterministic game-solving algorithms are conventionally analyzed in the light of their average-case complexity against a distribution of random game-trees, where leaf values are independently sampled from a fixed distribution. This simplified model enables uncluttered mathematical analysis, revealing two key properties: root value distributions asymptotically collapse to a single fixed value for finite-valued trees, and all reasonable algorithms achieve global optimality. However, these findings are artifacts of the model’s design: its long criticized independence assumption strips games of structural complexity, producing trivial instances where no algorithm faces meaningful challenges. To address this limitation, we introduce a class of synthetic games generated by a probabilistic model that incrementally constructs game-trees using a fixed level-wise conditional distribution. By enforcing ancestor dependencies, a critical structural feature of real-world games, our framework generates problems with adjustable difficulty while retaining some form of analytical tractability. For several algorithms, including AlphaBeta and Scout, we derive recursive formulas characterizing their average-case complexities under this model. These allow us to rigorously compare algorithms on deep game-trees, where Monte-Carlo simulations are no longer feasible. While asymptotically, all algorithms seem to converge to identical branching factor (a result analogous to that of independence-based models), deep finite trees reveal stark differences: AlphaBeta incurs a significantly larger constant multiplicative factor compared to algorithms like Scout, leading to a substantial practical slowdown. Our framework sheds new light on classical game-solving algorithms, offering rigorous evidence and analytical tools to advance the understanding of these methods under a richer, more challenging, and yet tractable model.

It has been long known from the theoretical work on evolution strategies, that recombination improves convergence towards better solution and improves robustness against selection error in noisy environment. We propose to investigate the effect of recombination in online embodied evolutionary robotics, where evolution is decentralized on a swarm of agents. We hypothesize that these properties can also be observed in these algorithms and thus could improve their performance. We introduce the (μ/μ, 1)-On-line EEA which use a recombination operator inspired from evolution strategies and apply it to learn three different collective robotics tasks, locomotion, item collection and item foraging. Different recombination operators are investigated and compared against a purely mutative version of the algorithm. The experiments show that, when correctly designed, recombination improves significantly the adaptation of the swarm in all scenarios.

We propose a novel innovation marking method for Neuro-Evolution of Augmenting Topologies in Embodied Evolutionary Robotics. This method does not rely on a centralized clock, which makes it well suited for the decentralized nature of EE where no central evolutionary process governs the adaptation of a team of robots exchanging messages locally.

In this paper, we study the impact of selection methods in the context of on-line on-board distributed evolutionary algorithms. We propose a variant of the mEDEA algorithm in which we add a selection operator, and we apply it in a taskdriven scenario. We evaluate four selection methods that induce different intensity of selection pressure in a multi-robot navigation with obstacle avoidance task and a collective foraging task. Experiments show that a small intensity of selection pressure is sufficient to rapidly obtain good performances on the tasks at hand. We introduce different measures to compare the selection methods, and show that the higher the selection pressure, the better the performances obtained, especially for the more challenging food foraging task.

The accuracy of recommendations of collaborative filtering based recommender systems mainly depends on which users (the neighbors) are exploited to estimate a user's ratings. We propose a new approach of neighbor selection, which adopts a global point of view. This approach defines a unique set of possible neighbors, shared by all users, referred to as Global Neighbors (GN). We view the problem of defining GN as a combinatorial optimization problem and propose to use an evolutionary algorithm to tackle this search. Our aim is to find a relatively small GN as the size of the resulting model, as well as the complexity of the computation of recommendations highly depend on the size of GN. We present experiments and results on a standard benchmark data-set from the recommender system community that support our choice of the evolutionary approach and show that it leads to a high accuracy of recommendations and a high coverage, while dramatically reducing the size of the model (by 84%). We also show that the evolutionary approach produces results able to generate accurate recommendations to unseen users, while easily allowing the insertion of new users in the system with little overhead.

A Ramsey theory problem, that can be seen as a 2 dimensional extension of the Van der Waerden theorem, was posed by Martin J. Erickson in his book [1]: “find the minimum n such that if the lattice points of [n] × [n] are two-colored, there exist four points of one color lying on the vertices of a square with sides parallel to the axes”. This was solved recently by Bacher and Eliahou in 2009 [2], who showed that n = 15. In this paper we tackle a derived version of this problem, searching for the minimum n that forces the existence of a monochromatic [3] × [3] subgrid of [n] × [n] of the form {i, i + t, i + 2t} × {j, j + t, j + 2t} for any 2-coloring of [n] × [n]. We use meta-heuristics on this open problem to find instances of 2-colorations without monochromatic [3] × [3] subgrid of the above form, setting a lower bound on n. In particular we found such a binary square grid of size 662, implying that n > 662.

We present an ant model that solves a discrete foraging problem. We describe simulations and provide a complete convergence analysis: we show that the ant population computes the solution of some optimal control problem and converges in some well defined sense. We discuss the rate of convergence with respect to the number of ants: we give experimental and theoretical arguments that suggest that this convergence rate can be superlinear with respect to the number of agents. Furthermore, we explain how this model can be extended in order to solve optimal control problems in general and argue that such an approach can be applied to any problem that involves the computation of the fixed point of a contraction mapping. This allows to design a large class of formally well understood ant like algorithms for problem solving.

We consider trajectory planning within the frameworks of optimal control and harmonic control. We present a formal evidence, in the continuous domain and in a standard discretization, that harmonic control is the limit case of some optimal control problem in which we make the noise level tend to infinity. In other words we show that optimal control subsumes harmonic control. We discuss properties of both paradigms and present simulations that illustrate this relationship.