Algorytmy genetyczne – kilka pytań

#include <cstdint>
#include <vector>
#include <algorithm> 
#include <random>
#include <assert.h>

const int nBits = 6;
const int halfPopulSize = 5;
double ThrM = 0.4,ThrF = 0.6;

class Individual {
public:
	bool bits[nBits];
	double fitness;
	void compFitness()
	{
		int x = decode();
		fitness = x*x;
	}
	void initRandom()
	{
		for (int i=0; i<nBits; i++)
			if (rand() % 2==0)
				bits[i] = 0;
			else
				bits[i] = 1;
	}	

	void crossOver(Individual &a, Individual &b)
	{
		int pos = rand() % (nBits-1);
		for (int i=0; i<=pos; i++)
			bits[i] = b.bits[i];
		for (int i = pos+1; i < nBits; i++)
			bits[i] = a.bits[i];
		printf("CO: %d %d,%d->%d\n",pos, a.decode(), b.decode(), decode());
	}

	int decode()
	{
		//Decode string as unsigned binary integer - true = 1, false = 0
		int accum = 0; int powerof2 = 1;
		for (int j = 0; j < nBits; j++)
		{
			if (bits[j])accum += powerof2;
			powerof2 *= 2;
		}
		return accum;
	}
};


std::vector<Individual> males;
std::vector<Individual> females;
std::vector<Individual> newMales;
std::vector<Individual> newFemales;

void initialize()
{
	for (int i=0; i<halfPopulSize; i++)
	{
		Individual ind;
		ind.initRandom();
		males.push_back(ind);
		ind.initRandom();
		females.push_back(ind);
	}
}

bool compare(const Individual &a, const Individual &b)
{
	return a.fitness > b.fitness;
}


void generate()
{
	for (int i = 0; i<halfPopulSize; i++)
		males[i].compFitness();
	sort(males.begin(), males.end(), compare);
	for (int i = 0; i<halfPopulSize; i++)
		females[i].compFitness();
	sort(females.begin(), females.end(), compare);
	int hM = (int)(halfPopulSize * ThrM);
	int hF = (int)(halfPopulSize * ThrF);
	for (int i = 0; i<halfPopulSize; i++)
	{
		int indexM = rand() % hM;
		int indexF = rand() % hF;
		Individual ind;
		ind.crossOver(males[indexM], females[indexF]);
		newMales.push_back(ind);
		indexM = rand() % hM;
		indexF = rand() % hF;
		ind.crossOver(males[indexM], females[indexF]);
		newFemales.push_back(ind);
	}
	males = move(newMales);
	females = move(newFemales);
}

void print()
{
	for (int i = 0; i<halfPopulSize; i++)
		printf("%d ",males[i].decode());
	printf("|");
	for (int i = 0; i<halfPopulSize; i++)
		printf("%d ", females[i].decode());
	printf("\n");
}

int main()
{
	initialize();
	for (int i=0; i<10; i++)
	{
	  generate();
	  print();
	}
    return 0;
}

#include <cstdint>
#include <vector>
#include <algorithm> 
#include <random>
#include <assert.h>

const int nBits = 8;
const int populSize = 100;
double Thr = 0.5;

unsigned int GrayToBinary(unsigned int num)
{
	unsigned int mask = num >> 1;
	while (mask != 0)
	{
		num = num ^ mask;
		mask = mask >> 1;
	}
	return num;
}


double fitfun(int x)
{
	x = GrayToBinary(x);
	return -2.18678 + 0.139089 * x - 0.00210957 * x*x
		+ 1.24172e-05 * x*x*x - 2.46726e-08 * x*x*x*x;
}

class Individual {
public:
	int x;
	double fitness;
	void compFitness()
	{
		fitness = fitfun(x);
	}
	void initRandom()
	{
		x = rand() % (1 << nBits);
	}

	/*	void crossOver(Individual &a, Individual &b)
	{
	int pos = rand() % (nBits-1);
	for (int i=0; i<=pos; i++)
	bits[i] = b.bits[i];
	for (int i = pos+1; i < nBits; i++)
	bits[i] = a.bits[i];
	printf("CO: %d %d,%d->%d\n",pos, a.decode(), b.decode(), decode());
	}*/

	static int mutate(int x, int maxBit)
	{
		if (rand() % 2 > 0)
			return x;
		else
		{
			int newx = x ^ (1 << (rand() % maxBit));
			return newx;
		}
	}

	void crossOver(Individual &a, Individual &b)
	{
		int ax = a.x;
		int bx = b.x;

		if (rand() % 2 == 0)
		{
			int tmp = ax;
			ax = bx;
			bx = tmp;
		}
		int first = -1, last = -1;
		for (int i = 0; i<nBits; i++)
		{
			if ((ax & (1 << i)) != (bx & (1 << i)))
			{
				if (first == -1) first = i;
				last = i;
			}
		}
		if (first<0)
		{
			x = mutate(ax, nBits);
			return;
		}
		if (first == last)
		{
			//printf("ax=%d, bx=%d\n",ax,bx);
			x = mutate(ax, first + 1);
			return;
		}

		int pos = rand() % (last - first) + first + 1;
		x = 0;
		//for (int pos = first+1; pos<last+1; pos++)		
		for (int i = 0; i<pos; i++)
		{
			if (ax & (1 << i))
				x |= (1 << i);
		}
		for (int i = pos; i<nBits; i++)
		{
			if (bx & (1 << i))
				x |= (1 << i);
		}
	}
};


std::vector<Individual> popul;
std::vector<Individual> newPopul;

bool compare(const Individual &a, const Individual &b)
{
	return a.fitness > b.fitness;
}

void initialize()
{
	for (int i = 0; i<populSize; i++)
	{
		Individual ind;
		ind.initRandom();
		popul.push_back(ind);
	}
	for (int i = 0; i<populSize; i++)
		popul[i].compFitness();
	sort(popul.begin(), popul.end(), compare);
}

/**
return true if is only 1 or 0 set bits
(for 0 retuns true)
if is severeal set bits return false
*/
#define isAlone(x) ((x & (x - 1))==0)


void generate()
{
	int goodCount = (int)(populSize * Thr);
	for (int i = 0; i<populSize; i++)
	{
		int indexA = rand() % goodCount;
		int indexB = rand() % goodCount;
		//int xor = males[indexM].x ^ females[indexF].x;
		//if (males[indexM].x !=females[indexF].x && newMales.size()<halfPopulSize && !isAlone(xor))
		{
			Individual ind;
			ind.crossOver(popul[indexA], popul[indexB]);
			newPopul.push_back(ind);
		}		
	}
	popul = move(newPopul);
	for (int i = 0; i<populSize; i++)
		popul[i].compFitness();
	sort(popul.begin(), popul.end(), compare);
}

void print(int nGen)
{
	/*for (int i = 0; i<std::min(10, populSize); i++)
		printf("%d ", GrayToBinary(popul[i].x), popul[i].fitness);
	printf("\n");*/
	if (GrayToBinary(popul[0].x)!=196) printf("%d\n",nGen);
}

int main()
{
	double maxf = fitfun(0);
	int idxmax = 0;
	for (int i = 1; i<256; i++)
	{
		double f = fitfun(i);
		if (f>maxf)
		{
			maxf = f;
			idxmax = i;
		}
	}
	printf("max for %d = %f\n", idxmax, maxf);
	initialize();
	print(0);
	for (int i = 1; i<100; i++)
	{
		generate();
		print(i);
	}
	return 0;
}