/*************************************************************************************
Janne Koljonen
Vaasan yliopisto

Soft Computing
Geneettinen algoritmi

**************************************************************************************/

public class GeneettinenAlgoritmi
{
	private int[][] population; // population[] : yksilöt, population[][] kromosomit
	private FitnessFunction fitnessf; // Käytettävä hyvyysfunktio (rajapinta)
	private int[] bits; // Bittien lukumäärä kussakin kromosomissa

	private double elitism=0.5; // 0-1, kuinka suuri osa populaatiosta kuuluu eliittiin
	private double uniformcrossoverprob=0.5; // 0-1, todennäköisyys, että tehdään uniform crossover
	private double onepointcrossoverprob=0.5; // 0-1, todennäköisyys, että tehdään 1-pisteen crossover
	private double randomprob=0.0; // Todennäköisyys, ettei tehdä risteytystä eikä mutaatiota vaan arvotaan uusi yksilö
	private double mutationrate=0.01; // Kunkin bitin mutaation todennäköisyys

	private int generation; // Current generation

	private int maxgenerations=100; // oletuksena 100
	private int stopfitness=0; // Tavoitehyvyys, oletuksena 0
	private boolean minimize=true; /* TRUE=minimoidaan, FALSE=maksimoidaan. 
		Minimointi oletuksena */
	private boolean noclones=false; /** Tuhotaanko kloonit. Oletus EI. **/

	private int solutions=0; /* Ratkaisujen määrä */
	private int stopsolutions; /* Montako ratkaisua haetaan */



	// Harjoitus 3. Tehtävä 3. Pääohjelma
	public static void main(String[] args)
	{
		System.out.println("SAT");

		int[][] bm=new int[11][16]; // Boolen funktio
		int[][] bm2=new int[11][16]; // Boolen funktio
		for(int i2=0;i2<bm.length;i2++)
		{
			for(int i1=0;i1<bm[i2].length;i1++)
			{
				bm[i2][i1]=2; // Aluksi kaikki muuttujat puuttuviksi
			}
		}
		for(int i2=0;i2<bm2.length;i2++)
		{
			for(int i1=0;i1<bm2[i2].length;i1++)
			{
				bm2[i2][i1]=2; // Aluksi kaikki muuttujat puuttuviksi
			}
		}
		bm[0][0]=1;
		bm[1][1]=0;
		bm[2][0]=1;
		bm[2][2]=1;
		bm[3][3]=1;
		bm[3][4]=1;
		bm[3][5]=0;
		bm2[4][1]=1;
		bm2[4][2]=1;
		bm2[4][5]=1;
		bm2[4][6]=0;
		bm2[5][2]=1;
		bm2[5][4]=0;
		bm2[5][7]=1;
		bm2[5][8]=1;
		bm2[6][0]=0;
		bm2[6][5]=1;
		bm2[6][8]=1;
		bm2[6][9]=0;
		bm2[7][2]=0;
		bm2[7][4]=0;
		bm2[7][7]=0;
		bm2[7][8]=1;
		bm[8][10]=1;
		bm[9][11]=1;
		bm[9][12]=1;
		bm[9][13]=1;
		bm[10][14]=0;
		bm[10][15]=0;

		SAT sat=new SAT(bm);
		SAT sat2=new SAT(bm2);
		SAT2 sattulo=new SAT2(sat, sat2);

		int pop=2000;
		int chrom=1;
		double elit=0.5;
		double unicross=0;
		double onepointcross=0;
		double randprob=1;
		double muta=0.01;
		FitnessFunction ff=sattulo;
		int[] bitss=new int[]{16};
		int stopfit=0;
		int maxgen=50;
		int tulost=2;


		GeneettinenAlgoritmi ga=new GeneettinenAlgoritmi(pop, chrom, elit, unicross, onepointcross, randprob, muta, ff, bitss);
		ga.setNoClones(true);
		ga.setStopsolutions(40000); // VHDL:llä
		//ga.printPopulation();
		ga.simulateMultiSolutions(tulost,maxgen);

		ga=new GeneettinenAlgoritmi(pop, chrom, elit, unicross, onepointcross, randprob, muta, ff, bitss);
		ga.setNoClones(true);
		ga.setStopsolutions(40000); // VHDL:llä
		//ga.printPopulation();
		ga.simulateMultiSolutions(tulost,maxgen);

		ga=new GeneettinenAlgoritmi(pop, chrom, elit, unicross, onepointcross, randprob, muta, ff, bitss);
		ga.setNoClones(true);
		ga.setStopsolutions(40000); // VHDL:llä
		//ga.printPopulation();
		ga.simulateMultiSolutions(tulost,maxgen);

		ga=new GeneettinenAlgoritmi(pop, chrom, elit, unicross, onepointcross, randprob, muta, ff, bitss);
		ga.setNoClones(true);
		ga.setStopsolutions(40000); // VHDL:llä
		//ga.printPopulation();
		ga.simulateMultiSolutions(tulost,maxgen);

		ga=new GeneettinenAlgoritmi(pop, chrom, elit, unicross, onepointcross, randprob, muta, ff, bitss);
		ga.setNoClones(true);
		ga.setStopsolutions(40000); // VHDL:llä
		//ga.printPopulation();
		ga.simulateMultiSolutions(tulost,maxgen);

		// Tulostetaan ratkaisujen muuttujien arvot
		int[] solutionss=new int[ga.solutions];
		int i=1;
		int isol=0;
		if(ga.solutions>0)
		{
			solutionss[0]=ga.population[0][1];
			isol++;
		}
		for(;i<ga.population.length-1 && i<ga.solutions && ga.population[i][0]==0;i++)
		{
			if(ga.population[i][1]!=solutionss[isol-1])
			{
				solutionss[isol]=ga.population[i][1];
				isol++;
			}
		}
		int[] solutionsss=new int[isol];
		for(i=0;i<isol;i++)
		{
			solutionsss[i]=solutionss[i];
		}
		solutionss=solutionsss;
		InsertionSort.sort(solutionss);
		//System.out.println("Solutions:");
		for(i=0;i<isol;i++)
		{
			//sat.printBooleanVector(solutionss[i]);
		}
		//System.out.println("Totally: "+isol+" solutions!");
		//System.out.println("Generations: "+ga.generation);
		System.exit(0);
	}

