public class AHMA {
  int length=100;// chromosome string length
  static int popsize;// population size
  double add_rat=0.2;//total additional cost ratio via evaluation
  double ls_rat,im_rat=add_rat/2;// addition evaluation cost ratio by local search and immigrant
  int ls_num,im_num;// addition evaluation by local search and immigrant
  int max_gen;// maximal allowable generation of each environment
  double pc=0.5,pm=0.01;// probablity of crossover and mutation
  int mut_num,mut_max=5,mut_min=1;// parameters in SMHC operator
  double lpc,lpc_max=pc,lpc_min=0.01;// parameters in GCHC operator
  Chromosome[] old_pop,new_pop,tem_pop;
  // parent population, child population and selection pool
  Chromosome good_chr,best_chr,elite_chr;
  // best chromosome each generation, best chromosome so far, elite chromosome for ls
  double[] sle_arr,best_val;
  // wheel selection array, best fitness each generation
  double cosa=0,alpha=1,delta=1,lamda=0.1;
  double pro_mls=0.5,pro_cls=0.5;

  public AHMA(int max_gen,int popsize){
    this.max_gen=max_gen;
    this.popsize=popsize;
    good_chr=new Chromosome();
    best_chr=new Chromosome();
    best_val=new double[max_gen];
  }
  // generate a random seed
  int[] randomSeed(){
    int[] seed0=new int[length];
    for(int i=0;i<seed0.length;i++){
      if(Math.random()<0.5){
        seed0[i]=0;
      }
      else{
        seed0[i]=1;
      }
    }
    return seed0;
  }
  //generate a random seed array
  int[][] randomSeed(int n){
    int[][] seed0=new int[n][length];
    for(int i=0;i<seed0.length;i++){
      seed0[i]=randomSeed();
    }
    return seed0;
  }

  public static void main(String args[]){
    AHMA ahma;
    double mean_val=0,s=0.9;
    int run=1,gen=100,popsize=100;
    int change=10;
    double[] result=new double[gen*change];
    double[] result1=new double[gen*change];
    for(int i=0;i<result.length;i++){
      result[i]=0;result1[i]=0;
    }
    int[] change_arr=new int[100];
    for(int r=0;r<run;r++){
      ahma=new AHMA(gen,popsize);
      System.out.println("run is "+r);
      int[][] initial_seed=ahma.randomSeed(popsize);
      ahma.run(initial_seed);
      for(int i=0;i<gen;i++){
        if(i==0){
          result[i]=ahma.best_val[i];
        }
        else{
          result[i]=(result[i-1]*i+ahma.best_val[i])/(i+1);
        }
      }
      for(int ca=1;ca<change;ca++){
        change_arr=ahma.getChangeArray(s);
        ahma.changeEnvironment(change_arr);
        ahma.runDynamic();
        for(int i=0;i<gen;i++){
          if(i==0){
             result[ca*gen+i]=ahma.best_val[i];
          }
          else{
            result[ca*gen+i]=(result[ca*gen+i-1]*i+ahma.best_val[i])/(i+1);
          }
        }
      }
      for(int i=0;i<change*gen;i++){
        result1[i]+=result[i];
      }
    }
    for(int i=0;i<result.length;i++){
      System.out.println(result1[i]/run);
    }
  }

  //create a initial population old_pop where each chromsome is evaluated
  //and find the best fitness chromosome in old_pop
  void initilization(int[][] seed){
    old_pop=new Chromosome[popsize];
    new_pop=new Chromosome[popsize];
    tem_pop=new Chromosome[2*popsize];
    for(int i=0;i<old_pop.length;i++){
      old_pop[i]=new Chromosome(seed[i]);
      new_pop[i]=new Chromosome();
      tem_pop[i]=new Chromosome();
      tem_pop[popsize+i]=new Chromosome();
      old_pop[i].evaluate();
    }
    sort(old_pop);
    dualMapping(old_pop[0]);
    cosa=calPopIndex(old_pop);
    if(cosa<lamda){
      ls_rat=add_rat-im_rat;
      adaptiveHillClimbing(old_pop[0],old_pop);
      randomImmigrant(old_pop,im_rat);
    }
    else{
      ls_rat=add_rat;
      adaptiveHillClimbing(old_pop[0],old_pop);
    }
    good_chr=getGoodChr(old_pop);
    copyChr(good_chr,best_chr);
    best_val[0]=best_chr.fitness;
  }

  double calPopIndex(Chromosome[] pop){
    double val1,val2;
    val1=pop[0].fitness;
    val2=pop[0].fitness;
    for(int i=1;i<pop.length;i++){
      if(val1<pop[i].fitness){
        val1=pop[i].fitness;
      }
      val2+=pop[i].fitness;
    }
    return (val1-val2/pop.length)/val1;
  }

  //find a best fitness chromosome from chrArr
  Chromosome getGoodChr(Chromosome[] pop){
    Chromosome tem_chr=new Chromosome();
    copyChr(pop[0],tem_chr);
    for(int i=1;i<pop.length;i++){
      if(tem_chr.fitness<pop[i].fitness) copyChr(pop[i],tem_chr);
    }
    return tem_chr;
  }

  //copy c1 to c2
  void copyChr(Chromosome c1,Chromosome c2){
    for(int i=0;i<c1.coding.length;i++)  c2.coding[i]=c1.coding[i];
    c2.fitness=c1.fitness;
  }

  //calculate a route wheel choosen array
  void calSelArr(Chromosome[] pop){
    double sumVal=0;
    for(int i=0;i<pop.length;i++){
      sumVal+=pop[i].fitness;
    }
    sle_arr=new double[pop.length+1];
    sle_arr[0]=0;
    for(int i=0;i<pop.length;i++){
      sle_arr[i+1]=sle_arr[i]+pop[i].fitness/sumVal;
    }
  }

  //the crossover between two parent chromosmes to achieve one child chromosome
  void uniformCrossChr(Chromosome par1,Chromosome par2,Chromosome chi1,Chromosome chi2){
    for(int i=0;i<par1.coding.length;i++){
      if(Math.random()<pc){
        chi1.coding[i]=par2.coding[i];
        chi2.coding[i]=par1.coding[i];
      }
      else{
        chi1.coding[i]=par1.coding[i];
        chi2.coding[i]=par2.coding[i];
      }
    }
  }

  void uniformCrossChr(Chromosome par1,Chromosome par2,Chromosome chi,double pc){
    for(int i=0;i<par1.coding.length;i++){
      if(Math.random()<pc){
        chi.coding[i]=par2.coding[i];
      }
      else{
        chi.coding[i]=par1.coding[i];
      }
    }
  }

  //sort the order of population via the fitness from large to little
  void sort(Chromosome pop[]){
    Chromosome temp_pop=new Chromosome();
    int k=0,j=0;
    for(int i=0;i<pop.length-1;i++){
      k=i;
      for(j=i+1;j<pop.length;j++)
        if(pop[j].fitness>pop[k].fitness) k=j;
      copyChr(pop[i],temp_pop);
      copyChr(pop[k],pop[i]);
      copyChr(temp_pop,pop[k]);
    }
  }

  //select a chromosome from the population via the route wheel selection array
  int selectChr(){
    int seleItem=0;
    double tem=Math.random();
    for(int i=0;i<sle_arr.length-1;i++){
      if(tem>=sle_arr[i]&&tem<sle_arr[i+1])  seleItem=i;
    }
    return seleItem;
  }
  int randomSelectChr(Chromosome[] pop){
    return (int)(pop.length*Math.random());
  }

  //mutate a chromosome
  void mutateChr(Chromosome chr){
    for(int i=0;i<length;i++){
      if(Math.random()<pm){
        chr.coding[i]=Math.abs(chr.coding[i]-1);
      }
    }
  }

  // execute dual mapping operation to chr
  void dualMapping(Chromosome chr){
    Chromosome dual_chr=new Chromosome();
    for(int i=0;i<chr.coding.length;i++){
      dual_chr.coding[i]=1-chr.coding[i];
    }
    dual_chr.evaluate();
    if(dual_chr.fitness>chr.fitness){
      copyChr(dual_chr,chr);
    }
  }

