Computing Single Source Shortest Paths using Single-Objective Fitness Functions^{∗}

Surender Baswana^{†}

Tobias Friedrich^{§} Somenath Biswas^{†}

Piyush P. Kurur^{†} Benjamin Doerr^{‡}

Frank Neumann^{‡}

† Department of Computer Science and Engineering

Indian Institute of Technology Kanpur 208016 Kanpur, India ‡ Max-Planck-Institut für Informatik Campus E1 4 66123 Saarbrücken, Germany

§ International Computer Science Institute 1947 Center St., Suite 600 94704 Berkeley, CA, USA

ABSTRACT

Runtime analysis of evolutionary algorithms has become an important part in the theoretical analysis of randomized search heuristics. The first combinatorial problem where rigorous runtime results have been achieved is the well-known single source shortest path (SSSP) problem. Scharnow, Tinnefeld and Wegener [PPSN 2002, J. Math. Model. Alg. 2004] proposed a multi-objective approach which solves the problem in expected polynomial time. They also suggest a related single-objective fitness function. However, it was left open whether this does solve the problem efficiently, and, in a broader context, whether multi-objective fitness functions for problems like the SSSP yield more efficient evolutionary algorithms. In this paper, we show that the single objective approach yields an efficient (1+1) EA with runtime bounds very close to those of the multi-objective approach.

Categories and Subject Descriptors: F.2 [Theory of Computation]: Analysis of Algorithms and Problem Complexity

General Terms: Theory, Algorithms, Performance

1. INTRODUCTION

Evolutionary algorithms (EAs) have been successfully applied to a wide range of combinatorial optimization problems. Understanding the success of these randomized search heuristics by rigorous analyses has gained increasing interest in recent years. One approach to analyze evolutionary algorithms is by means of carrying out a rigorous runtime analysis. The line of research has been started by analyzing the behavior of EAs on simple pseudo-Boolean functions [13, 15, 7]. Later on, some of the best known combinatorial optimization problems have been investigated [9, 14, 18].

The first problem of this kind where rigorous runtime results have been achieved is the well-known single source shortest path (SSSP) problem [17]. Computing shortest paths in a given graph is one of the fundamental problems in computer science and still an important field of research [16, 2, 11]. In the area of randomized search heuristics related problems such as vehicle routing [8] and routing problems in networks [6, 10] have been tackled. Therefore, it seems to be important to understand the basic SSSP problem from a theoretical point of view to gain new insights that will help practitioners solving related problems arising in applications.

In [17], the authors examined a simple EA together with a multi-objective fitness function which makes the EA mimic Dijkstra’s algorithm for the SSSP problem [3]. Its optimization time (that is, the number of fitness evaluations used) is O(n^{3}), where n is the number of vertices of the input graph. Additionally, they have given a single-objective approach which they suppose to be efficient. However, the authors state that they were not able to analyze their approach with respect to the runtime behavior. In this paper, we point out that the multi-objective fitness function is not necessary. We consider the proposed single-objective approach and show how it solves the SSSP problem in expected polynomial time.

In the case that a simple randomized local search procedure is used, it is not too hard to prove that such an approach again follows the ideas of Dijkstra’s algorithm. This follows from the fact that the new solution is constructed in the 1-neighborhood of the previous one. Simple EAs may construct solutions that are further away from the current search point. For the SSSP, this may result in that shortest paths for certain vertices can get lost in exchange for other short paths. This is a crucial difference to what happens in Dijkstra’s algorithm.

In fact, it has been shown recently (for a different problem though) that this more general search behavior can increase the optimization time from polynomial for randomized local (1 + 1)-EA for SSSP

∗Work supported by the Collaborative Research Program of the Research I Foundation, IIT Kanpur. Tobias Friedrich’s work was also partially supported by a postdoctoral fellowship from the German Academic Exchange Service (DAAD).

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.

FOGA’09, January 9–11, 2009, Orlando, Florida, USA.

Copyright 2009 ACM 978-1-60558-414-0/09/01 ...$5.00.

Initialization: 1 u ← (u_{1}, …, u_{n−1}),

u_{i} ∈ V \ {v_{i}} chosen uniformly at random. 2 repeat

Mutation:

3 Pick S according to Pois(λ = 1) 4 u^{0} ← u 5 for k = 1 to S + 1

6  do

7 Choose i ∈ {1, …, n − 1} uniformly at random. 8 Choose v_{j} ∈ V \ {v_{i}} uniformly at random. 9 Generate u^{k} from u^{k−1} by setting u_{i} to v_{j}.

