After Learning Evolutionary Retrofitting (AfterLearnER) consists in applying evolutionary optimization to refine fully trained machine learning models by optimizing a set of carefully chosen parameters or hyperparameters of the model, with respect to some actual, exact, and hence possibly non-differentiable error signal, performed on a subset of the standard validation set. The efficiency of AfterLearnER is demonstrated by tackling non-differentiable signals such as threshold-based criteria in depth sensing, the word error rate in speech resynthesis, the number of kills per life at Doom, computational accuracy or BLEU in code translation, image quality in 3D generative adversarial networks (GANs), and user feedback in image generation via latent diffusion models (LDM). This retrofitting can be done after training, or dynamically at inference time by taking into account the user feedback. The advantages of AfterLearnER are its versatility, the possibility to use non-differentiable feedback, including human evaluations (i.e., no gradient is needed), the limited overfitting supported by a theoretical study, and its anytime behavior. Last but not least, AfterLearnER requires only a small amount of feedback, i.e., a few dozen to a few hundred scalars, compared to the tens of thousands needed in most related published works.

Tokenization imposes a fixed granularity on the input text, freezing how a language model operates on data and how far in the future it predicts. Byte Pair Encoding (BPE) and similar schemes split text once, build a static vocabulary, and leave the model stuck with that choice. We relax this rigidity by introducing an autoregressive U-Net that learns to embed its own tokens as it trains. The network reads raw bytes, pools them into words, then pairs of words, then up to 4 words, giving it a multi-scale view of the sequence. At deeper stages, the model must predict further into the future -- anticipating the next few words rather than the next byte -- so deeper stages focus on broader semantic patterns while earlier stages handle fine details. When carefully tuning and controlling pretraining compute, shallow hierarchies tie strong BPE baselines, and deeper hierarchies have a promising trend. Because tokenization now lives inside the model, the same system can handle character-level tasks and carry knowledge across low-resource languages.

The growing ubiquity of machine learning (ML) has led it to enter various areas of computer science, including black-box optimization (BBO). Recent research is particularly concerned with Bayesian optimization (BO). BO-based algorithms are popular in the ML community, as they are used for hyperparameter optimization and more generally for algorithm configuration. However, their efficiency decreases as the dimensionality of the problem and the budget of evaluations increase. Meanwhile, derivative-free optimization methods have evolved independently in the optimization community. Therefore, we urge to understand whether cross-fertilization is possible between the two communities, ML and BBO, i.e., whether algorithms that are heavily used in ML also work well in BBO and vice versa. Comparative experiments often involve rather small benchmarks and show visible problems in the experimental setup, such as poor initialization of baselines, overfitting due to problem-specific setting of hyperparameters, and low statistical significance. With this paper, we update and extend a comparative study presented by Hutter et al. in 2013. We compare BBO tools for ML with more classical heuristics, first on the well-known BBOB benchmark suite from the COCO environment and then on Direct Policy Search for OpenAI Gym, a reinforcement learning benchmark. Our results confirm that BO-based optimizers perform well on both benchmarks when budgets are limited, albeit with a higher computational cost, while they are often outperformed by algorithms from other families when the evaluation budget becomes larger. We also show that some algorithms from the BBO community perform surprisingly well on ML tasks.

This paper introduces Interactive Latent Diffusion Model (IELDM), an encapsulation of a popular text-to-image diffusion model into an Evolutionary framework, allowing the users to steer the design of images toward their goals, alleviating the tedious trial-and-error process that such tools frequently require. The users can not only designate their favourite images, allowing the system to build a surrogate model based on their goals and move in the same directions, but also click on some specific parts of the images to either locally refine the image through dedicated mutation, or recombine images by choosing on each one some regions they like. Experiments validate the benefits of IELDM, especially in a situation where Latent Diffusion Model is challenged by complex input prompts.