  // execute adaptive hill climbing ls operation to chr
  void adaptiveHillClimbing(Chromosome chr,Chromosome[] pop){
    ls_num=(int)(popsize*ls_rat)-1;
    int imp_num=0;
    calSelArr(pop);
    lpc=alpha*cosa*(lpc_max-lpc_min)+lpc_min;
    if(lpc>lpc_max) lpc=lpc_max;
    mut_num=(int)(mut_min+alpha*cosa*(mut_max-mut_min));
    if(mut_num>mut_max) mut_num=mut_max;
    double award_mls=0,award_cls=0;
    Chromosome tem_chr=new Chromosome();
    for(int i=0;i<ls_num;i++){
      if(Math.random()<pro_cls){
        uniformCrossChr(chr,pop[selectChr()],tem_chr,lpc);
        tem_chr.evaluate();
        if(tem_chr.fitness>chr.fitness){
          award_cls+=tem_chr.fitness-chr.fitness;
          copyChr(tem_chr,chr);
          imp_num++;
        }
      }
      else{
        for(int j=0;j<mut_num;j++){
          int bit=(int)(length*Math.random());
          for(int k=0;k<length;k++){
            if(k==bit){
              tem_chr.coding[k]=Math.abs(1-chr.coding[k]);
            }
            else{
              tem_chr.coding[k]=chr.coding[k];
            }
          }
        }
        tem_chr.evaluate();
        if(tem_chr.fitness>chr.fitness){
          award_mls+=tem_chr.fitness-chr.fitness;
          copyChr(tem_chr,chr);
          imp_num++;
        }
      }
    }
    pro_cls=pro_cls+delta*award_cls/100;
    pro_mls=pro_mls+delta*award_mls/100;
    pro_cls=pro_cls/(pro_cls+pro_mls);
    pro_mls=pro_mls/(pro_cls+pro_mls);
  }

  // generate random immigrant into pop
  void randomImmigrant(Chromosome[] pop,double rat){
    int num=(int)(popsize*rat);
    Chromosome chr;
    for(int i=0;i<num;i++){
      chr=new Chromosome();
      chr.evaluate();
      copyChr(chr,pop[pop.length-1-i]);
    }
  }

  //the stationary course of SGA running
  void run(int[][] seed){
    initilization(seed);
    for(int ng=1;ng<max_gen;ng++){
      calSelArr(old_pop);
      for(int i=0;i<new_pop.length;i+=2){
        uniformCrossChr(old_pop[selectChr()],old_pop[selectChr()],
                        new_pop[i],new_pop[i+1]);
        mutateChr(new_pop[i]);new_pop[i].evaluate();
        mutateChr(new_pop[i+1]);new_pop[i+1].evaluate();
      }
      for(int i=0;i<tem_pop.length;i++){
        if(i<old_pop.length){
          copyChr(old_pop[i],tem_pop[i]);
        }
        else{
          copyChr(new_pop[i-old_pop.length],tem_pop[i]);
        }
      }
      sort(tem_pop);
      for(int i=0;i<old_pop.length;i++){
        copyChr(tem_pop[i],old_pop[i]);
      }
      dualMapping(old_pop[0]);
      cosa=calPopIndex(old_pop);
      if(cosa<lamda){
        ls_rat=add_rat-im_rat;
        adaptiveHillClimbing(old_pop[0],old_pop);
        randomImmigrant(old_pop,im_rat);
      }
      else{
        ls_rat=add_rat;
        adaptiveHillClimbing(old_pop[0],old_pop);
      }
      good_chr=getGoodChr(old_pop);
      if(good_chr.fitness>best_chr.fitness){
        copyChr(good_chr,best_chr);
      }
      best_val[ng]=best_chr.fitness;
    }
  }

  //the dynamic period of SGA running
  void runDynamic(){
    for(int i=0;i<old_pop.length;i++){
      old_pop[i].evaluate();
    }
    dualMapping(old_pop[0]);
    sort(old_pop);
    cosa=calPopIndex(old_pop);
    if(cosa<lamda){
      ls_rat=add_rat-im_rat;
      adaptiveHillClimbing(old_pop[0],old_pop);
      randomImmigrant(old_pop,im_rat);
    }
    else{
      ls_rat=add_rat;
      adaptiveHillClimbing(old_pop[0],old_pop);
    }
    good_chr=getGoodChr(old_pop);
    copyChr(good_chr,best_chr);
    best_val[0]=best_chr.fitness;
    for(int ng=1;ng<max_gen;ng++){
      calSelArr(old_pop);
      for(int i=0;i<new_pop.length;i+=2){
        uniformCrossChr(old_pop[selectChr()],old_pop[selectChr()],
                        new_pop[i],new_pop[i+1]);
        mutateChr(new_pop[i]);new_pop[i].evaluate();
        mutateChr(new_pop[i+1]);new_pop[i+1].evaluate();
      }
      for(int i=0;i<tem_pop.length;i++){
        if(i<old_pop.length){
          copyChr(old_pop[i],tem_pop[i]);
        }
        else{
          copyChr(new_pop[i-old_pop.length],tem_pop[i]);
        }
      }
      sort(tem_pop);
      for(int i=0;i<old_pop.length;i++){
        copyChr(tem_pop[i],old_pop[i]);
      }
      cosa=calPopIndex(old_pop);
      if(cosa<lamda){
        ls_rat=add_rat-im_rat;
        adaptiveHillClimbing(old_pop[0],old_pop);
        randomImmigrant(old_pop,im_rat);
      }
      else{
        ls_rat=add_rat;
        adaptiveHillClimbing(old_pop[0],old_pop);
      }
      good_chr=getGoodChr(old_pop);
      if(good_chr.fitness>best_chr.fitness){
        copyChr(good_chr,best_chr);
      }
      best_val[ng]=best_chr.fitness;
    }
  }

