import java.io.*;
import java.math.*;
import java.util.*;
import java.awt.*;
import java.awt.event.*;
import java.util.Scanner;

class individual{
	int parentNum=2,chromNum=100;
	int chrom[]=new int[chromNum];
	double fitness;
	double varible;
	int xsite;
	int parent[]=new int[parentNum];
	}
	
class bestever{
	int chromNum=100;
	int chrom[]=new int[chromNum];
	double fitness;
	double varible;
	int generation;
	}

class SGA{
	
	//Global
	double sumfitness;
	double max, avg, min;
    float pcross, pmutation;
    int popsize=5000,lchrom,chromsize,gen,maxgen;
	int printstrings; //* 輸出染色體編碼的判斷，0 -- 不輸出, 1 -- 輸出 */
    int nmutation; //* 當前代變異發(fā)生次數 */
    int ncross;
    /* 隨機數發(fā)生器使用的靜態(tài)變量 */
    double oldrand[]=new double[55];
    int jrand;
    double rndx2;
    int rndcalcflag; 
	String answer="";
	
	individual oldpop[]=new individual[popsize];        /* 當前代種群 */
	individual temp[]=new individual[popsize];          
	individual newpop[]=new individual[popsize];        /* 新一代種群 */
	bestever bestfit=new bestever();                    /* 最佳個體 */
	
    Scanner scanner=new Scanner(System.in);             //input scanner initialization
    
	
	public void preselect(){                                   //preselect function
		int j;
        sumfitness= 0;
        for(j=0;j<popsize;++j){
        	sumfitness += oldpop[j].fitness;
        	}
		}
		
	public int select(){        //* 輪盤賭選擇*///select function
		float sum, pick;
        int i;
        pick= randomperc();
        sum= 0;
        if (sumfitness!=0) {
        		for(i = 0; (sum < pick) && (i < popsize); ++i){
        			sum += (float)(oldpop[i].fitness/sumfitness);
        			}
        		}else{
        			i= rnd(1, popsize);
        			}
        return(i-1);
	    }
	    
	public int rnd(int low,int high){  //*在整數low和high之間產生一個隨機整數*///rnd function
		int i;
        if (low >= high){
        	i= low;
        	}else{
        		 i= (int)((randomperc()* (high - low + 1)) + low);
                 if (i > high){
                 	 i= high;
                 	 }
                 }
        return i;
		}
	    
	public float randomperc(){  //*與庫函數random()作用相同, 產生[0,1]之間一個隨機數 *///randomperc function
		jrand++;
        if (jrand >= 55){
        	jrand= 1;
        	advance_random();
        	}
        return((float)oldrand[jrand]);
		}
		
    public void advance_random(){               /* 產生55個隨機數 *///advance_random function
    	 int j1;
         double new_random;
         for(j1= 0;j1<24;++j1){
         	new_random= oldrand[j1] - oldrand[j1 + 31];
         	if (new_random < 0.0){
         		new_random= new_random + 1.0;
         		}
            oldrand[j1]= new_random;
            }
         for(j1= 24;j1<55;++j1){
         	new_random= oldrand[j1] - oldrand[j1 - 24];
         	if (new_random < 0.0){
         		new_random= new_random + 1.0;
         		}
    	    oldrand[j1]= new_random;
    	    }
    	    
    	}
    	
    public int crossover(int parent1[],int parent2[],int child1[],int child2[]){  //crossover function
    	int j, jcross, k;                               // * 由兩個父個體交叉產生兩個子個體 * /
        int mask, temp;
        if (flip(pcross)){
        	jcross= rnd(1, (lchrom - 1)); // * Cross between 1 and l - 1 * /
            ncross++;
            for(k= 1;k<=chromsize;++k){
            	if (jcross >= (k * 32)) {
            		child1[k - 1] = parent1[k - 1];
            		child2[k - 1] = parent2[k - 1];
            		}else if((jcross < (k * 32)) && (jcross > ((k - 1) * 32))){
            			mask = 1;
                        for(j = 1;j<= jcross - 1 - ((k - 1) * 32);++j){
                        	temp = 1;
                        	mask = mask << 1;
                        	mask = mask | temp;
                        	}
                        child1[k - 1] = (parent1[k - 1] & mask) | (parent2[k - 1] & (~mask));
                        child2[k - 1] = (parent1[k - 1] & (~ mask)) | (parent2[k - 1] &mask);
                        }else{
                        	child1[k - 1] = parent2[k - 1];
                        	child2[k - 1] = parent1[k - 1];
                        	}
                        	}
          }else{
          	for (k = 0;k<chromsize;++k){
          		child1[k] = parent1[k];
          		child2[k] = parent2[k];
          		}
            jcross= 0;
            }
         return jcross;
    	}
    	