Selection:

10 if f_{u^{S+1}} ≤ f_{u} 11 then u ← u^{S+1}

12 forever

Figure 1. The (1 + 1)-EA with single-objective fitness function f for the SSSP problem.

search to exponential for EAs, even under conditions that look highly favorable for the EA [5]. In this light, the work of [17] raises the question whether such a phenomenon also occurs for the SSSP problem.

We answer this question and prove that the more flexible mutation allowed in EAs still leads to a polynomial optimization time, more precisely, to an expected optimization time of O(n^{3} log(n + w_{max})), where w_{max} is the largest of the (integral) edge weight. Our analysis uses new structural insights of the SSSP problem which point out how randomized search heuristics may achieve progress for this kind of problem even if they may not follow the ideas of Dijkstra. These positive results are later on complemented with lower bounds for the examined algorithms which show that our analyses are almost tight.

We should note that the results in [17] have recently been improved in [4]. In addition to n denoting the number of vertices of the input graph, let ℓ denote the maximum number of edges of a shortest path. Then [4] shows that the optimization time of the multi-objective EA proposed in [17] is O(n^{2} max{log(n), ℓ}) with high probability. The methods of [17] would only yield an optimization time of O(n^{2}ℓ log(n)) in expectation. Hence the improvements are both a stronger bound on the expected optimization time for graphs having small diameter and a sharper concentration bound for the optimization time in general graphs. However, no progress was made on whether the SSSP can be approached via single-objective methods

The outline of the paper is as follows. In Section 2, we present the single-objective approach that will be analyzed throughout this paper. Section 3 shows that the singleobjective approach solves the SSSP in expected polynomial time and Section 4 gives almost matching lower bounds. Finally, we finish with some concluding remarks.

2. ALGORITHM

We consider the well-known single source shortest paths problem (SSSP). Given a directed graph G = (V, E) with V = {v_{0}, …, v_{n−1}} and E = {e_{1}, …, e_{m}}. Additionally, a weight function w: E → ℕ is given which assigns integer distance values to the edges. Let w_{max} = max_{e∈E} w(e). We may extend w to all (u, v), u ≠ v, by setting w((u, v)) = ∞ iff (u, v) ∉ E. Given a distinguished vertex s ∈ V, say s = v_{0}, the single source shortest path problem is to compute for each vertex v_{i}, 1 ≤ i ≤ n − 1, a shortest path from s to v_{i}. Without loss of generality, we assume that such a path exists for each v_{i}. It is both a well known fact and easy to see that a set of such shortest paths always forms a tree, which is therefore called a shortest path tree.

We examine the (1+1) EA for the SSSP problem (see Figure 1) already investigated in [17]. The search space consists of all candidate solutions u = (u_{1}, …, u_{n−1}) ∈ {v_{0}, …, v_{n−1}}^{n−1} where u_{i} ≠ v_{i}. The goal of the algorithm is to find a u = (u_{1}, …, u_{n−1}) such that the edges (u_{i}, v_{i}) form a shortest path tree T rooted at s (that is, for each vertex v_{i}, 1 ≤ i ≤ n − 1, u_{i} is the predecessor of v_{i} in the shortest path from s to v_{i} contained in T).

The initial solution is chosen uniformly at random from the search space. In each iteration one single offspring is produced by mutation. The mutation consists of changing the predecessor of some S + 1 vertices uniformly at random, where the value of S is chosen according to the Poisson distribution with parameter λ = 1. This distribution is as proposed in [17].

There are many invalid solutions, i. e., search points that do not represent trees. Assigning a cost of ∞ to such solutions, it is hard for a randomized search heuristic to obtain a valid solution. Due to this a multi-objective fitness function has been investigated for this problem and an upper bound of O(n^{3}) on the expected optimization time has been proven. Additionally, a single-objective fitness function has been given which leads the algorithm towards valid solutions. Instead of using the value ∞ for solutions that do not represent trees each vertex that is not connected to the source is penalized. Using penalty values is a common approach for handling constraints (see e. g. [12]) and leads the algorithm towards feasible solutions.

In [17] the authors state that they are not able to analyze this approach. Our goal is to show that this single-objective approach indeed works and finds an optimal solution in expected polynomial time.

