unit1.c

一个生产工序安排的算法（采用遗传算法

    }
else
    {
    for (i = 0; i < NVARS; i++)
       population[worst_mem].gene[i] = population[POPSIZE].gene[i];
    population[worst_mem].fitness = population[POPSIZE].fitness;
    } 
}
/**************************************************************/
/* Selection function: Standard proportional selection for    */
/* maximization problems incorporating elitist model - makes  */
/* sure that the best member survives                         */
/**************************************************************/

void select(void)
{
int mem, i, j, k;
double sum = 0;
double p;

/* find total fitness of the population */
for (mem = 0; mem < POPSIZE; mem++)
      {
      sum += population[mem].fitness;
      }

/* calculate relative fitness */
for (mem = 0; mem < POPSIZE; mem++)
      {
      population[mem].rfitness =  population[mem].fitness/sum;
      }
population[0].cfitness = population[0].rfitness;

/* calculate cumulative fitness */
for (mem = 1; mem < POPSIZE; mem++)
      {
      population[mem].cfitness =  population[mem-1].cfitness +       
                          population[mem].rfitness;
      }

/* finally select survivors using cumulative fitness. */

for (i = 0; i < POPSIZE; i++)
      { 
      p = rand()%1000/1000.0;
      if (p < population[0].cfitness)
            newpopulation[i] = population[0];      
      else
            {
            for (j = 0; j < POPSIZE;j++)      
                  if (p >= population[j].cfitness && 
                              p<population[j+1].cfitness)
                        newpopulation[i] = population[j+1];
            }
      }
/* once a new population is created, copy it back */

for (i = 0; i < POPSIZE; i++)
      population[i] = newpopulation[i];      
}

/***************************************************************/
/* Crossover selection: selects two parents that take part in  */
/* the crossover. Implements a single point crossover          */
/***************************************************************/

void crossover(void)
{
int i, mem, one;
int first  =  0; /* count of the number of members chosen */
double x;

for (mem = 0; mem < POPSIZE; ++mem)
      {
      x = rand()%1000/1000.0;
      if (x < PXOVER)
            {
            ++first;
            if (first % 2 == 0)
                  Xover(one, mem);
            else
                  one = mem;
            }
      }
}
/**************************************************************/
/* Crossover: performs crossover of the two selected parents. */
/**************************************************************/

void Xover(int one, int two)
{
int i;
int point; /* crossover point */

/* select crossover point */
if(NVARS > 1)
   {
   if(NVARS == 2)
         point = 1;
   else
         point = (rand() % (NVARS - 1)) + 1;

   for (i = 0; i < point; i++)
        swap(&population[one].gene[i], &population[two].gene[i]);

   }
}







/*************************************************************/
/* Swap: A swap procedure that helps in swapping 2 variables */
/*************************************************************/

void swap(double *x, double *y)
{
double temp;

temp = *x;
*x = *y;
*y = temp;

}

/**************************************************************/
/* Mutation: Random uniform mutation. A variable selected for */
/* mutation is replaced by a random value between lower and   */
/* upper bounds of this variable                              */
/**************************************************************/

void mutate(void)
{
int i, j;
double lbound, hbound;
double x;

for (i = 0; i < POPSIZE; i++)
      for (j = 0; j < NVARS; j++)
            {
            x = rand()%1000/1000.0;
            if (x < PMUTATION)
                  {
                  /* find the bounds on the variable to be mutated */
                  lbound = population[i].lower[j];
                  hbound = population[i].upper[j];  
                  population[i].gene[j] = randval();
                  }
            }
}

/***************************************************************/
/* Report function: Reports progress of the simulation. Data   */
/* dumped into the  output file are separated by commas        */
/***************************************************************/

void report(void)
{
int i;
double best_val;            /* best population fitness */
double avg;                 /* avg population fitness */
double stddev;              /* std. deviation of population fitness */
double sum_square;          /* sum of square for std. calc */
double square_sum;          /* square of sum for std. calc */
double sum;                 /* total population fitness */

sum = 0.0;
sum_square = 0.0;

for (i = 0; i < POPSIZE; i++)
      {
      sum += population[i].fitness;
      sum_square += population[i].fitness * population[i].fitness;
      }

avg = sum/(double)POPSIZE;
square_sum = avg * avg * POPSIZE;
stddev = sqrt((sum_square - square_sum)/(POPSIZE - 1));
best_val = population[POPSIZE].fitness;

fprintf(galog, "\n%5d: %10.3f, %10.3f, %10.3f;", generation, 
                                      MAXTIME - best_val, MAXTIME - avg, stddev);
}

/**************************************************************/
/* Main function: Each generation involves selecting the best */
/* members, performing crossover & mutation and then          */
/* evaluating the resulting population, until the terminating */
/* condition is satisfied                                     */
/**************************************************************/

void main(void)
{
int i,j;

if ((galog = fopen("galog.txt","w"))==NULL)
      {
      exit(1);
      }
generation = 0;

fprintf(galog, "\n Comment:  ");
fprintf(galog, "\n   Machine: #0 to #%d", NMACHINE-1);
fprintf(galog, "\n   Works  : #0 to #%d", NVARS-1);
fprintf(galog, "\n\n Star Simulation...\n");
fprintf(galog, "\ngener-    best       average   standard\ntion      value      fitness   deviation\nnumber\n-----:  ---------,-----------,-----------;");

initialize();
evaluate();
keep_the_best();
while(generation<MAXGENS)
      {
      generation++;
      select();
      crossover();
      mutate();
      report();
      evaluate();
      elitist();
      }
fprintf(galog,"\n\n Simulation completed\n");
fprintf(galog,"\n ==========================================");
fprintf(galog,"\n Result report: \n");
fprintf(galog,"\n Best member: \n");

fprintf(galog,"\n  Works would be arranged on which machine: \n");   
for (i = 0; i < NVARS; i++)
   {
   fprintf (galog,"\n    * Works#%d is done on Machine#%d, consuming time = %fs",i,(int)(population[POPSIZE].gene[i]), time_consuming[(int)(population[POPSIZE].gene[i])][i]);
   }


fprintf(galog,"\n\n\n  Works on Each Machine: \n");   
for ( i = 0; i < NMACHINE ; i ++)
	{
	double sum;
	fprintf( galog, "\n    * Works on Machine#%d: ",i);  
	sum = 0;
	for( j = 0; j < NVARS; j ++)
		{
			if((int)(population[POPSIZE].gene[j]) == i) 
				{
				fprintf( galog, "#%d(%fs),  ",j,time_consuming[i][j]);
				sum += time_consuming[i][j];
				}
		}
	fprintf( galog, " Total Time consumed = (%fs)", sum);

	}   
   
fprintf(galog,"\n\n Best consuming time = %fs\n\n End of report!",MAXTIME - population[POPSIZE].fitness);
fclose(galog);
printf("Success\n");
}
/***************************************************************/