// GeneticAlgorithm.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h> 
#include <iomanip.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <limits.h>

enum { FALSE = 0, TRUE = 1 };

const char szAppName[] = "redo";
const size_t POP_SZ = 100;
const size_t GEN_SZ = 50;
const bool	 cross	= TRUE;
const float  crate	= 0.9;
const bool	 mutate = TRUE;
const float  mrate  = 1.0;

const bool	 elite  = TRUE;
const bool   scale  = TRUE;

long Blackbox(long x);	
int main(int argc, char* argv[])
{
	long* pop = new long[POP_SZ];

	if(pop == NULL) throw;
		
	long* newpop = new long[POP_SZ];

	if(newpop == NULL) throw;

	long* fit = new long[POP_SZ];
	if(fit == NULL) throw;

	srand((unsigned)time(NULL));

	long bestl, bestf, minf, mask, sel, totf, avgf;
	size_t i, g, p1, p2;
	char buf[64];


	// create initial pop
	for(i = 0; i < POP_SZ; i++)
		pop[i] = long(rand());

	// start with generation zero
	g = 0;

	while(1)
	{
		// display progress
		//printf("%s (loop : %4u of %4u)", szAppName, g, GEN_SZ);
		
		// initialize for fitness testing
		bestf = -1L;
		totf  = 0L;
		minf  = LONG_MAX;

		// fitness testing
		for(i = 0; i < POP_SZ; i++)
		{
			// call fitness function and store result
			fit[i] = Blackbox(pop[i]);

			// keep track of best fitness
			if(fit[i] > bestf)
			{
				bestf = fit[i];
				bestl = pop[i];
			}

			// keep track of least fitness
			if(fit[i] < minf)
				minf = fit[i];

			// total fitness
			totf += fit[i];
		}

		// make sure we have at least some fit values
		if(totf == 0L)
		{
			printf(" pop has total fitness of ZERO");
			return 0;
		}

		// compute average fitness
		avgf = totf / POP_SZ;

		// sum(and maybe scale) fitness value
		if(scale)
		{
			// ensures that the least fitness is one
			++minf;

			// recalculate total fitness to reflected scaled values
			totf = 0L;

			for(i = 0; i < POP_SZ; i++)
			{
				fit[i] -= minf;   // reduce by smallest fitness
				fit[i] += fit[i]; // square result of above
				totf += fit[i];   // add into total fitness
			}
		}

		// display stats for this generation
		printf("Gen : %d, best : %d, avg : %d, min : %d\n",
				g, bestf, avgf, minf);
		
		// exit if this is final generation
		if(g == GEN_SZ)
			break;

		// create new population
		for(i = 0; i < POP_SZ; i++)
		{
			// roulette-select parent
			sel = (long)((float(rand()) / float(RAND_MAX)) * float(totf));

			p1 = 0;

			while(sel > fit[p1])
			{
				sel -= fit[p1];
				++p1;
			}

			// crossover reproduction
			if(cross && ((float(rand()) / float(RAND_MAX)) < crate))
			{
				sel = (long)((float(rand()) / float(RAND_MAX)) * float(totf));

				p2 = 0;

				while(sel > fit[p2])
				{
					sel -= fit[p2];
					++p2;
				}

				// mask of bits to be copied from first parent
				mask = 0xFFFFFFFFL << (int)((float(rand()) / float(RAND_MAX)) * 32.0F);

				// new string from two parents
				newpop[i] = (pop[p1] & mask) | (pop[p2] & (~mask));
			}

			else
			{
				// one parent. no crossover reproduction
				newpop[i] = pop[i];

				// mutation
				if(mutate && ((float(rand()) / float(RAND_MAX)) < mrate))
				{
					// select bit to be changed
					mask = 1L << (int)((float(rand()) / float(RAND_MAX)) * 32.0F);

					// flip the bit
					if(newpop[i] & mask) 
						newpop[i] &= ~mask;
					else
						newpop[i] |= mask;
				}
			}

			// if elite selection, replace first item with best
			if(elite)
				newpop[0] = bestl;

			// replace old population with new one
			memcpy(pop, newpop, POP_SZ * sizeof(long));
		}

		// increment generation
		g++;

	}
	
	delete [] pop;
	delete [] newpop;
	delete [] fit;

	getchar();
}	

long Blackbox(long x)
{
	// test value - the speed of light in meters persecond
	static const long n = 0x11DE784AL;

	long fit  = 0L;
	long mask = 1L;

	// count matching bits
	for(int i = 0; i < 32; i++)
	{
		if((x & mask) == (n & mask))
			++fit;

		mask <<= 1;
	}

	// return fitness 
	return fit;
}