Search and Optimisation Streams

After an initial spurt of Javascript hacking, the search algorithm pages in my Wiki seem to have stagnated. Have I given up on yet another project? Not quite; I’ve been building it into a library!

I realised that it’s all well and good explaining what search, optimisation, metaheuristics and the like are, but this information is already available elsewhere. The problem with these techniques is not obscurity (most programmers have probably heard of genetic algorithms, at least), and it’s not a lack of utility. To me, two of the main problems are: 1) There are few simple, off-the-shelf implementations available (I don’t count convoluted code like new GALib.GAFactory(crossoverApplicator = new GenericBinaryCrossoverApplicator(0.3777392), mutationRateDeterminator = new GenericAbstractMutatorFactoryBean(2)) as simple!). Those who like to tweak should be able to, but those willing to sacrifice performance for simplicity should be able to. 2) Lack of API consistency. What if a genetic algorithm turns out to be ill-suited to a problem? Currently, such integration work would probably have to be scrapped, and a different tactic integrated from scratch. If we’ve already got our infrastructure set up (solution decomposition, fitness functions, etc.), why can’t we swap a Genetic Algorithm for a Harmony Search, or a Particle Swarm Optimisation, or a Neural Network, or whatever?

Whilst there are undoubtedly many other problems with current metaheuristics, my library attempts to solve these 2 issues. I’ve mainly focused on consistency, since I think a few deep, general rules are simpler than many shallow, specific ones. Below, I’ll explain the decisions I’ve made in the process.

The most obvious part of the search pages on my wiki (at least as they existed when I designed the library) is that very little code differs between each technique. Pretty much everything is taken up by the support network (visualisation, resource management, etc.), and the heart of every algorithm can usually be expressed in one line. Added to this, there is a clear relationship between many search algorithms. For example:

Random choice: By definition, doesn’t follow any pattern. Uses a probability distribution that isn’t neccessarily uniform (eg. a decreasing distribution over the Naturals).

Enumeration: Follows a deterministic pattern. Requires that all of the possibilities are ordered one-dimensionally. Each solution depends only on the last (ie. it’s Markov).

Random walk: Requires that all of the possibilities are ordered, but potentially in many dimensions. These orderings are reminiscent of enumerations, as is its Markov property. The random choice taken at each step is, of course, reminiscent of random choice. Note that even with an effective solution topology, it’s usually possible to use several coordinate systems (eg. Manhattan, polar, etc.).

Hill-climbing: Hill-climbing says that we should back-track a step if a new solution isn’t as good as the previous one. This isn’t restricted to any algorithm in particular, it can be applied to many.

Simulated annealing: This is like hill-climbing, but probabilistically allows solutions with a worse fitness, based on the difference between the fitnesses (big jumps down are less likely) and an ever-decreasing “temperature” (lower temperature means less chance of jumping down). The “temperature” makes this technique very interesting, since the choice of an appropriate temperature gradient is itself a search problem. Note that if we keep the temperature zero, we recover hill-climbing behaviour.

Tabu search: Tabu search is similar to hill-climbing, and simulated annealing if we use probabalistic tabus. Tabu search applies a (potentially stateful) predicate to each new solution, and backtracks if the predicate fails. Clearly we can use tabu search to implement a hill-climber, as well as a simulated annealing if we keep internal state for the temperature.

Mutation: Mutation treats solutions as being made of separate parts, and swaps some of these at a time rather than the whole solution. Again, this is clearly a general technique which can be used in multiple algorithms, as long as the solutions are amenable to being subdivided.

Population: A population keeps track of many solutions at once, so there is more than one “current” solution. Like the above techniques, this is generic enough to apply on top of many other algorithms. The population size, and how to select which solutions to use next, require search algorithms themselves.

Crossover: Crossover, like mutation, requires solutions that are subdivided. It also requires a population. It selects a few candidates, then creates new solutions by swapping around some sections of the candidates. Note that we may also treat the selection of crossover points as a search task.

Artificial selection: This maintains a population, but requires that the least-fit solutions are discarded if new solutions have higher fitness. This is a form of distributed hill-climbing. We could imagine generalising this analogously to simulated annealing and tabu search. Again, it can be applied on top of many other algorithms.

Genetic algorithm: A genetic algorithm maintains a population and applies both crossover and mutation. Sophisticated genetic algorithms are already employing inner search algorithms, eg. to bias the selection and mutation probabilities.

