Brief Simplex Search Primer

The simplex algorithm is commonly applied to solve linear programming problems. It is relatively effective on noisy fitness landscapes but often does not sample the entire search space.

A canonical simplex search algorithm places N+1 points randomly in the N dimensional search space. The worst point is reflected across the plane defined by the other N points. Then the points are contracted or expanded according to the characteristics of the search space that they cover. These two steps are repeatted until some convergence criteria are satisfied. In two or three dimensional space, the set of points resemble an ameoba creeping around to the global maxima.

Algorithm Implemented in GAUL

1. Generate sample points and ensure that these initial solutions are scored.
2. Compute the vector average of all solutions except the least fit. Exploration will proceed along the vector from the least fit point to that vector average.
3. Check for convergence and restart if needed.
4. Simplex reflection - Extrapolate away from worst point.
5. Evaluate the function at this reflected point.
6. If the new solution is fitter than the previously fittest solution, attempt an additional extrapolation otherwise perform a contraction of the simplex along one dimension, away from worst point.
7. Continue at 2 unless specified number of iterations have been performed.

Using the GAUL Simplex Search

A general simplex search algorithm is implemented in GAUL. It is used in a very similar way to the tabu search algorithm. One restriction of the simplex algorithm is that the chromosome must be mapped onto a double-precision floating-point array.