Solve f(x)=0 by GA

gatest.cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <ctime>

const int maxGeneration = 1024;
const int populationSize = 1024;
const int gtypeLength = 20;
const double eliteRate = 0.1;
const double probMutate = 0.05;
const double probCross = 1.0;

struct Individual
{
	std::vector<int> gtype;
	double fitness;
};

bool compFitness(const Individual& v1, const Individual& v2)
{
	return v1.fitness > v2.fitness;
}

void printGtype(const std::vector<int>& gtype)
{
	for (size_t i = 0; i < gtype.size(); i++)
		std::cout << gtype[i];
}

double f(double x)
{
	return x*x - 2.0;
}

double decode(const std::vector<int>& gtype)
{
	double max = 5.0;
	double min = 1.0;
	double delta = max - min;
	double ret = min;
	for (int i = 0; i < gtypeLength; i++)
		ret += gtype[i] * delta / pow(2.0, i + 1);
	return ret;
}

double fitness(const std::vector<int>& gtype)
{
	// Decode g-type
	double x = decode(gtype);
	return 1.0 / (1.0 + abs(f(x)));
}

std::vector<int> cross(const std::vector<int> g1, const std::vector<int> g2, int pos)
{
	std::vector<int> ret;
	for (int i = 0; i < gtypeLength; i++)
		if (i < pos) ret.push_back(g1[i]);
		else ret.push_back(g2[i]);
	return ret;
}

int main()
{
	std::cout.precision(10);
	srand(time(NULL));

	std::vector<Individual> population, nextp;

	// Initialize population
	for (int i = 0; i < populationSize; i++)
	{
		Individual ind;
		for (int j = 0; j < gtypeLength; j++)
			ind.gtype.push_back(0);
		ind.fitness = 0.0;
		population.push_back(ind);
	}

	nextp = population;

	// Iterate and refine
	for (int gen = 0; gen < maxGeneration; gen++)
	{
		std::cout << "Generation #" << gen << std::endl;

		// Calculate fitness
		for (int i = 0; i < populationSize; i++)
		{
			Individual& ind = population[i];
			ind.fitness = fitness(ind.gtype);
		}

		// Sort by fitness
		std::sort(population.begin(), population.end(), compFitness);

		// Print the best one
		double x = decode(population[0].gtype);
		std::cout << "f(" << x << ") = " << f(x) << std::endl;
		std::cout << "[gtype ";
		printGtype(population[0].gtype);
		std::cout << "]" << std::endl;

		// Selection of the elites
		int elites = (int)((double)populationSize * eliteRate);
		for (int i = 0; i < elites; i++)
		{
			nextp[i].gtype = population[i].gtype;
		}

		// Cross and mutation
		for (int i = elites; i < populationSize; i++)
		{
			double drand = (double)rand() / RAND_MAX;

			// Cross
			if (drand < probCross)
			{
				int ind1 = rand() % populationSize;
				int ind2 = rand() % populationSize;
				int pos = rand() % (gtypeLength + 1);
				nextp[i].gtype = cross(population[ind1].gtype, population[ind2].gtype, pos);
			}
			else
			{
				// Nothing happens
				nextp[i].gtype = population[i].gtype;
			}

			// Mutation
			if (drand < probMutate)
			{
				int pos = rand() % gtypeLength;
				nextp[i].gtype[pos] = 1 - nextp[i].gtype[pos];
			}
		}

		population = nextp;
	}

	return 0;
}