Interest in applying Artificial Intelligence (AI) techniques to compiler optimizations is increasing rapidly, but compiler research has a high entry barrier. Unlike in other domains, compiler and AI researchers do not have access to the datasets and frameworks that enable fast iteration and development of ideas, and getting started requires a significant engineering investment. What is needed is an easy, reusable experimental infrastructure for real world compiler optimization tasks that can serve as a common benchmark for comparing techniques, and as a platform to accelerate progress in the field.We introduce CompilerGym, a set of environments for real world compiler optimization tasks, and a toolkit for exposing new optimization tasks to compiler researchers. CompilerGym enables anyone to experiment on production compiler optimization problems through an easy-to-use package, regardless of their experience with compilers. We build upon the popular OpenAI Gym interface enabling researchers to interact with compilers using Python and a familiar API.We describe the CompilerGym architecture and implementation, characterize the optimization spaces and computational efficiencies of three included compiler environments, and provide extensive empirical evaluations. Compared to prior works, CompilerGym offers larger datasets and optimization spaces, is 27× more computationally efficient, is fault-tolerant, and capable of detecting reproducibility bugs in the underlying compilers.In making it easy for anyone to experiment with compilers - irrespective of their background - we aim to accelerate progress in the AI and compiler research domains.

Existing studies in black-box optimization suffer from low generalizability, caused by a typically selective choice of problem instances used for training and testing of different optimization algorithms. Among other issues, this practice promotes overfitting and poor-performing user guidelines. We address this shortcoming by introducing in this work a general-purpose algorithm selection wizard that was designed and tested on a previously unseen breadth of black-box optimization problems, ranging from academic benchmarks to real-world applications, from discrete over numerical to mixed-integer problems, from small to very large-scale problems, from noisy over dynamic to static problems, etc. Not only did we use the already very extensive benchmark environment available in Nevergrad, but we also extended it significantly by adding a number of additional benchmark suites, including Pyomo, Photonics, large-scale global optimization (LSGO), and MuJoCo. Our wizard achieves competitive performance on all benchmark suites. It significantly outperforms previous state-of-the-art algorithms on some of the suites, including YABBOB and LSGO. Its excellent performance is obtained without any task-specific parametrization. The algorithm selection wizard, all of its base solvers, as well as the benchmark suites are available for reproducible research in the open-source Nevergrad platform.

Parallel black box optimization consists in estimating the optimum of a function using λ parallel evaluations of f. Averaging the μ best individuals among the λ evaluations is known to provide better estimates of the optimum of a function than just picking up the best. In continuous domains, this averaging is typically just based on (possibly weighted) arithmetic means. Previous theoretical results were based on quadratic objective functions. In this paper, we extend the results to a wide class of functions, containing three times continuously differentiable functions with unique optimum. We prove formal rate of convergences and show they are indeed better than pure random search asymptotically in λ. We validate our theoretical findings with experiments on some standard black box functions.

The task of image generation started receiving some attention from artists and designers, providing inspiration for new creations. However, exploiting the results of deep generative models such as Generative Adversarial Networks can be long and tedious given the lack of existing tools. In this work, we propose a simple strategy to inspire creators with new generations learned from a dataset of their choice, while providing some control over the output. We design a simple optimization method to find the optimal latent parameters corresponding to the closest generation to any input inspirational image. Specifically, we allow the generation given an inspirational image of the user's choosing by performing several optimization steps to recover optimal parameters from the model's latent space. We tested several exploration methods from classical gradient descents to gradient-free optimizers. Many gradient-free optimizers just need comparisons (better/worse than another image), so they can even be used without numerical criterion nor inspirational image, only with human preferences. Thus, by iterating on one's preferences we can make robust facial composite or fashion generation algorithms. Our results on four datasets of faces, fashion images, and textures show that satisfactory images are effectively retrieved in most cases.

Choosing automatically the right algorithm using problem descriptors is a classical component of combinatorial optimization. It is also a good tool for making evolutionary algorithms fast, robust and versatile. We present Shiwa, an algorithm good at both discrete and continuous, noisy and noise-free, sequential and parallel, black-box optimization. Our algorithm is experimentally compared to competitors on YABBOB, a BBOB comparable testbed, and on some variants of it, and then validated on several real world testbeds.

