Search

Surrogate-assisted evolutionary algorithms have the potential to be of high value for real-world optimization problems when fitness evaluations are expensive, limiting the number of evaluations that can be performed. In this article, we consider the domain of pseudo-Boolean functions in a black-box setting. Moreover, instead of using a surrogate model as an approximation of a fitness function, we propose to precisely learn the coefficients of the Walsh decomposition of a fitness function and use the Walsh decomposition as a surrogate. If the coefficients are learned correctly, then the Walsh decomposition values perfectly match with the fitness function, and, thus, the optimal solution to the problem can be found by optimizing the surrogate without any additional evaluations of the original fitness function. It is known that the Walsh coefficients can be efficiently learned for pseudo-Boolean functions with k -bounded epistasis and known problem structure. We propose to learn dependencies between variables first and, therefore, substantially reduce the number of Walsh coefficients to be calculated. After the accurate Walsh decomposition is obtained, the surrogate model is optimized using GOMEA, which is considered to be a state-of-the-art binary optimization algorithm. We compare the proposed approach with standard GOMEA and two other Walsh decomposition-based algorithms. The benchmark functions in the experiments are well-known trap functions, NK-landscapes, MaxCut, and MAX3SAT problems. The experimental results demonstrate that the proposed approach is scalable at the supposed complexity of O (ℓ log ℓ) function evaluations when the number of subfunctions is O (ℓ) and all subfunctions are k -bounded, outperforming all considered algorithms.

The Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (RV-GOMEA) has previously been successfully used to achieve highly scalable optimization of various real-world problems in a gray-box optimization setting. Deformable Image Registration (DIR) is a multi-objective problem, aimed at finding the most likely non-rigid deformation of a given source image so that it matches a given target image. We specifically consider the case where the deformation model allows for finite-element-type modeling of tissue properties. This optimization problem is non-smooth, necessitating techniques like EAs to get good results. Though the objectives of DIR are non-separable, non-neighboring regions of the deformation grid are conditionally independent. We show that GOMEA allows to exploit such knowledge through the large-scale parallel application of variation steps, where each is only accepted when leading to an improvement, on a Graphics Processing Unit (GPU). On various 2-dimensional DIR problems, we find that this way, similar results can be achieved as when sequential processing is performed, while allowing for substantial speed-ups (up to a factor of 111) for the highest-dimensional problems (i.e., the highest deformation-grid resolution). This work opens the door to the extension of this type of DIR to larger (3-dimensional) deformation grids, and its application to other real-world problems.

It is known that to achieve efficient scalability of an Evolutionary Algorithm (EA), dependencies (also known as linkage) must be properly taken into account during variation. In a Gray-Box Optimization (GBO) setting, exploiting prior knowledge regarding these dependencies can greatly benefit optimization. We specifically consider the setting where partial evaluations are possible, meaning that the partial modification of a solution can be efficiently evaluated. Such problems are potentially very difficult, for example, non-separable, multimodal, and multiobjective. The Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) can effectively exploit partial evaluations, leading to a substantial improvement in performance and scalability. GOMEA was recently shown to be extendable to real-valued optimization through a combination with the real-valued estimation of distribution algorithm AMaLGaM. In this article, we definitively introduce the Real-Valued GOMEA (RV-GOMEA), and introduce a new variant, constructed by combining GOMEA with what is arguably the best-known real-valued EA, the Covariance Matrix Adaptation Evolution Strategies (CMA-ES). Both variants of GOMEA are compared to L-BFGS and the Limited Memory CMA-ES (LM-CMA-ES). We show that both variants of RV-GOMEA achieve excellent performance and scalability in a GBO setting, which can be orders of magnitude better than that of EAs unable to efficiently exploit the GBO setting.

Purpose: The purpose of this study is to improve upon a recently introduced bi-objective treatment planning method for prostate high-dose-rate (HDR) brachytherapy (BT), both in terms of resulting plan quality and runtime requirements, to the extent that its execution time is clinically acceptable. Methods: Bi-objective treatment planning is done using a state-of-the-art multiobjective evolutionary algorithm, which produces a large number of potential treatment plans with different trade-offs between coverage of the target volumes and sparing organs at risk. A graphics processing unit (GPU) is used for large-scale parallelization of dose calculations and the calculation of the dose-volume (DV) indices of potential treatment plans. Moreover, the objectives of the previously used bi-objective optimization model are modified to produce better results. Results: We applied the GPU-accelerated bi-objective treatment planning method to a set of 18 patients, resulting in a set containing a few hundred potential treatment plans with different trade-offs for each of these patients. Due to accelerations introduced in this article, results previously achieved after 1 hour are now achieved within 30 seconds of optimization. We found plans satisfying the clinical protocol for 15 of 18 patients, whereas this was the case for only 4 of 18 clinical plans. Higher quality treatment plans are obtained when the accuracy of DV index calculation is increased using more dose calculation points, requiring still no more than 3 minutes of optimization for 100 000 points. Conclusions: Large sets of high-quality treatment plans that trade-off coverage and sparing are now achievable within 30 seconds, due to the GPU-acceleration of a previously introduced bi-objective treatment planning method for prostate HDR brachytherapy. Higher quality plans can be achieved when optimizing for 3 minutes, which we still consider to be clinically acceptable. This allows for more insightful treatment plan selection in a clinical setting.

Mixed-integer optimization, which focuses on problems where discrete and continuous variables exist simultaneously, is a well-known and challenging area for search algorithms. Mixed-integer optimization problems are especially difficult in a black-box setting where no structural problem information is available a-prior. In this paper we bring the strengths of the recently-proposed Genetic Algorithm for Model-Based mixed-Integer opTimization (GAMBIT) to the multi-objective (MO) domain, and determine whether the promising performance of GAMBIT is maintained. We introduce various mechanisms designed specifically for MO optimization resulting in MO-GAMBIT. We compare performance - in terms of the number of evaluations used - and runtime with alternative techniques, particularly linear scalarization and a selection of alternative MO algorithms. To this end, we introduce a set of objective functions which vary in composition in terms of discrete and continuous variables, as well as in the strength of dependencies between variables. Our results show that MO-GAMBIT can substantially outperform the alternative MO algorithms, thereby providing a promising new approach for multi-objective mixed-integer optimization in a black-box setting.

