//用glp法生成初始种群
//编码方式为实数编码
//选择方法为随机遍历
//采用了精英保存策略
//采用了自适应的交叉率和变异率
//采用了与模拟退火算法相结合的尺度变换
//程序可自动计算个体间的海明距离，然后根据结果进行最佳配对
//采用了最大信息保留的交叉算法

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <iostream.h>
#include <iomanip.h>
#include <time.h>
#include <windows.h>
#define IM1 2147483563
#define IM2 2147483399
#define AM (1.0/IM1)
#define IMM1 (IM1-1)
#define IA1 40014
#define IA2 40692
#define IQ1 53668
#define IQ2 52774
#define IR1 12211
#define IR2 3791
#define NTAB 32
#define NDIV (1+IMM1/NTAB)
#define EPS 1.2e-7
#define RNMX (1.0-EPS)
#define zhizhenjuli 0.005
#define PI 3.14159265358
#define T0 10000//温度要取得很高才行。
#define zhongqunshu1 200
#define zuobianjie -1000
#define youbianjie 1000
#define lanmuteshuliang 5
unsigned int seed=0; //seed 为种子，要设为全局变量
void mysrand(long int i) //初始化种子
{
seed = -i;
}
long a[1];
double hundun;
double c=3.95;
//设置全局变量
struct individual
{
 double *chrom;  //染色体；
 double geti;//变量值
 double shiyingdu; //目标函数的值；
 double fitness;   //变换后的适应度值；
};
struct haiming
{
 int bianhao;//编号
 double geti;
 int haimingchazhi;//海明差值
};
struct youxuan//确定交叉后的优选个体
{
 double geti;
 double shiyingdu;
};
double fangcha;   //目标函数值的方差
individual *zuiyougeti;//精英保存策略
double zuidafangcha;//到本代为止最优方差
int zhongqunshu;   //种群大小
individual *nowpop;//当前代
individual *newpop;//新一代
double sumfitness;//当代的总适应度fitness
double sumshiyingdu;//当代的总适应度shiyingdu
double maxfitness;//最大适应度
double avefitness;//平均适应度
double maxshiyingdu;//最大适应度
double aveshiyingdu;//平均适应度
float pc;//交叉概率
float pm;//变异概率
int lchrom;//染色体长度
int maxgen;//最大遗传代数
int gen;//遗传代数
//函数
int flipc(double ,double );//判断是否交叉
int flipm(double );//判断是否变异
int rnd(int low,int high);//产生low与high之间的任意数
void initialize();//遗传算法初始化
void preselectfitness(); //计算sumfiness,avefitness,maxfitness
void generation();
double suijibianli();//产生随机遍历指针
int fuzhi(float );//选择要复制的个体
void crossover(individual ,individual ,individual &,individual &);//交叉
void bianyi(individual &);//变异
void mubiaohanshu(individual &);//计算适应度
void chidubianhuan(individual &);//对shiyingdu进行尺度变换赋给fitness
double ran1(long *);//随机数初始
double gasdev(long *idum);//高斯随机数
void bianma(double bianliang,unsigned *p);//编码
double yima(unsigned *p);
void guanjiancanshujisuan();//计算shiyingdu,根据shiyingdu计算sumshiyingdu,对shiyingdu进行尺度变换变成fitness,根据fitness计算sumfitness，avefitness，maxfitness
void jingyingbaoliu();//精英保存的实现
void zuidafangchabaoliu();//最大方差值的保存
void glp(int n,int s,int *,int (*)[1],float (*)[1]);//glp生成函数
double hundunsuiji();
int haimingchazhijisuan(double,double);//计算个体的海明值
BOOL Exist(int Val, int Num, int *Array);//判断一个数在前面是否出现过
int cmpfitness(const void *p1,const void *p2)
{
 float i=((individual *)p1)->shiyingdu;//现在是按照"适应度"排序，改成"个体"的话就是按照"个体"排序
 float j=((individual *)p2)->shiyingdu;
 return i<j ? -1:(i==j ? 0:1);//现在是按升序牌排列，将1和-1互换后就是按降序排列
}
int cmpshiyingdu(const void *p1,const void *p2)
{
 float i=((individual *)p1)->shiyingdu;//现在是按照"个体"排序
 float j=((individual *)p2)->shiyingdu;
 return i<j ? -1:(i==j ? 0:1);//现在是按升序牌排列，将1和-1互换后就是按降序排列
}
int cmpshiyingdujiang(const void *p1,const void *p2)
{
 float i=((youxuan *)p1)->shiyingdu;
 float j=((youxuan *)p2)->shiyingdu;
 return i<j ? 1:(i==j ? 0:-1);//现在是按降序牌排列，将1和-1互换后就是按升序排列
}
int cmpgeti(const void *p1,const void *p2)
{
 float i=((individual *)p1)->geti;//现在是按照"个体值"排序
 float j=((individual *)p2)->geti;
 return i<j ? -1:(i==j ? 0:1);//现在是按升序牌排列，将1和-1互换后就是按降序排列
}
int cmphaimingchazhi(const void *p1,const void *p2)
{
 float i=((haiming *)p1)->haimingchazhi;//现在是按照"适应度"排序，改成"个体"的话就是按照"个体"排序
 float j=((haiming *)p2)->haimingchazhi;
 return i<j ? 1:(i==j ? 0:-1);//现在是按降序牌排列，将-1和1互换后就是按升排列
}
int cmp1(const void *p1,const void *p2)
{
 int i= *(int*)p1;
 int j= *(int*)p2;
 return i<j ? 1:(i==j ? 0:-1);//现在是按降序牌排列，将1和-1互换后就是按升序排列
}
void main()
{
 initialize();
 //cout<<zuiyougeti->geti<<" "<<-zuiyougeti->shiyingdu<<endl;/////////////
 for(gen=1;gen<maxgen;gen++)
 { generation();
 }
  jingyingbaoliu();
 cout<<setiosflags(ios::fixed)<<setprecision(6)<<"最小的n为"<<" "<<setiosflags(ios::fixed)<<setprecision(9)<<(-zuiyougeti->shiyingdu)<<endl;////////////////
 delete [] newpop;
 delete [] nowpop;
 delete [] zuiyougeti;
 system("pause");
}
void initialize()
{
 hundun=ran1(a);
 while(hundun==0||hundun==0.25||hundun==0.75||hundun==1)
 {
  hundun=ran1(a);
 }
 int q[zhongqunshu1][1],s=1;
 float xx[zhongqunshu1][1];//生成的glp用x储存
 int h[1]={1};//生成向量
 zuiyougeti=new individual;//最优个体的生成
 zhongqunshu=200;//种群数量
 nowpop=new individual[zhongqunshu1];//当代
 newpop=new individual[zhongqunshu1];//新一代
 maxgen=15;//最大代数
 gen=0;//起始代
 lchrom=22;//基因数量的初始化
 mysrand(time(0));//随机数种子
    a[0]=seed;//随机数种子
 //对最优个体的初始化
  zuiyougeti->geti=0;
       zuiyougeti->fitness=0;
     zuiyougeti->shiyingdu=-6.67e+66;
  zuidafangcha=0;
    glp(zhongqunshu,s,h,q,xx);
// for(int i=0;i<zhongqunshu1;i++)//产生初始种群
// {
//  for(int j=0;j<s;j++)
//  {
//   nowpop[i].geti=zuobianjie+(youbianjie-(zuobianjie))*xx[i][j];
//  }
// }
   for(int i=0;i<zhongqunshu1;i++)//产生初始种群
   {
    nowpop[i].geti=zuobianjie+(youbianjie-(zuobianjie))*ran1(a);
   }
 //nowpop[0].geti=999;//////////////////////////
 guanjiancanshujisuan();
 zuidafangchabaoliu();//最大方差值的保存
 jingyingbaoliu(); //精英保留的实现
 guanjiancanshujisuan();//计算shiyingdu,根据shiyingdu计算sumshiyingdu,对shiyingdu进行尺度变换变成fitness,根据fitness计算sumfitness，avefitness，maxfitness
 zuidafangchabaoliu();//最大方差值的保存
}
void jingyingbaoliu() //精英保留的实现
{
 individual *zuiyougetiguodu;
 zuiyougetiguodu=new individual[zhongqunshu1];//建立一个过渡数组
 for(int i=0;i<zhongqunshu;i++)//将当代个体复制到过渡数组中
  zuiyougetiguodu[i]=nowpop[i];
 qsort(zuiyougetiguodu,zhongqunshu1,sizeof(individual),&cmpfitness);//按fitness升序排序
      // cout<<"zuiyougetiguodu适应度:"<<zuiyougetiguodu[zhongqunshu1-1].shiyingdu<<endl;///////////
 // cout<<"zuiyougeti适应度:"<<zuiyougeti->shiyingdu<<endl;///////////////////
  //system("pause");
  if(zuiyougetiguodu[zhongqunshu-1].shiyingdu>zuiyougeti->shiyingdu)
  {
   *zuiyougeti=zuiyougetiguodu[zhongqunshu1-1];//如果最优个体的fitness比当代最大的fitness小则用当代的代替之
  //cout<<"zuiyougetiguodu个体:"<<zuiyougetiguodu[zhongqunshu1-1].geti<<endl;/////////////
  //cout<<"zuiyougeti个体:"<<zuiyougeti->geti<<endl;/////////////
  }
  else
   nowpop[rnd(0,(zhongqunshu1-1))]=*zuiyougeti;//否则的话从当代中随机挑选一个用最优个体代替之
  delete [] zuiyougetiguodu;//释放过渡数组
}
void zuidafangchabaoliu()//最大方差值的保存
{
 if(fangcha>zuidafangcha)
  zuidafangcha=fangcha;
}