Space-filling designs such as Low Discrepancy Sequence (LDS), Latin Hypercube Sampling (LHS) and Jittered Sampling (JS) were proposed for fully parallel hyperparameter search, and were shown to be more effective than random and grid search. We prove that LHS and JS outperform random search only by a constant factor. Consequently, we introduce a new sampling approach based on the reshaping of the search distribution, and we show both theoretically and numerically that it leads to significant gains over random search. Two methods are proposed for the reshaping: Recentering (when the distribution of the optimum is known), and Cauchy transformation (when the distribution of the optimum is unknown). The proposed methods are first validated on artificial experiments and simple real-world tests on clustering and Salmon mappings. Then we demonstrate that they drive performance improvement in a wide range of expensive artificial intelligence tasks, namely attend/infer/repeat, video next frame segmentation forecasting and progressive generative adversarial networks.

Super-resolution aims at increasing the resolution and level of detail within an image. The current state of the art in general single-image super-resolution is held by NESRGAN+, which injects a Gaussian noise after each residual layer at training time. In this paper, we harness evolutionary methods to improve NESRGAN+ by optimizing the noise injection at inference time. More precisely, we use Diagonal CMA to optimize the injected noise according to a novel criterion combining quality assessment and realism. Our results are validated by the PIRM perceptual score and a human study. Our method outperforms NESRGAN+ on several standard super-resolution datasets. More generally, our approach can be used to optimize any method based on noise injection.

Contextual bandit algorithms are applied in a wide range of domains, from advertising to recommender systems, from clinical trials to education. In many of these domains, malicious agents may have incentives to force a bandit algorithm into a desired behavior For instance, an unscrupulous ad publisher may try to increase their own revenue at the expense of the advertisers; a seller may want to increase the exposure of their products, or thwart a competitor’s advertising campaign. In this paper, we study several attack scenarios and show that a malicious agent can force a linear contextual bandit algorithm to pull any desired arm T − o(T) times over a horizon of T steps, while applying adversarial modifications to either rewards or contexts with a cumulative cost that only grow logarithmically as O(log T). We also investigate the case when a malicious agent is interested in affecting the behavior of the bandit algorithm in a single context (e.g., a specific user). We first provide sufficient conditions for the feasibility of the attack and an efficient algorithm to perform an attack. We empirically validate the proposed approaches on synthetic and real-world datasets.

Resampling methods, based on averaging the fitness of several clones, are the classical solution for dealing with noise. Population control has been proposed as a different tool for faster convergence of evolution strategies when the variance does not vanish around the optimum. However, we show that convergence may not hold even in the case of centered noise and construct a counterexample with variance dissymmetry, i.e. more variance on one side of the optimum than on the other. We propose a fix termed consistent population control and formally derive uniform constraints on deviations between averages and expectations within the proposed algorithm under either subgaussianity or finite variance assumptions on measurement noise. We prove convergence guarantees of consistent population control, verify it experimentally and show the effectiveness of population control in direct policy search, either with our fix or, in overparameterized cases, without our fix.

This paper studies the optimization of strategies in the context of possibly randomized two players zero-sum games with incomplete information. We compare 5 algorithms for tuning the parameters of strategies over a benchmark of 12 games. A first evolutionary approach consists in designing a highly randomized opponent (called naive opponent) and optimizing the parametric strategy against it; a second one is optimizing iteratively the strategy, i.e. constructing a sequence of strategies starting from the naive one. 2 versions of coevolutions, real and approximate, are also tested as well as a seed method. The coevolution methods were performing well, but results were not stable from one game to another. In spite of its simplicity, the seed method, which can be seen as an extremal version of coevolution, works even when nothing else works. Incidentally, these methods brought out some unexpected strategies for some games, such as Batawaf or the game of War, which seem, at first view, purely random games without any structured actions possible for the players or Guess Who, where a dichotomy between the characters seems to be the most reasonable strategy. All source codes of games are written in Matlab/Octave and are freely available for download.

