Keywords

1 Introduction

Optimization problems are ubiquitous. They usually arise in fields such as Architecture, Engineering, and Applied Sciences in general [3, 7, 19]. Broadly speaking, this sort of problem requires finding the extremes (maxima or minima, depending on the goal) of a function. The latter, called objective function in this context, involves different variables and models some aspect of interest. For instance, it can represent the cost of manufacturing a product depending on the providers selected and the quantities bought. In this situation, the points sought would be the minima, i.e., the values of the variables resulting in the minimum function value (cost). Alternatively, if the function modeled the strength of the resulting product, the points of interest would presumably be the maxima of the corresponding function. One of the applications in which optimization stands out is model tuning, where the parameters become variables, and the objective function is the comparison between the achieved and desired output [4, 12]. It allows automating processes that used to rely on experts and might be biased by them.

Depending on the objective function, constraints, and variables (e.g., continuous or discrete), there exist different types of optimization problems and methods to address them. For example, linear objective functions and constraints with real bounded variables generally result in problems relatively easy to solve [2, 5]. However, this is not always the case, especially when the functions involved do not exhibit a closed analytical form or do not have exploitable mathematical properties (such as linearity and convexity). Fortunately, there exist methods with fewer problem requirements that can even treat it as a black box. They usually rely on intuitive ideas to obtain acceptable results [10, 15]. These strategies are known as heuristics when they are problem-specific approaches and meta-heuristics of general-purpose. Similarly, the use of randomness serves to enhance the exploration capabilities at the expense of uncertainty [4].

The formulation of the optimization problem that attracts the attention of this work is as follows:

$$\begin{aligned} \begin{aligned}&\underset{x}{\text {minimize}}&f(x) \\&\text {subject to}&L_i \le x_i \le U_i,\; i = 1, \ldots , N. \end{aligned} \end{aligned}$$
(1)

where f is a N-dimensional objective function, i.e., \(f:\mathbb {R}^N \rightarrow \mathbb {R}\). The term x refers to any input in \(\mathbb {R}^N\) belonging to the region \(\left[ L_1, U_1\right] \times \ldots \times \left[ L_N, U_N\right] \), which is known as the search space. As can be seen, the problem only consists of the objective function and the bounds of each variable. There is no extra information about the mathematical properties of f (e.g., convexity, linearity and smoothness). It can only be evaluated in the N-dimensional domain defined as the search space. Thus, this problem can be classified as a black-box optimization one with box constraints [3, 7].

There exist numerous population-based meta-heuristics that can be applied to the problem defined above [1, 15]. Traditional genetic algorithms, Differential Evolution [4, 13], and the Universal Evolutionary Global Optimizer (UEGO) [6, 11] are good examples. However, they have multiple parameters, so they require fine parameter tuning. Teaching-Learning-Based Optimization (TLBO) [4, 14] avoids this problem as a population-based method that only needs the population size and the number of iterations. Regardless, this sort of method will generally need numerous function evaluations to converge due to its haphazard exploration strategy. Another option especially conceived for black-box optimization is DIRECT [7]. In contrast to the previous ones, it is a deterministic method. Furthermore, it only expects the number of function evaluations allowed and a tolerance factor that usually has little effect on its performance [8]. However, its rectangle division mechanism is rigid, and it may require an excessive number of function evaluations for degenerate cases.

This work presents an optimizer that balances the virtual lack of parameters, the use of randomness, and extensive exploration capabilities. To achieve this, it takes inspiration from previous optimization algorithms. The resulting method, called Tangram, defines an exploration procedure that moves from the center of the search space towards its corners. It keeps track of the best result achieved so far but uses that reference to divide the search space into smaller regions according to a deterministic division scheme. The new zones are ultimately explored by a local optimizer known as SASS [9], which is stochastic yet has a robust default configuration. Tangram aims to be effective for low-dimensional problems (less than 20 variables) and to be compatible with low budgets of function evaluations.

The rest of the paper is structured as follows: Sect. 2 describes the proposed method in detail. Section 3 explains the experimentation carried out. Finally, Sect. 4 shows the conclusions and states the future work.

Fig. 1.
figure 1

Normalization of a hypothetical 3D search space.

Full size image

2 Method Description

