Learning and Intelligent Optimization

Noisy optimization is the optimization of objective functions corrupted by noise. A portfolio of algorithms is a set of algorithms equipped with an algorithm selection tool for distributing the computational power among them. We study portfolios of noisy optimization solvers, show that different settings lead to different performances, obtain mathematically proved performance (in the sense that the portfolio performs nearly as well as the best of its’ algorithms) by an ad hoc selection algorithm dedicated to noisy optimization. A somehow surprising result is that it is better to compare solvers with some lag; i.e., recommend the

current

recommendation of the best solver, selected from a comparison based on their recommendations

earlier

in the run.

The Algorithm Selection Problem [

8

] is to select the most appropriate algorithm for solving a particular problem. It is especially relevant in the context of algorithm portfolios [

2

,

3

], where a single solver is replaced with a set of solvers and a mechanism for selecting a subset to use on a particular problem. A common way of doing algorithm selection is to train a machine learning model and predict the best algorithm from a portfolio to solve a particular problem.

Within the Constraints Satisfaction Problems (CSP) context, a methodology that has proven to be particularly performant consists in using a portfolio of different constraint solvers. Nevertheless, comparatively few studies and investigations have been done in the world of Constraint Optimization Problems (COP). In this work, we provide a generalization to COP as well as an empirical evaluation of different state of the art existing CSP portfolio approaches properly adapted to deal with COP. Experimental results confirm the effectiveness of portfolios even in the optimization field, and could give rise to some interesting future research.

Modern solvers for hard computational problems often expose parameters that permit customization for high performance on specific instance types. Since it is tedious and time-consuming to manually optimize such highly parameterized algorithms, recent work in the AI literature has developed automated approaches for this

algorithm configuration problem

[

1

,

3

,

10

,

11

,

13

,

16

].

Configuring algorithms automatically to achieve high performance is becoming increasingly relevant and important in many areas of academia and industry. Algorithm configuration methods take a parameterized target algorithm, a performance metric and a set of example data, and aim to find a parameter configuration that performs as well as possible on a given data set.

The propositional satisfiability problem (SAT) is one of the most prominent and widely studied NP-hard problems. The development of SAT solvers, whether it is carried out manually or through the use of automated design tools such as algorithm configurators, depends substantially on the sets of benchmark instances used for performance evaluation. Since the supply of instances from real-world applications of SAT is limited, and artificial instance distributions such as Uniform Random

$$k$$

k

-SAT are known to have markedly different structure, there has been a long-standing interest in instance generators capable of producing ‘realistic’ SAT instances that could be used during development as proxies for real-world instances. However, it is not obvious how to assess the quality of the instances produced by any such generator. We propose a new approach for evaluating the usefulness of an arbitrary set of instances for use as proxies during solver development, and introduce a new metric,

$$Q$$

Q

-score, to quantify this. We apply our approach on several artificially generated and real-world benchmark sets and quantitatively compare their usefulness for developing competitive SAT solvers.

Automating the process of finding good parameter settings is important in the design of high-performing algorithms. These automatic processes can generally be categorized into off-line and on-line methods. Off-line configuration consists in learning and selecting the best setting in a training phase, and usually fixes it while solving an instance. On-line adaptation methods on the contrary vary the parameter setting adaptively during each algorithm run. In this work, we provide an empirical study of both approaches on the operator selection problem, explore the possibility of varying parameter value by a non-adaptive distribution tuned off-line, and incorporate the off-line with on-line approaches. In particular, using an off-line tuned distribution to vary parameter values at runtime appears to be a promising idea for automatic configuration.

The Vertex Separator Problem (VSP) on a graph is the problem of finding the smallest collection of vertices whose removal separates the graph into two disjoint subsets of roughly equal size. Recently, Hager and Hungerford [

1

] developed a continuous bilinear programming formulation of the VSP. In this paper, we reinforce the bilinear programming approach with a multilevel scheme for learning the structure of the graph.

