Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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
Test 14(2020)
Print All Paths In Matrix
Median of row wise sorted matrix
poker.hpp
Eratosfen conmment
ForwardListString
xyz
MatrixVectorConversion
Shorting in one line using class members std and boost bind
PreDir