Adaptive Population based Simplex - User contributions [en]

Presentation

2013-10-17T10:24:14Z

MOmran:

<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/>

Presentation

2013-10-17T10:23:45Z

MOmran:

<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|Reflection]]
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/>

Contraction

2013-10-17T10:21:39Z

MOmran:

== 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_c$ 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-10-17T10:16:49Z

MOmran:

== Basic reflection (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_{r,d}=x_{best,d}+(w_{worst2,d}-w_{worst,d})$ 
else 
$ x_{r,d}=x_{i,d}$

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

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

.

Reflection/Expansion

2013-10-17T10:15:54Z

MOmran: Expansion to Reflection

== Basic reflection (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_{r,d}=x_{best,d}+(w_{worst2,d}-w_{worst,d})$ 
else 
$ x_{r,d}=x_{i,d}$

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

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

.

Presentation

2013-10-17T10:14:24Z

MOmran:

Presentation

2013-10-17T10:13:45Z

MOmran:

<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 [[Reflection|Reflection]]
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/>

Presentation

2013-10-17T10:13:15Z

MOmran: Change Expansion to Reflection

<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 [[Reflection|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/>

Welcome

2013-10-16T21:45:19Z

MOmran:

'''<big>A</big>daptive <big>P</big>opulation based <big>S</big>implex (<big>APS</big>)'''



a powerful tuning-free optimization method

== Getting started ==
If you do not know APS, please go to the [[Presentation]] page. And do not hesisate to use its Discussion tab.

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

Consult the [//meta.wikimedia.org/wiki/Help:Contents User's Guide] for information on using the wiki software.

{{#iDisplay:http://aps-optim.info/Clustrmaps.htm}}

Programs

2013-07-06T07:26:58Z

MOmran: /* Codes */

== Codes ==
{| class="wikitable"
|-
! Name and link !! Comments !! Date
|-
| [[Media:APS standard m.zip|Standard APS]] || MatLab (zipped), by Mahamed G. H. Omran || 2013-07-06
|-
| [[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:APS standard m.zip

2013-07-06T07:25:05Z

MOmran: Standard APS, Matlab version

Standard APS, Matlab version