Analysis of Users’ Requirements for Public Waste Management Services Using Fuzzy Inference

MENDEL — Soft Computing Journal, Volume 29, No.gk, .2+2K#2` 2023, Brno, Czech RepublicX ISSN: 1803-3814 (Printed), 2571-3701 (Online) https://doi.org/10.13164/mendel.2023.k.131 Diagonal Partitioning Strategy Using Bisection of Rectangles and a Novel Sampling Scheme Nabila Guessoum, Lakhdar Chiter  Department of Mathematics, Ferhat-Abbas University of S´etif1, S´etif 19000, Algeria. Fundamental and Numerical Mathematics Laboratory. [email protected], [email protected]  Abstract In this paper, we consider a global optimization problem where the objective function is assumed to be Lipschitz-continuous with an unknown Lipschitz constant. Building upon the recently introduced BIRECT (BIsection of RECTangles) algorithm, we propose a new diagonal partitioning and sampling scheme. Our framework, named BIRECT-V (V for vertices), combines bisection with the sampling of two points. In the initial hyper-rectangle, these points are located at 1/3and 1 along the main diagonal. Unlike most DIRECT-type algorithms, where evaluating the objective function at vertices is not suitable for bisection, our strategy, when combined with bisection, provides more comprehensive information about the objective function. However, the creation of new sampling points may coincide with existing ones at shared vertices, resulting in additional evaluations of the objective function and increasing the number of function evaluations per iteration. To overcome this issue, we propose modifying the original optimization domain to obtain a good approximation of the global solution. Experimental investigations demonstrate that this modification positively impacts the performance of the BIRECT-V algorithm. Our proposal shows promise as a global optimization algorithm compared to the original BIRECT and two popular DIRECT-type algorithms on a set of test problems. It particularly excels at high-dimensional problems. Keywords: Global Optimization, BIRECT Algorithm, Diagonal Partitioning Strategy, Sampling Scheme. Received: 21 August 2023 Accepted: 15 September 2023 Online: 18 September 2023 Published: 20 December 2023 1 Introduction Global optimization methods have long had a prominent position in many fields. They are becoming more popular tools due to the variety and nature of the problems they may be utilized to solve. According to the method used to find the optimum, global optimization approaches can generally be divided into two major categories: deterministic [10,11,40,6] and stochastic methods [19,56]. In black-box optimization cases, the development of derivative-free global optimization algorithms has been forced by the need to optimize various and often increasingly complex problems in practice because analytic information about the objective function is unavailable. In this paper, we consider the global optimization problem of the form min x∈Df(x),(1) where the feasible domain is an n-dimensional hyperrectangle D= [a,b] = {x∈Rn:aj≤xj≤bj, j = 1, . . . , n},a,b∈Rnand the objective function f(x) is usually assumed to be Lipschitzian with maybe unknown Lipschitz constant L, 0 < L < ∞, i.e., |f(x)−f(y)| ≤ L∥x−y∥,x,y∈D. (2) The norm ∥.∥denotes usually the Euclidean norm, but other equivalent norms can also be used [1,29, 30]. The function f(x) is also supposed to be nondifferentiable; therefore, numerical methods using gradient information cannot be used to solve this kind of problem. Various methods have been proposed to solve the optimization problem (1)-(2) using different domain partition schemes (see [10,36,56]). In global optimization, a feasible domain is usually a hyper-rectangle; therefore, most DIRECT-type methods use hyper-rectangular partitions. However, other types of sampling and partitioning schemes may be appropriate to some optimization problems, e.g., simplicial partitioning based on one-dimensional trisection or bisection and sampling at the center (DISIMPL-C[31]) or vertices (DISIMPL-V[30]). Other diagonal sampling schemes ([36,37,39,34,35]) use two points per hyper-rectangle instead of one point; e.g., adaptive diagonal curves (ADC algorithm[37]) use hyper-rectangular partitioning based on one-dimensional trisection and evaluate the objective function at two vertices of the main diagonals. A detailed review of different sampling and partitioning schemes is summarized in [48] and the references given therein. 131 MENDEL — Soft Computing Journal, Volume 29, No.gk, .2+2K#2` 2023, Brno, Czech RepublicX DIRECT (DIvide RECTangles) algorithm developed by Jones[14,12] is one of the most widely used partitioning-based algorithms due to its simplicity, and it only needs one algorithmic parameter ([8,7,4,5,3, 1]. The algorithm is an extension of classical Lipschitz optimization (see, e.g., [29,2,32,38,41]), where the need to know the Lipschitz constant is eliminated. However, DIRECT algorithm may converge slowly if it gets close to the optimum, requiring it to divide incessantly near the location of this optimum. The reason is that hyper-rectangles that are not potentially optimal (having bad function values at their centers) but may contain better function values will be selected in the next iterations. This procedure influences the selection of potentially optimal hyper-rectangles (having better function values), which need to be selected first. Since its introduction, various modifications have been introduced to improve the performance of DIRECT [4,5,8,7,12,13,14,3,21,20,22,23,24,25]. Recently, various DIRECT-type extensions and modifications have been proposed, aiming to improve the selection of potential optimal hyper-rectangles or by using different partitioning techniques leading to even more effective DIRECT-type algorithms [51,52,50,42,43,48,46,44]. The recent papers [47,15,16] provide a good and comprehensive review of techniques in DIRECT-type algorithms. It significantly contributes to the field of derivative-free global optimization and serves as a valuable resource for researchers and practitioners seeking to enhance the efficiency and effectiveness of such algorithms. Contrary to the most DIRECT-type algorithms, which use a central sampling strategy, the use of two points instead of one point in the sampling process, as in many diagonal-type algorithms, may reduce the probability for a hyper-rectangle with the global minimum to have a bad function value since the two (the good point and the bad function value) are in the same hyperrectangle. BIRECT (BIsection of RECTangles) algorithm was initially developed by Paulaviˇcius et al.[27]. The algorithm samples two points (located at 1/3 and 2/3) along a diagonal per hyper-rectangle and uses bisection instead of trisection. Many arguments revealed, in a recent review [13,26], that BIRECT gives very promising results compared to other DIRECT-type algorithms. Since the original BIRECT algorithm was introduced, the authors in [28] suggested two-phase globallybiased extensions from [30] to the BIRECT algorithm called Gb-BIRECT, and a hybridized BIRECT algorithm Gb-BIRMIN is constructed by combining the globally-biased framework and the local optimization. They also developed in [28] a version of BIRECT called BIRECT-l which differs from BIRECTin that only one hyper-rectangle is selected, even if several hyper-rectangles are potentially optimal. This paper introduces a variant of the original BIRECT by modifiying the location of the sampling points. Each hyper-rectangle is described by two sampling points, whose positions on the corresponding diagonal are located at one-third and at the opposite farthest vertex. In contrast to the most DIRECT-type algorithms, where the evaluation of the objective function at vertices is not favorable for bisection, this sampling strategy, combined with bisection, provides a better approximation of the objective function than central-sampling methods. Nevertheless, it is observed that the objective function could be re-evaluated more than twice at some shared vertices, leading to a significant increase in function evaluations. This strategy is typical for diagonal-based algorithms, which produce many unnecessary sampling points of the objective function. Every vertex where the function has been evaluated can belong to up to 2nhyper-rectangles [35,38,18]. Especially the algorithm takes significantly longer than usual to find a solution close to a global optimum. One of the possible suggestions to overcome these drawbacks is to consider a particular vertex database to avoid re-evaluation of the objective function [37]. The function is evaluated at every vertex only once, and then the result is directly retrieved from the database when required [35,38,18]. The second alternative is to group more hyper-rectangles having approximately the same size in the same group, which effectively reduces the set of selected potentially optimal hyperrectangles. Some suggested methods are summarized in [51,48,28,13]. This possibility is not considered in the present paper but can be observed, for example, in the case of BIRECT-Vl, since it selects only one potentially optimal hyper-rectangle from each group. This situation is favorable, especially when a good objective function value attained at the vertex can belong to many (up to 2n) hyper-rectangles. One possibility is to consider an appropriate (tight) Lipschitzian lower bound, since we observed that Eq. 5is much more in favor of BIRECT than of BIRECT-V. Another alternative that seems very attractive is to modify the original optimization domain for some test problems to obtain a good approximation to the global solution. The influence of such a modification on the performance of the BIRECT-V algorithm is as efficient as the number of function evaluations required to get close to a good solution. It is clear that this last alternative does not overcome the situation in a proper way, but at least it helps to reduce considerably the number of function evaluations. Therefore, the main purpose of this paper is to focus on this particular scheme (sampling at vertices) without any additional parameters to the BIRECT-V algorithm framework by investigating this new approach and discussing its advantages and drawbacks. Consequently, the contribution of this paper is summarized as follows: •A new modified BIRECT algorithm is suggested, named BIRECT-V. •A new variation of the BIRECT-V algorithm, called BIRECT-Vl is also introduced. 132 MENDEL — Soft Computing Journal, Volume 29, No.gk, .2+2K#2` 2023, Brno, Czech RepublicX Guessom-g2igHX,gD iagonal Partitioning Strategy Using Bisection of Rectangles and a Novel Sampling Scheme •The new approach incorporates bisection with sampling on diagonal vertices, which is not commonly used in the majority of existing BIRECTtype algorithms. •Numerical Comparison on Test Problems shows the advantages of the approach. •It is shown that a modification in the original domain can have a positive impact on the performance of the BIRECT-V algorithm. •An innovative extension built upon our approach to handle global optimization problems involving Lipschitz continuous functions subject to linear constraints seems to address a challenging and rrelevant problem [49]. The remainder of this paper is organized as follows: In Sect. 2, we outline the working principles of the original BIRECT. This will make more comprehensible the ideas behind the BIRECT-V algorithm to be proposed. A description of the new sampling and partitioning scheme is given in Sect. 2.2. Implementation of the BIRECT-V algorithm along with the other DIRECTtype algorithms is given in Sect. 3. Numerical investigation and comparison with BIRECT,BIRECT-l, and two DIRECTtype algorithms on 54 variants of Hedar test problems [9] is presented in Sect. 3.2. Finally, in Sect. 4, we conclude the paper with some remarks and directions for future research. 2 Materials and Methods In this section we start by giving a description of the principle of the sampling and division strategies retained from the original BIRECT algorithm. Then we introduce our suggested method with emphasis on the sampling strategy. We conclude this section by an illustration of this new scheme. 2.1 From BIRECT to BIRECT-V The original BIRECT (BIsection of RECTangles) algorithm, developed by Paulaviˇcius et al.[27], is based on a diagonal space-partitioning technique and includes two main procedures: sampling on diagonals and using bisection of hyper-rectangles. The algorithm begins by scaling the initial search space Dto the unit hypercube ¯ D, where all the variables are returned. At the initialization step of BIRECT,f(x) is evaluated at two points ′′lower′′ l= (l1, . . . , ln) = (1/3,...,1/3)Tand ′′upper′′ u= (u1, . . . , un) = (2/3, . . . , 2/3)Tlocated on the main diagonal of the normalized domain ¯ D, equidistant between themselves and the endpoints of the diagonal. The hyper-cube is then partitioned into a set of smaller hyper-rectangles and f(x) is evaluated over each hyper-rectangle at two diagonal points by following a specific sampling and partitioning scheme obeying the two following rules. 2.1.1 Selection Rule Let the partition of ¯ Dat iteration kbe defined as Pk={¯ Di:i∈Ik}, where ¯ Di= [ai,bi] = {x∈Rn:li≤x≤ui,∀i∈Ik}, li, ui∈[0,1] and Ikis the set of indices identifying the subsets defining the current partition Pk. At the generic kth iteration, starting from the current partition Pkof ¯ Di, a new partition Pk+1 is obtained by bisecting a set of potentially optimal hyper-rectangles from the previous partition Pk. The identification of a potentially optimal hyper-rectangle is based on the lower bound estimates for f(x) over each hyperrectangle by fixing some rate of change ˜ L > 0 (which has a role analogous to a Lipschitz constant). A hyperrectangle ¯ Dj, j ∈Ik. We call potentially optimal a hyper-rectangle jif ∀i∈Ik, the following inequalities hold min f(lj), f(uj)−˜ Lδj≤min f(li), f(ui)−˜ Lδi,(3) min f(lj), f(uj)−˜ Lδj≤fmin −ε|fmin|,(4) where the measure (distance, size) of the hyperrectangle is given by δi=2 3∥bi−ai∥,(5) ε > 0 is a positive constant, and fmin is the current best known function value. A hyper-rectangle jis potentially optimal if the lower bound for fcomputed by the left-hand side of (3) is optimal for some fixed rate of change ˜ Lamong the hyper-rectangles of the current partition Pk. Inequality (4) ensures guarding against an excessive emphasis on the local search [14]. 2.1.2 Division and Sampling Rule After the inital covering, BIRECT-V moves to the future iterations by partitioning potentially optimal hyperrectangles and evaluating the objective function f(x) at their new sampling points. New sampling points are obtained by adding and subtracting from the previous (old) ones a distance equal to the half-side length of the branching coordinate. This way, old sampled from the previous iterations are re-used in descendant subregions. A vital aspect of the algorithm is how the selected hyper-rectangles ¯ Di,i∈Ikare divided. For every potentially optimal hyper-rectangle the set of the maximum coordinates (edges) is computed, and every potentially optimal hyper-rectangle is bisected (divided in halves of equal size), along the coordinate (branching variable xbr,1≤br ≤n), having the largest side length (di br) and by first considering the coordinate directions with the lowest index j(if more coordinates may be chosen), where function values are more promising, [55]. br = min arg max 1≤j≤n =di j=bi j−ai j,(6) 133 MENDEL — Soft Computing Journal, Volume 29, No.gk, .2+2K#2` 2023, Brno, Czech RepublicX The partitioning process continues until a prescribed number of function evaluations has been performed, or a stopping criterion is satisfied. The best (smaller) found objective function value f(¯ x) over all sampled points of the final partition, and the corresponding generated point ¯ x, provide an approximate solution to the problem. Further details and comprehensive description of the original BIRECT algorithm can be found in Paulavicius et al.[27]. 2.2 Description of the New Sampling Scheme In this subsection, we present the basic idea of the new sampling scheme in a more general setting. An illustration is given in a two-dimensional example in Fig. 1and Fig. 2. Since our new method is based on the original BIRECT algorithm, BIRECT-V follows the same hyperrectangle selection and subdivision procedure, unlike the sampling method which is done in a different way. In the initialization phase, BIRECT-V normalize the search domain to an n-dimensional unit hyper-rectangle ¯ D1 0, and evaluates the objective function f(x) at two different diagonal points: ′′third′′ ti= (ti 1, . . . , ti n) = (1/3,...,1/3)Tand ′′vertex′′ vi= (vi 1, . . . , vi n) = (1,...,1)T. The scaled hyperrectangle is considered as the only trivial selected POH. In the succeeding iterations, POHs are selected and bisected in essentially the same way as BIRECT, with the change that in inequalites (3) and (4), the sampled points liand uiare replaced by ti=liand vi=ui+ 1 3∥bi−ai∥respectively, and using the same measure of the hyper-rectangle given by Eq. (5). Selected POHs are divided with the restriction that only along the coordinate (branching variable xbr,1≤ br ≤n), having the largest side length (di br), and by first considering the coordinate directions with the smallest index j(if more coordinates may be chosen). This restriction guarantees that the hyper-rectangle will reduce on every dimension. Potentially optimal hyper-rectangles are shown in the left-side of Fig. 3, and correspond to the lower-right convex hull of the set of points. Formalizing our sampling and partitioning schemes in a more general case. Suppose that at iteration k, ¯ Di k= [ai,bi] = {x∈¯ D: 0 ≤ai j≤xj≤bi j≤1, j = 1, ..., n, ∀i∈Ik}is a hyper-cube. Since all the variables (xj, j = 1, ..., n) of ¯ Di khave the same side lengths (di j=bi j−ai j,j= 1, ..., n), ¯ Di k is bisected (divided in halves) across the middle point 1 2(ai 1+bi 1) of the coordinate direction with the smallest index (xj, j = 1) into two hyper-rectangles ¯ Di+1 k, and ¯ Di+2 kof equal side lengths (see Fig. 1, iteration 1 for illustration). After ¯ Di kis bisected, the first iteration is performed by sampling two new points from the old ones. The new point ti+2 is obtained by adding or substracting from the old point one third side-length di br/3 to the lower coordinate of the branching variable. Also the new point vi+1 is obtained from the old one by subtracting or adding the whole side length di br, while keeping all the rest of coordinates issued from tiand viunchanged. In the case where ¯ Di kis a hyper-rectangle, new sampled points are obtained, after distinguishing the branching variable (br), by adding or substracting the required side length from the coordinate on which we branch, pursuant the following rule: If ti j< vi j, then ti+2 br =ti br +di br 3, and vi+1 br =vi br −di br,(7) otherwise, i.e., if ti j> vi j, then ti+1 br =ti br −di br 3, and vi+2 br =vi br +di br.(8) The two new points are obtained as follows: ti+2 = (ti 1, . . . , ti br ±di br 3, . . . , ti n) = (ti 1, . . . , ti br ± |bi 1−ai 1| 3, . . . , ti n), and vi+1 = (vi 1, . . . , vi br ±di br, . . . , vi n) = (vi 1, . . . , vi br ± bi 1−ai 1, . . . , vi n). Each descending hyper-rectangle ¯ Di+1 kand ¯ Di+2 kretainss one sampled point tiand vi, respectively from their ancestor ¯ Di k, At the same time, old sampling points are re-used in descending hyper-rectangles as ti+1 =tiand vi+2 =vi. More precisely: ti+1 =ti=ti 1, . . . , ti n = (ai 1+1 3bi 1−ai 1, . . . , ai n+1 3bi n−ai n) = (ai+1 1+2 3bi+1 1−ai+1 1, . . . , ai+1 n+1 3bi+1 n−ai+1 n), and vi+2 =vi=vi 1, . . . , vi n =ai 1+bi 1−ai 1, . . . , ai n+bi n−ai n =ai+2 1+bi+2 1−ai+2 1, . . . , ai+2 n+bi+2 n−ai+2 n. The BIRECT-V algorithm continues in this way by sampling two new points in each potentially optimal hyper-rectangle, by adding and subtracting the required side-length from the old points, and bisecting through the longest coordinate until some stopping rule is satisfied. After subdivision, each rectangle resulting from the previous iteration retains one point from its predecessor. Notice that the sampled points vi+1 and vi+1 in ¯ Di+1 kbelong to the same diagonal (see Fig. 1for illustration). This is a straightforward consequence of Theorem 1 in [27]. The same conclusion holds for hyperrectangle ¯ Di+2 k. 134 MENDEL — Soft Computing Journal, Volume 29, No.gk, .2+2K#2` 2023, Brno, Czech RepublicX Guessoum-g2igHX,gD iagonal Partitioning Strategy Using Bisection of Rectangles and a Novel Sampling Scheme Figure 1: Description of the initialization and the first three iterations used in the new sampling scheme on on the Branin test problem. Each iteration is performed by sampling two new points (blue color) issued from the old ones (red color) and bisecting potentially optimal hyper-rectangles (shown in gray color) along the coordinate (branching variable xbr,1≤br ≤n), having the largest side length (di br, where di j=bi j−ai j, j= 1, ..., n) and by first considering the coordinate directions with the smallest index j(if more coordinates may be chosen). Finally, let us emphasize that, in contrast to the naming convention used in [27] of the sampling points as “lower” (l) and “upper” (u), to make differentiate two points belonging to the same hyper-rectangle, we can assume without any confusion that the new points are affected as “third” tand “vertex” v. In this way, the two points are always identified during all the optimization process even if they are “lower” or “upper”. It is also of importance to stress again, that our new sampling scheme differs in its unique and distinctive way on how new sampled points are created by using different side-lengths, in contrast to direct-type algorithms and diagonal sampling strategies, where they use the same side-lengths. 135 MENDEL — Soft Computing Journal, Volume 29, No.gk, .2+2K#2` 2023, Brno, Czech RepublicX Figure 2: Illustration of selection, sampling and partitioning schemes ranging from iteration 4 to 5 on the Branin test problem. A situation where two adjacent hyper-rectangles share the same vertex. After bisection of the lower-left hyper-rectangle in iteration 4, the new created point fall exactly with the one in the adjacent hyper-rectangle. This point is marked with a circle in iteration 5. 2.2.1 Illustration Let t1= (t1 1, t1 2) = (1/3,1/3) and v1= (v1 1, v1 2) = (1,1)Tdenote two points lying on the main diagonal (see initialization in Fig. 1) of hyper-rectangle ¯ D1 0= [a1,b1]=[a1 1, b1 1]×[a1 2, b1 2]. Without losing generality, we restrict our illustration to two iterations only; the other situations are the same. In (Fig. 1, iteration 2), ¯ D3 2and ¯ D4 2are POHs. For hyper-rectangle ¯ D3 2, as there is only one longest side (coordinate j= 2) with side length d3 2= 1. Therefore using the rule in Eq. 7, the new sampling points t7and v6are expressed as follows: t7=t7 1, t7 2=t3 1, t3 2+d3 2 3=2 3,2 3, v6=v6 1, v6 2=v3 1, v3 2−d3 2= (1,0) . For hyper-rectangle ¯ D4 2, we use the second rule given by Eq. 8. The new sampling points are located at (see Fig. 1, iteration 2): t8=t4 1−d4 1 3, t4 2=t4 1−1 3, t4 2=1 6,2 3, v9=v4 1+d4 1, v4 2=v4 1+ 1, v4 2=1 2,1. However, in Fig. 2, we encounter a situation where two adjacent hyper-rectangles share the same vertex. After bisection of the lower-left hyper-rectangle in iteration 4, the newly created point falls exactly with the one in the adjacent hyper-rectangle. This point is marked with a circle in iteration 4. This situation is shown on the right side of Fig. 3), where we distinguish three sampled points at which the objective function has been evaluated twice at this vertex. Such a difference becomes more pronounced as optimization proceeds. 2.2.2 Main steps of the BIRECT-V Algorithm The BIRECT-V algorithm main steps are shown in Algorithm 1, where the inputs are problem (f), optimization domain (D), and some stopping criteria: required tolerance (ϵpe), the maximal number of function evaluations (Mmax), and the maximal number of iterations (Kmax). BIRECT-V returns the value of the objective function found (fmin), and the point (xmin) as well as the algorithmic performance measures: percent error (pe), number of function evaluations (m), and number of iterations (k) after termination. The BIRECT-V algorithm begins the initialization phase by the normalization of the feasible domain (D), evaluating the objective function (f) at the two first sampling points t1and v1, measuring and setting stopping conditions (see Algorithm 1, lines 2-4). lines 5-21 of Algorithm 1describes the main while loop, which is executed until one of the stopping conditions specified is met. As explained in the previous section (see Subsubsect. 2.2.1), the BIRECT-V algorithm, at the beginning of each iteration, identifies the set of POHs (see Algorithm 1, line 7, excluding steps 7 (high136 MENDEL — Soft Computing Journal, Volume 29, No.gk, .2+2K#2` 2023, Brno, Czech RepublicX Guessoum-g2igHX,gD iagonal Partitioning Strategy Using Bisection of Rectangles and a Novel Sampling Scheme Figure 3: Geometric interpretation of potentially optimal hyper-rectangles using the BIRECT-V algorithm on the Branin test function in the seventh iteration: (right side), POHs correspond to the lower-right convex hull of points marked in blue color (left side). The position of six points (values of f(x)) obtained in BIRECT can be clearly distinguished. We observe three sampled points at which the objective function has been re-evaluated. lighted in magenta color), which are performed only on the BIRECT-Vl algorithm).(see Algorithm 1, line 6), then bisects all POHs ( Algorithm 1, line 11) and creates the new sampling points tiand viof generated hyper-rectangles (see Algorithm 1, line 12). Finally, BIRECT-V found a solution, and the performance measures are returned (see Algorithm 1, line 22). The structure of BIRECT-V is outlined in Algorithm 1. 2.2.3 Convergence Since BIRECT-V is based on the ideas of BIRECT, therefore the convergence of BIRECT-V could be determined as many times as other DIRECT-type algorithms [14,12,8,7], in the sense of the ”everywhere-dense” type of convergence (see[33]). In addition, the continuity of the objective function in the neighborhood of global minima is a sufficient assumption that guarantees convergence. 3 Results and Discussion This section provides a description of the experimental results, their interpretation, and the experimental conclusions. we compare the performance of our newly introduced modification, BIRECT-V, and its variant, called BIRECT-Vl, which differs from BIRECT-V in that, if several rectangles are tied for being potentially optimal, only one of them is selected. with the original BIRECT algorithm, BIRECT-l [27,28], and two other well-known DIRECT-type algorithms [14,12,8,7]. 3.1 Implementation As the BIRECT-V algorithm is based on the original BIRECT algorithm, we use the same measure of the size of the hyper-rectangle. Note that in the DIRECT algorithm, this size is measured by the Euclidean distance from its center to a corner, while in DIRECT-l, it corresponds to the infinity norm, permitting the algorithm to collect more hyperrectangles having the same size. In BIRECT-Vl, the number of potentially hyper-rectangles in each group, to be further divided, is reduced to at most one hyperrectangle. In Table 1are listed the test problems from[9] used in this comparison, which consist in total of 54 global optimization test problems with dimensions varying from n= 2 to n= 10, with the main attributs: problem number, problem name, dimension (n), faisible domain (D), number of local minima, and known minimum (f∗). Note that these problems could also be found in [53], and in a more detailed version in [50] and related up-to-date versions. In our study, we chose to benchmark using the Hedar test set [9] instead of alternatives like the BBOB set and the GKLS generator [16,17]. This choice aligns with the specific objectives and scope of our research. It’s important to emphasize that we are comparing BIRECTv here only with other “pure” DIRECT-type algorithms. Consequently, our primary objective was to explore two distinct strategies: one involving sampling and bisection techniques employed in the new modification of BIRECT, contrasted with the original version of BIRECT,one sampling commonly employed in the majority of DIRECT-type algorithms. Utilizing multiple benchmark sets, we ensure a comprehensive analysis of our method’s performance across various problem domains. This choice allows us to assess our method’s generalizability and robustness by evaluating its performance on a diverse set of optimization problems. Some of these test problems have several variants, e.g. (Bohachevsky,Hartmann,Shekel), while others (Ackley,Dixon and Price,Levy,Rastrigin,Rosenbrock, 137 MENDEL — Soft Computing Journal, Volume 29, No.gk, .2+2K#2` 2023, Brno, Czech RepublicX %,5(&79l iteration: 1 fmin: 4.6082847879 f evals: 2 . . iteration: 50 fmin: 3.2479917988 f evals: 12 . . iteration: 150 fmin: 0.0007342074 f evals: 14 . . iteration: 170 fmin: 0.0002239623 f evals: 4 . . iteration: 188 fmin: 0.0002239623 f evals: 8 iteration: 189 fmin: 0.0002225978 f evals: 10 iteration: 190 fmin: 0.0000152596 f evals: 10 %,5(&79 LWHUDWLRQIPLQIHYDOV . iteration: 50 fmin: 3.2479917988 f evals: 522 iteration: 133 fmin: 0.0042301342 f evals: 2028 iteration: 134 fmin: 0.0040898808 f evals: 1294 iteration: 135 fmin: 0.0039448443 f evals: 2422 iteration: 136 fmin: 0.0037944837 f evals: 2482 iteration: 150 fmin: 0.0007342074 f evals: 1746 . iteration: 189 fmin: 0.0002225978 f evals: 2430 iteration: 190 fmin: 0.0000152596 f evals: 3306 Figure 4: Iteration progress of the BIRECT-Vl algorithm on the left-hand side and BIRECT-V on the right-hand side while solving the Ackley (No. 3, n =10, from Table 5) test problem. Table 1: Key characteristics of the Hedar test problems[9]. Problem Problem Dimension Feasible region No. of local Optimum No. name n D = ([aj, bj], j = 1, . . . , n) minima f∗ 1∗,2∗,3∗Ackley 2, 5, 10 [−15,35]nmultimodal 0.0 4 Beale 2 [−4.5,4.5]2multimodal 0.0 5∗Bohachevsky 1 2 [−100,110]2multimodal 0.0 6∗Bohachevsky 2 2 [−100,110]2multimodal 0.0 7∗Bohachevsky 3 2 [−100,110]2multimodal 0.0 8 Booth 2 [−10,10]2unimodal 0.0 9 Branin 2 [−5,10] ×[10,15] 3 0.39789 10 Colville 4 [−10,10]4multimodal 0.0 11,12,13 Dixon & Price 2, 5, 10 [−10,10]nunimodal 0.0 14 Easom 2 [−100,100]2multimodal −1.0 15 Goldstein & Price 2 [−2,2]24 3.0 16∗Griewank 2 [−600,700]2multimodal 0.0 17 Hartman 3 [0,1]34−3.86278 18 Hartman 6 [0,1]64−3.32237 19 Hump 2 [−5,5]26−1.03163 20,21,22 Levy 2, 5, 10 [−10,10]nmultimodal 0.0 23∗Matyas 2 [−10,15]2unimodal 0.0 24 Michalewics 2 [0, π]22! −1.80130 25 Michalewics 5 [0, π]55! −4.68765 26 Michalewics 10 [0, π]10 10! −9.66015 27 Perm 4 [−4,4]4multimodal 0.0 28,29 Powell 4, 8 [−4,5]nmultimodal 0.0 30 Power Sum 4 [0,4]4multimodal 0.0 31∗,32∗,33∗Rastrigin 2, 5, 10 [−5.12,6.12]nmultimodal 0.0 34,35,36 Rosenbrock 2, 5, 10 [−5,10]nunimodal 0.0 37,38,39∗Schwefel 2, 5, 10 [−500,500]nunimodal 0.0 40 Shekel, m= 5 4 [0,10]45−10.15320 41 Shekel, m= 7 4 [0,10]47−10.40294 42 Shekel, m= 10 4 [0,10]410 −10.53641 43 Shubert 2 [−10,10]2760 −186.73091 44∗,45∗,46∗Sphere 2, 5, 10 [−5.12,6.12]nmultimodal 0.0 47∗,48∗,49∗Sum squares 2, 5, 10 [−10,15]nunimodal 0.0 50 Trid 6 [−36,36]6multimodal −50.0 51 Trid 10 [−100,100]10 multimodal −210.0 52∗,53∗,54∗Zakharov 2, 5, 10 [−5,11]nmultimodal 0.0 138 MENDEL — Soft Computing Journal, Volume 29, No.gk, .2+2K#2` 2023, Brno, Czech RepublicX Guessoum-g2igHX,gD iagonal Partitioning Strategy Using Bisection of Rectangles and a Novel Sampling Scheme Table 2: Preliminary results during the first run of the BIRECT-V algorithm. Problem Optimum BIRECT-Vl BIRECT-V No. f∗f(¯x)f.eval. f(¯x) f.eval. 10.07.42 ×10−5198 7.42 ×10−5342 2 0.0 9.17 ×10−5422 9.17 ×10−53514 3 0.0 9.69 ×10−5984 9.69 ×10−570690 4 0.0 8.77 ×10−5640 8.77 ×10−51034 5 0.0 7.14 ×10−5676 7.14 ×10−5656 6 0.0 5.96 ×10−5692 5.96 ×10−5694 7 0.0 7.58 ×10−5902 7.58 ×10−51062 8 0.0 6.10 ×10−5234 6.10 ×10−5254 9 0.39789 0.39790 656 0.39790 492 10 0.0 9.82 ×10−52320 9.82 ×10−51910 11 0.0 8.92 ×10−5940 5.48 ×10−51432 12 0.0 9.34 ×10−528034 9.36 ×10−523412 13 0.0 8.79 ×10−3>500000 4.73 ×10−4>500000 14 −1.0−0.99999 180 −0.99999 1082 15 3.0 3.00000 28 3.00000 28 16 0.0 5.13 ×10−58288 5.13 ×10−58950 17 −3.86278 −3.86244 200 −3.86244 208 18 −3.32237 −3.32214 542 −3.32214 542 19 −1.03163 −1.03154 202 −1.03154 334 20 0.0 1.44 ×10−5188 1.44 ×10−5226 21 0.0 7.56 ×10−5674 7.56 ×10−51000 22 0.0 9.27 ×10−52082 9.27 ×10−518676 23 0.0 2.71 ×10−5148 2.71 ×10−5208 24 −1.80130 −1.80130 184 −1.80130 314 25 −4.68736 −4.64588 >500000 −4.68732 339818 26 −9.66015 −8.60560 >500000 −7.55568 >500000 27 0.0 0.00000 80890 0.00000 62368 28 0.0 4.59 ×10−52786 4.59 ×10−51678 29 0.0 9.15 ×10−5387440 9.15 ×10−5467200 30 0.0 0.00000 204 0.00000 204 31 0.0 0.00000 14 0.00000 16 32 0.0 0.00000 204 0.00000 210 33 0.0 0.00000 14360 0.00000 14348 34 0.0 9.65 ×10−5698 9.65 ×10−5718 35 0.0 2.41 ×10−52444 2.41 ×10−52972 36 0.0 5.42 ×10−516506 5.42 ×10−539846 37 0.0 5.64 ×10−5446 5.64 ×10−5580 38 0.0 9.49 ×10−563908 9.49 ×10−523022 39 0.0 1.79 ×10−82938 3.42 ×10−5134562 40 −10.15320 −10.15234 6618 −10.15234 5866 41 −10.40294 −10.40201 2298 −10.40201 2604 42 −10.53641 −10.53544 2498 −10.53544 3324 43 −186.73091 −186.72944 806 −186.72944 1684 44 0.0 1.15 ×10−5112 1.15 ×10−5190 45 0.0 2.87 ×10−5392 2.87 ×10−51400 46 0.0 5.74 ×10−51054 5.74 ×10−527566 47 0.0 8.74 ×10−5248 8.74 ×10−5280 48 0.0 3.97 ×10−51354 3.97 ×10−51776 49 0.0 9.35 ×10−53394 9.35 ×10−59244 50 −50.0−49.99511 1402 −49.99511 2112 51 −210.0−209.98223 168432 −209.98155 368312 52 0.0 0.00000 78 0.00000 78 53 0.0 0.00000 22498 0.00000 24150 54 0.0 1.13284 >500000 1.21289 >500000 Average 52485.148 58762.852 Median 921.000 1681.000 Schwefel,Sphere,Sum squares,Zakharov) and can be tested for different dimensionality. Finally, notice that it may occur occasionally that at the initial steps of the algorithm, the sampling is performed near the global minimizer. In this particular situation, the feasible domain was modified in the same way as in[27], i.e., the upper bound was increased. For clarity, the modified test problems are marked with an asterisk. Implementation and comparison of the newly introduced scheme with the original BIRECT together with other DIRECT-type algorithms were performed in the MATLAB programming language, using MATLAB R2016a on an EliteBook with the following hardware settings: Intel Core i5-6300U CPU @ 2.5 GHz, 8 GB of memory, and running on the Windows 10 operating system (64-bit). Potentially optimal hyper-rectangles are identified using modified Graham’s scan algorithm. In our implementation, the output values are rounded up to 10 decimals. A test problem is considered successful if an algorithm returns a value of an objective function that does not exceed 10−4error or a minimizer xmin that achieves a comparable value in [43]. The algorithms were stopped either when the point ¯ x (noted also xmin) was generated such that the following stopping criterion was satisfied: pe =(f(¯ x)−f∗ |f∗|≤10−4, f∗= 0, f(¯ x)≤10−4, f∗= 0,(9) (where f∗is the known global optimum) or when the number of function evaluations exceeds the prescribed limit of 500,000. (The maximum number of iterations was set to 100,000 but usually it is supposed to be unlimited.) The comparison is based on two criteria: the bestfound function value f(¯ x) and the number of function evaluations (f.eval.). For each test problem, the average and median numbers of function evaluations are shown at the bottom of each table. The best number of function evaluations is shown in bold font in Table 5. The number of iterations and the execution time (measured in seconds) are only reported in Tables 2and 3 in the link https://data.mendeley.com/datasets/ x9fpc9w7wh. 3.2 Discussion In this subsection, we discuss the efficiency of the newly introduced BIRECT-V algorithm and compare it with the original BIRECT,BIRECT-l (see [28,27]) and two DIRECT-type algorithms. In Table 2, we report the results obtained by BIRECT-V and BIRECT-Vl when the algorithm is running in the usual way without additional parameters. In Table 3are reported the results when the bestfound objective function value f(¯ x) found by the BIRECT algorithm is used as a known optimal (minimal) value (f∗). In Table 5, are summarized the experimental results for all tested algorithms are summarized and compared in the case where the original domain (D) was modified. Also, the results related to this comparison are presented in Table 4. First, it is easy to observe from Table 2, that our proposed partitioning scheme requires, most often, more function evaluations than in BIRECT and BIRECT-l, 139 MENDEL — Soft Computing Journal, Volume 29, No.gk, .2+2K#2` 2023, Brno, Czech RepublicX [50] Stripinis, L., Paulaviˇ cius, R., and Kudela, J. DIRECTGO: A new DIRECT-type MATLAB toolbox for derivative free global optimization. GitHub (2022). https://github.com/ blockchain-group/DIRECTGO. [51] Stripinis, L., Paulaviˇ cius, R., and ˇ Zilinskas, J. Improved scheme for selection of potentially optimal hyper-rectangles in direct. Optimization Letters 12 (2018), 1699–1712. [52] Stripinis, L., Paulaviˇ cius, R., and ˇ Zilinskas, J. Penalty functions and two-step selection procedure based direct-type algorithm for constrained global optimization. Structural and Multidisciplinary Optimization 59 (2019), 2155–2175. [53] Surjanovic, S., and Bingham, D. Virtual library of simulation experiments: test functions and datasets. Simon Fraser University, Burnaby, BC, Canada, accessed May 13 (2013), 2015. [54] Tsvetkov, E., and Krymov, R. Pure random search with virtual extension of feasible region. Journal of Optimization Theory and Applications 195, 2 (2022), 575–595. [55] Tuy, H., Hoang, T., Hoang, T., Math´ ematicien, V.-n., Hoang, T., and Mathematician, V. Convex analysis and global optimization. Springer, 1998. [56] Zhigljavsky, A., and Zilinskas, A. Stochastic global optimization, vol. 9. Springer Science & Business Media, 2007. 146