Now we describe the single objective function that is investigated in the rest of this paper. Consider a candidate solution u = (u_{1}, …, u_{n−1}) where u_{i} is supposed to be the immediate predecessor of the vertex v_{i}. Associated with u consider the subgraph T_{u} of the input graph G consisting of those pairs (u_{j}, v_{j}) which are edges in G. For a vertex v, if there is a path in T_{u} from the source s to v it has to be unique. Let γ_{v} denote the unique path in such cases. Whenever such unique path γ_{v} exists for a vertex v we define its cost f_{u}(v) to be the sum of the weights of the edges in γ_{v}. On the other hand if v is unreachable from s in T_{u}, then the cost f_{u}(v) is set to d_{penalty} := n · w_{max}. The fitness f_{u} of a candidate solution u is given by

f_{u} := ∑_{i=1}^{n−1} f_{u}(v_{i}).

In our analysis of the runtime behavior of the algorithm, we bound the number of evaluations of the fitness function required to reach an optimal solution. The expected optimization time refers to the expectation of this value. The difficulty in analyzing the stated approach lies in the occurrence of mutation steps that change more than one predecessor. In this case, shortest paths found during the run of the algorithm may get lost. Assuming that in each mutation step just one vertex changes its predecessor it is easy to prove an upper bound of O(n^{3}) as for the multi-objective approach given in [17] by following the ideas of Dijkstra’s algorithm.

3. UPPER BOUND

We now prove an upper bound on the running time of the (1+1) EA. As mentioned before we will assume that the input graph is a complete graph. We start the algorithm with each vertex picking one of the edges incident on it at random. It then proceeds in stages where in each stage it decides to mutate k + 1 vertices, k picked according to the Poisson distribution of mean 1, accepting the mutation if and only if it does not lead to an increase in the objective function.

Let u_{i} denote the candidate solution after i mutations. Recall the definition of the objective function f_{u_{i}}. For ease of notation let f_{i}(v) denote the cost f_{u_{i}}(v) associated with the vertex v and let f_{i} denote the fitness f_{u_{i}} of the candidate solution u_{i}. Similarly let T_{i} denote the subgraph T_{u_{i}} of valid edges (i.e. edges of the input graph G) present in the candidate solution u_{i}.

The key idea behind our upper bound is the following: We prove that in each mutation the value of the objective function reduces at least by a factor of 1 − Ω(n^{−3}) with high probability. Thus in time O(n^{3}) the value of the objective function reduces by a multiplicative factor of at most c < 1. The value of the objective function is less than n · d_{penalty} initially. Assuming the edge weights are integers, after O (n^{3} · (log n + log d_{penalty})) mutations the algorithm will find the shortest distance tree with high probability. Note, that this approach is similar to the expected multiplicative weight decrease for the analysis of the (1+1) EA and the minimum spanning tree problem [14]. The difference of our approach to this one is that we do not give a set

e  γ′ γ  s y v  x

Figure 2. How a good edge enters the solution.

of operations that turn the current solution into an optimal one. Instead of this we give a set of operations that lead to a solution whose distance to an optimal one is by a factor of (1 − 1/n) smaller than the distance of the current solution to an optimal one.

We now define two parameters called delay and gap which we use to analyze the rate at which the objective function decreases. Let T be the shortest path tree in the graph (if there are more than one pick one and fix it for the rest of the section). Let δ(s, v) denote the distance of v from s in T. The delay of the vertex v after i mutations is defined to be d_{i}(v) = f_{i}(v) − δ(s, v). By gap g_{i} of the candidate solution after i mutations we mean g_{i} = f_{i} − ∑_{v} δ(s, v). Notice that g_{i} = ∑_{v} d_{i}(v). When the gap drops to 0 we have the desired shortest distance tree. Thus gap measures how far the fitness function is currently from the final optimal value ∑_{v} δ(s, v).

Lemma 1. Let g_{i} denote the gap after i mutations then the conditional expectation 𝔼[g_{i+1} | g_{i} = g] is given by.

𝔼[g_{i+1} | g_{i} = g] ≤ g (1 − \frac{1}{3 · n^{3}} )

Proof. Let the current gap g_{i} be g. Since the total delay ∑_{v} d_{i}(v) is g, there is at least one vertex v such that its delay d_{i}(v) is at least \frac{g}{n}. Let T be the shortest path tree in the graph that we have fixed for our analysis. Let γ = ⟨s = v_{0}, …, v_{ℓ} = v⟩ be the path from s to v in T. Denote by E(γ) the set of its edges. For an edge e = (v_{k}, v_{k+1}) ∈ E(γ) let D(e) = d_{i}(v_{k+1}) − d_{i}(v_{k}) be the difference of the delays of the end points of e. Since d_{i}(s) = 0 we have

