Adaptive Population based Simplex - User contributions [en]

Sandbox

2013-07-16T17:02:43Z

78.229.106.132:

== Math test ==
Use LaTeX syntax. 

Warning: the Preview doesn't work for mathematical expressions. You have to Publish (or Save page).

$N=20*\sqrt{D}$

$$
\operatorname{erfc}(x) =
\frac{2}{\sqrt{\pi}} \int_x^{\infty} e^{-t^2}\,dt =
\frac{e^{-x^2}}{x\sqrt{\pi}}\sum_{n=0}^\infty (-1)^n \frac{(2n)!}{n!(2x)^{2n}}
$$

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

== Text + Image Map ==
<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>
The main idea was to define ... 

...

...
== Test ==

...

Sandbox

2013-07-16T16:58:40Z

78.229.106.132:

Sandbox

2013-07-16T16:58:04Z

78.229.106.132:

== Math test ==
Use LaTeX syntax. 

Warning: the Preview doesn't work for mathematical expressions. You have to Publish (or Save page).

$N=20*sqrt{D}$

$$
\operatorname{erfc}(x) =
\frac{2}{\sqrt{\pi}} \int_x^{\infty} e^{-t^2}\,dt =
\frac{e^{-x^2}}{x\sqrt{\pi}}\sum_{n=0}^\infty (-1)^n \frac{(2n)!}{n!(2x)^{2n}}
$$

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

== Text + Image Map ==
<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>
The main idea was to define ... 

...

...
== Test ==

...

...

Sandbox

2013-07-16T16:56:34Z

78.229.106.132:

== Math test ==
Use LaTeX syntax. 

Warning: the Preview doesn't work for mathematical expressions. You have to Publish (or Save page).

$N=20sqrt{D}$

$$
\operatorname{erfc}(x) =
\frac{2}{\sqrt{\pi}} \int_x^{\infty} e^{-t^2}\,dt =
\frac{e^{-x^2}}{x\sqrt{\pi}}\sum_{n=0}^\infty (-1)^n \frac{(2n)!}{n!(2x)^{2n}}
$$

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

== Text + Image Map ==
<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>
The main idea was to define ... 

...

...
== Test ==

...

...

Talk:Presentation

2013-06-18T19:47:14Z

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

== Combinatorial APS? ==
For some problems that are at least partly discrete, the basic APS applies a ''quantisation'' operator. If the quantum is $q_{d}$ for
the dimension $d$, the operator is defined by 

$$
x_{i,d}\leftarrow q_{d}\left\lfloor \left(0.5+x_{i,d}/q_{d}\right)\right.\label{eq:quantis}
$$ 

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].

Let us consider the canonical case in which the search space is the set of permutations of $D$ different elements. We know how to "substract" two permutations, how to "add" two permutations, how to "multiply" a permutation by a real coefficient. At first glance, it is all we need to define a combinatorial APS.

=== Local search ===
The easiest one: we just have 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.
In standard this combination is
$$
Y=X_{worst2}+(X_{worst}-X_{best})\label{eq:expansion}
$$

It is formally equivalent to the PSO operator "new_position = position + velocity", for the "velocity" is anyway the difference of two positions.

=== Contraction ===
$$
Y=(1/3)*(X_{best}+X_{worst2}+X_{worst})\label{eq:contraction}
$$

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

Programs

2013-06-16T20:36:39Z

78.229.106.132: /* 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-06-15
|-
| [[Media:Research_APS_C.zip|Research APS]] || C (zipped), by Maurice Clerc. A lot of options|| 2013-06-10
|-
| || ||
|}

Sandbox

2013-06-16T19:56:59Z

78.229.106.132: /* Text + picture */

== Math test ==
Use LaTeX syntax. 

Warning: the Preview doesn't work for mathematical expressions. You have to Publish (or Save page).

$N=20sqrt{D}$

$$
\operatorname{erfc}(x) =
\frac{2}{\sqrt{\pi}} \int_x^{\infty} e^{-t^2}\,dt =
\frac{e^{-x^2}}{x\sqrt{\pi}}\sum_{n=0}^\infty (-1)^n \frac{(2n)!}{n!(2x)^{2n}}
$$

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

== Text + Image Map ==
The main idea was to define ... 

...

<imagemap>
Image:Flow_chart.png|right|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>

Sandbox

2013-06-16T19:36:56Z

78.229.106.132:

People

2013-06-09T18:15:27Z

78.229.106.132: Created page with "People"

People

Papers

2013-06-09T18:15:05Z

78.229.106.132: Created page with "Papers"

Papers

Programs

2013-06-09T18:14:47Z

78.229.106.132: Created page with "Programs"

Programs

APS:Community portal

2013-06-09T18:14:23Z

78.229.106.132: Created page with "Community portal"

Community portal

Welcome

2013-06-09T08:50:23Z

78.229.106.132:

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

a powerful parameter-free optimization method

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

== Getting started ==
* [//www.mediawiki.org/wiki/Manual:Configuration_settings Configuration settings list]
* [//www.mediawiki.org/wiki/Manual:FAQ MediaWiki FAQ]
* [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce MediaWiki release mailing list]

Welcome

2013-05-27T13:19:36Z

78.229.106.132:

'''Adaptive Population based Simplex'''

a powerful parameter-free optimization method

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

== Getting started ==
* [//www.mediawiki.org/wiki/Manual:Configuration_settings Configuration settings list]
* [//www.mediawiki.org/wiki/Manual:FAQ MediaWiki FAQ]
* [https://lists.wikimedia.org/mailman/listinfo/mediawiki-announce MediaWiki release mailing list]