Markov Chain Analysis of Noise and Restart in Stochastic Local Search

1 Introduction

Stochastic local search (SLS) algorithms are greedy optimizers that also make noisy (random) search steps to improve their performance. The SLS paradigm is simple but broadly applicable [Hoos and St¨utzle, 2005], and underlies strong algorithms for satisfiability [Selman et al., 1992; 1994; Gu et al., 1997; Hoos and St¨utzle, 2005] as well as computing the most probable explanation [Kask and Dechter, 1999; Mengshoel, 2008; Mengshoel et al., 2011b] and the maximum a posteriori hypothesis [Park and Darwiche, 2004] in Bayesian networks. Restart, often combined with powerful initialization heuristics, has proven to be essential in many SLS algorithms [Selman et al., 1992; Gent and Walsh, 1993; Ruan et al., 2002; Ryvchin and Strichman, 2008; Mengshoel et al., 2011b; 2011a; Audemard and Simon, 2012].

Youssef Ahres

Electrical Engineering Stanford University yahres@stanford.edu

Tong Yu

Electrical and Computer Engineering Carnegie Mellon University tong.yu@sv.cmu.edu

Despite the empirical success of SLS algorithms, their mathematical foundation is in general under-developed [Wegener, 2001; Mengshoel, 2008]. For example, hard restart as implemented in most classic SLS algorithms [Selman et al., 1992; Gent and Walsh, 1993; Selman et al., 1994; Gu et al., 1997; Hoos and St¨utzle, 2005; Mengshoel, 2008; Mengshoel et al., 2011b] violates the assumption of a homogeneous Markov chain as we discuss further below. This makes a Markov chain analysis that takes classic restart into account quite complex.

Evolutionary algorithms (EAs) including genetic algorithms (GAs) have been studied using Markov chains [Goldberg and Segrest, 1987; Suzuki, 1995; Yu and Zhou, 2008]. Among EAs, the (1+1)EA [Wegener, 2001; Droste et al., 2002] may appear similar to our MarkovSLS approach. These EAs, however, do not integrate the greedy, noise, and restart steps typically found in SLS algorithms. For example, the (1+1)EA does not have greedy or restart steps and can during mutation flip multiple bits per search step, assuming that the search space is a bit string. Our MarkovSLS algorithm, on the other hand, only flips one bit per search step but integrates greedy, noise, and restart steps.

There is also related research on Las Vegas algorithms, which always compute the correct answer but have a random running time. Luby et al. develop a universal restart strategy for Las Vegas algorithms [Luby et al., 1993]. However, this work does not integrate noise and restart, which is our focus.

More broadly, most previous research on SLS is limited in at least one of the following ways. It (i) is typically either strictly empirical or strictly theoretical; (ii) investigates the impact of a single algorithmic operator (noise, restart, or mutation) to complement greedy search but not several; (iii) does not adapt operator parameters at run-time; or (iv) focuses on problems other than feature selection (for example SAT).

This paper seeks to jointly address all issues (i)-(iv) through a simple algorithm MarkovSLS, which has two special cases SoftSLS and AdaptiveSLS. Issue (i): Using deceptive problems and Markov chains, SoftSLS enables us to develop a theoretical foundation to optimize the parameters analytically by means of expected hitting times as opposed to the traditional empirical way. Experimentally, we show the combined impact of the SoftSLS and problem instance parameters on the average running time, validating our expected hitting time results. Issue (ii): We study a probabilistic SLS restart approach, which we call soft restart, and embed it into MarkovSLS. Due to the use of soft restart, and in contrast to the classic hard restart, SoftSLS does not violate the homogeneous Markov chain property. We can therefore investigate analytically how restart and noise interact. 1 Issue (iii): The novel AdaptiveSLS algorithm, which dynamically adjusts its noise and restart parameters, is shown to have robust performance on several different problem instances. Issue (iv): In small-scale experiments, we investigate feature selection problems using SoftSLS and AdaptiveSLS.

In addition, we hope that this work will provide a foundation for future work, both on SLS algorithms and on integrating SLS more tightly with Markov decision processes (MDPs) and other techniques based on Markov chains.

2 Preliminaries and Notation