void guanjiancanshujisuan()//计算shiyingdu,根据shiyingdu计算sumshiyingdu,对shiyingdu进行尺度变换变成fitness,根据fitness计算sumfitness，avefitness，maxfitness
{
 for(int i=0;i<zhongqunshu;i++)//计算shiyingdu
  mubiaohanshu(nowpop[i]);
 sumshiyingdu=0;
 for(i=0;i<zhongqunshu;i++)
  sumshiyingdu=sumshiyingdu+nowpop[i].shiyingdu;
 aveshiyingdu=sumshiyingdu/zhongqunshu;
 fangcha=0;
 for(i=0;i<zhongqunshu;i++)//求方差
  fangcha+=pow((nowpop[i].shiyingdu-aveshiyingdu),2)/zhongqunshu;
 for(i=0;i<zhongqunshu;i++)//对shiyingdu进行尺度变换变成fitness
  chidubianhuan(nowpop[i]);
 preselectfitness();//根据fitness计算sumfitness，avefitness，maxfitness
}
void mubiaohanshu(individual &bianliang)//计算shiyingdu
{
 double ping_fang,cheng_fang;
 ping_fang=100*pow(bianliang.geti,2);
 cheng_fang=pow(2,bianliang.geti);
 if(ping_fang<cheng_fang)
  bianliang.shiyingdu=-bianliang.geti;
}
void chidubianhuan(individual &bianliang)//对shiyingdu进行尺度变换变成fitness
{
 double T;//退火温度
 T=T0*(pow(0.99,(gen+1-1)));
 double sum=0;
    for(int j=0;j<zhongqunshu;j++)
  sum+=exp(nowpop[j].shiyingdu/T);
 bianliang.fitness=exp(bianliang.shiyingdu/T)/sum;//算出fitness
}
void preselectfitness()//根据fitness计算sumfitness，avefitness，maxfitness
{
 int j;
 sumfitness=0;
 for(j=0;j<zhongqunshu;j++)
  sumfitness+=nowpop[j].fitness;
 individual *guodu;
 guodu=new individual[zhongqunshu1];
 for(j=0;j<zhongqunshu;j++)
  guodu[j]=nowpop[j];
 qsort(guodu,zhongqunshu1,sizeof(individual),&cmpfitness);
 maxfitness=guodu[zhongqunshu1-1].fitness;
 avefitness=sumfitness/zhongqunshu1;
 delete [] guodu;
}
void generation()
{
 individual fuqin1,fuqin2,*pipeiguodu,*pipeichi;
 int *peiduishuzu;//用来存放产生的随机配对
 pipeiguodu=new individual[zhongqunshu1];
 pipeichi=new individual[zhongqunshu1];
 peiduishuzu=new int[zhongqunshu1];
 haiming *haimingrongqi;
 haimingrongqi=new haiming[zhongqunshu1];
 int member1,member2,j=0,fuzhijishu=0,i=0,temp=0,tt=0;
 float zhizhen;
 //随机遍历的实现
 for(zhizhen=suijibianli();zhizhen<1;(zhizhen=zhizhen+zhizhenjuli))//设定指针1/66
 {
  pipeichi[fuzhijishu]=nowpop[fuzhi(zhizhen)];
  fuzhijishu++;//复制计数
 }
// for(int iii=0;iii<10;iii++)
// {
//  if(pipeichi[iii].geti<zuobianjie||pipeichi[iii].geti>youbianjie)
//  cout<<pipeichi[iii].geti<<" ";///////////
// }
// cout<<endl;////////////////
   // system("pause");//////////////////////////
 //交叉与变异的实现
 //交叉
    for(i=0;i<zhongqunshu1;i++)
 {
  peiduishuzu[i]=-1;
 }
 
 for(i=0;i<zhongqunshu1;i++)
 {
  haimingrongqi[i].geti=pipeichi[i].geti;
 }
 //cout<<haimingrongqi[1].geti<<endl;//////////////
 //system("pause");//////////////////////////
 double rou;//进化因子
 double avehai=0;//平均海明值
 int sumchahainei=0;//单个个体和其他个体海明距离和
 int sumchahaiwai=0;//总的海明距离和
 int jisuancishu=0;//求海明和的次数
 for(int ii=0;ii<zhongqunshu1-1;ii++)
 {
  sumchahainei=0;
        //cout<<"ii的值:"<<haimingrongqi[ii].geti<<endl;//////////
  for(int jj=ii+1;jj<zhongqunshu1;jj++)
  {
   //cout<<"jj的值:"<<haimingrongqi[jj].geti<<endl;//////////
   //system("pause");//////////////////////////
   sumchahainei=sumchahainei+haimingchazhijisuan(haimingrongqi[ii].geti,haimingrongqi[jj].geti);
  }
  sumchahaiwai=sumchahaiwai+sumchahainei;
 }
 //cout<<"平均海明差:"<<sumchahaiwai<<endl;////////////////////////////
 //system("pause");///////////////
// cout<<endl;
 for(ii=1;ii<=zhongqunshu1-1;ii++)
 {
  jisuancishu=jisuancishu+(zhongqunshu1-ii);
 }
//  cout<<jisuancishu<<endl;////////////////////////////
// system("pause");///////////////
// cout<<endl;
 rou=exp(-pow(gen,2)/(2*pow(maxgen/3,2)));
 avehai=(double)(rou*sumchahaiwai/jisuancishu);
// cout<<rou<<" "<<avehai<<" "<<jisuancishu<<" "<<sumchahaiwai<<endl;////////////////////////////
  // system("pause");///////////////
 for (i=0; i<zhongqunshu1; i++)
 {
  temp =rnd(0,zhongqunshu1-1); //产生值在0-zhongqunshu1-1的随机数
   while(Exist(temp, i, peiduishuzu))//判断产生的随机数是否已经产生过，如果是，则再产生一个随机数
   {
    temp =rnd(0,zhongqunshu1-1);
   }
   //如果没有的话，则把产生的随机数放在peiduishuzu中
    *(peiduishuzu+i) = temp;
   // cout<<temp<<endl;/////////////////////////
    int t=zhongqunshu1;
       j=0;
    while(Exist(j,i,peiduishuzu)||haimingchazhijisuan(haimingrongqi[temp].geti,haimingrongqi[j].geti)<avehai)
    {
     //cout<<"编号:"<<j<<"海明差值内:"<<haimingchazhijisuan(haimingrongqi[temp].geti,haimingrongqi[j].geti)<<" "<<"是否存在:"<<Exist(j,i,peiduishuzu)<<endl;//////
     // system("pause");//////////////
     j=j+1;
     t--;
     if(t<1)
      break;
    }
   // if(t>=1)
   // cout<<"编号:"<<j<<"海明差值外:"<<haimingchazhijisuan(haimingrongqi[temp].geti,haimingrongqi[j].geti)<<" "<<"是否存在:"<<Exist(j,i,peiduishuzu)<<endl;//////
     // system("pause");//////////////
   // cout<<j<<" "<<t<<endl;///////////
   // system("pause");/////
    if(t>=1)
    {
     i=i+1;
     *(peiduishuzu+i)=j;
    }
    else
    {
     haiming *haimingchazhirongqi;
     haimingchazhirongqi=new haiming[zhongqunshu1];
     for(j=0;j<zhongqunshu1;j++)
     {
      haimingchazhirongqi[j].haimingchazhi=haimingchazhijisuan(haimingrongqi[temp].geti,haimingrongqi[j].geti);
      haimingchazhirongqi[j].bianhao=j;
     }
     qsort(haimingchazhirongqi,zhongqunshu1,sizeof(haiming),&cmphaimingchazhi);
     int m=0;
     while(Exist(haimingchazhirongqi[m].bianhao,i,peiduishuzu)||haimingchazhirongqi[m].bianhao==temp)
     {
      m=m+1;
     }
     i=i+1;
     *(peiduishuzu+i)=haimingchazhirongqi[m].bianhao;
    // cout<<"m="<<m<<endl;///////////////////////////////////
    // cout<<"配对编号:"<<haimingchazhirongqi[m].bianhao<<endl;///////
    // cout<<"海明差值:"<<haimingchazhirongqi[m].haimingchazhi<<endl;///////
                   // cout<<"海明差值小:"<<haimingchazhirongqi[m+2].haimingchazhi<<endl;///////
    // system("pause");//////////////////////////////////
    }
  
 }
//    for(int iii=0;iii<10;iii++)///////////////////
// {
//  cout<<pipeichi[peiduishuzu[iii]].geti<<endl;///////////////
// }
//    system("pause");//////////////////////
//    cout<<endl;
// qsort(peiduishuzu,200,sizeof(int),&cmp1);//////////////
// cout<<endl;/////////////////////////////////
//   for(int iii=0;iii<200;iii++)///////////////////
// {
//  cout<<peiduishuzu[iii]<<endl;///////////////
// }
//    system("pause");//////////////////////
//    cout<<endl;
 for(i=0;i<zhongqunshu1-1;i=i+2)
 {
  fuqin1=pipeichi[peiduishuzu[i]];
  fuqin2=pipeichi[peiduishuzu[i+1]];
  crossover(fuqin1,fuqin2,newpop[i],newpop[i+1]);
 }
 for(j=0;j<zhongqunshu1;j++)
 {
  //if(newpop[j].geti<-1000)
   //cout<<"个体数值小于下界了";
  nowpop[j].geti=newpop[j].geti;
 }
 //
 guanjiancanshujisuan();
 //变异的实现
    for(j=0;j<zhongqunshu;j++)
 {
  bianyi(nowpop[j]);
 }
 //
 guanjiancanshujisuan();
 //精英保留的实现
 jingyingbaoliu();
  //
 guanjiancanshujisuan();
 delete [] haimingrongqi;
 delete [] peiduishuzu;
 delete [] pipeichi;
 delete [] pipeiguodu;
}
void crossover(individual parent1,individual parent2,individual &child1,individual &child2)//交叉
{
 int j=0,i=0;
 if(flipc(parent1.fitness,parent2.fitness))
 {
  //cout<<"父个体1:"<<parent1.geti<<endl;////////////////
  //cout<<"父个体2:"<<parent2.geti<<endl;////////////////
  int xingcunzhe;
  youxuan *zuihouliangge;//将优选群的个体按高斯变异的结果排序（高斯变异为了验证是否是信息最大化点），取适应度最大的两个
  individual *jingzhengqun,*youxuanqun,*beiyongyouxuanqun;
  int *I,*index,*red;
  double lanmute,*getipingjunhaiming;
  I=new int[2*lanmuteshuliang+2];
  index=new int[2*lanmuteshuliang+2];
      jingzhengqun=new individual[(2*lanmuteshuliang+2)];//设置竞争群的大小，用于交叉的栏目特暂时设为5个
  youxuanqun=new individual[(2*lanmuteshuliang+2)];//优选群的大小最后为信息最大化选择后剩下的个体
  beiyongyouxuanqun=new individual[(2*lanmuteshuliang+2)];
        getipingjunhaiming=new double[(2*lanmuteshuliang+2)];//用来储存个体平均海明距离
  red=new int[(2*lanmuteshuliang+2)];//用来储存冗余信息
  zuihouliangge=new youxuan[(2*lanmuteshuliang+2)];
  for(j=0;j<(2*lanmuteshuliang+2);j++)
  {
   I[j]=0;
   index[j]=1;
  }
  for(j=0;j<lanmuteshuliang;j++)
  {
   lanmute=0.5+ran1(a)*(1.5-0.5);
      jingzhengqun[i].geti=lanmute*parent1.geti+(1-lanmute)*parent2.geti;
   jingzhengqun[i+1].geti=lanmute*parent2.geti+(1-lanmute)*parent1.geti;
   while(jingzhengqun[i].geti<zuobianjie||jingzhengqun[i].geti>youbianjie||jingzhengqun[i+1].geti<zuobianjie||jingzhengqun[i+1].geti>youbianjie)
   {
    lanmute=0.5+ran1(a)*(1.5-0.5);
          jingzhengqun[i].geti=lanmute*parent1.geti+(1-lanmute)*parent2.geti;
       jingzhengqun[i+1].geti=lanmute*parent2.geti+(1-lanmute)*parent1.geti;
   }
   i=i+2;
  }
  jingzhengqun[i].geti=parent1.geti;
  jingzhengqun[i+1].geti=parent2.geti;
  //for(j=0;j<(2*lanmuteshuliang+2);j++)////////////////////
  //{
  // cout<<jingzhengqun[j].geti<<endl;
  //}
 // system("pause");///////////////////////////////////
  for(j=0;j<(2*lanmuteshuliang+2);j++)
  {
   mubiaohanshu(jingzhengqun[j]);
  }
 // for(j=0;j<(2*lanmuteshuliang+2);j++)////////////////////
 // {
 //  cout<<jingzhengqun[j].shiyingdu<<endl;
 // }
 // system("pause");///////////////////////////////////
 // for(j=0;j<(2*lanmuteshuliang+2);j++)////////////////////
 // {
 //  cout<<jingzhengqun[j].geti<<endl;
 // }
 // system("pause");///////////////////////////////////
  qsort(jingzhengqun,(2*lanmuteshuliang+2),sizeof(individual),&cmpgeti);//将竞争群按空间排序
 // for(j=0;j<(2*lanmuteshuliang+2);j++)////////////////////
 // {
 //  cout<<jingzhengqun[j].geti<<endl;
 // }
 // system("pause");///////////////////////////////////
 // for(j=0;j<(2*lanmuteshuliang+2);j++)////////////////////
 // {
 //  cout<<jingzhengqun[j].shiyingdu<<endl;
 // }
 // system("pause");///////////////////////////////////
  //判断是否是峰值附近
        for(j=0;j<(2*lanmuteshuliang+1);j++)
  {
   if(jingzhengqun[j].shiyingdu<jingzhengqun[j+1].shiyingdu)
   {
    I[j]=1;
   }
   else if(jingzhengqun[j].shiyingdu>=jingzhengqun[j+1].shiyingdu)
   {
    I[j]=-1;
   }
  }
  I[(2*lanmuteshuliang+1)]=I[2*lanmuteshuliang];
 // for(j=0;j<(2*lanmuteshuliang+2);j++)////////////////////
 // {
 // cout<<I[j]<<endl;
 // }
 // system("pause");///////////////////////////////////
        for(j=0;j<(2*lanmuteshuliang+1);j++)
  {
   if(I[j]==I[j+1])
    index[j]=0;
  }
  //for(j=0;j<(2*lanmuteshuliang+2);j++)////////////////////
  //{
  // cout<<index[j]<<endl;
  //}
  //system("pause");///////////////////////////////////
        //判断冗余度
  //求平均海明距离
    double avehai=0;//平均海明值
 int sumchahainei=0;//单个个体和其他个体海明距离和
 int sumchahaiwai=0;//总的海明距离和
 int jisuancishu=0;//求海明和的次数
 for(int ii=0;ii<(2*lanmuteshuliang+1);ii++)
 {
  sumchahainei=0;
        //cout<<"ii的值:"<<haimingrongqi[ii].geti<<endl;//////////
  for(int jj=ii+1;jj<(2*lanmuteshuliang+2);jj++)
  {
   //cout<<"jj的值:"<<haimingrongqi[jj].geti<<endl;//////////
   //system("pause");//////////////////////////
   sumchahainei=sumchahainei+haimingchazhijisuan(jingzhengqun[ii].geti,jingzhengqun[jj].geti);
  }
  sumchahaiwai=sumchahaiwai+sumchahainei;
 }
 //cout<<sumchahaiwai<<endl;///////////
 for(ii=1;ii<=(2*lanmuteshuliang+1);ii++)
 {
  jisuancishu=jisuancishu+((2*lanmuteshuliang+2)-ii);
 }
 avehai=(double)(sumchahaiwai/jisuancishu);
// cout<<"平均海明距离:"<<avehai<<endl;////////////////////
 //system("pause");////////////////////
    //求单个个体平均海明距离
 for(ii=0;ii<(2*lanmuteshuliang+2);ii++)
 {
  getipingjunhaiming[ii]=0;
  for(int jj=0;jj<(2*lanmuteshuliang+2);jj++)
  {
   getipingjunhaiming[ii]=getipingjunhaiming[ii]+haimingchazhijisuan(jingzhengqun[ii].geti,jingzhengqun[jj].geti);
  }
  getipingjunhaiming[ii]= getipingjunhaiming[ii]/(2*lanmuteshuliang+1);
 }
//   for(ii=0;ii<(2*lanmuteshuliang+2);ii++)////////////////////////
// {////////////////
//  cout<<getipingjunhaiming[ii]<<endl;///////////
// }////////////////////
// system("pause");////////////////////
    for(ii=0;ii<(2*lanmuteshuliang+2);ii++)
 {
  if(getipingjunhaiming[ii]>=avehai)
   red[ii]=1;
  else
   red[ii]=0;
 }
// for(ii=0;ii<(2*lanmuteshuliang+2);ii++)////////////////////////
// {////////////////
//  cout<<red[ii]<<endl;///////////
// }/////////////////////
// system("pause");////////////////////
 ii=0;
 xingcunzhe=0;
    for(ii=0;ii<(2*lanmuteshuliang+2);ii++)
 {
  if(index[ii]!=0||red[ii]!=0)
  {
   youxuanqun[xingcunzhe].geti=jingzhengqun[ii].geti;
   xingcunzhe++;
  }
 }
// cout<<"幸存者数量:"<<xingcunzhe<<endl;//////////////////
 //   for(ii=0;ii<xingcunzhe;ii++)////////////////////////
// {////////////////
//  mubiaohanshu(youxuanqun[ii]);
//  cout<<"个体:"<<youxuanqun[ii].geti<<" "<<"适应度:"<<youxuanqun[ii].shiyingdu<<endl;///////////
// }/////////////////////
  //  system("pause");////////////////////
    for(ii=0;ii<xingcunzhe;ii++)////////////////////////
 {
  //zuihouliangge[ii].geti=youxuanqun[ii].geti;
  zuihouliangge[ii].shiyingdu=0;
 }

 //对优选群进行高斯变异
 if(xingcunzhe>=2)
 {
  for(int jjj=0;jjj<20;jjj++)
  {
  
   for(ii=0;ii<xingcunzhe;ii++)
   {
    mubiaohanshu(youxuanqun[ii]);
   }
      for(ii=0;ii<xingcunzhe;ii++)
   {
       beiyongyouxuanqun[ii].geti=youxuanqun[ii].geti+gasdev(a);
    while(beiyongyouxuanqun[ii].geti<zuobianjie||beiyongyouxuanqun[ii].geti>youbianjie)
    {
     beiyongyouxuanqun[ii].geti=youxuanqun[ii].geti+gasdev(a);
    }
   }
      for(ii=0;ii<xingcunzhe;ii++)
   {
       mubiaohanshu(beiyongyouxuanqun[ii]);
   }
       for(ii=0;ii<xingcunzhe;ii++)
   {
       if(beiyongyouxuanqun[ii].shiyingdu>youxuanqun[ii].shiyingdu)
    {
        youxuanqun[ii].geti=beiyongyouxuanqun[ii].geti;
    }
   }
  }
      for(ii=0;ii<xingcunzhe;ii++)
  {
   mubiaohanshu(youxuanqun[ii]);
  }
 
 //   for(ii=0;ii<xingcunzhe;ii++)////////////////////
// {////////////////
//  cout<<"个体:"<<youxuanqun[ii].geti<<" "<<"适应度:"<<youxuanqun[ii].shiyingdu<<endl;///////////
// }///
// cout<<endl;///////////
// system("pause");/////////////
 for(ii=0;ii<xingcunzhe;ii++)
 {
  zuihouliangge[ii].shiyingdu=youxuanqun[ii].shiyingdu;
  zuihouliangge[ii].geti=youxuanqun[ii].geti;
 }
 //   for(ii=0;ii<xingcunzhe;ii++)////////////////////
// {////////////////
//  cout<<"个体:"<<zuihouliangge[ii].geti<<" "<<"适应度:"<<zuihouliangge[ii].shiyingdu<<endl;///////////
// }///
// cout<<endl;///////////
// system("pause");/////////////
    qsort(zuihouliangge,(2*lanmuteshuliang+2),sizeof(youxuan),&cmpshiyingdujiang);//将优选群按变异后适应度降序排序
// for(ii=0;ii<xingcunzhe;ii++)////////////////////
// {////////////////
//  cout<<"个体:"<<zuihouliangge[ii].geti<<" "<<"适应度:"<<zuihouliangge[ii].shiyingdu<<endl;///////////
// }///
// cout<<endl;///////////
// system("pause");/////////////
 child1.geti=zuihouliangge[0].geti;
 child2.geti=zuihouliangge[1].geti;
// cout<<child1.geti<<endl;///////////////////////
 //cout<<child2.geti<<endl;///////////////////////
 }
 else
 {
  double alpha=ran1(a);
  child1.geti=alpha*parent1.geti+(1-alpha)*parent2.geti;
  child2.geti=alpha*parent2.geti+(1-alpha)*parent1.geti;
 } 
  delete [] zuihouliangge;
  delete [] red;
  delete [] getipingjunhaiming;
  delete [] beiyongyouxuanqun;
  delete [] youxuanqun;
  delete [] jingzhengqun;
  delete [] index;
  delete [] I;

 }
 else
 {
   child1.geti=parent1.geti;
   child2.geti=parent2.geti;
 }
}
void bianyi(individual &child)//变异
{
 if(flipm(child.fitness))
 {
 double alpha,r,derta;
    alpha=ran1(a);
 if(alpha>0.5)
 {
  derta=(youbianjie-child.geti)*(1-ran1(a)*pow((1-gen/maxgen),2));
  child.geti=child.geti+derta;
 }
 else
 {
  derta=(child.geti-zuobianjie)*(1-ran1(a)*pow((1-gen/maxgen),2));
  child.geti=child.geti-derta;
 }
 }
 if(child.geti>2000||child.geti<-2000)//////////////////
   system("pause");/////////////////////
}
double ran1(long *idum)
{
int j;
long k;
static long idum2=123456789;
static long iy=0;
static long iv[NTAB];
float temp;
if (*idum <= 0)
{
if (-(*idum) < 1) *idum=1;
else *idum = -(*idum);
idum2=(*idum);
for (j=NTAB+7;j>=0;j--)
{
k=(*idum)/IQ1;
*idum=IA1*(*idum-k*IQ1)-k*IR1;
if (*idum < 0) *idum += IM1;
if (j < NTAB) iv[j] = *idum;
}
iy=iv[0];
}
k=(*idum)/IQ1;
*idum=IA1*(*idum-k*IQ1)-k*IR1;
 if (*idum < 0) *idum += IM1;
k=idum2/IQ2;
idum2=IA2*(idum2-k*IQ2)-k*IR2;
if (idum2 < 0) idum2 += IM2;
j=iy/NDIV;
iy=iv[j]-idum2;
iv[j] = *idum;
if (iy < 1) iy += IMM1;
if ((temp=AM*iy) > RNMX) return RNMX;
else return temp;
}
double suijibianli()//随机遍历
{
 double i=ran1(a);
 while(i>zhizhenjuli)
 {
  i=ran1(a);
 }
 //cout<<i<<endl;//////////////
 return i;
}
int fuzhi(float p)//复制
{
 int i;
 double sum=0;
 if(sumfitness!=0)
 {
  for(i=0;(sum<p)&&(i<zhongqunshu);i++)
   sum+=nowpop[i].fitness/sumfitness;
 }
 else
  i=rnd(1,zhongqunshu1);
 return(i-1);
}

