This paper reports on the first international competition on AI for the traveling salesman problem (TSP) at the International Joint Conference on Artificial Intelligence 2021 (IJCAI-21). The TSP is one of the classical combinatorial optimization problems, with many variants inspired by real-world applications. This first competition asked the participants to develop algorithms to solve an orienteering problem with stochastic weights and time windows (OPSWTW). It focused on two learning approaches: surrogate-based optimization and deep reinforcement learning. In this paper, we describe the problem, the competition setup, and the winning methods, and give an overview of the results. The winning methods described in this work have advanced the state-of-the-art in using AI for stochastic routing problems. Overall, by organizing this competition we have introduced routing problems as an interesting problem setting for AI researchers. The simulator of the problem has been made open-source and can be used by other researchers as a benchmark for new learning-based methods. The instances and code for the competition are available at https://github.com/paulorocosta/ai-for-tsp-competition.

This article introduces a benchmarking framework that allows rigorous evaluation of parallel model-based optimizers for expensive functions. The framework establishes a relationship between estimated costs of parallel function evaluations (on real-world problems) to known sets of test functions. Such real-world problems are not always readily available (e.g., confidentiality and proprietary software). Therefore, new test problems are created by Gaussian process simulation. The proposed framework is applied in an extensive benchmark study to compare multiple state-of-the-art parallel optimizers with a novel model-based algorithm, which combines ideas of an explorative search for global model quality with parallel local searches to increase function exploitation. The benchmarking framework is used to configure good batch size setups for parallel algorithms systematically based on landscape properties. Furthermore, we introduce a proof of concept for a novel automatic batch size configuration. The predictive quality of the batch size configuration is evaluated on a large set of test functions and the functions generated by Gaussian process simulation. The introduced algorithm outperforms multiple state-of-the-art optimizers, especially on multimodal problems. Additionally, it proves to be particularly robust over various problem landscapes, and performs well with all tested batch sizes. Consequently, this makes it well suited for black-box kinds of problems.

Hospitals and health-care institutions need to plan the resources required for handling the increased load, i.e., beds and ventilators during the COVID-19 pandemic. BaB-Sim.Hospital, an open-source tool for capacity planning based on discrete event simulation, was developed over the last year to support doctors, administrations, health authorities, and crisis teams in Germany. To obtain reliable results, 29 simulation parameters such as durations and probabilities must be specified. While reasonable default values were obtained in detailed discussions with medical professionals, the parameters have to be regularly and automatically optimized based on current data.We investigate how a set of parameters that is tailored to the German health system can be transferred to other regions. Therefore, we use data from the UK. Our study demonstrates the flexibility of the discrete event simulation approach. However, transferring the optimal German parameter settings to the UK situation does not work-parameter ranges must be modified. The adaptation has been shown to reduce simulation error by nearly 70%. The simulation-via-optimization approach is not restricted to health-care institutions, it is applicable to many other real-world problems, e.g., the development of new elevator systems to cover the last mile or simulation of student flow in academic study periods.

Surrogate-based optimization relies on so-called infill criteria (acquisition functions) to decide which point to evaluate next. When Kriging is used as the surrogate model of choice (also called Bayesian optimization), one of the most frequently chosen criteria is expected improvement. We argue that the popularity of expected improvement largely relies on its theoretical properties rather than empirically validated performance. Few results from the literature show evidence, that under certain conditions, expected improvement may perform worse than something as simple as the predicted value of the surrogate model. We benchmark both infill criteria in an extensive empirical study on the 'BBOB' function set. This investigation includes a detailed study of the impact of problem dimensionality on algorithm performance. The results support the hypothesis that exploration loses importance with increasing problem dimensionality. A statistical analysis reveals that the purely exploitative search with the predicted value criterion performs better on most problems of five or higher dimensions. Possible reasons for these results are discussed. In addition, we give an in-depth guide for choosing the infill criteria based on prior knowledge about the problem at hand, its dimensionality, and the available budget.

Optimization in hierarchical search spaces deals with variables that only have an influence on the objective function if other variables fulfill certain conditions. These types of conditions complicate the optimization process. If the objective function is expensive to evaluate, these complications are further compounded. Especially, if surrogate models are learned to replace the objective function, they have to be able to respect the hierarchical dependencies in the data. In this work a new kernel is introduced, that allows Kriging models (Gaussian process regression) to handle hierarchical search spaces. This new kernel is compared to existing kernels based on an artificial benchmark function. Thereby, we face a typical algorithm design problem: The statistical analysis of benchmark results. Instead of just identifying the best algorithm, it is often desirable to compute algorithm rankings that depend on additional experimental parameters. We propose a method for the automated analysis of such algorithm comparisons. Instead of investigating all parameter constellations of our artificial test function at once, we apply a cluster algorithm and analyze rankings of the algorithms within each cluster. This new method is used to analyze the above mentioned benchmark of kernels for hierarchical search spaces.

