Search

The factors determining a drug's success are manifold, making de novo drug design an inherently multi-objective optimisation (MOO) problem. With the advent of machine learning and optimisation methods, the field of multi-objective compound design has seen a rapid increase in developments and applications. Population-based metaheuris-tics and deep reinforcement learning are the most commonly used artificial intelligence methods in the field, but recently conditional learning methods are gaining popularity. The former approaches are coupled with a MOO strat-egy which is most commonly an aggregation function, but Pareto-based strategies are widespread too. Besides these and conditional learning, various innovative approaches to tackle MOO in drug design have been proposed. Here we provide a brief overview of the field and the latest innovations.

In complex, expensive optimization domains we often narrowly focus on finding high performing solutions, instead of expanding our understanding of the domain itself. But what if we could quickly understand the complex behaviors that can emerge in said domains instead? We introduce surrogate-assisted phenotypic niching, a quality diversity algorithm which allows to discover a large, diverse set of behaviors by using computationally expensive phenotypic features. In this work we discover the types of air flow in a 2D fluid dynamics optimization problem. A fast GPU-based fluid dynamics solver is used in conjunction with surrogate models to accurately predict fluid characteristics from the shapes that produce the air flow. We show that these features can be modeled in a data-driven way while sampling to improve performance, rather than explicitly sampling to improve feature models. Our method can reduce the need to run an infeasibly large set of simulations while still being able to design a large diversity of air flows and the shapes that cause them. Discovering diversity of behaviors helps engineers to better understand expensive domains and their solutions.

Kriging or Gaussian Process Regression is applied in many fields as a non-linear regression model as well as a surrogate model in the field of evolutionary computation. However, the computational and space complexity of Kriging, that is cubic and quadratic in the number of data points respectively, becomes a major bottleneck with more and more data available nowadays. In this paper, we propose a general methodology for the complexity reduction, called cluster Kriging, where the whole data set is partitioned into smaller clusters and multiple Kriging models are built on top of them. In addition, four Kriging approximation algorithms are proposed as candidate algorithms within the new framework. Each of these algorithms can be applied to much larger data sets while maintaining the advantages and power of Kriging. The proposed algorithms are explained in detail and compared empirically against a broad set of existing state-of-the-art Kriging approximation methods on a well-defined testing framework. According to the empirical study, the proposed algorithms consistently outperform the existing algorithms. Moreover, some practical suggestions are provided for using the proposed algorithms., Submitted to IEEE Computational Intelligence Magazine for review

An algorithm is proposed for multi-objective optimisation of Lipschitz objective functions that each satisfy a Lipschitz condition of which a Lipschitz constant is a priori known. The number of function evaluations is reduced by determining a good next point of evaluation using an Expected Hypervolume Improvement (EHVI) approach. It is closely related to Shubert’s Algorithm for single objective optimisation on one-dimensional decision space, but sampling sequences can be slightly different.

This paper provides a short summary of a novel algorithm tailored towards multi-objective flexible job shop scheduling problems (FJSP). The result shows that for challenging real-world problems in combinatorial optimization, off-the-shelf implementations of multi-objective optimization evolutionary algorithms (MOEAs) might not work, but by using various adaptations, these methods can be tailored to provide excellent results. This is demonstrated for a state of the art MOEA, that is NSGA-III, and the following adaptations: (1) initialization approaches to enrich the first-generation population, (2) various crossover operators to create a better diversity of offspring, (3) parameter tuning, to determine the optimal mutation probabilities, using the MIP-EGO configurator, (4) local search strategies to explore the neighborhood for better solutions. Using these measures, NSGA-III has been enabled to solve benchmark multi-objective FJSPs and experimental results show excellent performance.

