Mutation and crossover operations in discrete differential evolutionary operations?

Question

I need to use discrete differential evolutionary algorithm for assigning discrete values from set size $L$ to vectors of size $D$ where $L$ could be smaller, equal or larger than $D$. Elements of vector $X$ could take the same values of other elements. My question is if we have a population of size $NP$ with each vector $X$ in the population of size $D$. How do we actually apply the mutation operand:

$$V_{j,i}^{G+1} = X_{j, r_1}^{G} + F\cdot (X_{j, r_2}^{G}-X_{j, r_3}^{G})$$

where $i$, $r_1$, $r_2$, $r_3$ are references to vectors in $NP$ and none is equal to the other, $J$ is an index in vector $X$, and $F$ is a random number between $0$ and $1.2$.

Suppose $X_{r_1}^{G}$ is equal to $\{4, 1, 3, 2, 2, 0\}$ and $X_{r_2}^{G}$ is equal to $\{2, 2, 3, 0, 4, 2\}$ and $X_{r_3}^{G}$ is equal to $\{1, 2, 3, 3, 0, 1\}$ Could anyone explain in detail the steps (through example if possible) on how to get the mutant vector $V_{j,i}^{G+1}$

Answer 1

There isn't a single way in which one can approach a discrete optimization problem using Differential Evolution (DE).

Widespread techniques listed under the Discrete Differential Evolution label aren't DE-specific.

You can allow variables to take values in a continuous range and use penalty functions to enforce integer values:

$$ \bar{f}(w) = f(w) - \sum_i{k_i \cdot (w_i - \operatorname{round}(w_i))^2} $$

$w$ is the vector of parameters (chromosome values), $f: \mathbb R^n \rightarrow \mathbb R$ the basic fitness function (here assuming "greater is better"), $k$ a problem-specific scaling vector, $\bar{f}(\cdot)$ the "penalized" fitness function.

In this way the DE algorithm (DE/rand/1) stays the same:

$$\begin{align} X_{j,r2}^G - X_{j,r3}^G & = \{2,2,3,0,4,2\} - \{1,2,3,3,0,1\} = \{1,0,0,-3,4,1\} \\ F \cdot (X_{j,r2}^G - X_{j,r3}^G) & = 0.5 \cdot \{1,0,0,-3,4,1\} = \{0.5,0,0,-1.5,2,0.5\} \\ V_{j,i}^{G+1} & = \{4,1,3,2,2,0\} + \{0.5,0,0,-1.5,2,0.5\} = \{4.5,1,3,0.5,4,0.5\} \end{align} $$

The trial vector $U$ is obtained via crossover between the donor vector $V_{j,i}^{G+1}$ and a target vector $X$:

$$U_{j,i}^{G+1} = \operatorname{crossover}(V_{j,i}^{G+1}, X_{j,i}^{G}) $$

The target vector is compared with the trial vector and the best one is admitted to the next generation.

This is the recommended procedure with R DEOptim Package (via the optional fnMap parameter).

---

You can round all the real-valued parameters before evaluating the fitness function:

$$\bar{f}(w) = f(\operatorname{round}(w))$$

(round acts as a repair operator)

This is the technique used by Mathematica's functions NMinimize / NMaximize with the options Method → "DifferentialEvolution" and Element[w,Integers]

---

There are also many variations of DE named something-Discrete-DE:

• Binary Discrete Differential Evolution: the solution of a problem is presented as a binary string instead of a real-valued vector
• Real Value based Discrete Differential Evolution introduces forward/backward transformations to map integer into real number and viceversa
• Exchange based Discrete Differential Evolution: here the crossover operator doesn't change but mutation, being the primary operator acting on elements of vector in continuous space, is replaced.
• ...

So you should specify what form of Discrete DE you're interested in for a step by step example.

Meanwhile A Comparative Study of Discrete Differential Evolution on Binary Constraint Satisfaction Problems by Qingyun Yang (2008 IEEE Congress on Evolutionary Computation) is a good starting point with many references.