Genetic Algorithm

Trilobyte

Alright. So I've been attempting to create a genetic algorithm to make a ball learn to find a goal. In order to calculate fitness, I made a vector between the ball and the goal, and measured the magnitude. I have tried to store the values of this changing magnitude in an array to find the maximum fitness later. However, I cannot seem to just add values to the array without either just changing the value of the one data point in the array or creating new arrays with the added value. Any suggestions? Similarly, how do you think I can make "chromosomes" and create new, modified versions of the object in the object array?

Trilobyte

Ball[] balls;

float [] val;

int pop = 1;
int current = 0;

float diameter = 60;
float xac = random(-5, 5);
float yac = random(-5, 5);

int counter = 0;
FloatList values;
float v;

void setup() {
  size(800, 800);
  balls = new Ball[pop];
  for (int i = 0; i< balls.length; i++) {
    balls[i] = new Ball();
    values = new FloatList();
  }
  //frameRate(4);
}

void draw() {
  background(255);


  for (int i = 0; i< balls.length; i++) { 
    balls[i].update();
    balls[i].edges();
    balls[i].fitness();
    balls[i].display();


    rectMode(CENTER);
    rect(width/2, 0, 40, 20);

    counter ++;
    text("time: " + counter, width/2, height- 50);
  }
}


class Ball {
  PVector position;
  PVector velocity;
  PVector acceleration;
  PVector dist;

  Ball() {
    position = new PVector(random(0, width), random(0, height));
    //position = new PVector(width/2, height/2);
    velocity = new PVector(xac, yac);
    acceleration = new PVector (xac, yac);
  }

  void update() {

    position.add(velocity);
    velocity.limit(5);
    line(position.x, position.y, width/2, 0);
    float x = position.x-width/2;
    float y = 0 -position.y;
    dist = new PVector(x, y);
    float m = dist.mag();
    //println(1/m);
  }

  void edges() {

    if ((position.x > width) || (position.x < 0)) {
      velocity.x = velocity.x * -1;
    }
    if ((position.y > height) || (position.y < 0)) {
      velocity.y = velocity.y * -1;
    }
  }


  public void fitness() {

    float m = dist.mag();
    //float n = max(m);
    for (int i = 0; i< balls.length; i++) {
      text("Ball "  + (i+1), 10, 0+ 20*i+20 );
      text(" fit of " + (m/894.427), 40, 0+ 20*i+20 );
    }



    //float [] val = new float[1];
    //text("arraylength: " +val.length, width/2, height-10);



    //append(val, m);
    //printArray(val);




    values.append(m); 



    printArray(values);

    text("size" + values.size(), width/2, height/2);
  }

  void display() {
    stroke(0);
    fill(175);
    ellipse(position.x, position.y, diameter, diameter);
  }
}

GoToLoop

https://forum.Processing.org/two/discussion/17524/why-can-t-i-append-a-new-vector-to-an-array-of-vectors

TfGuy44

blows off a lot of dust

ArrayList<Car> cars = new ArrayList();

float goalX, goalY;

int timeStep = 200;

Car gbCar = new Car( -1, "0" );
float gbScore;

String[] str_a;
String[] str_b;
float[] scores;
final int gen_size = 5;
int cur_sub;
int countGen = 0;

void setup() {
  size(600, 400);
  background(0);
  gbScore = dist(0, 0, width, height);
  goalX = random(width);
  goalY = random(height);
  smooth();
  ellipseMode(CENTER);
  str_a = new String[gen_size];
  str_b = new String[gen_size];
  scores = new float[gen_size];
  for ( int j = 0; j < gen_size; j++ ) {
    str_a[j] = starterString();
    scores[j] = 0;
  }
  cur_sub = -1;
  countDoneCars = 0;
  for ( int i=0; i < gen_size; i++ ) cars.add( new Car( i, str_a[i] ) );
}

String starterString() {
  String mut = "" + char( '0' + int( random(4) ) ); //  + "00000000" ;
  return( mut );
  // Ok, a bit more random would be nice.
  // I suppose that's ok.
}

int countDoneCars;

String hr( String cr ) {
  String r = "";
  for ( int t = 0; t < cr.length(); t++) {
    if ( cr.charAt(t) == '0' ) r+= 'N';
    if ( cr.charAt(t) == '1' ) r+= 'L';
    if ( cr.charAt(t) == '2' ) r+= 'R';
    if ( cr.charAt(t) == '3' ) r+= 'A';
  }
  return( r );
}