We propose a novel surrogate-assisted Evolutionary Algorithm for solving expensive combinatorial optimization problems. We integrate a surrogate model, which is used for fitness value estimation, into a state-of-the-art P3-like variant of the Gene-Pool Optimal Mixing Algorithm (GOMEA) and adapt the resulting algorithm for solving non-binary combinatorial problems. We test the proposed algorithm on an ensemble learning problem. Ensembling several models is a common Machine Learning technique to achieve better performance. We consider ensembles of several models trained on disjoint subsets of a dataset. Finding the best dataset partitioning is naturally a combinatorial non-binary optimization problem. Fitness function evaluations can be extremely expensive if complex models, such as Deep Neural Networks, are used as learners in an ensemble. Therefore, the number of fitness function evaluations is typically limited, necessitating expensive optimization techniques. In our experiments we use five classification datasets from the OpenML-CC18 benchmark and Support-vector Machines as learners in an ensemble. The proposed algorithm demonstrates better performance than alternative approaches, including Bayesian optimization algorithms. It manages to find better solutions using just several thousand fitness function evaluations for an ensemble learning problem with up to 500 variables.

Purpose. Recently, we introduced a bi-objective optimization approach based on dose-volume indices to automatically create clinically good HDR prostate brachytherapy plans. To calculate dose-volume indices, a reconstruction algorithm is used to determine the 3D organ shape from 2D contours, inevitably containing settings that influence the result. We augment the optimization approach to quickly find plans that are robust to differences in 3D reconstruction. Methods. Studied reconstruction settings were: interpolation between delineated organ contours, overlap between contours, and organ shape at the top and bottom contour. Two options for each setting yields 8 possible 3D organ reconstructions per patient, over which the robust model defines minimax optimization. For the original model, settings were based on our treatment planning system. Both models were tested on data of 26 patients and compared by re-evaluating selected optimized plans both in the original model (1 organ reconstruction, the difference determines the cost), and in the robust model (8 organ reconstructions, the difference determines the benefit). Results. Robust optimization increased the run time from 3 to 6 min. The median cost for robust optimization as observed in the original model was −0.25% in the dose-volume indices with a range of [−0.01%, −1.03%]. The median benefit of robust optimization as observed in the robust model was 0.93% with a range of [0.19%, 4.16%]. For 4 patients, selected plans that appeared good when optimized in the original model, violated the clinical protocol with more than 1% when considering different settings. This was not the case for robustly optimized plans. Conclusions. Plans of high quality, irrespective of 3D organ reconstruction settings, can be obtained using our robust optimization approach. With its limited effect on total runtime, our approach therefore offers a way to account for dosimetry uncertainties that result from choices in organ reconstruction settings that is viable in clinical practice.

The aim of multimodal optimization (MMO) is to obtain all global optima of an optimization problem. In this chapter, we introduce a general framework for two-phase MMO evolutionary algorithms (EAs), in which different high-fitness regions (niches) are located in the first phase via clustering, and each of the located niches is separately optimized with a core search algorithm in the second phase. One such two-phase MMO EA is the Hill-Valley Evolutionary Algorithm (HillVall-EA). In HillVallEA, the remarkably simple hill-valley clustering method is used. The idea behind hill-valley clustering is that two solutions belong to the same niche (valley) when there is no hill in between them, which can be easily tested by performing additional function evaluations. We compare hill-valley clustering to two other recently introduced fitness-informed clustering methods: nearest-better clustering and hierarchical Gaussian mixture learning. We show how these clustering methods, as well as different core search algorithms, influence the resulting optimization performance of the two-phase MMO framework on the commonly used CEC 2013 niching benchmark suite. Our results show that HillVallEA, equipped with the core search algorithm Adapted Maximum-Likelihood Gaussian Model Univariate (AMu) as core search algorithm, outperforms all other MMO EAs, both within the limited benchmark budget, and in the long run. HillVallEA-AMu was the winner of the GECCO niching competition in 2018 and 2019, and is currently, to the best of our knowledge, the best performing algorithm on this benchmark suite.

Purpose: Bi-objective simultaneous optimization of catheter positions and dwell times for high-dose-rate (HDR) prostate brachytherapy, based directly on dose-volume indices, has shown promising results. However, optimization with the state-of-the-art evolutionary algorithm MO-RV-GOMEA so far required several hours of runtime, and resulting catheter positions were not always clinically feasible. The aim of this study is to extend the optimization model and apply GPU parallelization to achieve clinically acceptable computation times. The resulting optimization procedure is compared with a previously introduced method based solely on geometric criteria, the adapted Centroidal Voronoi Tessellations (CVT) algorithm. Methods: Bi-objective simultaneous optimization was performed with a GPU-parallelized version of MO-RV-GOMEA. This optimization of catheter positions and dwell times was retrospectively applied to the data of 26 patients previously treated with HDR prostate brachytherapy for 8–16 catheters (steps of 2). Optimization of catheter positions using CVT was performed in seconds, after which optimization of only the dwell times using MO-RV-GOMEA was performed in 1 min. Results: Simultaneous optimization of catheter positions and dwell times using MO-RV-GOMEA was performed in 5 min. For 16 down to 8 catheters (steps of 2), MO-RV-GOMEA found plans satisfying the planning-aims for 20, 20, 18, 14, and 11 out of the 26 patients, respectively. CVT achieved this for 19, 17, 13, 9, and 2 patients, respectively. The P-value for the difference between MO-RV-GOMEA and CVT was 0.023 for 16 catheters, 0.005 for 14 catheters, and