Multidimensional scaling is a technique for exploratory analysis of multidimensional data. The essential part of the technique is minimization of a function with unfavorable properties like multimodality, non-differentiability, and invariability with respect to some transformations. Recently various two-level optimization algorithms for multidimensional scaling with city-block distances have been proposed exploiting piecewise quadratic structure of the least squares objective function with such distances. A problem of combinatorial optimization is tackled at the upper level, and convex quadratic programming problems are tackled at the lower level. In this paper we discuss a new reformulation of the problem where lower level quadratic programming problems seem more suited for two-level optimization.

The main goal of the present paper is the development of general approach to network analysis of statistical data sets. First a general method of market network construction is proposed on the base of idea of measures of association. It is noted that many existing network models can be obtained as a particular case of this method. Next it is shown that statistical multiple decision theory is an appropriate theoretical basis for market network analysis of statistical data sets. Finally conditional risk for multiple decision statistical procedures is introduced as a natural measure of quality in market network analysis. Some illustrative examples are given.

The present paper deals with a problem of stock selection in market network as a multiple decision problem. The quality of the multiple decision procedure is measured by conditional risk (mean of the loss function). Optimal in this sense multiple decision statistical procedure for stock selection is constructed. Conditional risk behavior is studied for different number of observations and different significance levels. The obtained results can be applied to stock selection by various criteria: returns, volumes, risks.

In recent years there have been a number of important improvements in exact color-based maximum clique solvers, which have considerably enhanced their performance. Initial vertex ordering is one strategy known to have a significant impact on the size of the search tree. Typically, a degenerate sorting by minimum degree is used; literature also reports different tiebreaking strategies. A systematic study of the impact of initial sorting in the light of new cutting-edge ideas (e.g. recoloring [

8

], selective coloring [

13

], ILS initial lower bound computation [

15

,

16

] or MaxSAT-based pruning [

14

]) is, however, lacking. This paper presents a new initial sorting procedure and relates performance to the new mentioned variants implemented in leading solver BBMC [

9

,

10

].

The objective functions in multiobjective optimization problems are often non-linear, noisy, or not available in a closed form and evolutionary multiobjective optimization (EMO) algorithms have been shown to be well applicable in this case. Here, our objective is to facilitate

interactive decision making

by saving function evaluations outside the “interesting” regions of the search space within a hypervolume-based EMO algorithm. We focus on a basic model where the Decision Maker (DM) is always asked to pick the most desirable solution among a set. In addition to the scenario where this solution is chosen directly, we present the alternative to specify preferences via a set of so-called comparative preference statements. Examples on standard test problems show the working principles, the competitiveness, and the drawbacks of the proposed algorithm in comparison with the recent iTDEA algorithm.

As an evolutionary approach to solve multi-objective optimization problems involving several constraints, recently a MOEA using the two-stage non-dominated sorting and the directed mating (TNSDM) has been proposed. In TNSDM, the directed mating utilizes infeasible solutions dominating feasible solutions in the objective space to generate offspring. Our previous work showed that the directed mating significantly contributed to improve the search performance of TNSDM on several benchmark problems. However, the conventional directed mating has two problems. First, since the conventional directed mating selects a pair of parents based on the conventional Pareto dominance, two parents having different search directions are mated in some cases. Second, in problems with high feasibility ratio, since the number of infeasible solutions in the population is low, sometimes the directed mating cannot be performed. Consequently, the effectiveness of the directed mating cannot be obtained. To overcome these problems and further improve the effectiveness of the directed mating in TNSDM, in this work we propose a method to control selection areas of infeasible solutions by controlling dominance area of solutions (CDAS). We verify the effectiveness of the proposed method in TNSDM, and compare its search performance with the conventional CNSGA-II on

$$m$$

m

objectives

$$k$$

k

