Can Metropolis be considered as evolutionary algorithm?

Question

If we compare simple 1+1 evolutionary algorithm (e.g. Droste, Jansen, and Wegener, 2002)

1+1 evolutionary algorithm

1. Set $p_m := 1/n$.
2. Choose randomly an initial bit string $x \in \{0,1\}^n$.
3. Repeat the following mutation step:
   Compute $x'$ by flipping independently each bit $x_i$ with probability $p_m$.
   Replace $x$ by $x'$ iff $f(x') \geq f(x)$.

to Metropolis algorithm

Metropolis algorithm

1. Set arbitrary $x_0$.
2. Repeat the following steps:
   Generate $x'$ from candidate distribution $q(x'|x_i)$.
   Set $\alpha = f(x') / f(x_i)$.
   Set $p = \max (\alpha, 1)$.
   $x_{i+1} = \begin{cases} x' & \text{ with probability } & p \\ x_{i} & \text{ with probability } & 1-p \end{cases}$

they seem to be very similar. Metropolis is sometimes mentioned in introductory chapters of books on evolutionary algorithms (e.g. here for some Google example), however is not called as an evolutionary algorithm.

Can be Metropolis considered as an evolutionary algorithm? If not, why not?

---

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

Answer 1

I would say, and I think this is a fairly mainstream take on the question, "yes and no".

It's important to realize that "evolutionary algorithms" is a pretty fuzzy set of things. If you try and come up with a rigorous definition or formal taxonomy, it's not blindingly obvious how to both (a) include all the things we think of as being "evolutionary algorithms" and (b) not include all the things we don't really think of as members of that set. In any case, there's no single accepted definition, and classically, we think of things like a (1+1) evolution strategy as being within the realm of what we study.

So my answer is that if I'm attempting to be formal and theoretical about it, then yes Metropolis fits into my definition of what counts as an evolutionary algorithm. But in matters of practical speech and understanding, when I say "evolutionary algorithm", I'm not talking about a simple hill climber or Metropolis, even though both could technically meet the criteria.