For a given optimization problem in the form of Eq. 1, the algorithm Tangram only expects as input the number of allowed function evaluations. Like DIRECT, the optimizer sees the search space as an N-dimensional unit hypercube, so it is first scaled accordingly from \(\mathbb {R}^N\) to \(\left[ 0,1\right] ^N\). This strategy simplifies the implementation of the method and avoids issues concerning variables of significantly different scales at local search [16]. This idea is depicted in Fig. 1 for a hypothetical problem in a sub-domain in \(\mathbb {R}^3\), \(\left[ 10, 20\right] \times \left[ 0, 7\right] \times \left[ 1, 3\right] \). The space of solutions remains unaltered.

Again like DIRECT, Tangram starts by evaluating the center of the search space, i.e., \((0.5, \ldots , 0.5)\in \mathbb {R}^N\), which becomes the current result. This process defines its initialization stage, which is shown in Fig. 2a. After that, it compares the budget of function evaluations to the dimensionality of the search space and enters into one of two modes, namely, the standard or the incisive one. Although both keep the same fundamentals, there is a subtle yet significant difference between them. The standard mode is covered first, as it was the only one at preliminary design stages. The local solver, which remains the same, is also explained in detail. Later, the decision criterion and the incisive mode are described in terms of the potential flaws of the standard one.

Fig. 2.
figure 2

Main concepts of Tangram.

Full size image

2.1 Standard Execution Mode

Algorithm 1 outlines Tangram (omitting the selection between modes). As can be seen, the initial steps described above (without the mode selection) are in lines 1 and 2.

figure a

The optimization loop defining the standard mode is between lines 3 and 14. It lasts while there are function evaluations remaining and consists of the following stages:

  • Global Phase (line 4): The local search component, SASS, is launched from the current result to try to improve it. This is the local solver generally used with the aforementioned memetic algorithm, UEGO, and has been chosen because of its effectiveness for different problems. The optimizer is configured so that the maximum step size is equal to the diameter of the search space, i.e., \(\sqrt{N}\). This strategy allows reaching any solution and also comes from the way in which UEGO handles its initial or first-level species. Figure 2b depicts this process starting from the initial point, i.e., the center of the search space, for a hypothetical 2D problem. Notice how SASS attempts several movements, but the current result only changes when a better point is found.

  • Division (lines 5 to 9): Tangram computes and evaluates the midpoint between each corner of the search space and the current result. This part emphasizes the exploration of the search space. It allows the method to escape from local optima and identify new promising regions. It is vaguely inspired in how DIRECT keeps a representing point of every region of the search space. However, the division does not keep the regions strictly isolated. Figure 2c represents this stage graphically extending the previous context. It also serves to explain the name chosen for the proposed optimizer. Namely, if the resulting regions were colored in different colors, they would look like a Tangram, i.e., the widespread Chinese dissection puzzle [18].

  • Local Phase (lines 10 to 12): Tangram launches its local optimizer, SASS, from each of the previous midpoints to improve them. Those having a better value for the objective function are chosen first. By proceeding this way, in case the number of function evaluations allowed is low, the method ensures having explored the most promising regions at least. This aspect is relevant because the optimizer has been conceived for situations in which calling the objective function is computationally demanding. At this stage, in contrast to the global phase, SASS is configured not to take steps bigger than the distance between each starting midpoint and the corner used to define it (line 11). The further the midpoint is from the current global result, the wider initial region it has. Thus, exploration is automatically enhanced while the whole search space always remains virtually covered. Figure 2d summarizes these ideas graphically. Finally, notice that since the local solver updates its current point every time that it finds a better one, the definition of regions is dynamic like in UEGO.

  • Update (line 13): If any of the points found after the division and local searches outperforms the current solution, that point replaces it. Then, the algorithm returns to the global phase and starts to repeat the previous process if there are function evaluations available. This stage is show in Fig. 2e.

After consuming all the function evaluations allowed, Tangram returns the best solution achieved so far (line 15). However, despite being omitted from Algorithm 1, notice that the method registers every evaluation of the objective function. Hence, this situation can be detected at any stage. If that happens, Tangram assigns an infinite value to any new point and tries to finish as soon as possible.

2.2 Local Search Component (SASS)

Regarding the local search component, as introduced, it is SASS, which was initially proposed in [17]. This name is an acronym for Single-Agent Stochastic Search. SASS does not have any special requirement for the objective function apart from being fully defined in the search space. For this reason, it is especially suitable for black-box optimization. It was one of the main reasons why it was chosen for UEGO, and the same criterion has been followed for Tangram.