We consider problem instances as bitstrings b 2 ¶0↪1♦n and define N(b), the neighbors of b, to be all bitstrings with a Hamming distance of one to b. Without loss of generality, we study maximization problems. For simplicity, we assume a unique optimal solution b⇤ in our analysis. We construct a one-to-one mapping b from the original search space as follows: 1 means a correct value (relative to b⇤ ) and 0 an incorrect value (relative to b⇤ ). Under these assumptions, b(b⇤ ) = 1▷▷▷1 is the unique optimal solution.

We use Markov chains to formalize SLS algorithms.

Definition 1. (Markov chain) A Markov chain M = (S↪V↪P) has a set S = ¶s1↪ ▷▷▷↪ sn♦ of states, an initialization vector V = (p1↪ ▷▷↪pn), and an n⇥n transition probability matrix P. M is homogeneous if P(Xt+1 = j ♣ Xt = i) = pi j is independent of t, else it is inhomogeneous.

In this paper, "Markov violation" or "violation of the Markov property" is an abbreviation of "violation of the assumption of a homogeneous Markov chain."

The optimal state s⇤ is what SLS seeks to find. We now define first passage time for s⇤ .

Definition 2. (First passage time) Consider a Markov chain M = (S↪V↪P) with a unique optimal state s⇤ 2 S. The first passage time T into s⇤ is given by: T =min( j ≥ 0 : Xj = s⇤ ). The expected value of T given an initial state si 2 S is:

Using the definition of first passage time, the expected hitting time for a Markov chain is defined.

Definition 3. Given a Markov chain M = (S↪V↪P), the expected hitting time is:

The expected hitting time of an SLS algorithm is the analytical counterpart to average running time as measured for an implementation of that algorithm [Mengshoel, 2008]. 2

1 While very interesting, Luby et al.'s paper, for example, leaves this issue unanswered.

2 An alternative to using hitting times is to introduce, for optima, absorbing states in the Markov chain and study absorption times [Zhou et al., 2009; Ermon et al., 2014].

Data: pr, pn, f , n, t, ar, an Result: s0 , g0 , t 1 t 1; g0 0; 2 while g0 < t do 3 s INIT(n); g f (s); 4 if g≥g0 then g0 g; s0 s ; 5 restart f alse; 6 while !restart and g0 < t do 7 next NEXT STEP(pr↪ pn); 8 if next = oG then 9 old s s; s GREEDY STEP(s); 10 if old s = s then 11 pr = pr + ¯ prar ; 12 pn = pn+ ¯ pnan; 13 else 14 pr = pr(1-ar◁2); 15 pn = pn(1-an◁2); 16 end 17 end 18 if next =oN then s NOISE STEP(s); 19 if next =oR then restart t rue; 20 g f (s); 21 if g≥g0 then g0 g; s0 s ; 22 t t + 1; 23 end 24 end 25 Return s0 , g0 , t

Our deceptive functions, used to evaluate restart, are inspired by deceptive problems [Goldberg, 1987; Whitley, 1991; Deb and Goldberg, 1991; Mengshoel, 2008]. Deceptive problems typically contain a global optimum and a distinct local optimum, also called a deceptive attractor.

Definition 4. (Deceptive function) Let n↪g↪µ↪d↪x2Nand d : x ! R, where 0  x  n. A deceptive function d(x; n↪ g ↪ µ↪ d ), abbreviated d(x), with 0  d < µ < g  n is defined as follows: there is a unique global maximum d ⇤ = d(g), a local (but non-global) maximum d(d ), and a local minimum µ (the slope-change location). Formally, we have: d(x+1) > d(x) for x < d or µ  x < g; d(x+1) < d(x) for d  x < µ or x > g; and d(µ +1) > d(µ -1).

A deceptive function helps to improve the understanding of the interaction between problem instance difficulty and parameters of stochastic optimization algorithms [Mengshoel, 2008], as reflected in our Markov chain analysis of SoftSLS in Section 4. The parameters n↪g↪µ↪d of these deceptive functions can easily be varied to study the restart aspect of SLS algorithms. This is important, given our focus on the soft (probabilistic) restart mechanism.

The notation ¯p = (1- p) is used in this paper.

3 The MarkovSLS Algorithm

Our MarkovSLS algorithm is presented in Algorithm 1, with these inputs and outputs. The inputs are: restart probability pr; noise probability pn; pseudo-boolean fitness function f :

¶0↪1♦n ! R; bitstring length n; termination threshold t 2 R with t  f (s⇤ ); restart adaptation parameter ar 2 [0↪1]; and noise adaptation parameter an 2 [0↪1]. The outputs are: approximate maximum s0 ; approximately maximal fitness g0 = f (s0 ) ≥ t; and search step counter t.

