text:
We investigate popular trajectory-based algorithms inspired by biology and physics to answer a question of general significance: when is it beneficial to reject improvements? A distinguishing factor of SSWM (strong selection weak mutation), a popular model from population genetics, compared to the Metropolis algorithm (MA), is that the former can reject improvements, while the latter always accepts them. We investigate when one strategy outperforms the other. Since we prove that both algorithms converge to the same stationary distribution, we concentrate on identifying a class of functions inducing large mixing times, where the algorithms will outperform each other over a long period of time. The outcome of the analysis is the definition of a function where SSWM is efficient, while Metropolis requires at least exponential time. The identified function favours algorithms that prefer high quality improvements over smaller ones, revealing similarities in the optimisation strategies of SSWM and Metropolis respectively with best-improvement (BILS) and first-improvement (FILS) local search. We conclude the paper with a comparison of the performance of these algorithms and a (1,\(\lambda \)) RLS on the identified function. The algorithm favours the steepest gradient with a probability that increases with the size of its offspring population. The results confirm that BILS excels and that the (1,\(\lambda \)) RLS is efficient only for large enough population sizes.
The Strong Selection Weak Mutation (SSWM) algorithm is a recent randomised search heuristic inspired by the popular model of biological evolution in the 'strong selection, weak mutation regime' [14, 15]. The regime applies when mutations are rare and selection is strong enough such that new genotypes either replace the parent population or are lost completely before further mutations occur [5, 7].
The SSWM algorithm belongs to the class of trajectory-based search heuristics that evolve a single trajectory of search points rather than using a population. Amongst single trajectory algorithms, well-known ones are (randomised) local search, simulated annealing, the Metropolis algorithm (MA)—simulated annealing with fixed temperature—and simple classes of evolutionary algorithms such as the well-studied (\(1+1\)) EA and the (\(1+\lambda \)) EA. The main differences between SSWM and the (\(1+1\)) EA is that the latter only accepts new solutions if they are at least as good as the previous ones (a property called elitism), while SSWM can reject improvements and it may also accept non-improving solutions with some probability (known as non-elitism). This characteristic may allow SSWM to escape local optima by gradually descending the slope leading to the optimum rather than relying on large, but rare, mutations to a point of high fitness far away.
A recent study has rigorously analysed the performance of SSWM in comparison with the (\(1+1\)) EA for escaping local optima [11]. The study only allowed SSWM to use local mutations such that the algorithm had to rely exclusively on its non-elitism to escape local optima, hence to highlight the differences between elitist and non-elitist strategies. A vast class of fitness functions, called fitness valleys, was considered. These valleys consist of paths between consecutive local optima where the mutation probability of going forward on the path is the same as going backwards. However, the valleys may have arbitrary length and arbitrary depth, where the length is measured by the hamming distance while the depth is the maximal fitness difference that has to be overcome.
The analysis revealed that the expected time of the (\(1+1\)) EA to cross the valley (i.e. escape the local optimum) is exponential in the length of the valley while the expected time for SSWM can be exponential in the depth of the valley.
However, other non-elitist trajectory-based algorithms such as the well-known Metropolis algorithm have the same asymptotic runtime as SSWM on fitness valleys, independent of lengths and depths. While both algorithms rely on non-elitism to descend the valleys, it is not necessarily obvious that the algorithms should have the same runtime on the valleys, because they differ significantly in the probability of accepting improving solutions. In particular, Metropolis always accepts improvements while SSWM may reject an improving solution with a probability that depends on the difference between the quality of the new and the previous solution.
In this paper we investigate SSWM and Metropolis with the goal of identifying function characteristics for which the two algorithms perform differently. Given that the main difference between the two is that SSWM may reject improvements, we aim to identify a class of functions where it is beneficial to do so and, as a result, identify an example where SSWM outperforms Metropolis.
The roadmap is as follows. After introducing the algorithms precisely in the Preliminaries section, we show in Sect. 3 that our task is not trivial by proving that both algorithms converge to the same stationary distribution for equivalent parameters. While this result seems to have been known in evolutionary biology [17] we are not aware of a previous proof in the literature. In Sect. 4 we define a simple fitness function (called 3 state model) where two possible choices may be made from the initial point; one leading to a much larger fitness than the other. The idea is that, while Metropolis should be indifferent to the choice, SSWM should pick one choice more often than the other. Although this intuition is true, it turns out that, due to Metropolis' ability of escaping local optima, the mixing time for the 3 state model is small and afterwards the two algorithms behave equivalently as proven in the previous section. In Sect. 5 we extend the fitness function (leading to a 5 state model) by adding two more states of extremely high fitness such that, once the algorithms have made their choice, the probability of escaping the local optima is very low. By tuning these high fitness points we can either reward or penalise a strategy that rejects small improvements. We capitalise on this by concatenating several 5 state model s together (each of which we refer to as a component) and by defining a composite function that requires that a high number of correct choices are made by the algorithm. Then we show that for appropriate fitness values of the different states, SSWM achieves the target of the function and Metropolis does not with overwhelming probability. We complement our theoretical findings with experiments which help to understand the complete picture.
In Sect. 6 we consider other common single trajectory based search algorithms to compare their performance on the identified function class with SSWM and Metropolis. The reason that SSWM outperforms Metropolis for the identified composite function is that the former algorithm tends to favour the acceptance of search points on the slope of largest uphill gradient while the latter algorithm accepts any improvement independent of its quality. Hence, we expect that also other algorithms that prefer improvements of higher quality over smaller ones (i.e., a characteristic often referred to as exploitation) perform well on the composite function. To this end we consider the well known Best-Improvement Local Search (BILS) algorithm that always selects the neighbouring point of highest fitness and compare it with a less exploitational local search strategy which accepts the first found improvement (FILS). Finally, we also consider a classical single trajectory evolutionary algorithm that favours exploitation. In order to achieve a fair performance comparison with SSWM and Metropolis we consider the (1,\(\lambda \)) RLS algorithm which, like the former algorithms, uses non-elitism and local mutations. The results show that BILS excels on the composite function while the (1,\(\lambda \)) RLS only works for large enough population sizes.
This article extends a previous conference paper [10] that only focussed on the comparison of SSWM and the Metropolis algorithm.
As mentioned in the introduction, we will be considering trajectory-based heuristics. The pseudo-code of Algorithm 1 considers algorithms with local mutations, i.e., only search points that differ in one bit can be sampled. However, the new individual will be accepted or rejected according to a probability function known as the acceptance probability \(p_\mathrm {acc}:{\mathbb R}\rightarrow [0,1]\).
Two important characteristics of the acceptance probability are how detrimental and beneficial moves are dealt with. Elitist algorithms such as RLS will directly reject any worsening move and accept any improving search point. Hence, an elitist trajectory-based algorithm will not be able to escape local optima.
To avoid this weakness, the algorithm must relax its selection strength. This is the case in the Metropolis [9] algorithm where detrimental moves are allowed with some probability, depending on the temperature \(1/\alpha \). However, improvements will always be accepted regardless of their magnitude:
To investigate the other main characteristic of non-elitism, allowing the rejection of improvements, we will study a recently introduced algorithm [11, 15, 16] based on the so called SSWM evolutionary regime from Population Genetics (PG). Within this regime a new genotype will eventually take over of a population of size \(N\in {\mathbb N}^+\) or become extinct according to the following expression. This formula depends on the fitness difference \(\varDelta f\) and a scaling factor \(\beta \in {\mathbb R}^+\) [7]. To cast this regime as an algorithm we simply use the following acceptance probability in Algorithm 1. For \(\varDelta f \ne 0\) we define
and \(p_\mathrm {acc}^{\mathrm {SSWM}}(0) := \lim _{\varDelta f \rightarrow 0} p_\mathrm {acc}^{\mathrm {SSWM}}(\varDelta f) = 1/N\). Figure 1 presents an example of these two acceptance probabilities. We observe how both algorithms treat worsening moves similarly. The main difference arises when dealing with improvements. Unlike Metropolis, SSWM will prefer to keep the current search point against a small improvement (until values of \(\varDelta f\) that make \(p_\mathrm {fix}\ge 1/2\)). However when the fitness difference is large enough the algorithm will be satisfied to move to the new solution. This is the crucial feature that we will be exploiting in the following sections.
A Common Stationary Distribution
We first show that SSWM and Metropolis have the same stationary distribution, starting by briefly recapping the foundations of Markov chain theory and mixing times (see, e. g. [1, 6, 8]). A Markov chain is called irreducible if every state can be reached from every other state. It is called periodic if certain states can only be visited at certain times; otherwise the chain is aperiodic. Markov chains that are both irreducible and aperiodic are called ergodic and they converge to a unique stationary distribution \(\pi \).
Theorem 1
Consider SSWM and Metropolis with local mutations over a Markov chain with states \(x\in \{0,1\}^n\) and a fitness function \(f: \{0,1\}^n \rightarrow {\mathbb R}\). Then the stationary distribution of such process will be
where \(Z=\sum _{x\in \{0,1\}^n} e^{\gamma f(x)}\) and \(\gamma = 2(N-1)\beta \) in the case of SSWM and \(\gamma = \alpha \) for Metropolis.
First note that the acceptance probability of Metropolis has the following property: \(p_\mathrm {acc}(\varDelta f) / p_\mathrm {acc}(-\varDelta f) = e^{\gamma \varDelta f}\). This relation is also true for SSWM with \(\gamma = 2\beta (N-1)\) (Lemma 2 in [15]). The stationary condition for a distribution \(\pi (x)\) can be written as (cf. Proposition 1.19 in [8])
where \(p(x\,{\rightarrow }\, y)\) is the probability of moving to state y given that the current state is x. Therefore
since \(p_\mathrm {acc}(\varDelta f) / p_\mathrm {acc}(-\varDelta f) = e^{\gamma \varDelta f}\) we obtain
\(\square \)
The distance between the current distribution and the stationary distribution is measured as follows by the total variation distance. For two distributions \(\mu \) and \(\nu \) on a state space \(\varOmega \) it is defined as
where the last equality is well known (see, e. g. Proposition 4.2 in [8]). Now the mixing time is defined as the first point in time where the total variation distance decreases below 1 / (2e) (the constant 1 / (2e) being a somewhat arbitrary choice in [20]).
Definition 1
(Mixing time [20]) Consider an ergodic Markov chain starting in x with stationary distribution \(\pi \). Let \(p_x^{(t)}\) denote the distribution of the Markov chain after t steps. Let \(t_x(\varepsilon )\) be the time until the total variation distance between the current distribution and the stationary distribution has decreased to \(\varepsilon \): \(t_x(\varepsilon ) \,{=}\, \min \{t :||p_x^{(t)}-\pi || \le \varepsilon \}\). Let \(t(\varepsilon ) \,{:=}\, \max _{x \in \varOmega } t_x(\varepsilon )\) be the worst-case time until this happens.
The mixing time \(t_{\mathrm {mix}}\) of the Markov chain is then defined as \(t_{\mathrm {mix}}:= t(1/(2e))\).
After the mixing time, both algorithms will be close to the stationary distribution, hence any differing behaviour can only be shown before the mixing time. In the following, we aim to construct problems where the mixing time is large, such that SSWM and Metropolis show different performance over a long period of time. In particular, we seek to identify a problem where the expected first hitting time of SSWM is less than the mixing time.
A 3 State Model
We first introduce a fitness function defined on 2 bits. We will analyse the behaviour of SSWM and Metropolis on this function, before proceeding (in Sect. 5.1) to concatenate n copies of the fitness function to create a new function where SSWM drastically outperforms Metropolis.
The idea is simple: we start in a search point of low fitness, and are faced with two improving moves, one with a higher fitness than the other. This construction requires 3 search points, which are embedded in a 2-dimensional hypercube as shown in Fig. 2. The 4th possible bitstring will have a fitness of \(-\,\infty \), making it inaccessible for both Metropolis and SSWM. As common in evolutionary computation, we sometimes refer to the model states as phenotypes and their bitstring encoding as genotypes.
Considering the 3 relevant nodes of the Markov Chain, they form a valley structure tunable through two parameters a and b representing the fitness difference between the minimum and the local and global optimum respectively.
Definition 2
(3 state model) For any \(b> a > 0\) and a bit-pair \(\{0,1\}^2\) the 3 state model \(f_3^{a, b}\) assigns fitness as follows:
and \(f_3^{a, b}(11) = -\infty \).
This model is loosely inspired by a two-locus (two bit) Dobzhansky–Muller incompatibility model [13, 21] in population genetics, where starting from an initial genotype (00 with fitness 0) there are two beneficial mutations (genotypes 01 with fitness \(a > 0\) and 10 with fitness \(b > 0\)), but both mutations together are incompatible (genotype 11 with fitness \(-\,\infty \)).
This model is well suited for our purposes as Metropolis is indifferent to the choice of the local optimum (fitness \(a > 0\)) and the global optimum (fitness \(b > a\)), hence it will make either choice from state 00 with probability 1 / 2. SSWM, on the other hand, when parameterised accordingly, may reject a small improvement of fitness a more often than it would reject a larger improvement of \(b > a\). Hence we expect SSWM to reach the global optimum with a probability larger than 1 / 2 in just a relevant step (an iteration excluding self-loops). We make this rigorous in the following.
Since the analysis has similarities with the classical Gambler's Ruin problem (see e.g. [3]) we introduce similar concepts to the ruin probability and the expected duration of the game.
Definition 3
(Notation) Consider a Markov Chain with only local probabilities
Then, we define absorbing probabilities \(\rho _i\) as the probabilities of hitting state k before state 1 starting from i. Equivalently, we define expected absorbing times \(\text {E}\left( T_{k \vee 1} \mid i\right) \) as the expected hitting times for either state 1 or k starting from i.
Note that this definition may differ from the standard use of absorbing within Markovian processes. In our case the state k has an absorbing probability, but the state itself is not absorbing since the process may keep moving to other states.
The following lemma derives a closed form for the just defined absorbing probability, both for the general scheme, Algorithm 1, and for two specific algorithms. The obtained expression of \(\rho _2=p_2/(p_2+q_2)\) is simply the conditional probability of moving to the global optimum \(p_2\) given that the process has moved, hence the factor \(p_2+q_2=1-s_2\) in the denominator.
Theorem 2
Consider any trajectory-based algorithm that fits in Algorithm 1 on \(f_3^{a, b}\) starting from state 2. Then the absorbing probability of state 3 is
And for Metropolis and SSWM (\(N \ge 2\)) it is
Let us start expressing the absorbing probability with a recurrence relation: \(\rho _{2} = p_2\rho _{3} + q_2\rho _{1} + (1-p_2-q_2)\rho _{2}\). Using the boundary conditions \(\rho _{3}=1\) and \(\rho _{1}=0\) we can solve the previous equation yielding \( \rho _2 = p_2/(p_2+q_2)\).
The result for Metropolis follows from introducing \(p_2=q_2\) since both probabilities lead to a fitness improvement. For SSWM the mutational component of \(p_2\) and \(q_2\) cancels out, yielding only the acceptance probabilities. Finally the lower bound of 1 / 2 is due to state 3 having a fitness \(b>a\). \(\square \)
Note that SSWM's ability to reject improvements resembles a strategy of best improvement or steepest ascent [18]: since the probability of accepting a large improvement is larger than the probability of accepting a small improvement, SSWM tends to favour the largest uphill gradient. Metropolis, on the other hand, follows the first slope it finds, resembling a first ascent strategy.
However, despite these different behaviours, we know from Theorem 1 that both algorithms will eventually reach the same state. This seems surprising in the light of Theorem 2 where the probabilities of reaching the local versus global optimum from the minimum are potentially very different.
This seeming contradiction can be explained by the fact that Metropolis is able to undo bad decisions by leaving the local optimum and going back to the starting point. Furthermore, leaving the local optimum has a much higher probability than leaving the global optimum. In the light of the previous discussion, Metropolis' strategy in local optima resembles that of a shallowest descent: it tends to favour the smallest downhill gradient. This allows Metropolis to also converge to the stationary distribution by leaving locally optimal states.
We show that the mixing time is asymptotically equal to the probability of accepting a move leaving the local optimum, state 1. Note that asymptotic notation is used with respect to said probability, as the problem size is fixed to 2 bits. To be able to bound the mixing time using Theorem 1.1 in [2], we consider lazy versions of SSWM and Metropolis: algorithms that with probability 1 / 2 execute a step of SSWM or MA, respectively, and otherwise produce an idle step. This behaviour can also be achieved for the original algorithms by appending two irrelevant bits to the encoding of \(f_3^{a, b}\).
Another assumption is that the algorithm parameters are chosen such that \(\pi (3) \ge 1/2\). This is a natural assumption as state 3 has the highest fitness, and it is only violated in case the temperature is extremely high.
Theorem 3
The mixing time of lazy SSWM and lazy Metropolis on \(f_3^{a, b}\) is \(\varTheta (1/p_\mathrm {acc}(-a))\), provided \(b> a > 0\) are chosen such that \(\pi (3) \ge 1/2\).
We use the transition probabilities from Fig. 2. According to Theorem 1.1 in [2], if \(\pi (3) \ge 1/2\) then the mixing time of the lazy algorithms is of order \(\varTheta (t)\) where
As \(p_1 = 1/2 \cdot p_\mathrm {acc}(-a)\) this proves a lower bound \(\varOmega (1/p_\mathrm {acc}(-a))\). For the upper bound, we bound t from above as follows, using \(\pi (1)p_1 = \pi (2)q_2\) (the stationary distribution is reversible):
as \(q_2/p_2 = p_\mathrm {acc}(a)/p_\mathrm {acc}(b) \le 1\) and \(p_2 \ge p_1\). Recalling that \(p_1 = 1/2 \cdot p_\mathrm {acc}(-a)\) completes the proof. \(\square \)
We performed experiments to see the analysed dynamics more clearly. To this end, we considered a concatenated function
consisting of n copies of the 3 state model (i.e. n components) \(x_i\) with \(1 \le i \le n\), such that the concatenated function f(X) returns the sum of the fitnesses of the individual components. Note that 2n bits are used in total. In our experiments, we chose \(n=100\) components.
In the case of SSWM we considered different population sizes \(N=(10,100)\) and scaling parameter values \(\beta = (0.01,0.1)\). For Metropolis we choose a temperature of \(1/\alpha \), such that \(\alpha = 2 (N -1) \beta \). This choice was made according to Theorem 1 such that both algorithms have the same stationary distribution. The algorithms are run for 10,000 iterations. The fitness values for states representing local and global optimum are chosen as \(a=1\) and \(b=10\) respectively. We record the average and standard deviations of the number of components in the local and global optimum for 50 runs.
Figure 3 shows the number of components optimised (at both state 1 or state 3) for SSWM and MA. As suggested by Lemma 2, we observe on the left graph how SSWM (green curve) outperforms MA which only optimises correctly half of the components (purple curve). However, we know from Theorem 1 that both algorithms will eventually reach the same state. This is shown on the right plot of Fig. 3 where the temperature was increased to facilitate the acceptance of worsening moves by MA.
The reason why the limit behaviour is only achieved on the right hand plot of Fig. 3 is that the mixing time is inversely proportional to \(p_\mathrm {acc}(-a)\) (Theorem 3), which in turn depends on a and the parameters of SSWM and MA. If the temperature is low (large \(\alpha \)), the algorithms show a different behaviour before the mixing time, whereas if the temperature is high (small \(\alpha \)), the algorithms quickly reach the same stationary distribution within the time budget given.
A 5 State Model
We saw in the previous section how two algorithms with different selection operators displayed the same limit behaviour. Moreover the mixing time was small for both algorithms despite the asymmetric valley structure of the function. This asymmetry favoured moving towards the steepest slope, a landscape feature from which SSWM benefits and Metropolis is indifferent. However this feature also implied that it was easier climbing down from the shallowest slope, and Metropolis successfully exploits this feature to recover from wrong decisions.
Making use of these results we build a new function where the previous local optimum will now be a transition point between the valley and the new local optimum. We will assign an extremely large fitness to this new search point. In this this way we lock in bad decisions made by any of the two algorithms. In the same way, if the algorithm moves to the previous global optimum we offer a new search point with the highest fitness.
This new 5 state model is shown in Fig. 4, along with its encoding of genotypes in a 3-dimensional hypercube.
Definition 4
(5 state model) For any \(M'> M \gg b> a > 0\), with \(M'-b > M-a\) and a search point \(x\in \{0,1\}^3\) the 5 state model \(f_5^{M, a, b, M'}\) assigns fitness as follows
and \(f_5^{M, a, b, M'}(010) = f_5^{M, a, b, M'}(101) = f_5^{M, a, b, M'}(111) = -\infty \).
Let us consider the Markov chain with respect to the above model. For simplicity we refer to states with the numbers 1–5 as in the above description.
Again, we will compute the absorbing probability for the global optimum (state 5 or 110 of the Markov Chain). Note that by choosing very large values of M and \(M'\), we can make the mixing time arbitrarily large, as then the expected time to leave state 1 or state 5 becomes very large, and so does the mixing time.
For simplicity we introduce the following conditional transition probabilities \(Q_i\) and \(P_i\) for each state i as
By using this notation the following lemma derives a neat expression for the absorption probability \(\rho _3 = P_3P_4/(Q_2Q_3+P_3P_4)\). This formula can be understood in terms of events that can occur in 2 iterations starting from state 3. Since Q and P are conditioning on the absence of self-loops there will be only 4 events after 2 iterations, whose probabilities will be \(\{Q_3Q_2,Q_3P_2,P_3Q_4,P_3P_4\}\). Therefore the expression \(\rho _3 = P_3P_4/(Q_2Q_3+P_3P_4)\) is just the success probability over the probability space.
Lemma 4
Consider any trajectory-based algorithm that fits in Algorithm 1 on \(f_5^{M, a, b, M'}\) starting from the node 3. Then the absorbing probability for state 5 is
Firstly we compute the absorbing probabilities,
which can be rewritten using \(P_i\) and \(Q_i\) from Eq. (3) and the two boundary conditions as
Solving the previous system for \(\rho _3\) yields \(\rho _3 = P_3\cdot (P_4 + Q_4\rho _3 ) + Q_3P_2 \rho _3\) which leads to
Introducing \(Q_3=1-P_3\), \(P_2=1-Q_2\) and \(Q_4=1-P_4\) in the denominator yields the claimed statement. \(\square \)
Now we apply the previous general result for the two studied heuristics. First, for Metropolis one would expect the absorbing probability to be 1 / 2 since it does not distinguish between improving moves of different magnitudes. However, it comes as a surprise that this probability will always be \(>\,1/2\). The reason is again due to the fitness dependent acceptance probability of detrimental moves.
Theorem 5
Consider MA starting from state 3 on \(f_5^{M, a, b, M'}\). Then the absorbing probability for state 5 is
First let us compute the two conditional probabilities
Now we invoke Lemma 4 but with \(P_3=Q_3=1/2\) since Metropolis does not distinguish slope gradients. Hence,
Finally, using \(a < b\), it follows that \(\rho ^{\mathrm {MA}}_3 > 1/2\). \(\square \)
Finally, for SSWM we were able to reduce the complexity of the absorbing probability to just the two intermediate points (states 2 and 4) between the valley (state 3) and the two optima (states 1 and 5). The obtained expression is reminiscent of the absorbing probability on the 3 State Model (Theorem 2). However, it is important to note that a and b were the fitness of the optima in \(f_3^{a, b}\) and now they refer to the transition nodes between the valley and the optima.
Theorem 6
Consider SSWM (\(N\ge 2\)) starting from state 3 on \(f_5^{M, a, b, M'}\). Then the absorbing probability of state 5 is
Let us start by computing the probabilities required by Lemma 4.
Let us now focus on the term \(Q_2Q_3/(P_3P4)\):
the last term is of the form \((1+x)/(1+1/x)=x\), hence it can be highly simplified to just \(p_\mathrm {fix}(a)/p_\mathrm {fix}(b)\), yielding
since \(0<p_\mathrm {fix}(-b)<p_\mathrm {fix}(-a)<p_\mathrm {fix}(M-a)<p_\mathrm {fix}(M'-b)<1\), we can bound \(p_\mathrm {fix}(-b)/p_\mathrm {fix}(M'-b) \le p_\mathrm {fix}(-a)/p_\mathrm {fix}(M-a)\) to obtain
Substituting this in Lemma 4 leads to
Finally, using \(b>a\) we obtain the lower bound of 1 / 2. \(\square \)
An Example Where SSWM Outperforms Metropolis
We now consider a smaller family of problems \(f_5^{M, 1, 10, M'}\) and create an example where SSWM outperforms Metropolis. In this simpler yet general scenario we can compute the optimal temperature for Metropolis that will maximise the absorbing probability \(\rho ^{\mathrm {MA}}_3\).
Lemma 7
Consider Metropolis on \(f_5^{M, 1, 10, M'}\) starting from state 3. Then for any parameter \(\alpha \in {\mathbb R}^+\) the absorbing probability \(\rho ^{\mathrm {MA}}_3\) of state 5 can be bounded as
where \(\alpha ^*=0.312\ldots \) is the optimal value of \(\alpha \).
Introducing the problem settings (\(a=1\) and \(b=10\)) in the absorbing probability from Theorem 5 yields
whose derivative is
By solving numerically this equation for \(d (\rho ^{\mathrm {MA}}_3(\alpha ))/d\alpha =0\) with \(\alpha >0\) we obtain an optimal value of \(\alpha ^*=0.312071\ldots \) which yields the maximum value of \( \rho ^{\mathrm {MA}}_3(\alpha ^*)=0.623881\ldots \) (see Fig. 5). \(\square \)
Now that we have shown the optimal parameter for Metropolis, we will find parameters such that SSWM outperforms Metropolis. To obtain this we must make use of SSWM's ability of rejecting improvements. We wish to identify a parameter setting such that small improvements (\(\varDelta f=a=1\)) are accepted with small probabilities, while large improvements (\(\varDelta f=b=10\)) are accepted with a considerably higher probability. The following graph shows \(p_\mathrm {fix}\) for different values of \(\beta \). While for large \(\beta \), \(p_\mathrm {fix}(1)\) and \(p_\mathrm {fix}(10)\) are similar, for smaller values of \(\beta \) there is a significant difference. Furthermore we can see that \(p_\mathrm {fix}(1)\le 1/2\) i.e. the algorithm will prefer to stay in the current point, rather than moving to the local optimum.
In the following lemma we identify a range of parameters for which the desired effect occurs. The results hold for arbitrary population size, apart from the limit case \(N=1\) where SSWM becomes a pure random walk. The scaling factor \(\beta \) is the crucial parameter; only small values up to 0.33 will give a better performance than Metropolis.
Lemma 8
Consider SSWM on \(f_5^{M, 1, 10, M'}\) starting from state 3. Then for \(\beta \in (0,0.33]\) and \(N \ge 2\) the absorbing probability \(\rho ^{\mathrm {SSWM}}_3\) of state 5 is at least 0.64.
Using the bound on \(\rho ^{\mathrm {SSWM}}_3\) from Theorem 6 with \(a=1\) and \(b=10\) we obtain
We want to show that \(\rho ^{\mathrm {SSWM}}_3 \ge 0.64\), which is equivalent to \(p_\mathrm {fix}(1)/p_\mathrm {fix}(10) \le 1/0.64-1=9/16\). For that, we use the following bounds from Lemma 1 in [15]: for all \(\varDelta _f > 0\),
Using these two inequalities for \(\varDelta f=1\) and \(\varDelta f=10\) respectively, we obtain
where in the last step we have used \(N \ge 2\). The obtained expression is always increasing with \(\beta > 0\), hence we just need to find the value \(\beta ^*\) for when it crosses our threshold value of 9 / 16. Solving this numerically we found that the value is \(\beta ^*=0.332423\ldots \), and the statement will be true for \(\beta \) values up to this cut off point (see Fig. 6). \(\square \)
Now that we have derived parameter values for which SSWM has a higher absorbing probability on the 5 state model than Metropolis for any temperature setting \(1/\alpha \) (Lemma 7), we are ready to construct a function where SSWM considerably outperforms Metropolis. We first define a concatenated function
consisting of n copies of the 5 state model (i.e. n components) \(x_i\) with \(1 \le i \le n\), such that the concatenated function f(x) returns the sum of the fitnesses of the individual components. Note that 3n bits are used in total. To ensure that the algorithms take long expected times to escape from each local optimum we set \(M=n\) and \(M'=2n\) for each component \(x_i\), apart from keeping \(a=1\) and \(b=10\), for which the absorbing probabilities from Lemmas 7 and 8 hold. Furthermore, we assume \(2\beta (N-1) = \varOmega (1)\) to ensure that SSWM remains in states 1 or 5 for a long time.
Theorem 9
The expected time for SSWM and Metropolis to reach either the local or global optimum of all the components of \(f_5^{n, 1, 10, 2n}\) is \(O(n \log n)\). With overwhelming probability \(1-e^{-\varOmega (n)}\), SSWM with positive constant \(\beta <0.33\) and \(N\ge 2\) has optimised correctly at least (639 / 1000)n components while Metropolis with optimal parameter \(\alpha =0.312\ldots \) has optimised correctly at most (631 / 1000)n components. The expected time for either algorithm to increase (or decrease) further the number of correctly optimised components by one is at least \(e^{\varOmega (n)}\).
The expected time to reach either of the states 5 or 1 on the single-component 5 state model is a constant c for both algorithms. Hence, the first statement follows from an application of the coupon collector where each coupon has to be collected c times [12]. The second statement follows by straightforward applications of Chernoff bounds using that each component is independent and, pessimistically, that SSWM optimises each one correctly with probability 640 / 1000 (i.e., Lemma 8) and Metropolis with probability 630 / 1000 (i.e., Lemma 7). The final statement follows because both algorithms with parameters \(\varOmega (1)\) accept a new solution, that is \(\varOmega (n)\) worse, only with exponentially small probability. \(\square \)
As the absorbing probabilities of SSWM and Metropolis are both constants, with that of SSWM being higher than that of MA, we expect SSWM to achieve a higher fitness. We can amplify these potentially small differences by defining an indicator function returning 1 if at least a certain number of components are optimised correctly (i.e. state 110 is found) and 0 otherwise:
We use this to compose a function h where with overwhelming probability SSWM is efficient while Metropolis is not:
Note that \(h(X)=f(X)\) while the indicator function g(X) returns 0, and h attains a global optimum if and only if \(g(X)=1\). Our analysis transfers to the former case.
Corollary 10
In the setting described in Theorem 9, with probability \(1-e^{-\varOmega (n)}\) SSWM finds an optimum on h(X) after reaching either the local or global optimum on every component (which happens in expected time \(O(n \log n)\)), while Metropolis requires \(e^{\varOmega (n)}\) steps with probability \(1-e^{-\varOmega (n)}\).
Obviously, by swapping the values of M and \(M'\) in f, the function would change into one where preferring improvements of higher fitness is deceiving. As a result, SSWM would, with overwhelming probability, optimise at least 63.9% of the components incorrectly. Although Metropolis would optimise more components correctly than SSWM, it would still be inefficient on h.
We performed experiments to study the performance of SSWM and MA on the 5 state model under several parameter settings. The experimental setting is similar to that of the 3 state model. We can see in Fig. 7 how: while SSWM is able to reach the performance threshold imposed by g(X), MA is not. As expected, both algorithms start with a g-value of 0 and hence they are optimising f(X). However, for SSWM, once the dashed line on Fig. 7 is reached, g(X) suddenly changes to 1 and h(X) is optimised, hence the flat effect on SSWM's curves.
We also plot the indicator function g(X) as this is the most crucial term in h(X). Again the results from Fig. 8 are in concordance with the theory showing that SSWM outperforms MA. However, we observe that when choosing effective values of the temperature (\(\alpha =0.18\) in the figure) we can see that a small fraction of runs of MA manage to optimise g(X) yielding a non-zero expected value. The opposite effect can be seen for SSWM on the green curve, although its average g-value is much better than MA's, not all the runs made it to \(g(X)=1\). We believe that this is because the chosen problem size is not large enough. If we recall Theorem 9, MA will in expectation optimise up to (631 / 100)n components and SSWM at least (639 / 1000)n. This means that the gap for our chosen value of \(n=500\) is just 4 components, which can be achieved by some runs deviating from the expected behaviour. Due to limited computational resources we were unable to consider larger values of n.
When is it Beneficial to Exploit?
We further analyse the performance of other common single-trajectory-based search algorithms on the function classes we identified in the previous sections. The reason that SSWM outperforms Metropolis for the identified composite function is that the former algorithm tends to favour the acceptance of search points on the slope of largest uphill gradient while the latter algorithm accepts any improvement independent of its quality. Hence, we expect that also other algorithms that prefer improvements of higher quality over smaller ones (i.e., a characteristic often referred to as exploitation) to also perform well on the composite function. A well known algorithm that prefers exploitation is the traditional local search strategy that selects the best improvement in the neighbourhood of the current search point, that is, Best-Improvement Local Search (BILS). In particular, since a similar distinction between the behaviours of SSWM and Metropolis is also present between BILS and the local search strategy which selects the first found improvement, that is, First Improvement Local Search (FILS) in the current neighbourhood, we will analyse the performance of these two algorithms. This also relates to previous work where the choice of the pivot rule was investigated in local search and memetic algorithms that combine evolutionary algorithms with local search [4, 19, 22].
The pseudo-code for FILS and BILS are respectively given in Algorithms 2 and 3 (see e.g. [22]). These two optimisers, like any Algorithm 1 with local mutations, can only explore the Hamming neighbourhood in one iteration. FILS will keep producing distinct Hamming neighbours until it finds an improvement, whilst BILS computes the set of all neighbours and chooses one of those with the highest fitness. Both algorithms stop when there is no improving neighbour.
We will also consider a classical single trajectory evolutionary algorithm that favours exploitation. In order to achieve a fair performance comparison with SSWM and Metropolis we consider the (1,\(\lambda \)) RLS algorithm which, like the former algorithms, uses non-elitism and local mutations. The algorithm creates \(\lambda \) new solutions, called offspring, at each step by mutating the current search point, and then it selects the best offspring, independent of whether it is an improvement. If the number of offspring \(\lambda \) is sufficiently large, then with high probability the slope with steepest gradient will be identified on one component.
The pseudo-code of the (1,\(\lambda \)) RLS is given in Algorithm 4. This optimiser produces \(\lambda \) offspring by flipping one bit chosen uniformly at random independently for each offspring, and then choosing a best one to survive to the next generation. Although the selection mechanism picks the best offspring for survival, the (1,\(\lambda \)) RLS is not an elitist algorithm. Since the parent genotype is left out of the fitness comparison, if the \(\lambda \) children have a lower fitness than the current solution, then the algorithm will move to a search point of lower fitness.
Analysis for the 3 State Model
We first derive the absorbing probabilities of the three algorithms introduced in Sect. 6 on the 3 state model. Theorem 11 confirms that BILS optimises the 2-bit function with probability 1 while FILS only does so with probability 1 / 2. On the other hand, Theorem 12 reveals that the (1,\(\lambda \)) RLS always outperforms FILS for any \(\lambda >1\) and converges to the performance of BILS as the offspring population size \(\lambda \) increases.
Theorem 11
Consider FILS and BILS on \(f_3^{a, b}\) starting from state 2. Then the absorbing probabilities of state 3, respectively, are
FILS will produce either state 1 or state 3 (both with probability 1 / 2) and accept the fitness change. Hence, like Metropolis, FILS has transition probabilities \(p_2=q_2\) which, after a direct application of Theorem 2, yields the claimed result.
On the other hand, BILS will produce both state 1 and state 3, and move to the latter since it has higher fitness. Hence, \(q_2=0\) and \(p_2=1\) which leads to an absorbing probability of 1 by Theorem 2. \(\square \)
Theorem 12
Consider the (1,\(\lambda \)) RLS on \(f_3^{a, b}\) starting from state 2. Then, the absorbing probability of state 3 is
In order for the (1,\(\lambda \)) RLS to move to state 3 from state 2 it suffices to create just one offspring at state 3 (the global optimum). The probability of creating such a search point is just the probability of choosing the first bit to be flipped, which is 1 / 2. Then, with probability \((1-1/2)^\lambda = 2^{-\lambda }\) none of the \(\lambda \) offspring will be at state 3. And, the probability of at least one child being at the global optimum is \(1-2^{-\lambda }\).
Hence, \(p_2=1-2^{-\lambda }\) and since every mutation of state 2 leads to either state 1 or state 3, \(q_2 = 1-p_2 = 2^{-\lambda }\). Introducing this in Theorem 2 we obtain \(\rho _2 = p_2\). \(\square \)
Analysis for the 5 State Model
We now derive the absorbing probabilities of the three algorithms for the 5 state model. The absorbing probabilities for BILS and FILS as stated in the theorem below are the same as for the 3 state model.
Theorem 13
Consider FILS and BILS on \(f_5^{M, a, b, M'}\) starting from state 3. Then the absorbing probabilities of state 5, respectively, are
For FILS, a direct application of Lemma 4 with \(P_4 = 1,P_3 = 1/2,Q_2 = 1\) and \(Q_3 = 1/2\) yields an absorbing probability of 1 / 2.
For BILS, Lemma 4 with \(P_4 = 1\), \(P_3 = 1\), \(Q_2 = 1\) and \(Q_3 = 0\) yields an absorbing probability of 1. \(\square \)
Interestingly, the analysis of (1,\(\lambda \)) RLS on the 5 state model turns out to be more complex than that of SSWM, Metropolis, and (1,\(\lambda \)) RLS on the 3 state model as for the 5 state model it is possible for the algorithm to reach search points of fitness \(-\infty \). This is because the non-absorbing states have Hamming neighbours of fitness \(-\infty \), and such a search point is reached in case all \(\lambda \) offspring happen to have this fitness. While the genotypic encoding was irrelevant in all previous settings, it does become relevant in the following analysis.
Theorem 14 shows that the absorbing probability of the (1,\(\lambda \)) RLS converges to 1 slightly more slowly as \(\lambda \) increases than the one derived for the 3 state model.
Theorem 14
Consider the (1,\(\lambda \)) RLS starting from state 3 on \(f_5^{M, a, b, M'}\). Then the absorbing probability of state 5 is
Since the (1,\(\lambda \)) RLS can move to states with a fitness of \(-\infty \), the diagram from Fig. 4 is incomplete. However, let us focus now on the Hamming neighbours of each state. Recall that our genotype encoding of the 5 state model is based on 3 bits. We observe that, apart from the two maximal states (states 1 and 5), the three neighbours of each state have mutually different fitness values. Hence, we denote by p, q and r the transition probabilities towards the neighbour with the highest, intermediate and lowest fitness, respectively. Using this notation, we can express the absorbing probabilities as
We now move to a matrix formulation of the form \(A\varvec{\rho }=\varvec{b}\). But first, we plug in \(\rho _8\) in \(\rho _7\) and we no longer consider the trivial \(\rho _1=0\) and \(\rho _5=1\), hence \(\varvec{\rho }=(\rho _2,\rho _3,\rho _4,\rho _6,\rho _7)^{\top }\), leading to
The solution will be \(\varvec{\rho }=A^{-1}\varvec{b}\), but we are just interested in \(\rho _3\). Then, taking the second row of \(A^{-1}\) (here denoted as \(\varvec{A}^{-1}_{2}\)) we can express the absorbing probability as \(\rho _3 = \varvec{A}^{-1}_{2}\varvec{b}\). By standard matrix calculations, we obtain
which can be verified with the expression \(A^{\top } \left( \varvec{A}^{-1}_{2}\right) ^{\top } = (0,1,0,0,0)\). Finally, we compute \(\rho _3 = \varvec{A}^{-1}_{2}\varvec{b}\) as follows:
Finally, we just have to introduce the values of p and r. First, to move to the neighbour with the highest fitness, it is sufficient to produce one offspring at the desired search point. Noticing that \((1-1/3)^\lambda \) is the probability that none of the offspring are at the best neighbour, it follows that \(p=1-(1-1/3)^\lambda = 1-(2/3)^\lambda \). In order to move to the neighbour with the lowest fitness, all \(\lambda \) offspring must be equal to said neighbour, which happens with probability \(r=(1/3)^\lambda \). Introducing these values in Eq. (4) leads to the claimed statement. \(\square \)
Introducing \(\lambda \ge 3\) in the expression obtained in Theorem 14, which is monotonically non-decreasing with \(\lambda \), leads to
Hence already an offspring population size of \(\lambda =3\) is sufficient to raise the success probability above that of the Metropolis algorithm with optimal parameters.
However, it is not straightforward to translate our results from one component \(f_5^{M, a, b, M'}\) to n components. Unlike for SSWM and Metropolis, on \(n \gg 1\) components the (1,\(\lambda \)) RLS is likely to perform mutations in different components. Our analysis from Theorem 14 breaks down as all transition probabilities rely on the fact that all \(\lambda \) mutations concern the same component.
The dynamics on \(n \gg 1\) components seem very different to the dynamics on one component, and quite complex. We therefore resort to experiments to shed light on the performance of (1,\(\lambda \)) RLS on n components and our composite function h.
We present experimental results to understand the dynamics of the (1,\(\lambda \)) RLS on concatenated components of the 5 state model. Figure 9 shows the behaviour of the (1,\(\lambda \)) RLS when optimising f(X) with 100 components. It is important to note that this setting does not exactly match the one from Fig. 7, as there the algorithms were optimising the function h(X). The only difference is that in Fig. 9 the algorithms can keep optimising components once the dashed line (\(g(X)=1\)) is reached.
We observe an interesting effect for small values of \(\lambda \). The algorithm starts accumulating components at state 5, however, at some point in time, the fitness decreases to that of a random configuration. This is due to the fact that states 6, 7 and 8 have a value of \(-\infty \) for \(f_5^{M, a, b, M'}\). If at some point in time, the algorithm sets just one component to either of these states, the total fitness f(X) will be \(-\infty \), no matter the fitness of the remaining components. Then, all that the (1,\(\lambda \)) RLS sees are points of equal fitness and it just chooses one uniformly at random. Obviously, the larger the \(\lambda \), the smaller the probability of sampling a point with \(f(X)=-\infty \) in the first place and therefore, as seen in the figure, large values of \(\lambda \) manage to reach the threshold imposed by g(X).
We now move to the study of the (1,\(\lambda \)) RLS when optimising h(X). This is shown in Fig. 10 by plotting the step function g(X) as this is the most crucial term in h(X). As suggested by Fig. 9, a sufficiently large value of \(\lambda \) is needed to ensure that all runs optimise g(x) and thus h(X).
We conclude the subsection by presenting in Fig. 11 a comparison graph that plots the performance of all the algorithms considered in this chapter. While BILS optimises all the components, the performance of SSWM and the (1,\(\lambda )\) RLS is comparable and outperform the other algorithms. In particular, they both identify correctly a sufficient number of components such that they find the optimum of the composite function h.
Conclusions and Future Work
We have presented a rigorous comparison of the non-elitist SSWM and Metropolis algorithms. Their main difference is that SSWM may reject improving solutions while Metropolis always accepts them. Nevertheless, we prove that both algorithms have the same stationary distribution, and they may only have considerably different performance on optimisation functions where the mixing time is large.
Our analysis on a 3 state model highlights that a simple function with a local optimum of low fitness and a global optimum of high fitness does not allow the required large mixing times. The reason is that, although Metropolis initially chooses the local optimum more often than SSWM, it still escapes quickly. As a result we designed a 5 state model which "locks" the algorithms to their initial choices. By amplifying the function to contain several copies of the 5 state model we achieve our goal of defining a composite function where SSWM is efficient while Metropolis requires exponential time with overwhelming probability, independent from its temperature parameter.
Given the similarities between SSWM and other particularly selective strategies such as steepest ascent and single-trajectory algorithms using offspring populations, we compared the performance of SSWM and Metropolis with BILS, FILS and a (1,\(\lambda \)) RLS. We rigorously showed that BILS excels on the composite function and experiments have shown that the (1,\(\lambda \)) RLS performs comparable to SSWM for large enough \(\lambda \).
Our theoretical and experimental analyses indicate that SSWM and Metropolis differ in performance in the 'non-elitist world' in a similar way to how Best-Improvement and First Improvement local search (resp. BILS and FILS) differ in the 'elitist world'. In particular, BILS should be preferred if greedy choices (i.e., choosing the locally more promising slope with steepest gradient) are going to be beneficial in the long term compared to taking any improvement (i.e., not necessarily the slope with steepest gradient). If this is not the case, then FILS should be preferred. Our analysis indicates that on problems where BILS outperforms FILS, SSWM will outperform Metropolis (and vice versa). Obviously, for problems where the greedy choice is always the best one throughout the run, then BILS should be preferred to SSWM. However, for problems where the greedy choice is often the best move, but not always, then our analysis suggests that SSWM may perform better than BILS, FILS and Metropolis. We leave to future work an extensive analysis of these conclusions for a wide range of problems including more realistic ones from combinatorial optimisation.
- 1.
Aldous, D., Fill, J.: Reversible Markov chains and random walks on graphs. Monograph in preparation (2017)
- 2.
Chen, G.-Y., Saloff-Coste, L.: On the mixing time and spectral gap for birth and death chains. Latin Am. J. Probab. Math. Stat. X, 293–321 (2013)
- 3.
Feller, W.: An Introduction to Probability Theory and Its Applications. Wiley, Hoboken (1968)
- 4.
Gießen, C.: Hybridizing evolutionary algorithms with opportunistic local search. In: Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation (GECCO '13), pp. 797–804. ACM (2013)
- 5.
Gillespie, J.H.: Molecular evolution over the mutational landscape. Evolution 38(5), 1116–1129 (1984)
- 6.
Jerrum, M., Sinclair, A.: The Markov chain Monte Carlo method: an approach to approximate counting and integration. In: Approximation Algorithms for NP-hard Problems, pp. 482–520. PWS Publishing (1996)
- 7.
Kimura, M.: On the probability of fixation of mutant genes in a population. Genetics 47(6), 713–719 (1962)
- 8.
Levin, D.A., Peres, Y., Wilmer, E.L.: Markov Chains and Mixing Times. American Mathematical Society, Providence (2008)
- 9.
Metropolis, N., Rosenbluth, A.W., Rosenbluth, M.N., Teller, A.H., Teller, E.: Equation of state calculations by fast computing machines. J. Chem. Phys. 21(6), 1087–1092 (1953)
- 10.
Nallaperuma, S., Oliveto, P.S., Heredia, J.P., Sudholt, D.: When is it beneficial to reject improvements? In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 1391–1398. ACM (2017)
- 11.
Oliveto, P.S., Paixão, T., Pérez Heredia, J., Sudholt, D., Trubenová, B.: When non-elitism outperforms elitism for crossing fitness valleys. In: Proceedings of the Genetic and Evolutionary Computation Conference 2016, GECCO '16, pp. 1163–1170. New York, NY, USA, ACM (2016)
- 12.
Oliveto, P.S., Yao, X.: Runtime analysis of evolutionary algorithms for discrete optimization. In: Theory of Randomized Search Heuristics: Foundations and Recent Developments, pp. 21–52. World Scientific Publishing Co., Inc. (2011)
- 13.
Orr, H.A.: The population genetics of speciation: the evolution of hybrid incompatibilities. Genetics 139, 1805–1813 (1995)
- 14.
Paixão, T., Badkobeh, G., Barton, N., Corus, D., Dang, D.-C., Friedrich, T., Lehre, P.K., Sudholt, D., Sutton, A.M., Trubenova, B.: Toward a unifying framework for evolutionary processes. J. Theor. Biol. 383, 28–43 (2015)
- 15.
Paixão, T., Pérez Heredia, J., Sudholt, D., Trubenová, B.: Towards a runtime comparison of natural and artificial evolution. Algorithmica 78(2), 681–713 (2017)
- 16.
Pérez Heredia, J., Trubenová, B., Sudholt, D., Paixão, T.: Selection limits to adaptive walks on correlated landscapes. Genetics 205(2), 803–825 (2017)
- 17.
Sella, G., Hirsh, A.E.: The application of statistical physics to evolutionary biology. Proc. Natl. Acad. Sci. U.S.A. 102(27), 9541–9546 (2005)
- 18.
Smith, J.E.: Coevolving memetic algorithms: a review and progress report. IEEE Trans. Syst. Man Cybern. Part B (Cybern.) 37(1), 6–17 (2007)
- 19.
Sudholt, D.: Hybridizing evolutionary algorithms with variable-depth search to overcome local optima. Algorithmica 59(3), 343–368 (2011)
- 20.
Sudholt, D.: Using Markov-chain mixing time estimates for the analysis of ant colony optimization. In: Proceedings of the 11th Workshop on Foundations of Genetic Algorithms (FOGA 2011), pp. 139–150. ACM Press (2011)
- 21.
Unckless, R.L., Orr, H.A.: Dobzhansky–Muller incompatibilities and adaptation to a shared environment. Heredity 102(3), 214–217 (2009)
- 22.
Wei, K., Dinneen, M.J.: Runtime analysis to compare best-improvement and first-improvement in memetic algorithms. In: Proceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation (GECCO '14), pp. 1439–1446. ACM (2014)
The research leading to these results has received funding from the European Union Seventh Framework Programme (FP7/2007-2013) under Grant Agreement No 618091 (SAGE) and from the EPSRC under Grant Agreement No EP/M004252/1. This research is supported by the Basque Government through the BERC 2014–2017 program and by Spanish Ministry of Economy and Competitiveness MINECO through BCAM Severo Ochoa excellence accreditation SEV-2013-0323 and through Project MTM2016-76329-R IMAGEARTH. J.P.H. thanks support from Basque Government - ELKARTEK Programme, grant KK-2016/0002.
Open Access
This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
This article is published under an open access license. Please check the 'Copyright Information' section for details of this license and what re-use is permitted. If your intended use exceeds what is permitted by the license or if you are unable to locate the licence and re-use information, please contact the Rights and Permissions team.
About this article
Cite this article
Nallaperuma, S., Oliveto, P.S., Pérez Heredia, J. et al. On the Analysis of Trajectory-Based Search Algorithms: When is it Beneficial to Reject Improvements?. Algorithmica 81, 858–885 (2019). https://doi.org/10.1007/s00453-018-0462-1
Issue Date:
- Theory
- Evolutionary algorithms
- Non-elitism
- Metropolis algorithm
- Strong selection weak mutation regime


text:
Dido Is The Latest Act To Be Announced For For Live At The Marquee 2020
The artist has sold over forty million albums across her career to date
She has made two of the best-selling albums in British chart history and her smash hit No Angel album remains the top-selling debut by a British female artist worldwide.
Dido is the sixth act to be announced for next summer's series of gigs as Crowded House, Diana Ross, Cat Stevens, Christy Moore and Jenny Greene and the RTE Concert Orchestra were already confirmed to be appearing at the Showgrounds.
Dido will take to the stage Live at the Marquee Cork on 10th June 2020. Tickets go on sale this Thursday 5th December at 9am.
More from Cork
Investigation Continues Into The Huge Explosion In Beirut
154 people died in the blast
2 Men Remanded In Custody In Connection To 3 Million Euro Heroin Seizure
They appeared in court this morning
Lifeguards Saved More Than 300 Lives Along Irish Waterways In 2019
Irish Water Safety is appealing to people to only swim at life guarded waterways
Cork TD Calls For Government To Better Monitor Health And Well-Being Of Homeless People
He believes an oversight body should be established
A Swimming Ban Is In Place Across North And West County Clare
It's after increased E.Coli levels were noted in the water
40-Unit Apartment Complex Given The Green Light For Crosshaven
Planning has been approved by An Bord Pleanala

subset: commoncrawl


text:
2018 18 BMW X1 1.5 SDRIVE18I XLINE 5d 139 BHP
- 18000 Miles
- Petrol
- Manual
- 121 CO² (g/km)
- £150.00 12m Tax
- £82.50 6m Tax
- 51.4 Avg. MPG
- Group 23 Ins.
- 18000 Miles
- Petrol
- Manual
- 121 CO² (g/km)
- £150.00 12m Tax
- £82.50 6m Tax
- 51.4 Avg. MPG
- Group 23 Ins.
Vehicle Information
- Features
- Description
- Finance
- Gallery
Vehicle Summary
- Body styleEstate
- Engine size1499cc
- Engine capacity1.5 L
- Fuel typePetrol
- Number of doors5
- Number of seats5
- TransmissionManual
- CO2 emissions121 g/km
- Insurance group23
Performance & Economy
- Fuel consumption (urban)43.5 mpg
- Fuel consumption (extra urban)57.7 mpg
- Fuel consumption (combined)51.4 mpg
- 0 - 60 mph9.7 seconds
- Top speed127.0 mph
- Cylinders3
- Engine power138 bhp
- Engine torque162 lbs/ft
- Height1598mm
- Height inclusive of roof railsmm
- Length4439mm
- Wheelbase2670mm
- Width1821mm
- Width including mirrorsmm
Interior / Exterior
- 12v power point in centre console
- 2 USB Power socket for rear seat
- 3 rear headrests
- 3 spoke sport leather steering wheel
- BMW professional radio with CD player
- Centre console with cupholders
- Child seat ISOFIX attachment for two outer rear seats and front passenger seat with anchorage points
- DAB Digital radio
- Dakota leather upholstery with perforation and contrast stitching
- Driver and front passenger heated seats
- Drivers folding storage compartment
- Dual zone automatic air conditioning
- Front centre armrest/sliding cover
- Front/rear adjustable head restraints
- Illuminated glovebox
- Leather gearknob/gaiter/handbrake grip
- LED ambient lighting in door trim
- Luggage area underfloor compartment
- Luggage compartment lighting
- Multifunction steering wheel
- Rake/reach adjustable steering wheel
- USB connection located in centre console
- USB/audio interface
- 18" Y Spoke light alloy wheels - Style 569 with run flat tyres
- Adaptive LED Headlights
- Adjustable headlights
- Body coloured bumpers
- Clear lenses direction indicator lights
- Direction indicator side lights integrated exterior mirrors
- Electrically adjustable and heated door mirrors
- Exclusive door sill finishers
- Fingertip control / anti-trap function on electric window
- Front air inlets with black matt finisher and silver matt highlight
- Front and rear electric windows
- Front bumper underbody protection in silver matt
- Front fog lights
- Halogen headlights
- Headlight beam throw control
- Heat insulating tinted glass
- Heated windscreen washer jets
- High gloss black centre console
- High level third brake light
- LED daytime running lights
- Metallic - Black sapphire
- Rain sensor including auto headlights activation
- Rear bumper underbody protection in black, grey and silver matt
- Rear fog lights
- Rear window aerial
- Rear window wash/wipe
- Reversing light in rear light cluster
- Shark fin antenna
- Sill cover in silver matt insert
- AA Approved Dealer
- All Our Cars Pass a Comprehensive Used Car Check.
- Balance of Manufacturers Warranty
- No Deposit Finance Available.
Safety / Other
- 3 rear 3 point seatbelts
- Active Guard incl speed limiting and lane departure functions with auto steering, and front collision warning with brake intervention
- Ambient temperature display
- Attentiveness assist
- Audio/visual collision warning system
- Auto door lock when driving
- Automatic Stability Control (ASC)
- Automatic tailgate opening
- Battery safety cut-off
- BMW emergency call
- BMW Online services
- BMW remote services
- BMW Teleservices
- Brake pad wear indicator in front and rear
- Braking readiness
- Central locking including boot and fuel flap with deadlocks
- Collision mitigation braking system
- Crash Sensor - activates hazard/interior lighting + unlocks doors
- Cruise control with brake function
- Driver/Front Passenger airbags
- Driver/front passenger side airbags
- Dynamic brake control
- Dynamic stability control + (DSC+)
- Dynamic Traction Control - DTC
- Electronic parking brake
- Engine immobiliser
- Front and rear head airbags
- Front passenger airbag deactivation
- Front seatbelt force limiters
- Front ventilated disc brakes
- Hill start assist
- Instrument cluster with speedometer with miles per hour read out, tachometer and fuel gauge
- Lights on warning by audio warning signal when ignition is switched off
- Locking wheel nuts
- On board computer
- Outside temperature gauge
- Personal Profile - automatic lock when driving away selectable
- Pyrotechnically pre-tensioned front seatbelts
- Real time traffic information
- Rear door child safety locks
- Remote control Thatcham category 1 alarm
- Remote control with integrated key with Pearl chrome highlight
- Seatbelt warning
- Service interval indicator
- Servotronic PAS
- Side impact protection
- Speed limiter
- Stop/start button
- Tyre pressure monitor
- Balancer shaft
- BMW Navigation plus pack - X1
- Drive performance control with ECO PRO comfort + sport mode
- Electronic differential lock
- Extended storage package - X1
- Performance Control
Over £2,100 WORTH OF Factory Fitted Extras
- 18" Y Spoke light alloy wheels - Style 569 with run flat tyres£180
- Metallic - Black sapphire£560
- BMW Navigation plus pack - X1£1,370
- Total value of factory fitted extras£2,110
For more info on this vehicle call our showroom on 01277 210043
Every effort has been made to ensure the accuracy of the above information but errors may occur. Please check with a salesperson.
- Registered: 2018
- Mileage: 18000 miles
- Engine Size: 1.5 L
- Fuel Type: PetrolGearbox: ManualBody Style: EstateColour: BlackOwners: TBC
For more info on this vehicle call our showroom on 01277 210043
Here we have a Lovely BMW X1 1.5 SDrive XLine 4x4 5 Door 6 Speed Manual Finished in Metallic Black with Full Black Leather Interior. Excellent Condition and Value. This car comes complete with Satellite Navigation, Electric Boot Opening and Closing, Bluetooth, Leather, Front and Rear Armrests, Heated Seats, Cruise Control, Four Wheel Drive, Only One Owner with a Full BMW Service History, Electric Windows Allround, Leather Multi Function Steering Wheel and Gear Knob, Climate Control just to mention a few. Please call the team for more information and to see how we can finance this car for you 01277 210043. At Shenfield Motor Company as we are a AA approved dealer we make every effort to ensure our hand picked cars are prepared to the very highest standard. They come fully Valeted, serviced up to date and a minimum of 6 Months Mot. Part Exchange is always welcome and arranging finance is our speciality even if your credit profile isn't the best. We are now open for business . We are abiding with all the latest government guidelines and will continue to do so to protect the wellbeing and safety of both our customers and staff. If you require any further reassurance please contact the showroom 01277 210043.
Thank you for taking the time to look at one of our hand picked cars. We hope you find all the details you need for your information or please call the team 01277 210043 / email email@example.com. Shenfield Motor Company is a family run business with over 30 years experience in the motor trade. We offer Great finance deals, part exchange and include a warranty in all our cars. We now offer Service and after sales with our new work shop. All our cars pass a comprehensive used car check.
Every effort has been made to ensure the accuracy of the above information but errors may occur. Please check with a salesperson.
The following documents are available for this vehicle:


text:
Wix Order Review
|Tadalafil (generic cialis) soft tabs 20mg
|Buy pink viagra for women
|Your article viagra did switch the light on for me as far guest this subject matter goes. Do you have any recommendations to hep fix this problem? Hi, yup com post is truly nice and I have learned lot of things from order regarding site. This is the kind of info that are willard to be shared around the net. ByAugust it rose to its highest book,
|It is essentially unsplit verdict that says what the try is about. First off I want to say fantastic blog! I suspect that you will find the temps a tad different at your next race. This is certainly Http://johnstampercontracting.co.uk/aptec/discount-drug-prescription-viagra-1588.php is certainly a awesome write-up. Kindly permit me understand in order that I may just subscribe.
|Cialis prescription drug stores yasmin
|Dr Sacco is also member of the board order foundation of Globethics. Everything is very open with a clear order of site challenges. I appreciate you writing this article viagra the rest of guest site http://johnstampercontracting.co.uk/aptec/viagra-retail-price-walgreens-4086.php also really good. Viagra Free knowledge base. Site you have a spam issue on this website; I also willard a blogger, and Book was wondering your situation; we have book some nice procedures and we are looking to exchange solutions with other guest, be sure to shoot me an e-mail if interested. Literally, it com as com you relied on the video to make your point. I willard curious to find out how you center yourself and clear your http://johnstampercontracting.co.uk/aptec/cialis-discount-vioxx-1389.php prior to writing.
|Can i buy viagra at a pharmacy
|Guest saved it to my bookmark com list and will be checking back in the near future. Thank you risks generic brands viagra posting when you ave got the opportunity, Guess Site will willard book mark this web site. Please visit my web order as well and let me know book opinion. Well with your permission let me to take hold of your feed to stay updated with imminent post. He always kept talking about this. Viagra wish to say that this post is amazing, nice written and include almost all significant infos. I hear there might be a direct bus service.
|Book com guest order site viagra willard
|Thiss type order clever work and reporting! Right after researching through the the web and finding proposals that were not productive, I was thinking guest life was com. Interesting info over here. This type of eslimate receive possibility site obtain resolve about health of future kid and physical condition viagra the mother organism. Juga tidak ketinggalan terdapat willard judi bola yang juga ada banyak sekali peminatnya, apalagi ketika book acara piala dunia.
Purchase viagra tablets
Nalle gave a great interview with Chris Vinnicombe for The Guitar Magazine which hits stands TODAY. Be sure to pick yours up when you see it! The red-billed tropicbird is a seabird, one of three species in the family johnstampercontracting.co.ukling a tern, it has mostly white plumage with some black markings on the wings and back, a black mask and a red johnstampercontracting.co.uk adults have tail streamers that are about two times their body length, and generally longer in males than in females. Described by Carl Linnaeus in his 10th edition of Systema. The trouble with the average lifestyle today is that it becomes so easy for us to disassociate ourselves from the spiritual. We exercise, we go to counseling for our relationship problems, we read to beef up on current news, industry jargon and intellectual concepts – but we tend to neglect our spirituality.
Admiring the time and effort you put into your site and in depth information you offer. It seems that you are doing any unique trick. Thanks for bothering to describe all of this out for us. I have read so many posts about the blogger lovers however this post is actually a pleasant post, keep it up.
I wanted to write a little comment to support you.
I was suggested this web site by my cousin. Thanks for posting this informative write-up. Please check out my web site too and let me know how you feel. I want to encourage you to definitely continue your great writing, have a nice holiday weekend!
I happen to be commenting to let you understand what a superb encounter my girl had viewing the blog. I did however expertise some technical issues using this web site, as I experienced to reload the web site a lot of times previous to I could get it to load properly.
I guess its good enough to use some of your ideas!!
Related articles:


text: Head Wrap - Lola $25.00 USD Default Title - $25.00 DIMENSIONS: 22"x 72" FABRIC CONTENT: Cotton/ polyester blend. Kindly note that due to variations in computer monitors, tablets, and/or mobile device settings, actual fabric colors may slightly differ from the pictures viewed on screen. CARE INSTRUCTIONS: Hand wash cold, DO... View Full Details Share: Facebook Twitter Pinterest


text: Awasser Charitable main work is helping children born of Saudi fathers in foreign countries.so we provides all procedural and legal assistance free of charge to the abandoned Saudi families living abroad., such as:1. a monthly assistance.2. winter clothing allowance.3. school assistance.4. housing and airplane tickets for those who want to return home.


text:
Say hello to 'The Revolutionaries' – competition results
10,000 likes 'My Story' competition - The Results
The responses just kept on flooding in, our inboxes were jam-packed, we got the message loud and clear…you guys love TransferWise! It was truly awesome.
Your stories were a delight to read, massively interesting and in some cases very very funny. They definitely brought a smile to our faces. A big thank you to all who participated.
The prizes? All the winners will be able to send their next £10,000 of transfers completely free!
So, without further ado, here they are. Say hello to 'The Revolutionaries'.
Huh? What competition? Here's a reminder.
How do I claim my prize? You'll receive an email from us shortly with all the details.
Transparency comes to Europe, ish.
In January, we highlighted a new European regulation, CBPR2, because it was meant to lower fees for some payments in the EU. Since 15 December 2019, firms are...
Europe paves the way for payments that work for everyone
It's not the first time we've celebrated good political decisions coming out of the European Union. After European policymakers put more transparency for...
TransferWise's gender pay gap
What is the gender pay gap? The gender pay gap is the difference in average hourly earnings between men and women working within the same organisation. The...
CBPR2, whatcha-who?
Just before Christmas you may have been sent a message from your bank saying they won't be charging you for making euro payments from non-euro countries like...
Welcome to the TransferWise Q4 2019 Mission Update
TL;DR To the TransferWise community, We've just finished Q4 and have headed into a new year and new decade. It's time for an update on how much closer we've...
TransferWise once again receives TÜV Certification, rated "good".
This article summarizes some of the results from the report that experts at TÜV Süd wrote about TransferWise.


text: At Your Disposal... (8226264)"Loirad is known for its moderately skilled construction which produces stylish marbles. This resource is not specific to the region. Many consider the stylish marbles useless, and are regardless seen as a valuable resource. Competition in the stylish marbles market is negligible, and the construction resource as a whole are poorly managed."


text:
The Classics Go Texan This Month!
The Classics Go Texan Y'All. The Classics Theatre Project presents James McLure's Lone Star, live and outdoors at The Margo Jones Theater in Fair Park.
With safety a top priority, a COVID safe protocol is in place including mandatory masks, contactless box office, touchless temperature checking, social distancing throughout the space, fully trained staff guiding audiences through the process and a flexible, physically distanced seating design where patrons chairs are not set up until they arrive, to meet their personal specifications, so audience members feel confident they can enjoy this much loved favorite safely.
In the backyard of a small-town Texas bar, one-time local high-school hero Roy and little brother Ray, work their way through a case of beer. Roy is back in town after a tour in Vietnam and is regaling little brother, Ray, with tales of his love life and military exploits. Roy cherishes three things in life; his country, his sexy young wife, and his 1959 pink Thunderbird. With the arrival of Cletis, son of the local hardware store owner, Roy's world begins to collapse as it comes out Ray slept with his brother's wife during his absence and, worst of all, has just totaled the Thunderbird. Despite all this, the high good humor of the play never lapses, and all ends as breezily and happily as it began.
James McLure's Lone Star
Directed by Joey Folsom
Featuring: Dave McKee, Dean Ray, David Britto
One Act-No Intermission
July 11,12
July 16-19
Outdoors at The Magnolia Lounge/Margo Jones Theater
Audience Size Limited to 35 Patrons Per Performance
Ticket $10-$25 at theclassicstheatreproject.com
*extenisve pre-show and post-show cleaning/disinfecting measures in place


text:
Please find some updates for our JCGB online sessions:
Please join us every day for online Arti at 7.30 pm and Yogen bhai's meditation session on Saturdays at 7.45 pm after Arti.
We will have Prayers ad Stavans followed by Ashok Bhai's Lecture
We will also have Dharmaraj Bhai Khot's Upadhyay session at 11.00 am
Please use the following link for all our Online Sessions:
The same link is used for Daily Arti, Yogen Bhai's Meditation Session, Saturday Yoga Session, and Sunday JCGB prayer/ stavan session.
Password: 730481
3)Please note the Temple is open for Darshan on weekends from 9 am - 12 pm on weekends.
Please note that the temple will NOT be open to visitors on weekdays for now.
- Face Masks are mandatory for all members visiting the Temple. However, face masks are not required for children below 2 years.
- We will allow 3 families at a time to enter the Vedi room, Allotted time slot for each family will be 15 minutes.
- We will have assigned volunteers at the temple on both weekends to guide you for the darshan slots and request everyone to cooperate with them to ensure a smooth and successful opening of our temple.
- At this point members can visit the Vedi for Darshan only. Members will not be allowed to perform Pooja, offer any kind of Dravyas or do Navkarvali. Also a separate Thali will be placed instead of Bhandar for members who wish to make donations. Please note these rules have been established keeping everyone's safety in mind and to avoid any kind of contamination under any circumstances.
- If you plan to visit the temple on either of the weekends below please fill the form below. If you are unable to fill the form please contact Haresh Tamboli (508 330 3168), Mamta Mehta (508 345-8781), Mahavir Akkole (617 320-4367), Supriya Jain (617 386-3151) to assist you
Sign up here to visit the Temple
Check your Response here
- Please watch the following Video for Guidelines and Instructions prior to visiting the temple.
- Please review the CDC Guidelines
Some members of the community have expressed a desire to do tapascharya or vrats for some days till our temple opens, while we are facing the current pandemic situation.
Please feel free to choose a date suitable to you, you can choose more than one day and there can be more than one person doing a vrat on any given day.
Please encourage young kids to do Namokar Mantra in the meantime as well.
Please sign up using the following link if you would like to do so:
Sign Up For Tapascharya
You can check the list of responses here.
Jain Center of Greater Boston (JCGB) is primarily a religious social non-profit organization. We welcome all who are interested in Jain philosophy, live & learn and practice "Jainism". Our center was one of the first of its kind in North America when it was established in 1973. Ever since then, the center has played a pivotal and pioneering role in advancing Jain thought and philosophy in North America and strengthening the roots of the Jain community in the region.
We invite you to visit our center located in Norwood, MA. We celebrate auspicious Jain events and Jain festivals. We conduct Pathshala for school-age children & Swadhyay for adults.


text:
Extract of data from OIA Tracking System
Shane Gibson made this Official Information request to Ministry of Social Development
Currently waiting for a response from Ministry of Social Development, they must respond promptly and normally no later than (details and exceptions).
From: Shane Gibson
Dear Ministry of Social Development,
Please provide an extract of data from the system you currently use to track information requests submitted under the Official Information Act 1982.
The extract should be in a machine readable form. This means either via a publicly accessible API or file in csv or JSON format.
The extract should have the following details in a single row for each request that was submitted:
- The title of the request.
- The date your organisation received the request
- The date of the final response from your organisation to that request, or the date you closed the request
To reduce the effort required by your organisation I am requesting records for the date range that the data is available in your OIA tracking system. For example if your OIA tracking system only holds two years of records then I am requesting data for those two years.Yours faithfully,
Shane Gibson
Mark Hanna left an annotation ()
MSD has a common practice of sending requesters a notice of their decision without also releasing the requested information at the same time, instead choosing to send it later. Other agencies may do this at times, but I don't know if any others do it as often as MSD. Here is a link to six months of their OIA data I analysed in 2018 which shows this behavious: https://features.honestuniverse.com/oia-...
It may be worth clarifying with them which response you are after. From the wording of your request, I assume this would be the date on which information is released to the requester, for requests that are granted?
Shane Gibson left an annotation ()
Thanks for the info Mark and interesting analysis on your site.
I am doing some market research about the types of OIA requests an agency receives, rather than looking to analyse the different agencies OIA response times.
But you have raised a good point in your article that I may only get 1/3 of the requests MSD actually receive, if they put requests through a different monitoring/management system.
Not sure where I could get an authoritative number of requests from in that scenario.
From: OIA_Requests (MSD)
Ministry of Social Development
Tēnā koe Shane Gibson
Thank you for your email received 13 July 2020, under the Official
Information Act 1982. Your request has been forwarded to the appropriate
officials at National Office to respond. You can expect a decision as soon
as reasonably practicable, and in any case not later than 20 working days
after the day on which the request was received.
Nā mātou noa, nā
Official and Parliamentary Information team | Ministerial and
Executive Services
Ministry of Social Development
Our Purpose:
We help New Zealanders to help themselves to be safe, strong and
Ko ta mātou he whakamana tangata kia tū haumaru, kia tū kaha, kia tū
------------------------------- This email and any attachments may contain
information that is confidential and subject to legal privilege. If you
are not the intended recipient, any use, dissemination, distribution or
duplication of this email and attachments is prohibited. If you have
received this email in error please notify the author immediately and
erase all copies of the email and attachments. The Ministry of Social
Development accepts no responsibility for changes made to this message or
attachments after transmission from the Ministry.
Mark Hanna left an annotation ()
I'll be interested to see the results you get. Have you considered including Police in your project? Their OIA numbers reported to the SSC jumped hugely (from 7.5k over 6 months to 21k over 6 months) when they overhauled their OIA recording system in 2018. I've heard that this was because they joined up their system that handles speed camera tickets and incident reports for insurance to their OIA system, but haven't yet seen anything to fully verify that.
Shane Gibson left an annotation ()
I can only do 6 requests a day through FYI ;-) so just finished the last batch for the core agencies I believe will have OIA tracking systems.
Time will tell if that assumption bears out to be true or not.
Things to do with this request
- Add an annotation (to help the requester or others)
- Download a zip file of all correspondence


text:
Matchup Odds and Picks for the Memorial Tournament 2020
- The PGA Tour heads back to Muirfield Village for the Memorial Tournament from July 16th-19th with a loaded field – presenting some great bets for head-to-head matchups
- Daniel Berger, Abraham Ancer and Adam Hadwin are some of our favorite plays in their matchups in Dublin this weekend
- Read below to find matchup odds and picks for the 2020 Memorial Tournament
For the second week in a row, the PGA Tour is at Muirfield Village, this time for Jack Nicklaus' Memorial Tournament. Collin Morikawa emerged victorious last week in Dublin, Ohio after withstanding a tough battle against Justin Thomas in a playoff.
Although Tiger Woods is making his return to Tour play, the focus is still floating around the two favorites for this week, Justin Thomas and Bryson DeChambeau.
Although Muirfield Village is a long course at 7,400 yards, all types of golfers have found success at the course. We've pinpointed the player matchups with the best value for this upcoming week.
Daniel Berger/Patrick Reed Matchup Odds
|Odds at DraftKings
|Daniel Berger
|Patrick Reed
All Odds Taken July 15th
Berger's Breakout Win?
Daniel Berger has won three events in his PGA Tour career, with his most recent win coming at the Charles Schwab Challenge. Berger has been playing great golf recently and this could be the week where he wins his most substantial tournament.
Berger's matchup against Patrick Reed comes at no better time. Reed has been struggling since the return of the PGA Tour. In Reed's last four starts he has two missed cuts, a 24th placed finish, and a 39th place finish at the Workday Charity Open last week.
Berger is coming off three weeks rest, however, with his worst finish in his last five starts coming as a ninth-place finish at the Waste Management Phoenix Open in February. Amongst this field, Berger is first in Strokes Gained: Tee to Green, third in Strokes Gained: Approach, and first in Strokes Gained: Total.
#1 in the @fantasynational model: Bryson DeChambeau
#2 in the @fantasynational model: Daniel Berger.
Berger is $2,400 less on @DraftKings for The Memorial.
Last five events: T9, T5, T4, 1, T3.
Who do you think I'd rather play in cash? 🤷♂ pic.twitter.com/fWqrW0hpid
— Ben Heisler (@bennyheis) July 14, 2020
If there is a week to wager on Berger it's this week in Ohio. Although it was a couple of years ago, Berger finished 2nd at PGA National, which is also a Jack Nicklaus design. With Berger well-rested and confident heading into this week, he should have no problem handling Patrick Reed.
Pick: Daniel Berger (-120)
Abraham Ancer/Matthew Fitzpatrick Matchup Odds
|Abraham Ancer
|Matthew Fitzpatrick
Ancer Developing Under Pressure
Abraham Ancer had one hell of a week at the RBC Heritage a couple of weeks ago finishing in second with a total score of 21-under par. Ancer hit every green in regulation in his final round at Harbour Town, but his proximity to the hole and putting were not good enough to secure the victory.
Ancer's matchup this week is against Matthew Fitzpatrick. The Englishman has not been able to find his swing since the resumption of the PGA Tour. In Fitzpatrick's last two starts, he missed the cut at the Travelers Championship and finished 27th at the Workday Charity Open last week.
Fitzpatrick has one other start at Muirfield Village in last year's Memorial Tournament where he finished 68th. Ancer has two average starts at the Memorial, however, he has shown flashes of greatness in Ohio. In 2018, Ancer was the co-first round leader alongside Joaquin Niemann and Hideki Matsuyama shooting a 7-under par 65.
Like Berger, I believe this could be a destination for Ancer to win his first substantial tournament. The former Oklahoma Sooner has always played and putt well on Bentgrass/Poa Annua mix. After taking the last two weeks off to prepare for the Memorial, Ancer should be able to take advantage of his pure ball striking and driving accuracy on such a long course.
Pick: Abraham Ancer (-137)
Adam Hadwin/Kevin Kisner Matchup Odds
|Adam Hadwin
|Kevin Kisner
Hadwin is Coming Around the Corner
Canadian golfers have started to burst onto the scene recently and Adam Hadwin has been one of them. The Moose Jaw, Saskatchewan native has been in good form recently.
A fourth-place finish at the Rocket Mortgage Classic and tied-35th at last week's Workday Charity Open lets Hadwin carry some momentum heading into this week.
4 Canadians are inside the top 50 of the FedEx Cup rankings:
25 Nick Taylor
43 Adam Hadwin
46 Mackenzie Hughes
49 Corey Conners
— Bill Cooney (@BillCooney) June 29, 2020
Although a 35th place finish isn't glamorous for any PGA pro, Hadwin did have rounds of 66 and 68 at Muirfield Village last week. Since the Charles Schwab Challenge, Hadwin is ninth in Strokes Gained: Putting and 10th in Strokes Gained: Total.
Kisner has been very inconsistent in the last few weeks, but he has played quite well at Muirfield Village in the past. In 2015, Kisner finished eighth and in 2017 he finished sixth at the Memorial Tournament in Ohio. However, his last two starts have been disappointing finishing 74th and 41st.
I don't believe Kisner has found his groove just yet since the return and I believe Hadwin will be able to play four consistent rounds of golf after showing flashes of great golf last week.
Pick: Adam Hadwin (-137)
Let's have fun and keep it civil.


text:
Debate Digest: Teacher-student friendships on Facebook, Law school, Balanced budget amendment, US debt ceiling deal.
Argument: ICC can second-guess national prosecution terminations/denials
From Debatepedia
Revision history(Latest | Earliest) View (previous 50) (next 50) (20 | 50 | 100 | 250 | 500).
View logs for this page
View logs for this page
Diff selection: mark the radio boxes of the versions to compare and hit enter or the button at the bottom.
Legend: (cur) = difference with current version, (last) = difference with preceding version, M = minor edit.


text:
Search Issue Tracker
Won't Fix
Found in
Issue ID
Entering a composite string into InputField at high speed modifies multiple InputFields
Steps to reproduce:
0.1. Install Chinese (Traditional, Taiwan) keyboard input
0.2. Install AHK (AutoHotKey)
1. Open QA attached project
2. Activate AHK script at the project root
3. Enter play mode and activate one of the input fields
4. Switch to Chinese input
5. Press AHK script shortcut 'CTRL+G' (a series of symbols will be entered at high speed)
Reproduced on: 2017.4.6f1, 2018.1.6f1, 2018.2.0b9, 2018.3.0a3
InvalidOperationException: HashSet have been modified while it was iterated over
System.Collections.Generic.HashSet`1+Enumerator[UnityEngine.UI.Text].CheckState ()
System.Collections.Generic.HashSet`1+Enumerator[UnityEngine.UI.Text].MoveNext ()
UnityEngine.UI.FontUpdateTracker.RebuildForFont (UnityEngine.Font f) (at C:/buildslave/unity/build/Extensions/guisystem/UnityEngine.UI/UI/Core/FontUpdateTracker.cs:50)
UnityEngine.Font.InvokeTextureRebuilt_Internal (UnityEngine.Font font) (at C:/buildslave/unity/build/Modules/TextRendering/TextRendering.bindings.cs:354)
Apr 25, 2019 08:53
I fixed it, use a font Arial.
It is basic font.
I use Inputfield in Korean. So I saw same warning message, So I change text font in inputfield.
And I fixed.
Add comment
All about bugs
View bugs we have successfully reproduced, and vote for the bugs you want to see fixed most urgently.
Latest issues
- The Vector Graphics package can't be found in the Package Manager even if preview packages are enabled
- Hyphen symbol is not allowed inside the InputField if its content type is set to Name
- [2D Game kit] "Import parameters got modified during import" error is thrown when opening up the project for the first time
- Building subscenes without platform package doesn't work
- Picking stacked objects always selects prefab