D(γ) := ∑_{e∈E(γ)} D(e)
= d_{i}(v_{ℓ}) − d_{i}(v_{ℓ−1}) + … + d_{i}(v_{1}) − d_{i}(v_{0})
= d_{i}(v_{ℓ}) − d_{i}(v_{0})
≥ \frac{g}{n} .  (1)

We define an edge e in γ to be positive if the difference of the delays of its end points, D(e), is positive. Let E^{+}(γ) denote the set of positive edges in γ. Then

D(E^{+}(γ)) := ∑_{e∈E^{+}(γ)} D(e) ≥ ∑_{e∈E(γ)} D(e) ≥ \frac{g}{n} (2)

Consider any positive edge e = (x, y) in the path γ. We claim that x has to be connected to the source s in the graph T_{i}. Otherwise the value of the fitness function f_{i}(x) = d_{penalty}. Since f_{i}(y) ≤ d_{penalty}, it follows that D(e) = d(y)− d(x) ≤ 0 and hence e is not positive.

Having proved that x is reachable from s we prove that the edge e is not present in the current candidate solution. Otherwise e will be present in the graph T_{i} and since the vertex x is reachable from s in T_{i}, so will be y. Let γ′ be the path from s to x in T_{i}. Then the path to the vertex y from the source s in T_{i} is the path γ′ followed by the edge e (see Figure 2).

Notice that since the edge e is present in the shortest path tree T we have δ(s, y) = δ(s, x)+w(e). As a result the delay of y is given by d_{i}(y) = f_{i}(x)+w(e)−(δ(s, x)+w(e)) = d_{i}(x) and hence D(e) = d_{i}(y) − d_{i}(x) = 0. This contradicts the fact that the edge e is positive and hence it is not present in the graph T_{i}.

Let M_{i} be the event that in the ith mutation only one vertex is mutated. The events M_{i}’s are mutually independent. In the ith mutation step k_{i} + 1 vertices are mutated, where k_{i} follows a Poisson distribution with mean 1. Therefore, we have P[M_{i}] = \frac{1}{e} ≥ \frac{1}{3} . Consider any positive edge e = (x, y). Given that the event M_{i+1} has occurred the probability that the vertex y switches its predecessor to x is at least 1/n^{2}. If such a switch occurs the gap reduces by an amount equal to D(e). This is because, as noted in the previous paragraph, x is reachable from s in the current solution, and the edge e between x and y is in the shortest path tree T, the delay of y will become the same as that of x as e comes into the solution. Therefore given M_{i+1} the expected decrease in gap, Δg, is given by

𝔼[Δg | g_{i} = g, M_{i+1}] ≥ ∑_{e∈E^{+}(γ)} \frac{1}{n^{2}} D(e) ≥ \frac{1}{n^{3}} g.

Since the P[M_{i+1}] ≥ \frac{1}{3} , the expected decrease in gap is at least \frac{1}{3·n^{3}} g. Hence the expected gap after the (i + 1)-st mutation will be less than or equal to (1 − \frac{1}{3·n^{3}} )g provided the gap after i mutations is g.

As a corollary of Lemma 1 we have:

Corollary 2.

𝔼[g_{i+j} | g_{i} = g] ≤ g (1 − \frac{1}{3 · n^{3}} )^{j} .

Theorem 3. The expected optimization time of the (1+1) EA on the shortest path problem with integer edge weights is O (n^{3} · (log n + log w_{max})), where w_{max} is the maximum of the weights of all edges in the graph.

Proof. Recall that the gap g_{0} at the beginning of the algorithm is at most n · d_{penalty} and we have set d_{penalty} to be n·w_{max}. We partition the sequence of iterations into epochs. Each epoch consists of a sequence of 6n^{3} iterations in the algorithm. Consider any such epoch. It follows from Corollary 2 that conditioned on the event that the epoch begins with gap g_{begin} = g, the expected value of the gap g_{final} after the epoch is given by

𝔼[g_{final} | g_{begin} = g] ≤ g (1 − \frac{1}{3n^{3}} )^{6n^{3}} ≤ \frac{g}{e^{2}} .

Figure 3. The worst case graph. The edges at the bottom form the shortest path tree. All edges not drawn have weight w_{max}.

Using Markov’s Inequality it follows that

Pr [g_{final} ≥ \frac{g_{begin}}{e} ] ≤ 1/e