void draw() {
  background(0);
  fill(255,0,0);
  String extra = "";
  //if( gbScore < 10 ) extra = "      That's close enough! Click the mouse to move the goal. :-)";
  text("Best ever: (" + hr(gbCar.genome) + ") = " + int(gbScore) + extra, 10, 20 );
  fill(255,255,0);
  text("Generation " + countGen , 10, 34 );
  for( int tt=0; tt< gen_size; tt++){
    fill(cars.get(tt).k);
    text( "(" + hr( cars.get(tt).genome ) + ")", 10, 48 + 14 * tt);
  }

  // If no car, last car is done, simulate next one.
  // If all cars done, simulate next generation.
  if ( countDoneCars == gen_size ) { // cars.size() == 0 ) {
    while ( cars.size () > 0 ) cars.remove(0); 
    //cur_sub++;
    // If all cars in this generation simulated, create next generation.
    //if ( cur_sub == gen_size ) {
    countDoneCars = 0; // cur_sub = 0;
    //println( "Making next generation..." );

    // Always keep the best one, and toss the worse.
    arrayCopy( str_a, str_b );
    int bestIndex = 0;
    int worstIndex = 0;
    for ( int j = 0; j < gen_size; j++ ) {
      if ( scores[bestIndex] > scores[j] ) {
        bestIndex = j;
      }
      if ( scores[worstIndex] < scores[j] ) {
        worstIndex = j;
      }
    }  
    str_b[worstIndex] = str_b[bestIndex]; // Replace the worst with a copy of the best for breeding.
    // Scramble.
    for ( int j = 0; j < gen_size; j++ ) {
      str_a[j] = scramble( j, str_b[int(random(gen_size))], str_b[int(random(gen_size))] );
    }
    //str_a[0] = str_b[bestIndex]; // Always keep the best.
    // Add all the cars to simulate.
    for ( int j = 0; j < gen_size; j++ ) {
      cars.add( new Car( j, str_a[j] ) );
    }
    countGen++;
    //}
    //cars.add( new Car( cur_sub, str_a[cur_sub] ) );
  }
  // Draw the global best car ever.
  gbCar.render(); // It don't move, yo.  
  // Simulate the current subject.
  for ( int i=0; i < cars.size(); i++ ) cars.get(i).go(); // It go.
  // Draw the cheese.
  stroke(255);
  fill(random(255));
  ellipse(goalX, goalY, 10, 10);
}

String scramble( int which, String a, String b ) {
  String r;
  int pos = int(random(min(a.length(), b.length())));
  r = a.substring(0, pos) + b.substring(pos, b.length());

  // Mutation!
  if ( random(1) < .5 ) {
    pos = int(random(r.length()));
    if ( random(1) < .5 ) { 
      String mut = "" + char( '0' + int( random(4) ) );
      //println( "New Car #" + which + ": Mutation! Adding a char: '" + mut + "' at position " + pos );
      r = r.substring(0, pos) + mut + r.substring(pos, r.length());
    } 
    else {
      if ( r.length() > 0 ) {
        pos = int(random(r.length()-1));
        //println( "New Car #" + which + ": Mutation! Losing the char at position " + pos );
        r = r.substring(0, pos) + r.substring(pos+1, r.length());
      }
    }
  }
  return( r );
}


void mousePressed() {
  goalX = random(width);
  goalY = random(height);
  gbScore = dist(0, 0, width, height);
  countGen=0;
  //println( "GLOBAL BEST: (" + gbCar.genome + ") = " + gbScore );
}

