⚠️There's a newer version (1.2.0) of this package. Take me there.

General-purpose optimisation with SOMA

The soma package provides an R implementation of the Self-Organising Migrating Algorithm, a general-purpose, stochastic optimisation algorithm developed originally by Ivan Zelinka.

The algorithm's approach is similar to that of genetic algorithms, although it is based on the idea of a series of "migrations" by a fixed set of individuals, rather than the development of successive generations. It can be applied to any cost-minimisation problem with a bounded parameter space, and is robust to local minima. Further details of the algorithm, and implementations for other languages, can be found at the SOMA home page. Only the "all-to-one" strategy is currently implemented in this package.

Usage

The soma() function provides the R interface to the SOMA algorithm. It is called with a function to minimise, a list consisting of minimum and maximum bounds for each parameter, and an optional list of options. The cost function must take a numeric vector of parameters as its first argument, and return a numeric scalar representing the associated cost value.

As an example, consider the two-dimensional version of Rastrigin's function, which has many local minima, and a global minimum of zero at (0,0).

rastrigin <- function(a) 20 + a[1]^2 + a[2]^2 - 10*(cos(2*pi*a[1])+cos(2*pi*a[2]))

The function surface looks like this (image from Wikimedia Commons):

We can attempt to find the global minimum with the call

x <- soma(rastrigin, list(min=c(-5.12,-5.12),max=c(5.12,5.12)))
# INFO: Starting SOMA optimisation
# INFO: Migration limit (20) reached - stopping
# INFO: Leader is #4, with cost 1.67e-05

We can see from the informative output that on this run the best location has a cost function of 1.67e-05, close to the true minimum value of zero. The location in search space is

print(x$population[,x$leader])
# [1] -1.005039e-05  2.896569e-04

Again, this is very close to the true location of (0,0). Finally, we can plot the progress of the optimisation, showing the best cost function value at each iteration:

plot(x)

We observe that there is an initial, rapid decrease in the cost function value of the "leader"—the individual with the lowest value—followed by further, smaller steps downwards towards zero as the algorithm progresses.

Options

The supported options are as follows. The defaults are as recommended in the reference below.

Option nameDescriptionDefault value
pathLengthThe distance towards the leader that individuals may migrate. A value of 1 corresponds to the leader's position itself, and values greater than one (recommended) allow for some overshoot.3
stepLengthThe granularity at which potential steps are evaluated. It is recommended that the pathLength not be a whole multiple of this value.0.11
perturbationChanceThe probability that individual parameters are changed on any given step.0.1
minAbsoluteSepThe smallest absolute difference between the maximum and minimum cost function values. If the difference falls below this minimum, the algorithm will terminate.0
minRelativeSepThe smallest relative difference between the maximum and minimum cost function values. If the difference falls below this minimum, the algorithm will terminate.0.001
nMigrationsThe maximum number of migrations to complete.20
populationSizeThe number of individuals in the population. It is recommended that this be somewhat larger than the number of parameters being optimised over, and it should not be less than 2.10

Reference

I. Zelinka (2004). SOMA - self-organizing migrating algorithm. In G.C. Onwubolu & B.V. Babu, eds, New optimization techniques in engineering. Volume 141 of "Studies in Fuzziness and Soft Computing", pp. 167-217. Springer.

Copy Link

Version

Down Chevron

Install

install.packages('soma')

Monthly Downloads

204

Version

1.1.1

License

GPL-2

Issues

Pull Requests

Stars

Forks

Maintainer

Last Published

November 25th, 2014

Functions in soma (1.1.1)