After the recent groundbreaking results of AlphaGo and AlphaZero, we have seen strong interests in deep reinforcement learning and artificial general intelligence (AGI) in game playing. However, deep learning is resource-intensive and the theory is not yet well developed. For small games, simple classical table-based Q-learning might still be the algorithm of choice. General Game Playing (GGP) provides a good testbed for reinforcement learning to research AGI. Q-learning is one of the canonical reinforcement learning methods, and has been used by (Banerjee & Stone, IJCAI 2007) in GGP. In this paper we implement Q-learning in GGP for three small-board games (Tic-Tac-Toe, Connect Four, Hex), to allow comparison to Banerjee et al. We find that Q-learning converges to a high win rate in GGP. For the ϵ" role="presentation" style="display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; position: relative;">ϵ-greedy strategy, we propose a first enhancement, the dynamic ϵ" role="presentation" style="display: inline-table; line-height: normal; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border-width: 0px; border-style: initial; position: relative;">ϵ algorithm. In addition, inspired by (Gelly & Silver, ICML 2007) we combine online search (Monte Carlo Search) to enhance offline learning, and propose QM-learning for GGP. Both enhancements improve the performance of classical Q-learning. In this work, GGP allows us to show, if augmented by appropriate enhancements, that classical table-based Q-learning can perform well in small games.

Many problems are of a mixed integer nature, rather than being restricted to a single variable type. Although mixed integer algorithms exist for the single-objective case, work on the multi-objective case remains limited. Evolution strategies are stochastic optimisation algorithms that feature step size adaptation mechanisms and are typically used in continuous domains. More recently they were generalised to mixed integer problems. In this work, first steps are taken towards extending the single-objective mixed integer evolution strategy for the multi-objective case. First results are promising, but step size adaptation for the multi-objective case can likely be improved.

It is a common technique in global optimization with expensive black-box functions, to learn a regression model (or surrogate-model) of the response function from past evaluations and to use this model to decide on the location of future evaluations. In surrogate model assisted optimization it can be difficult to select the right modeling technique. Without preliminary knowledge about the function it might be beneficial if the algorithm trains as many different surrogate models as possible and selects the model with the smallest training error. This is known as model selection. Recently a generalization of this approach was proposed: instead of selecting a single model we propose to use optimal convex combinations of model predictions. This approach, called model mixtures, is adopted and evaluated in the context of sequential parameter optimization. Besides discussing the general strategy, the optimal frequency of learning the convex weights is investigated. The feasibility of this approach is examined and its benefits are compared to simpler methods.

Bayesian Global Optimization (BGO) is a very efficient technique to optimize expensive evaluation problems. However, the application domain is limited to continuous search spaces when using a BGO algorithm. To solve mixed integer problems with a BGO algorithm, this paper adapts the heterogeneous distance function to construct the Kriging models and applies these new Kriging models in Multi-objective Bayesian Global Optimization (MOBGO). The proposed mixed integer MOBGO algorithm and the traditional MOBGO algorithm are compared on three mixed integer multi-objective optimization problems (MOP), w.r.t. the mean value of the hypervolume (HV) and the related standard deviation.

This paper proposes a new method for multi-disciplinary optimisation of building spatial designs in the preliminary design stage. First it discusses two recently developed building spatial design optimisation methods, one using a super-structured approach and the other applying a superstructure free approach. Subsequently, a combination of the two methods into a new hybrid method is presented. A case study is demonstrated to compare the three methods based on their performance and the characteristics of their design evolution. First results show that the hybrid method could aid in the effective exploration of large design search spaces by selecting more confined design search spaces based on engineering knowledge.

The aim of evolutionary level set approximation is to find a finite representation of a level set of a given black box function. The problem of level set approximation plays a vital role in solving problems, for instance in fault detection in water distribution systems, engineering design, parameter identification in gene regulatory networks, and in drug discovery. The goal is to create algorithms that quickly converge to feasible solutions and then achieve a good coverage of the level set. The population based search scheme of evolutionary algorithms makes this type of algorithms well suited to target such problems. In this paper, the focus is on continuous black box functions and we propose a challenging benchmark for this problem domain and propose dual mutation strategies, that balance between global exploration and local refinement. Moreover, the article investigates the role of different indicators for measuring the coverage of the level set approximation. The results are promising and show that even for difficult problems in moderate dimension the proposed evolutionary level set approximation algorithm (ELSA) can serve as a versatile and robust meta-heuristic.

