3
$\begingroup$

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}$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.