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

using namespace std;

// Třída pro logování výpočtů
class Logovani {
	ofstream ofs;
public:
	void open(int x) {
		stringstream name;
		name << "beh" << x << ".log";
		ofs.open(name.str().c_str());
	}
	void close() {
		ofs.close();
	}
	void write(vector<double> fitness, int it) {
		double mini = 99999999;
		double total = 0;
		for (int i=0; i<fitness.size(); i++) {
			total += fitness[i];
			mini = min(mini, fitness[i]);
		}
		ofs << it << "\t" << total/fitness.size() << "\t" << mini << endl;
	}
} LOG;

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

void randperm(vector<int> &p) {
	int n = p.size();
	for (int i=1; i<n; i++) {
		swap(p[i], p[rand()%(i+1)]);
	}
}

/* Parametry algoritmu */
int N = 70;		// Velikost populace
int D = 10;		// Velikost jedince
double F = 0.7;		// Koeficient mutace
double C = 0.5;		// Pravděpodobnost křížení
int IT = 500;		// Maximální počet iterací
int BEHY = 10;		// Počet běhů celého algoritmu

double MIN_X = -3.0;	// Minimální možná hodnota jedné složky jedince
double MAX_X = 15.0;	// Maximální možná hodnota jedné složky jedince
// Populace a její fitness
vector<vector<double> > populace;
vector<double> fitness;
// Dárci
vector<vector<double> > darci;
// Noví jedinci a jejich fitness
vector<vector<double> > novi;
vector<double> novi_fitness;
// Nejlepší jedinec a jeho fitness
vector<double> best;
double best_fitness;
// Fitness nejlepšího zalogovaného
double best_log = 999999999;

/* Ohodnocující funkce jedince */
/* Momentálně nastavená pro vývoj jedince, kde v[i] = i
 * Změňte v závislosti na vámi řešeném problému
 */
double ohodnot_jedince(vector<double> v) {
	double res = 0;
	for (int i=0; i<D; i++)
		res += abs((double)i-v[i]);
	return res;
}

/* Vygeneruje náhodného jedince délky d s hodnotami mezi MIN_X a MAX_X */
vector<double> generuj_jedince(int d) {
	vector<double> v(d);
	for (int i=0; i<d; i++) {
		v[i] = randdouble()*(MAX_X - MIN_X) + MIN_X;
	}
	return v;
}

/* Inicializuje počáteční populaci */
void init_populace() {
	// Vygeneruj jedince
	populace.clear();
	for (int i=0; i<N; i++) {
		populace.push_back(generuj_jedince(D));
	}
	// Spočítej jejich fitness
	fitness.clear();
	fitness = vector<double>(N);
	best_fitness = 9999999; int index = -1;
	for (int i=0; i<N; i++) {
		fitness[i] = ohodnot_jedince(populace[i]);
		if (fitness[i] < best_fitness) {
			best_fitness = fitness[i];
			index = i;
		}
	}
	// Zkopiruj si nejlepšího
	best = vector<double>(D);
	for (int i=0; i<D; i++) best[i] = populace[index][i];
}

/* Ze tří zadaných jedinců vytvoří dárce */
vector<double> vytvor_darce(vector<double> &p, vector<double> &q, vector<double> &r) {
	vector<double> d(D);
	for (int i=0; i<D; i++) {
		d[i] = p[i] + F*(q[i]-r[i]);
	}
	return d;
}

/* Provede křížení dárce a původního jedince */
vector<double> krizeni(vector<double> &x, vector<double> &d) {
	vector<double> y(D);
	int j = rand()%D;	// Náhodný gen, který se určitě vezme z dárce
	double pst = randdouble();
	for (int i=0; i<D; i++) {
		y[i] = (pst < C || i==j) ? d[i] : x[i];
	}
	return y;
}

/* Průběh celého algoritmu */
void diferencialni_evoluce() {
	init_populace();
	// Inicializace tří permutací
	vector<int> p(N);
	vector<int> q(N);
	vector<int> r(N);
	for (int i=0; i<N; i++) p[i] = q[i] = r[i] = i;
	for (int it=0; it < IT; it++) {
		if (it%10==0) {
			LOG.write(fitness, it);
		}
		darci.clear();
		// Generování náhodných permutací
		randperm(p);
		randperm(q);
		randperm(r);
		// Vytvoření dárců (mutace)
		for (int i=0; i<N; i++) {
			darci.push_back(vytvor_darce(populace[p[i]], populace[q[i]], populace[r[i]]));
		}
		// Křížení
		novi.clear();
		novi_fitness.clear();
		for (int i=0; i<N; i++) {
			vector<double> y = krizeni(populace[i], darci[i]);
			novi.push_back(y);
			novi_fitness.push_back(ohodnot_jedince(y));
		}
		// Selekce -- vybere lepšího z původního a nového jedince
		int index = -1;
		for (int i=0; i<N; i++) {
			if (novi_fitness[i] <= fitness[i]) {
				swap(populace[i], novi[i]);
				swap(fitness[i], novi_fitness[i]);
			}
			// Pamatuj si index nejlepšího jedince
			if (fitness[i] < best_fitness) {
				index = i;
				best_fitness = fitness[i];
			}
		}
		// Pokud jsme našli nejlepšího, zapamatujeme si jej
		if (index!=-1) {
			for (int i=0; i<D; i++) best[i] = populace[index][i];
		}
	}
	LOG.write(fitness, IT);
}

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

int main() {
	srand(10121996);	// Zadejte své datum narození jako DDMMYYYY
	// Spusť několik nezávislých běhů
	for (int b=0; b<BEHY; b++) {
		cout << "Beh " << b << endl;
		LOG.open(b);
		diferencialni_evoluce();
		LOG.close();
		// Pokud máme nového nejlepšího jedince, zalogujeme jej
		if (best_log > best_fitness) {
			zaloguj_nejlepsiho(best);
		}
	}
	return 0;
}