Dar, C++ (gcc) - rextester

Dar

#include <iostream>

void greeting();
//declaration for greeting function
void print(const char*s);
void print(double d);

const int GW = 10; //grid width
const int GL = 10; //grid length
const int GENES = 16; //number of genes per robot
const int GENELEN=5; //length of each gene
const int GN = 0; //empty grid cell
const int GB = 9; //battery grid cell
const int GDC = 5; //used in gene to match any cell
const int GWA = 1; //wall grid cell (out-of-bounds assumed to be a wall)
//array of view codes that can go in gene
const int VC[4]={GN,GB,GWA,GDC};
const int NVC=4;
//directions and the random direction
const int UP=1;
const int LEFT=2;
const int RIGHT=3;
const int DOWN=4;
const int RANDDIR=5;
const int NDC =5; //number of direction codes including the code for random direction
const int MOVECODES[5]={UP,LEFT,RIGHT,DOWN,RANDDIR};
const int NR=200; //number of robots in each generation
const double PERCBAT = 0.4; //proportion of batteries in grid
const int GENERATIONS = 6000;
const double MUTRATE=0.05;
const int INITEN=5; //initial energy of a robot

class Grid { 
  int g[GW][GL]; //g[x][y] is cell at (x,y)
//to place k batteries in empty cells, place 1 battery in an empty cell, then recursively place k-1 batteries
void randbat(int k){
  int x,y;
  if (k==0) return;
  //generate random (x,y) pairs until (x,y) is empty, then place a battery there
  do {
    x=rand()%GW; 
    y=rand()%GL;
  } while(g[x][y] != GN);
  g[x][y]=GB;
  randbat(k-1);
}
public:
  //random Grid with a percentage of cells occupied with batteries
Grid(double perc) {
  for (int y=0; y<GL; y++) 
    for (int x=0; x<GW;x++)
       g[x][y]=0;
  int k=(GW*GL)*perc;
  randbat(k);
}
//get code of cell at (x,y) so out-of-bounds is a wall
int getcode(int x, int y) {
  if ((x>=GW)||(x<0)||(y>=GL)||(y<0)) return GWA;
  else return g[x][y];
}
//get codes of cells north, west, east, and south of 
//(x,y) and pack into pre-allocated array of 4 ints
void getnwes(int x, int y, int* into) {
  into[0]=getcode(x,y-1);
  into[1]=getcode(x-1,y);
  into[2]=getcode(x+1,y);
  into[3]=getcode(x,y+1);
}

//creature munches at cell (x,y)
//deplete battery there accordingly if any
//return energy munched
  int munch(int x, int y) {
     if (g[x][y]==GB) {g[x][y]=GN; return 1;}
     else return 0;
  }
  //is cell (x,y) not a grid wall?
  int cango(int x, int y) {
    return (getcode(x,y)!=GWA);
  }
//end class
};

//robot
class Rb {
  int genes[GENES][GENELEN];
  int energy;
  int x,y;
  int movesmade;
  void randplace() {
    x=rand()%GW;
    y=rand()%GL;
  }
 void randgene(int* g) {
   //first 4 codes are one of nothing,wall,battery,or don't care
   for (int i=0;i<4;i++) {
     g[i]=VC[rand()%NVC];
   }
   //5th code is a (non-zero) direction code
   g[4]=MOVECODES[rand()%NDC];
}
public:
//construct a robot with a random set of genes ready to run
Rb() {
      for (int g=0;g<GENES;g++) {
         randgene(genes[g]);
      }
      randplace();
      movesmade=0;
      energy=INITEN;
}
//returns 0 if view does not match gene
//else returns the code at the end of the gene
int activategene(int*view,int*gene){
   for (int i=0;i<4;i++) {
      if (view[i]!=gene[i]&&gene[i]!=GDC) return 0;
   }
   return gene[GENELEN-1];
}
//return the last code from the first of this robot's 
//genes that matches view
//if no gene matches, return last gene's last code
int lookup(int* view) {
    int move;
    for (int i=0;i<GENELEN;i++) {
       move=activategene(view, genes[i]);
       if (move!=0) return move;
    }
    //if there are gene activations assume the last gene is activated
    return genes[GENES-1][GENELEN-1];
}
//gets the robot ready to run the grid again
void reset() {
    randplace();
    movesmade=0;
    energy=INITEN;
 }
//runs the robot to energy depletion
void go(Grid*gr) {
  for(;;) {
  if (energy<0) return;
  int view[4]; 
  int move;
  int x2, y2;
  gr->getnwes(x,y,view);
  move=lookup(view);
  //if move represents a random move then 
  //the move becomes a random move
  if (move==RANDDIR) {
     int ds[4]={UP,LEFT,RIGHT,DOWN};
     move=ds[rand()%4];
  }
  y2=y;x2=x;
  switch(move) {
     case(UP): y2--;break;
     case(LEFT): x2--; break;
     case(RIGHT): x2++; break;
     case(DOWN): y2++; break;
  }
  //if can go then go
  if (gr->cango(x2,y2)) {x=x2;y=y2;}
  //and always increment moves made
  movesmade++;
  //return energy
  energy+=gr->munch(x,y);
  energy--;
  }
}
//mutates gene number z
void mutate(int z) {
  //randomly select a code number
  int code=rand()%GENELEN;
  //initialize int* source to VC and an int l to its length
  const int* source=VC; //array to from which to choose a code
  int l=NVC;                      //length of array from which to choose a code
  //if the last code has been selected, change the source array and length values
  if (code==GENELEN-1) {
    source=MOVECODES;
    l=NDC;
  }
  //mutate code on gene z to a random selection from the source array
  genes[z][code]=source[rand()%l];
}

//print each gene as a space separated line of text
void printgenes() {
  for (int g=0; g<GENES;g++) {
    for (int i=0; i<GENELEN; i++) {
      print(genes[g][i]);
      print(" ");
    }
    print("\n");
  }
}
//return the harvest after a run
int harvest() {
  return movesmade-INITEN;
}
//return a copy of a Rb which has its first half genes from this and its second half genes from Rb pa
Rb mate(Rb pa) {
  Rb baby;
  int i=0;
  Rb *source=this;
  for (i=0;i<GENES;i++) {
    if(i>=GENES/2) source=&pa;
    for(int i2=0;i2<GENELEN;i2++) {
       baby.genes[i][i2]=source->genes[i][i2];
    }
  }
  return baby;
}
//end class
};

