Genetic Algorithm Example

Overview


This example uses a genetic algorithm to approximate a function. The value of the function is known at a handful of points. For example, we are given

  • {% f(0)=5 %}
  • {% f(1) = 6 %}
  • {% f(2) = 9 %}

This information gets encoded as pairs of values in an array. 

let data = [
	[0,5],[1,6],[2,9],[3,14]
];

Representing a Function


For this example, we will represent a function as an Abstract Syntax Tree.

Here is an example of how the function add is represented. 

let function1 = {
  function:function(x,y){
    return x+y;
  },
  name:'add',
  arguments:[1,2]
}


Note that in this example, the arguments are just listed as numbers, but they could be other functions.

For example, the following represents the function
{% 1 + e^{2} %} 

let function1 = {
  function:function(x,y){
    return x+y;
  },
  arguments:[
    1,
    {
      function:function(x){
        return Math.exp(x)
      },
      arguments:[2]
    }
  ]
}

Steps


The genetic algorithm engages the following steps.



Full Example


The following represents the full example detailed above. The two libraries contain the funcitons used. 




let gn = await import('/lib/ast/v1.0.0/genetic.mjs');
let st = await import('/lib/sort/v1.0.0/sort.mjs');
let ast = await import('/lib/ast/v1.0.0/ast.mjs');

let data = [
    [0,5],[1,6],[2,9],[3,14]
];
    
let list = gn.newIndividuals(12);
let top;

for(let i=0;i<10;i++){
  top = gn.top(data, list, 12, gn.error.abs);
  let results = gn.reproduce(top);
  results = results.map(p=>gn.mutate(p));
  list = [...top,...results];
  list = [...list, ...gn.newIndividuals(6,list)];  
}

let error = function(item){
  let sum = 0;
  for(let point of data){
    let result = [point[1], ast.evaluate(item, point[0])];
    let error = Math.abs(result[1]- result[0]);
    sum += error;
  }
  return sum;
}

let minerror;
top = st.sort(top, item=>{
  return error(item);
});
Try it

Contents