#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>

using namespace std;

/* Náhodné číslo z intervalu [0, 1) */
double randdouble() {
    return rand()/(double(RAND_MAX)+1);
}

/* Parametry algoritmu */
int N = 100;		// Velikost populace
int D = 50;		// Velikost jedince
double PK = 0.9;	// Pravděpodobnost křížení
double PM = 0.1;	// Pravděpodobnost mutace
double PB = 0.02;	// Pravděpodobnost mutace na jednom bitu
double PE = 0.01;	// Velikost elitismu
int IT = 120;		// Maximální počet iterací
int BEHY = 10;		// Počet běhů celého algoritmu
const int L = 10;	// Jednou za kolik iterací se loguje

/* Jedinci */
struct Jedinec {
	vector<int> geny;
	double fitness;
	/* Zařídí, že jedinci se třídí na základě fitness od největšího */
	bool operator<(const Jedinec &x) const {
		return fitness > x.fitness;
	}
};
/* Třída pro logování výpočtů – není třeba jí rozumět */
class Logovani {
	ofstream ofs;
public:
	/* Otevře soubor pro logování */
	void open(int x) {
		stringstream name;
		name << "beh" << x << ".log";
		ofs.open(name.str().c_str());
	}
	/* Ukončí logování */
	void close() {
		ofs.close();
	}
	/* Udělá zápis z generace gen z iterace it */
	void write(vector<Jedinec> gen, int it) {
		double maxi = 0;
		double total = 0;
		for (int i=0; i<gen.size(); i++) {
			total += gen[i].fitness;
			maxi = max(maxi, gen[i].fitness);
		}
		ofs << it << "\t" << total/gen.size() << "\t" << maxi << endl;
	}
} log;

/* Vygeneruje náhodného binárního jedince */
Jedinec generuj_jedince(int d) {
	Jedinec j;
	j.geny = vector<int>(d, 0);
	for (int i=0; i<d; i++)
		j.geny[i] = rand()%2;
	return j;
}

/* Spočítá fitness a uloží ji do jedince */
void spocitej_fitness(Jedinec &x) {
	double f = 0;
	for (int i=0; i< x.geny.size(); i++)
		f += x.geny[i];
	x.fitness = f;
}

/* Zmutuje jedince */
void mutace(Jedinec &x) {
	for (int i=0; i<x.geny.size(); i++) {
		double p = randdouble();
		if (p < PB) {
			// Prohození bitů
			x.geny[i] = !x.geny[i];
		}
	}
}

/* Zkříží dva jedince */
void krizeni(Jedinec &x, Jedinec &y) {
	// Náhodný bod jednobodového křížení
	int k = rand()%D;
	for (int i=k; i<D; i++) {
		swap(x.geny[i], y.geny[i]);
	}
}

/* Ruletová selekce */
vector<Jedinec> ruletova_selekce(vector<Jedinec> &gen, int n) {
	// Spočítej celkovou fitness
	double total = 0;
	for (int i=0; i<gen.size(); i++)
		total += gen[i].fitness;
	// Vyber n jedinců
	vector<Jedinec> vyber;
	for (int i=0; i<n; i++) {
		// Hození kuličky do rulety
		double d = randdouble() * total;
		// Výběr příslušného jedince
		int j = 0;
		while (gen[j].fitness < d) {
			d -= gen[j].fitness;
			j++;
		}
		vyber.push_back(gen[j]);
	}
	return vyber;
}

/* Samotný průběh algoritmu */
Jedinec geneticky_algoritmus() {
	// Vygeneruj náhodnou populaci
	vector<Jedinec> generace;
	for (int i=0; i<N; i++)
		generace.push_back(generuj_jedince(D));
	// Spočítej fitness jejích jedinců
	for (int i=0; i<N; i++)
		spocitej_fitness(generace[i]);
	sort(generace.begin(), generace.end());
	Jedinec best = generace[0];
	// Iterace algoritmu
	for (int it=0; it<IT; it++) {
		// Logování jednou za L iterací
		if (it%L==0) {
			log.write(generace, it);
		}
		vector<Jedinec> vyber = ruletova_selekce(generace, N);
		// Křížení
		for (int i=0; i<vyber.size(); i+=2) {
			double p = randdouble();
			if (p < PK)
				krizeni(vyber[i], vyber[i+1]);
		}
		// Mutace
		for (int i=0; i<vyber.size(); i++) {
			double p = randdouble();
			if (p < PM)
				mutace(vyber[i]);
		}
		for (int i=0; i<vyber.size(); i++)
			spocitej_fitness(vyber[i]);
		// Elitismus – přidá do výběru část předchozí generace
		for (int i=0; i<N*PE; i++)
			vyber.push_back(generace[i]);
		// Setřídí podle fitness
		sort(vyber.begin(), vyber.end());
		// Smaže minulou generaci
		generace.clear();
		// Vezme N nejlepších do další generace
		generace = vector<Jedinec>(vyber.begin(), vyber.begin()+N);
		if (generace[0].fitness > best.fitness)
			best = generace[0];
	}
	log.write(generace, IT);
	return best;
}

/* Zapíše do souboru fitness a geny nejlepšího jedince */
void zaloguj_nejlepsiho(Jedinec best) {
	ofstream ofs("best.log");
	ofs << "Fitness: " << best.fitness << endl;
	ofs << "Geny:" << endl;
	for (int i=0; i<best.geny.size(); i++)
		ofs << best.geny[i] << " ";
	ofs << endl;
}

int main() {
	// Zadejte své datum narození jako DDMMYYYY
	srand(10121996);
	Jedinec best;
	best.fitness = 0;
	for (int b=0; b<BEHY; b++) {
		cout << "Beh " << b << endl;
		// Otevře logování b-tého běhu
		log.open(b);
		// Spustí běh genetického algoritmu a vrátí z něj nejlepšího jedince
		Jedinec j = geneticky_algoritmus();
		// Zavře logování b-tého běhu
		log.close();
		if (j.fitness > best.fitness) {
			best = j;
			zaloguj_nejlepsiho(best);
		}
	}
	return 0;
}