Feature construction can substantially improve the accuracy of Machine Learning (ML) algorithms. Genetic Programming (GP) has been proven to be effective at this task by evolving non-linear combinations of input features. GP additionally has the potential to improve ML explainability since explicit expressions are evolved. Yet, in most GP works the complexity of evolved features is not explicitly bound or minimized though this is arguably key for explainability. In this article, we assess to what extent GP still performs favorably at feature construction when constructing features that are (1) Of small-enough number, to enable visualization of the behavior of the ML model; (2) Of small-enough size, to enable interpretability of the features themselves; (3) Of sufficient informative power, to retain or even improve the performance of the ML algorithm. We consider a simple feature construction scheme using three different GP algorithms, as well as random search, to evolve features for five ML algorithms, including support vector machines and random forest. Our results on 21 datasets pertaining to classification and regression problems show that constructing only two compact features can be sufficient to rival the use of the entire original feature set. We further find that a modern GP algorithm, GP-GOMEA, performs best overall. These results, combined with examples that we provide of readable constructed features and of 2D visualizations of ML behavior, lead us to positively conclude that GP-based feature construction still works well when explicitly searching for compact features, making it extremely helpful to explain ML models., Comment: We included more experiments: - A high-dimensional dataset is considered - The machine learning algorithm XGBoost is considered We also repeated the experiments using the Naive Bayes classifier, because we discovered that the implementation we relied on had issues (see https://github.com/mlpack/mlpack/issues/2017)

We present an automatic bi-objective parameter-tuning approach for inverse planning methods for high-dose-rate prostate brachytherapy, which aims to overcome the difficult and time-consuming manual parameter tuning that is currently required to obtain patient-specific high-quality treatment plans. We modelled treatment planning as a bi-objective optimization problem, in which dose-volume-based planning criteria related to target coverage are explicitly separated from organ-sparing criteria. When this model is optimized, a large set of high-quality plans with different trade-offs can be obtained. This set can be visualized as an insightful patient-specific trade-off curve. In our parameter-tuning approach, the parameters of inverse planning methods are automatically tuned, aimed to maximize the two objectives of the bi-objective planning model. By generating trade-off curves for different inverse planning methods, their maximally achievable plan quality can be insightfully compared. Automatic parameter tuning furthermore allows to construct standard parameter sets (class solutions) representing different trade-offs in a principled way, which can be directly used in current clinical practice. In this work, we considered the inverse planning methods IPSA and HIPO. Thirty-nine previously treated prostate cancer patients were included. We compared automatic parameter tuning, random parameter sampling, and the maximally achievable plan quality obtained by directly optimizing the bi-objective planning model with the state-of-the-art optimization software GOMEA. We showed that for each patient, a set of plans with a wide range of trade-offs could be obtained using automatic parameter tuning for both IPSA and HIPO. By tuning HIPO, better trade-offs were obtained than by tuning IPSA. For most patients, automatic tuning of HIPO resulted in plans close to the maximally achievable plan quality obtained by optimizing the bi-objective planning model directly. Automatic parameter tuning was shown to improve plan quality significantly compared to random parameter sampling. Finally, from the automatically-tuned plans, three class solutions were successfully constructed representing different trade-offs.

The Multi-objective Gene-pool Optimal Mixing Evolutionary Algorithm (MO-GOMEA) has been shown to be a promising solver for multi-objective combinatorial optimization problems, obtaining an excellent scalability on both standard benchmarks and real-world applications. To attain optimal performance, MO-GOMEA requires its two parameters, namely the population size and the number of clusters, to be set properly with respect to the problem instance at hand, which is a non-trivial task for any EA practitioner. In this article, we present a new version of MO-GOMEA in combination with the so-called Interleaved Multi-start Scheme (IMS) for the multi-objective domain that eliminates the manual setting of these two parameters. The new MO-GOMEA is then evaluated on multiple benchmark problems in comparison with two well-known multi-objective evolutionary algorithms (MOEAs): Non-dominated Sorting Genetic Algorithm II (NSGA-II) and Multi-objective Evolutionary Algorithm Based on Decomposition (MOEA/D). Experiments suggest that MO-GOMEA with the IMS is an easy-to-use MOEA that retains the excellent performance of the original MO-GOMEA.

High-Dose-Rate (HDR) brachytherapy (BT) treatment planning involves determining an appropriate schedule of a radiation source moving through a patient's body such that target volumes are irradiated with the planning-aim dose as much as possible while healthy tissues (i.e., organs at risk) should not be irradiated more than certain thresholds. Such movement of a radiation source can be defined by so-called dwell times at hundreds of potential dwell positions, which must be configured to satisfy a clinical protocol of multiple different treatment criteria within a strictly-limited time frame of not more than one hour. In this article, we propose a bi-objective optimization model that intuitively encapsulates in two objectives the complicated high-dimensional multi-criteria nature of the BT treatment planning problem. The resulting Pareto-optimal fronts exhibit possible trade-offs between the coverage of target volumes and the sparing of organs at risk, thereby intuitively facilitating the decision-making process of treatment planners when creating a clinically-acceptable plan. We employ real medical data for conducting experiments and benchmark four different Multi-Objective Evolutionary Algorithms (MOEAs) on solving our problem: the Non-dominated Sorting Genetic Algorithm II (NSGA-II), the Multi-Objective Evolutionary Algorithm based on Decomposition (MOEA/D), the Multi-objective Adapted Maximum-Likelihood Gaussian Model Iterated Density-Estimation Evolutionary Algorithm (MAMaLGaM), and the recently-introduced Multi-Objective Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (MO-RV-GOMEA). The variation operator that is specific to MO-RV-GOMEA enables performing partial evaluations to efficiently calculate objective values of offspring solutions without incurring the cost of fully recomputing the radiation dose distributions for new treatment plans. Experimental results show that MO-RV-GOMEA is the best performing MOEA that effectively exploits dependencies between decision variables to efficiently solve the multi-objective BT treatment planning problem.

Often, real-world problems are of the gray-box type. It has been shown that the Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (RV-GOMEA) is in principle capable of exploiting such a Gray-Box Optimization (GBO) setting using linkage models that capture dependencies between problem variables, resulting in excellent performance and scalability on both benchmark and real-world problems that allow for partial evaluations. However, linkage models proposed for RV-GOMEA so far cannot explicitly capture overlapping dependencies. Consequently, performance degrades if such dependencies exist. In this paper, we therefore introduce various ways of using conditional linkage models in RV-GOMEA. Their use is compared to that of non-conditional models, and to VkD-CMA, whose performance is among the state of the art, on various benchmark problems with overlapping dependencies. We find that RV-GOMEA with conditional linkage models achieves the best scalability on most problems, with conditional models leading to similar or better performance than non-conditional models. We conclude that the introduction of conditional linkage models to RV-GOMEA is an important contribution, as it expands the set of problems for which optimization in a GBO setting results in substantially improved performance and scalability. In future work, conditional linkage models may prove to benefit the optimization of real-world problems.

Purpose: Prostate high-dose-rate brachytherapy (HDR-BT) planning involves determining the movement that a high-strength radiation stepping source travels through the patient’s body, such that the resulting radiation dose distribution sufficiently covers tumor volumes and safely spares nearby healthy organs from radiation risks. The Multi-Objective Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (MO-RV-GOMEA) has been shown to be able to effectively handle this inherent bi-objective nature of HDR-BT planning. However, in clinical practice there is a very restricted planning time budget (often less than 1 h) for HDR-BT planning, and a considerable amount of running time needs to be spent before MO-RV-GOMEA finds a good trade-off front of treatment plans (about20–30 min on a single CPU core) with sufficiently accurate dose calculations, limiting the applicability of the approach in the clinic. To address this limitation, we propose an efficiency enhancement technique for MO-RV-GOMEA solving the bi-objective prostate HDR-BT planning problem. Methods: Dose-Volume (DV) indices are often used to assess the quality of HDR-BT plans. The accuracy of these indices depends on the number of dose calculation points at which radiation doses are computed. These are randomly uniformly sampled inside target volumes and organs at risk. In available HDR-BT planning optimization algorithms, the number of dose calculation points is fixed. The more points are used, the better the accuracy of the obtained results will be, but also the longer the algorithms need to be run. In this work, we introduce a so-called multi-resolution scheme that gradually increases the number of dose calculation points during the optimization run such that the running time can be substantially reduced without compromising on the accuracy of the obtained results. Results and conclusion: Experiments on a data set of 18 patient cases show that with the multi-resolution scheme, MO-RV-GOMEA can achieve a sufficiently good trade-off front of treatment plans after five minutes of running time on a single CPU core (4–6 times faster than the old approach with a fixed number of dose calculation points). When the optimization with the multi-resolution scheme is run on a quad-core machine, five minutes are enough to obtain trade-off fronts that are nearly as good as those obtained by running optimization with the old approach in one hour (i.e., 12 times faster). This leaves ample time to perform the selection of the preferred treatment plan from the trade-off front for the specific patient at hand. Furthermore, comparisons with real clinical treatment plans, which were manually made by experienced BT planners within 30–60 min, confirm that the plans obtained by our approach are superior in terms of DV indices. These results indicate that our proposed approach has the potential to be employed in clinical practice.

We introduce a novel surrogate-assisted Genetic Algorithm (GA) for expensive optimization of problems with discrete categorical variables. Specifically, we leverage the strengths of the Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA), a state-of-the-art GA, and, for the first time, propose to use a convolutional neural network (CNN) as a surrogate model. We propose to train the model on pairwise fitness differences to decrease the number of evaluated solutions that is required to achieve adequate surrogate model training. In providing a proof of principle, we consider relatively standard CNNs, and demonstrate that their capacity is already sufficient to accurately learn fitness landscapes of various well-known benchmark functions. The proposed CS-GOMEA is compared with GOMEA and the widely-used Bayesian-optimization-based expensive optimization frameworks SMAC and Hyperopt, in terms of the number of evaluations that is required to achieve the optimum. In our experiments on binary problems with dimensionalities up to 400 variables, CS-GOMEA always found the optimum, whereas SMAC and Hyperopt failed for problem sizes over 16 variables. Moreover, the number of evaluated solutions required by CS-GOMEA to find the optimum was found to scale much better than GOMEA.