	/** Muodostin: (populaation koko, kromosomien määrä, hyvyysfunktio, kromosomien bitit) **/
	public GeneettinenAlgoritmi(int popu,int numofp,FitnessFunction ff, int[] bitss)
	{
		population=new int[popu][1+numofp];
		fitnessf=ff;
		bits=bitss;
		initialize();
		sort();
		if(popu<30) printPopulation();
		else printBest();
	}


	/** Muodostin: */
	public GeneettinenAlgoritmi(int popu,int numofp, double elit, double unicross, double onepointcross, double randprob, double muta, FitnessFunction ff, int[] bitss)
	{
		population=new int[popu][1+numofp];
		fitnessf=ff;
		elitism=elit;
		uniformcrossoverprob=unicross;
		onepointcrossoverprob=onepointcross;
		randomprob=randprob;
		mutationrate=muta;
		fitnessf=ff;
		bits=bitss;
		initialize();
		sort();
		if(popu<30) printPopulation();
		//else printBest();
	}


	/** Arpoo aloituspopulaation **/
	public void initialize()
	{
		generation=1;
		if(bits==null)
		{
			for(int i2=0;i2<population.length;i2++)
			{
				for(int i1=1;i1<population[i2].length;i1++)
				{
					int x=1;
					population[i2][i1]=this.newCromosome(32);
				}
			}
		}
		else
		{
			for(int i2=0;i2<population.length;i2++)
			{
				for(int i1=1;i1<population[i2].length;i1++)
				{
					int x=1;
					population[i2][i1]=this.newCromosome(bits[i1-1]);
				}
			}
		}
	}

	/** Arpoo uuden bittivektorin **/
	private int newCromosome(int bitss)
	{
		int x=1;
		int apu=0;
		for(int b=0;b<32;b++)
		{
			if(b<bitss && Math.random()>=0.5 )
			{
				apu+=x;
			}
			x<<=1;
		}
		return apu;
	}

	/** Asettaa noClonesin **/
	public void setNoClones(boolean noclo)
	{
		noclones=noclo;
	}

	/** Asettaa noClonesin **/
	public void setStopsolutions(int stopsol)
	{
		stopsolutions=stopsol;
	}


