import java.util.*;
import java.io.*;

/* Jedinci */
class Jedinec implements Comparable<Jedinec> {
	private int[] geny;
	private double fitness;
	private Random rand;
	
	/* Konstruktor – vygeneruje náhodného binárního jedince */
	public Jedinec(int d, Random rand) {
		this.rand = rand;
		geny = new int[d];
		for (int i=0; i<d; i++)
			geny[i] = rand.nextInt(2);
	}
	
	/* Kopírovací konstruktor */
	public Jedinec(Jedinec j) {
		fitness = j.fitness;
		rand = j.rand;
		geny = new int[j.geny.length];
		for (int i=0; i<geny.length; i++)
			geny[i] = j.geny[i];
	}
	
	/* Spočítá fitness a uloží ji do jedince */
	public double spocitejFitness() {
		fitness = 0;
		for (int i=0; i<geny.length; i++) {
			fitness += geny[i];
		}
		return fitness;
	}
	
	/* gettery a settery k privátním členům */
	public double getFitness() {
		return fitness;
	}
	public void setFitness(double fitness) {
		this.fitness = fitness;
	}
	public int[] getGeny() {
		return geny;
	}
	public void setGeny(int[] geny) {
		this.geny = geny;
	}
	/* Zařídí, že jedinci se třídí na základě fitness od největšího */
	@Override
	public int compareTo(Jedinec j) {
		return (int)Math.signum(j.fitness - fitness);
	}
}

public class GenetickyAlgoritmus {
	/* 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í
	static int BEHY = 10;		// Počet běhů celého algoritmu
	final int L = 10;		// Jednou za kolik iterací se loguje
	
	Random rand;			// Náhodný generátor
	Logovani log;			// Logování výpočtu
	
	/* Konstruktor */
	public GenetickyAlgoritmus(Random rand, Logovani log) {
		this.rand = rand;
		this.log = log;
	}
	
	/* Zmutuje jedince */
	public void mutace(Jedinec j) {
		int[] geny = j.getGeny();
		for (int i=0; i<geny.length; i++) {
			double p = rand.nextDouble();
			if (p < PB) {
				// Prohození bitů
				geny[i] = (geny[i]==0) ? 1 : 0;
			}
		}
	}
	
	/* Zkříží dva jedince */
	public void krizeni(Jedinec x, Jedinec y) {
		int[] xgeny = x.getGeny();
		int[] ygeny = y.getGeny();
		// Náhodný bod jednobodového křížení
		int k = rand.nextInt(D);
		for (int i=k; i<D; i++) {
			int tmp = xgeny[i];
			xgeny[i] = ygeny[i];
			ygeny[i] = tmp;
		}
	}
	
	/* Ruletová selekce */
	public ArrayList<Jedinec> ruletovaSelekce(ArrayList<Jedinec> gen, int n) {
		// Spočítej celkovou fitness
		double total = 0;
		for (int i=0; i<gen.size(); i++)
			total += gen.get(i).getFitness();
		// Vyber n jedinců
		ArrayList<Jedinec> vyber = new ArrayList<Jedinec>();
		for (int i=0; i<n; i++) {
			// Hození kuličky do rulety
			double d = rand.nextDouble() * total;
			// Výběr příslušného jedince
			int j = 0;
			while (gen.get(j).getFitness() < d) {
				d -= gen.get(j).getFitness();
				j++;
			}
			vyber.add(new Jedinec(gen.get(j)));
		}
		return vyber;
	}
	
	/* Samotný průběh algoritmu */
	Jedinec run() {
		// Vygeneruj náhodnou populaci
		ArrayList<Jedinec> generace = new ArrayList<Jedinec>();
		for (int i=0; i<N; i++)
			generace.add(new Jedinec(D, rand));
		// Spočítej fitness jejích jedinců
		for (int i=0; i<N; i++)
			generace.get(i).spocitejFitness();
		Collections.sort(generace);
		Jedinec best = generace.get(0);
		// Iterace algoritmu
		for (int it=0; it<IT; it++) {
			// Logování jednou za L iterací
			if (it%L==0) {
				log.write(generace, it);
			}
			ArrayList<Jedinec> vyber = ruletovaSelekce(generace, N);
			// Křížení
			for (int i=0; i<vyber.size(); i+=2) {
				double p = rand.nextDouble();
				if (p < PK) {
					krizeni(vyber.get(i), vyber.get(i+1));
				}
			}
			// Mutace
			for (int i=0; i<vyber.size(); i++) {
				double p = rand.nextDouble();
				if (p < PM) {
					mutace(vyber.get(i));
				}
			}
			for (int i=0; i<vyber.size(); i++) {
				vyber.get(i).spocitejFitness();
			}
			// Elitismus – přidá do výběru část předchozí generace
			for (int i=0; i<N*PE; i++) {
				vyber.add(generace.get(i));
			}
			// Setřídí podle fitness
			Collections.sort(vyber);
			// Smaže minulou generaci
			generace.clear();
			// Vezme N nejlepších do další generace
			for (int i=0; i<N; i++)
			generace.add(vyber.get(i));
			if (generace.get(0).getFitness() > best.getFitness())
				best = generace.get(0);
		}
		log.write(generace, IT);
		return best;
	}
	
	/* Zapíše do souboru fitness a geny nejlepšího jedince */
	public static void zaloguj_nejlepsiho(Jedinec best) {
		try {
			FileWriter fw = new FileWriter("best.log");
			fw.write("Fitness: " + best.getFitness() + "\n");
			fw.write("Geny:\n");
			for (int i=0; i<best.getGeny().length; i++)
				fw.write(best.getGeny()[i] + " ");
			fw.write("\n");
			fw.close();
		}
		catch(IOException ioe) {
			System.err.println("IOException");
			System.exit(1);
		}
	}
	
	public static void main(String[] args) {
		// Zadejte své datum narození jako DDMMYYYY
		Random rand = new Random(10121996);
		Logovani log = new Logovani();
		Jedinec best = new Jedinec(0, rand);
		best.setFitness(0);
		for (int b=0; b<BEHY; b++) {
			// Otevře logování b-tého běhu
			log.open(b);
			System.out.println("Beh " + b);
			// Spustí běh genetického algoritmu a vrátí z něj nejlepšího jedince
			Jedinec j = new GenetickyAlgoritmus(rand, log).run();
			// Zavře logování b-tého běhu
			log.close();
			if (j.getFitness() > best.getFitness()) {
				best = j;
				zaloguj_nejlepsiho(best);
			}
		}
	}
}

/* Třída pro logování výpočtů – 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(ArrayList<Jedinec> gen, int it) {
		double maxi = 0.0;
		double total = 0.0;
		for (int i=0; i<gen.size(); i++) {
			total += gen.get(i).getFitness();
			maxi = (gen.get(i).getFitness() > maxi) ? gen.get(i).getFitness() : maxi;
		}
		try {
			fw.write(it + "\t" + (total/gen.size()) +"\t" + maxi + "\n");
		}
		catch (IOException ioe) {
			System.err.println("IOException");
			System.exit(1);
		}
	}
}