Questions or comments should be sent to annevolve-devel@lists.sourceforge.net.
Metavolv is a free download from the ANNEvolve website: http://annevolve.sourceforge.net.

Contents:
1. What is it?
2. What's Required to Use it?
3. How to Use it
4. How Does it Work?
5. Output and Discussion

1. What it is:

Metavolv.py is a computer program that searches for a better set of parameters for some other program, which we call the target program.  The target program determines what "better" means, and it writes a merit value to the screen. The parameters appear in a configuration file for the target program. Although metavolv.py is written in Python, the target program can be any executable file that meets two conditions: It must read a configuration file to get values for parameters, and it must eventually write a result to the screen. Metavolv will repeatedly execute the target program, each time re-writing the configuration file with new parameter values. Metavolv.py will use two other Python files, modify.py and editThis.py.  The three files together comprise the program. Metavolv is primarily designed for stochastic target programs, and also for those that require significant execution time.   For such programs we cannot be sure of finding a global optimum in a reasonable time span; we are primarily interested in improving the set of parameters that we start with.  Hence we are primarily attempting to move toward a local optimum.

2. What's Required to Use it:



3. How to Use it:

Once editThis.py is suited to the target, and the target is ready to run, metavolv.py is executed from a command line window.  The command is simply metavolv.py followed by the desired number of trials.  For example "metavolv.py 100".  That can optionally be followed by a filename containing the initial parameter set.  Normally the parameter set is taken from the initializer in editThis.py, but if the name of a file containing the parameter values is given, then those values will be used.   This file should have all of the parameter names and values, and in the same order that they appear in the initializer.  (This is most commonly used with result.ini, which is created by metavolv during each run.  It contains the best parameter set found.)

4. How it Works:

(A pseudocode representation is below.)  The general idea is that metavolv.py writes a new version of the configuration file each time it executes the target program.   Metavolv receives all of the output that the target sends to the screen. From that output it finds the fitness value that the target produced.  (The target program outputs a fitness value or merit factor at the end of execution).  Then the parameters are changed, and the above steps are repeated.   The best fitness found is always kept, as well as the parameter set that produced it. Of course, the devil is in the details, and there are a lot more details here.  The most important have to do with how the parameter set is modified.  Initially, we take random jumps in parameter space. We save all of this data, both the parameter values and the resulting fitness. After we have enough points, then a linear function of all of the parameters is fitted to these points by the method of least squares.  (This is accomplished using the linalg.lstsq() function of NumPy.)  We treat this linear function as if it were a good approximation to the actual, unknown, function relating fitness to the parameters.  For a linear function we know which direction to move in order to raise the fitness.  That's the direction of the gradient vector, and we know what that is. So we take a step in that direction.  However, this step is not guaranteed to increase the fitness, for two reasons. 1) the linear function is only a rough approximation of the actual function, and 2) our function may be stochastic, so that there is great random variation in results returned by the target program.  (Programs involving simulated evolution are almost always stochastic.)

There are more details:  There is a variable, sigma, which is related to the step size.   When taking random steps it is the standard deviation of the random amount added to a parameter.  When taking a projected step using the linear fit, it is the Euclidean norm of the N dimensional step.  We would like to take large steps to rapidly find our maximum, but if the step is too large it is guaranteed to take us farther from the maximum.  Hence there is a best step size.  Furthermore, The best step size depends on how far we are from the maximum point; smaller steps are necessary as one approaches the maximum. Therefore we have incorporated a method of automatically adjusting sigma.  Whenever we take a projected step in the gradient direction, we also take another step with sigma 50% greater.  Hence we execute the target twice.  We keep only the result with the higher fitness, and discard the other.  However, if one result was significantly higher than the other, then we change the step size.  If the shorter step was better we reduce sigma.  If the longer step was better we increase it.

Another important detail is the transformation of the parameters so that they all have similar behavior.  The original parameter set often has parameters that are very different.  For example, one parameter may be probability, and must stay between zero and one.  Another parameter may be a population size that can vary from 20 to 2000.  Clearly, an appropriate step size cannot be defined that suits both of those parameters.   Hence, we permit the user to define as many custom transformations as are required by his active parameter set.   However, in most cases some or all of the transformations that are in modify.py may be used.

