Efficient Hill Climber for Multi-Objective Pseudo-Boolean Optimization

Efficient Hill Climber for Multi-Objective Pseudo-Boolean Optimization Francisco Chicano1, Darrell Whitley2, and Renato Tin´os3 1Dept. de Lenguajes y Ciencias de la Computaci´on, University of M´alaga, Spain ? [email protected] 2Dept. of Computer Science, Colorado State University, Fort Collins CO, USA ?? [email protected] 3Department of Computing and Mathematics, University of S˜ao Paulo, Brazil ??? [email protected] Abstract. Local search algorithms and iterated local search algorithms are a basic technique. Local search can be a stand-alone search method, but it can also be hybridized with evolutionary algorithms. Recently, it has been shown that it is possible to identify improving moves in Hamming neighborhoods for k-bounded pseudo-Boolean optimization problems in constant time. This means that local search does not need to enumerate neighborhoods to find improving moves. It also means that evolutionary algorithms do not need to use random mutation as a operator, except perhaps as a way to escape local optima. In this paper, we show how improving moves can be identified in constant time for multiobjective problems that are expressed as k-bounded pseudo-Boolean functions. In particular, multiobjective forms of NK Landscapes and Mk Landscapes are considered. Keywords: Hamming Ball Hill Climber, Delta Evaluation, Multi-Objective Optimization, Local Search 1 Introduction Local search and iterated local search algorithms [8] start at an initial solution and then search for an improving move based on a notion of a neighborhood of solutions that are adjacent to the current solution. This paper will consider k-bounded pseudo-Boolean functions, where the Hamming distance 1 neighborhood is the most commonly used local search neighborhood. ?This research was partially funded by the Fulbright program, the Spanish Ministry of Education (CAS12/00274), the University of M´alaga, Andaluc´ıa Tech, and the Spanish Ministry of Science and Innovation and FEDER (TIN2014-57341-R). ?? It was also sponsored by the Air Force Office of Scientific Research, Air Force Materiel Command, USAF, under grant number FA9550-11-1-0088. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. ??? Renato Tin´os would like to thank FAPESP (under grant 2015/06462-1) and CNPq for the financial support. Recently, it has been shown that the location of improving moves can be calculated in constant time for the Hamming distance 1 “bit flip” neighborhood [16]. This has implications for both local search algorithms as well as simple evolutionary algorithms such as the (1+1) Evolutionary Algorithm. Since we can calculate the location of improving moves, we do not need to enumerate neighborhoods to discover improving moves. Chicano et al. [3] generalize this result to present a local search algorithm that explores the solutions contained in a Hamming ball of radius raround a solution in constant time. This means that evolutionary algorithms need not use mutation to find improving moves; either mutation should be used to make larger moves (that flip more than rbits), or mutation should be used to enable a form of restart. It can also makes crossover more important. Goldman et al. [6] combined local search that automatically calculates the location of improving moves in constant time with recombination to achieve globally optimal results on relatively large Adjacent NK Landscape problems (e.g. 10,000 variables). Whitley [15] has introduced the notion of Mk Landspaces to replace NK Landscapes. Mk Landscapes are k-bounded pseudo-Boolean optimization problems composed of a linear combination of Msubfunctions, where each subfunction is a pseudo-Boolean optimization problem defined over kvariables. This definition is general enough to include NK landscapes, MAX-kSAT, as well as spin glass problems. In this paper, we extend these related concepts to multi-objective optimization. We define a class of multi-objective Mk Landscapes and show how these generalize over previous definitions of multi-objective NK Landscapes. We also show how exact methods can be used to select improving moves in constant time. In the multi-objective space, the notion of an “improving move” is complex because improvement can be improvement in all objectives, or improvement in only part of the objectives. When there are improvement in all objectives, then clearly the improvement should be accepted. However, when there are improvement in only a subset of objectives, it is less clear what moves should be accepted because it is possible for search algorithms to cycle and to visit previously discovered solutions. Methods are proposed that allow the identification of improving moves in constant time for multi-objective optimization. Methods are also proposed to prevent local search algorithms from cycling and thus repeatedly revisiting previously discovered solutions. The results of this work could also be introduced in existing local search algorithms for multi-objective optimization, like Anytime Pareto Local Search [5]. The rest of the paper is organized as follows. In the next section we introduce multi-objective pseudo-Boolean optimization problems. Section 3 defines the “Scores” of a solution. The Score vector tracks changes in the evaluation function and makes it possible to track the locations of improving moves. An algorithm is introduced to track multiple Scores and to efficiently update them for multi-objective optimization. Section 4 considers how to address the problems of selecting improving moves in a multi-objective search space when the move only improves some, but not all, of the objectives. Section 5 empirically evaluates the proposed algorithms. Section 6 summarizes the conclusions and outline the potential for future work. 2 Multi-Objective Pseudo-Boolean Optimization In this paper we consider pseudo-Boolean vector functions with k-bounded epistasis, where the component functions are embedded landscapes [7] or Mk Landscapes [15]. We will extend the concept of Mk Landscapes to the multi-objective domain and, thus, we will base our nomenclature in that of Whitley [15]. Definition 1 (Vector Mk Landscape). Given two constants kand d, a vector Mk Landscape f:Bn→Rdis 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 variables4: fi(x) = mi X l=1 f(l) i(x)for 1≤i≤d,(1) where the subfunctions f(l) idepend only on kcomponents of x∈Bn. This definition generalizes that of Aguirre and Tanaka [1] for MNK Landscapes. In Figure 1(a) we show a vector Mk Landscape with d= 2 dimensions. The first objective function, f1, can be written as the sum of 5 subfunctions, f(1) 1to f(5) 1. The second objective function, f2, can be written as the sum of 3 subfunctions, f(1) 2to f(3) 2. All the subfunctions depend at most on k= 2 variables. It could seem that the previous class of functions is restrictive because each subfunction depends on a bounded number of variables. However, every compressible pseudo-Boolean function can be transformed in polynomial time into a quadratic pseudo-Boolean function (with k= 2) [12]. A useful tool for the forthcoming analysis is the co-ocurrence graph [4] G= (V, E), where Vis the set of Boolean variables and Econtains all the pairs of variables (xj1, xj2) that co-occur in a subfunction f(l) ifor any 1 ≤i≤dand 1≤l≤mi(both variables are arguments of the subfunction). In Figure 1(b) we show the variable co-occurrence graph of the vector Mk Landscape of Figure 1(a). We will consider, without loss of generality, that all the objectives (components of the vector function) are to be maximized. Next, we include the definition of some standard multi-objective concepts to make the paper self-contained. Definition 2 (Dominance). Given a vector function f:Bn→Rd, we say that solution x∈Bndominates solution y∈Bn, denoted with xfy, if and only if fi(x)≥fi(y)for all 1≤i≤dand there exists j∈ {1,2, . . . , d}such that 4In general, we will use boldface to denote vectors in Rd, as f, but we will use normal weight for vectors in Bn, like x. x1x2x3x4x5 f(1) 1f(2) 1f(3) 1f(4) 1f(5) 1 f(1) 2f(2) 2f(3) 2 (a) Vector Mk Landscape x1x2 x3 x4 x5 (b) Co-occurrence graph Fig. 1. A vector Mk Landscape with k= 2, n= 5 variables and d= 2 dimensions (top) and its corresponding co-occurrence graph (bottom). fj(x)> fj(y). When the vector function is clear from the context, we will use  instead of f. Definition 3 (Pareto Optimal Set and Pareto Front). Given a vector function f:Bn→Rd, the Pareto Optimal Set is the set of solutions Pthat are not dominated by any other solution in Bn. That is: P={x∈Bn|@y∈Bn, y x}.(2) The Pareto Front is the image by fof the Pareto Optimal Set: PF =f(P). Definition 4 (Set of Non-dominated Solutions). Given a vector function f:Bn→Rd, we say that a set X⊆Bnis a set of non-dominated solutions when there is no pair of solutions x, y ∈Xwhere yx, that is, ∀x∈X, @y∈X, y x. Definition 5 (Local Optimum [11]). Given a vector function f:Bn→Rd, and a neighborhood function N:Bn→2Bn, we say that solution xis a local optimum if it is not dominated by any other solution in its neighborhood: @y∈ N(x), y x. 3 Moves in a Hamming Ball We can characterize a move in Bnby a binary string v∈Bnhaving 1 in all the bits that change in the solution. Following [3] we will extend the concept of Score5to vector functions. 5What we call Score here is also named ∆-evaluation by other authors [13]. Definition 6 (Score). For v, x ∈Bn, and a vector function f:Bn→Rd, we denote the Score of xwith respect to move vas Sv(x), defined as follows: Sv(x) = f(x⊕v)−f(x),(3) where ⊕denotes the exclusive OR bitwise operation (sum in Z2). The Score Sv(x) is the change in the vector function when we move from solution xto solution x⊕v, that is obtained by flipping in xall the bits that are 1 in v. Our goal is to efficiently decide where to move from the current solution. If possible, we want to apply improving moves to our current solution. While the concept of “improving” move is clear in the single-objective case (an improving move is one that increases the value of the objective function), in multi-objective optimization any of the dcomponent functions could be improving, disimproving or neutral. Thus, we need to be more clear in this context, and define what we mean by “improving” move. It is useful to define two kinds of improving moves: the weak improving moves and the strong improving moves. The reason for this distinction will be clear in Section 4. Definition 7 (Strong and Weak Improving Moves). Given a solution x∈ Bn, a move v∈Bnand a vector function f:Bn→Rd, we say that move vis a weak improving move if there exists i∈ {1,2, . . . , d}such that fi(x⊕v)> fi(x). We say that move vis a strong improving move if it is a weak improving move and for all j∈ {1,2, . . . , d}fj(x⊕v)≥fj(x). Using our definition of Score, we can say that a move vis a weak improving move if there exists a j∈ {1,2, . . . , d}for which Sj,v(x)>0. It is a strong improving move if Si,v(x)≥0 for all i∈ {1,2, . . . , d}and there exists a j∈ {1,2, . . . , d}for which Sj,v(x)>0. From Definition 7 it can be noticed that if vis a strong improving move in xthen x⊕vx, that is, the concept of strong improving move coincides with that of dominance. It can also be noticed that in the single-objective case, d= 1, both concepts are the same. Strong improving moves are clearly desirable, since they cannot be disimproving for any objective and they will improve at least one. Weak improving moves, on the other hand, improve at least one objective but could disimprove other ones. In particular, if vis a weak, but not strong, improving move in solution x, then it will improve at least one objective, say i-th, and disimprove at least another one, say j-th. If this move is taken, in the new solution, x⊕v, the same move vwill be again a weak, but not strong, improving move. However, now vwill improve (at least) the j-th objective and will disimprove (at least) i-th. Taking vagain in x⊕vwill lead to x, and the algorithm cycles. Any hill climber taking weak improving moves should include a mechanism to avoid cycling. Scores are introduced in order to efficiently identify where the (weak or strong) improving moves are. For this purpose, we can have a data structure where all the improving moves can be accessed in constant time. As the search progresses the Score values change and they also move in the data structure to keep improving moves separated from the rest. A na¨ıve approach to track all improving moves in a Hamming Ball of radius raround a solution would require to store all possible Scores for moves vwith |v| ≤ r, where |v|denotes the number of 1 bits in v. If we naively use equation (3) to explicitly update the scores, we will have to evaluate all Pr i=1 n i=O(nr) neighbors in the Hamming ball. Instead, if the objective function is a vector Mk Landscape where each Boolean variable appears in at most a constant number of subfunctions, we can design an efficient next improvement hill climber for the radius rneighborhood that only stores a linear number of Scores and requires a constant time to update them. 3.1 Scores Update Using the fact that each component fiof the objective vector function is an Mk Landscape, we can write: Si,v(x) = mi X l=1 f(l) i(x⊕v)−f(l) i(x)= mi X l=1 S(l) i,v(x),(4) where we use S(l) i,v to represent the score of the subfunction f(l) ifor move v. Let us define wi,l ∈Bnas the binary string such that the j-th element of wi,l is 1 if and only if f(l) idepends on variable xj. The vector wi,l can be considered as a mask that characterizes the variables that affect f(l) i. Since f(l) ihas bounded epistasis k, the number of ones in wi,l, denoted with |wi,l|, is at most k. By the definition of wi,l, the next equalities immediately follow. f(l) i(x⊕v) = f(l) i(x) for all v∈Bnwith v∧wi,l = 0,(5) S(l) i,v(x) = (0 if wi,l ∧v= 0, S(l) i,v∧wi,l (x) otherwise. (6) Equation (6) claims that if none of the variables that change in the move characterized by vis an argument of f(l) ithe Score of this subfunction is zero, since the value of this subfunction will not change from f(l) i(x) to f(l) i(x⊕v). On the other hand, if f(l) idepends on variables that change, we only need to consider for the evaluation of S(l) i,v(x) the changed variables that affect f(l) i. These variables are characterized by the mask vector v∧wi,l. With the help of (6) we can re-write (4): Si,v(x) = mi X l=1 wi,l∧v6=0 S(l) i,v∧wi,l (x).(7) Equation (7) simply says that we don’t have to consider all the subfunctions to compute a Score. This can reduce the runtime to compute the scores from scratch. During the search, instead of computing the Scores using (7) after every move, it is more efficient in time to store the Scores Sv(x) of the current solution xin memory and update only those that are affected by the move. In the following, and abusing of notation, given a move v∈Bnwe will also use vto represent the set of variables that will be flipped in the move (in addition to the binary string). For each of the Scores to update, the change related to subfunction f(l) iafter move t∈Bncan be computed with the help of S(l) i,v(x⊕t) = f(l) i(x⊕t⊕ v)−f(l) i(x⊕t) and S(l) i,v(x) = f(l) i(x⊕v)−f(l) i(x). The component Si,v will be updated by subtracting S(l) i,v(x) and adding S(l) i,v(x⊕t). This procedure is shown in Algorithm 1, where the term Si,v represents the i-th component of the Score of move vstored in memory and Mris the set of moves whose scores are stored. In the worst (and na¨ıve) case Mris the set of all strings vwith at most rones, Mr={v|1≤ |v| ≤ r}, and |Mr|=O(nr). However, we will prove in Section 3.2 that, for some vector Mk Landscapes, we only need to store O(n) Scores to identify improving moves in a ball of radius r. Algorithm 1 Efficient algorithm for Scores update Input: scores vector S, current solution x, move t 1: for (i, l) such that wi,l ∧t6= 0 do 2: for v∈Mrsuch that wi,l ∧v6= 0 do 3: Si,v ←Si,v +f(l) i(x⊕t⊕v)−f(l) i(x⊕t) −f(l) i(x⊕v) + f(l) i(x) 4: end for 5: end for 3.2 Scores Decomposition Some scores can be written as a sum of other scores. The benefit of such a decomposition is that we do not really 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 on the objective function f. The co-occurrence graph has a main role in identifying the moves whose Scores are fundamental to recover all the improving moves in the Hamming ball. Let us denote with G[v] the subgraph of Ginduced by v, that is, the subgraph containing only the vertices in vand the edges of Ebetween vertices in v. Proposition 1 (Score decomposition). Let v1, v2∈Bnbe two moves such that v1∩v2=∅and variables in v1do not co-occur with variables in v2. In terms of the co-occurrence graph this implies that there is no edge between a variable in v1and a variable in v2and, thus, G[v1∪v2] = G[v1]∪G[v2]. Then, the score function Sv1∪v2(x)can be written as: Sv1∪v2(x) = Sv1(x) + Sv2(x).(8) Proof. Using (7) we can write: Si,v1∪v2(x) = mi X l=1 wi,l∧(v1∨v2)6=0 S(l) i,(v1∨v2)∧wi,l (x) = mi X l=1 (wi,l∧v1)∨(wi,l∧v2)6=0 S(l) i,(v1∧wi,l)∨(v2∧wi,l)(x). Since variables in v1do not co-occur with variables in v2, there is no wi,l such that v1∧wi,l 6= 0 and v2∧wi,l 6= 0 at the same time. Then we can write: Si,v1∪v2(x) = mi X l=1 wi,l∧v16=0 S(l) i,v1∧wi,l (x) + mi X l=1 wi,l∧v26=0 S(l) i,v2∧wi,l (x) = Si,v1(x) + Si,v2(x), and the result follows. ut For example, in the vector Mk Landscape of Figure 1 the scoring function S1,3,4can be written as the sum of the scoring functions 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. A consequence of Proposition 1 is that we only need to store scores for moves vwhere G[v] is a connected subgraph. If G[v] is not a connected subgraph, then there are sets of variables v1and v2such that v=v1∪v2and v1∩v2=∅and, applying Proposition 1 we have Sv(x) = Sv1(x) + Sv2(x). Thus, we can recover all the scores in the Hamming ball of radius rfrom the ones for moves vwhere 1≤ |v| ≤ rand G[v] is connected. In the following we will assume that the set Mrof Algorithm 1 is: Mr={v∈Bn|1≤ |v| ≤ rand G[v] is connected}.(9) 3.3 Memory and Time Complexity of Scores Update We will now address the question of how many of these Scores exist and what is the cost in time of updating them after a move. Lemma 1. Let f:Bn→Rdbe a vector Mk Landscape where each Boolean variable appears in at most csubfunctions f(l) i. Then, the number of connected subgraphs with size no greater than rof the co-occurrence graph Gcontaining a given variable xjis O((3ck)r). Proof. For each connected subgraph of Gcontaining xjwe can find a spanning tree with xjat the root. The degree of any node in Gis bounded by ck, since each variable appears at most in csubfunctions and each subfunction depends at most on kvariables. Given a tree of lnodes with xjat the root, we have to assign variables to the rest of the nodes in such a way that two connected nodes have variables that are adjacent in G. The ways in which we can do this is bounded by (ck)l−1. We have to repeat the same operation for all the possible rooted trees of size no greater than r. If Tlis the number of rooted trees with l vertices, then the number of connected subgraphs of Gcontaining xjand with size no greater than rnodes is bounded by r X l=1 Tl(ck)l−1≤ r X l=1 3l(ck)l−1≤3(3ck)r,(10) where we used the result in [10] for the asymptotic behaviour of Tl: lim l→∞ Tl Tl−1 ≈2.955765.(11) ut Lemma 1 provides a bound for the number of moves in Mrthat contains an arbitrary variable xj. In effect, the connected subgraphs in Gcontaining xj corresponds to the moves in Mrthat flip variable xj. An important consequence is given by the following theorem. Theorem 1. Let f:Bn→Rdbe a vector Mk Landscape where each Boolean variable appears in at most csubfunctions. Then, the number of connected subgraphs of Gof size no greater than ris O(n(3ck)r), which is linear in nif cis independent of n. This is the cardinality of Mrgiven in (9). Proof. The set of connected subgraphs of Gwith size no greater than ris the union of connected subgraphs of Gof size no greater than rthat contains each of the nvariables. According to Lemma 1 the cardinality of this set must be O(n(3ck)r). ut The next Theorem bounds the time required to update the scores. Theorem 2. Let f:Bn→Rdbe a vector Mk Landscape where each Boolean variable appears in at most csubfunctions f(l) i. The time required to update the Scores using Algorithm 1 is O(b(k)|t|(3ck)r+1)where b(k)is a bound on the time required to evaluate any subfunction f(l) i. Proof. Since each variable appears in at most csubfunctions, the number of subfunctions containing at least one of the bits in tis at most c|t|, and this is the number of times that the body of the outer loop starting in Line 1 of Algorithm 1 is executed. Once the outer loop has fixed a pair (i, l), the number of moves v∈Mrwith wi,l ∧v6= 0 is the number of moves v∈Mrthat contains a variable in wi,l. Since |wi,l| ≤ kand using Lemma 1, this number of moves is O(k(3ck)r). Line 3 of the algorithm is, thus, executed O(|t|ck(3ck)r) times, and considering the bound on the time to evaluate the subfunctions, b(k) the result follows. ut combination with other components to build an efficient search algorithm seem two promising and challenging directions to work in the near future. References 1. Aguirre, H.E., Tanaka, K.: Insights on properties of multiobjective MNKlandscapes. In: Proceedings of the Congress on Evolutionary Computation. vol. 1, pp. 196–203 (June 2004) 2. Chen, W., Whitley, D., Hains, D., Howe, A.: Second order partial derivatives for NK-landscapes. In: Proceeding of GECCO. pp. 503–510. ACM, New York, NY, USA (2013) 3. Chicano, F., Whitley, D., Sutton, A.M.: Efficient identification of improving moves in a ball for pseudo-boolean problems. In: Proceedings of Genetic and Evolutionary Computation Conference. pp. 437–444. ACM, New York, NY, USA (2014) 4. Crama, Y., Hansen, P., Jaumard, B.: The basic algorithm for pseudo-boolean programming revisited. Discrete Applied Mathematics 29(2-3), 171–185 (1990) 5. Dubois-Lacoste, J., L´opez-Ib´a˜nez, M., St¨utzle, T.: Anytime pareto local search. European Journal of Operational Research 243(2), 369–385 (2015) 6. Goldman, B.W., Punch, W.F.: Gray-box optimization using the parameter-less population pyramid. In: Proceedings of Genetic and Evolutionary Computation Conference. pp. 855–862. ACM, New York, NY, USA (2015) 7. Heckendorn, R., Rana, S., Whitley, D.: Test function generators as embedded landscapes. In: Foundations of Genetic Algorithms. pp. 183–198. Morgan Kaufmann (1999) 8. Hoos, H.H., St¨utzle, T.: Stochastic Local Search: Foundations and Applications. Morgan Kaufman (2004) 9. Knowles, J.: A summary-attainment-surface plotting method for visualizing the performance of stochastic multiobjective optimizers. In: Proceedings of Intelligent Systems Design and Applications. pp. 552–557 (Sept 2005) 10. Otter, R.: The number of trees. Annals of Mathematics 49(3), 583–599 (1948) 11. Paquete, L., Schiavinotto, T., St¨utzle, T.: On local optima in multiobjective combinatorial optimization problems. Annals of Operations Research 156(1), 83–97 (2007) 12. Rosenberg, I.G.: Reduction of bivalent maximization to the quadratic case. Cahiers Centre Etudes Rech. Oper. 17, 71–74 (1975) 13. Taillard, E.: Robust taboo search for the quadratic assignment problem. Parallel Comput. 17(4-5), 443–455 (Jul 1991) 14. Whitley, D., Howe, A., Hains, D.: Greedy or not? best improving versus first improving stochastic local search for MAXSAT. In: Proc.of AAAI-2013 (2013) 15. Whitley, D.: Mk landscapes, NK landscapes, MAX-kSAT: A proof that the only challenging problems are deceptive. In: Proceedings of Genetic and Evolutionary Computation Conference. pp. 927–934. ACM, New York, NY, USA (2015) 16. Whitley, D., Chen, W.: Constant time steepest descent local search with lookahead for NK-landscapes and MAX-kSAT. In: Soule, T., Moore, J.H. (eds.) GECCO. pp. 1357–1364. ACM (2012)