	/** Simuloi, kunnes generations sukupolvea, vaikka stopfitness saavutettu.
	Useamman ratkaisun etsimiseen **/
	public void simulateMultiSolutions(int tulostus, int generations)
	{
		maxgenerations=generations;
		//printNumOfSolutions();
		generation=1;
		if(tulostus==0)
		{
			while(generation<=maxgenerations && solutions<stopsolutions)
			{
				nextGeneration();
				printNumOfSolutions();
			}
		}
		else if(tulostus==1)
		{
			while(generation<=maxgenerations && solutions<stopsolutions)
			{
				nextGeneration();
				printAllBest();
				printNumOfSolutions();
			}
		}
		if(tulostus==2)
		{
			while(generation<=maxgenerations && solutions<stopsolutions)
			{
				nextGeneration();
			}
		}
		else
		{
			while(generation<=maxgenerations && solutions<stopsolutions)
			{
				nextGeneration();
				printPopulation();
				printNumOfSolutions();
			}
		}
		System.out.println("Simulation over!");
		//printAllBest();
		printNumOfSolutions();
	}

	/** Simuloi populaatiota: (tulostustapa, sukupolvien määrä) **/
	public void simulate(int tulostus, int generations)
	{
		maxgenerations=generations;
		generation=1;
		simulate(tulostus);
	}

	/** Simuloi populaatiota: (tulostustapa) **/
	public void simulate(int tulostus)
	{
		if(tulostus==0)
		{
			while(generation<=maxgenerations && population[0][0]>stopfitness)
			{
				nextGeneration();
			}
		}
		else if(tulostus==1)
		{
			while(generation<=maxgenerations && population[0][0]>stopfitness)
			{
				nextGeneration();
				printBest();
			}
		}
		else
		{
			while(generation<=maxgenerations && population[0][0]>stopfitness)
			{
				nextGeneration();
				printPopulation();
			}
		}
		System.out.println("Simulation over!");
		printBest();
	}

	/** Arpoo risteytykseen vanhemmat **/
	public void nextGeneration()
	{
		int x1=0;
		int x2=0;
		for(int ind=(int)(elitism*population.length);ind<population.length;ind++) // Eliitin jälkeen uusia yksilöitä
		{
			x1=(int)(Math.random()*elitism*population.length);
			x2=(int)(Math.random()*elitism*population.length);

			double temp=Math.random();
			if(temp<uniformcrossoverprob)
			{
				this.uniformcrossover(x1,x2,ind);
				this.mutation(ind);
			}
			else if(temp<uniformcrossoverprob+onepointcrossoverprob)
			{
				this.onepointcrossover(x1,x2,ind);
				this.mutation(ind);
			}
			else if(temp<uniformcrossoverprob+onepointcrossoverprob+randomprob)
			{
				this.randomtrial(ind);
			}
			else
			{
				this.twopointcrossover(x1,x2,ind);
				this.mutation(ind);
			}
		}
		this.sort();
		generation++;
	}

	/** Risteyttää **/
	public void uniformcrossover(int x1,int x2,int xnew)
	{
		population[xnew][0]=0;
		for(int chrom=1; chrom<population[x1].length; chrom++)
		{
			int x=1;
			population[xnew][chrom]=0;
			for(int b=0;b<bits[chrom-1];b++)
			{
				if(Math.random()>=0.5) // TRUE => bitti 1. vanhemmasta
				{
					population[xnew][chrom]|=population[x1][chrom]&x;
				}
				else // Toisesta vanhemmasta
				{
					population[xnew][chrom]|=population[x2][chrom]&x;
				}
				x<<=1;
			}
		}
	}

	public void onepointcrossover(int x1,int x2,int xnew)
	{
		// Lasketaan bittien määrä
		int bitit=0;
		for(int i=0; i<bits.length; i++)
		{
			bitit+=bits[i];
		}
		// Arvotaan risteytyskohta
		int crosspoint=(int)(Math.random()*bitit);

		population[xnew][0]=0;
		int tempbitti=0;
		for(int chrom=1; chrom<population[x1].length; chrom++)
		{
			int x=1;
			population[xnew][chrom]=0;
			for(int b=0;b<bits[chrom-1];b++)
			{
				if(tempbitti<crosspoint) // TRUE => bitti 1. vanhemmasta
				{
					population[xnew][chrom]|=population[x1][chrom]&x;
				}
				else // Toisesta vanhemmasta
				{
					population[xnew][chrom]|=population[x2][chrom]&x;
				}
				tempbitti++;
				x<<=1;
			}
		}
	}

