ga(c++).txt

遺傳演算法(Genetic Algorithm),使用c++編譯

#include <stdlib.h> 
#include <time.h> 
#include <math.h> 
#include <fstream.h> 
#include "randgen.h" 
#include "array.h" 
  
// 
// BitArray object class for Genetic Algorithm 
// 
  
class BitArray: public Array1D<bool> 
{ 
public: 
  void Initialize(int n) 
  { 
    Array1D<bool>::Initialize(n); 
    for(int i=0;i<nb;i++)m[i]=0; 
  } 
  void Randomize(unsigned long seed); 
  void SetBit(int ndx, bool bit){m[ndx]=bit;} 
  void SetBits(ifstream &in){for(int i=0;i<nb;i++)in>>m[i];} 
  bool GetBit(int ndx){return m[ndx];} 
  long ToDecimal(); 
  int HammingDistance(BitArray &by); 
  void Print(ofstream& out){for(int i=0;i<nb;i++)out<<m[i];out<<endl;} 
  void Print(){for(int i=0;i<nb;i++)cout<<m[i];cout<<endl;} 
  bool operator==(BitArray &by); 
}; 
  
void BitArray::Randomize(unsigned long seed) 
{ 
  RanBit32 rbg(seed); 
  for(int i = 0; i<nb; i++) m[i] = rbg.Next(); 
} 
  
long BitArray::ToDecimal() 
{ 
  long value = 0; 
  for(int i = 0; i<nb; i++) 
  { 
    if(m[i])value += m[i]<<i; 
  } 
  return value; 
} 
  
int BitArray::HammingDistance(BitArray &by) 
{ 
  int dist=0; 
  for(int i=0;i<nb;i++)if(by.m[i]!=m[i])dist++; 
  return dist; 
} 
  
bool BitArray::operator==(BitArray &by) 
{ 
  if(by.nb!=nb)return false; 
  bool flag=true; 
  for(int i=0;i<nb;i++)if(by.m[i]!=m[i]) 
  { 
    flag = false; 
    break; 
  } 
  return flag; 
} 
  
  
// 
// object class for Genetic Algorithm : Evaluator 
// 
  
class Evaluator 
{ 
protected: 
  int nb_variables; 
  i1D nb_bits; 
  Array1D<BitArray> BinaryVariable; 
public: 
  int GetTotalBits() 
  { 
    int total_bits=0; 
    for(int i=0;i<nb_variables;i++)total_bits += nb_bits[i]; 
    return total_bits; 
  } 
  int GetNbVariable(){return nb_variables;} 
  void Decompose(BitArray &bitarray); 
  virtual double Evaluate(BitArray &bitarray, 
                               double (*userfunc)(f1D &para))=0; 
  virtual f1D& Decoding(BitArray &individ)=0; 
}; 
  
void Evaluator::Decompose(BitArray &bitarray) 
{ 
  int count=0; 
  for(int i=0;i<nb_variables;i++) 
  { 
    for(int j=0;j<nb_bits.m[nb_variables-1-i];j++) 
    { 
      BinaryVariable[nb_variables-1-i].m[j]=bitarray.m[count]; 
      count++; 
     } 
  } 
} 
  
class NumericEvaluator : public Evaluator 
{ 
protected: 
  int total_bits; 
  f1D min; 
  f1D max; 
public: 
  f1D RealVariable; 
  void Initialize(ifstream &in); 
  f1D& Decoding(BitArray &individ); 
  double Evaluate(BitArray &bitarray, 
                  double (*userfunc)(f1D &para)); 
}; 
  
