📂Optimization

What is chaos operation in genetic algorithm?

Terminology ¹

In genetic algorithms, a chaos operation refers to a technique that uses a chaotic map when inducing mutation to increase the diversity of candidate solutions.

Description

When performing mutation operations in a genetic algorithm, if the domain of the dimension to be mutated is a closed interval $[a, b]$, one first applies normalization and then generates new solutions using maps such as the following logistic map. $$ x_{n+1} = r x_{n} \left( 1 - x_{n} \right) $$ In the logistic map, when $r = 4$ holds, $x_{n+1}$ is completely deterministic yet, except for a few specific initial conditions, is sensitive to initial conditions, so it can explore the entire search space widely.

Theoretical justification?

I understand that, aside from the fixed points of the logistic iteration, the chaos operation can explore the search space broadly. But how does this differ from simply sampling from a uniform distribution?

Several studies report that chaos operations yield good performance, but the exact reason is unclear. Personally, considering the logistic map’s natural invariant measure, I think it can be advantageous when solutions are located near the ends of the closed interval.

The logistic map’s $\rho$ resembles a probability density function similar to a beta distribution, and it seems to offer advantages over pure random sampling, including aspects related to implementation itself.