Let $B$ be a set of $n$ axis-parallel boxes in $\mathbb{R}^d$ such that each box has a corner at the origin and the other corner in the positive quadrant of $\mathbb{R}^d$, and let $k$ be a positive integer. We study the problem of selecting $k$ boxes in $B$ that maximize the volume of the union of the selected boxes. This research is motivated by applications in skyline queries for databases and in multicriteria optimization, where the problem is known as the hypervolume subset selection problem. It is known that the problem can be solved in polynomial time in the plane, while the best known running time in any dimension $d \ge 3$ is $\Omega\big(\binom{n}{k}\big)$. We show that: - The problem is NP-hard already in 3 dimensions. - In 3 dimensions, we break the bound $\Omega\big(\binom{n}{k}\big)$, by providing an $n^{O(\sqrt{k})}$ algorithm. - For any constant dimension $d$, we present an efficient polynomial-time approximation scheme., Comment: Presented at SoCG'17. Full Version. 24 pages

The vehicle routing problem is a classical combinatorial optimization problem. This work is about a variant of the vehicle routing problem with dynamically changing orders and time windows. In real-world applications often the demands change during operation time. New orders occur and others are canceled. In this case new schedules need to be generated on-the-fly. Online optimization algorithms for dynamical vehicle routing address this problem but so far they do not consider time windows. Moreover, to match the scenarios found in real-world problems adaptations of benchmarks are required. In this paper, a practical problem is modeled based on the procedure of daily routing of a delivery company. New orders by customers are introduced dynamically during the working day and need to be integrated into the schedule. A multiple ant colony algorithm combined with powerful local search procedures is proposed to solve the dynamic vehicle routing problem with time windows. The performance is tested on a new benchmark based on simulations of a working day. The problems are taken from Solomon’s benchmarks but a certain percentage of the orders are only revealed to the algorithm during operation time. Different versions of the MACS algorithm are tested and a high performing variant is identified. Finally, the algorithm is tested in situ: In a field study, the algorithm schedules a fleet of cars for a surveillance company. We compare the performance of the algorithm to that of the procedure used by the company and we summarize insights gained from the implementation of the real-world study. The results show that the multiple ant colony algorithm can get a much better solution on the academic benchmark problem and also can be integrated in a real-world environment.

Building design can be supported effectively by computer-aided design exploration. This paper investigates optimisation based on a mixed-integer super-structure representation of the search space of building spatial designs. It can take into account parametric as well as topological variations. In the suggested super-structure – the so-called supercube representation – discrete and continuous variables determine the existence, respectively, dimensioning of spaces of the building spatial design. Constraints are formulated as closed form equations and can be used to numerically assess the feasibility of designs. A population-based constraint-handling evolutionary strategy is developed. In the constraint handling repair and penalty methods are combined in a domain specific way. The method is tested on different search space sizes and first promising results are reported.

This paper proposes a first step towards multidisciplinary design of building spatial designs. Two criteria, total surface area (i.e. energy performance) and compliance (i.e. structural performance), are combined in a multicriteria optimisation framework. A new way of representing building spatial designs in a mixed integer parameter space is used within this framework. Two state-of-the-art algorithms, namely NSGA-II and SMS-EMOA, are used and compared to compute Pareto front approximations for problems of different size. Moreover, the paper discusses domain specific search operators, which are compared to generic operators, and techniques to handle constraints within the mutation. The results give first insights into the trade-off between energy and structural performance and the scalability of the approach.

Contains fulltext : 72676.pdf (Publisher’s version ) (Open Access) Belgian-Dutch Conference on Artificial Intelligence (BNAIC), 2008, Enschede, the Netherlands, 30 oktober 2008

Building performance simulation (BPS) is a powerful tool to predict and analyze the dynamic behavior of indicators such as energy consumption and comfort among others. Previous work has shown that the use of BPS is mostly limited to code compliance checking in the detailed design. Our long-term goal is to improve the use of BPS in the later phases of the design process by, for instance, indicating design solutions and by introducing integrated building and system optimization. In this context, we hypothesize that introducing a design optimization and exploration capability to BPS-tools can provide a valuable support for decision making. This paper presents preliminary results and experiences on extending an existing BPS – tool with a capability for single-and multiobjective optimization and parameter exploration. The focus of this work is on energy consumption and thermal comfort.