int rnd(int low, int high)           /*在整数low和high之间产生一个随机整数*/
{
    int i;
    if(low >= high)
        i = low;
    else
    {
        i =(int)((ran1(a) * (high - low + 1)) + low);
        if(i > high) i = high;
    }
    return(i);
}
int flipc(double p,double q)//判断是否交叉
{
 double pc1=0.9,pc2=0.8;
 if((p-q)>0)
 {
  if(p>=avefitness)
  {
   pc=pc1-(pc1-pc2)*(p-avefitness)/(maxfitness-avefitness);
  }
  else
   pc=pc1;
 }
 else
 {
  if(q>=avefitness)
  {
   pc=pc1-(pc1-pc2)*(q-avefitness)/(maxfitness-avefitness);
  }
  else
   pc=pc1;
 }
    if(ran1(a)<=0.8)
        return(1);
    else
        return(0);
}
int flipm(double p)//判断是否变异
{
 double pm1=0.01,pm2=0.001;
 if(p>=avefitness)
 {
  pm=(pm1-(pm1-pm2)*(maxfitness-p)/(maxfitness-avefitness));
 }
 else
 pm=pm1;
 if(ran1(a)<=0.01)
        return(1);
    else
        return(0);
}
void glp(int n,int s,int *h,int (*q)[1],float (*xx)[1])//glp
{
 int i=0,j=0;
 //求解q
 for(i=0;i<n;i++)
 {
  for(j=0;j<s;j++)
  {
   *(*(q+i)+j)=((i+1)*(*(h+j)))%n;
  }
 }
 i=n-1;
 for(j=0;j<s;j++)
 {
  *(*(q+i)+j)=n;
 }
 //求解x
 for(i=0;i<n;i++)
 {
  for(j=0;j<s;j++)
  {
   *(*(xx+i)+j)=(float)(2*(*(*(q+i)+j))-1)/(2*n);
  }
 }
}
BOOL Exist(int Val, int Num, int *Array)//判断一个数是否在一个数组的前Num个数中
{
BOOL FLAG = FALSE;
int i;
for (i=0; i<Num; i++)
if (Val == *(Array + i))
{
FLAG = TRUE;
break;
}
return FLAG;
}
double hundunsuiji()
{
 hundun=c*hundun*(1-hundun);
 return hundun;
}

