Talk:Presentation

Combinatorial APS?

For some problems that are at least partly discrete, the basic APS applies a quantisation operator. If the quantum is $q_{d}$ for the dimension $d$, the operator is defined by

$$ x_{i,d}\leftarrow q_{d}\left\lfloor \left(0.5+x_{i,d}/q_{d}\right)\right.\tag{1} $$

where $\left\lfloor \right.$ is the floor operator.

Now, for combinatorial problems, it is certainly better to define specific operators for Expansion, Contraction, and Local search, similarly to what has been done, for example, for PSO. It means that we have to define a distance. Let us consider the canonical case in which the search space is the set of permutations of $D$ different elements. As we know, to transform a given permutation $X$ into another one $Y$, there exists a minimum number of transpositions. So we define the quasi-distance between $X$ and $Y$ as this minimum number.

The specific Local search operator is the easiest one to define: we have just to apply a "small" number of transpositions.

Expansion and Contraction are a bit more difficult. For Expansion, starting from three "positions" (i.e. permutations), $X_{best}$, $X_{worst}$, and $X_{worst2}$ (the second worst), we have to combine them in order to define $Y$ so that $$ distance(Y,X_{best}) > distance(Y,X_{worst}) $$ and
$$ distance(Y,X_{best}) > distance(Y,X_{worst2}) $$ and we should have $$distance(X_{best},X_{worst})+distance(X_{worst},Y)$$ as similar as possible to $$distance(X_{best},X_{worst2})+distance(X_{worst2},Y)$$

For Contraction, the three distances $distance(Y,X_{best})$, $distance(Y,X_{worst})$, and $distance(Y,X_{worst2})$, should be as similar as possible.

Moreover, in Standard APS only some components are modified (according to a probability threshold $p$). In order to "simulate" this, we should also randomly keep only some of the components of the $Y$ given by the above methods, the other ones being still the components of $X_{best}$.