knapsacks problems. As results, we show that the search performance of TNSDM is further improved by controlling selection area of infeasible solutions in the directed mating.

We propose an evolutionary multiobjective algorithm that approximates multiple reference points (the aspiration set) in a single run using the concept of the averaged Hausdorff distance.

Many studies in the literature have applied multi-objective evolutionary algorithms (MOEAs) to multi-objective combinatorial optimization problems. Few of them analyze the actual contribution of the basic algorithmic components of MOEAs. These components include the underlying EA structure, the fitness and diversity operators, and their policy for maintaining the population. In this paper, we compare seven MOEAs from the literature on three bi-objective and one tri-objective variants of the permutation flowshop problem. The overall best and worst performing MOEAs are then used for an iterative analysis, where each of the main components of these algorithms is analyzed to determine their contribution to the algorithms’ performance. Results confirm some previous knowledge on MOEAs, but also provide new insights. Concretely, some components only work well when simultaneously used. Furthermore, a new best-performing algorithm was discovered for one of the problem variants by replacing the diversity component of the best performing algorithm (NSGA-II) with the diversity component from PAES.

The aim of this work is to compare different approaches for parallelization in model-based optimization. As another alternative aside from the existing methods, we propose using a multi-objective infill criterion that rewards both the diversity and the expected improvement of the proposed points. This criterion can be applied more universally than the existing ones because it has less requirements. Internally, an evolutionary algorithm is used to optimize this criterion. We verify the usefulness of the approach on a large set of established benchmark problems for black-box optimization. The experiments indicate that the new method’s performance is competitive with other batch techniques and single-step EGO.

The main principle of a look-ahead strategy is to inspect a few steps ahead before taking a decision on the direction to choose. We propose two original look-ahead strategies that differ in the object of inspection. The first method introduces a look-ahead mechanism at a superior level for selecting local-search operators. The second method uses a look-ahead strategy on a lower level in order to detect promising solutions for further improvement. The proposed approaches are implemented using a hyper-heuristic framework and tested against alternative methods. Furthermore, a more detailed investigation of the second method is added and gives insight on the influence of parameter values. The experiments reveal that the introduction of a simple look-ahead strategy into an iterated local-search procedure significantly improves the results over tested problem instances.

The leader-follower facility location problem arises in the context of two non-cooperating companies, a leader and a follower, competing for market share from a given set of customers. In our work we assume that the firms place a given number of facilities on locations taken from a discrete set of possible points. The customers are assumed to split their demand inversely proportional to their distance to all opened facilities. In this work we present an evolutionary algorithm with an embedded tabu search to optimize the location selection for the leader. A complete solution archive is used to detect already visited candidate solutions and convert them into not yet considered ones. This avoids unnecessary time-consuming re-evaluations, reduces premature convergence and increases the population diversity at the same time. Results show significant advantages of our approach over an existing algorithm from the literature.

The Berth Allocation Problem aims at assigning and scheduling incoming vessels to berthing positions along the quay of a container terminal. This problem is a well-known optimization problem within maritime shipping. For solving it, we propose two POPMUSIC (Partial Optimization Metaheuristic Under Special Intensification Conditions) approaches that incorporate an existing mathematical programming formulation. POPMUSIC is an efficient metaheuristic that may serve as blueprint for matheuristics approaches once hybridized with mathematical programming. In this regard, the use of exact methods for solving the sub-problems defined in the POPMUSIC template highlight an interoperation between metaheuristics and mathematical programming techniques, which provide a new type of approach for this problem. Computational experiments reveal excellent results.

This paper proposes a hybrid Greedy Randomized Adaptive Search Procedure with path-relinking for the maximum contact map overlap problem, an NP-hard combinatorial optimization problem that arises in computational biology. Preliminary experimental results illustrate the effectiveness and efficiency of the algorithm.

Unlike a

synchronous

program evolution in the context of evolutionary computation that evolves individuals (

i.e.

, programs) after evaluations of