MarkovSLS has two main advantages relative to previous work: First, it allows a deeper theoretical analysis of its search by randomizing the restart procedure via pr, so-called soft restart. Second, it introduces a novel parameter adaptation mechanism that adapts both the noise and the restart probabilities pn and pr based on information collected about the optimization landscape.

Explanation. We first explain the key variables and functions used in MarkovSLS in Algorithm 1. The variables s, s0 , and old s in Algorithm 1 are bitstrings of length n. INIT(n) creates a bitstring of length n, according to an initialization method. Sampling uniformly at random is such an initialization method. GREEDY STEP(s) and NOISE STEP(s) flip one bit in their input s when creating their output, which is then assigned to s. NEXT STEP(pr↪ pn) randomly decides the next search operator O according to this definition.

Definition 5. (MarkovSLS search operators) The restart operator oR has probability P(O = oR) = pr; the noise operator oN has probability P(O = oN) = (1- pr)pn = ¯ pr pn; and the greedy operator oG has probability P(O = oG) = (1-pr)(1-pn) = ¯ pr ¯ pn.

In a GREEDY STEP(s), the best-fit neighboring state u⇤ of s, among u 2 N(s), is picked as the next state. If there are k candidates u⇤1 , u⇤2 , ▷ ▷ ▷, u⇤k , such that f (u⇤1 ) = f (u⇤2 ) = · · · = f (u⇤k ), one of them is picked as the next step, uniformly at random. In a NOISE STEP(s), a neighboring state u 2 N(s) is picked, uniformly at random, as the next step (regardless of f (u)). To simplify analysis, MarkovSLS runs until an achievable input threshold t is reached.

Soft restart. In classic SLS algorithms, restart is hard (or deterministic) and happens after a fixed number, often called MAX FLIPS, of search steps [Selman et al., 1992; Gent and Walsh, 1993; Selman et al., 1994; Hoos, 2002; Hoos and St¨utzle, 2005; Mengshoel, 2008; Mengshoel et al., 2011b]. Since hard restart violates the Markov property, it is difficult to analyze the impact of restart in these classic algorithms. Instead of having a hard boundary on MAX FLIPS and always restart once we reach it, MarkovSLS uses a probability pr to restart at each step. This is what we refer to as probabilistic (or soft) restart. With soft restart, the effect of restart on the expected hitting time can be better understood, see Section 4.

Parameter adaptation. MarkovSLS updates pr and pn according to the values of the adaptation parameters ar and an. 3 The increments are defined by pr = pr +(1- pr)ar and pn = pn +(1- pn)an, while the decrements are pr = pr(1-ar◁2) and pn = pn(1-an◁2). The increase rate is more aggressive than the decrease rate: once stagnation is detected, we deduce that we are trapped in a local (but perhaps not global) maximum and increase the probabilities pn and pr to escape it. To detect search stagnation, we simply store the last state visited and compare it with the current state, i.e., a self-loop.

3 Similar to AdaptiveNoise [Hoos, 2002], we optimized them empirically for a small set of problem instances and then fixed them for the rest of the study. In this paper, their optimized values are: an = 0▷2 and ar = 0▷1.

Depending on the values of ar and an, we have different variants of MarkovSLS. In this paper we investigate SoftSLS (using ar = an = 0 in MarkovSLS) and AdaptiveSLS (using ar > 0 and an > 0 in MarkovSLS).

3.1 SoftSLS: MarkovSLS with ar =0, an =0

For ar = an = 0, it is easy to see that pr and pn remain at their respective input values in MarkovSLS. There is no adaptation. We define this MarkovSLS variant as SoftSLS in reference to the soft restart mechanism.

In extreme cases, the behavior of SoftSLS can easily be deduced. If pr = 0 and pn = 1, it is a random walk. If pr = 1, we restart without any greedy or noisy steps, and perform random sampling according to INIT(n). However, we are most interested in the interaction between pn and pr in general, where 0  pn  1 and 0  pr  1, as we now discuss.

Restart in most SLS algorithms, which we will call classic SLS algorithm, works like this: after a number of steps defined by MAX FLIPS, the search process deterministically restarts. Cleary, this violates the homogeneous Markov chain property. Let ClassicSLS be the same as the SoftSLS, except it has deterministic restart. The SoftSLS and ClassicSLS algorithms have, in a certain sense, similar behavior if we carefully choose their respective input parameters.

