import java.io.FileWriter;
import java.io.IOException;
import java.util.Random;


public class DiferencialniEvoluce {
	static void randperm(int[] p, Random rand) {
		int n = p.length;
		for (int i=1; i<n; i++) {
			int j = rand.nextInt(i+1);
			int tmp = p[i];
			p[i] = p[j];
			p[j] = tmp;
		}
	}

	/* 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í
	static int BEHY = 10;	// Počet behů 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
	double[][] populace;
	double[] fitness;
	// Dárci
	double[][] darci = new double[N][];
	// Noví jedinci a jejich fitness
	double[][] novi = new double[N][];
	double[] novi_fitness = new double[N];
	// Nejlepší jedinec a jeho fitness
	static double[] best;
	static double best_fitness;
	// Fitness nejlepšího zalogovaného
	static double best_log = Double.MAX_VALUE;

	Logovani LOG;
	Random rand;

	DiferencialniEvoluce(Random rand, Logovani log) {
		this.rand = rand;
		this.LOG = log;
	}

	/* 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(double[] v) {
		double res = 0;
		for (int i=0; i<D; i++)
			res += Math.abs(i-v[i]);
		return res;
	}

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

	/* Inicializuje počáteční populaci */
	void init_populace() {
		// Vygeneruj jedince
		populace = new double[N][];
		for (int i=0; i<N; i++) {
			populace[i] = generuj_jedince(D);
		}
		// Spočítej jejich fitness
		fitness = new double[N];
		best_fitness = Double.MAX_VALUE; 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 = new double[D];
		for (int i=0; i<D; i++)
			best[i] = populace[index][i];
	}

	/* Ze tří zadaných jedinců vytvoří dárce */
	double[] vytvor_darce(double[] p, double[] q, double[] r) {
		double[] d = new double[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 */
	double[] krizeni(double[] x, double[] d) {
		double[] y = new double[D];
		int j = rand.nextInt(D);	// Náhodný gen, který se určitě vezme z dárce
		double pst = rand.nextDouble();
		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 spust() {
		init_populace();
		// Inicializace tří permutací
		int[] p = new int[N];
		int[] q = new int[N];
		int[] r = new int[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 = new double[N][];
			// Generování náhodných permutací
			randperm(p, rand);
			randperm(q, rand);
			randperm(r, rand);
			// Vytvoření dárců (mutace)
			for (int i=0; i<N; i++) {
				darci[i] = vytvor_darce(populace[p[i]], populace[q[i]], populace[r[i]]);
			}
			// Křížení
			novi = new double[N][];
			novi_fitness = new double[N];
			for (int i=0; i<N; i++) {
				double[] y = krizeni(populace[i], darci[i]);
				novi[i] = y;
				novi_fitness[i] = 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]) {
					populace[i] = novi[i];
					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 */
	public static void zaloguj_nejlepsiho(double[] best) {
		try {
			FileWriter fw = new FileWriter("best.log");
			fw.write("Fitness: " + best_fitness + "\n");
			fw.write("Geny:\n");
			for (int i=0; i<best.length; i++)
				fw.write(best[i] + " ");
			fw.write("\n");
			fw.close();
		}
		catch(IOException ioe) {
			System.err.println("IOException");
			System.exit(1);
		}
	}

	public static void main(String[] args) {
		Random rand = new Random(10121996);	// Zadejte své datum narození jako DDMMYYYY
		Logovani LOG = new Logovani();
		// Spusť několik nezávislých běhů
		for (int b=0; b<BEHY; b++) {
			System.out.println("Beh " + b);
			LOG.open(b);
			DiferencialniEvoluce de = new DiferencialniEvoluce(rand, LOG);
			de.spust();
			LOG.close();
			// Pokud máme nového nejlepšího jedince, zalogujeme jej
			if (best_log > best_fitness) {
				zaloguj_nejlepsiho(best);
			}
		}
	}

}

/* Třída pro logování výpočtu -- není třeba jí rozumět */
class Logovani {
	FileWriter fw;

	/* Otevře soubor pro logování */
	public void open(int b) {
		try {
			fw = new FileWriter("beh" + b + ".log");
		}
		catch (IOException ioe) {
			System.err.println("IOException");
			System.exit(1);
		}
	}

	/* Ukončí logování */
	public void close() {
		try {
			fw.close();
		}
		catch (IOException ioe) {
			System.err.println("IOException");
			System.exit(1);
		}
	}

	/* Udělá zápis z generace gen z iterace it */
	public void write(double[] fitness, int it) {
		double miny = Double.MAX_VALUE;
		double total = 0.0;
		for (int i=0; i<fitness.length; i++) {
			total += fitness[i];
			miny = (fitness[i] < miny) ? fitness[i] : miny;
		}
		try {
			fw.write(it + "\t" + (total/fitness.length) +"\t" + miny + "\n");
		}
		catch (IOException ioe) {
			System.err.println("IOException");
			System.exit(1);
		}
	}
}