GAWorkbench a general purpose modular genetic algorithm class

Inherits from: Object

This is a general purpose modular genetic algorithm class for SuperCollider. Genetic algorithm is a search technique used for finding approximate solutions to search and optimization problems. They use techniques derived from evolutionary biology like inheritance, mutation, (artificial) selection and crossover.

For more info on the subject see:

http://en.wikipedia.org/wiki/Genetic_algorithm

GAWorkbench is a general purpose class that provides an easy interface to interact with your data to be used with GA's. It can be used for solving general computational search problems and can also be used for exploring sound spaces, finding suitable parameters for synthesis networks etc.

Creation / Class Methods

*new (argPoolSize, argRandomChromosomeFunc, argFitnessFunc, argMutationFunc)

argPoolSize - Number of items in the gene pool. Should be tuned for each problem. Default: 100

argRandomChromosomeFunc - A Function. This function should return a randomly generated

chromosome formatted in your chosen way of  encoding for the problem.

argFitnessFunc - A Function. Each member defined by the chromosomes in your gene pool

will pass through this function in each GA iteration, and this function will be passed in the chromosome as an argument. You should rate the fitness of the member with this function and return the fitness value.

argMutationFunc - When a chromosome will be mutated, it will be sent into this func, you should

grab it as an argument, mutate it in the way you want it and return the mutated chromosome.

Accessing Instance and Class Variables

randomChromosomeFunc_(arg1)

randomChromosomeFunc

fitnessFunc_(arg1)

fitnessFunc

mutationFunc_(arg1)

mutationFunc

The functions provided at initialization can be changed and accessed with these at any time. This for example, allows implementation of increasingly demanding fitness functions.

mutationProb_(arg1)

mutationProb

The mutation probability, should be between 0 and 1. Default: 0.08

coProb_(arg1)

coProb

Crossover probability. The default crossover operator uses a multi-point crossover method where the number of split points is determined proportionally to the crossover probability. The user can provide his/her own crossover function by setting externalCrossover member variable to true and provide a userCrossover function.

externalCrossover_(arg1)

externalCrossover

The crossover functionality provided with this class is simple. If you need to craft and use

a custom crossover function, you should set arg1 to true (boolean) and provide a

userCrossover function as an instance variable.

The external crossover function will be passed in this arguments:

genePool: The whole gene pool as an Array.

mutationProb: Value of the mutation probability for the instance.

You should grab those arguments in your custom crossover function, and return the

new genePool from your function. Default value is false.

userCrossover_(arg1)

userCrossover

Custom crossover function to be supplied by the user. See the help for externalCrossover

variable. Default is nil.

genePool

The whole gene pool as a List ordered from fittest (with higher fitness score) to weakest.

fitnessScores

The fitness scores for the items in the gene pool in the same order. So the fitness rating of the chromosome in genepool[10] would be fitnessScores[10].

Doing Some Task (optional)

rateFitness

Rates the fitness of the genePool and sorts the chromosomes inside genePool from the

highest fitness to lowest (used inside the crossover -> rateFitness GA loop).

crossover

Applies the crossover function to the members of the genePool (used inside the crossover -> rateFitness GA loop). The selection and mutation also happens at this stage. The default selection scheme is tournament selection, you can override these by providing your own crossove function (see userCrossover).

injectFitness (argFitness)

If you want to calculate the fitness values for the members of the genePool outside the instance,

and supply them by your own, you should use this method. argFitness is an array, which contains 

the fitness scores of the members in the genePool. The members of the genePool is ordered automatically, according to their fitness scores (as it is with the rateFitness method) automatically inside this method.

You might want to execute your fitness function outside a GAWorkbench instance to implement interactive GA applications. When you get the fitness ratings from the user, you may just inject the values with this method and GAWorkbench takes care of the ordering of the members.

Examples

A simple example: We want to reach to a target value (4242) with a mathematical expression composed of

17 operators and digits. So the expression is composed in [digit operator digit operator ...] formation. We are 

searching for the expression. poolSize is 100, and we will find the fittest expression after 100 generations.