Fuzzy relationships exist between students’ learning performance with various abilities and a test item. However, the challenges in implementing adaptive assessment agents are obtaining sufficient items, efficient and accurate computerized estimation, and a substantial feedback agent. Additionally, the agent must immediately estimate students’ ability item by item, which places a considerable burden on the server, especially for a group test. Hence, the implementation of an adaptive assessment agent is more difficult in practice. This paper proposes an agent with particle swarm optimization (PSO) based on a fuzzy markup language (FML) for students’ learning performance evaluation and educational applications, and the proposed agent is according to the response data from a conventional test and an item response theory (IRT)-based three-parameter logistic model. First, we apply a Gauss–Seidel based parameter estimation mechanism to estimate the items’ parameters according to the response data, and then to compare its results with those of an IRT-based Bayesian parameter estimation mechanism. In addition, we propose a static-IRT test assembly mechanism to assemble a form for the conventional test. The presented FML-based dynamic assessment mechanism infers the probability of making a correct response to the item for a student with various abilities. Moreover, this paper also proposes a novel PSO-based FML (PFML) learning mechanism for optimizing the parameters between items and students. Finally, we adopt aK-fold cross-validation mechanism to evaluate the performance of the proposed agent. Experimental results show that the novel PFML learning mechanism for the parameter estimation and learning optimization performs favorably. We believe the proposed PFML will be a reference for education research and pedagogy and an important colearning mechanism for future human–machine educational applications.

Bridge is an incomplete information game which is complex both for humans and for Computer-Bridge programs. The purpose of this paper is to present our work related to the adaptation to Bridge of a recent methodology used for boosting game Artificial Intelligence (AI) by seeking a random seed, or a probability distribution on random seeds, better than the others on a particular game. The Bridge AI Wbridge5 developed by Yves Costel has been boosted with the best seed found on the outcome of these experiments and has won the World Computer-Bridge Championship in September 2016.

Derivative Free Optimization is known to be an efficient and robust method to tackle the black-box optimization problem. When it comes to noisy functions, classical comparison-based algorithms are slower than gradient-based algorithms. For quadratic functions, Evolutionary Algorithms without large mutations have a simple regret at best O(1/√N) when N is the number of function evaluations, whereas stochastic gradient descent can reach (tightly) a simple regret in O(1/N). It has been conjectured that gradient approximation by finite differences (hence, not a comparison-based method) is necessary for reaching such a O(1/N). We answer this conjecture in the negative, providing a comparison-based algorithm as good as gradient methods, i.e. reaching O(1/N) - under the condition, however, that the noise is Gaussian. Experimental results confirm the O(1/N) simple regret, i.e., squared rate compared to many published results at O(1/√N).

The performance measure of an algorithm is a crucial part of its analysis. The performance can be determined by the study on the convergence rate of the algorithm in question. It is necessary to study some (hopefully convergent) sequence that will measure how "good" is the approximated optimum compared to the real optimum. The concept of Regret is widely used in the bandit literature for assessing the performance of an algorithm. The same concept is also used in the framework of optimization algorithms, sometimes under other names or without a specific name. And the numerical evaluation of convergence rate of noisy algorithms often involves approximations of regrets. We discuss here two types of approximations of Simple Regret used in practice for the evaluation of algorithms for noisy optimization. We use specific algorithms of different nature and the noisy sphere function to show the following results. The approximation of Simple Regret, termed here Approximate Simple Regret, used in some optimization testbeds, fails to estimate the Simple Regret convergence rate. We also discuss a recent new approximation of Simple Regret, that we term Robust Simple Regret, and show its advantages and disadvantages.

This paper is devoted to noisy optimization in case of a noise with standard deviation as large as variations of the fitness values, specifically when the variance does not decrease to zero around the optimum. We focus on comparing methods for choosing the number of resamplings. Experiments are performed on the differential evolution algorithm. By mathematical analysis, we design a new rule for choosing the number of resamplings for noisy optimization, as a function of the dimension, and validate its efficiency compared to existing heuristics.