int haimingchazhijisuan(double bianliang1,double bianliang2)
{
 unsigned *p;
 unsigned *q;
// unsigned *gray;
 p=new unsigned[lchrom];
 q=new unsigned[lchrom];
// gray=new unsigned[lchrom];
 int x=0;
 int i=0,j=0;
 if(bianliang1<zuobianjie||bianliang1>youbianjie)///////////////////
 {
  cout<<"bianliang1:"<<bianliang1<<endl;/////////
  system("pause");
 }
 if(bianliang2<zuobianjie||bianliang2>youbianjie)///////////////////
 {
  cout<<"bianliang2:"<<bianliang2<<endl;/////////
  system("pause");
 }
 //cout<<youbianjie-(zuobianjie)<<endl;
 //system("pause");
 for(i=0;i<lchrom;i++)//p，q两个数组归零
 {
  q[i]=0;
  p[i]=0;
 }
 //对变量1进行编码
 x=(bianliang1-(zuobianjie))*((pow(2,lchrom)-1)/(youbianjie-(zuobianjie)));
 //cout<<x<<endl;///////////
 if(x<0)
 system("pause");///////////
 i=0;
 while (x!=0&&(i!=lchrom))
 {
  q[i]=(unsigned)(x%2);
  x=x/2;
  i++;
 }
// for(i=0;i<lchrom;i++)//////////////////
//  cout<<q[i];///////////////
// cout<<endl;///////////
 int w=lchrom-1;
 if(q[w]!=0&&q[w]!=1)
  system("pause");
 //对变量2进行编码
 x=0;
 x=(bianliang2-(zuobianjie))*((pow(2,lchrom)-1)/(youbianjie-(zuobianjie)));
 //cout<<x<<endl;///////////
 if(x<0)
 system("pause");///////////
 i=0;
 while (x!=0&&(i!=lchrom))
 {
  p[i]=(unsigned)(x%2);
  x=x/2;
  i++;
 }
    w=lchrom-1;
 if(p[w]!=0&&p[w]!=1)
  system("pause");
// for(j=0;j<lchrom&&w>0;j++)
// {
//  p[j]=q[w];
//  w--;
// }
// //cout<<"yuanma"<<endl;
// for(j=0;j<lchrom;j++)///////////
//  cout<<p[j];////////
// cout<<endl;////////////////////
// for(j=0;j<lchrom;j++)///////////
//  cout<<q[j];////////
// cout<<endl;////////////////////
// gray[0]=p[0];
// for(j=1;j<lchrom;j++)
// {
//  if(p[j-1]==p[j])
//   gray[j]=0;
//  else if(p[j-1]!=p[j])
//   gray[j]=1;
// }
 //for(j=0;j<lchrom;j++)
 // p[j]=gray[j];
 //cout<<"geleima"<<endl;
 //for(j=0;j<lchrom;j++)///////////
 // cout<<p[j];////////
 //cout<<endl;////////////////////
 //system("pause");///////////
    int hai=0,a=0;
 for(j=0;j<lchrom;j++)
 {
  if(q[j]==p[j])
   a=0;
  else
   a=1;
  hai=hai+a;
  //cout<<hai<<endl;////
 }
 if(hai<0)//////////////
 {
  cout<<"海明差值计算结果:"<<hai<<endl;///////////////
  system("pause");/////////////////////
 }
// delete [] gray;
 delete [] q;
 delete []p;
 return hai;
}
double gasdev(long *idum)
{ 
 double ran1(long *idum);
 static int iset=0;
 static double gset;
 double fac,rsq,v1,v2;
 if (*idum < 0)
  iset=0; //初始化
 if (iset == 0)
 {
  do
  {
   v1=2.0*ran1(idum)-1.0;
   v2=2.0*ran1(idum)-1.0;
   rsq=v1*v1+v2*v2;
  }while (rsq >= 1.0 || rsq == 0.0);
  fac=sqrt(-2.0*log(rsq)/rsq);
  gset=v1*fac;
  iset=1;
  return v2*fac;
 }
 else
 {
  iset=0;
  return gset;
 }
}