  //the environment is changed with the severity s
  int[] getChangeArray(double s){
    int[] result=new int[length];
    int num=(int)(s*length),val;
    for(int i=0;i<length;i++){
      if(i<num){
        result[i]=1;
      }
      else{
        result[i]=0;
      }
    }
    for(int i=0;i<length/2;i++){
      int j,k;
      while(true){
        j=(int)(length*Math.random());
        k=(int)(length*Math.random());
        if(j!=k){
          break;
        }
      }
      val=result[j];result[j]=result[k];result[k]=val;
    }
    return result;
  }

  void changeEnvironment(int[] arr){
    for(int i=0;i<old_pop.length;i++){
      for(int j=0;j<old_pop[i].coding.length;j++){
        old_pop[i].coding[j]=Math.abs(old_pop[i].coding[j]-arr[j]);
      }
    }
  }

  int[] getBitArray(int len){
    int[] arr=new int[len];
    int val;
    for(int i=0;i<arr.length;i++){
      arr[i]=i;
    }
    for(int i=0;i<len/2;i++){
      int j,k;
      while(true){
        j=(int)(len*Math.random());
        k=(int)(len*Math.random());
        if(j!=k){
          break;
        }
      }
      val=arr[j];arr[j]=arr[k];arr[k]=val;
    }
    return arr;
  }

  //one-max function
  int oneMaxFun(int[] arr){
    int val=0;
    for(int i=0;i<arr.length;i++){
      val+=arr[i];
    }
    return val;
  }

  //royal road function
  int royalRoadFun(int a,int b,int c,int d){
    int sum=a+b+c+d;
    if(sum==4){
      return 4;
    }
    else{
      return 0;
    }
  }
  int royalRoadFun(int[] arr){
    int val=0,block=4;
    for(int i=0;i<arr.length/block;i++){
      val+=royalRoadFun(arr[block*i],arr[block*i+1],arr[block*i+2],arr[block*i+3]);
    }
    return val;
  }
  int plateauFun(int a,int b,int c,int d){
    int sum=a+b+c+d;
    if(sum==4){
      return 4;
    }
    else if(sum==3){
      return 2;
    }
    else{
      return 0;
    }
  }
  // plateau function
  int plateauFun(int[] arr){
    int val=0;
    for(int i=0;i<arr.length/4;i++){
      val+=plateauFun(arr[4*i],arr[4*i+1],arr[4*i+2],arr[4*i+3]);
    }
    return val;
  }

  //deceptive function
  int deceptiveFun(int a,int b,int c,int d){
    int sum=a+b+c+d;
    if(sum==0){
      return 3;
    }
    else if(sum==1){
        return 2;
    }
    else if(sum==2){
        return 1;
    }
    else if(sum==3){
        return 0;
    }
    else{
        return 4;
    }
  }
  int deceptiveFun(int[] arr){
    int val=0;
    for(int i=0;i<arr.length/4;i++){
      val+=deceptiveFun(arr[4*i],arr[4*i+1],arr[4*i+2],arr[4*i+3]);
    }
    return val;
  }

  //a class for contruct a chromosome
  class Chromosome{
    int[] coding=new int[length];
    double fitness=0;
    Chromosome(){
      for(int i=0;i<coding.length;i++){
        if(Math.random()<0.5)  coding[i]=0;
        else coding[i]=1;
      }
    }

    Chromosome(int[] chr){
      for(int i=0;i<coding.length;i++) {
        coding[i]=chr[i];
      }
    }

    void evaluate(){
      fitness=oneMaxFun(coding);
      //fitness=plateauFun(coding);
      //fitness=royalRoadFun(coding);
      //fitness=deceptiveFun(coding);
    }

    void print(){
      for(int i=0;i<length;i++){
        System.out.print(coding[i]+" ");
      }
      System.out.println("  the fitness is "+fitness);
    }
  }
}