Monte Carlo simulations are widely accepted as a tool for evaluating positions in games. It can be used inside tree search algorithms, simple Monte Carlo search, Nested Monte Carlo and the famous Monte Carlo Tree Search algorithm which is at the heart of the current revolution in computer games. If one has access to a perfect simulation policy, then there is no need for an estimation of the game value. In any other cases, an evaluation through Monte Carlo simulations is a possible approach. However, games simulations are, in practice, biased. Many papers are devoted to improve Monte Carlo simulation policies by reducing this bias. In this paper, we propose a complementary tool: instead of modifying the simulations, we modify the way they are averaged by adjusting weights. We apply our method to MCTS for Tsumego solving. In particular, we improve Gnugo-MCTS without any online computational overhead.

We study mathematically and experimentally the convergence rate of differential evolution and particle swarm optimization for simple unimodal functions. Due to parallelization concerns, the focus is on lower bounds on the runtime, i.e. upper bounds on the speed-up, as a function of the population size. Two cases are particularly relevant: A population size of the same order of magnitude as the dimension and larger population sizes. We use the branching factor as a tool for proving bounds and get, as upper bounds, a linear speed-up for a population size similar to the dimension, and a logarithmic speed-up for larger population sizes. We then propose parametrizations for differential evolution and particle swarm optimization that reach these bounds.

We consider the problem of optimizing functions corrupted with additive noise. It is known that Evolutionary Algorithms can reach a Simple Regret O(1/√n) within logarithmic factors, when n is the number of function evaluations. Here, Simple Regret at evaluation $n$ is the difference between the evaluation of the function at the current recommendation point of the algorithm and at the real optimum. We show mathematically that this bound is tight, for any family of functions that includes sphere functions, at least for a wide set of Evolution Strategies without large mutations.

Owing to advanced technical progress in information and communication technology, computerized adaptive assessment becomes more and more important for the personalized learning achievement. According to the response data from the conventional test and three-parameter logistic (3PL) model of the item response theory (IRT), this paper combines IRT with fuzzy markup language (FML) for an adaptive assessment application. The novel FML-based IRT estimation mechanism includes a Gauss-Seidel (GS) parameter estimation mechanism, a fuzzy knowledge base and a fuzzy rule base, to estimate the item parameters for each item. Meanwhile, it is able to infer the possibility of correct response to each item for each involved student. Additionally, this paper also proposes a static-IRT test assembly mechanism to assemble a form for the conventional test. After that, this paper chooses 5-fold cross validation to validate the research performance. From the experimental results, it shows that the proposed approach performs better than the traditional Bayesian estimation one.

The game of Go is a board game with a long history that is much more complex than chess. The uncertainties of this game will be higher when the board size gets bigger. For evaluating the human performance on Go games, one human could be advanced to a higher rank based on the number of winning games via a formal human against human competition. However, a human Go player's performance could be influenced by factors such as the on-the-spot environment, as well as physical and mental situations of the day, which causes difficulty and uncertainty in certificating the human's rank. Thanks to a sample of one player's games, evaluating his/her strength by classical models such as the Bradley-Terry model is possible. However, due to inhomogeneous game conditions and limited access to archives of games, such estimates can be imprecise. In addition, classical rankings (1 Dan, 2 Dan, ...) are integers, which lead to a rather imprecise estimate of the opponent's strengths. Therefore, we propose to use a sample of games played against a computer to estimate the human's strength. In order to increase the precision, the strength of the computer is adapted from one move to the next by increasing or decreasing the computational power based on the current situation and the result of games. The human can decide some specific conditions, such as komi and board size. In this paper, we use type-2 fuzzy sets (T2FSs) with parameters optimized by a genetic algorithm for estimating the rank in a stable manner, independently of board size. More precisely, an adaptive Monte Carlo tree search (MCTS) estimates the number of simulations, corresponding to the strength of its opponents. Next, the T2FS-based adaptive linguistic assessment system infers the human performance and presents the results using the linguistic description. The experimental results show that the proposed approach is feasible for application to the adaptive linguistic assessment on a human Go player's performance.