Model-based evolutionary algorithms (MBEAs) are praised for their broad applicability to black-box optimization problems. In practical applications however, they are mostly used to repeatedly optimize different instances of a single problem class, a setting in which specialized algorithms generally perform better. In this paper, we introduce the concept of a new type of MBEA that can automatically specialize its behavior to a given problem class using tabula rasa self-learning. For this, reinforcement learning is a naturally fitting paradigm. A proof-of-principle framework, called SL-ENDA, based on estimation of normal distribution algorithms in combination with reinforcement learning is defined. SL-ENDA uses an RL-agent to decide upon the next population mean while approaching the rest of the algorithm as the environment. A comparison of SL-ENDA to AMaLGaM and CMA-ES on unimodal noiseless functions shows mostly comparable performance and scalability to the broadly used and carefully manually crafted algorithms. This result, in combination with the inherent potential of self-learning model-based evolutionary algorithms with regard to specialization, opens the door to a new research direction with great potential impact on the field of model-based evolutionary algorithms.

Semantic Backpropagation (SB) is a recent technique that promotes effective variation in tree-based genetic programming. The basic idea of SB is to provide information on what output is desirable for a specified tree node, by propagating the desired root-node output back to the specified node using inversions of functions encountered along the way. Variation operators then replace the subtree located at the specified node with a tree for which the output is closest to the desired output, by searching in a pre-computed library. In this paper, we propose two contributions to enhance SB specifically for symbolic regression, by incorporating the principles of Keijzer's Linear Scaling (LS). In particular, we show how SB can be used in synergy with the scaled mean squared error, and we show how LS can be adopted within library search. We test our adaptations using the well-known variation operator Random Desired Operator (RDO), comparing to its baseline implementation, and to traditional crossover and mutation. Our experimental results on real-world datasets show that SB enhanced with LS substantially improves the performance of RDO, resulting in overall the best performance among all tested GP algorithms.

The Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) is a model-based EA framework that has been shown to perform well in several domains, including Genetic Programming (GP). Differently from traditional EAs where variation acts blindly, GOMEA learns a model of interdependencies within the genotype, i.e., the linkage, to estimate what patterns to propagate. In this article, we study the role of Linkage Learning (LL) performed by GOMEA in Symbolic Regression (SR). We show that the non-uniformity in the distribution of the genotype in GP populations negatively biases LL, and propose a method to correct for this. We also propose approaches to improve LL when ephemeral random constants are used. Furthermore, we adapt a scheme of interleaving runs to alleviate the burden of tuning the population size, a crucial parameter for LL, to SR. We run experiments on 10 real-world datasets, enforcing a strict limitation on solution size, to enable interpretability. We find that the new LL method outperforms the standard one, and that GOMEA outperforms both traditional and semantic GP. We also find that the small solutions evolved by GOMEA are competitive with tuned decision trees, making GOMEA a promising new approach to SR., Comment: fix NMSE definition (it is 100xMSE/var instead of MSE/var)

In model-based evolutionary algorithms (EAs), the underlying search distribution is adapted to the problem at hand, for example based on dependencies between decision variables. Hill-valley clustering is an adaptive niching method in which a set of solutions is clustered such that each cluster corresponds to a single mode in the fitness landscape. This can be used to adapt the search distribution of an EA to the number of modes, exploring each mode separately. Especially in a black-box setting, where the number of modes is a priori unknown, an adaptive approach is essential for good performance. In this work, we introduce multi-objective hill-valley clustering and combine it with MAMaLGaM, a multi-objective EA, into the multi-objective hill-valley EA (MO-HillVallEA). We empirically show that MO-HillVallEA outperforms MAMaLGaM and other well-known multi-objective optimization algorithms on a set of benchmark functions. Furthermore, and perhaps most important, we show that MO-HillVallEA is capable of obtaining and maintaining multiple approximation sets simultaneously over time.

Current state-of-the-art medical deformable image registration (DIR) methods optimize a weighted sum of key objectives of interest. Having a pre-determined weight combination that leads to high-quality results for any instance of a specific DIR problem (i.e., a class solution) would facilitate clinical application of DIR. However, such a combination can vary widely for each instance and is currently often manually determined. A multi-objective optimization approach for DIR removes the need for manual tuning, providing a set of high-quality trade-off solutions. Here, we investigate machine learning for a multi-objective class solution, i.e., not a single weight combination, but a set thereof, that, when used on any instance of a specific DIR problem, approximates such a set of trade-off solutions. To this end, we employed a multi-objective evolutionary algorithm to learn sets of weight combinations for three breast DIR problems of increasing difficulty: 10 prone-prone cases, 4 prone-supine cases with limited deformations and 6 prone-supine cases with larger deformations and image artefacts. Clinically-acceptable results were obtained for the first two problems. Therefore, for DIR problems with limited deformations, a multi-objective class solution can be machine learned and used to compute straightforwardly multiple high-quality DIR outcomes, potentially leading to more efficient use of DIR in clinical practice.

The importance and potential of Gray-Box Optimization (GBO) with evolutionary algorithms is becoming increasingly clear lately, both for benchmark and real-world problems. We consider the GBO setting where partial evaluations are possible, meaning that sub-functions of the evaluation function are known and can be exploited to improve optimization efficiency. In this paper, we show that the efficiency of GBO can be greatly improved through large-scale parallelism, exploiting the fact that each evaluation function requires the calculation of a number of independent sub-functions. This is especially interesting for real-world problems where often the majority of the computational effort is spent on the evaluation function. Moreover, we show how the best parallelization technique largely depends on factors including the number of sub-functions and their required computation time, revealing that for different parts of the optimization the best parallelization technique should be selected based on these factors. As an illustration, we show how large-scale parallelization can be applied to optimization of high-dose-rate brachytherapy treatment plans for prostate cancer. We find that use of a modern Graphics Processing Unit (GPU) was the most efficient parallelization technique in all realistic scenarios, leading to substantial speed-ups up to a factor of 73.

The Multi-Objective Real-Valued Gene-pool Optimal Mixing Evolutionary Algorithm (MO-RV-GOMEA) has been shown to exhibit excellent performance in solving various bi-objective benchmark and real-world problems. We assess the competence of MO-RV-GOMEA in tackling many-objective problems, which are normally defined as problems with at least four conflicting objectives. Most Pareto dominance-based Multi-Objective Evolutionary Algorithms (MOEAs) typically diminish in performance if the number of objectives is more than three because selection pressure toward the Pareto-optimal front is lost. This is potentially less of an issue for MO-RV-GOMEA because its variation operator creates each offspring solution by iteratively altering a currently existing solution in a few decision variables each time, and changes are only accepted if they result in a Pareto improvement. For most MOEAs, integrating scalarization methods is potentially beneficial in the many-objective context. Here, we investigate the possibility of improving the performance of MO-RV-GOMEA by further guiding improvement checks during solution variation in MO-RV-GOMEA with carefully constructed Tchebycheff scalarizations. Results obtained from experiments performed on a selection of well-known problems from the DTLZ and WFG test suites show that MO-RV-GOMEA is by design already well-suited for many-objective problems. Moreover, by enhancing it with Tchebycheff scalarizations, it outperforms MOEA/D-2TCHMFI, a state-of-the-art decomposition-based MOEA.