class Car {
  float x, y, z, v;
  color k;
  boolean a, b, c;
  int ins; // Current instruction.
  int time; // Time of next instruction.
  int[] instructions;// = { 3, 1, 1, 3, 1, 2, 2, 2 };
  boolean disable;
  int myNumber;
  String genome;
  Car( int oo, String input ) {
    x=20; //width/2;
    y=height/2;
    if ( oo == -1 ) { 
      x = -20; 
      y = -20;
    }
    z=0;//random(TWO_PI);
    v=0;//random(10);
    k=color(0, random(128, 255), random(128, 255));
    a=b=c=false;
    // Added for running a set program.
    myNumber = oo;
    ins = 0;
    parseString( input );
    time = millis() + timeStep;
    disable = false;
    genome = input;
  }
  void parseString( String in ) {
    instructions = new int[in.length()];
    for ( int j = 0; j < in.length(); j++ ) {
      instructions[j] = int( in.charAt(j) - '0' );
    }
  }
  void report() {
    scores[myNumber] = dist( x, y, goalX, goalY ) + genome.length(); // Experimental score formula - adds a small penalty for long strings.
    //println( "Car #" + myNumber + " (" + genome + ") stopped at " + int( x ) + ", " + int( y ) + ". Score: " + scores[myNumber] );
    if ( scores[myNumber] < gbScore ) {
      gbScore = scores[myNumber];
      gbCar.x = x;
      gbCar.y = y;
      gbCar.z = z;
      gbCar.k = k;
      gbCar.genome = genome;
    }
    countDoneCars++;
    // I know it's mean, but move the cheese if one gets way close...
    //    if ( scores[myNumber] < 10 ) {
    //      goalX = random(width);
    //      goalY = random(height);
    //      //println( " SOMEONE GOT THE CHEESE!!!" );
    //    }
    //cars.remove(0);
  }
  void go() {   
    if ( millis() > time && !disable) {
      time = millis() + timeStep;
      if ( ins < instructions.length ) {
        int i = instructions[ins++];
        switch( i ) {
        case 0:
          // Do nothing.
          break;
        case 1:
          a = !a;
          break;
        case 2:
          b = !b;
          break;
        case 3:
          c = !c;
          break;
        default:
          //println( "Bum instruction: " + i );
          break;
        }
      } 
      else { // Terminate run.
        a=b=c=false;
        v=0;
        disable = true;
        report();
      }
    }
    // Car movement systems follow.
    z+=(a?-.1:0)+(b?.1:0);
    v+=(c?.1:0);
    //x=(x+width+v*cos(z))%width;
    //y=(y+height+v*sin(z))%height;
    x=x+v*cos(z);
    y=y+v*sin(z);
    v*=.99;
    render();
  }
  void render() {
    pushMatrix();
    translate(x, y);
    rotate(z);
    noStroke();
    fill(k); 
    if ( myNumber==-1) fill(255, 0, 0);
    rect(-10, -10, 20, 20);
    stroke(0);
    noFill();
    triangle(-8, -8, 7, 0, -8, 8);
    popMatrix();
  }
}

koogs

Tons of irrelevant code there, posted without comment.

The first line is the important one, see ArrayList in the reference. ArrayList is like an array you can extend...

TfGuy44

It's not irrelevant! It's showing off chromosome-based movement!

koogs

that's the kind of comment that should've been posted alongside the code 8)

Trilobyte

Thanks all for the quick replies and helpful comments. What I have gathered from TfGuy44's comments and code is that I should perhaps use dist() instead of the magnitude of a vector to calculate the distance between the goal and the ball, and then use strings instead of arrays to store my values. Similarly, the code helped with my problems with genomes and such. Thanks a lot again and I will post more questions as I inevitably fail miserably.

Trilobyte

Just a few questions about your code, TfGuy44. In your program, how does the car move? Similarly, what characteristics are carried over between generations? Thanks and if you would like to clarify any other sections as well, that would be wonderful. @TfGuy44

TfGuy44

When I first wrote the Car class, I only had one instance of it, and it was controlled by the arrow keys. The LEFT arrow key would turn it to the left. The RIGHT arrow key would turn it to the right. the UP arrow key would give it some gas and make it accelerate forward in the direction it was pointing. You could also not press any key, and it would gradually slow down.

Essentially, then, there are four "actions" that make the car move differently: LEFT, RIGHT, ACCELERATE, and NOTHING. For short, let's call them L, R, A, and N.

When arrow-key-based control was removed, I switched the Cars over to having a genome-based movement. The "genes" a car possessed were a list of actions to take in the hopes that these actions would move the car closer to the goal. For example, (NNNAARNN) means "Do nothing for a bit, then accelerate some, and turn to the right, then coast for a while." This COULD get the car closer to the goal... if the goal was ahead of the car on the right. But maybe the goal was to the left of the car. In that case (LLA) might be a "better" gene sequence for a car to have.

From there, it was an easy jump to having a generation of cars. Each would have a gene sequence that mapped directly to how the car moved. Each car was then simulated, and the "best" gene sequence would be kept for the next generation. Then you throw in some breading (the first half of one car's sequence and the second half of anothers) and mutation (randomly removing, adding, or changing an action), and suddenly you have cars that get closer and closer to the goal.

Trilobyte

Thanks a lot. The code is very impressive. Do you mind if I base sections of my code off of yours if I credit you? Thanks.

TfGuy44

You can base your code off it, sure. I would use it as an example and write your own, new version of it, however, since it's sort of a mess...

Chrisir

http://natureofcode.com/book/chapter-9-the-evolution-of-code/

http://www.karlsims.com/papers/siggraph91.html