In the last years, reinforcement learning received a lot of attention. One method to solve reinforcement learning tasks is Neuroevolution, where neural networks are optimized by evolutionary algorithms. A disadvantage of Neuroevolution is that it can require numerous function evaluations, while not fully utilizing the available information from each fitness evaluation. This is especially problematic when fitness evaluations become expensive. To reduce the cost of fitness evaluations, surrogate models can be employed to partially replace the fitness function. The difficulty of surrogate modeling for Neuroevolution is the complex search space and how to compare different networks. To that end, recent studies showed that a kernel based approach, particular with phenotypic distance measures, works well. These kernels compare different networks via their behavior (phenotype) rather than their topology or encoding (genotype). In this work, we discuss the use of surrogate model-based Neuroevolution (SMB-NE) using a phenotypic distance for reinforcement learning. In detail, we investigate a) the potential of SMB-NE with respect to evaluation efficiency and b) how to select adequate input sets for the phenotypic distance measure in a reinforcement learning problem. The results indicate that we are able to considerably increase the evaluation efficiency using dynamic input sets.

Surrogate Model Based Optimization (SMBO) is an established technique for handling computationally expensive optimization problems. One important application is the optimization of Particle Reinforced Metal Matrix Composites (PRMMCs). Multi-phase materials are gaining attention. Their performance is strongly affected by microscale properties. By optimizing the microscale structure, these materials can be tailored to satisfy specific requirements. Current manufacturing techniques have limited control over the distribution of reinforcing particles and are subject to considerable uncertainty. Moreover, the simulation and optimization of PRMMCs requires significant computational effort. We propose an approach that tackles the problem of optimizing the characteristics of PRMMCs subject to uniaxial load, by improving the particles' spatial distribution. The optimization problem is split into a bilevel problem: The upper-level optimization aims to find the particle distribution parameters which maximize the PRMMC limit load. Due to potentially infeasible distributions, the lower-level problem attempts to create a particle placement that reflects the specifications of an upper-level candidate solution.

The availability of several CPU cores on current computers enables parallelization and increases the computational power significantly. Optimization algorithms have to be adapted to exploit these highly parallelized systems and evaluate multiple candidate solutions in each iteration. This issue is especially challenging for expensive optimization problems, where surrogate models are employed to reduce the load of objective function evaluations.

When designing or developing optimization algorithms, test functions are crucial to evaluate performance. Often, test functions are not sufficiently difficult, diverse, flexible or relevant to real-world applications. Previously, test functions with real-world relevance were generated by training a machine learning model based on real-world data. The model estimation is used as a test function. We propose a more principled approach using simulation instead of estimation. Thus, relevant and varied test functions are created which represent the behavior of real-world fitness landscapes. Importantly, estimation can lead to excessively smooth test functions while simulation may avoid this pitfall. Moreover, the simulation can be conditioned by the data, so that the simulation reproduces the training data but features diverse behavior in unobserved regions of the search space. The proposed test function generator is illustrated with an intuitive, one-dimensional example. To demonstrate the utility of this approach it is applied to a protein sequence optimization problem. This application demonstrates the advantages as well as practical limits of simulation-based test functions.

Cyclone separators are filtration devices frequently used in industry, e.g., to filter particles from flue gas. Optimizing the cyclone geometry is a demanding task. Accurate simulations of cyclone separators are based on time consuming computational fluid dynamics simulations. Thus, the need for exploiting cheap information from analytical, approximative models is evident. Here, we employ two multi-objective optimization algorithms on such cheap, approximative models to analyze their optimization performance on this problem. Under various limitations, we tune both algorithms with Sequential Parameter Optimization (SPO) to achieve best possible results in shortest time. The resulting optimal settings are validated with different seeds, as well as with a different approximative model for collection efficiency. Their optimal performance is compared against a model based approach, where multi-objective SPO is directly employed to optimize the Cyclone model, rather than tuning the optimization algorithms. It is shown that SPO finds improved parameter settings of the concerned algorithms and performs excellently when directly used as an optimizer.

Real-world optimization problems may require time consuming and expensive measurements or simulations. Recently, the application of surrogate model-based approaches was extended from continuous to combinatorial spaces. This extension is based on the utilization of suitable distance measures such as Hamming or Swap Distance. In this work, such an extension is implemented for Kriging (Gaussian Process) models. Kriging provides a measure of uncertainty when determining predictions. This can be harnessed to calculate the Expected Improvement (EI) of a candidate solution. In continuous optimization, EI is used in the Efficient Global Optimization (EGO) approach to balance exploitation and exploration for expensive optimization problems. Employing the extended Kriging model, we show for the first time that EGO can successfully be applied to combinatorial optimization problems. We describe necessary adaptations and arising issues as well as experimental results on several test problems. All surrogate models are optimized with a Genetic Algorithm (GA). To yield a comprehensive comparison, EGO and Kriging are compared to an earlier suggested Radial Basis Function Network, a linear modeling approach, as well as model-free optimization with random search and GA. EGO clearly outperforms the competing approaches on most of the tested problem instances.

Biogas plants are reliable sources of energy based on renewable materials including organic waste. There is a high demand from industry to run these plants efficiently, which leads to a highly complex simulation and optimization problem. A comparison of several algorithms from computational intelligence to solve this problem is presented in this study. The sequential parameter optimization was used to determine improved parameter settings for these algorithms in an automated manner. We demonstrate that genetic algorithm and particle swarm optimization based approaches were outperformed by differential evolution and covariance matrix adaptation evolution strategy. Compared to previously presented results, our approach required only one tenth of the number of function evaluations.