techSideUp(): PSO

PSO is Particle Swarm Optimization. A simple but powerful artificial intelligence field. In its simplest form, PSO is composed of a problem space with a certain solution or best position in it. Particles are scattered across this problem space. The particles each have a local fitness value according to their positions relative to the global best position. According to a simple algorithm displayed below, the particles evolve and begin to converge upon the solution to the problem in the problem space.

Algorithm:

Let there be

n

particles, each with associated positions $\mathbf{x}_i \in \mathbb{R}^m$ and velocities $\mathbf{v}_i \in \mathbb{R}^m$ , $i = 1, \ldots, n$ . Let $\hat{\mathbf{x}}_i$ be the current best position of each particle and let $\hat{\mathbf{g}}$ be the global best.

Initialize $\mathbf{x}_i$ and $\mathbf{v}_i$ for all $i$ . One common choice is to take $\mathbf{x}_{ij} \in U[a_j, b_j]$ and $\mathbf{v}_i = \mathbf{0}$ for all $i$ and $j = 1, \ldots, m$ , where $a j, b j$ are the limits of the search domain in each dimension.
$\hat{\mathbf{x}}_i \leftarrow \mathbf{x}_i$ and $\hat{\mathbf{g}} \leftarrow \min_{\mathbf{x}_i} f(\mathbf{x}_i), i = 1, \ldots, n$ .

While not converged:
- For :
  - $\mathbf{x}_i \leftarrow \mathbf{x}_i+\mathbf{v}_i$ .
  - $\mathbf{v}_i \leftarrow {\omega}\mathbf{v}_i+c_1\mathbf{r}_1\circ(\hat{\mathbf{x}}_i-\mathbf{x}_i)+c_2\mathbf{r}_2\circ(\hat{\mathbf{g}}-\mathbf{x}_i)$ .
  - If $f(\mathbf{x}_i) < f(\hat{\mathbf{x}}_i)$ , $\hat{\mathbf{x}}_i \leftarrow \mathbf{x}_i$ .
  - If $f(\mathbf{x}_i) < f(\hat{\mathbf{g}})$ , $\hat{\mathbf{g}} \leftarrow \mathbf{x}_i$ .

Note the following about the above algorithm:

$ω$ is an inertial constant. Good values are usually slightly less than 1.
$c 1$ and $c 2$ are constants that say how much the particle is directed towards good positions. They represent a "cognitive" and a "social" component, respectively, in that they affect how much the particle's personal best and the global best (respectively) influence its movement. Usually, we take $c_1, c_2 \approx 1$ but this need not be the case.
$\mathbf{r}_1, \mathbf{r}_2$ are two random vectors with each compenent generally a uniform random number between 0 and 1.
$\circ$ operator indicates element-by-element multiplication i.e. the Hadamard matrix multiplication operator.

techSideUp()

Tuesday, January 9, 2007

PSO

1 comment:

Blog Archive