Adaptive Population based Simplex - User contributions [en]

Programs

2013-09-06T06:59:23Z

Editor:

== Codes ==
{| class="wikitable"
|-
! Name and link !! Comments !! Date
|-
| [[File:APS standard m.zip|Standard APS]] || MatLab (zipped), by Mahamed G. H. Omran || 2013-09-05
|-
| [[Media:Standard APS C.zip|Standard APS]] || C (zipped), by Maurice Clerc. Include just an additional "tryMore" option || 2013-07-05
|-
| [[Media:Research_APS_C.zip|Research APS]] || C (zipped), by Maurice Clerc. A lot of options|| 2013-06-10
|-
| || ||
|}

Or you may simply want to play with the "[[APS online]]" version.

Programs

2013-09-05T20:08:07Z

Editor:

== Codes ==
{| class="wikitable"
|-
! Name and link !! Comments !! Date
|-
| [[Media:APS standard m.zip|Standard APS]] || MatLab (zipped), by Mahamed G. H. Omran || 2013-09-05
|-
| [[Media:Standard APS C.zip|Standard APS]] || C (zipped), by Maurice Clerc. Include just an additional "tryMore" option || 2013-07-05
|-
| [[Media:Research_APS_C.zip|Research APS]] || C (zipped), by Maurice Clerc. A lot of options|| 2013-06-10
|-
| || ||
|}

Or you may simply want to play with the "[[APS online]]" version.

File:APS standard m.zip

2013-09-05T20:07:23Z

Editor: Editor uploaded a new version of "File:APS standard m.zip": Added test_APS_standard.m

Standard APS, Matlab version

Talk:APS online

2013-07-11T20:33:36Z

Editor: /* Improve, enrich */ new section

== Improve, enrich ==

If you find a bug, or want to suggest a possible improvement, or want to add a function, just click on "Add topic", and write your comments. For a suggested new function, the Javascript code would be perfect, but not necessary. You may give the code in another language, or simply the mathematical formula

APS online

2013-07-11T20:09:34Z

Editor: Created page with "{{#iDisplay:http://aps-optim.info/APS_JS/APS_JS.htm}}"

Programs

2013-07-05T06:34:04Z

Editor: /* Codes */

== Codes ==
{| class="wikitable"
|-
! Name and link !! Comments !! Date
|-
| Standard APS || MatLab, by Mahamed G. H. Omran || 2013-06-10
|-
| [[Media:Standard APS C.zip|Standard APS]] || C (zipped), by Maurice Clerc. Include just an additional "tryMore" option || 2013-07-05
|-
| [[Media:Research_APS_C.zip|Research APS]] || C (zipped), by Maurice Clerc. A lot of options|| 2013-06-10
|-
| || ||
|}

File:Standard APS C.zip

2013-07-05T06:33:04Z

Editor: Editor uploaded a new version of "File:Standard APS C.zip"

== Licensing ==
{{GPL}}

File:Standard APS C.zip

2013-07-03T13:05:43Z

Editor: Editor uploaded a new version of "File:Standard APS C.zip": Fixed a small bug in the output format.

== Licensing ==
{{GPL}}

Presentation

2013-07-03T06:45:09Z

Editor:

<imagemap>
Image:Flow_chart.png|right|thumb|280px|Standard APS flow chart

rect 6 5 368 122 [[Initialisation|Initialisation]]
rect 198 234 563 346 [[Selection|Selection]]
rect 199 426 562 539 [[Expansion|Expansion]]
rect 198 617 563 732 [[Contraction|Contraction]]
rect 197 810 564 925 [[Local search|Local search]]
rect 134 547 268 565 [[Improvement|Improvement]]
rect 133 738 268 752 [[Improvement|Improvement]]
desc none
</imagemap>