Motivated by applications in energy management, this paper presents the Multi-Armed Risk-Aware Bandit (MaRaB) algorithm. With the goal of limiting the exploration of risky arms, MaRaB takes as arm quality its conditional value at risk. When the user-supplied risk level goes to 0, the arm quality tends toward the essential infimum of the arm distribution density, and MaRaB tends toward the MIN multi-armed bandit algorithm, aimed at the arm with maximal minimal value. As a first contribution, this paper presents a theoretical analysis of the MIN algorithm under mild assumptions, establishing its robustness comparatively to UCB. The analysis is supported by extensive experimental validation of MIN and MaRaB compared to UCB and state-of-art risk-aware MAB algorithms on artificial and real-world problems.

In spite of various recent publications on the subject, there are still gaps between upper and lower bounds in evolutionary optimization for noisy objective function. In this paper we reduce the gap, and get tight bounds within logarithmic factors in the case of small noise and no long-distance influence on the objective function.

Go game is one game with a long history. Two players alternatively play their black or white stone at a vacant intersection of the board. Usually, weaker player holds Black. In the end, the player with bigger territory wins the game. For the learning in Go games, humans could be advanced to higher rank, for example, by winning 4 out of 5 games. However, a Go player's performance could be influenced by some factors, such as the spot environment as well as physical and mental situations of the day, which causes the difficulty and uncertainty in certificating the human's rank. In this paper, a type-2 fuzzy markup language (T2FML)-based system is proposed to infer the human's rank according to simulation number, komi, and board size. Based on the adaptive Upper Confidence Bounds for Trees (UCT)-based Go-ranking mechanism, the number of simulations for each move of the game is collected when the invited Go players are against the computer Go program, MoGoTW. At the same time, the strength of the human is also estimated by using the Bradley-Terry and Particle Swarm Optimization (PSO) models. The experimental results show that the proposed approach is feasible for estimating the strength of a human.

Several comparison-based complexity results have been published recently, including multi-objective optimization. However, these results are, in the multiobjective case, quite pessimistic, due to the huge family of fitness functions considered. Combining assumptions on fitness functions and traditional comparison-based assumptions, we get more realistic bounds emphasizing the importance of reducing the number of conflicting objectives for reducing the runtime of multiobjective optimization. The approach can in particular predict lower bounds on the computation time, depending on the type of requested convergence: pointwise, or to the whole Pareto set. Also, a new (untested yet) algorithm is proposed for approximating the whole Pareto set.

The eight papers in this special issue cover Go, Lines of Action, Hex, single-player general game playing, parallelization in Go, and analyzing game records using Monte Carlo techniques.

This paper presents the recent technical advances in Monte Carlo tree search (MCTS) for the game of Go, shows the many similarities and the rare differences between the current best programs, and reports the results of the Computer Go event organized at the 2009 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE2009), in which four main Go programs played against top level humans. We see that in 9 × 9, computers are very close to the best human level, and can be improved easily for the opening book; whereas in 19 × 19, handicap 7 is not enough for the computers to win against top level professional players, due to some clearly understood (but not solved) weaknesses of the current algorithms. Applications far from the game of Go are also cited. Importantly, the first ever win of a computer against a 9th Dan professional player in 9 × 9 Go occurred in this event.

In order to stimulate the development and research in computer Go, several Taiwanese Go players, including three professional Go players and four amateur Go players, were invited to play against the famous computer Go program, MoGo, in the Taiwan Open 2009. The MoGo program combines the online game values, offline values extracted from databases, and expert rules defined by Go expert that shows an excellent performance in the games. The results reveal that MoGo can reach the level of 3 Dan in Taiwan amateur Go environment. But there are still some drawbacks for MoGo that should be solved, for example, the weaknesses in semeai and how to flexibly practice the human knowledge through the embedded opening books. In this paper, a new game record ontology for computer Go knowledge management is proposed to solve the problems that MoGo is facing. It is hoped that the advances in intelligent agent and ontology model can provide much more knowledge to make a progress in computer Go and achieve as much as computer chess or Chinese chess in the future.