all

individuals in each generation, this paper focuses on an

asynchronous

program evolution that evolves individuals during evaluations of

each

individual. To tackle this problem, we explore the mechanism that can promote an asynchronous program evolution by selecting a

good

individual without waiting for evaluations of

all

individuals, and investigates its effectiveness in genetic programming (GP) domain. The intensive experiments have revealed the following implications: (1) the program

asynchronously

evolved

with

the proposed mechanism can be completed with the shorter execution steps than the program

asynchronously

evolved

without

the proposed mechanism; and (2) the program

asynchronously

evolved

with

the proposed mechanism can be completed with mostly the same or shorter execution steps than the program

synchronously

evolved by the conventional GP.

This study addresses a two-stage supply chain scheduling problem, where the jobs need to be processed on the manufacturer’s serial batching machine and then transported by vehicles to the customer for further processing. The size and processing time of the jobs are varying due to the differences of types, and setup time is needed before processing one batch. For the problem with minimizing the makespan, we formalize it as a mixed integer programming model. In addition, the structural properties and lower bound of the problem are provided. Based on the analysis above, a novel hybrid dynamic programming algorithm, combining dynamic programming and heuristics, is proposed to solve the problem. Furthermore, its time complexity is also analyzed. By comparing the experimental results of our proposed algorithm with the heuristics

$$BFF$$

B

F

F

and

$$LFF$$

L

F

F

, we demonstrate that our proposed algorithm has better performance and can solve the problem in a reasonable time.

The Clonal Selection Algorithm is the most known algorithm inspired from the Artificial Immune Systems and used effectively in optimization problems. In this paper, this nature inspired algorithm is used in a hybrid scheme with other metaheuristic algorithms for successfully solving the Vehicle Routing Problem with Stochastic Demands (VRPSD). More precisely, for the solution of this problem, the Hybrid Clonal Selection Algorithm (HCSA) is proposed which combines a Clonal Selection Algorithm (CSA), a Variable Neighborhood Search (VNS), and an Iterated Local Search (ILS) algorithm. The effectiveness of the original Clonal Selection Algorithm for this NP-hard problem is improved by using ILS as a hypermutation operator and VNS as a receptor editing operator. The algorithm is tested on a set of 40 benchmark instances from the literature and ten new best solutions are found. Comparisons of the proposed algorithm with several algorithms from the literature (two versions of the Particle Swarm Optimization algorithm, a Differential Evolution algorithm and a Genetic Algorithm) are also reported.

One of the key challenges in robotic bipedal locomotion is finding gait parameters that optimize a desired performance criterion, such as speed, robustness or energy efficiency. Typically, gait optimization requires extensive robot experiments and specific expert knowledge. We propose to apply data-driven machine learning to automate and speed up the process of gait optimization. In particular, we use Bayesian optimization to efficiently find gait parameters that optimize the desired performance metric. As a proof of concept we demonstrate that Bayesian optimization is near-optimal in a classical stochastic optimal control framework. Moreover, we validate our approach to Bayesian gait optimization on a low-cost and fragile real bipedal walker and show that good walking gaits can be efficiently found by Bayesian optimization.

In this paper, we use robust optimization models to formulate the support vector machines (SVMs) with polyhedral uncertainties of the input data points. The formulations in our models are nonlinear and we use Lagrange multipliers to give the first-order optimality conditions and reformulation methods to solve these problems. In addition, we have proposed the models for transductive SVMs with input uncertainties.

