The amoeba method in Lisp

Code: amoeba.lisp

The method searches for a local minimum of a function defined in an n-dimensional space.

An n-dimensional simplex — an “amoeba” — moves downhill along the surface of the function until it surrounds the minimum.

Then, the amoeba contracts around the minimum until its size is less than the tolerance value.

Wikipedia has a nice description of the algorithm: link

In my code, the amoeba is a list of n+1 lists of n-dimensional coordinates — n+1 vertices of an n-simplex.

The optional parameters are the tolerance, the maximum number of iterations, the distance function (for now I implemented only Euclidean but other distance functions can be added), and the parameters specifying how the amoeba moves (the coefficients of reflection, expansion, contraction and shrinking).

I tested the method on the Rosenbrock’s banana function and the Himmelblau’s function.

The code for both functions (rosenbrock-banana and himmelblau) is in the end of the file.

Published in: on 12/01/2013 at 20:30  Comments (1)  

The URI to TrackBack this entry is:

RSS feed for comments on this post.

One CommentLeave a comment

  1. This post really peaked my interest.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: