operators.c

genetic algorithm c code

/*=================================================     
       file : operators.c
 
    purpose : messy GA operators 
 
  developed : 1991

     author : Kalyanmoy Deb
     bugfix : Alex Kosorukoff
====================================================*/

#include "mga.ext"


INDV_ID select_pop()
/*  determine which selection operator  */
{
	if (gen < init_select_gen)
		return (init_select());
	else 
	{
		if (thresholdingflag)
			return(thresholding_select());
		else
			return(normal_select());
	}
}


INDV_ID select(first, second)
INDV_ID first, second;
/*  selects the better of first and second  */
{
	if (oldpop[first].fitness == oldpop[second].fitness) {
		if (tiebreakingflag)
			return((oldpop[first].chromlen < \
				oldpop[second].chromlen) ? first : second);
		else 
			return(flip(0.5) ? first : second);
	}
	else if (oldpop[first].fitness > oldpop[second].fitness)
	{
		return((maximizationflag) ? first : second);
	}
	else 
	{
		return((maximizationflag) ? second : first);
	}
}


INDV_ID init_select()
/*  tournament selection operator without shuffling  */
{
	INDV_ID first,second;

	if (pick >= popsize-1)
		pick = 0;
	first = pick;
	second = pick + 1;
	pick += 2;
	return (select(first, second));
}


INDV_ID normal_select()
/*  tournament selection operator with shuffling  */
{
	INDV_ID first,second;

	if (pick >= popsize-1)
	{
		pick = 0;
		shuffle_pop();
	}
	first = shuffle[pick];
	second = shuffle[pick+1];
	pick += 2;
	return (select(first, second));
}


INDV_ID thresholding_select()
/*  tournament selection operator with thresholding  */
{
	register int i,j,k;
	INDV_ID first, second, fittest, secondid;
	int num1, num2, count, temp, threshold;
	BOOLEAN flag;
	unsigned *rawgn1, *rawgn2;

	if (pick >= popsize-1)
	{
		pick = 0;
		shuffle_pop();
	}
	/*  choose the first individual, default is first  */
	fittest = first = shuffle[pick];
	rawgn1 = oldpop[first].fullgene;
	num1 = oldpop[first].genelen;

	for (k=1,flag=0; (k<=shuffle_num && !flag); k++)
	{
		/*  choose the second individual  */
		secondid = pick + k;
		/*  if required, scroll to the begining of the array */
		if (k >= (popsize - pick))
			secondid = k - (popsize - pick);
		second = shuffle[secondid];
		rawgn2 = oldpop[second].fullgene;
		num2 =  oldpop[second].genelen;

		/*  count the number of matched genes  */
		count = matched_genes(rawgn1, rawgn2);

		/*  calculate the threshold value  */
		threshold = (num1 * num2);
		threshold /= problem_length;

		if (count > threshold)
		/*  if count > threshold, found a match, perform selection */
		{
			flag = 1;
			temp = shuffle[secondid];
			shuffle[secondid] = shuffle[pick + 1];
			shuffle[pick + 1] = temp;
			fittest = select(first, second);
			pick++;
		}
	}
	pick++;
	return (fittest);
}

int matched_genes(rawgn1,rawgn2)
unsigned *rawgn1;
unsigned *rawgn2;
/*  count the number of matched genes  */
{
	register int i, j;
	int num = 0;
	unsigned rawgn, mask = 1;

	for (i = 0; i < bytesize; i++)
	{
		/*  get the template of common genes */
		rawgn = (rawgn1[i] & rawgn2[i]);

		/*  count the number of 1's in the template  */
		for (j = 0; j < bytelimit[i]; j++)
		{
			if (((rawgn >> j) & mask) == 1)
				num++;
		}
	}
	return(num);
}