Raman microspectroscopy combined with advanced data mining methods are used to demonstrate proof-of-concept for the development of a non-invasive, real-time in vitro assay platform for the classification and characterization of anti-cancer agents. Breast cancer cells were investigated over a 48 h time course of treatment with Paclitaxel. Raman spectroscopic analysis is used with a multiclass One-versus-One Support Vector Machines classification algorithm to classify cell death over a 48 h period. The Fisher-based Feature Selection method provides discriminative features descriptive of the apoptotic process during time-course. Spectral datasets collected at each of the time-points during a separate 48 h 3-point time course study are used as the testing datasets. The features, or spectral peaks, output directly as wavenumbers are correlated to corresponding biochemical species for each time point yielding an analysis of the biochemical compositional changes. Conventional assay methods are employed to validate and confirm results of the Raman spectroscopic analysis.

We consider classification tasks in the regime of scarce labeled training data in high dimensional feature space, where specific expert knowledge is also available. We propose a new hybrid optimization algorithm that solves the elastic-net support vector machine (SVM) through an alternating direction method of multipliers in the first phase, followed by an interior-point method for the classical SVM in the second phase. Both SVM formulations are adapted to knowledge incorporation. Our proposed algorithm addresses the challenges of automatic feature selection, high optimization accuracy, and algorithmic flexibility for taking advantage of prior knowledge. We demonstrate the effectiveness and efficiency of our algorithm and compare it with existing methods on a collection of synthetic and real-world data.

In this paper, we focus on expensive multiobjective optimization problems and propose a method to predict an approximation of the Pareto optimal set using classification of sampled decision vectors as dominated or nondominated. The performance of our method, called EPIC, is demonstrated on a set of benchmark problems used in the multiobjective optimization literature and compared with state-of the-art methods, ParEGO and PAL. The initial results are promising and encourage further research in this direction.

The radiotherapy scheduling problems are hard constrained problems which involve many resources like doctors, patients and machines. These problems have varying structures in different institutions even within the same country. Due to the lack of standard benchmarks, the algorithms proposed in the literature are very specific ones and they are neither easily comparable nor adaptable. In this paper we describe the radiotherapy scheduling problem in different countries in order to identify common components. Our goal is to provide exchangeable benchmarks for this problem. The benchmark generator is available online.

The theory of single upper and lower tolerances for combinatorial minimization problems has been formalized in 2005 for the three types of cost functions sum, product and maximum, and since then shown to be rather useful in creating heuristics and exact algorithms for the Traveling Salesman Problem and related problems. In this paper for these three types of cost functions we extend this theory from single to set tolerances and the related reverse set tolerances. In particular, we characterize specific values of (reverse) set upper and lower tolerances as positive and infinite, and we present a criterion for the uniqueness of an optimal solution to a combinatorial minimization problem. Furthermore, we present formulas or bounds for computing (reverse) set upper and lower tolerances using the relation to their corresponding single tolerance counterparts. Finally, we give formulas for the minimum and maximum (reverse) set upper and lower tolerances using again their corresponding single tolerance counterparts.

The use of orthogonal frequency division multiple access (OFDMA) in Long Term Evolution (LTE) and WiMax cellular systems mitigates downlink intra-cell interference by the use of sub-carriers that are orthogonal to each other. Intercell interference, however, limits the downlink performance of cellular systems. In order to mitigate inter-cell interference, various techniques have been proposed. These techniques are generally divided into static and dynamic techniques. In static techniques, resources allocated for base stations are fixed, while they are adaptively allocated in the dynamic techniques. Although static and dynamic frequency reuse techniques, address the issue of interference, they do not have any mechanism to sustain a disruption or to maintain a allocation in a distributed manner. Hence, the need for distributed frequency allocation. In this paper we briefly discuss the merits of distributed spectrum allocation algorithms for cellular networks and also present an assessment of static interference schemes, and evaluate overall performance of the system in terms of the SINR, and spectral efficiency by adjusting different input parameters. In addition, we study an adaptive frequency reuse algorithm presented by and compare it with the static techniques.

We derive a new existence condition for Hadamard matrices with circulant core, in terms of resultants, Hall polynomials and cyclotomic polynomials. The derivation of this condition is based on a formula for the determinant of a circulant matrix and properties of resultants.