Many fields rely on some stochastic sampling of a given complex space. Low-discrepancy sequences are methods aiming at producing samples with better space-filling properties than uniformly distributed random numbers, hence allowing a more efficient sampling of that space. State-of-the-art methods like nearly orthogonal Latin hypercubes and scrambled Halton sequences are configured by permutations of internal parameters, where permutations are commonly done randomly. This paper proposes the use of evolutionary algorithms to evolve these permutations, in order to optimize a discrepancy measure. Results show that an evolutionary method is able to generate low-discrepancy sequences of significantly better space-filling properties compared to sequences configured with purely random permutations.

Following a number of recent papers investigating the possibility of optimal comparison-based optimization algorithms for a given distribution of probability on fitness functions, we (i) discuss the comparison-based constraints (ii) choose a setting in which theoretical tight bounds are known (iii) develop a careful implementation using billiard algorithms, Upper Confidence trees and (iv) experimentally test the tractability of the approach. The results, on still very simple cases, show that the approach, yet still preliminary, could be tested successfully until dimension 10 and horizon 50 iterations within a few hours on a standard computer, with convergence rate far better than the best algorithms.

International audience

In order to promote computer Go and stimulate further development and research in the field, the event activities, Computational Intelligence Forum and World 9$\,\times\,$9 Computer Go Championship, were held in Taiwan. This study focuses on the invited games played in the tournament Taiwanese Go Players Versus the Computer Program MoGo held at the National University of Tainan (NUTN), Tainan, Taiwan. Several Taiwanese Go players, including one 9-Dan (9D) professional Go player and eight amateur Go players, were invited by NUTN to play against MoGo from August 26 to October 4, 2008. The MoGo program combines all-moves-as-first (AMAF)/rapid action value estimation (RAVE) values, online “upper confidence tree (UCT)-like” values, offline values extracted from databases, and expert rules. Additionally, four properties of MoGo are analyzed including: 1) the weakness in corners, 2) the scaling over time, 3) the behavior in handicap games, and 4) the main strength of MoGo in contact fights. The results reveal that MoGo can reach the level of 3 Dan (3D) with: 1) good skills for fights, 2) weaknesses in corners, in particular, for “semeai” situations, and 3) weaknesses in favorable situations such as handicap games. It is hoped that the advances in AI and computational power will enable considerable progress in the field of computer Go, with the aim of achieving the same levels as computerChessorChinese Chessin the future.

This paper deals with the optimization of noisy fitness functions, where the noise level can be reduced by increasing the computational effort. We theoretically investigate the question of the control of the noise level. We analyse two different schemes for an adaptive control and prove sufficient conditions ensuring the existence of an homogeneous Markov chain, which is the first step to prove linear convergence when dealing with non-noisy fitness functions. We experimentally validate the relevance of the homogeneity criterion. Large-scale experiments conclude to the efficiency in a difficult framework.

This paper investigates extensions of No Free Lunch (NFL) theorems to countably infinite and uncountable infinite domains. The original NFLdue to Wolpert and Macready states that all search heuristics have the same performance when averaged over the uniform distribution over all possible functions. For infinite domains the extension of the concept of distribution over all possible functions involves measurability issues and stochastic process theory. For countably infinite domains, we prove that the natural extension of NFL theorems does not hold, but that a weaker form of NFL does hold, by stating the existence of non-trivial distributions of fitness leading to equal performance forall search heuristics. Our main result is that for continuous domains, NFL does not hold.

In a preliminary part of this paper, we analyze the necessity of randomness in evolutionstrategies. We conclude to the necessity of continuous-randomness, but with a much more limited use of randomness than whatis commonly used in evolution strategies. We then apply these results to CMA-ES, a famous evolution strategy already based on the idea of derandomization, which uses random independent Gaussian mutations. We here replace these random independent Gaussian mutations by a quasi-randomsample. The modification is very easy to do, the modified algorithm is computationally more efficient and its convergence is faster in terms of the number of iterates for a given precision.

Randomized search heuristics (e.g., evolutionary algorithms, simulated annealing etc.) are very appealing to practitioners, they are easy to implement and usually provide good performance. The theoretical analysis of these algorithms usually focuses on convergence rates. This paper presents a mathematical study of randomized search heuristics which use comparison based selection mechanism. The two main results are that comparison-based algorithms are the best algorithms for some robustness criteria and that introducing randomness in the choice of offspring improves the anytime behavior of the algorithm. An original Estimation of Distribution Algorithm combining both results is proposed and successfully experimented.