	public void twopointcrossover(int x1,int x2,int xnew)
	{
		// Lasketaan bittien määrä
		int bitit=0;
		for(int i=0; i<bits.length; i++)
		{
			bitit+=bits[i];
		}
		// Arvotaan 2 risteytyskohtaa
		int crosspoint1=(int)(Math.random()*bitit);
		int crosspoint2=(int)(Math.random()*bitit);

		population[xnew][0]=0;
		int tempbitti=0;
		for(int chrom=1; chrom<population[x1].length; chrom++)
		{
			int x=1;
			population[xnew][chrom]=0;
			for(int b=0;b<bits[chrom-1];b++)
			{
				if(tempbitti<crosspoint1 && tempbitti<crosspoint2) // TRUE => bitti 1. vanhemmasta
				{
					population[xnew][chrom]|=population[x1][chrom]&x;
				}
				else if(tempbitti>=crosspoint1 && tempbitti>=crosspoint2) // TRUE => bitti 1. vanhemmasta
				{
					population[xnew][chrom]|=population[x1][chrom]&x;
				}
				else // Toisesta vanhemmasta
				{
					population[xnew][chrom]|=population[x2][chrom]&x;
				}
				tempbitti++;
				x<<=1;
			}
		}
	}

	public void randomtrial(int xnew)
	{
		population[xnew][0]=0;
		for(int chrom=1; chrom<population[xnew].length; chrom++)
		{
			int x=1;
			population[xnew][chrom]=0;
			for(int b=0;b<bits[chrom-1];b++)
			{
				if(Math.random()>=0.5) // TRUE => bitti=1
				{
					population[xnew][chrom]|=x;
				}
				//else: bitti=0
				x<<=1;
			}
		}
	}

	/* Mutaatio biteittäin */
	public void mutation(int xnew)
	{
		for(int chrom=1; chrom<population[xnew].length; chrom++)
		{
			int x=1;
			for(int b=0;b<bits[chrom-1];b++)
			{
				if(Math.random()<mutationrate) // TRUE => mutaatio
				{
					population[xnew][chrom]^=x;
				}
			}
			//else: ei mutaatiota
			x<<=1;
		}
	}

	/** Järjestää yksilöt paremmuusjärjestykseen **/
	public void sort()
	{
		this.fitnesses();
		if(minimize)
		{
			if(noclones)
			{
				for(int i1=1;i1<population[0].length;i1++)
				{
					int max=(1<<bits[i1-1])-1;
					InsertionSort.killClones(population,i1,max);
				}
			}
			InsertionSort.sort(population,0); // Pienimmät ensin
		}
		else InsertionSort.sortDescending(population,0); // Suuret hyvyysarvot ensin
	}

	/** Laskee hyvyysarvot kaikille objekteille **/
	private void fitnesses()
	{
		for(int i2=0;i2<population.length;i2++)
		{
			population[i2][0]=fitnessf.fitness(population[i2]);
		}
	}

	/** Tulostaa koko populaation **/
	public void printPopulation()
	{
		System.out.println("Fitnesses and values on generation "+generation);
		for(int i2=0;i2<population.length;i2++)
		{
			System.out.print("Object "+i2+"\t Fitness="+population[i2][0]);
			for(int i1=1;i1<population[i2].length;i1++)
			{
				System.out.print("\tChromosome "+i1+"="+population[i2][i1]);
			}
			System.out.println();
		}
		System.out.println();
	}

	/** Tulostaa parhaan yksilön **/
	public void printBest()
	{
		System.out.println("Best fitness and value on generation "+generation);
		System.out.print("Fitness="+population[0][0]);
		for(int i1=1;i1<population[0].length;i1++)
		{
			System.out.print("\tChromosome "+i1+"="+population[0][i1]);
		}
		System.out.println();
	}

	/** Tulostaa parhaan yksilön **/
	public void printAllBest()
	{
		System.out.println("Values of all best fitness objects on generation "+generation);
		int tot=0;
		for(int i2=0;i2<elitism*population.length && population[i2][0]==stopfitness;i2++)
		{
			System.out.print("Object "+i2+"\t Fitness="+population[i2][0]);
			for(int i1=1;i1<population[i2].length;i1++)
			{
				System.out.print("\tChromosome "+i1+"="+population[i2][i1]);
			}
			tot++;
			System.out.println();
		}
		System.out.println("Totally: "+tot+" solutions!");
		solutions=tot;
	}

	public void printNumOfSolutions()
	{
		solutions=0;
		for(int i2=0;i2<elitism*population.length && population[i2][0]==stopfitness;i2++)
		{
			boolean apu=true; // kloonitarkistus. Ei varma, jos kloonit sallittuja
			for(int i1=1;i1<population[i2].length;i1++)
			{
				if(population[i2][i1]!=population[i2+1][i1])
				{
					apu=false;
				}
			}
			if(!apu)
			{
				solutions++;
			}
		}
		System.out.println("Generation: "+generation+" Solutions: "+solutions);
	}
}