#include<iostream.h>
#include<math.h>
#include<stdlib.h>

double function(double);
const int popsize=32, L=4,a=-1,b=2;
const double pm=0.02;

void initial(int[][L]);
void decode(int [][L],double []);
double binary_to_decimal(int[][L],int);
void fitness_sorting(double[],int[][L]);
void mutation(int [][L]);
void reproduction(int [][L]);

void main()
{
double x[popsize]={0.0},fx[popsize]={0.0};
int population[popsize][L]={0};
int count1=0,count2=0;

initial(population);

while(count2<10)
{
for(int i=0;i<popsize;i++)
fx[i]=function(x[i]);
double max=fx[0];
fitness_sorting(fx,population);

if(fx[0]<=max)count1++;
if(count1==10)
{
count2++;
count1=0;
mutation(population);
}
else reproduction(population);
decode(population,x);
}
cout<<"max="<<fx[0]<<endl;
cout<<"x="<<x[0]<<endl;
}


double function(double x)
{
return x*sin(10*3.14159265359*x)+1.0;
}

void initial(int population[popsize][L])
{
for(int i=0;i<popsize;i++)
for(int j=0;j<L;j++)
population[i][j]=rand()%2;
}

void decode(int population[popsize][L],double x[popsize])
{
for(int i=0;i<popsize;i++)
{
double temp=binary_to_decimal(population,i);
x[i]=a+temp*(b-a)/(pow(2,L)-1);
}
}

double binary_to_decimal(int population[popsize][L], int i)
{
double x=0.0;
for(int j=0;j<L;j++)
x=x+population[i][j]*pow(2,L-j-1);
return x;
}

void fitness_sorting(double fx[popsize],int population[popsize][L])
{
int order[popsize]={0};
for(int i=0;i<popsize;i++)
order[i]=i;
//inverse of bubble-sort fx[popsize] rearrange x[popsize]
for(int i=0;i<(popsize-1);i++)
for(int pos=popsize-1;pos>0;pos--)
if(fx[pos]>fx[pos-1])
{
double temp1=0.0;
int temp2=0;
temp1=fx[pos-1];
fx[pos-1]=fx[pos];
fx[pos]=temp1;

temp2=order[pos-1];
order[pos-1]=order[pos];
order[pos]=temp2;
}
//get the new population array according to the fitness
int temp[popsize][L]={0};
for(int i=0;i<popsize;i++)
//temp[i]=old population[order[i]]
for(int j=0;j<L;j++)
temp[i][j]=population[order[i]][j];
//new population=temp
for(int i=0;i<popsize;i++)
for(int j=0;j<L;j++)
population[i][j]=temp[i][j];
}

void reproduction(int population[popsize][L])
{
//simply choose the first half population array
//which is fitter than second half;Two parents geneate
//two children by using single point crossover,
//store the children into the second half population array;
for(int i=0;i<(popsize/2-1);i=i+2)
{
int nc=(rand()%100)/100*(L-1);
for(int j=0;j<nc;j++)
{
population[popsize/2+i][j]=population[i][j];
population[popsize/2+i+1][j]=population[i+1][j];
}
for(int j=nc;j<(L-1);j++)
{
population[popsize/2+i][j]=population[i+1][j];
population[popsize/2+i+1][j]=population[i][j];
}
}
}

void mutation(int population[popsize][L])//(1/4~1/2);
{
int mutation_gene=popsize*L*pm;
for(int i=0;i<mutation_gene;i++)
{
if(population[(1+i*2)%(popsize/2)][rand()%L]==0)
population[(1+i*2)%(popsize/2)][rand()%L]=1;
else population[(1+i*2)%(popsize/2)][rand()%L]=0;
}
}