To specify that a particular transformation function is to be used by a particular parameter, put its name into the appropriate line of the initializer in editThis.py.   Note that these transformation functions must include the inverse transformation.  For example, the function floatXform() uses the natural log function to transform a parameter. For the inverse transformation it uses the exponential function.  If you add any new function names, they must be included in the line that begins "from modify import ....." in metavolv.py.

The goal of each transformation function is to cause the corresponding active parameter value to vary across a good portion of the range -10 to +10.  In many cases all that is required is the log() function, with exp() for its inverse.  However, if the value of the parameter must be limited, then the transformation function must also enforce the limits. There are two examples of that in modify.py, namely probXform() and declineXform().  Finally, the active parameter set must consist only of floating point numbers.  If some of the original parameters are integers, the transformation function must translate.  An example of this is intXform(), in modify.py.  

If no transformation is needed, then use the null transformation function, noXform().  This is done when hill.c is the target program, so you can see it used in editThis.hill.   noXform() can be used with any parameter and any target, but the search results may not be as good, depending on the behavior of the parameters.   Also, some of the parameters may reach unreasonable values; the effect of that depends on the target program.

It is the transformed parameters that are used for the search.  The initial parameter set is transformed after it is read in from the initializer.  It is de-transformed in order to re-write the configuration file, or to display it.

pseudocode explanation of how it works:

write new .ini file for target program
(this includes initial vector of parameters)
set bestFitness to very unfit value
set currentParams to transformed values from the .ini
loop forever:
    invoke target program
    capture its output scanning for termination
    when termination occurs:
        scan for the fitness
        if fitness > bestFitness:
            bestFitness <- fitness
            bestParams <- currentParams
        else:
            restore params to best    
    store the fitness value
    store the xformed param set that produced it        
    make some changes to currentParams
        (these may be based on linear projection, or may be random)
    de-transform them and write new .ini file


5. Output and Discussion:

Definitions:

parameter - A number whose value you would like to determine.  A variable with a numerical value.  (For use with metavolv.py it must appear in a configuration file for the target program.)

active parameters - the parameters whose values will be varied during the search.  The configuration file will usually contain other parameters also.  The flag field in the initializer determines which parameters are active.

parameter space - The set of all possible values of all active parameters.  If there are N active parameters then this is an N-dimensional space.

target - (or target program) An executable file which can be invoked by metavolv.py.  (It will be invoked over and over again.)  The target program can be any executable file that meets three conditions: It must be executable from a command line window, it must read a configuration file to get values for parameters, and it must eventually write a merit value to the screen via stdout.

configuration file - A text file containing names and values of parameters. The target program will read it when it begins execution and use the values found there.

4Play - A neuroevolution software package which is a free download from http://annevolve.sourceforge.net

EvSail - A neuroevolution software package which is a free download from http://annevolve.sourceforge.net

merit value or merit factor or fitness - A number that estimates how good the parameter set is; larger meaning better. This is usually a random variable, so a given parameter set will produce different merit values each time it is used.

stochastic - containing random influences

initializer - a list structure at the beginning of editThis.py.  Each item of the list consists of a name, value, flag, and function name.  This mirrors the configuration file of the target program, but with the flag & function fields added.

trial - a single determination of the merit value.  Metavolv obtains this by running the target program once or twice.

linear function - f(x, y, z, ....) = k + a*x + b*y + c*z + .........  In this case f is the fitness, x, y, z.... are the parameters of the target program, and a, b, c .... are the estimated components of the gradient vector.

gradient vector - for a function of several variables, a vector that points in the direction of greatest rate of change of the independent variable.  This is at a particular point in the space of the dependent variables.

method of least squares - minimize the sum of the squares of the errors.  The errors are the differences between a set of given values and corresponding estimated values.

transformation - putting a variable through a function that changes its characteristics.  For example, if x is replaced by z = x squared, then z will never be negative, like x could be, and z will vary very slowly when near 0, and very rapidly when far from zero.

step - distance between successive trial points in parameter space.  In two or three dimensions this is the familiar quantity, distance.  In higher dimensions it is the analogous quantity, the Euclidean norm.