0
$\begingroup$

I'm implementing a differential evolution algorithm and when it comes to evolving a population, the page I am referencing is vague on how the new population is generated.

https://en.wikipedia.org/wiki/Differential_evolution#Algorithm

The algorithm looks like the population is mutated during evolution.

# x, a, b, c are agents in the population
# subscriptable to find position in specific dimension
# pop is filled with Agent objects
for i, x in enumerate(pop):
  [a, b, c] = random.sample(pop[:i]+pop[i+1:], 3)
  ri = random.randint(0, len(x))
  new_position = []
  for j in range(len(x)):
    if random.uniform(0, 1) < CR or j == ri:
      new_pos.append(a[j] + (F * (b[j] - c[j])))
    else:
      new_pos.append(x[j])
  # Agent() class constructor for agent, takes position as arg
  new_agent = Agent(new_pos)
  if fitness(new_agent) <= fitness(x):
    pop[i] = new_agent # replace x with new_agent

But I wonder if instead it means a new population is made and then populated iteratively:

new_pop = []
for i, x in enumerate(pop):
  [a, b, c] = random.sample(pop[:i]+pop[i+1:], 3)
  ri = random.randint(0, len(x))
  new_position = []
  for j in range(len(x)):
    if random.uniform(0, 1) < CR or j == ri:
      new_pos.append(a[j] + (F * (b[j] - c[j])))
    else:
      new_pos.append(x[j])
  new_agent = Agent(new_pos)
  if fitness(new_agent) <= fitness(x):
    new_pop.append(new_agent)
  else:
    new_pop.append(x)
pop = new_pop

Note new_pop is made, and filled with agents as the for loop continues.

The first allows previously evolved agents to be used again in the same generation; in other words, the population is changed during the evolution. The second doesn't allow updated agents to be re-used, and only at the end is the original population changed.

Which is it?

$\endgroup$
1
  • $\begingroup$ It may be a good idea to provide the sources of these pseudocodes. $\endgroup$ – nbro Apr 15 at 10:21
2
+50
$\begingroup$

Quoting the original paper:

For each target vector $x_{i,G}$ ,a mutant vector is generated according to $$ v_{i,G+1} = x_{r_1,G} + F\left(x_{r_2,G} + x_{r_3,G}\right)$$

And later

To decide whether or not it should become a member of generation $G + 1$, the trial vector $v_{i,G+1}$ is compared to the target vector $x_{i,G}$ using the greedy criterion.

I'd say it is pretty unambiguous that author's intent was to split evolving agents' populations into "generations" indexed by $G$. A new generation $G+1$ is created by applying the DE algorithm to the previous generation $G$. No agents are changed within the generation $G$.

So, it looks like the answer to your question is "no" - the population of the current generation $G$ is not mutated. Your second approach is the correct one.

$\endgroup$
1
  • $\begingroup$ Some metaheuristics, like particle swarm optimization and bat algorithm, mutate their populations during the current generation; however, some like genetic algorithm doesn't. Thanks for clarifying, it seemed like it's closer in metaphor to the ones that do but it's nice having a declarative answer. $\endgroup$ – gator Apr 17 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.