We call an epoch good if the gap at the end of the epoch is less than 1/e times the gap in the beginning of the epoch. It follows that an epoch is good with probability at least 1−1/e. Furthermore, each epoch is good or bad independent of other epochs (owing to the independence of mutations in each iteration). Thus it follows that ⌈ln g_{0}⌉ good epochs suffice to reduce the gap below 1. Since each epoch consists of 6n^{3} iterations, the expected number of iterations in the (1+1) EA is O(n^{3} log g_{0}).

4. LOWER BOUND

In this section we show a lower bound matching the upper bound presented in the previous section up to the logarithmic factor. More precisely, for any n ∈ ℕ we define a graph G_{n} on n vertices for which the algorithm has an optimization time of at least Ω(n^{3}) with high probability.

The worst case graph G_{n} is a weighted complete graph (V, E) with V = {v_{0}, …, v_{n−1}}, E = V ×V \{(v, v) | v ∈ V }, and edge weights w(v_{i}, v_{j}), i, j ∈ [0..n − 1], i ≠ j defined by

w(v_{i}, v_{j}) := \{ \begin{matrix}2, & if 0 ≤ i, j < n, j = i + 1, \\ 2j + 1, & if i = 0, 2 ≤ j < n, \\ w_{max}, & otherwise. \end{matrix}

We choose w_{max} = 4n. This implies that (v_{0}, v_{1}, v_{2}, …, v_{n−2}, v_{n−1}) is the unique shortest path tree starting from s = v_{0}. Figure 3 illustrates the graph. We prove the following theorem.

Theorem 4. The optimization time of the (1 + 1)-EA on G_{n} is Ω(n^{3}) with probability 1 − e^{−Ω(n)}.

To prove this lower bound, we need the following Chernofftype inequalities.

Theorem 5. Let X_{i}, i ∈ [1..n], be independent random variables X := ∑_{i=1}^{n} X_{i}. Let 0 < p < 1 and δ > 0.

a) If Pr[X_{i} = 1] = p and Pr[X_{i} = 0] = 1 − p for all i ∈ [1..n], then

Pr[X ≤ (1 − δ)𝔼[X]] ≤ exp (− \frac{δ^{2}𝔼[X]}{2} ) ,
Pr[X ≥ (1 + δ)𝔼[X]] ≤ exp (− \frac{min\{δ, δ^{2}\}𝔼[X]}{3} ) .

b) If the X_{i} are geometrically distributed random variables with Pr[X_{i} = j] = (1 − p)^{j−1}p for all j ∈ ℕ, then

Pr[X ≥ (1 + δ)𝔼[X]] ≤ exp (− \frac{δ^{2}}{2} \frac{(n − 1)}{1 + δ} ) .

Proof. Part a) is a classical Chernoff bound, cf. [1]. To prove part b), let Y_{1}, Y_{2}, … be an infinite sequence of independent, identically distributed biased coin tosses (binary random variables) such that Y_{i} is one with probability Pr[Y_{i} = 1] = p and zero with probability Pr[Y_{i} = 0] = 1 − p. Note that the random variable “smallest j such that Y_{j} = 1” has the same distribution as each X_{i}. In consequence, X has the same distribution as “smallest j such that exactly n of the variables Y_{1}, …, Y_{j} are one”. In particular, Pr[X ≥ j] = Pr[∑_{i=1}^{j−1} Y_{i} ≤ n − 1] for all j ∈ ℕ. This manipulation reduces our problem to the analysis of independent Bernoulli trials and will enable us to use the classical Chernoff bounds.

The expected value of each X_{i} is 𝔼[X_{i}] = \frac{1}{p}, thus 𝔼[X] = \frac{n}{p}. Let Y := ∑_{i=1}^{⌈(1+δ)𝔼[X]−1⌉} Y_{i}. By the above,

Pr[X ≥ (1 + δ)𝔼[X]] = Pr[Y ≤ n − 1].

The expected value of Y is bounded by

𝔼[Y] = ⌈(1 + δ)𝔼[X] − 1⌉p ≥ (1 + δ)n − p > (1 + δ)(n − 1).

Now let δ′ := 1 − \frac{n−1}{𝔼[Y ]} . Then 0 < δ′ ≤ 1 and Pr[Y ≤ n − 1] = Pr[Y ≤ (1 − δ′)𝔼[Y]]. Hence we can apply the classical Chernoff bound from part a) to get

Pr[X ≥ (1 + δ)𝔼[X]]