In multi-disciplinary building optimisation, solutions depend on the representation of the design search space, the latter being a collection of all solutions. This paper presents two design search space representations and discusses their advantages and disadvantages: The first, a super-structure approach, requires all possible solutions to be prescribed in a so-called super-structure. The second approach, super-structure free, uses dynamic data structures that offer freedom in the range of possible solutions. It is concluded that both approaches may supplement each other, if applied in a combination of optimisation methods. A method for this combination of optimisation methods is proposed. The method includes the transformation of one representation into the other and vice versa. Finally, therefore in this paper these transformations are proposed, implemented, and verified as well.

This thesis describes the importance of being able to control the selectivity of potential drug candidates. It explains how computational models are employed to predict and rationalize compound-protein binding (affinity) and therewith, selectivity of compounds. Moreover, it shows that selectivity can purposely be tuned to target either a single protein or an entire panel of proteins. The challenges of selectivity modeling are addressed based on case studies in the sodium-dependent glucose co-transporters, G protein-coupled receptors, and kinases.

It is a common technique in global optimization with expensive black-box functions to learn a surrogate-model of the response function from past evaluations and use it to decide on the location of future evaluations.In surrogate-model-assisted optimization, selecting the right modeling technique without preliminary knowledge about the objective function can be challenging. It might be beneficial if the algorithm trains many different surrogate models and selects the model with the smallest training error. This approach is known as model selection.In this thesis, a generalization of this approach is developed. Instead of choosing a single model, the optimal convex combinations of model predictions is used to combine surrogate models into one more accurate ensemble surrogate model.This approach is studied in a fundamental way, by first evaluating minimalistic ensembles of only two surrogate models in detail and then proceeding to ensembles with more surrogate models.Finally, the approach is adopted and evaluated in the context of sequential parameter optimization. Besides discussing the general strategy, the optimal frequency of learning the convex combination of weights is investigated.The results provide insights into the performance, scalability, and robustness of the approach.

Optimization tasks in practice have multifaceted challenges as they are often black box, subject to multiple equality and inequality constraints and expensive to evaluate. The efficiency of a constrained optimizer has a crucial importance when it comes to selecting a suitable method for solving real-world optimization problems from industry with strict resource limitations. The primary concern of this work is to develop new black box optimization algorithms which are generic enough to successfully handle a broad set of constrained optimization problems (COPs) efficiently and without requiring apriori parameter tuning for different classes of the problems. To achieve this goal we benefit from two main conceptual components in the development of new constrained solvers: 1. utilizing surrogate modeling techniques to save real function evaluations, 2. automatically adjusting sensitive problem-dependent parameters based on the information gained about the problems during the optimization procedure. This work eventuated in the development of two surrogate-assisted constrained solvers: SACOBRA and SOCU. It turns out that SACOBRA outperforms most other COP-solvers in solving the well-known G-problem suite and MOPTA08 (a COP from automotive industry), if the number of function evaluations is strongly limited.

Multi-objective evolutionary computation aims to find high quality (Pareto optimal) solutions that represent the trade-off between multiple objectives. Within this field there are a number of key challenges. Among others, this includes constraint handling and the exploration of mixed-integer search spaces. This thesis investigates how these challenges can be handled at the same time, and in particular how they can be applied in the multi-objective optimisation algorithms. These algorithms are developed in the context of the optimisation of building spatial designs, which describe the exterior shape of a building, and the internal division into different spaces. Spatial designs are developed early in the design process, and thus have a large impact on the final building design, and in turn also on the quality of the building. Here the structural and thermal performance of a building are optimised to reduce resource consumption. The main contributions of this thesis are as follows. Firstly, a representation for building spatial designs in is introduced. Secondly, specialised search operators are designed to ensure only feasible solutions will be explored. Thirdly, data about the discovered solutions is analysed to explain the results to domain experts. Finally, a general purpose multi-objective mixed-integer evolutionary algorithm is developed.