It has been empirically established that multiobjective evolutionary algorithms do not scale well with the number of conflicting objectives. This paper shows that the convergence rate of all comparison-based multi-objective algorithms, for the Hausdorff distance, is not much better than the convergence rate of the random search under certain conditions. The number of objectives must be very moderate and the framework should hold the following assumptions: the objectives are conflicting and the computational cost is lower bounded by the number of comparisons is a good model. Our conclusions are: (i) the number of conflicting objectives is relevant (ii) the criteria based on comparisons with random-search for multi-objective optimization is also relevant (iii) having more than 3-objectives optimization is very hard. Furthermore, we provide some insight into cross-over operators.

This paper presents a framework for the theoretical analysis of Estimation of Distribution Algorithms (EDA). Using this framework, derived from the VC-theory, we propose non-asymptotic bounds which depend on: 1) the population size, 2) the selection rate, 3) the families of distributions used for the modelling, 4) the dimension, and 5) the number of iterations. To validate these results, optimization algorithms are applied to a context where bounds on resources are crucial, namely Design of Experiments, that is a black-box optimization with very few fitness-values evaluations.

We show negative results about the automatic generation of programs within bounded-time. Combining recursion theory and statistics, we contrast these negative results with positive computability results for iterative approachs like genetic programming, provided that the fitness combines e.g. fastness and size. We then show that simulation-based approachs (approachs evaluating only by simulation the quality of programs) like GP are not too far from the minimal time required for evaluating these combined fitnesses.

A Quasi-Monte-Carlo method based on the computation of a surrogate model of the fitness function is proposed, and its convergence at super-linear rate 3/2 is proved under rather mild assumptions on the fitness function -- but assuming that the starting point lies within a small neighborhood of a global maximum. A memetic algorithm is then constructed, that performs both a random exploration of the search space and the exploitation of the best-so-far points using the previous surrogate local algorithm, coupled through selection. Under the same mild hypotheses, the global convergence of the memetic algorithm, at the same 3/2 rate, is proved.

Code bloat, the excessive increase of code size, is an important issue in Genetic Programming (GP). This paper proposes a theoretical analysis of code bloat in the framework of symbolic regression in GP, from the viewpoint of Statistical Learning Theory, a well grounded mathematical toolbox for Machine Learning. Two kinds of bloat must be distinguished in that context, depending whether the target function lies in the search space or not. Then, important mathematical results are proved using classical results from Statistical Learning. Namely, the Vapnik-Chervonenkis dimension of programs is computed, and further results from Statistical Learning allow to prove that a parsimonious fitness ensures Universal Consistency (the solution minimizing the empirical error does converge to the best possible error when the number of examples goes to infinity). However, it is proved that the standard method consisting in choosing a maximal program size depending on the number of examples might still result in programs of infinitely increasing size with their accuracy; a more complicated modification of the fitness is proposed that theoretically avoids unnecessary bloat while nevertheless preserving the Universal Consistency.

Estimating the normal vector field on the boundary of discrete three-dimensional objects is essential for rendering and image measurement problems. Most of the existing algorithms do not provide an accurate determination of the normal vector field for shapes that present edges. Here, we propose a new and simple computational method in order to obtain accurate results on all types of shapes, whatever their local convexity degree. The presented method is based on the gradient vector field analysis of the object distance map. This vector field is adaptively filtered around each surface voxel using angle and symmetry criteria so that as many relevant contributions as possible are accounted for. This optimizes the smoothing of digitization effects while preserving relevant details of the processed numerical object. Thanks to the precise normal field obtained, a projection method can be proposed to immediately derive the surface area from a raw discrete object. An empirical justification of the validity of such an algorithm in the continuous limit is also provided. Some results on simulated data and snow images from X-ray tomography are presented, compared to the Marching Cubes and Convex Hull results, and discussed.