APS has been inspired by some previous works, in particular the ones of Luo et al. <ref name=luo2012lowdimensional> Luo, C. & Yu, B. Low dimensional simplex evolution: a new heuristic for global optimization Journal of Global Optimization, 2012, 52, 45-55</ref> <ref name=luo_modifications_2013>Luo, C.; Zhang, S.-L. & Yu, B. Some modifications of low-dimensional simplex evolution and their convergence Optimization Methods and Software, 2013, 28, 54-81 </ref> on Low dimensional simplex evolution (LDSE).

Each phase is explained on its own page (just click on the corresponding area of the figure). After the initialisation of $N$ individuals, all the other phases are in a loop on them. In the explanation, the current individual is called $x_i$. This loop is itself repeated as long as a stop criterion is not met. As usually, the stop criterion is either a maximum number of fitness evaluations, or an error value found smaller than a predefined threshold.

<references/>

APS:About

2013-06-28T20:05:39Z

Editor: Created page with "If you work on the Adaptive Population Simplex method or its variants, or if you want to work on it, or if you just want to know more about it, this site is for you. In any c..."

If you work on the Adaptive Population Simplex method or its variants, or if you want to work on it, or if you just want to know more about it, this site is for you.

In any case, do not hesitate to contribute, at least on the Discussion pages.

Presentation

2013-06-28T18:14:44Z

Editor:

<imagemap>
Image:Flow_chart.png|right|thumb|280px|Standard APS flow chart

rect 6 5 368 122 [[Initialisation|Initialisation]]
rect 198 234 563 346 [[Selection|Selection]]
rect 199 426 562 539 [[Expansion|Expansion]]
rect 198 617 563 732 [[Contraction|Contraction]]
rect 197 810 564 925 [[Local search|Local search]]
rect 134 547 268 565 [[Improvement|Improvement]]
rect 133 738 268 752 [[Improvement|Improvement]]
desc none
</imagemap>

APS has been inspired by some previous works, in particular the ones of Luo et al. <ref name=luo2012lowdimensional> Luo, C. & Yu, B. Low dimensional simplex evolution: a new heuristic for global optimization Journal of Global Optimization, 2012, 52, 45-55</ref> <ref name=luo_modifications_2013>Luo, C.; Zhang, S.-L. & Yu, B. Some modifications of low-dimensional simplex evolution and their convergence Optimization Methods and Software, 2013, 28, 54-81 </ref>

Each phase is explained on its own page (just click on the corresponding area of the figure). After the initialisation of $N$ individuals, all the other phases are in a loop on them. In the explanation, the current individual is called $x_i$. This loop is itself repeated as long as a stop criterion is not met. As usually, the stop criterion is either a maximum number of fitness evaluations, or an error value found smaller than a predefined threshold.

<references/>

Presentation

2013-06-28T18:00:25Z

Editor:

Local search

2013-06-28T17:53:59Z

Editor: /* Basic local search (l0) */

== Basic local search (l0) ==
The idea is to perform a random search "around" a good point, but only if the current point is worse than average, i.e. if $\frac{f(x_i)}{N}>C$. In that case, 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}$.

=== 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)$.

Local search

2013-06-28T17:53:01Z

Editor: /* Basic local search (l0) */

== Basic local search (l0) ==
The idea is to perform a random search "around" a good point, but only if the current point is worse than average, i.e. if $C>\frac{f(x_i)}{N}$. In that case, 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}$.

=== 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)$.

Local search

2013-06-28T17:48:16Z

Editor: /* Basic local search (l0) */

== Basic local search (l0) ==
The idea is just to perform a random search "around" a good 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}$.

=== 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)$.

Local search

2013-06-28T17:14:18Z

Editor: /* Random choice */

== Basic local search (l0) ==
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}$.

=== 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)$.

Local search

2013-06-28T17:13:26Z

Editor: /* Random choice */

== Basic local search (l0) ==
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}$.

=== 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)$.

Local search

2013-06-28T17:12:32Z

Editor:

== Basic local search (l0) ==
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}$.

=== 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)$.

Initialisation

2013-06-28T16:55:49Z

Editor: /* Population cost */

== Basic initialisation (i0) ==
[[Image:Basic APS N vs D.png|right|thumb|400px|Population size vs Dimension]]
Draw at random $N$ agents (positions) in the search space, according to an uniform distribution.