Proposition 1. Let pr >0 and 1◁pr 2N+. Consider the ClassicSLS algorithm with parameters (pn,MAX FLIPS), where MAX FLIPS is the number of flips before restart, and SoftSLS with parameters (pn↪ pr). Let MAX FLIPS = 1◁pr . Then the expected time to restart is the same for ClassicSLS and SoftSLS.

Proof. Given the MarkovSLS pseudo-code, the number of steps before restarting follows a geometric distribution with a parameter pr. Thus, its expectation is 1◁pr . Using the Weak Law of Large Number, we conclude that SoftSLS restarts on average after 1◁pr steps. Under the assumption that classic SLS has restart parameter MAX FLIPS = 1◁pr , clearly the expectations of the restart times are the same.

For SoftSLS, since pr and pn are fixed, we have homogeneous Markov chains, analyzed in Section 4.

3.2 AdaptiveSLS: MarkovSLS with ar >0, an >0

The SoftSLS presented above can be mathematically analyzed to extract optimal parameters for a given problem. However, in practice, we have limited information about the fitness landscape, making the optimization very challenging. Thus, we propose a second special case of MarkovSLS, namely AdaptiveSLS with ar > 0 and an > 0.

For ar > 0↪an > 0, pr and pn are being adapted in MarkovSLS; we define this MarkovSLS variant as AdaptiveSLS. AdaptiveSLS initializes MarkovSLS with parameters pn and pr; MarkovSLS increases them when search stagnates, and decreases them otherwise. The adaptive mechanism in AdaptiveSLS, while relatively simple, appears to be highly competitive with optimized SoftSLS as we will show experimentally.

To our knowledge, previous work has not adapted both noise and restart like AdaptiveSLS. Hoos explored adaptive noise [Hoos, 2002] but not adaptive restart. Luby, Sinclair, and Zuckerman, in contrast, vary restart in their universal strategy but do not investigate adaptive noise [Luby et al., 1993]. Ryvchin and Strichman advocate a related concept, namely localized restarts [Ryvchin and Strichman, 2008].

For AdaptiveSLS, the homogeneous Markov chain property is violated, since pr and pn are changing. Consequently, the analysis in Section 4 refers to SoftSLS, where pr and pn are fixed (giving a homogeneous Markov chain) and not to AdaptiveSLS (giving an inhomogeneous Markov chain).

4 Markov Chain Analysis of SoftSLS

SLS has been analyzed within a Markov chain framework [Mengshoel, 2008]. However, a main constraint of this previous analysis is that the process never restarts: MAX FLIPS = ·. In practice, however, restart typically plays an essential role in SLS. The soft restart in SoftSLS enables us to analyze SLS using homogeneous Markov Chains, taking into consideration the whole SLS process including restart.

4.1 Exact Markov ChainModel

We now analyze SoftSLS, and in particular find the transition probabilities in its Markov chain.

Proposition 2. SoftSLS induces a Markov chain M = (S↪V↪ P) where S = ¶s♣s 2 ¶0↪ 1♦n♦, V is given by INIT(n), and P is as follows. Let oG define a greedy operator, oR a restart operator, and oN a noise operator. Let P(O = o) be the prior, where o 2 ¶oG↪oR↪oN♦. Let SoftSLS be in state m at iteration i, and suppose that m↪ k 2 ¶1↪ 2↪ ▷ ▷ ▷ ↪ 2 n♦. The probability of a transition to state k is:

Proof. S and V are obvious, and we turn to P. The three possible SoftSLS operators (restart oR, greedy oG, and noise oN) are mutually exclusive. Thus, using the law of total probability, we calculate the probability P(Xi+1 = k ♣ Xi = m) of a new state k by adding up the products of the probability P(Xi+1 = k ♣ Xi = m↪O = o) for o 2 ¶oG↪oR↪oN♦ and their respective priors P(O = oG), P(O = oR), and P(O = oN).

An exact Markov chain analysis of SoftSLS would be most accurate, since it is performed over all ¶0↪1♦n states. However, this state space grows exponentially in n, which makes the analysis difficult even for small problem instances.

4.2 Deceptive Markov ChainModel

We now introduce approximate Markov chains, giving a better opportunity to analyze and optimize the SoftSLS algorithm. We introduce deceptive Markov chains, used to evaluate the behavior of SoftSLS as its parameters vary.