void cut_and_splice(chr1,chr2)
struct INDIVIDUAL chr1,chr2;
/*  cut and splice operators  */
{
	int chr3flag, chr4flag;       /* chr4flag appended -- AK */
	struct INDIVIDUAL chr3;
	struct INDIVIDUAL chr4;

	/*  if first chromosome needs to be cut  */
	chr4flag = flip(cut_prob * (chr1.chromlen - 1));   /* AK */
	if (chr4flag)
	{
		cut(&chr1,&chr4);
		/* if chr4 is not empty first element in chrom_stack is chr4 */
		if (chr4.firstgene != NIL)
			push_stack(&chrom_stack,chr4);
	}

	chr3.firstgene = NIL;
	/*  if second chromosome needs to be cut  */
        chr3flag = flip(cut_prob * (chr2.chromlen - 1));   /* AK */
	if (chr3flag)
		cut(&chr2,&chr3);

	/*  next element in the chrom_stack is chr2  */
	push_stack(&chrom_stack,chr2);

	/*  if chr3 is not empty, next element in the stack is chr3  */
	if (chr3flag)		/* modified by AK */
				/* the zero-length chromosome check  */
				/* is no longer needed here */
		push_stack(&chrom_stack,chr3);

	/*  top most element is chr1  */
	push_stack(&chrom_stack,chr1);

	/*  check elements in the stack and splice  */
	do  {
	}   while (test_splice());
}


BOOLEAN test_splice()
/*  splice two members of the stack, send 1 if there is a member left,
    0 otherwise  */
{
	struct INDIVIDUAL chr1,chr2;

	/*  get the first member  */
	if (pop_stack(&chrom_stack,&chr1))
	{
		if (flip(splice_prob))
		{
			/*  check for another member in the stack  */
			/*  splice if yes  */
			if (pop_stack(&chrom_stack,&chr2))
				splice(&chr1,&chr2);
		}
		push_stack(&newchrom_stack,chr1);
		return(1);
	}
	else
		return(0);
}


void cut(chr1,chr2)
struct INDIVIDUAL *chr1,*chr2;
/*   cut chr1 into two pieces: chr1, chr2   */
{
	register int i;
	struct GENE *temp;
	int cut_site;
	char msg[PAGEWIDTH];

	temp = (*chr1).firstgene;

	/* find out cut site  */
	cut_site = rnd(1,(*chr1).chromlen-1);   /* modified -- AK */

	/*  cut chr1 at cut_site  */
	for (i = 1; i < cut_site; i++)
		temp = temp->nextgene;

	/*   assign other members of chr1 and chr2  */
	(*chr2).firstgene = temp->nextgene;
	(*chr2).lastgene = (*chr1).lastgene;
	(*chr1).lastgene = temp;
	temp->nextgene = NIL;
	(*chr2).chromlen = (*chr1).chromlen - cut_site;
	(*chr1).chromlen = cut_site;

	/*  allocate memory for chr2 fullchrom and fullgene  */
	if(!((*chr2).fullchrom = (unsigned *)malloc(bytesize*sizeof(unsigned)))) {
		sprintf(msg, "Insufficient memory for fullchrom\n");
		print_error(msg);
	}
	if(!((*chr2).fullgene = (unsigned *)malloc(bytesize*sizeof(unsigned)))) {
		sprintf(msg, "Insufficient memory for fullgene\n");
		print_error(msg);
	}
}


void splice(chr1,chr2)
struct INDIVIDUAL *chr1,*chr2;
/*   splice chr1 and chr2 to chr1  */
{
	/*  chr2 is appended behind chr1  */
	(*chr1).lastgene->nextgene = (*chr2).firstgene;
	(*chr1).lastgene = (*chr2).lastgene;
	(*chr1).chromlen = (*chr1).chromlen + (*chr2).chromlen;

	/*  destroy chr2 fullchrom and fullgene */
	free((*chr2).fullchrom);
	free((*chr2).fullgene);
}


void mutation(chr)
struct INDIVIDUAL *chr;
/*  if mutation probabalities are greater than zero, perform mutation  */
{
	register int i;
 	struct GENE *temp;

	if ((allelic_mut_prob > 0.0) || (genic_mut_prob > 0.0)) {
		temp = (*chr).firstgene;
		while (temp != NIL)
		{
			if (flip(allelic_mut_prob))
			/*   perform allelic mutation  */
			{
				if (temp->allele == 1)
					temp->allele = 0;
				else 
					temp->allele = 1;
				allelicmutation++;
			}
			if (flip(genic_mut_prob))
			/*  perform genic mutation  */
			{
				temp->genenumber = \
					genic_mutation(temp->genenumber);
				genicmutation++;
			}
			temp = temp->nextgene;
		}
	}
}


GENE_ID genic_mutation(num)
GENE_ID num;
/*  change the genenumber to other  */
{
	GENE_ID n;

	do {
		n = rnd(0, problem_length-1);
	}  while (n == num);
	return(n);
}