SASS is a stochastic hill-climber of adaptive step size. It starts at any given point, which is treated as its current local solution, and randomly decides a direction to move. The jump size cannot be greater than a given threshold. As explained, it will be \(\sqrt{N}\) for the global phase and the distance between the midpoint and the corner used to compute it for any local one. However, the jump size is further scaled depending on the number of improving (accepted) and non-improving (discarded) movements.

In practical terms, every movement consists in generating a new candidate solution, \(x'\), according to Eq. (2), where x is the current solution and \(\xi \) is a normally-distributed random vector (perturbation). The standard deviation, \(\sigma \), is globally defined between 1e−5 and 1, starting at the upper bound. Every component has a specific mean or bias factor that is initially set to 0. They form the bias vector, \(b=\left( b_1,\dots ,b_N\right) \). If the movement amplitude (the module of the perturbation), is greater than allowed, \(\xi \) is rescaled by the maximum step size.

$$\begin{aligned} x'=x+\xi \end{aligned}$$
(2)

SASS then computes the objective function at \(x'\). If it is better than the current solution, \(x'\) replaces it, the iteration is considered successful, the bias vector is updated as \(b=0.2b+0.4\xi \), and a new iteration starts. Otherwise, the opposite direction is explored by generating and evaluating a new candidate solution, \(x''=x-\xi \). If it outperforms the current one, \(x''\) replaces it, and the iteration is also considered successful. In this situation, the bias vector is updated as \(b=b-0.4\xi \). However, if neither \(x'\) nor \(x''\) are better than the current solution, the iteration is tagged as failed, and the bias vector is set to \(b=0.5b\). Figure 3 shows the key aspects of an iteration of SASS in Tangram, which forces any perturbation vector to be within a delimited (yet moving) region.

Fig. 3.
figure 3

Depiction of an iteration of SASS.

Full size image

The global standard deviation, \(\sigma \), is doubled after five consecutive successful movements (expansion) or halved after three consecutive discarded ones (contraction), which represents the adaptive nature of SASS. This is the recommended configuration, and it is known to perform well. Besides, within Tangram, SASS will terminate after 32 iterations. This arbitrary threshold is assumed enough to converge to the nearby optima according to previous knowledge on the method when used with UEGO. Nevertheless, varying this local budget would just result in a second parameter to tune.

2.3 Incisive Execution Mode

According to the previous explanation, the first function evaluation is always for the center of the search space. Then, the loop of the standard execution mode starts. Every global phase takes 32 evaluations through SASS. After that, the division requires \(2^N\) function evaluations, one for each new midpoint. Let us think of a problem with \(N=20\), which is the highest dimensionality for a problem expected to be addressed with Tangram. It would be approximately \(1\times 10^6\) evaluations, which is the recommended budget for a robust execution of UEGO. Later, the local phase would end the current iteration after consuming 32*\(2^N\) evaluations, i.e., \(2^{N+5}\).

In this context, if the function evaluation budget is low (less than \(33+2^N\)), Tangram will not even be able to reach the local stage. This means that the local search will have been launched only once. Thus, the candidate solutions competing with the current result will be a subset of midpoints not sharpened by SASS. Accordingly, the probability of having identified a competitive point in the search space is low. The incisive mode of Tangram deals with this problem.

The incisive mode is selected over the standard one when the number of function evaluations allowed is less than \(33+2^N\). This mode maintains the structure of the standard one but has a relevant modification in the division and local phases, which are merged. Namely, instead of generating and evaluating all the midpoints before moving to the local exploration phase, Tangram launches SASS from every new midpoint iteratively. By proceeding this way, the proposed method avoids the lack of local optimization that results in working with non-sharpened points at the expense of not prioritizing the most promising regions.

3 Experimentation and Results

The goals of Tangram are to be effective for low-dimensionality problems, without tuning requirements, and with a low budget of function evaluations. These aims are well aligned with the experimentation described in [3]. Thus, the 20 continuous box-constrained problems proposed in that work, which feature between 1 and 10 variables, have been addressed with Tangram. As the authors say, they are challenging for black-box methods not exploiting any analytical information. The limit of function evaluations has been computed as in the referred paper, i.e., \(30(N+1)\), which is low and makes the test more challenging. It is also compatible with a context where the cost function is computationally demanding (e.g., simulation-based model tuning).

To have an adequate reference, Tangram has been compared to a pure random search (PRS), a plain multi-start configuration of SASS (MSASS), and the population-based optimizer TLBO. The pure random search is expected to be a baseline reference, since any optimizer should be more effective than simply generating and evaluating points. The multi-start SASS is a especially descriptive comparison: Since Tangram can be seen as a rule-based multi-start component linked to SASS, it should serve as a better guide for this local solver rather than simply generating random starts. Finally, TLBO has been included in the comparison due to its fame of being simple to tune and effective [4]. It is also relevant to highlight that both TLBO and MSASS achieved very good results in the model tuning application described in [4], which supports their selection.

All of the optimizers considered have been configured with the same function evaluation limit. This task is more difficult for TLBO, as it depends on a population size and a number of cycles. For this reason, TLBO takes that limit at least but slightly exceeds it in some cases. The development environment used is MATLAB 2020a in Mac OSX (MacBook Pro, Intel i5 2.9 GHz, 8 GB of RAM). Each method has been executed 200 times for each case to handle stochasticity.

Table 1 contains the results of experimentation. More specifically, the first column lists the 20 problems addressed including their name with their dimensionality and optimum value below. The other columns show the results obtained with each optimizer in the form of the average value of the objective function ± the standard deviation below. The cells in bold highlight the best result of the row. As can be seen in the results, the average differs from the theoretical optimum in most cases. Namely, only problems 3, 4, and 5 have a method that virtually offers the best possible value. This situation confirms the challenging nature of the testbeds for this kind of method and the evaluation budget allowed.

In this context, Tangram stands out as the best performing solver, as it offers the best average result for all the instances. In general, the number of function evaluations allows it to run in the standard mode. However, for problems 11, 14, and 15, the incisive mode is selected according to the defined criterion (e.g., for problem 8, the budget is 270, while the threshold is 289, so the incisive mode is activated). Its role is decisive, as the results of the standard mode for instances 11, 14, and 15 would have been 8003.54550 ± 2889.46980, 332.05440 ± 61.81830, and 246.38150 ± 63.87150, respectively. Hence, the predominant position of the proposed optimizer would be lost in those degenerate cases. There is another revealing fact to highlight: MSASS performs worse that Tangram even though they share the same local solver. Thus, the design of Tangram seems effective.

Regarding the other methods, as expected, PRS is the worst option due to its complete lack of search orientation. MSASS and TLBO approximately share the second position, with 12 relative victories for the former and 8 for the latter. Regardless, the differences are small in general, and both methods exhibit particularly bad averages in some problems. See for example problems 7 for MSASS and 12 for TLBO, where they are almost equivalent to PRS.

Table 1. Results of the compared optimizers for the 20 test problems.
Full size table

4 Conclusions and Future Work

In this work, a new algorithm for black-box optimization has been described. The method is virtually parameter-free, as it only expects the number of allowed function evaluations, and aims to be effective for low-dimensionality problems (up to 20 variables). It is expected to be valid for model tuning through numerical optimization. Its name is Tangram, and it combines several ideas from the literature. More specifically, it works in a unitary hypercube and tries to apply a deterministic strategy to define regions, like DIRECT. Besides, its behavior can be self-adapted to adapt the search to best-effort explorations in which the algorithm detects that it will not be able to execute all its steps appropriately. The proposal also uses a local optimizer from the literature, SASS, which is the one usually used within the memetic algorithm UEGO. From this population-based method, Tangram replicates the scheme of making SASS focus on different regions by limiting the steps yet keeping one covering the whole search space. Nevertheless, Tangram avoids the sophisticated management of points as a population in UEGO.

Tangram has been used to address 20 benchmark problems from the literature in a context of few function evaluations allowed. Its performance has been compared to a pure random search, a random multi-start configuration of SASS, and TLBO, a widespread population-based method. Tangram outperforms all of them. Among the appreciated aspects, one of the most descriptive ones is the fact that Tangram performs better than SASS in the multi-start configuration, which supports the design of the proposal. Another interesting idea to highlight from the experimentation is how the adaptive nature of Tangram is effectively able to anticipate the potential flaws of its standard mode and opts for the incisive one instead.

For future work, we will study how to automatically detect the local convergence of SASS to save function evaluations that can be reassigned to other parts of the method. We also intend to increase the number of benchmark problems and the optimizers compared, possibly starting with DIRECT and UEGO.