= Pr[Y ≤ (1 − δ′)𝔼[Y]]

≤ exp (− \frac{1}{2} 𝔼[Y] (1 − \frac{n − 1}{𝔼[Y]} )^{2})

≤ exp (− \frac{1}{2} 𝔼[Y] (1 − \frac{1}{1 + δ} )^{2})

≤ exp (− \frac{1}{2} (n − 1)(1 + δ) ( \frac{δ}{1 + δ} )^{2}) .

As the last preparation to prove Theorem 4, we show the following lemma. We use u to denote an individual. The predecessor of a vertex v is then called u(v).

Lemma 6. Let u be an individual, v ≠ s be a vertex and y ∈ V \ {v, u(v)}. Let u′ be the outcome of applying a mutation step (without selection) to u. Then Pr [u′(v) = y] ≤ 2e(n − 1)^{−2}.

Let v_{i_{1}}, …, v_{i_{k}} ∈ V \ {s} pairwise different and y_{1}, …, y_{k} ∈ V such that y_{j} ∉ {v_{i_{j}} , u(v_{i_{j}})} for all j ∈ [1..k]. Then Pr[∀j ∈ [1..k]: u′(v_{i_{j}}) = y_{j}] ≤ 2e(n − 1)^{−k−1}.

Proof. To have u′(v) ≠ u(v), at least one of the S + 1 elementary mutations performed in the mutation step has to regard the vertex v (“first event”), and to have u′(v) = y, the last one of these elementary mutations has to change u(v) to y (“second event”). The probability of the first event is at most

∑_{S=0}^{∞} \frac{1}{S!} \frac{S + 1}{n − 1} = 1/(n − 1) (∑_{S=1}^{∞} \frac{S}{S!} + ∑_{S=0}^{∞} \frac{1}{S!} )

= 1/(n − 1) (∑_{S=1}^{∞} \frac{1}{(S − 1)!} + e)
= 2e/(n − 1).

Conditional on the first event, the second happens with probability exactly 1/(n − 1).

For the second claim, note that the above shows that Pr[u′(v_{i_{1}}) = y_{1}] ≤ 2e(n − 1)^{−2}. Even assuming that v_{i_{j}}, j ≤ 2, is touched by the mutation, the probability that the last change of its predecessor is to y_{j}, is exactly (n − 1)^{−1}, and this event is independent of all other random decisions.

Clearly, the second part of the lemma is not best possible—the probability should be of order n^{−2k}—but sufficient for our purposes. We can now prove Theorem 4.

Proof of Theorem 4. As we are only interested in asymptotic bounds, implicit we assume that n is sufficiently large. Also, we will not try to find the best possible constants. To prove the claim, we analyze how long it takes until the individual u for the first time is the path P := (s = v_{0}, v_{1}, …, v_{n−1}). To this aim, we analyze how the length L = L(u) of the longest subpath of P starting in s that is contained in u grows. Note that, contrary to the multiobjective setting, this length L may decrease. We shall adopt the proof of [4] for the multi-objective setting to deal with this issue. In particular, we denote by L_{t} the maximum length ℓ such that the path (v_{0}, …, v_{ℓ}) was contained in the individual at some time t′ ≤ t.

We first convince ourselves that for all times t and all i > L_{t} + 1, we have Pr[u(v_{i}) = v_{i−1}] ≤ ν := 2e^{2}/(2e^{2} + 1) ≈ 0.936. This is clearly true for t = 0, since the initial individual satisfies Pr[u(v_{i}) = v] = 1/(n − 1) for all v ≠ v_{i}.

Assume that the claim is correct for some t ≥ 0. Let i > L_{t}+1. Fix a mutation chosen by the algorithm. We may assume i > L_{t+1} + 1 (otherwise there is nothing to show). Denote by u′ the individual resulting from this iteration, that is, from applying the mutation to u in case this does not worsen the fitness. With the help of Lemma 6 we compute

Pr[u′(v_{i}) = v_{i−1}]

= Pr[u′(v_{i}) = v_{i−1} | u(v_{i}) = v_{i−1}] Pr[u(v_{i}) = v_{i−1}]

+ Pr[u′(v_{i}) = v_{i−1} | u(v_{i}) ≠ v_{i−1}] Pr[u(v_{i}) ≠ v_{i−1}]

≤ (1 − (1/e)(n − 1)^{−2}) Pr[u(v_{i}) = v_{i−1}]

+ 2e(n − 1)^{−2} (1 − Pr[u(v_{i}) = v_{i−1}])