    public boolean flip(float prob){                    // 以一定概率產生0或1 flip function
    	if (randomperc() <= prob){
    		return true;
    		}else{
    			return false;
    			}
    	}
    	
    public void mutation(int child[]){                 //mutation function//*變異操作*/
         int j, k, stop;
         int mask, temp;
         temp = 1;
         for (k = 0;k<chromsize;++k){
         	mask = 0;
         	if (k ==(chromsize - 1)){
         		stop = lchrom - (k * 32);
         		}else{
         			stop = 8 * 4;
         			}
            for (j = 0;j<stop;++j){
            	if (flip(pmutation)){
            		mask = mask | (temp << j);
            		nmutation++;
            		}
            		}
            child[k] = child[k] ^ mask;
            }
    	}
    	
    public void objfunc(individual critter){          //objfunc function//* 計算適應度函數值 */
    	int mask, bitpos, tp;
        double bitpow;
        int j, k, stop;
        mask = 1;
        critter.varible = 0.0;
        for (k = 0;k< chromsize;++k){
        	if (k == (chromsize - 1)){
        		stop = lchrom - (k * 32);
        	}else{
        		stop = 8 * 4;
        	}
        	tp = critter.chrom[k];
			for (j = 0;j<stop;++j){
				bitpos = j + (8 * 4) * k;
				if ((tp & mask) == 1){
					bitpow = Math.pow(2.0, (double)bitpos);
					critter.varible = critter.varible + bitpow;
				}
                tp = tp >> 1;
            }
            }
        critter.varible = -1 + critter.varible * 3 / (Math.pow(2.0, (double)lchrom) -1);
        critter.fitness= critter.varible * Math.sin(critter.varible * 10 * Math.atan(1)* 4) + 2.0;
        
    	}
	
	public void generation(){                                   //generation function
		int mate1, mate2, jcross, j=0;
		preselect();//*  每代運算前進行預選 */
		            
		do{              //* 選擇, 交叉, 變異 */
			
			mate1=select();
			mate2=select();
			jcross=crossover(oldpop[mate1].chrom, oldpop[mate2].chrom, newpop[j].chrom,
      newpop[j + 1].chrom);
            mutation(newpop[j].chrom);
            mutation(newpop[j + 1].chrom);
             //* 解碼, 計算適應度
            objfunc(newpop[j]);
              //*記錄親子關系和交叉位置 */
		    newpop[j].parent[0]= mate1 + 1;
		    newpop[j].xsite= jcross;
		    newpop[j].parent[1]= mate2 + 1;
		    objfunc(newpop[j + 1]);
		    newpop[j + 1].parent[0]= mate1 + 1;
		    newpop[j + 1].xsite= jcross;
		    newpop[j + 1].parent[1]= mate2 + 1;
		    j= j + 2;
            
			}while(j<(popsize-1));
			
		}
		
	public void statistics(individual pop[]){     //* 計算種群統(tǒng)計數據 *///statistics function
		  int i, j;
		  sumfitness = 0.0;
		  min = pop[0].fitness;
		  max = pop[0].fitness;
		    //* 計算最大、最小和累計適應度 */
		  for (j = 0;j<popsize;++j){
		  	sumfitness = sumfitness + pop[j].fitness;
		    if (pop[j].fitness > max){
		    	max = pop[j].fitness;
		    }
		    if (pop[j].fitness < min){
		    	min = pop[j].fitness;
		    }
		    // * new global best - fit individual * /
		    if (pop[j].fitness > bestfit.fitness){
		    	for (i = 0;i<chromsize;++i){
		    		bestfit.chrom[i] = pop[j].chrom[i];