/***********************************************************************
   
                       SIMPLE GENETIC ALGORITHM
                           ZERO-ONE KNAPSACK

                           WHO:  Robert Walsh
                           WHAT: CSCI 475
                           WHEN: Jan 10, 1995
                     
 This is a simple genetic algorithm which attempts to solve the zero/one
                           knapsack problem.  
                     
************************************************************************/
#include <stdio.h>

#define NObj 50
#define NPop 50
#define NCap 500
#define NMut 1
#define NCrs 50

short int Item[200], G;

struct Objects
{
   char  Bit[NObj];
   int   Fitness;
};

struct Objects Chrome[NPop][2];

void GetData()
/**********************************************************************
WHAT: Reads the data from a file and stores it in the array, Item[].  
      The data in this array is assumed to be formated as follows:
      Item[0] = Value, Item[1] = Weight
      Item[2] = Value, Item[3] = Weight
              |                |
      Item[198] = Value, Item[199] = Weight
***********************************************************************/
{
   FILE *In, *fopen();
   
   if(In = fopen("KSData", "r"))
   {
      fread(Item, 2, 200, In);
      fclose(In);
   }
}

void InitPop()
/**********************************************************************
WHAT: Randomly creates an initial population of size NPop by assigning
      a binary value to the array Chrome[][].Bit[j] which acts as the
      chromosome.
***********************************************************************/
{
   int t, i;
   
   for(t=0; t<NPop; t+=1)
   {
      for(i=0; i<NObj; i+=1) 
      if(RangeRand(25)==1) Chrome[t][G].Bit[i]=1;
         else Chrome[t][G].Bit[i]=0;
   }
}

int Evaluate()
/**********************************************************************
WHAT: Evaluates the population.  The evaluation assigns a fitness value
      to each member of the population.  The fitness value is also the
      total value of the items in the knapsack.  In the case that knap-
      sack is overfull, the fitness is assign 0.
OUT:  Returns the highest fitness of the current population. 
***********************************************************************/
{
   register short int t, i, Value, Weight;
   int High=0;
   
   for(t=0; t<NPop; t+=1)
   {
      Value=0; Weight=0;
      for(i=0; i<NObj; i+=1)
      {
         if(Chrome[t][G].Bit[i]==1)
         {
            Value+=Item[i*2];
            Weight+=Item[i*2+1];
         }
      }
      if(Weight<=NCap) 
      {
         Chrome[t][G].Fitness=Value;
         if(Value>High) High=Value;
      }
      else Chrome[t][G].Fitness=0;
   }
   return High;
}

void Crossover(M, F, T)
register int M, F, T;
/**********************************************************************
WHAT: Creates two new offsprings from parents.  The offsprings are born
      in the alternate population buffer.  Therefore, this routine 
      write to every data bit in the alternate buffer.  However, to 
      prevent every generation from simply be a clone of the last, there
      is a NCrs% chance that the bits of the parents wil be swapped at a
      random point.
IN:   int M : One of the parents
      int F : The other parent
      int T : The offsprings number in the new generation
***********************************************************************/
{
   register int i, z;

   z=RangeRand(NObj);
   for(i=0; i<z; i+=1) 
   {
      Chrome[T][1-G].Bit[i]=Chrome[F][G].Bit[i];
      Chrome[T+1][1-G].Bit[i]=Chrome[M][G].Bit[i];
   } 
   if(RangeRand(100)<NCrs)
      for(i=z; i<NObj; i+=1)
      {
         Chrome[T][1-G].Bit[i]=Chrome[M][G].Bit[i];
         Chrome[T+1][1-G].Bit[i]=Chrome[F][G].Bit[i];
      }
   else 
      for(i=z; i<NObj; i+=1) 
      {
         Chrome[T][1-G].Bit[i]=Chrome[F][G].Bit[i];
         Chrome[T+1][1-G].Bit[i]=Chrome[M][G].Bit[i];
      }
}

void Select()
/**********************************************************************
WHAT: This routine decides which of the strings are going to be parents.
      The selection scheme is based on the roulette wheel although it
      does not look it from the code.  Anyhow, after two parents are
      choosen, they are sent to crossover.  This is done NPop/2 times
      which creates NPop members for the next generation.  
***********************************************************************/
{
   register int t, i, X, M, F;
   int Wheel[NPop], TotFit=0;
   
   for(t=0; t<NPop; t+=1) 
   {
      TotFit+=Chrome[t][G].Fitness;
      Wheel[t]=TotFit;
   }
   for(t=0; t<NPop; t+=2)
   {
      X=RangeRand(TotFit); i=0;
      while((Wheel[i]<X)&&(i<NPop)) i+=1; M=i;
      if(M>=NPop) M=RangeRand(NPop);
      X=RangeRand(TotFit); i=0;
      while((Wheel[i]<X)&&(i<NPop)) i+=1; F=i;
      if(F>=NPop) F=RangeRand(NPop);
      Crossover(M, F, t);
   }
}

void Mutation()
/**********************************************************************
WHAT: This routine mutates chromosomes by changing 0 to 1 and vice
      versa.  There is a NMut percent chance that any 0 or 1 will be
      changed.
***********************************************************************/
{
   register int t, i;
   
   for(t=0; t<NPop; t+=1)
   {
      for(i=0; i<NObj; i+=1)
      {
         if(RangeRand(100)<NMut)
           Chrome[t][1-G].Bit[i]=1-Chrome[t][1-G].Bit[i];  
      }
   }  
}


void main()
/**********************************************************************
WHAT: This is the main routine of this simple genetic algorithm.  Every-
      thing is quite standard except that for G which keeps track of 
      the 
        
***********************************************************************/
{
   int t, OptGen, AtGen=0, OptTot=0, Gen=0;
   
   G=0;
   GetData();   
   InitPop();
   while(Gen<1000)
   {
      Gen+=1;
      OptGen=Evaluate();
      if(OptGen>OptTot)
      {
         AtGen=Gen;
         OptTot=OptGen;
      }
      Select();
      Mutation(); 
      G=1-G;
   }
   printf("Optimum Value: %d\nFound at Generation: %d\n", OptTot, AtGen);
   scanf("%d",t);
}