(

//this will take a few seconds to complete.

var digits = "0123456789"; //allowed digits

var operators = "+-*/%"; //allowed operators

var poolSize = 100, chromLength = 17;

var target = 4242;

var numGenerations = 100;

var inGeneration = 0; //current generation

var randChromFunc =

{

var randChrom = List.new;

chromLength.do

({|cnt|

if(cnt.even,

{

randChrom.add(digits.choose);

},

{

randChrom.add(operators.choose);

});

});

randChrom;

};

var fitnessFunc = 

{|chrom|

var result;

chrom = chrom.as(String);

//if the result is inf (divide by zero etc), bigger numbers are

//weaker (we return the reciprocal) here so they won't be fit. 

//We set NaN's as inf.

result = (chrom.interpret - target).abs; 

if(result.isNaN, { result = inf; });

result.reciprocal; //smaller results (difference from target) should be fitter

};

var mutationFunc =

{|chrom|

var index = chromLength.rand;

if(index.even, { chrom[index] = digits.choose; }, { chrom[index] = operators.choose; });

chrom;

};

var gaInstance = GAWorkbench(poolSize, randChromFunc, fitnessFunc, mutationFunc);

gaInstance.mutationProb = 0.1;

block

({|break|

numGenerations.do

({

gaInstance.rateFitness;

//if an exact solution is found, break the loop.

if(gaInstance.genePool[0].as(String).interpret == target, { break.value; });

gaInstance.crossover;

inGeneration = inGeneration + 1;

});

});

gaInstance.rateFitness;

"Target value was % and reached value after % generations is: %"

.format(target, inGeneration, gaInstance.genePool[0].as(String).interpret).postln;

("The operation was:" + gaInstance.genePool[0].as(String)).postln;

)

It can be observed that the algorithm sometimes converges to an exact solution pretty quickly, and other times 

it gets stuck in a local optimum. To overcome that, one can use parallel GA's where more than one

GAWorkbench instance works on the same problem with different initial random pools for a few generations,

and then their fittest members can be mixed into a new pool to be iterated further.

Another example:

Travelling salesman problem. We have 25 cities to visit, we start from the red city and want to visit each city

only and only once, then come back to our origin in the shortest path possible. With a brute-force approach, 

one needs to check 15511210043330985984000000 different paths to find the shortest route (for 25 cities),

(which is not feasible) so genetic algorithms provides us an easy search method for finding a nice 

enough path in very little time. This code will show the fittest route in each generation for randomly selected 

points in a 2d space. Be aware that there is no way to find out that a given solution is the global optimum. In 

fact, the method used here converges to a local optimum pretty quickly but hopefully the route will converge to 

something with an high fitness. The chromosome encoding scheme here is left as an exercise for the reader. :)

(

var numPoints, points, randChromFunc, mutationFunc, fitnessFunc, 

chromInterpreter, gaInstance, win, view, drawPaths, routine;

//problem

numPoints = 25;

points = { 500.0.rand@500.0.rand } ! numPoints;

//ga funcs

randChromFunc = 

{ 

(numPoints - 1, (numPoints - 2) .. 1).collect

({|cnt| 

(exprand(1, cnt) - 1).floor;

});

};

mutationFunc = 

{|chrom| 

var randIndex = (chrom.size - 1).rand;

chrom[randIndex] = (exprand(1, (numPoints - randIndex - 2)) - 1).floor;

chrom;

};

fitnessFunc =

{|chrom|

var pathIndexes = chromInterpreter.value(chrom);

var totalDistance = 0;

(numPoints).do

({|cnt|

totalDistance = totalDistance + points[pathIndexes[cnt]].dist(points[pathIndexes[(cnt+1) % numPoints]]);

});

totalDistance.reciprocal; //shorter paths are better

};

chromInterpreter = //this chunk of code is shared between fitness function and visualization

{|chrom|

var ptsToGo = (1, 2 .. numPoints - 1);

var travellerIsIn = 0;

var currentDistances, curDistOrders;

var pathIndexes = List.new;

(numPoints - 1).do

({|inHop|

currentDistances = 

ptsToGo.collect

({|pntIndex|

points[travellerIsIn].dist(points[pntIndex]);

});

curDistOrders = currentDistances.order.order;

pathIndexes.add(ptsToGo[curDistOrders.detectIndex({|item| item == chrom[inHop]; })]);

ptsToGo.remove(pathIndexes.last);

travellerIsIn = pathIndexes.last;

});

pathIndexes.add(0);

pathIndexes;

};

gaInstance = GAWorkbench.new(100, randChromFunc, fitnessFunc, mutationFunc);

gaInstance.mutationProb = 0.2;

win = Window.new("TSP", Rect(300, 300, 500, 500));

view = UserView(win, win.view.bounds).background_(Color.black)

.drawFunc_

({

var fittest = gaInstance.genePool[0];

points.do

({|pnt, cnt|

Pen.color = if(cnt == 0, { Color.red; }, { Color.white; });

Pen.fillOval(Rect(pnt.x - 4, pnt.y - 4, 8, 8));

});

drawPaths.value(fittest);

});

drawPaths =

{|chrom|

var pathIndexes = chromInterpreter.value(chrom);

(numPoints).do

({|cnt|

Pen.line(points[pathIndexes[cnt]], points[pathIndexes[(cnt+1) % numPoints]]);

});

Pen.stroke;

};

win.front;

win.onClose_({ routine.stop; });

routine = {

inf.do

({

gaInstance.crossover;

gaInstance.rateFitness;

win.refresh;

0.1.wait;

});

}.fork(AppClock);

)