Differential Evolution for Finding Predictive Gene Subsets

Differential Evolution – Global, Evolution Strategy Based Optimization Method

This chapter introduces another evolutionary method – differential evolution – for predictive gene selection. The choice was dictated by the fact that differential evolution is one of the newest members in the family of evolutionary optimization methods.

Differential evolution is akin to the evolutionary algorithms in (Jirapech-Umpai & Aitken, 2005), (Deutsch, 2003). It is the tool for global optimization.

You can naturally suspect that finding a globally optimal solution can be much harder than getting a locally optimal solution. In many cases, the exact solution of the global optimization problem is impossible to find. In the context of combinatorial problems, such problems are called NP-hard, where the frightening ‘NP-hard’ stands for non-deterministic polynomial-time hard¹. By providing this meaning and halting here, let me avoid of venturing further into the broad and misterious realm of computational complexity theory.

For those of you who would like to know more about global optimization, I can recommend the book of Zhigljavsky and Žilinskas (Zhigljavsky & Žilinskas, 2008).

The history and, what is more important, the development of differential evolution is well presented in (Feoktistov, 2006)². I will rely on this book when explaining the basic differential evolution algorithm, despite the fact that it was invented by Kenneth Price and Rainer Storn (Price & Storn, 1997), (Storn & Price, 1997). As another view of differential evolution, the book of these authors (Price, Storn, & Lampinen, 2005) is highly recommended in addition to (Feoktistov, 2006). I preferred the book of Feoktistov, because it is thin (yes, yes, I must confess that like many of you I like thin books) and contains MATLAB® and C code that turned to be extremely useful in understanding differential evolution. I, of course, do not want to say that the inventors of differential evolution left people starving: on the contrary, the inventors turned out to be polyglots as can be found at the following web page: http://www.icsi.berkeley.edu/~storn/code.html. This web page hosts code in C, Java, MATLAB, C++, Python, R and some other programming languages. In addition, there is an advice (under ‘Practical Advice’ title) on how to choose values for the parameters of differential evolution. Such guidance is invaluable as we all are aware of headache caused by tedious parameter tuning.