≤ ν(1 − (1/e)(n − 1)^{−2} − 2e(n − 1)^{−2}) + 2e(n − 1)^{−2} = ν.

Note that the above holds independent of the values of u(v), v ∈ V \{s, v_{i}} (of course, still assuming i > L_{t}+1). For this reason, the claim Pr[u(v_{i}) = v_{i−1}] ≤ ν also holds if we condition on arbitrary values for these u(v). In consequence, for any k ≥ 1, i_{1}, …, i_{k} pairwise distinct element of [L_{t} + 1..n − 1], we have

Pr[∀j ∈ [k]: u′(v_{i_{j}}) = v_{i_{j} −1}]
= Pr[u′(v_{i_{1}}) = v_{i_{1}−1}]
Pr[u′(v_{i_{2}}) = v_{i_{2}−1} | u′(v_{i_{1}}) = v_{i_{1}−1}] …
Pr[u′(v_{i_{k}}) = v_{i_{k}−1} | u′(v_{i_{1}}) = v_{i_{1}−1}, …,
u′(v_{i_{k−1}}) = v_{i_{k−1}−1}]
≤ (2e/(2e + 1))^{k}.

We start our analysis of the growth of L_{t} by noting that with high probability L_{0} is constant. More precisely, the probability that in the initial individual some vertex v_{i} ∈ \{v_{1}, …, v_{n−1}\} is already linked to v_{i−1}, is exactly \frac{1}{n−1} independent of all other values of u. Hence the probability that L_{0} ≥ k, is (n − 1)^{−k} for all k ∈ ℕ.

We now analyze the growth D_{t} := L_{t} −L_{t−1} of the path in iteration t. For D_{t} to be positive, the mutation has to change u(v_{L_{t}+1}) to v_{L_{t}}. By Lemma 6, this happens with probability at most 2e(n − 1)^{−2}. D_{t} can be larger than one due to two effects: (i) the mutation can change u(v_{j}) to v_{j−1} for further vertices on the path, and (ii), some vertices v_{j} not touched at all by the mutation can already be connected to v_{j−1}. Again by Lemma 6, the probability of an event of type (i) is at most 2e(n−1)^{−2} independently of all other random decisions now or in the past. By the above reasoning, the probability of an event of type (ii), i. e., that certain k vertices not touched by the mutation in this iteration were already connected with their natural predecessor, is at most ν^{k}.

Hence Pr[D_{t} ≥ k] ≤ \frac{2e}{(n−1)^{2}} (2e(n − 1)^{−2} + ν)^{k−1} ≤ 2en^{−2} (0.95)^{k−1} for n sufficiently large. For all t, D_{t} is dominated by a random variable \overline{D} with distribution Pr[\overline{D} = k] = 2en^{−2} (0.95)^{k−1}0.05 and Pr[\overline{D} = 0] = 1 − 2en^{−2} as this implies Pr[\overline{D} ≥ k] = 2en^{−2} (0.95)^{k−1}. Similarly, we see that L_{0} − 1 is dominated by a random variable with distribution \overline{D}. Hence L_{t} − 1 = L_{0} − 1 + ∑_{k=1}^{t} D_{k} is dominated by the sum of t independent random variables with distribution \overline{D}.

The probability that after t = (2e)(1/80)(n − 2)n^{2} steps the optimal solution is found is Pr[L_{t} = n − 1]. This is at most Pr[∑_{i=1}^{t} X_{i} ≥ n − 2] by the above considerations, where the X_{i} are independent random variables with distribution \overline{D}. Denote by x the number of X_{i} that are positive. Then 𝔼[x] = 2en^{−2}t = (1/80)(n − 2) and thus Pr[x > 4en^{−2}t] ≤ exp(−𝔼(x)/12) = exp(−(n − 2)/960). We compute

Pr[L_{t} = n − 1]

≤ Pr [∑_{i=1}^{t} X_{i} ≥ n − 2]

≤ Pr [∑_{i=1}^{t} X_{i} ≥ n − 2 | x ≤ (1/40)(n − 2)]

+ Pr[x > 2 · 2en^{−2}t]

≤ Pr [∑_{i=1}^{t} X_{i} ≥ n − 2 | x = (1/40)(n − 2)]

+ exp(−(n − 2)/960).

For all i, define the random variable Y_{i} = (X_{i} | X_{i} ≥ 1). Then Y_{i} has the geometric distribution Pr[Y_{i} = k] = Pr[X_{i} = k]/ Pr[X_{i} ≥ 1] = (0.95)^{k−1} 0.05 and 𝔼[Y_{i}] = 20. Hence by Theorem 5, we have

