Difference between revisions of "Talk:Presentation"
m (→Combinatorial APS?) |
(→Combinatorial APS?) |
||
| Line 9: | Line 9: | ||
where $\left\lfloor \right.$ is the floor operator. | 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. | + | 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) | ||
| + | distance(Y,X_best) > distance(Y,X_worst2) | ||
| + | $$ | ||
| + | |||
| + | For Contraction, the three distances $distance(Y,X_best)$, $distance(Y,X_worst)$, and $distance(Y,X_worst2)$, should be as similar as possible. | ||
Revision as of 10:03, 14 June 2013
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) distance(Y,X_best) > distance(Y,X_worst2) $$
For Contraction, the three distances $distance(Y,X_best)$, $distance(Y,X_worst)$, and $distance(Y,X_worst2)$, should be as similar as possible.