$N=\max\left(40+2\sqrt{D},\sqrt{40^{2}+\left(D+2\right)^{2}}\right)\label{eq:N_popsize}$

where $D$ is the dimension of the search space. Note that $N$ needs to be at least equal to $D+1$.

We will need the volume $V(0)$ of the previous simplex. As no one has been defined yet, we simply set it to 0: 
$$V(0)=0$$

=== Population cost ===
Evaluate the $N$ individuals, thanks to the function $f$ we are studying. Save the best one as $Best$.

The sum of all values (they are all supposed to be positive, which is always possible), is the initial ''population cost'' $C$. We are trying here to minimise it.

Contraction

2013-06-28T16:55:02Z

Editor:

== Basic contraction (c0) ==
We combine four individuals, $x_{best}$, $x_{worst2}$, $w_{worst}$, and the current $x_i$ that has to be moved. 

The idea is that the gravity centre of the three first points may be interesting. However, this move is not applied on all dimensions, but only on some of them, according to the probability estimated at the end of the selection phase. So, finally, the formulae to define the new point $x_e$ are, for each dimension $d$: 
if $rand(0,1)<p)$ 
$ x_{c,d}=(x_{best,d}+w_{worst2,d}+w_{worst,d})/3$ 
else 
$ x_{c,d}=x_{i,d}$

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

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

Contraction

2013-06-28T16:54:41Z

Editor:

T== Basic contraction (c0) ==
We combine four individuals, $x_{best}$, $x_{worst2}$, $w_{worst}$, and the current $x_i$ that has to be moved. 

The idea is that the gravity centre of the three first points may be interesting. However, this move is not applied on all dimensions, but only on some of them, according to the probability estimated at the end of the selection phase. So, finally, the formulae to define the new point $x_e$ are, for each dimension $d$: 
if $rand(0,1)<p)$ 
$ x_{c,d}=(x_{best,d}+w_{worst2,d}+w_{worst,d})/3$ 
else 
$ x_{c,d}=x_{i,d}$

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

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

Contraction

2013-06-28T16:54:12Z

Editor: /* Basic contraction (c0) */

TO COMPLETE

== Basic contraction (c0) ==
We combine four individuals, $x_{best}$, $x_{worst2}$, $w_{worst}$, and the current $x_i$ that has to be moved. 

The idea is that the gravity centre of the three first points may be interesting. However, this move is not applied on all dimensions, but only on some of them, according to the probability estimated at the end of the selection phase. So, finally, the formulae to define the new point $x_e$ are, for each dimension $d$: 
if $rand(0,1)<p)$ 
$ x_{c,d}=(x_{best,d}+w_{worst2,d}+w_{worst,d})/3$ 
else 
$ x_{c,d}=x_{i,d}$

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

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

Reflection/Expansion

2013-06-28T16:49:46Z

Editor: /* Basic expansion (e0) */

== Basic expansion (e0) ==
We combine four individuals, $x_{best}$, $x_{worst2}$, $w_{worst}$, and the current $x_i$ that has to be moved. The idea is that a move from $w_{worst}$ to $w_{worst2}$ is probably a good one, so, on the contrary, the same move applied to $x_{best}$ is probably a bad one, i.e. it tends to deteriorate the position. But on the other hand, it also gives a chance to escape from the attraction basin of $x_{best}$.

Of course, for a unimodal landscape, this is a waste of time, but for multimodal ones, it may be useful. Moreover, this move is not applied on all dimensions, but only on some of them, according to the probability estimated at the end of the selection phase. So, finally, the formulae to define the new point $x_e$ are, for each dimension $d$: 

if $rand(0,1)<p)$ 
$ x_{e,d}=x_{best,d}+(w_{worst2,d}-w_{worst,d})$ 
else 
$ x_{e,d}=x_{i,d}$

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

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

.

Initialisation

2013-06-28T16:45:01Z

Editor: /* Basic initialisation (i0) */

