Difference between revisions of "Local search"

Revision as of 19:12, 28 June 2013

The idea is just to perform a random search "around" the current best point. So the process is the following:

Compute the maximum distance $\rho$ between $x_{best}$ and all the other individuals of the population.
Select the $x_l$ position at random in the hypersphere of centre $x_{best}$ and of radius $\rho$ . The basic random choice makes use of two distributions, an uniform one, and a non-uniform one (see below).

If $x_{l}$ is better than $x_i$ , decrease the population cost $C\leftarrow C-f(x_i)+f(x_l)$

If $x_{l}$ is better than the best ever found (i.e. $Best$ ), set $Best=x_{l}$ .

The distribution that is used is itself selected at random (uniform distribution) between two ones:

the uniform one. The components of the direction vector follow the normalised Gaussian distribution, and the radius is $r=\rho*rand(0,1)^{\frac{1/D}}$
a non uniform one (more dense near to the centre). Here the radius is simply $r=\rho*rand(0,1)$ .

@@ Line 1: / Line 1: @@
-TO COMPLETE
 == Basic local search (l0) ==
-Define a hypersphere around the best point of the three ones defined in the selection phase.<br />
+The idea is just to perform a random search "around" the current best point. So the process is the following:
-Radius= maximum distance to the other vertices of the simplex
+* Compute the maximum distance  $\rho$  between  $x_{best}$  and all the other individuals of the population.
+* Select the  $x_l$  position at random in the hypersphere of centre  $x_{best}$  and of radius  $\rho$ . The basic random choice makes use of two distributions, an uniform one, and a non-uniform one (see below).
+If  $x_{l}$  is better than  $x_i$ , decrease the population cost
+ $C\leftarrow C-f(x_i)+f(x_l)$
+If  $x_{l}$  is better than the best ever found (i.e.  $Best$ ), set  $Best=x_{l}$ .
-The test position is chosen at random in the hypersphere. Random direction (uniform), random radius (uniform), which implies that the distribution is '''not''' random (more dense near to the centre)
+=== Random choice ===
+The distribution that is used is itself selected at random (uniform distribution) between two ones:
+# the uniform one. The components of the direction vector follow the normalised Gaussian distribution, and the radius is  $r=\rho*rand(0,1)^{\frac{1/D}}$
+# a non uniform one (more dense near to the centre). Here the radius is simply  $r=\rho*rand(0,1)$ .