void NumericEvaluator::Initialize(ifstream &in) 
{ 
  int required_precision; 
  in>>nb_variables>>required_precision; 
  int i,j, morder = required_precision-1; 
  max.Initialize(nb_variables); 
  min.Initialize(nb_variables); 
  nb_bits.Initialize(nb_variables); 
  BinaryVariable.Initialize(nb_variables); 
  RealVariable.Initialize(nb_variables); 
// define by case 
  for(i=0;i<nb_variables;i++) 
  {in>>min[i]>>max[i];} 
  double *t=new double[nb_variables]; 
  for(i=0;i<nb_variables;i++) 
    t[i] = double(max[i] - min[i])*pow10(morder); 
  for(i=0;i<nb_variables;i++)nb_bits[i]=0; 
  for(i=0;i<nb_variables;i++) 
  { 
    for(j=1;j<32;j++)if((t[i]>pow(2,j-1))&&(t[i]<=pow(2,j))) 
    {nb_bits[i]=j; break;} 
  } 
  delete t; 
  total_bits=0; 
  for(i=0;i<nb_variables;i++)total_bits+=nb_bits[i]; 
  for(i=0;i<nb_variables;i++) 
    BinaryVariable[i].Initialize(nb_bits[i]); 
} 
  
double NumericEvaluator::Evaluate(BitArray &bitarray, 
        double (*userfunc)(f1D &para)) 
{ 
  if(bitarray.nb!=total_bits)return double(0.0); 
  Decoding(bitarray); 
  return userfunc(RealVariable); 
} 
  
f1D& NumericEvaluator::Decoding(BitArray &individ) 
{ 
  Decompose(individ); 
  for(int i=0;i<nb_variables;i++) 
  { 
    RealVariable[i]=BinaryVariable[i].ToDecimal(); 
    RealVariable[i]=min.m[i]+RealVariable[i]*(max.m[i]-min.m[i]) 
                   /(pow(2,nb_bits.m[i])-1.0); 
  } 
  return RealVariable; 
} 
  
// 
// object class for Genetic Algorithm : population 
// 
  
class Population 
{ 
protected: 
  int generation; 
  int nb_individ; 
  int nb_bit; 
  int optimal_individ_ndx; 
  float CrossoverP; 
  float MutationP; 
  float ReserveP; 
  float total_fitness; 
  Ran32 GlbRan; 
  Array1D<BitArray> individ, individtmp; 
  f1D Fitness, AccFitness; 
  f1D ProbaTable; 
  Array1D<bool> Survivor; 
  i1D ndx; 
  int NSurvivor; 
  BitArray CrossoverMask; 
  void IndividCrossOver(BitArray &b1, BitArray &b2, int pos); 
  void ConvertFitnessByOrder(); 
  void FindNBestIndivids(f1D &fit, int N); 
public: 
  void Initialize(int nindivid, int nbit); 
  void Recording(Evaluator &eva, ofstream &out); 
  
// Genetic mecanism 
  f1D& Evaluate(Evaluator &eva, double (*userfunc)(f1D &para)); 
  void Evolution(); 
  void CrossOverOnePointCut();                 // one-point-cut crossover 
  void CrossOverByMask(unsigned long seed);    // mask crossover 
  void Mutation(); 
  void Selection(); 
  
// User interface 
  void SetCrossOverProbability(float p){CrossoverP=p;} 
  void SetMutationProbability(float p){MutationP=p;} 
  int Get_Nb_Individ(){return nb_individ;} 
  int Get_Nb_Bit(){return nb_bit;} 
  BitArray& GetIndivid(int index); 
  BitArray& GetOptimalIndivid(); 
  double GetOptimalFitness(); 
  double GetFitness(int index){return Fitness[index];} 
  double GetTotalFitness(){return total_fitness;} 
  void Print(ofstream& out); 
  int GetOptimalIndividIndex(){return optimal_individ_ndx;} 
}; 
  