== Basic initialisation (i0) ==
[[Image:Basic APS N vs D.png|right|thumb|400px|Population size vs Dimension]]
Draw at random $N$ agents (positions) in the search space, according to an uniform distribution.

$N=\max\left(40+2\sqrt{D},\sqrt{40^{2}+\left(D+2\right)^{2}}\right)\label{eq:N_popsize}$

where $D$ is the dimension of the search space. Note that $N$ needs to be at least equal to $D+1$.

We will need the volume $V(0)$ of the previous simplex. As no one has been defined yet, we simply set it to 0: 
$$V(0)=0$$

=== Population cost ===
Evaluate the $N$ individuals. Save the best one as $Best$.

The sum of all values (they are all supposed to be positive, which is always possible), is the initial ''population cost'' $C$. We are trying here to minimise it.

Initialisation

2013-06-28T16:44:18Z

Editor: /* Basic initialisation (i0) */

== Basic initialisation (i0) ==
[[Image:Basic APS N vs D.png|right|thumb|400px|Population size vs Dimension]]
Draw at random $N$ agents (positions) in the search space, according to an uniform distribution.

$N=\max\left(40+2\sqrt{D},\sqrt{40^{2}+\left(D+2\right)^{2}}\right)\label{eq:N_popsize}$

where $D$ is the dimension of the search space. Note that $N$ needs to be at least equal to $D+

We will need the volume $V(0)$ of the previous simplex. As no one has been defined yet, we simply set it to 0: 
$$V(0)=0$$

=== Population cost ===
Evaluate the $N$ individuals. Save the best one as $Best$.

The sum of all values (they are all supposed to be positive, which is always possible), is the initial ''population cost'' $C$. We are trying here to minimise it.

Reflection/Expansion

2013-06-28T16:38:21Z

Editor: /* Basic expansion (e0) */

Reflection/Expansion

2013-06-28T16:36:58Z

Editor: /* Basic expansion (e0) */

== Basic expansion (e0) ==
We combine four individuals, $x_{best}$, $x_{worst2}$, $w_{worst}$, and the current $x_i$ that has to be moved. The idea is that a move from $w_{worst}$ to $w_{worst2}$ is probably a good one, so, on the contrary, the same move applied to $x_{best}$ is probably a bad one, i.e. it tends to deteriorate the position. But on the other hand, it also gives a chance to escape from the attraction basin of $x_{best}$.

Of course, for a unimodal landscape, this is a waste of time, but for multimodal ones, it may be useful. Moreover, this move is not applied on all dimensions, but only on some of them, according to the probability estimated at the end of the selection phase. So, finally, the formulae to define the new point $x_e$ are, for each dimension $d$: 

if $rand(0,1)<p)$ 
:Indented line
$x_{e,d}=x_{best,d}+(w_{worst2,d}-w_{worst,d})$ 
else 
:Indented line
$x_{e,d}=x_{i,d}$

.

Reflection/Expansion

2013-06-28T16:36:20Z

Editor: /* Basic expansion (e0) */

== Basic expansion (e0) ==
We combine four individuals, $x_{best}$, $x_{worst2}$, $w_{worst}$, and the current $x_i$ that has to be moved. The idea is that a move from $w_{worst}$ to $w_{worst2}$ is probably a good one, so, on the contrary, the same move applied to $x_{best}$ is probably a bad one, i.e. it tends to deteriorate the position. But on the other hand, it also gives a chance to escape from the attraction basin of $x_{best}$.

Of course, for a unimodal landscape, this is a waste of time, but for multimodal ones, it may be useful. Moreover, this move is not applied on all dimensions, but only on some of them, according to the probability estimated at the end of the selection phase. So, finally, the formulae to define the new point $x_e$ are, for each dimension $d$: 

if $rand(0,1)<p)$ 
$x_{e,d}=x_{best,d}+(w_{worst2,d}-w_{worst,d})$ 
else $x_{e,d}=x_{i,d}$

.

Reflection/Expansion

2013-06-28T16:35:33Z

Editor: /* Basic expansion (e0) */