Bayesian networks (BNs) are probabilistic graphical models which are widely used for knowledge representation and decision making tasks, especially in the presence of uncertainty. Finding or learning the structure of BNs from data is an NP-hard problem. Evolutionary algorithms (EAs) have been extensively used to automate the learning process. In this paper, we consider the use of the Gene-Pool Optimal Mixing Evolutionary Algorithm (GOMEA). GOMEA is a relatively new type of EA that belongs to the class of model-based EAs. The model used in GOMEA is aimed at modeling the dependency structure between problem variables, so as to improve the efficiency and effectiveness of variation. This paper shows that the excellent performance of GOMEA transfers from well-known academic benchmark problems to the specific case of learning BNs from data due to its model-building capacities and the potential to compute partial evaluations when learning BNs. On commonly-used datasets of varying size, we find that GOMEA outperforms standard algorithms such as Order-based search (OBS), as well as other EAs, such as Genetic Algorithms (GAs) and Estimation of Distribution algorithms (EDAs), even when efficient local search techniques are added.

Model-based evolutionary algorithms (EAs) adapt an underlying search model to features of the problem at hand, such as the linkage between problem variables. The performance of EAs often deteriorates as multiple modes in the fitness landscape are modelled with a unimodal search model. The number of modes is however often unknown a priori, especially in a black-box setting, which complicates adaptation of the search model. In this work, we focus on models that can adapt to the multi-modality of the fitness landscape. Specifically, we introduce Hill-Valley Clustering, a remarkably simple approach to adaptively cluster the search space in niches, such that a single mode resides in each niche. In each of the located niches, a core search algorithm is initialized to optimize that niche. Combined with an EA and a restart scheme, the resulting Hill-Valley EA (HillVallEA) is compared to current state-of-the-art niching methods on a standard benchmark suite for multi-modal optimization. Numerical results in terms of the detected number of global optima show that, in spite of its simplicity, HillVallEA is competitive within the limited budget of the benchmark suite, and shows superior performance in the long run.

The recently introduced Gene-pool Optimal Mixing Evolutionary Algorithm for Genetic Programming (GP-GOMEA) has been shown to find much smaller solutions of equally high quality compared to other state-of-the-art GP approaches. This is an interesting aspect as small solutions better enable human interpretation. In this paper, an adaptation of GP-GOMEA to tackle real-world symbolic regression is proposed, in order to find small yet accurate mathematical expressions, and with an application to a problem of clinical interest. For radiotherapy dose reconstruction, a model is sought that captures anatomical patient similarity. This problem is particularly interesting because while features are patient-specific, the variable to regress is a distance, and is defined over patient pairs. We show that on benchmark problems as well as on the application, GP-GOMEA outperforms variants of standard GP. To find even more accurate models, we further consider an evolutionary meta learning approach, where GP-GOMEA is used to construct small, yet effective features for a different machine learning algorithm. Experimental results show how this approach significantly improves the performance of linear regression, support vector machines, and random forest, while providing meaningful and interpretable features.

The recently introduced permutation Gene-pool Optimal Mixing Evolutionary Algorithm (GOMEA) has shown to be an effective Model Based Evolutionary Algorithm (MBEA) for permutation problems. So far, permutation GOMEA has only been used in the context of Black-Box Optimization (BBO). This paper first shows that permutation GOMEA can be improved by incorporating a constructive heuristic to seed the initial population. Secondly, the paper shows that hybridizing with job swapping neighborhood search does not lead to consistent improvement. The seeded permutation GOMEA is compared to a state-of-the-art algorithm (VNS4) for solving the Permutation Flowshop Scheduling Problem (PFSP). Both unstructured and structured instances are used in the benchmarks. The results show that permutation GOMEA often outperforms the VNS4 algorithm for the PFSP with the total flowtime criterion.

Mixed-integer optimization considers problems with both discrete and continuous variables. The ability to learn and process problem structure can be of paramount importance for optimization, particularly when faced with black-box optimization (BBO) problems, where no structural knowledge is known a priori. For such cases, model-based Evolutionary Algorithms (EAs) have been very successful in the fields of discrete and continuous optimization. In this paper, we present a model-based EA which integrates techniques from the discrete and continuous domains in order to tackle mixed-integer problems. We furthermore introduce the novel mechanisms to learn and exploit mixed-variable dependencies. Previous approaches only learned dependencies explicitly in either the discrete or the continuous domain. The potential usefulness of addressing mixed dependencies directly is assessed by empirically analyzing algorithm performance on a selection of mixed-integer problems with different types of variable interactions. We find substantially improved, scalable performance on problems that exhibit mixed dependencies.

We recently demonstrated the strong potential of using dual-dynamic transformation models when tackling deformable image registration problems involving large anatomical differences. Dual-dynamic transformation models employ two moving grids instead of the common single moving grid for the target image (and single fixed grid for the source image). We previously employed powerful optimization algorithms to make use of the additional flexibility offered by a dual-dynamic transformation model with good results, directly obtaining insight into the trade-off between important registration objectives as a result of taking a multi-objective approach to optimization. However, optimization has so far been initialized using two regular grids, which still leaves a great potential of dual-dynamic transformation models untapped: a-priori grid alignment with image structures/areas that are expected to deform more. This allows (far) less grid points to be used, compared to using a sufficiently refined regular grid, leading to (far) more efficient optimization, or, equivalently, more accurate results using the same number of grid points. We study the implications of exploiting this potential by experimenting with two new smart grid initialization procedures: one manual expert-based and one automated image-feature-based. We consider a CT test case with large differences in bladder volume with and without a multi-resolution scheme and find a substantial benefit of using smart grid initialization.

