sNES
Separable Natural Evolutionary Strategy

Giuseppe Cuccu, giuse@idsia.ch, Jan 2011

Single step for outside control

Distribution initialization

μinitrange={-1,1};
initμ[ndims_]:=RandomReal[μinitrange,ndims]
initσ[ndims_]:=Array[1&,ndims]
initμσ[ndims_]:={initμ[ndims],initσ[ndims]};

Optimizations from literature

(* CMA-optimized + declarative style *)
utilityFunction[n_]:=utilityFunction[n]=
Reverse[N[(((Max[0,#1]&)/@(Log[(n/2)-1]-Log[Range[n]]))/(Total[(Max[0,#1]&)/@(Log[(n/2)-1]-Log[Range[n]])]))-(1/n)]];

(* CMA-optimized *)
learningRate[dim_]:=N[((3+Log[dim])/(5 (Sqrt[dim])))]

(* Hansen & Ostermaier population size lower bound *)
populationSize[dim_]:=Max[4+Floor[3 Log[dim]],5]

sNES algorithm

(* Generate population, evaluate it and return a list of tuples {fit,pick} *)
scoredpicks[fit_,μ_,σ_,ndims_,popsize_]:=
Array[With[{pick=RandomVariate[NormalDistribution[],ndims]},
{fit[μ+σ×pick],pick}]&,popsize];

(* Single step for outside control *)
sNESstep[fit_,{μ_,σ_},ndims_,popsize_,ημ_,ησ_]:=
Module[{u,p,s,Jd,Js,newμ,newσ},
u=utilityFunction@popsize;
p=scoredpicks[fit,μ,σ,ndims,popsize];
s=p[[Ordering[p[[All,1]]],2]];
Jd=u.s;
Js=u.((s^2)-1);
newμ=μ+ημ×σ×Jd;
newσ=σ×Exp[ησ×Js/2];
{  newμ, newσ  }]

Testing

Test functions

testNSQ[x_]:=Total[-(x^2)]
testRosenbrock[x_]:=-Total[100 (((((x[[1;;-2]])^2)-x[[2;;-1]]))^2)+(((x[[1;;-2]]-1))^2)]

Table[Plot3D[test[{x,y}],
{x,-1,1},{y,-1,1}],
{test,{testNSQ,testRosenbrock}}]

Run control example

sNESrun[nepochs_,fitfn_,dim_,popsize_,ημ_,ησ_]:=
Nest[sNESstep[fitfn,#,dim,popsize,ημ,ησ]&,initμσ[dim],nepochs]

Test runs

{nepochs,ndims}={1000,100};
outNSQ=sNESrun[nepochs,testNSQ,ndims,populationSize@ndims,learningRate@ndims,learningRate@ndims];
TableForm[Mean/@outNSQ,TableHeadings->{{"Avg μ","Avg σ"},None}]

{nepochs,ndims}={10000,3};
outRosen=sNESrun[nepochs,testRosenbrock,ndims,populationSize@ndims,learningRate@ndims,learningRate@ndims]
TableForm[Mean/@outRosen,TableHeadings->{{"Avg μ","Avg σ"},None}]