== Basic expansion (e0) ==
We combine four individuals, $x_{best}$, $x_{worst2}$, $w_{worst}$, and the current $x_i$ that has to be moved. The idea is that a move from $w_{worst}$ to $w_{worst2}$ is probably a good one, so, on the contrary, the same move applied to $x_{best}$ is probably a bad one, i.e. it tends to deteriorate the position. But on the other hand, it also gives a chance to escape from the attraction basin of $x_{best}$.

Of course, for a unimodal landscape, this is a waste of time, but for multimodal ones, it may be useful. Moreover, this move is not applied on all dimensions, but only on some of them, according to the probability estimated at the end of the selection phase. So, finally, the formulae to define the new point $x_e$ are, for each dimension $d$: 

if $rand(0,1)<p)$ $x_{e,d}=x_{best,d}+(w_{worst2,d}-w_{worst,d})$ 
else $x_{e,d}=x_{i,d}$

.

Reflection/Expansion

2013-06-28T16:35:02Z

Editor: /* Basic expansion (e0) */

== Basic expansion (e0) ==
We combine four individuals, $x_{best}$, $x_{worst2}$, $w_{worst}$, and the current $x_i$ that has to be moved. The idea is that a move from $w_{worst}$ to $w_{worst2}$ is probably a good one, so, on the contrary, the same move applied to $x_{best}$ is probably a bad one, i.e. it tends to deteriorate the position. But on the other hand, it also gives a chance to escape from the attraction basin of $x_{best}$.

Of course, for a unimodal landscape, this is a waste of time, but for multimodal ones, it may be useful. Moreover, this move is not applied on all dimensions, but only on some of them, according to the probability estimated at the end of the selection phase. So, finally, the formulae to define the new point $x_e$ are, for each dimension $d$: 

if $rand(0,1)<p)$ x_{e,d}=x_{best,d}+(w_{worst2,d}-w_{worst,d})$ 
else $x_{e,d}=x_{i,d}$

.

Reflection/Expansion

2013-06-28T16:34:39Z

Editor: /* Basic expansion (e0) */

== Basic expansion (e0) ==
We combine four individuals, $x_{best}$, $x_{worst2}$, $w_{worst}$, and the current $x_i$ that has to be moved. The idea is that a move from $w_{worst}$ to $w_{worst2}$ is probably a good one, so, on the contrary, the same move applied to $x_{best}$ is probably a bad one, i.e. it tends to deteriorate the position. But on the other hand, it also gives a chance to escape from the attraction basin of $x_{best}$.

Of course, for a unimodal landscape, this is a waste of time, but for multimodal ones, it may be useful. Moreover, this move is not applied on all dimensions, but only on some of them, according to the probability estimated at the end of the selection phase. So, finally, the formulae to define the new point $x_e$ are, for each dimension $d$: 

if $rand(0,1)<p) x_{e,d}=x_{best,d}+(w_{worst2,d}-w_{worst,d})$ 
else $x_{e,d}=x_{i,d}$

.

Reflection/Expansion

2013-06-28T16:34:08Z

Editor:

== Basic expansion (e0) ==
We combine four individuals, $x_{best}$, $x_{worst2}$, $w_{worst}$, and the current $x_i$ that has to be moved. The idea is that a move from $w_{worst}$ to $w_{worst2}$ is probably a good one, so, on the contrary, the same move applied to $x_{best}$ is probably a bad one, i.e. it tends to deteriorate the position. But on the other hand, it also gives a chance to escape from the attraction basin of $x_{best}$.

Of course, for a unimodal landscape, this is a waste of time, but for multimodal ones, it may be useful. Moreover, this move is not applied on all dimensions, but only on some of them, according to the probability estimated at the end of the selection phase. So, finally, the formulae to define the new point $x_e$ are, for each dimension $d$: 

if $rand(0,1)<p) x_{e,d}=x_{best,d}+(w_{worst2,d}-w_{worst,d}) 
else x_{e,d}=x_{i,d}

.

Selection