Deformable image registration is currently predominantly solved by optimizing a weighted linear combination of objectives. Successfully tuning the weights associated with these objectives is not trivial, leading to trial-and-error approaches. Such an approach assumes an intuitive interplay between weights, optimization objectives, and target registration errors. However, it is not known whether this always holds for existing registration methods. To investigate the interplay between weights, optimization objectives, and registration errors, we employ multi-objective optimization. Here, objectives of interest are optimized simultaneously, causing a set of multiple optimal solutions to exist, called the optimal Pareto front. Our medical application is in breast cancer and includes the challenging prone-supine registration problem. In total, we studied the interplay in three different ways. First, we ran many random linear combinations of objectives using the well-known registration software elastix. Second, since the optimization algorithms used in registration are typically of a local-search nature, final solutions may not always form a Pareto front. We therefore employed a multi-objective evolutionary algorithm that finds weights that correspond to registration outcomes that do form a Pareto front. Third, we examined how the interplay differs if a true multi-objective (i.e., weight-free) image registration method is used. Results indicate that a trial-and-error weight-adaptation approach can be successful for the easy prone to prone breast image registration case, due to the absence of many local optima. With increasing problem difficulty the use of more advanced approaches can be of value in finding and selecting the optimal registration outcomes.

The use of gradient information is well-known to be highly useful in single-objective optimization-based image registration methods. However, its usefulness has not yet been investigated for deformable image registration from a multi-objective optimization perspective. To this end, within a previously introduced multi-objective optimization framework, we use a smooth B-spline-based dual-dynamic transformation model that allows us to derive gradient information analytically, while still being able to account for large deformations. Within the multi-objective framework, we previously employed a powerful evolutionary algorithm (EA) that computes and advances multiple outcomes at once, resulting in a set of solutions (a so-called Pareto front) that represents efficient trade-offs between the objectives. With the addition of the B-spline-based transformation model, we studied the usefulness of gradient information in multiobjective deformable image registration using three different optimization algorithms: the (gradient-less) EA, a gradientonly algorithm, and a hybridization of these two. We evaluated the algorithms to register highly deformed images: 2D MRI slices of the breast in prone and supine positions. Results demonstrate that gradient-based multi-objective optimization significantly speeds up optimization in the initial stages of optimization. However, allowing sufficient computational resources, better results could still be obtained with the EA. Ultimately, the hybrid EA found the best overall approximation of the optimal Pareto front, further indicating that adding gradient-based optimization for multiobjective optimization-based deformable image registration can indeed be beneficial.

Medium-voltage distribution network expansion planning involves finding the most economical adjustments of both the capacity and the topology of the network such that no operational constraints are violated and the expected loads, that the expansion is planned for, can be supplied. This paper tackles this important real-world problem using realistic yet computationally feasible models and, for the first time, using two instances of the recently proposed class of Gene-pool Optimal Mixing Evolutionary Algorithms (GOMEAs) that have previously been shown to be a highly efficient integration of local search and genetic recombination, but only on standard benchmark problems. One GOMEA instance that we use employs linkage learning and one instance assumes no dependencies among problem variables. We also conduct experiments with a widely used traditional Genetic Algorithm (GA). Our results show that the favorable performance of GOMEA instances over traditional GAs extends to the real-world problem at hand. Moreover, the use of linkage learning is shown to further increase the algorithm’s effectiveness in converging toward optimal solutions.

Market Garden is a scalable research environment and demonstration tool, in which market mechanisms for smart energy systems and the interaction between end users, traders and system operators can be simulated. Users can create scenarios in a user-friendly editor in which a hierarchical market architecture and a model of the physical grid can be defined. The system sets up an interactive and competitive environment of modular market mechanisms. A visualiser in which the results can be explored in a graphical and intuitive way is included, making Market Garden very suitable for user experience and demonstration purposes, next to its application for research.

Some of the hardest problems in deformable image registration are problems where large anatomical differences occur between image acquisitions (e.g. large deformations due to images acquired in prone and supine positions and (dis)appearing structures between image acquisitions due to surgery). In this work we developed and studied, within a previously introduced multi-objective optimization framework, a dual-dynamic transformation model to be able to tackle such hard problems. This model consists of two non-fixed grids: one for the source image and one for the target image. By not requiring a fixed, i.e. pre-determined, association of the grid with the source image, we can accommodate for both large deformations and (dis)appearing structures. To find the transformation that aligns the source with the target image we used an advanced, powerful model-based evolutionary algorithm that exploits features of a problem's structure in a principled manner via probabilistic modeling. The actual transformation is given by the association of coordinates with each point in the two grids. Linear interpolation inside a simplex was used to extend the correspondence (i.e. transformation) as found for the grid to the rest of the volume. As a proof of concept we performed tests on both artificial and real data with disappearing structures. Furthermore, the case of prone-supine image registration for 2D axial slices of breast MRI scans was evaluated. Results demonstrate strong potential of the proposed approach to account for large deformations and (dis)appearing structures in deformable image registration.

For an evolutionary algorithm (EA) to be efficiently scalable, variation must be linkage friendly. For this reason many EAs have been introduced that build and exploit linkage models, amongst which are estimation-of-distribution algorithms (EDAs). Although various models have been empirically evaluated, it remains of key importance to better understand the conditions under which model building is successful. In this paper, we consider the linkage tree genetic algorithm (LTGA). LTGA is a recent powerful linkage-learning EA that builds a hierarchical linkage model known as the linkage tree (LT). LTGA exploits this model using an intensive mixing procedure aimed at optimally exchanging building blocks. Empirical evaluation studies of LTGA have appeared in literature using different entropy-based measures for building the LT, but with comparable results. We study the differences in these measures to better understand the requirements for detecting important linkage information and point out why some measures are more successful than others.

