Talk:Presentation - Revision history

78.229.106.132: /* Which order for the phases? */ new section

2013-06-18T19:47:14Z

‎Which order for the phases?: new section

MClerc: /* Contraction */

2013-06-18T19:05:19Z

‎Contraction

MClerc: /* Combinatorial APS? */

2013-06-18T19:04:31Z

‎Combinatorial APS?

MClerc: /* Contraction */

2013-06-14T16:31:38Z

‎Contraction

MClerc: /* Expansion (reflection) */

2013-06-14T16:31:15Z

‎Expansion (reflection)

MClerc: /* Expansion (reflection) */

2013-06-14T16:30:56Z

‎Expansion (reflection)

MClerc: /* Combinatorial APS? */

2013-06-14T16:30:19Z

‎Combinatorial APS?

MClerc: /* Combinatorial APS? */

2013-06-14T09:18:05Z

‎Combinatorial APS?

MClerc: /* Combinatorial APS? */

2013-06-14T09:17:28Z

‎Combinatorial APS?

MClerc: /* Combinatorial APS? */

2013-06-14T09:08:37Z

‎Combinatorial APS?

← Older revision		Revision as of 19:47, 18 June 2013
Line 32:		Line 32:
	--------		--------
	However, in APS, the formulae for Expansion/Reflection and Contraction are applied in fact only for some dimensions, not for all, according to an adaptive probability threshold. In order to "simulate" the same method, we should apply the combinatorial equivalent formula only on a subset of the dimensions. The difficulty is that we are then not sure that the global result is still a permutation (we may generate two times the same element). How to cope with it?		However, in APS, the formulae for Expansion/Reflection and Contraction are applied in fact only for some dimensions, not for all, according to an adaptive probability threshold. In order to "simulate" the same method, we should apply the combinatorial equivalent formula only on a subset of the dimensions. The difficulty is that we are then not sure that the global result is still a permutation (we may generate two times the same element). How to cope with it?
		+
		+	== Which order for the phases? ==
		+
		+	In standard APS, after initialisation, we have three phases in the loop, namely
		+	# Expansion/Réflection
		+	# Contraction
		+	# Local search
		+
		+	However, there is for the moment no theoretical reason for this order. So, it may be modified. For example, let $p_Exp(t)$, $p_Con(t)$, and $p_Ls(t)$, the probabilities of improvement by using each phase at time $t$. Of course, we do not know them. However, they may be adaptively estimated by analysing the history, or, at least, they may be sorted. For example, we often have
		+	$$ p_Con(t) > p_Ls(t) > p_Exp(t) $$
		+
		+	In such a case, if want an algorithm that quickly find an acceptable solution (but with a higher risk to be trapped in a local optimum), the order should be
		+	# Contraction
		+	# Local search
		+	# Expansion/Reflection
		+
		+	Another method could be to simply randomly permutate the phases at each iteration.

← Older revision		Revision as of 19:05, 18 June 2013
Line 31:		Line 31:

	--------		--------
−	However, in APS, the formulae for Expansion/Reflection and Contraction are applied in fact only for some dimensions, not for all, according to an adaptive probability threshold. In order to "simulate" the same method, we should apply the combinatorial equivalent formula only on a subset of the dimensions. Th difficulty is that we are then not sure that the global result is still a permutation (we may generate two times the same element). How to cope with it?	+	However, in APS, the formulae for Expansion/Reflection and Contraction are applied in fact only for some dimensions, not for all, according to an adaptive probability threshold. In order to "simulate" the same method, we should apply the combinatorial equivalent formula only on a subset of the dimensions. The difficulty is that we are then not sure that the global result is still a permutation (we may generate two times the same element). How to cope with it?

@@ Line 9: / Line 9: @@
 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, [http://clerc.maurice.free.fr/pso/pso_tsp/Discrete_PSO_TSP.htm 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. Here are a few ideas of how the specific operators could be defined. In what follows, we keep the same adaptive probability $p$ threshold than in standard APS. It means that we have to modify only
+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, [http://clerc.maurice.free.fr/pso/pso_tsp/Discrete_PSO_TSP.htm for PSO].
 === Expansion (reflection) ===
@@ Line 18: / Line 23: @@
 $$
-It is formally equivalent to the PSO operator "new_position = position + velocity", for the "velocity" is anyway the difference of two positions.  We already know how to compute the difference of two permutations, and how to add two permutations. We could apply here these two operators. However, in APS, the above formula is applied in fact only for some dimensions, not for all, according to the probability threshold. In order to "simulate" the same method, we have to apply the combinatorial equivalent formula only on a subset of the dimensions.
+It is formally equivalent to the PSO operator "new_position = position + velocity", for the "velocity" is anyway the difference of two positions.
 === Contraction ===
-We "add" the three permutations $X_{best}$, $X_{worst}$, and $X_{worst2}$, and we "multiply" the result by 1/3.
+$$
-=== Local search ===
+--------
-The easiest one: we  just have to apply a "small" number of transpositions.
+However, in APS, the formulae for Expansion/Reflection and Contraction are applied in fact only for some dimensions, not for all, according to an adaptive probability threshold. In order to "simulate" the same method, we should apply the combinatorial equivalent formula only on a subset of the dimensions. Th difficulty is that we are then not sure that the global result is still a permutation (we may generate two times the same element). How to cope with it?

@@ Line 21: / Line 21: @@
 === Contraction ===
-We "add" the three permutations $X_{best}$, $X_{worst}, and $X_{worst2}$, and we "multiply" the result by 1/3.
+We "add" the three permutations $X_{best}$, $X_{worst}$, and $X_{worst2}$, and we "multiply" the result by 1/3.
 === Local search ===
 The easiest one: we  just have to apply a "small" number of transpositions.

@@ Line 15: / Line 15: @@
 In standard this combination is
 $$
-Y=X_{worst2}+(X_{worst}-X_{best}\label{eq:expansion}
+Y=X_{worst2}+(X_{worst}-X_{best})\label{eq:expansion}
 $$

@@ Line 9: / Line 9: @@
 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.
+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, [http://clerc.maurice.free.fr/pso/pso_tsp/Discrete_PSO_TSP.htm 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. Here are a few ideas of how the specific operators could be defined. In what follows, we keep the same adaptive probability $p$ threshold than in standard APS. It means that we have to modify only
-The specific Local search operator is the easiest one to define: we have just to apply a "small" number of transpositions.
+=== Expansion (reflection) ===
+We have three "positions" (i.e. permutations), $X_{best}$, $X_{worst}$, and $X_{worst2}$ (the second worst), we have to combine them.
-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
+In standard this combination is
-$$
-distance(Y,X_{best}) > distance(Y,X_{worst})
-$$
-and<br />
 $$
-distance(Y,X_{best}) > distance(Y,X_{worst2})
+Y=X_{worst2}+(X_{worst}-X_{best}\label{eq:expansion}$
 $$
-For Contraction, the three distances $distance(Y,X_{best})$, $distance(Y,X_{worst})$, and $distance(Y,X_{worst2})$, should be as similar as possible.
+=== Contraction ===
-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}$.
+=== Local search ===

← Older revision		Revision as of 09:18, 14 June 2013
Line 29:		Line 29:
	For Contraction, the three distances $distance(Y,X_{best})$, $distance(Y,X_{worst})$, and $distance(Y,X_{worst2})$, should be as similar as possible.		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}$.	+	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}$.