2013-06-28T16:15:14Z

Editor: /* Adaptive probability */

== Basic selection (s0) ==
# Select a simplex $S$ (i.e. $D+1$ individuals) at random. Be sure that the current one is in this list. If not, replace the last of the list by the current one.
# Select the three first ones.
# Sort them, by increasing order of value (fitness). They are $x_{best}$, $x_{worst2}$, and $w_{worst}$.

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

=== Adaptive probability ===
The rationale is the following: 
the more the simplex volume increases, the less the algorithm is successful, and the more one needs randomness to increase the diversity.

Compute the volume $V(1)$ of the simplex. If the previous volume is zero (in practice, too small) the probability $p$ is set to 0.5. If not, the formula is
$$
p=\frac{1}{1+e^{-\frac{V(1)-V(0)}{V(0)}}}
$$

After that, we simply set $V(0)=V(1)$, to save the simplex volume as the "previous" one.

Selection

2013-06-28T16:12:39Z

Editor:

== Basic selection (s0) ==
# Select a simplex $S$ (i.e. $D+1$ individuals) at random. Be sure that the current one is in this list. If not, replace the last of the list by the current one.
# Select the three first ones.
# Sort them, by increasing order of value (fitness). They are $x_{best}$, $x_{worst2}$, and $w_{worst}$.

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

=== Adaptive probability ===
Compute the volume $V(1)$ of the simplex. If the previous volume is zero (in practice, too small) the probability $p$ is set to 0.5. If not, the formula is
$$
p=\frac{1}{1+e^{-\frac{V(1)-V(0)}{V(0)}}}
$$

The rationale is the following: 
the more the simplex volume increases, the less the algorithm is successful, and the more one needs randomness to increase the diversity.

Initialisation

2013-06-28T15:57:53Z

Editor:

== Basic initialisation (i0) ==
[[Image:Basic APS N vs D.png|right|thumb|400px|Population size vs Dimension]]
Draw at random $N$ agents (positions) in the search space, according to an uniform distribution.

$N=\max\left(40+2\sqrt{D},\sqrt{40^{2}+\left(D+2\right)^{2}}\right)\label{eq:N_popsize}$

where $D$ is the dimension of the search space. Note that $N$ needs to be at least equal to $D+1$.

Evaluate the $N$ individuals. Save the best one as $Best$.

We will need the volume $V(0)$ of the previous simplex. As no one has been defined yet, we simply set it to 0: 
$$V(0)=0$$

Selection

2013-06-28T15:50:37Z

Editor:

== Basic selection (s0) ==
# Select a simplex $S$ (i.e. $D+1$ individuals) at random. Be sure that the current one is in this list. If not, replace the last of the list by the current one.
# Compute the volume $V_S$ of the simplex defined by these points.
# Select the three first ones.
# Sort them, by increasing order of value (fitness). They are $x_{best}$, $x_{worst2}$, and $w_{worst}$.

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

Selection

2013-06-28T15:47:35Z

Editor:

== Basic selection (s0) ==
# select a simplex S (i.e. $D+1$ individuals) at random;
# select the three first ones;
# sort them, by increasing order of value (fitness). They are $x_{best}$, $x_{worst2}$, and $w_{worst}$.

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

Initialisation

2013-06-28T15:46:01Z

Editor: /* Basic initialisation (i0) */

Selection

2013-06-28T15:38:56Z

Editor: /* Basic selection (s0) */

TO COMPLETE

== Basic selection (s0) ==
# select a simplex S (i.e. $D+1$ individuals) at random;
# select the three first ones;
# sort them, by increasing order of value (fitness). They are $x_{best}$, $x_{worst2}$, and $w_{worst}$.

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

Selection

2013-06-28T15:37:50Z

Editor: /* Basic selection (s0) */

TO COMPLETE

== Basic selection (s0) ==
# select a simplex S (i.e. $D+1$ individuals) at random;
# select the three first ones;
# sort them, by increasing order of value (fitness). They are $x_{best}$, $x_{worst2}$, and $w_{worst}.

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