void Population::Initialize(int nindivid, int nbit) 
{ 
  nb_individ=nindivid; 
  nb_bit=nbit; 
// default values for CrossoverP, MutationP 
  CrossoverP = 0.6; 
  MutationP = 0.005; 
  ReserveP = 0.1; 
  unsigned long seed = (unsigned long)time(0); 
  GlbRan.Reset(seed); 
  for(int i=0;i<GlbRan.Next(0,10000);i++)seed=GlbRan.Next(); 
  GlbRan.Reset(seed); 
  individ.Initialize(nb_individ); 
  individtmp.Initialize(nb_individ*ReserveP); 
  Fitness.Initialize(nb_individ); 
  AccFitness.Initialize(nb_individ); 
  ProbaTable.Initialize(nb_individ); 
  Survivor.Initialize(nb_individ); 
  ndx.Initialize(nb_individ); 
  for(int i=0;i<individ.nb;i++) 
  { 
    individ.m[i].Initialize(nb_bit); 
    individtmp.m[i].Initialize(nb_bit); 
    individ.m[i].Randomize(GlbRan.Next()); 
  } 
  CrossoverMask.Initialize(nb_bit); 
  CrossoverMask.Randomize(GlbRan.Next()); 
  generation=0; 
} 
  
void Population::Recording(Evaluator &evaluator, ofstream &out) 
{ 
  int i,j; 
  f1D t; 
  out<<endl<<"generation : "<<generation<<endl; 
  for(i=0;i<nb_individ;i++) 
  { 
    t = evaluator.Decoding(individ[i]); 
    out<<i<<"\tf("; 
    for(j=0;j<evaluator.GetNbVariable();j++)out<<t[j]<<", ";out<<") = "; 
    out<<Fitness[i]<<endl; 
  } 
  out<<"average fitness : "<<total_fitness/float(nb_individ)<<endl; 
  out<<"optimal individual is : "<<optimal_individ_ndx<<endl; 
  t = evaluator.Decoding(individ.m[optimal_individ_ndx]); 
  out<<"optimal solution : "<<"\tf("; 
  for(j=0;j<evaluator.GetNbVariable();j++)out<<t[j]<<", ";out<<") = "; 
  out<<Fitness[optimal_individ_ndx];out<<endl; 
} 
  
void Population::IndividCrossOver(BitArray &b1, BitArray &b2, int pos) 
{ 
  bool b; 
  for(int i=0;i<pos;i++) 
  { 
    b=b1.m[i]; 
    b1.m[i]=b2.m[i]; 
    b2.m[i]=b; 
  } 
} 
  
void Population::ConvertFitnessByOrder() 
{ 
  int i,j; 
  for(i=0;i<nb_individ;i++) 
  { 
    AccFitness.m[i]=0; 
    for(j=0;j<nb_individ;j++)if(Fitness.m[i]>Fitness.m[j])AccFitness.m[i]++; 
  } 
  for(i=0;i<nb_individ;i++)Fitness.m[i]=AccFitness.m[i]; 
} 
  
void Population::Selection() 
{ 
  int i,j; 
  float sum=0.0; 
  ConvertFitnessByOrder(); 
  for(i=0;i<nb_individ;i++)sum+=Fitness.m[i]; 
  for(i=0;i<nb_individ;i++)AccFitness.m[i]=Fitness.m[i]/sum; 
  for(i=1;i<nb_individ;i++)AccFitness.m[i]+=AccFitness.m[i-1]; 
  fRan32 rg(GlbRan.Next()); 
  for(i=0;i<nb_individ;i++)ProbaTable.m[i]=rg.Next(0.0, 1.0); 
  NSurvivor=0; 
  for(i=0;i<nb_individ;i++)if(ProbaTable.m[i]<CrossoverP) 
  { 
    Survivor.m[i] = true; 
    ndx.m[NSurvivor] = i; 
    NSurvivor++; 
  } 
  NSurvivor = (NSurvivor/2)*2; 
} 
  
void Population::CrossOverOnePointCut() 
{ 
  int i,n,a,b; 
  Ran32 rg(GlbRan.Next()); 
  for(i=0;i<NSurvivor/2;i++) 
  { 
    a = rg.Next(0,NSurvivor); 
    b = rg.Next(0,NSurvivor); 
    n=rg.Next(0,nb_bit); 
    IndividCrossOver(individ[ndx[a]],individ[ndx[b]],n); 
  } 
} 
  