This thesis seeks to combine two different research topics; Multi-Objective Optimization and Complex Network Analysis. Multi-Objective Optimization aims at finding a set of optimal, non-dominated solutions for optimization problems with multiple (actually, many) conflicting objectives. There is a wide range of applications of multi-objective optimization such as in science, engineering design, network analysis, chemical processes, delivery of products, economics and logistics, medical health and so forth. Since one often faces problems with a larger number of objective functions to be optimized simultaneously, the research topic has shifted to Many-Objective Optimization, which means optimization with (far) more than three objective functions. Complex network analysis is a research field that deals with analyzing large networks. In this research line, there are some active research topics, such as controlling complex networks, finding communities in a network, and measuring the importance of nodes in networks. Due to the bigger amount of data and more difficult problems arising in complex network analysis, research in this field has increased significantly. To this end, more complex networks has given the challenge of finding better approaches in dealing with the problem to yield some adequate result of an analysis.

Continuous optimization is never easy: the exact solution is always a luxury demand and the theory of it is not always analytical and elegant. Continuous optimization, in practice, is essentially about the efficiency: how to obtain the solution with same quality using as minimal resources (e.g., CPU time or memory usage) as possible? In this thesis, the number of function evaluations is considered as the most important resource to save. To achieve this goal, various efforts have been implemented and applied successfully. One research stream focuses on the so-called stochastic variation (mutation) operator, which conducts an (local) exploration of the search space. The efficiency of those operator has been investigated closely, which shows a good stochastic variation should be able to generate a good coverage of the local neighbourhood around the current search solution. This thesis contributes on this issue by formulating a novel stochastic variation that yields good space coverage.

A common method to solve expensive function evaluation problem is using Bayesian Global Optimization, instead of Evolutionary Algorithms. However, the execution time of multi-objective Bayesian Global Optimization (MOBGO) itself is still too long, even though it only requires a few function evaluations. The reason for the high cost of MOBGO is two-fold: on the one hand, MOBGO requires an infill criterion to be calculated many times, but the computational complexity of an infill criterion has so far been very high. Another reason is that the optimizer, which aims at searching for an optimal solution according to the surrogate models, is not sufficiently efficient. The main contributions of this thesis consist of 1. Decreased the computational complexity of a well-known infill criteria, Expected Hypervolume Improvement, into $n log (n)$ both in 2-D and 3-D cases; 2. Proposed a new criterion, Truncated Expected Hypervolume Improvement, to make full use of a-priori knowledge of objective functions, whenever it is available; 3. Proposed another infill criterion, Expected Hypervolume Improvement Gradient, to improve the convergence of the optimizer in MOBGO.

Software architecting is a non-trivial and demanding task for software engineers to perform. The architecture is a key enabler for software systems. Besides being crucial for user functionality, the software architecture has deep impact on software qualities such as performance, safety, and cost. In this dissertation, an automated approach for software architecture design is proposed that supports analysis and optimization of multiple quality attributes:First of all, we demonstrate an optimization approach for automated software architecture design. It reports the results of applying our architecture optimization framework to an automotive sub-system that was conducted based on a large-scale real world case study. Moreover, we introduce two novel degrees of freedom which demonstrate how the number of processing nodes and their interconnecting network can be codified to fit into a genetic algorithm. Our studies show that these extra degrees of freedom lead to better overall software architecture optimization. Finally, we propose a new search-based approach for generating a set of optimal software architectural solutions for use in software product lines. Our new approach analyses the commonality of the found optimal solutions and proposes a set of solutions which are suitable for the range of products defined by various feature combinations.

Real-world (black-box) optimization problems often involve various types of uncertainties and noise emerging in different parts of the optimization problem. When this is not accounted for, optimization may fail or may yield solutions that are optimal in the classical strict notion of optimality, but fail in practice. Robust optimization is the practice of optimization that actively accounts for uncertainties and/or noise. Evolutionary Algorithms form a class of optimization algorithms that use the principle of evolution to find good solutions to optimization problems. Because uncertainty and noise are indispensable parts of nature, this class of optimization algorithms seems to be a logical choice for robust optimization scenarios. This thesis provides a clear definition of the term robust optimization and a comparison and practical guidelines on how Evolution Strategies, a subclass of Evolutionary Algorithms for real-parameter optimization problems, should be adapted for such scenarios.