Definition 6. (Deceptive Markov chain) An n-bit deceptive Markov chain (DMC) with local optimum d , global optimum

g = n, local minimum µ, probability of noise step pn and probability of restart pr, abbreviated DMC(pn↪ pr;g↪µ↪d), is defined as follows. It has n+1 states, S = ¶0↪ ▷▷↪n♦, and the initial distribution V is defined for i 2 S, as pi = (n i)◁2 n . State transition probabilities are for 0  x < d or µ  x < n defined as:

for d  x < µ:

for 0< x d or µ  x n:

for d < x < µ:

and for x = 0 or x = n:

The above equations divide the transitions into regions: the first two regions consist of increasing slopes between 0 and the local optimum d and between local minimum µ and the global maximum g = n. (We have generally assumed, in this paper, that g = n for simplicity.) The third region consists of a decreasing slope between d , the deceptive optimum, and the local minimum µ. Within each of these two regions, SLS moves forward (toward g) or backward (away from g) according to the above equations.

Proposition 3. If INIT(n) in SoftSLS(pr,pn, f ,n t) is initialization uniformly at random and f is a deceptive function d(x; n↪ g↪ µ↪ d ), then the Markov chain induced by SoftSLS for t = f (n) is a DMC, DMC(pn↪ pr;g↪µ↪d).

Proof Sketch. This follows from the definitions of SoftSLS and of a deceptive function. We start by formulating a Markov chain, then using the fact that f is a deceptive function, we divide the Markov chain into regions: two ascending slope regions and a descending slope region as explained above. It is then easy to deduce the probability to go to a given state using pn and pr, resulting in DMC(pn↪ pr; g↪ µ↪ d ).

Figure 1 shows as an example DMC(pn↪ pr;5↪3↪0), where each directed edge is a probabilistic transition. When pr > 0 in SoftSLS, each node should be connected to all other nodes, since restart can lead the search from a node to any other node. To improve readability, we omit these restart edges.

Generally, we are interested in the influence that the problem difficulty parameters µ and d in a DMC have on the expected hitting time, and their interaction with the SoftSLS parameters (pn↪ pr).

Proposition 4. Let M be a vector of expected first passage times for a DMC(pn↪ pr;g↪µ↪d); mi for 0  i  n. Clearly, mn = 0 as we assumed g = n. We obtain the following. For i =d:

For the same reason as in Definition 5, the above equations are divided into two regions. We see that the expressions for mi greatly depend on µ, d, pr, and pn in addition to the current state i. Thus, we use the notation mi↪µ↪d (pn↪ pr) to more fully characterize the equations.

Following (1), the expected hitting time for a DMC problem of size n and difficulty parameters µ and d is:

From (2), the expected hitting time for a particular deceptive Markov chain, formally denoted as DMC(pn↪ pr; g↪ µ↪ d ), can be computed. An example is provided in Section 4.3.

4.3 Markov Chain Optimization

The above formulation establishes a framework to analyze the performance of SoftSLS on a given search landscape. In this section, we show how we can utilize it to optimize the SoftSLS parameters on that particular landscape. Then, we propose a strategy to generalize this optimization approach to non-trivial problems and unknown landscapes.

An Optimization Example

Let us consider how to solve a DMC and find an optimal pair (p⇤n↪ p⇤r ). We use a small DMC, with n = 5.

Consider the DMC(pn↪ pr;5↪3↪0) as shown in Figure 1 along with its transition probabilities. We will now derive h5↪3↪0(pn↪ pr). The Markov chains initialization vector is V = (p0↪p1↪p2↪p3↪p4↪p5) and we define the vector M = (m0↪m1↪m2↪m3↪m4↪m5) where m5 = 0 and:

Assuming uniform restart in SoftSLS, we have pi = (5 i)◁2 5 . By solving, we obtain mi for i 2 ¶0↪1↪2↪3↪4↪5♦ as a function of pn and pr. Then, we compute  5 0 E[T ♣ X0 = i]P[X0 = i] =  5 0 mipi to obtain the expected hitting time h5↪3↪0(pn↪ pr). Given that they are bivariate, the expression for this solution is quite space-consuming, even for this small 5-bit problem. It is thus omitted here.