Pr [∑_{i=1}^{t} X_{i} ≥ n − 2 | x = (1/40)(n − 2)]

= Pr [ ∑_{i=1}^{(1/40)(n−2)} Y_{i} ≥ n − 2]

≤ Pr [ ∑_{i=1}^{(1/40)(n−2)} Y_{i} ≥ 2 · 20 · (1/40)(n − 2)]

≤ exp(−((1/40)(n − 2) − 1)/4).

This shows that

Pr[L_{t} = n − 1] ≤ exp(−((1/40)(n − 2) − 1)/4) + exp(−(n − 2)/960) = exp(−Ω(n)).

5. CONCLUSION

The single source shortest path problem is one of the fundamental problems in computer science and the first combinatorial optimization problem for which a rigorous runtime analysis of evolutionary algorithms has been carried out. We have shown that a multi-objective approach is not necessary to solve this problem efficiently by evolutionary algorithms and analyzed the single-objective one given in [17]. The upper bound obtained is similar to the multi- objective result. Additionally, our analyses give new insights how evolutionary algorithms may achieve progress towards an optimal solution even if the proof ideas can not follow the run of Dijkstra’s algorithm.

References

[1] N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, 2nd edition, 2000.

[2] H. Bast, S. Funke, P. Sanders, and D. Schultes. Fast routing in road networks with transit nodes. Science, 316(5824):566, 2007.

[3] E. W. Dijkstra. A note on two problems in connexion with graphs. In Numerische Mathematik, volume 1, pages 269–271. Mathematisch Centrum, Amsterdam, The Netherlands, 1959.

[4] B. Doerr, E. Happ, and C. Klein. A tight bound for the (1+1)-EA on the single source shortest path problem. In Proc. of the IEEE Congress on Evolutionary Computation (CEC 2007), pages 1890–1895, 2007.

[5] B. Doerr, T. Jansen, and C. Klein. Comparing global and local mutations on bit strings. In Proc. of the 10th annual conference on Genetic and evolutionary computation (GECCO ’08), pages 929–936, 2008.

[6] M. Dorigo and T. Stützle. Ant Colony Optimization. MIT Press, 2004.

[7] S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276(1–2):51–81, 2002.

[8] A. El-Fallahi, C. Prins, and R. W. Calvo. A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem. Computers & OR, 35(5):1725– 1741, 2008.

[9] O. Giel and I. Wegener. Evolutionary algorithms and the maximum matching problem. In Proc. of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS ’03), pages 415–426, 2003.

[10] S. J. Kim and M. K. Choi. Evolutionary algorithms for route selection and rate allocation in multirate multicast networks. Appl. Intell., 26(3):197–215, 2007.

[11] S. Knopp, P. Sanders, D. Schultes, F. Schulz, and D. Wagner. Computing many-to-many shortest paths using highway hierarchies. In Proc. of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX ’07), 2007.

[12] Z. Michalewicz. A survey of constraint handling techniques in evolutionary computation methods. In Evolutionary Programming, pages 135–155, 1995.

[13] H. Mühlenbein. How genetic algorithms really work: mutation and hillclimbing. In Proc. 2nd International Conference Parallel Problem Solving from Nature (PPSN II), pages 15–26, 1992.

[14] F. Neumann and I. Wegener. Randomized local search, evolutionary algorithms, and the minimum spanning tree problem. Theoretical Computer Science, 378(1):32– 40, 2007.

[15] G. Rudolph. How mutation and selection solve long path problems in polynomial expected time. Evolutionary Computation, 4(2):195–205, 1996.

[16] P. Sanders and D. Schultes. Engineering highway hierarchies. In Proc. of the 14th Annual European Symposium on Algorithms (ESA ’06), pages 804–816, 2006.

[17] J. Scharnow, K. Tinnefeld, and I. Wegener. The analysis of evolutionary algorithms on sorting and shortest paths problems. Journal of Mathematical Modelling and Algorithms, 3(4):349–366, 2004. (Conference version appeared in Proc. 7th International Conference Parallel Problem Solving from Nature 2002 (PPSN VII)).

[18] C. Witt. Worst-case and average-case approximations by simple randomized search heuristics. In Proc. of the 22nd Annual Symposium on Theoretical Aspects of Computer Science (STACS ’05), pages 44–56, 2005.