void Population::CrossOverByMask(unsigned long seed) 
{ 
  int i,j,a,b; 
  RanBit32 rbg(seed); 
  for(i = 0; i< CrossoverMask.nb; i++) CrossoverMask.m[i] = rbg.Next(); 
  Ran32 rg(GlbRan.Next()); 
  bool t; 
  for(i=0;i<NSurvivor/2;i++) 
  { 
    a = rg.Next(0,NSurvivor); 
    b = rg.Next(0,NSurvivor); 
    for(j=0;j<CrossoverMask.nb;j++)if(CrossoverMask.m[j]==1) 
    { 
      t = individ[ndx[a]].m[j]; 
      individ[ndx[a]].m[j] = individ[ndx[b]].m[j]; 
      individ[ndx[b]].m[j] = t; 
    } 
  } 
} 
  
void Population::Mutation() 
{ 
  long length = nb_individ*nb_bit; 
  int x, xd, xm; 
  int nb_mt = int(MutationP*float(length)+0.5); 
  for(int i=0;i<nb_mt;i++) 
  { 
    x = GlbRan.Next(0, length-1); 
    xd = x/nb_bit; 
    xm = x%nb_bit; 
    if(individ[xd].m[xm]==0)individ[xd].m[xm]=1; 
    else individ[xd].m[xm]=0; 
   } 
} 
  
f1D& Population::Evaluate(Evaluator &evaluator, double (*userfunc)(f1D &para)) 
{ 
  int i; 
  for(i=0;i<nb_individ;i++) 
    Fitness.m[i]=evaluator.Evaluate(individ.m[i], userfunc); 
  float max=-1e30; 
  for(i=0;i<nb_individ;i++)if(Fitness.m[i]>max) 
  { 
    max=Fitness.m[i]; 
    optimal_individ_ndx=i; 
  } 
  total_fitness=0; 
  for(i=0;i<nb_individ;i++)total_fitness += Fitness.m[i]; 
  return Fitness; 
} 
  
void Population::FindNBestIndivids(f1D &fit, int N) 
{ 
  
} 
  
void Population::Evolution() 
{ 
  Selection(); 
//  CrossOverByMask(GlbRan.Next()); 
  CrossOverOnePointCut(); 
  Mutation(); 
  generation++; 
} 
  
BitArray& Population::GetIndivid(int ndx) 
{ 
  return individ[ndx]; 
} 
  
BitArray& Population::GetOptimalIndivid() 
{ 
  return individ[optimal_individ_ndx]; 
} 
  
double Population::GetOptimalFitness() 
{ 
  return Fitness[optimal_individ_ndx]; 
} 
  
void Population::Print(ofstream& out) 
{ 
  for(int i=0;i<nb_individ;i++)individ[i].Print(out); 
} 
  
  
double user_evaluation_function(f1D &v) 
{ 
  return -(v[0]*v[0] + v[1]*v[1]); 
} 
  
  
  
// Testing main program 
main() 
{ 
  char key; 
  char filename[128]; 
  cout<<"Input filename of parameter description data : "; 
  cin>>filename; 
  ifstream in(filename); 
  ofstream out("ga.dat"); 
  if(!in){cout<<"Cannot open file! Any key to terminate...";cin>>key;exit(1);} 
  NumericEvaluator evaluator; 
  evaluator.Initialize(in); 
  Population population; 
  SetCrossOverProbability(0.6); 
  SetMutationProbability(0.02); 
  int generation, nb_individ; 
  cout<<"\nEnter number of individuals in the population : ";cin>>nb_individ; 
  cout<<"\nEnter number of iteration for evolution : ";cin>>generation; 
  population.Initialize(nb_individ, evaluator.GetTotalBits()); 
  population.Evaluate(evaluator, user_evaluation_function); 
  for(int i=0;i<generation;i++) 
  { 
    population.Evolution(); 
    population.Evaluate(evaluator,user_evaluation_function); 
    population.Recording(evaluator, out); 
    cout<<i<<endl; 
  } 
  cout<<endl<<"The evolution process is saved in ga.dat"<<endl; 
  cout<<"any key to terminate..."; 
  cin>>key;