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; //Specification C1 - Program Output 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
CODE K
completeBubbleSort
RegExpress
PRIx64 on gcc
string match2
String match with test
cache_node.cc
shivratri
Problem D
CPP - Arrays - Ex.2 - Solution