Using the solution expression for h5↪3↪0(pn↪ pr) and the active-set algorithm [Nocedal and Wright, 2006], we can deduce an optimal pair (p⇤n↪ p⇤r ) = (0↪ 0▷346) that minimizes the expected hitting time of the Markov chain.

An optimal value of p⇤n = 0 may seem surprising, since it goes against the idea of escaping from local optima via noise. However, p⇤n = 0 is a direct consequence of the deceptive function studied, which mainly stresses the restart aspect of MarkovSLS as discussed in Section 2. In fact, p⇤n 6= 0 for many real-world and synthetic problems. 4

Towards Optimization in General

Above, we formulated a Markov chain and found the optimal (p⇤n↪ p⇤r ) for a known 5-bit problem. However, in practice, we may not know the shape of the search space or its characteristics such as the number of local optima or their locations. Therefore, a procedure to generalize the analysis presented above is necessary for it to inform applications. A very simple, yet potentially powerful, strategy consists of using minimal knowledge of the problem and optimize the parameters over a set of DMCs. For instance, by knowing problem size n, we can solve the DMC(pn↪ pr;g↪µ↪d) for combinations of (g↪ µ↪ d ). This makes a strong assumption about the nature of the problem instance, which may or may not be appropriate. However, the approach has a cubic complexity and there is opportunity for pre-processing.

5 Experimental Results

In experiments with synthetic and real-world problems, we compare SoftSLS, AdaptiveSLS, AdaptiveNoise [Hoos, 2002], and Simulated Annealing [Kirkpatrick et al., 1983].

5.1 Methods and Data

We use both synthetic (deceptive Markov chains) and realworld datasets (feature selection) in our experiments. Table 1

4 For real-world examples, we refer to feature selection problems in Section 5.4. There are also synthetic problems where p⇤n 6= 0 (in the optimal pair). In fact, for deceptive functions with n ≥ 10, this is usually the case. For a family of deceptive functions and their corresponding DMCs, we found an average of pn = 0▷075 and pr = 0▷0388 over optimal pairs, when averaging over a range of values of d and µ.

presents the real-world datasets used for feature selection. 5

In experiments we use t = f (s⇤ ) as input to MarkovSLS. Consequently, both average running time and expected hitting time refer to a global optimum, and fitness or accuracy when terminating does not vary between experiments. Difference in fitness or accuracy is not a confounding factor here.

For apples-to-apples comparisons with analytical results, we measure the average running time, via MarkovSLS's output t. An average over 500 experiments is computed, giving an empirical estimate of the expected hitting time. We also include experimental results for AdaptiveNoise (AN) [Hoos, 2002] and Simulated Annealing (SA) [Kirkpatrick et al., 1983].

5.2 SoftSLS on Synthetic Problems

We now study deceptive Markov chains DMC(pn↪ pr ; n↪ µ↪ d ) with d = 0. Using different values for pr, pn, and µ, we study the performance of SoftSLS. Figure 2 reflects the behavior of SoftSLS for varying pn on the x-axis and varying pr on the y-axis.

The two experimental plots shown leftmost in Figure 2 (for n = 10) correspond well to the expected hitting time results found analytically. 6 This validates our Markov chain analysis. The rightmost two plots show similar behavior for n = 15. Another interesting result is the behavior of the average running time for small values of pn. For very small and very large values of pr, SoftSLS performs poorly. However, by carefully choosing pr, we can drastically reduce the running time. The contour plots in Figure 2 highlight this behavior. This shows how crucial the restart parameter can be to optimize the running time of SLS algorithm.

5 Please see https://archive.ics.uci.edu/ml and http://www.liacc. up.pt

6 Due to space restrictions, we do not show the analytical contour plots corresponding to Figure 2 here. The analysis was done as discussed in Section 4.3.

5.3 AdaptiveSLS on Synthetic Problems

We investigate the performance of AdaptiveSLS, including its response to varying synthetic problem parameters. The DMC problem size is n = 10, and results are averaged over 500 experiments. In order to perform a stringent comparison, we optimized SoftSLS mathematically using its Markov chain analysis.

Table 2 shows a summary of our results. Perhaps surprisingly, AdaptiveSLS sometimes performs better than an optimized SoftSLS. The intuition behind this is that AdaptiveSLS adapts its pr and pn parameters given the current state of search, whether stagnated or not, without knowing the globally optimal values of the parameters. On the other hand, SoftSLS keeps its globally optimized parameters (p⇤n↪ p⇤r ) independently of the current state, which may cause poor performance if it is stuck searching close to a local optimum.

