Efficient Hill Climber for Constrained Pseudo-Boolean Optimization Problems

Efficient Hill Climber for Constrained Pseudo-Boolean Optimization Problems Francisco Chicano University of Málaga Andalucía Tech, Spain [email protected] Darrell Whitley Colorado State University Fort Collins, CO, USA whitle[email protected].edu Renato Tinós University of São Paulo Riberão Preto, SP, Brazil r[email protected] ABSTRACT Efficient hill climbers have been recently proposed for singleand multi-objective pseudo-Boolean optimization problems. For k-bounded pseudo-Boolean functions where each variable appears in at most a constant number of subfunctions, it has been theoretically proven that the neighborhood of a solution can be explored in constant time. These hill climbers, combined with a high-level exploration strategy, have shown to improve state of the art methods in experimental studies and open the door to the so-called Gray Box Optimization, where part, but not all, of the details of the objective functions are used to better explore the search space. One important limitation of all the previous proposals is that they can only be applied to unconstrained pseudo-Boolean optimization problems. In this work, we address the constrained case for multi-objective k-bounded pseudo-Boolean optimization problems. We find that adding constraints to the pseudo-Boolean problem has a linear computational cost in the hill climber. Keywords Hamming Ball Hill Climber; Local Search; Constraint Handling; Vector Mk Landscapes; Multi-Objective Optimization 1. INTRODUCTION Hill climbing is one base technique used as a component of higher-level search algorithms like Iterated Local Search or Variable Neighborhood Search [7]. A hill climber starts at an initial solution and then searches for an improving move based on a notion of a neighborhood of solutions that are adjacent to the current solution. We focus in this work on Mk landscapes. Mk landscapes, introduced by Whitley [12], are k-bounded pseudo-Boolean optimization problems composed of a linear combination of Msubfunctions, where each subfunction is a pseudoBoolean optimization problem defined over kvariables. This definition is general enough to include NK landscapes, MAXkSAT, as well as spin glass problems. For Mk landscapes, To appear in Genetic and Evolutionary Computation Conference 2016 Whitley and Chen [13] proved that the location of improving moves can be determined in constant time for the Hamming distance 1 neighborhood. Two solutions are neighboring in this neighborhood if they differ in one bit. This result was later generalized by Chicano et al. [3], who proposed a hill climber that explores the solutions contained in a Hamming ball of radius raround a solution in constant time. Goldman et al. [6] combined this so-called Hamming Ball Hill Climber with recombination to achieve globally optimal results on relatively large Adjacent NK Landscape problems (e.g. 10,000 variables). The work of Goldman et al. shows that evolutionary algorithms do not need mutation to find improving moves, although mutation could probably be used to enable a form of restart. In a recent paper [4], the Hamming Ball Hill Climber proposed in [3] was extended to deal with multi-objective problems, where the objective function is given by the so-called vector Mk landscapes. One aspect that is missing in all the previous work related to efficient hill climbers is the constraint handling. None of the previous hill climbers can be applied to constrained optimization problems. However, many optimization problems have constraints. One example that will be revisited later is the knapsack problem [8], whose objective function is an Mk landscape, since it is a linear pseudo-Boolean function in the form Pn i=1 vixi, and its constraint is also based on an Mk landscape (in the form Pn i=1 wixi≤W). It can be argued that constraints can be handled using penalties in the objective function. In the case of (vector) Mk landscapes, however, the non-linearities introduced by the penalties could increase the epistasis degree and the number of variables of the problem, making hill climbers less efficient. In this work, we provide some theoretical results that limit the performance of efficient hill climbers over constrained problems. In particular, it is found that the constant time per move of the previous hill climbers cannot be achieved when constraints are added to the problem. Instead, a linear time per move is possible. We use these theoretical results to propose an efficient hill climber for multi-objective constrained pseudo-Boolean problems. The rest of the paper is organized as follows. In the next section we introduce some background and review the previous results. Section 3 provides the new theoretical results regarding hill climbing in constrained pseudo-Boolean problems and Section 4 proposes a hill climber based on these results. We also analyze the hill climber using some experiments whose results are presented in Section 5. Finally, Section 6 outlines some conclusions and future work. 2. BACKGROUND In constrained multi-objective optimization, there is a vector function f:Bn→Rdto optimize, called the objective function. We will assume, without loss of generality, that all the objectives (components of the vector function) are to be maximized. The constraints of the problem will be given in the form1g(x)≥0, where g:Bn→Rbis a vector function, that will be called constraint function2. That is, a solution is feasible if all the components of the vector function gare nonnegative when evaluated in that solution. This type of constraints does not represent a limitation. Any other equality or inequality constraint can be expressed in the form gi(x)≥0, including those that use strict inequality constraints (>and <)3. The set of feasible solutions of a problem will be denoted by Xg={x∈Bn|g(x)≥0}. Given a vector function f:Bn→Rd, we say that solution x∈Bndominates solution y∈Bn, denoted with xfy, if and only if f(x)≥f(y) and there exists j∈ {1,2,...,d}such that fj(x)> fj(y). When the vector function is clear from the context, we will use instead of f. Observe that we do not restrict the definition of dominance to feasible solutions of a problem, since we will need to consider dominance also between feasible and non-feasible solutions. Furthermore, we will use the concept of dominance using as vector function the constraint function. The Pareto Optimal Set is the set of feasible solutions P that are not dominated by any other feasible solution in Xg: P={x∈Xg|@y∈Xg, y x}.(1) The Pareto Front is the image by fof the Pareto Optimal Set: PF =f(P). Definition 1 (Local Optimum [10]). Given a vector function f:Bn→Rd, a constraint function g:Bn→Rb, and a neighborhood function N:Bn→2Bn, we say that solution x∈Xgis a local optimum if it is not dominated by any other feasible solution in its neighborhood: @y∈N(x)∩ Xg, y x. In this work we focus our attention to problems where the objective and constraint functions have k-bounded epistasis, that is, their components are Mk Landscapes [12]. These vector functions have been recently called vector Mk landscapes and are defined as follows. Definition 2 (Vector Mk Landscape [4]). Given two constants kand d, a vector Mk Landscape f:Bn→Rd is a d-dimensional vector pseudo-Boolean function defined over Bnwhose components are Mk Landscapes. That is, each component fican be written as a sum of misubfunctions, each one depending at most on kinput variables: fi(x) = mi X l=1 f(l) i(x)for 1≤i≤d,(2) where the subfunctions f(l) idepend on kcomponents of x. Figure 1(a) shows a multi-objective constraint pseudoBoolean problem with d= 2 objective functions and b= 1 1The relational operators applied to vectors will mean that each component must fulfill the inequality. 2We will use boldface to denote vectors in Rdor Rb, such as f, but we will use normal weight for vectors in Bn, like x. 3This is a consequence of the finite search space. x1x2x3x4x5 f(1) 1f(1) 2f(2) 1f(2) 2f(3) 1 g(1) 1g(2) 1g(3) 1 (a) Vector Mk Landscape x1x2 x3 x4 x5 (b) Co-occurrence graph Figure 1: A multi-objective constrained pseudoBoolean problem with k= 2,n= 5 variables, d= 2 objectives and b= 1 constraint (top) and its corresponding co-occurrence graph (bottom). constraint function. The first objective function, f1, can be written as the sum of 3 subfunctions, f(1) 1to f(3) 1, shown with white rectangles. The second component function, f2, can be written as the sum of 2 subfunctions, f(1) 2and f(2) 2, shown with blue (grey) rectangles. Finally, the constraint g1can be written as the sum of 3 subfunctions, g(1) 1to g(3) 1, and is shown with circles in the figure. All the subfunctions depend at most on k= 2 variables. Considering only vector Mk landscapes for the objective and constraint functions is not a limitation, since every pseudo-Boolean function that can be expressed in algebraic form using polynomial space can be transformed in polynomial time into a quadratic (k= 2) pseudo-Boolean function [11]. An important tool for the forthcoming analysis is the coocurrence graph. Definition 3 (Co-ocurrence Graph [5]). Given an objective function f:Bn→Rdand a constraint function g:Bn→Rb, the co-occurrence graph is G= (V, E), where Vis the set of Boolean variables and Econtains all the pairs of variables (xj1, xj2)that co-occur (both variables are arguments) in a subfunction of the objective or the constraint function. In Figure 1(b) we show the variable co-occurrence graph of the vector Mk Landscape of Figure 1(a). Amove in Bncan be characterized by a binary string v∈Bnhaving 1 in all the bits that change in the solution. The Score of a move, has been previously defined as the increment in the objective function when that move is taken. Definition 4 (Score). For v, x ∈Bn, and a vector function f:Bn→Rd, we denote the Score of xwith respect to move vfor function fas S(f) v(x), defined as follows: S(f) v(x) = f(x⊕v)−f(x),(3) where ⊕is the exclusive OR bitwise operation. When constraints are considered, we also need to track where feasible solutions are, and Scores of the contraint function will also be useful to efficiently track them. For this reason we decorate the notation for a Score with the function the Score is referred to (see Definition 4) and we distinguish between the objective Score,S(f), and the constraint Score,S(g). If a result holds for both we will omit the vector function. 2.1 Previous Results There are some previous results for Multi-Objective pseudoBoolean problems that can be easily adapted to the case of constrained multi-objective problems without providing a proof. We review these results in this subsection. In [4] it was found that some Scores can be written as a sum of other Scores. Proposition 1 (from [4]). Let v1, v2∈Bnbe two moves such that4v1∩v2=∅and variables in v1do not co-occur with variables in v2, that is, the subfunctions where variables in v1appear and the ones where variables in v2appear are disjoint. Then, the Score function Sv1∪v2(x)can be written as: Sv1∪v2(x) = Sv1(x) + Sv2(x).(4) When v1, v2∈Bnare two moves fulfilling the previous proposition, we will say that v1and v2do not interact. If such a decomposition is not possible we will say that v1and v2interact. For example, in the vector Mk Landscape of Figure 1 the Score S1,3,4can be written as the sum of the Score S1and S3,4, where we used i1, i2, ... to denote the binary string having 1 in positions i1, i2, . . ., and the rest set to 0. That is, 3,4 and 1 do not interact. One important consequence of this result is that there is no need to store all the Scores in memory to have complete information of the influence that the moves in a Hamming ball of radius rhave. Only the Scores defined as Mr={v∈Bn|1≤ |v| ≤ rand G[v] is connected},(5) need to be stored. In the previous expression, Gis the cooccurrence graph of the problem and G[v] is the subgraph of Ginduced by the set of vertices v. If all the variables appear in at most a constant number of subfunctions c, the number of Scores to store in memory was proven to be Θ(n(3ck)r). Although the original proof is for unconstrained multi-objective problems, it is still true if we add constraints, since the only difference with the unconstrained case is that the variables could appear in more subfunctions (the ones of the constraint function). Another consequence of Proposition 1 is the constant time required to update the Scores in one move. This time is O(b(k)|t|(3ck)r+1), where b(k) is a bound on the time required to evaluate any subfunction and |t|is the number of bits flipped in the move. The efficient hill climbers in the previous work [13, 14, 3, 4] only explore the moves in Mrto identify improving moves. In the multi-objective case it was found that it is not always possible to deduce the presence or absence of a move in the Hamming ball of radius rdominating the current solution, unless one exists in Mr. These type of moves were called strong improving moves. The fact that the objective function is a vector and not a scalar has to do with this. Under some conditions, however, it is possible to 4Abuse of notation: we will interpret moves as binary strings and sets of variables to flip. certify that no strong improving move exists in the ball. In particular: Proposition 2 (from [4]). Let f:Bn→Rdbe a vector Mk Landscape, and w∈Rdad-dimensional weight vector with w>0. If there exists a strong improving move in a ball of radius raround solution x, then there exists v∈Mr such that w·Sv(x)>0. The moves where w·Sv(x)>0 is true are called wimproving moves. The previous result was the basis of a hill climber that first takes all the strong improving moves in Mr and, if none exists, it takes the w-improving moves. If no w-improving move exists the algorithm stops, since there is no strong improving move in the Hamming ball. Taking wimproving moves does not guarantee that a strong improving move in the Hamming ball of the original solution will be reached. But probably it is the best strategy a hill climber can use to reach a strong improving move (if it exists) in constant time per move. We will see in Section 3 that something similar occurs with the feasible moves. And we will need to define the concept of w-feasible move. 3. CONSTRAINED PROBLEMS We have seen in the previous section that when the number of subfunctions each variable appears in is bounded by a constant, all the Scores (either objective or constraint) can be updated in constant time. The strong improving and w-improving moves can also be identified in constant time, since the value of an objective Score is enough to determine its category. However, the classification of the moves as feasible or unfeasible, requires more than constant time. The feasibility of a move vdoes not only depend on the contraint Score S(g) v(x), but also on g(x). A move vis feasible in a solution xwhen g(x) + S(g) v(x)≥0. The value of g(x) could change, in general, after every move. Thus, even if the contraint Score S(g) v(x) does not change for move v, the feasibility of move vcould change. This means that we need to re-evaluate the feasibility of each move every time g(x) changes. Since the number of moves whose Scores are stored in memory is Θ(n), this is also the worst case time required to re-classify the moves as feasible or unfeasible. We could use a complex data structure to keep track of which moves need to be re-classified and which not5. However, the next Theorem proves that, in the worst case, the time required to re-classify moves is Θ(n). Theorem 1. Let x, y ∈Bnbe two neighboring solutions of a multi-objective constrained Pseudo-Boolean problem and Mrthe set of moves whose Scores are stored in memory. Let us assume that |Mr|= Θ(n). The number of moves feasible in xthat are unfeasible in ycould be Θ(n)in the worst case. Proof. In order to prove this, we only need to find a constrained pseudo-Boolean problem with |Mr|= Θ(n) where this could happen. Let’s use the knapsack problem [8], which consists in maximizing the sum of the value of a set of items with the constraint that the sum of the weights of the items 5For example, if g(x) has increased in all the components, then the constraint Scores with S(g) v(x)≥0 stay in the same class. does not exceed a maximum capacity (of the knapsack). Let us consider only the case when r= 1. In this case all the n moves have their Scores stored in memory. Let us assume that the weight of the heaviest item is the maximum capacity of the knapsack. Let solution x= 0 represent an empty knapsack. In xall the order-1 moves are feasible, since any item can be introduced in the knapsack without exceeding the capacity. Let us say that solution yis the one where the heaviest item is introduced in the knapsack. It is clear that yis a neighbor of xand the Hamming distance between both solutions is 1. In solution y, however, all moves are unfeasible, except the one that leads to solution x= 0 (empty knapsack). Thus, the number of moves feasible in x and unfeasible in the neighboring solution yis n−1. The previous result implies that hill climbers considering constraints require O(n) time per move, in contrast to the O(1) time per move when there is no constraint. Now we address the identification of feasible moves in the ball. The next theorem proves that an analysis of the moves in Mr provides some information about the existence of feasible moves in the ball. Theorem 2. Let x∈Bnbe a feasible solution of a multiobjective constrained pseudo-Boolean problem, that is, x∈ Xg. If there is a feasible move in the Hamming ball of radius raround x, then, there must exist a move vin Mrfor which w·g(x⊕v)≥0, for any w>0. Proof. Let us say that vis a feasible move in the Hamming ball of radius r. Then, by Proposition 1, there exist moves v1, v2,...vj∈Mrsuch that S(g) v(x) = Pj l=1 S(g) vl(x). Since vis feasible and all w>0, we have: w·(g(x) + S(g) v(x)) = w·g(x) + j X l=1 w·S(g) vl(x)≥0.(6) Due to the feasibility of xwe have w·g(x)≥0, and adding j−1 times this value to (6) we obtain: j X l=1 w·g(x) + S(g) vl(x)≥0.(7) For the previous expression to be nonnegative, there must be a vlwith 1 ≤l≤jsuch that w·(g(x)+S(g) vl(x)) ≥0. A move vwith w·g(x⊕v)≥0 will be called w-feasible. The previous result allows us to efficiently identify the case in which no feasible solution exists around the current solution. In that case, none of the stored moves will be wfeasible. However, if there is a w-feasible move in Mrthat is not feasible, we cannot ensure that a feasible move exists in the Hamming ball of radius r. In that case, the only computationally efficient decision a hill climber can take is to enter the unfeasible region taking an unfeasible, but wfeasible, move. Unfortunately, when the current solution is unfeasible, identifying a feasible move or prove that none exists in the Hamming ball of radius rseems to be not much more efficient than an exhaustive exploration of the Hamming ball. Conjecture 1. Given a multi-objective constrained pseudo-Boolean optimization problem, and x∈Bnan unfeasible solution to the problem (x /∈Xg), any algorithm to identify a feasible move in the Hamming ball of radius raround xor to confirm that such a move does not exist runs in Ω(nr)time in the worst case, which is the time required to enumerate the Hamming ball. In order to support this conjecture, let us first introduce the Move Interaction Graph. Definition 5 (Move Interaction Graph). Given a multi-objective constrained pseudo-Boolean optimization problem and a set of moves M, the Move Interaction Graph is defined as GM= (M, EM), where the vertices are the moves in Mand an edge exists between v1and v2if the moves v1 and v2interact with each other, that is, they share a variable, or they have variables that interact. 45 12 23 2 3 5 4 1 2434 Figure 2: Move Interaction Graph of M2for the multi-objective constrained pseudo-Boolean problem of Figure 1. . Figure 2 shows the Move Interaction Graph for the set M2associated to the multi-objective constrained pseudoBoolean problem of Figure 1. The numbers in the nodes are the bits flipped in each move. Observe that the five second order moves of M2form a complete graph (joined by dotted lines). The subgraph containing only the order-1 moves coincides with the variable co-occurence graph of Figure 1(b) (joined by solid lines in Figure 2). The rest of edges (dashed lines) correspond to interactions between order-1 and order2 moves. According to Proposition 1, the Score of a move can be decomposed if and only if the move can be described as the union of two moves that do not interact. We can apply the argument the other way around. Joining a set of moves that do not interact with each other, it is possible to create a higher-order move whose Score can be computed as the sum of the Scores of the component moves. Sets of moves that do not interact are independent sets6of a Move Interaction Graph. By definition of Mr, the independent sets of GMrcover all the moves in the Hamming ball of radius r. In other words, any move in the Hamming ball can be expressed as an independent set of GMr. But there are also independent sets in GMrthat correspond to moves outside the ball. 6In a graph, an independent set is a subset of vertices where no pair is adjacent. Let us consider the case in which the constraint function g is 1-dimensional. Let us weigh each move vin GMrwith its corresponding constraint Score S(g) v(x). If xis unfeasible, g(x)<0. A feasible move, v, in the Hamming ball must fulfill g(x) + S(g) v(x)≥0, or equivalently, S(g) v(x)≥ −g(x). Observe that −g(x)>0. Finding such a move is equivalent to finding an independent set in GMrsuch that the sum of weights is greater than or equal to −g(x). Since an independent set of a graph is a clique in the complementary graph, the problem we are trying to solve is the decision problem related to the maximum weighted clique problem, which is NP-hard. If we assume that gcan only take integer values and the constraint Score of all the moves are, by chance, 1, the problem is an instance of the k-clique problem, which is also NP-hard. We know, however, that finding a feasible move can be solved in Θ(nr) by exploring the Hamming ball. Thus, the particular instances of the maximum weighted clique problem we are solving are easier to solve than a general instance. An important question arises. Could we exploit some particular feature of the Move Interaction Graph to reduce the computation time below Θ(nr)? We have no answer to this question yet and we defer an answer to future work. But the previous argument makes us pessimistic. 4. A HILL CLIMBER FOR CONSTRAINED PROBLEMS We have now all the theoretical ingredients to build an efficient hill climber for multi-objective constrained pseudoBoolean problems. We assume that there is a high-level algorithm that runs the hill climber and provides the weight vector w, which determines the direction of exploration in the objective space. We defer to future work the problem of finding an appropriate weight vector. We would like our hill climber to be able to identify feasible improving moves in the Hamming ball and stop only when no feasible improving move exists. Conjecture 1, however, prevents us from doing this efficiently. We will preserve efficiency and relax the identification requirement. The hill climber is shown in Algorithm 1. Let us assume that the hill climber starts in a feasible solution. Then, it first explores the feasible region taking w-improving moves while it is possible. This is the role of exploreFeasibleRegion, which is detailed in Algorithm 2. This procedure first takes a feasible strong improving move if one exist (Line 3) or a feasible w-improving (and not strong improving) move otherwise (Line 5). In this case, it reports the solution to the high-level algorithm using the report procedure, since it could be one of the non-dominated solutions provided by the hill climber7. The procedure report should add the reported solution to an external set of non-dominated solutions. This set should be managed by the high-level algorithm invoking the hill climber. The exploreFeasibleRegion procedure finishes when there is no feasible w-improving move in Mr. We can distinguish three possible scenarios here. It could happen that there is no w-improving move (either feasible or unfeasible) in Mr. Then, by Proposition 2 we can certify that no improving solution exists in the Hamming ball, and, in particular, no feasible improving move. In that case, the hill climber 7If a strong improving move is taken, the starting solution is clearly a dominated solution. stops in Line 5 of Algorithm 1. It can also happen that there is no feasible move in Mr. Since we are in a feasible solution, we can randomly select a w∗vector and apply Theorem 2 to check if we can discard the existence of feasible solutions in the Hamming ball. This is the goal of Line 8. Observe that it is very unlikely that this check is true, since it requires a solution to be feasible in the middle of a ball of unfeasible solutions. Anyway, with an appropriate structure this check requires only constant time. The third scenario is a mix of unfeasible and feasible but not w-improving moves in Mr. In this case, feasible improving moves of higher order could exist in the ball and could be found joining several moves in Mr. Thus, we should continue with the exploration. This exploration can be done in two ways: we could take feasible disimproving moves or unfeasible moves in Mr. We decided to explore the unfeasible moves. Two main reasons support our decision. First, it could happen that only unfeasible moves exist in Mrwhile feasible moves exist in the Hamming ball. Thus, exploring unfeasible moves is something the hill climber should be prepared for, anyway. Second, we do not want the hill climber to cycle (return to a previously explored solution). During the exploration of the feasible region, cycling is avoided because only strong improving or w-improving moves are considered (notice the > operator in Lines 3 and 5). If we allow the hill climber to take disimproving moves, there is no easy way to avoid cycling. Thus, if the hill climber finds that w∗-feasible moves exist in Mrit selects one of such moves in Line 12. Otherwise, it selects an unfeasible (and not w∗-feasible) move in Line 14 (at least one unfeasible w-improving move must exist if the flow reaches this line). Then, it stores the last visited feasible move in variable y(Line 16) and continues the search in the unfeasible region calling the exploreUnfeasibleRegion procedure, which is detailed in Algorithm 3. According to Conjecture 1, we cannot efficiently determine the presence or absence of feasible moves while the hill climber is exploring the unfeasible region. One efficient option, however, is to direct the search to find a feasible solution. This is what Algorithm 3 does. It tries to maximize the constraint function gin the direction of w∗with the hope that it will enter again the feasible region. This exploration is done taking first the strong improving moves for g (Line 6) and the w∗-improving moves if no strong improving move exists (Line 8). When feasible moves appear in Mr during this exploration, only those that w-improve the last feasible solution, y, are taken. The reason is to avoid cycling. Here again, the algorithm selects first a feasible move strong improving y(Line 13) if one exists, or a feasible move wimproving yin second place (Line 15). Then, the algorithm enters the feasible region and runs again the exploreFeasibleRegion procedure. If no improving move exists for g in the Hamming ball of radius raround an unfeasible solution, the algorithm stops in Line 2. Observe that, in this case, a feasible move could exist in the Hamming ball. This solution, if it exists, does not w∗-improves the current one and must be the union of several moves in Mr. This is the only scenario in which the hill climber could stop without identifying a feasible improving move in Hamming ball of radius r. But, as we announced above, we traded accuracy by efficiency in this case. Although we assumed that a feasible solution is provided to the hill climber, it is not difficult to modify it to start in an unfeasible solution. The only thing to do is to run explore- Algorithm 1 Hill Climber. Input: Scores vector S, weight vector w, initial feasible solution x 1: S←computeScores(x); 2: while true do 3: exploreFeasibleRegion(S,w,x) 4: if ∀v∈Mr,w·S(f) v(x)≤0then 5: stop algorithm 6: end if 7: chose a weight vector w∗>0 randomly 8: if ∀v∈Mr,w∗·g(x⊕v)<0then 9: stop algorithm 10: end if 11: if ∃v∈Mr,w∗·g(x⊕v)≥0, x ⊕v /∈Xgthen 12: t←pick({v∈Mr|w∗·g(x⊕v)≥0, x ⊕v /∈Xg}) 13: else 14: t←pick({v∈Mr|x⊕v /∈Xg}) 15: end if 16: y←x 17: move(S,x,t) 18: exploreUnfeasibleRegion(S,w,w∗,x,y) 19: end while Algorithm 2 Procedure exploreFeasibleRegion. Input: Scores vector S, weight vector w, initial solution x 1: while ∃v∈Mr,w·S(f) v(x)>0, x⊕v∈Xgdo 2: if ∃v∈Mr,S(f) v(x)>0, x⊕v∈Xgthen 3: t←pick({v∈Mr|S(f) v(x)>0, x ⊕v∈Xg}) 4: else 5: t←pick({v∈Mr|w·S(f) v(x)>0, x ⊕v∈Xg}) 6: report(x); 7: end if 8: move(S,x,t) 9: end while 10: report(x); Algorithm 3 Procedure exploreUnfeasibleRegion. Input: Scores vector S, weight vector w, weight vector w∗, initial solution x, last feasible solution y 1: while ∀v∈Mr,x⊕v /∈Xg∨w·f(x⊕v)≤w·f(y)do 2: if ∀v∈Mr,w∗·S(g) v(x)≤0then 3: stop algorithm 4: end if 5: if ∃v∈Mr,S(g) v(x)>0then 6: t←pick({v∈Mr|S(g) v(x)>0}) 7: else 8: t←pick({v∈Mr|w∗·S(g) v(x)>0}) 9: end if 10: move(S,x,t) 11: end while 12: if ∃v∈Mr,x⊕v∈Xg,f(x⊕v)>f(y)then 13: t←pick({v∈Mr|f(x⊕v)>f(y), x ⊕v∈Xg}) 14: else 15: t←pick({v∈Mr|w·f(x⊕v)>w·f(y), x⊕v∈Xg}) 16: end if 17: move(S,x,t) UnfeasibleRegion first with no previous feasible solution y. This procedure should try to enter the feasible region and, once a feasible solution is found, the hill climber runs in the way described above. 5. EXPERIMENTAL RESULTS In order to check the performance of the proposed hill climber, we implemented a simple Multi-Start Hill Climber algorithm that generates a feasible random solution, a weight vector wand, then, runs Algorithm 1. These three steps are iterated until a time limit of 1 minute is reached. Our implementation tries to avoid the re-evaluation of the feasibility of moves when all of them are in the feasible region. In order to do this, it keeps the minimum value of the constraint Scores and updates it when the Scores are changed (in constant time). It then checks if the minimum plus the current constraint value is nonnegative. If this is the case, it can certify in constant time that all moves stay in the feasible region and no re-classification of moves occurs (which is computationally costly). Thus, for unconstrained or slightly constrained problems, it recovers the constant time per move that previous work achieved. The machine used in all the experiments has an Intel Core 2 Quad CPU (Q9400) at 2.7 GHz, 3GB of memory and Ubuntu 14.04 LTS. Only one core of the Processor is used. The algorithm was implemented in Java 1.6 and the source code is publicly available in Github8. We used a constrained version of MNK Landscapes [1] as benchmark functions. An MNK Landscape is a vector Mk Landscape where all mi=Nfor all 1 ≤i≤dand each subfunction f(l) idepends on xiand other Kmore variables (thus, k=K+ 1). In our experiments K= 3. The subfunctions f(l) iand g(l) iwere randomly generated using integer numbers in the ranges [-49, 50] and [-50, 49]. The sum of subfunctions was not divided by N9. The ranges of values used for the subfunctions codomain were chosen in such a way that the fraction of unfeasible solutions is small in one case (for range [-49, 50]) and large in the other. This way we can compare what happens in slightly and highly constrained problems. Each component fiand gican be considered a shifted NKq Landscape [2]. We also focused on the adjacent model of NKq Landscape, where the variables each subfunction depends on are consecutive, that is, xi, xi+1,...,xi+K. This ensures that the number of subfunctions a given variable appears in is bounded by a constant and the theoretical results of Sections 2 and 3 apply. 5.1 Runtime In this first experiment we measure the time per move of our hill climber. This experiment will provide a concrete value for the wall clock time the hill climber requires, although this value depends on the hardware and the programming skills of the developer. Before running the hill climber, it is necessary to run a problem-dependent initialization procedure, where the Scores to be stored in memory are determined. This procedure is run only once per problem instance and, for this reason, we did not take it into 8https://github.com/jfrchicanog/EfficientHillClimbers in branch constrained-multiobjective 9This is different from the original MNK Landscapes, where real values between 0 and 1 are used and the sum of subfunctions is normalized dividing it by N. However, we want to avoid floating-point inaccuracy problems. account to compute the time per move. In our experiments this initialization procedure required between 138 and 6,308 milliseconds. The rest of the time required by the multistart hill climber is divided by the number of moves taken and reported as average time per move. Figure 3 shows the average time per move in microseconds for the multi-start hill climber solving constrained MNK Landscapes, where Nvaries from 10,000 to 100,000, the range of values for the subfunctions codomain is [−49,50], the number of objectives is d= 1 and d= 2, the number of constraints is b= 1 and b= 2, and the exploration radius r varies from 1 to 3. These instances are slightly constrained with around 2% of the search space being unfeasible10. We performed 30 independent runs of the algorithm for each configuration, and the results are the average of these 30 runs. 0 200 400 600 800 1000 1200 1400 1600 10 20 30 40 50 60 70 80 90 100 Average time per move (microseconds) N (number of variables in thousands) r=1, d=1, b=1 r=1, d=2, b=1 r=1, d=1, b=2 r=1, d=2, b=2 r=2, d=1, b=1 r=2, d=2, b=1 r=2, d=1, b=2 r=2, d=2, b=2 r=3, d=1, b=1 r=3, d=2, b=1 r=3, d=1, b=2 r=3, d=2, b=2 Figure 3: Average time per move in microseconds for the Multi-Start Hill Climber based on Algorithm 1 for constrained MNK Landscapes with d= 1,2,b= 1,2,N= 10,000 to 100,000, subfunctions codomain [−49,50], and r= 1 to 3. We can observe an almost constant time per move as Nincreases. Since this is a slightly constrained instance, the hill climber explores the feasible region most of the time, where the implementation trick mentioned above prevents the reclassification of all the moves, which takes linear time. We also observe that the radius of exploration has the highest influence on the time. This time is proportional to (3ck)r(see Section 2.1), but kis fixed in this experiment (k=K+1 = 4). Thus, only the number of objectives d, the number of constraints b, and the radius rexternally affect the time. The objectives and constraints affect the value of c, in particular, c= (K+ 1)(d+b). This expression appears in the base of (3ck)r, but ris in the exponent. This explains why rhas the highest influence. On the other hand, since the sum d+binfluences c, the difference between d= 1, c = 2 and d= 2, c = 1 is small in Figure 3. In Figure 4 we show the average time per move (in microseconds) obtained by the multi-start hill climber solving a highly constrained MNK Landscape. The subfunctions codomain here is [−50,49] and Nvaries from 1,000 to 10,000. There is only one constraint and two objectives (b= 1, d= 2). The fraction of unfeasible solutions in this case is around 80%. 10This is an estimation computed as the fraction of unfeasible solutions obtained after generating random solutions. 0 2000 4000 6000 8000 10000 12000 14000 16000 1 2 3 4 5 6 7 8 9 10 Average time per move (microseconds) N (number of variables in thousands) r=1 r=2 r=3 Figure 4: Average time per move in microseconds for the Multi-Start Hill Climber based on Algorithm 1 for constrained MNK Landscapes with d= 2, b= 1,N= 1,000 to 10,000, subfunctions codomain [−50,49], and r= 1 to 3. In this case, we can appreciate a clear linear increase in the time per move as Nincreases. Observe that the time per move in this figure is higher than the time per move in Figure 3, even when the search space is smaller (Nis 10 times smaller). The reason is that the hill climber enters the unfeasible region very often and it needs to re-classify all the moves almost after every move, which takes linear time. 5.2 Quality of the Solutions Exploring larger neighborhoods allows the hill climber to jump to better solutions but it also requires more time per move. Thus, increasing rdoes not necessarily improve the quality of the solutions when time is the stopping criterion. For each problem instance, there is a value of rfor which the quality of the solutions is maximum. We will investigate here this maximum for the problems we are solving. In Figure 5 we show the average value of the best solution found for the single-objective slightly constrained instances (d= 1). We can observe that the quality of the solutions increases as rdoes. This means that the optimum value for ris 3 or higher in this case. We can also observe how the number of constraints seems not to affect the quality of the solutions in this case and the two lines are overlapped. The number of constraints must certainly have an influence in the quality of the solutions found by the hill climber. But this influence is negligible in slightly constrained problems like these ones. We now repeat the analysis for the bi-objective instances (d= 2) using the 50%-empirical attainment surfaces11 to compare the fronts obtained when ris changed. In Figures 6(a) and 6(b) we show 50%-EAS for instances with N= 10,000 and N= 50,000, constrained by b= 1 and b= 2 functions, respectively. In this case we notice that the 50%-EAS obtained with r= 2 always dominates the one obtained with r= 1 (this happens also in the instances that are not shown). However, the 50%-EAS obtained for 11The 50%-empirical attainment surface (50%-EAS) limits the region in the objective space that is dominated by half the runs of the algorithm. It generalizes the concept of median to the multi-objective case (see [9] for more details). 0 500000 1e+06 1.5e+06 2e+06 2.5e+06 3e+06 10 20 30 40 50 60 70 80 90 100 Average quality of best found solution N (number of variables in thousands) r=1, b=1 r=1, b=2 r=2, b=1 r=2, b=2 r=3, b=1 r=3, b=2 Figure 5: Average (over 30 runs) solution quality of the best solution found by the Multi-Start Hill Climber based on Algorithm 1 for a MNK Landscape with d= 1,b= 1,2, subfunctions codomain [−49,50],N= 10,000 to 100,000, and r= 1 to 3. 0 50000 100000 150000 200000 250000 300000 0 50000 100000 150000 200000 250000 300000 f2 f1 r=1 r=2 r=3 (a) N= 10,000, b= 1 0 200000 400000 600000 800000 1e+06 1.2e+06 1.4e+06 0 200000 400000 600000 800000 1e+06 1.2e+06 1.4e+06 f2 f1 r=1 r=2 r=3 (b) N= 50,000, b= 2 Figure 6: 50%-empirical attainment surfaces of the 30 runs of the Multi-Start Hill Climber based on Algorithm 1 for a MNK Landscape with d= 2, subfunctions codomain [−49,50], and r= 1 to 3. r= 3 does not always dominate the one with r= 2. As Nincreases, the 50%-EAS obtained with r= 3 shrinks and is usually dominated by the 50%-EAS obtained with r= 2. Thus, we can say that r= 2 is the optimal value for these instances. 6. CONCLUSIONS AND FUTURE WORK The use of problem knowledge is always beneficial to design more effective search procedures and operators. In the case of pseudo-Boolean optimization the formal structure of Mk Landscapes has been previously used to develop efficient hill climbers that explore a Hamming ball of radius rin constant time if the number of subfunctions each variable appears in is bounded by a constant. We conclude in this work that this O(1) time cannot be guaranteed if we want to solve constrained problems and we proposed a new hill climber for multi-objective constrained problems whose worst case runtime is O(n), which is still low compared to the complete exploration of the Hamming ball when r > 1. Combining the proposed hill climber with high-level search algorithms seems a promising line of work that could produce new very efficient optimization algorithms. Another future line of research is the adaptaion of the key ingredients of this hill climber to other search spaces, like permutations or integer vectors. Acknowledgements This research was partially funded by the Fulbright program, the Spanish Ministry of Education, Culture and Sport (CAS12/00274), the Spanish Ministry of Economy and Competitiveness and FEDER (TIN2014-57341-R), the University of M´alaga, Andaluc´ıa Tech, the Air Force Office of Scientific Research, Air Force Materiel Command, USAF (FA9550-11-1-0088), the FAPESP (2015/06462-1) and CNPq. 7. REFERENCES [1] Hernan E. Aguirre and Kiyoshi Tanaka. Insights on properties of multiobjective MNK-landscapes. In Proceedings of CEC, volume 1, pages 196–203, 2004. [2] Wenxiang Chen, Darrell Whitley, Doug Hains, and Adele Howe. Second order partial derivatives for NK-landscapes. In Proceeding of GECCO, pages 503–510, New York, NY, USA, 2013. ACM. [3] Francisco Chicano, Darrell Whitley, and Andrew M. Sutton. Efficient identification of improving moves in a ball for pseudo-boolean problems. In Proceedings of GECCO, pages 437–444. ACM, 2014. [4] Francisco Chicano, Darrell Whitley, and Renato Tin´os. Efficient hill climber for multi-objective pseudo-boolean optimization. In Proceedings of EvoCOP, pages 88–103, 2016. [5] Yves Crama, Pierre Hansen, and Brigitte Jaumard. The basic algorithm for pseudo-boolean programming revisited. Discrete Applied Mathematics, 29(2-3):171–185, 1990. [6] Brian W. Goldman and William F. Punch. Gray-box optimization using the parameter-less population pyramid. In Proceedings of GECCO, pages 855–862, New York, NY, USA, 2015. ACM. [7] Holger H. Hoos and Thomas St¨ utzle. Stochastic Local Search: Foundations and Applications. Morgan Kaufman, 2004. [8] Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer-Verlag, 2004. [9] J. Knowles. A summary-attainment-surface plotting method for visualizing the performance of stochastic multiobjective optimizers. In Proceedings of ISDA, pages 552–557, 2005. [10] Luis Paquete, Tommaso Schiavinotto, and Thomas St¨ utzle. On local optima in multiobjective combinatorial optimization problems. Annals of Operations Research, 156(1):83–97, 2007. [11] Ivo G. Rosenberg. Reduction of bivalent maximization to the quadratic case. Cahiers Centre Etudes Rech. Oper., 17:71–74, 1975. [12] Darrell Whitley. Mk landscapes, NK landscapes, MAX-kSAT: A proof that the only challenging problems are deceptive. In Proceedings of GECCO, pages 927–934, New York, NY, USA, 2015. ACM. [13] Darrell Whitley and Wenxiang Chen. Constant time steepest descent local search with lookahead for NK-landscapes and MAX-kSAT. In Proceedings of GECCO, pages 1357–1364, 2012. [14] Darrell Whitley, Wenxiang Chen, and Adele E. Howe. An empirical evaluation of O(1) steepest descent for NK-landscapes. In Proceedings of PPSN, pages 92–101, 2012.