Extremal optimisation: This requires that a solution can be broken into parts, and that the fitness of the parts can be determined. The canonical approach is to consider a single solution and to keep replacing the least-fit part with a randomly chosen alternative. However, this can be considered as an amalgamation of a few different strategies, which could be varied: how large the population should be (in the canonical example, a population of 1), how the fitness of a solution’s parts determines what is changed (ie. always choosing the least fit part), and how to construct the new solution (random choice, in the canonical version).

Stream Combinators

As a wet-behind-the-ears functional programmer, the consistency of this domain told me one thing: use a combinator library. The idea of a library should be familiar to any programmer; a collection of generally useful, hopefully compatible, code which solves common problems. Unfortunately the idea of combinators may not. Simply put, a combinator is a function which accepts some objects, and produces different objects of the same type. For example, addition, subtraction and multiplication are combinators; they accepts numbers and give out numbers. Combinators can have no internal state and cannot cause side-effects (which is why they’re popular with functional programmers). With these properties, we are free to combine combinators in arbitrary ways (hence the name); if we have some numbers, we can always add some, subtract some and multiply some (although we can’t always divide, due to zero).

In my case, the combinators accept search algorithms and give out search algorithms. Given some search algorithms, we can always send them through our combinators. The obvious thing to do once we’ve decided on using combinators is to look at a desirable search algorithm, for example a genetic algorithm, and break it down into simpler parts. As stated above, a genetic algorithm needs a population, artificial selection, mutation (which is a form of random walk, which is a form of accumulator) and crossover. In each case, we tease apart the components until we can’t get any simpler. While we’re at it, we also parameterise the algorithms as much as possible. For example, if we want to bias the mutation of a genetic algorithm, all we should have to do is choose a different random number generator; the rest of the existing functions should carry on working as before (although I’m still working out the best way to implement GAs ;) ).

To represent a search algorithm, I decided to use thunks. Since Javascript functions are closures, these serve nicely as streams of values. This fits well with lazy functional programming, where an often-used technique is to create a lazy list of all possible results, then pop values off it until an acceptable one is found. This is exactly the case with an optimisation stream; we can keep pulling values out.

To create more and more elaborate (and hopefully powerful) algorithms, the library contains a wealth of higher-order functions which act as stream combinators. A stream combinator is a function which takes one or more streams or other values as arguments, and returns a new stream. For example, there is an interleave combinator which takes an array of streams and returns a stream which interleaves the values of each. In fact, the interleave combinator is a specialisation of the more general chooser combinator. chooser takes a stream of integers (choices) and an array of streams. It returns a stream of values taken from the given streams, where the stream is chosen by index, based on the next choice value. For example, if we use a stream of all zeros (which we can obtain by calling zeros()) as our choices then we would keep getting values from the first stream in the array.

interleave is simply chooser where the choice is fixed to increment each time (chooser applies % streams.length to its choices for us). To see how simple this is, let’s see the code:

var chooser = c(function(choices, streams) {
    // Interleaves N streams according to a stream of
    // integer choices from 0 to N-1
    return map(
        subscript(streams),
        map(
            modulus(streams.length),
            choices
        )
    );
});

var interleave = chooser(counter());

As you can see, this is written in a very functional style. There are some auxiliary functions being used here which I should probably explain:

The c function, which chooser’s definition is wrapped in, is the Curry function which I explained in an earlier blog post. It allows us to supply a function’s arguments a few at a time. All multi-argument functions in the search streams library are wrapped in c to make them Curryable. Notable uses of Currying here are the fact that interleave only supplies one argument to chooser (since, as we said above, it simply fixes the choice stream).

We also only give one argument to the binary functions subscript (which returns first argument[second argument]) and modulus (which returns first argument % second argument).

The map combinator sends the results of a stream through a function.

Finally counter() gives us a stream of the Natural numbers (0, 1, 2, …).

As you can see, the nice property of combinators is that they compose nicely (as you would hope!). The result of one combinator can be passed as an argument to another. Indeed, the chain of map -> chooser -> interleave doesn’t stop there. There are combinators which specialise the interleave combinator; notably the exhaustive combinator, which interleaves its argument with a brute-force enumeration. By wrapping a stream in exhaustive, we may at worst halve its rate of convergence, but we guarantee that a solution will eventually be found, if there is one in the domain (since the brute-force enumeration will eventually find one).

The code is available, as always, in [Git] 1 and is Public Domain. I plan to show off some examples here at some point, but given my track record for abandoning code we’ll just have to see ;)