5.4 Use Case: Feature Selection Problems

We now study the performance of SoftSLS and AdaptiveSLS on the real-world problem of feature selection. The goal of the experiment is to investigate, in a randomized wrapper approach to feature selection [Stracuzzi, 2007; Kohavi and John, 1997], whether AdaptiveSLS can achieve comparable results to SoftSLS, without intensive parameter optimization. For each MarkovSLS bitstring s we have a corresponding feature subset. A 0-bit in s means that the corresponding feature is not included in the feature subset; a 1-bit means that it is.

We trained a Decision Tree, on varying feature subsets and computed the cross-validation accuracy. In feature selection, the goal is to find a bitstring s⇤ with the maximal crossvalidation accuracy. Thus, we set a bitstring s's fitness f (s) as its cross-validation accuracy, using 2-fold cross-validation. 7 For each dataset, we searched exhaustively to predetermine the globally optimal feature subset s⇤ , and passed t = f (s⇤ ) to both SoftSLS and AdaptiveSLS. Both algorithms terminate when finding a globally optimal feature subset.

In the comparison between AdaptiveSLS and SoftSLS in the feature selection problems, the results of SoftSLS with empirically optimized parameters are reported. We report the average results of SoftSLS and AdaptiveSLS over 500 experimental runs, to reduce noise.

Table 3 and Figure 3 summarize the average running time results. In general, when the dataset's dimension is larger, the running time is larger as reflected in Table 3. As shown in Figure 3, the approximately optimal pairs are: Diabetes: p⇤r = 1◁4, p⇤n = 2◁100; Australian: p⇤r = 1◁4, p⇤n = 0; Wine: p⇤r = 1◁4, p⇤n = 6◁100; and Breast Cancer: p⇤r = 1◁4, p⇤n = 4◁100. These pairs were found by grid search over 9⇥51 = 459 points (51 values pn 2 ¶0↪ 2◁100↪ 4◁100↪ ▷ ▷ ▷♦ and 9 values pr 2 ¶1↪ 1◁2↪ 1◁4↪ 1◁8↪ 1◁16↪ ▷ ▷ ▷♦). As we can see in Figure 3, the near-optimal pairs of pn and pr form a region. In this region, we have (pn↪ pr) giving either exactly the same or very similar performance to the optimal pair (p⇤n↪ p⇤r ). For Wine, a relatively high pr is necessary in order to minimize average running time, even after considering this region.

Note that AdaptiveSLS does not rely on prior knowledge about p⇤r and p⇤n, which can save substantial computing time. On Diabetes, Wine and Australian, AdaptiveSLS can also beat AdaptiveNoise [Hoos, 2002] where only noise pn is adapted, in terms of average running time. This demonstrates the potential of adapting both the restart and noise probabilities as done in AdaptiveSLS.

7 In multi-class problems, like the Wine dataset, if the number of folds is too large, validation performance will degrade due to imbalance between different folds.

Figure 4 shows the evolution of pr and pn in AdaptiveSLS during search, after initialization pr = pn = 0. Generally, we can divide the search process into two phases: In the first phase, the algorithm often gets stuck in a local optimum. Thus, pr and pn are increased. Due to these high probabilities for pr and pn, we are able to get out of the trap. Then, a second phase starts where we converge towards an optimum while the probabilities decrease. The two phases may repeat, as shown in the rightmost plot of Figure 4. At the end of search, the found pr and pn for Wine and Australian match well with the optimal regions shown in Figure 3.

6 Conclusion

This paper presents a simple SLS algorithm, MarkovSLS. We study two special cases of the algorithm: SoftSLS and AdaptiveSLS. SoftSLS avoids violating the homogeneous Markov chain property by modifying the deterministic restart approach of most SLS algorithms, and using instead a probabilistic restart. This probabilistic restart enables a broad Markov chain and hitting time analysis, including finding the global optima of the noise and restart parameters, for synthetic problems. Experimentally, we study the impact of varying the use of the greedy, noise, and restart operators on the time it takes SoftSLS to find an optimal solution. In contrast to SoftSLS, AdaptiveSLS, dynamically adjusts the probability parameters. Experimentally, we find that the AdaptiveSLS algorithm behaves very well compared to optimized SoftSLS, both for synthetic deceptive problems and for real-world feature selection problems.