Randomized, but not Random

The first thing to understand about randomized (stochastic) search is that it is not the same thing as random search. Not even close.

It is this fundamental confusion that is behind many people's difficulty with the idea that evolution could possibly have produced the richness and sophistication of life we see on Earth. They focus on the "random" nature of mutation and reason that just changing things randomly can't possibly produce a brain, a butterfly, an oak tree or even a single-cell organism. And they're right. It's selection that does the heavy lifting. The random nature of mutation simply provides variation for selection — survival of the fittest — to winnow down. Most mutations are harmful, destroying useful features that have been built up, and most of those that aren't harmful, are neutral, neither improving nor harming the organism. It's the rare few that actually make something better, and it's the role of selection to favour those few. Even then, the process isn't automatic: an organism with an advantageous mutation, axiomatically has a better chance of surviving and reproducing than the same organism that doesn't (because that's how we define selective advantage). But that organism can be unlucky and die young or fail to reproduce. So selection too has a strong random element. However, even a small and probabilistic selective advantage is multiplied exponentially through the generations, with the consequence that improving mutations build up.

Some of the stochastic search methods we use at Stochastic Solutions are directly modelled on natural evolution — techniques such as genetic algorithms, evolution strategies and genetic programming. Others, like simulated annealing, take their inspiration from other natural stochastic processes, such as the way a metal cools.

Hybridization

Staff at Stochastic Solutions, have a long history of harnessing and exploiting the power of random variation and using it to solve challenging industrial and commercial problems. We do this by combining strong theoretical and technical knowledge of cutting-edge techniques with ruthlessly practical and pragmatic approaches to exploiting all other information and methods that can help to crack the problem in question. This leads us to favour hybrid approaches, whereby we try to incorporate existing search and optimization approaches into either evaluation functions or move operators. Because stochastic search methods, especially those based on evolutionary paradigms, provide excellent frameworks for this approach, this usually allows us to produce systems that out-perform both the existing approaches and a purer methodology based on a single stochastic search paradigm. We love theory, and admire purity, but in the end we do whatever it takes to get the job done.

Applications

Successful applications of this approach by staff at Stochastic Solutions have come in many industrial and commercial settings. One application was optimizing the design of gas pipelines to supply cities. Here, the goal was to minimize the cost of the pipeline while satisfying all engineering and safety constraints. Another was credit scoring, where we produced a hybrid solution that combined best-practice scorecarding with an evolutionary approach that produced a solution better than had previously been believed to be possible. We have also applied these methods successfully in fields as diverse as retail dealership location, oil production scheduling and computational process placement. More recently, we have harnessed the power of stochastic search to optimize the data-preparation phase that typically dominates the time spent in predictive modelling and data mining.

Whatever your requirement for optimization, search, covering, or constraint satisfaction, Stochastic Solutions will work with you to harness modern search methods to solve your problem.

Representation • Domain Knowledge • Move Operators

Our approach to search is informed by the insight that three features are dominant in determining the effectiveness of optimization methods. These are domain knowledge, problem representation and choice of move operators.

It all starts with domain knowledge, because without that stochastic methods are reduced to the very aimless wandering that is evolution's caricature. 1  So our first step is always to capture what is known about the problem from whatever sources of information are available. This can include interviewing domain experts, studying current and previous approaches, reviewing the literature and, where possible, directly probing or studying whatever system is being optimized.

The domain knowledge then has to be encapsulated in a way that makes it available in a useful form to the search algorithm. This is achieved through a combination of the choice of problem representation (logical, rather than physical, normally) and the move operators to be employed during the search.

Nicholas Radcliffe, who founded Stochastic Solutions, has worked for many years on the relationship between these three pivotal aspects of search, and has developed, through a series of publications, a solid theory of representation for stochastic search in general, and evolutionary algorithms more particularly, called forma analysis. This is an intensely practical theory that helps move from specific insights about a problem, through a systematic process that aids the production of suitable problem representations and move operators. These can then be used directly, or modified further, using heuristic insights, to produce a sound and effective approach to the problem at hand.

1 The careful reader may wonder where natural evolution's ``domain knowledge'' comes from. The difference here arises because our goal is to harness the power of evolution to to a particular end — usually, to optimize a function. In natural evolution, the goal is implicit: it is survival through the generations. It is in bending evolution to our own ends that the requirement for domain knowledge surfaces. ↩