#include "genocop.h" #if DOS_SYS extern FILE *input,*output; extern int test_num; #endif /* Cummulative probability on crossover */ /* Random probability on mutation */ /* NO multiple hits per agent possible */ /********************************************************************************/ /* */ /* FUNCTION NAME : optimization() */ /* */ /* SYNOPSIS : void optimization(X,x1,x2,fin_mat,rc,tot_eq) */ /* */ /* DESCRIPTION : This procedure initializes the population */ /* with the values X passed from main, and */ /* evaluates them. After assigning weight */ /* for each member of the populaiton, a group */ /* of them are chosen to reproduce and a group */ /* is chosen to die. Genetic operators are */ /* applied and a new generation is produced */ /* to replace the members that died. This */ /* cycle continues for the number of times, */ /* user specifies in the input file */ /* */ /* FUNCTIONS CALLED : assign_probab(), */ /* evaluate(), */ /* find_cum_probab(), */ /* find_live_die(), */ /* find_parent(), */ /* ivector(), */ /* matrix(), */ /* oper1(), */ /* oper2(), */ /* oper3(), */ /* oper4(), */ /* oper5(), */ /* oper6(), */ /* print_matrix(), */ /* print_population(), */ /* sort(), */ /* vector(). */ /* */ /* CALLING FUNCITONS : main() */ /* */ /* */ /********************************************************************************/ void optimization(X,x1,x2,fin_mat,rc,tot_eq,a1_b) MATRIX fin_mat; VECTOR X,a1_b; IVECTOR x1,x2; INDEX rc; int tot_eq; { MATRIX new_genera, /*Temporary storage for the new generation*/ population, /*Population of x2 variables*/ print_pop, temp; VECTOR probab, /*Probability of agents to die or live*/ cum_probab, /*Cumilative probability of agents*/ t_vec; IVECTOR live, die; unsigned long generations; /*Total number of Generations*/ unsigned long count_gener= 1; /*Counter to keep track of the number of generations*/ unsigned long peak_cnt; int pop_size, /*Population size*/ MinMax, /*Minimization or Maximization problem 0 or 1 */ P, /*Total number of agents chosen to reproduce*/ P1, /*Number of parents for each of the 5 operators*/ P2, P3, P4, P5, P6, P7, j1, j2, j3, j4, j5, j6, j7, oper, B, /*Parameter for the 3rd operator - nonuniform mutation*/ STEP, /*Parameter for the 5th operator - simple arithmetical crossover*/ x2_vari = rc.c-2, first, /*Index of the parent to mutate*/ first_live, /*Index of the two parents for crossover parents*/ second_live, first_die, /*Index of the two parents for crossover death*/ second_die, tot, /*total number of chosen parents not used*/ i, j, k; float Q, /*Probability of the best agent*/ A, /*Parameter for the 4th operator - whole arithmetical cross over*/ Teval, /*Evaluation of the best agent*/ initial_val; /*Initial value of the population */ float peak_val; int x,y; FLAG same; float**new; /*Reading from the file the population size, total number of generations, total number*/ /*of times each of the 5 operators to be applied, probability of the best agent,*/ /*minimization or maximization problem, the parameters for the operators*/ fscanf(input,"%d %lU %d %d %d %d %d %d %d",&pop_size,&generations,&P1,&P2,&P3,&P4,&P5,&P6,&P7); fscanf(input,"%f ",&Q); fscanf(input,"%d ",&MinMax); fscanf(input,"%d ",&B); fscanf(input,"%d ",&STEP); fscanf(input,"%d ",&test_num); fclose(input); fprintf(output,"\n\n"); fprintf(output,"Test case number : %d\n", test_num); fprintf(output,"Number of operators : %d %d %d %d %d %d %d\n", P1, P2, P3, P4, P5, P6, P7); fprintf(output,"Number of generations : %lu\n",generations); fprintf(output,"Population size : %d\n", pop_size); fprintf(output,"Parameter B : %d\n", B); fprintf(output,"Parameter Q : %f\n", Q); /*P is the total number of parents needed for applying all the operators*/ P = P1 + P2 + P3 + P4 + P5 + P6 + P7; if(P > pop_size) { printf("The total number of operators greater than population\n"); fprintf(output,"The total number of operators greater than population\n"); fclose(output); exit(1); } peak_val = 0; peak_cnt = 0; /*Space allocation for all the vectors and matrices involved*/ population = matrix(1,pop_size,0,x2_vari+1); print_pop = matrix(1,pop_size,0,x2_vari+tot_eq+1); new_genera = matrix(1,pop_size,1,x2_vari+1); temp = matrix(1,2,1,x2_vari); probab = vector(1,pop_size); t_vec = vector(1,x2_vari); cum_probab = vector(1,pop_size); live = ivector(1,pop_size); die = ivector(1,pop_size); /*Initial population with all identical agents, whose values were got randomly*/ for(i=1; i<=x2_vari; i++) for(j=1; j<=pop_size; j++) { population[j][i] = X[x2[i]]; population[j][x2_vari+1] = 0; } fprintf(output,"\nThe initial point of the population is\n"); print_vector(X,1,tot_eq+x2_vari); fprintf(output,"\n\n"); fprintf(output,"\n\nGeneration#\t Solution Value\n"); /*Evaluation of the initial population with the given function*/ population[1][0] = evaluate(X); for(j=2; j<=pop_size; j++) population[j][0] = population[1][0]; fprintf(output,"\n%7d \t%18.8f\n", 0, population[2][0]); /*Assigning probability of survival for each of the agent, with the*/ /*probability provided by the user for the best agent*/ assign_probab(probab,pop_size,Q); /*Finding the cumulative probability of the agents*/ find_cum_probab(cum_probab,probab,pop_size); Teval = population[1][0]; for(j=1; j<=pop_size; j++) new_genera[j][x2_vari+1] = 0.0; /*Reproducing and evaluating for the total number of generations times*/ do { /*Initializing the live and die vectors*/ for(j=1; j<=pop_size; j++) { live[j] = die[j] = 0; for(i=0; i<=x2_vari + 1; i++) new_genera[j][i] = population[j][i]; } /*Finding the agents that will die and the agents that will reproduce*/ find_live(cum_probab,live,pop_size,P4+P5+P7); j1=j2=j3=j4=j5=j6=j7=0; while(j1+j2+j3+j4+j4+j5+j5+j6+j7+j7 < P) { oper = irange_ran(1,7); switch (oper) { case 1: /*Applying the first operator, uniform mutation, for the number of times specified*/ if (j1 != P1) { do first = irange_ran(2,pop_size); while (die[first] == 1); die[first] = 1; new_genera[first][x2_vari+1] = 1.0; for(i=1; i<=x2_vari; i++) t_vec[i] = population[first][i]; oper1(t_vec,fin_mat,rc); for(i=1; i<=x2_vari; i++) new_genera[first][i] = t_vec[i]; j1++; } break; case 2: /*Applying the second operator, boundary mutation, for the number of times specified*/ if (j2 != P2) { do first = irange_ran(2,pop_size); while (die[first] == 1); die[first] = 1; new_genera[first][x2_vari+1] = 2.0; for(i=1; i<=x2_vari; i++) t_vec[i] = population[first][i]; oper2(t_vec,fin_mat,rc); for(i=1; i<=x2_vari; i++) new_genera[first][i] = t_vec[i]; j2++; } break; case 3: /*Applying the third operator, non-uniform mutation, for the number of times specified*/ if (j3 != P3) { do first = irange_ran(2,pop_size); while (die[first] == 1); die[first] = 1; new_genera[first][x2_vari+1] = 3.0; for(i=1; i<=x2_vari; i++) t_vec[i] = population[first][i]; oper3(t_vec,fin_mat,rc,generations,count_gener,B); for(i=1; i<=x2_vari; i++) new_genera[first][i] = t_vec[i]; j3++; } break; case 4: /*Applying the fourth operator, whole arithmetical crossover*/ if (j4 != (int) P4/2) { /*Find two distinct parents for crossover operator 4*/ first_live = find_parent(live,pop_size); second_live = find_parent(live,pop_size); same = TRUE; for(i=1; i<=x2_vari; i++) if (population[first_live][i] != population[second_live][i]) same = FALSE; if (!same) { first_die = find_die(cum_probab, die ,pop_size); second_die = find_die(cum_probab, die ,pop_size); die[first_die] = 1; die[second_die] = 1; new_genera[first_die][x2_vari+1] = 4.0; new_genera[second_die][x2_vari+1] = 4.0; for(i=1; i<=x2_vari; i++) { temp[1][i] = population[first_live][i]; temp[2][i] = population[second_live][i]; } oper4(temp[1],temp[2],x2_vari); for(i=1; i<=x2_vari; i++) { new_genera[first_die][i] = temp[1][i]; new_genera[second_die][i] = temp[2][i]; } } j4++; } break; case 5: /*Applying the fifth operator, simple arithmetical crossover*/ if (j5 != (int) P5/2) { /*Find two distinct parents for crossover operator 5*/ first_live = find_parent(live,pop_size); second_live = find_parent(live,pop_size); same = TRUE; for(i=1; i<=x2_vari; i++) if (population[first_live][i] != population[second_live][i]) same = FALSE; if (!same) { first_die = find_die(cum_probab, die ,pop_size); second_die = find_die(cum_probab, die ,pop_size); die[first_die] = 1; die[second_die] = 1; new_genera[first_die][x2_vari+1] = 5.0; new_genera[second_die][x2_vari+1] = 5.0; for(i=1; i<=x2_vari; i++) { temp[1][i] = population[first_live][i]; temp[2][i] = population[second_live][i]; } oper5(temp[1],temp[2],STEP,rc,fin_mat); for(i=1; i<=x2_vari; i++) { new_genera[first_die][i] = temp[1][i]; new_genera[second_die][i] = temp[2][i]; } } j5++; } break; case 6: /*Applying the sixth operator, whole non-uniform mutation, for the number of times specified*/ if (j6 != P6) { do first = irange_ran(2,pop_size); while (die[first] == 1); die[first] = 1; new_genera[first][x2_vari+1] = 6.0; for(i=1; i<=x2_vari; i++) t_vec[i] = population[first][i]; oper6(t_vec,fin_mat,rc,generations,count_gener,B); for(i=1; i<=x2_vari; i++) new_genera[first][i] = t_vec[i]; j6++; } break; case 7: /*Applying the seventh operator*/ if (j7 != (int) P7/2) { /*Find two distinct parents for operator 7*/ first_live = find_parent(live,pop_size); second_live = find_parent(live,pop_size); same = TRUE; for(i=1; i<=x2_vari; i++) if (population[first_live][i] != population[second_live][i]) same = FALSE; if (!same) { first_die = find_die(cum_probab, die ,pop_size); die[first_die] = 1; new_genera[first_die][x2_vari+1] = 7.0; for(i=1; i<=x2_vari; i++) if (first_live < second_live) /* first agent is better agent */ { temp[2][i] = population[first_live][i]; temp[1][i] = population[second_live][i]; } else /* second agent is better agent */ { temp[2][i] = population[second_live][i]; temp[1][i] = population[first_live][i]; } oper7(temp[1],temp[2],rc,fin_mat); for(i=1; i<=x2_vari; i++) new_genera[first_die][i] = temp[1][i]; } j7++; } } } /*Replace the population with the new generation */ new = new_genera; new_genera = population; population = new; /*Evaluate each of the agents in the new population*/ for(i=1; i<=pop_size; i++) { if (population[i][x2_vari+1] != 0) /* do not reevaluate if no changes were made */ { if (tot_eq != 0) { for(j=1; j<=x2_vari + tot_eq; j++) X[j] = 0.0; find_X(fin_mat,population[i],X,x2_vari,tot_eq,x1,x2,a1_b); } else for(j=1; j<=x2_vari; j++) X[j] = population[i][j]; population[i][0] = evaluate(X); } } /*Sort the new population based on their evaluation function*/ sort(MinMax,population,pop_size); switch(MinMax) { case 0: if(Teval > population[1][0]) { Teval = population[1][0]; fprintf(output,"%7lu \t%18.8f\n",count_gener,population[1][0]); peak_cnt = count_gener; peak_val = population[1][0]; } break; case 1: if(Teval < population[1][0]) { Teval = population[1][0]; fprintf(output,"%7lu \t%18.8f\n",count_gener,population[1][0]); peak_cnt = count_gener; peak_val = population[1][0]; } break; } #if DOS_SYS gotoxy(5,7); #endif /* printf("Generation# %7lu %18.8f ",count_gener, population[1][0]); */ /*Increment the number of iteration*/ count_gener++; } while (count_gener <= generations); fprintf(output,"\nBest solution was found at generation %lu (solution value = %.8f)\n",peak_cnt,peak_val); fprintf(output,"\n\nBest solution found:\n\n"); /* print best solution */ find_X(fin_mat,population[1],X,x2_vari,tot_eq,x1,x2,a1_b); for(j = 1; j <= x2_vari+tot_eq; j++) fprintf(output," X[%2d] :\t%18.8f\n",j,X[j]); /* print final population */ /* for(i=1; i<=pop_size; i++) { if (tot_eq != 0) { for(j=1; j<=x2_vari + tot_eq; j++) X[j] = 0.0; find_X(fin_mat,population[i],X,x2_vari,tot_eq,x1,x2,a1_b); for(j=1; j<=x2_vari + tot_eq; j++) print_pop[i][j] = X[j]; } else for(j=1; j<=x2_vari; j++) print_pop[i][j] = X[j] = population[i][j]; print_pop[i][0] = evaluate(X); print_pop[i][x2_vari+tot_eq+1] = population[i][x2_vari+1]; } fprintf(output,"\n\nThe Final Population:\n\n"); fprintf(output," Solution Value\t Agent variables: X[1] X[2] ...\n\n"); print_population(output, pop_size,x2_vari+tot_eq+1,print_pop); */ } /********************************************************************************/ /* */ /* FUNCTION NAME : sort() */ /* */ /* SYNOPSIS : void sort(MinMax, population,pop_size) */ /* */ /* DESCRIPTION : This function sorts the population, in the */ /* ascending or the descending order of the */ /* evaluation function, depending on whether */ /* it is a maximization or a minimization */ /* function, respectively. */ /* */ /* As an alternative, the sortq function below */ /* can be used, That sorting function uses */ /* the quicksort algorithm. */ /* */ /* */ /* FUNCTIONS CALLED : swap() */ /* */ /* CALLING FUNCITONS : optimization() */ /* */ /* AUTHOR : Swarnalatha Swaminathan */ /* */ /* DATE : 1/17/92 */ /* */ /* */ /* REV DATE BY DESCRIPTION */ /* --- ---- -- ----------- */ /* A 9/11/92 Tom Logan Rewrote */ /* */ /********************************************************************************/ void sort(MinMax,population,pop_size) int MinMax, /*Tells whether it is a maximizaiton or a minimization function*/ pop_size; /*Population size*/ MATRIX population;/*Array of population*/ { int i,j,k; /*If MinMax is 0 sorts in the descending order, and*/ /*if it is 1 sorts in the ascending order*/ /*Sorted in ascending or descending order, based on*/ /*the evaluated values of each of the agents*/ switch(MinMax) { case 0 : for(i=1; i<=pop_size; i++) for(j=i+1; j<=pop_size; j++) if(population[i][0] > population[j][0]) swap(&population[i],&population[j]); break; case 1 : for(i=1; i<=pop_size; i++) for(j=i+1; j<=pop_size; j++) if(population[i][0] < population[j][0]) swap(&population[i],&population[j]); break; default: fprintf(output,"Incorrect data: Must be a 0 or 1"); exit(1); } } /********************************************************************************/ /* */ /* FUNCTION NAME : swap() */ /* */ /* SYNOPSIS : void swap(x,y) */ /* */ /* DESCRIPTION : This function interchanges the values of */ /* x and y. */ /* */ /* FUNCTIONS CALLED : None */ /* */ /* CALLING FUNCITONS : sort() */ /* */ /* AUTHOR : Swarnalatha Swaminathan */ /* */ /* DATE : 1/17/92 */ /* */ /* */ /* REV DATE BY DESCRIPTION */ /* --- ---- -- ----------- */ /* */ /* */ /********************************************************************************/ void swap(x,y) float **x,**y; { float *temp; temp = *x; *x = *y; *y = temp; } /********************************************************************************/ /* */ /* FUNCTION NAME : find_parent() */ /* */ /* SYNOPSIS : int find_parent(live,pop_size) */ /* */ /* DESCRIPTION : This function returns the index of the */ /* agent in the population, which is to be */ /* chosen for reproduction. */ /* */ /* FUNCTIONS CALLED : irange_ran() */ /* */ /* CALLING FUNCITONS : optimization() */ /* */ /* AUTHOR : Swarnalatha Swaminathan */ /* */ /* DATE : 1/17/92 */ /* */ /* */ /* REV DATE BY DESCRIPTION */ /* --- ---- -- ----------- */ /* */ /* */ /********************************************************************************/ int find_parent(live,pop_size) int pop_size; /*Population size*/ IVECTOR live; /*Vector containing the number of times each agent*/ /*is going to reproduce*/ { int i,temp,t1,tot=0; /*Finding the total number of parents to reproduce*/ for(i=1; i<=pop_size; i++) tot = tot + live[i]; if(tot==0) { printf("No agents to select\n"); exit(1); } /*Choosing one of them randomly*/ temp = irange_ran(1,tot); tot = 0; i = 1; do{ if(live[i]!=0) t1 = i; tot = tot + live[i++]; }while(tot cum_probab[i]) && (i< pop_size)); /*Chosing the parent with that probability to reproduce*/ if(count < P) { live[i]++; count++; } }while(count < P); } /********************************************************************************/ /* */ /* FUNCTION NAME : find_die() */ /* */ /* SYNOPSIS : void find_die(cum_probab,die,pop_size,P4+P5) */ /* */ /* DESCRIPTION : This function finds the agents from the */ /* population, who are going to die. / /* */ /* FUNCTIONS CALLED : frange_ran() */ /* */ /* CALLING FUNCITONS : optimization() */ /* */ /* AUTHOR : Tom Logan */ /* */ /* DATE : 9/15/92 */ /* */ /* */ /* REV DATE BY DESCRIPTION */ /* --- ---- -- ----------- */ /* */ /* */ /********************************************************************************/ int find_die(cum_probab,die,pop_size) VECTOR cum_probab; /*Cumulative probability*/ IVECTOR die; /*Agents that are going to die*/ int pop_size; /*Population size*/ { float random; int i; int done = FALSE; do { /*Choosing a random cumulative probability*/ random = frange_ran(0.0,1.0); i=0; /*Finding the agent with the chosen cumulative probability*/ do{ i++; } while((random > cum_probab[i]) && (i< pop_size)); /*Chosing the agent to die*/ if ((die[pop_size+1-i] == 0) && (i < pop_size)) done = TRUE; } while(!done); return(pop_size+1-i); } /********************************************************************************/ /* */ /* FUNCTION NAME : find_X() */ /* */ /* SYNOPSIS : void find_X(final,agen.X,x2_vari,tot_eq,x1, */ /* x2)*/ /* */ /* DESCRIPTION : This function finds the value of all the */ /* variables in the original problem, with */ /* the values of the remaining variables. */ /* */ /* FUNCTIONS CALLED : none */ /* */ /* CALLING FUNCITONS : optimization() */ /* */ /* AUTHOR : Swarnalatha Swaminathan */ /* */ /* DATE : 1/17/92 */ /* */ /* */ /* REV DATE BY DESCRIPTION */ /* --- ---- -- ----------- */ /* */ /* */ /********************************************************************************/ void find_X(final,agent,X,x2_vari,tot_eq,x1,x2,a1_b) MATRIX final; VECTOR agent,X,a1_b; IVECTOR x1,x2; int x2_vari,tot_eq; { int i,j; for(j=1; j<=x2_vari; j++) X[x2[j]] = agent[j]; for(j = 1; j<=tot_eq; j++) { X[x1[j]] = a1_b[j]; for(i=1; i<=x2_vari; i++) X[x1[j]] = X[x1[j]] + agent[i] * final[j+x2_vari][i+1]; } }