We define the linkage model evolvability and the evolvability-based fitness distance correlation. These measures give an insight in the search characteristics of linkage model building genetic algorithms. We apply them on the linkage tree genetic algorithm for deceptive trap functions and the nearest-neighbor NK-landscape problem. Comparisons are made between linkage trees, based on mutual information, and random trees which ignore similarity in the population. On a deceptive trap function, the measures clearly show that by learning the linkage tree the problem becomes easy for the LTGA. On the nearest-neighbor NK-landscape the evolvability analysis shows that the LTGA does capture enough of the structure of the problem to solve it reliably and efficiently even though the linkage tree cannot represent the overlapping epistatic information in the NK-problem. The linkage model evolvability measure and the evolvability-based fitness distance correlation prove to be useful tools to get an insight into the search properties of linkage model building genetic algorithms.

In this work we develop and study a methodology for deformable image registration that overcomes a drawback of optimization procedures in common deformable image registration approaches: the use of a single combination of different objectives. Because selecting the best combination is well-known to be non-trivial, we use a multi-objective optimization approach that computes and presents multiple outcomes (a so-called Pareto front) at once. The approach is inherently more powerful because not all Pareto-optimal outcomes are necessarily obtainable by running existing approaches multiple times, for different combinations. Furthermore, expert knowledge can be easily incorporated in making the final best-possible decision by simply looking at (a diverse selection of) the outcomes illustrating both the transformed image and the associated deformation vector field. At the basis of the optimization methodology lies an advanced, model-based evolutionary algorithm that aims to exploit features of a problem's structure in a principled manner via probabilistic modeling. Two objectives are defined: 1) maximization of intensity similarity (normalized mutual information) and 2) minimization of energy required to accomplish the transformation (a model based on Hooke's law that incorporates elasticity characteristics associated with different tissue types). A regular grid of points forms the basis of the transformation model. Interpolation extends the correspondence as found for the grid to the rest of the volume. As a proof of concept we performed tests on a 2D axial slice of a CT scan of a breast. Results indicate plausible behavior of the proposed methodology that innovatively combines intensity-based and model-based registration criteria with state-of-the-art adaptive computation techniques for multi-objective optimization in deformable image registration.

Objective-space discretization is a popular method to control the elitist archive size for evolutionary multi-objective optimization and avoid problems with convergence. By setting the level of discretization, the proximity and diversity of the Pareto approximation set can be controlled. This paper proposes an adaptive archiving strategy which is developed from a rigid-grid discretization mechanism. The main advantage of this strategy is that the practitioner just decides the desirable target size for the elitist archive while all the maintenance details are automatically handled. We compare the adaptive and rigid archiving strategies on the basis of a performance indicator that measures front quality, success rate, and running time. Experimental results confirm the competitiveness of the adaptive method while showing its advantages in terms of transparency and ease of use.

Dynamic Pricing (DyP) is a form of Revenue Management in which the price of a (usually) perishable good is changed over time to increase revenue. It is an effective method that has become even more relevant and useful with the emergence of Internet firms and the possibility of readily and frequently updating prices. In this paper a new approach to DyP is presented. We design adaptive dynamic pricing strategies and optimize their parameters with an Evolutionary Algorithm (EA) offline while the strategies can deal with stochastic market dynamics quickly online. We design two adaptive heuristic dynamic pricing strategies in a duopoly where each firm has a finite inventory of a single type of good. We consider two cases, one in which the average of a customer population’s stochastic valuation for each of the goods is constant throughout the selling horizon and one in which the average customer valuation for each good is changed according to a random Brownian motion. We also design an agent-based software framework for simulating various dynamic pricing strategies in agent-based marketplaces with multiple firms in a bounded time horizon. We use an EA to optimize the parameters for each of the pricing strategies in each of the settings and compare the strategies with other strategies from the literature. We also perform sensitivity a analysis and show that the optimized strategies work well even when used in settings with varied demand functions.

Anke K. Hutzschenreuter Dept. of Industrial Engineering & Innovation Sciences Eindhoven University of Technology P.O. Box 513 5600 MB Eindhoven The Netherlands a.hutzschenreuter@gmail.com Peter A.N. Bosman Centrum Wiskunde & Informatica (CWI) P.O. Box 94079 1090 GB Amsterdam The Netherlands Peter.Bosman@cwi.nl Han La Poutre Centrum Wiskunde & Informatica (CWI) P.O. Box 94079 1090 GB Amsterdam The Netherlands Han.La.Poutre@cwi.nl

Fundamental research into Genetic Algorithms (GA) has led to one of the biggest successes in the design of stochastic optimization algorithms: Estimation-of-Distribution Algorithms (EDAs). These principled algorithms identify and exploit structural features of a problem's structure during optimization. EDA design has so far been limited to classical solution representations such as binary strings or vectors of real values. In this chapter we adapt the EDA approach for use in optimizing problems with tree representations and thereby attempt to expand the boundaries of successfull evolutionary algorithms. To do so, we propose a probability distribution for the space of trees, based on a grammar. To introduce dependencies into the distribution, grammar transformations are performed that facilitate the description of specific subfunctions. The results of performing experiments on two benchmark problems demonstrate the feasibility of the approach.

With advances in technology in communication and navigation, the ability to make decisions online (i.e. as time goes by) becomes increasingly important in transportation and logistics. In this chapter, we focus on online decision making in these areas. First, we point out the importance of anticipation when optimizing decision processes online. Anticipation is the possibility to take into account future events and the influence of decisions taken now on those future events. Second, we discuss how computational intelligence (CI) can be used to design approaches that perform anticipation. We illustrate this particular use of CI techniques in two different applications: dynamic vehicle routing (transportation) and inventory management (logistics). In both cases the use of anticipation is found to lead to substantial improvements. This demonstrates our main conclusion that the ability to perform anticipation in online transportation and logistics is very important.