/* Darwin Program */ #include <stdio.h> #include <stdlib.h> /* Data Type Definitions */ typedef struct { int x; int y; int width; int height; } TRectangle; typedef struct { TRectangle rectangles[20]; void *population; } TRectangles; typedef struct { TRectangles individuals[100]; int size; float fitscores[100]; void *algorithm; float crossrate; float mutationrate; float avgfitness; float minfitness; float maxfitness; } Pop; typedef struct { Pop population; int generation; float convergence; } GA; /* Function Prototypes */ void TRectangleCrossover(TRectangle parent[], int pcount, TRectangle child[], int *ccount) ; void TRectangleMutator(TRectangle *gene); void TRectanglePrinter(TRectangle *gene); void TRectanglesInitializer(TRectangles *chrom, void *pop); int TRectanglesEvaluator(TRectangles *chrom); void TRectanglesCrossover(TRectangles parent[], int pcount, TRectangles child[], int *ccount); void TRectanglesMutator(TRectangles *chrom); void TRectanglesPrinter(TRectangles *chrom); void PopInitializer(Pop *pop, void *alg); void PopEvaluator(Pop *pop); int PopSelector(Pop *pop); void PopReproducer(Pop *pop, Pop *newpop); void PopMutator(Pop *pop); void PopPrinter(Pop *pop); void GAInitializer(GA *alg); int GATerminator(GA *alg); void GAReplacement(GA *alg, Pop *newpop); void GAEvolver(); void GAPrinter(GA *alg); void RectangleInit(TRectangle *gene); float RectangleEval(TRectangle *gene); /* Gene Moderator Functions */ void TRectangleCrossover(TRectangle parent[], int pcount, TRectangle child[], int *ccount) { int crossmember; int crosspoint; crossmember = randomint(1, 2); switch (crossmember) { case 1 : { crosspoint = randomint(1, sizeof(int)) + sizeof(int); RawCopy(child[0], parent[0], 0, crosspoint - 1); RawCopy(child[0], parent[1], crosspoint, sizeof(TRectangle)); RawCopy(child[1], parent[0], 0, crosspoint - 1); RawCopy(child[1], parent[1], crosspoint, sizeof(TRectangle)); break; } case 2 : { crosspoint = randomint(1, sizeof(int)) + (sizeof(int) + sizeof(int)); RawCopy(child[0], parent[0], 0, crosspoint - 1); RawCopy(child[0], parent[1], crosspoint, sizeof(TRectangle)); RawCopy(child[1], parent[0], 0, crosspoint - 1); RawCopy(child[1], parent[1], crosspoint, sizeof(TRectangle)); break; } }; }; void TRectangleMutator(TRectangle *gene) { int selmemb; int selbit; int selidx; selmemb = randomint(1, 2); switch (selmemb) { case 1 : { selbit = randomint(0, sizeof(int)); flipbit(gene->x, selbit); break; } case 2 : { selbit = randomint(0, sizeof(int)); flipbit(gene->y, selbit); break; } }; }; void TRectanglePrinter(TRectangle *gene) { printf("x = %d ", gene->x); printf("y = %d ", gene->y); printf("width = %d ", gene->width); printf("height = %d ", gene->height); printf("\n"); }; void RectangleInit(TRectangle *gene) { gene->x = randomint(0, 255); gene->y = randomint(0, 255); gene->width = randomint(0, 255 - gene->x); gene->height = randomint(0, 255 - gene->y); }; float RectangleEval(TRectangle *gene) { if (gene->x>255 || gene->y>255) return(0); return(1); }; /* Chromosome Moderator Functions */ void TRectanglesInitializer(TRectangles *chrom, void *pop) { int i0; for (i0 = 0; i0<20; ++i0) RectangleInit(&(chrom->rectangles[i0]), chrom); chrom->population = pop; }; int TRectanglesEvaluator(TRectangles *chrom) { int sum; int i0; sum = 0; for (i0 = 0; i0<20; ++i0) sum += RectangleEval(&(chrom->rectangles)[i0]); return(sum); }; void TRectanglesCrossover(TRectangles parent[], int pcount, TRectangles child[], int *ccount) { int crossmember; int crosspoint; crossmember = randomint(1, 1); switch (crossmember) { case 1 : { TRectangle mchi[2]; TRectangle mpar[2]; int cchi; int i0; for (i0 = 0; i0<20; ++i0) { mpar[0] = parent[0].rectangles[i0]; mpar[1] = parent[1].rectangles[i0]; TRectangleCrossover(mpar, 2, mchi, &cchi); child[0].rectangles[i0] = mchi[0]; child[1].rectangles[i0] = mchi[1]; }; break; } }; }; void TRectanglesMutator(TRectangles *chrom) { int selmemb; int selbit; int selidx; selmemb = randomint(1, 1); switch (selmemb) { case 1 : { selidx = randomint(0, 20); TRectangleMutator(&(chrom->rectangles[selidx])); break; } }; }; void TRectanglesPrinter(TRectangles *chrom) { int i0; for (i0 = 0; i0<20; ++i0) TRectanglePrinter(&(chrom->rectangles[i0])); printf("\n"); }; /* Population Moderator Functions */ void PopInitializer(Pop *pop, void *alg) { int i0; for (i0 = 0; i0<100; ++i0) TRectanglesInitializer(&(pop->individuals[i0]), pop); pop->algorithm = alg; pop->size = 100; pop->crossrate = 0.95; pop->mutationrate = 0.05; }; void PopEvaluator(Pop *pop) { float sum; float min; float max; float fitness; int i; pop->fitscores[0] = TRectanglesEvaluator(&(pop->individuals[0])); sum = pop->fitscores[0]; min = pop->fitscores[0]; max = pop->fitscores[0]; for (i = 1; i<100; ++i) { fitness = TRectanglesEvaluator(&(pop->individuals[i])); pop->fitscores[i] = fitness; sum+=fitness; if (fitness>max) max = fitness; if (fitness<min) min = fitness; }; pop->avgfitness = sum/100; pop->minfitness = min; pop->maxfitness = max; }; int PopSelector(Pop *pop) { int idx; float dist; float partsum; float fullsum; idx = 0; fullsum = pop->avgfitness*100; dist = randomfloat(0, 1)*fullsum; while (partsum<dist && idx<100 ) { partsum += pop->fitscores[idx]; ++idx; }; return(idx); }; void PopReproducer(Pop *pop, Pop *newpop) { int paridx1; int paridx2; int i; TRectangles tmppar[2]; TRectangles tmpchi[2]; int cchi; for (i = 0; i<100; i+=2) { paridx1 = PopSelector(pop); paridx2 = PopSelector(pop); if (randomfloat(0, 1)>pop->crossrate) { tmppar[0] = pop->individuals[paridx1]; tmppar[1] = pop->individuals[paridx2]; TRectanglesCrossover(tmppar, 2, tmpchi, &cchi); newpop->individuals[i] = tmpchi[0]; newpop->individuals[i + 1] = tmpchi[1]; } else { newpop->individuals[i] = pop->individuals[paridx1]; newpop->individuals[i + 1] = pop->individuals[paridx2]; }; }; if (i<100) newpop->individuals[i] = pop->individuals[i]; }; void PopMutator(Pop *pop) { int i0; for (i0 = 0; i0<100; ++i0) if (randomfloat(0, 1) > pop->mutationrate) TRectanglesMutator(&(pop->individuals)[i0]); }; void PopPrinter(Pop *pop) { int i0; for (i0 = 0; i0<100; ++i0) TRectanglesPrinter(&(pop->individuals[i0])); printf("\n"); }; /* Algorithm Moderator Functions */ void GAInitializer(GA *alg) { PopInitializer(&(alg->population), alg); alg->generation = 0; }; int GATerminator(GA *alg) { if (alg->generation>100) return(1); return(0); }; void GAReplacement(GA *alg, Pop *newpop) { alg->population = *newpop; }; void GAEvolver() { GA alg; Pop Offspring; GAInitializer(&alg); while (!GATerminator(&alg) ) { PopEvaluator(&(alg.population)); PopReproducer(&(alg.population), &Offspring); PopMutator(&Offspring); GAReplacement(&alg, &Offspring); ++alg.generation; }; GAPrinter(&alg); }; void GAPrinter(GA *alg) { PopPrinter(&(alg->population)); printf("\n"); }; // Extra Functions