//Breeder has, runs generations of, and selectively breeds generations of robots, and analyzes, and prints data about them
class Breeder {
  Rb rs[NR]; //the generation of robots
  double avg[GENERATIONS]; //historic data for each generation
//returns a copy of a new Grid
Grid newgrid() {
  Grid g(PERCBAT);
  return g;
}
//runs and selectively breeds all the generations of robots, recording average harvest for each generation
void runrs() {
  for (int gennum=0; gennum<GENERATIONS; gennum++) {
  double tot=0.0;
  for (int i=0; i<NR; i++) {
     Grid g=newgrid();
     rs[i].reset();
     rs[i].go(&g);
     tot+=rs[i].harvest();
  }
  avg[gennum]=tot/(double)NR;
  sort();
  breed();
  } 
}
//sort the robots by harvest in non-ascending order
void sort() {
  Rb temp;
  for (int i=0;i<NR-1;i++) {
    for (int i2=i+1;i2<NR;i2++) {
       if (rs[i].harvest()<rs[i2].harvest()) {
         temp=rs[i];
         rs[i]=rs[i2];
         rs[i2]=temp;
      }
    }
  }
}
void breed() {
  //do the gene combining perfectly
  //for the first half of robots (assumed sorted)
  //mate the ith with the 1+ith, and put the offspring in 
  //the ith place of the second half
  //then mate the 1+ith with the ith and put the
  //offspring in the 1+ith place of the second half
  //then go on to the 2+ith robot and repeat
  for(int i=0;i<NR/2;i=i+2) {
    rs[i+NR/2]=rs[i].mate(rs[i+1]);
    rs[i+NR/2+1]=rs[i+1].mate(rs[i]);
  }
  //make some mutants
  int m[(int)(NR*MUTRATE*GENES)]; //array to be filled with individual gene numbers in the population where gene x*GENES+y represents the yth gene in the xth robot
  //mutate exactly the MUTRATE proportion of genes in the population
  for (int i=0; i<NR*MUTRATE*GENES;i++) {
    int in;
    //randomly select a gene number that has not already been selected
    do {
       in=0;
       m[i]=rand()%(NR*GENES);
       for(int i2=0;i2<i;i2++) if (m[i2]==m[i]) in=1;
     } while (in);
     //tell the corresponding robot to mutate its corresponding gene
     rs[i/GENES].mutate(i%GENES);
   }
}
public:
//upon construction runs all the generations and sorts the final generation
Breeder() {
  runrs();
  sort();
}
//for each generation, prints the average harvest
void printout() {
  //Specification A1 - Output Headers
  for (int i=0;i<GENERATIONS;i++) {
    //Specification A2 - Display variables
    print(i+1);
    print("\t");
    print(avg[i]);
    print("\n");
  }
}
//bonus feature - prints the genes and harvest of the top robot 
void printwinner() {
  rs[0].printgenes();
  print(rs[0].harvest());
  print("\n");
}
};

int main()
{  
    srand(time(NULL));
    greeting();
    //set up a breeding ground. It automatically runs the generations
    Breeder b;
    //print the data
    b.printout();
    //do the bonus feature
    std::cout<<"Bonus feature - genes followed by harvest of top robot in the final generation"<<std::endl;
    b.printwinner();
    return 0;
}

void greeting() {
    //Program Greeting
   print("Greetings! Welcome to genetic algorithm robots.\n");
}
void print(const char*s){
  std::cout<<s;
}
void print(double d) {
  std::cout<<d;
}


run \| edit \| history \| help	0

Please log in to post a comment.