gaqueen.cpp

这是一个解决皇后问题的遗传算法

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define Critical 1e-3
#define MAX_QUEENS 500		

int n ;                     //实际的皇后数
int goal ;					// 种群进化的目标，达到 goal 即返回程序
clock_t start, end ;		
time_t	start_time, end_time ;

typedef struct 
{
	int queen[MAX_QUEENS] ;
	int Fitness	;
} Population ; 

Population population[30+MAX_QUEENS/10] ;
int size ;           
int totFitness ;    

void init ()
{
	//srand (time(0)) ;
	printf("请输入皇后的个数：");
	scanf ("%d", &n) ;
	if(n<4)
	{
		printf("输入的皇后数最少为4!\n");
		exit(0);
	}
	goal = n;
	size = 30 + n / 10 ;
	start = clock () ;
	time (&start_time) ;	
	printf("Start: \t %s", ctime(&start_time));
}

int compare(const void *a,const void *b)
{
  return ((Population *)b)->Fitness - ((Population *)a)->Fitness;
}  

void UpdateFitnessScore (Population *p) 
{
	int i,r=0;
	int ru[2*MAX_QUEENS],rd[2*MAX_QUEENS];

	for(i=0;i<2*n;i++)
	{
		ru[i]=0;
		rd[i]=0;
	}
	for(i=0;i<n;i++)
	{
		ru[p->queen[i]-i+n]++;
		rd[p->queen[i]+i]++;
	}
	for(i=0;i<2*n;i++)
	{
		if(ru[i]>1) r+=ru[i]-1;
		if(rd[i]>1) r+=rd[i]-1;
	}
	p->Fitness=n-r;

}


void CreateMultiStartPopulation ()
{	
	int loop, i, j ;
	int tmp[MAX_QUEENS] ;
	
	for (loop = 0 ; loop < size ; loop ++)	
	{

		for (i = 0 ; i < n ; i++)
				tmp[i] = i ;

			for (i = 0 ; i < n ; i++)
			{
				j = rand() % (n - i) ;
				population[loop].queen[i] = tmp[j] ;
				tmp[j] = tmp[n - i - 1] ;
			}
			UpdateFitnessScore(&population[loop]) ;
	}
	/*
	int i,j,flag,loop;
	for(loop=0;loop<size;loop++)
	{
		flag=0;
		population[loop].queen[0]=(int)abs(rand()%n);
		for(i=1;i<n;i++)
		{
			do
			{
				population[loop].queen[i]=(int)abs(rand()%n);
				for(j=0;j<i;j++)
				{
					if(population[loop].queen[i]==population[loop].queen[j])
					{
						flag=1;
						break;
					}
					else flag=0;
				}
			}while(flag);
		}
	    UpdateFitnessScore(&population[loop]) ;
	}*/
}

// 双亲遗传中的变异算子
void MultiMutate (Population* p)
{
	int i, j, k,swap ;
	Population baby ;

	baby = *p ;
	for (i = 0 ; i < n / 4 ; i++)
	{
		do 
		{
			j = rand() % n ;
			k = rand() % n ;
		} while (j == k) ;	
			
		swap = baby.queen[k] ;
		baby.queen[k] = baby.queen[j] ;
		baby.queen[j] = swap ;

		UpdateFitnessScore(&baby) ;
		if (baby.Fitness > p->Fitness || (double)rand() / RAND_MAX < Critical)
		{
			*p = baby ;
			break ;
		}
	}
}

int RouletteWheelSelection()
{
	int selection = 0;
	int i ;

	double slice = (double)rand() / RAND_MAX;
	double addFitness = 0;
	for(i = 0; i < size ; i++)
	{
		addFitness +=  (double)population[i].Fitness / totFitness ;
		if(addFitness > slice)
		{
			selection = i;
			break;
		}
	}
	return selection;
}

void CrossOverFM (Population father, Population mother, Population *baby)
{
	int flag[MAX_QUEENS] ;
	int pos1, pos2, tmp ;
	int i, j ;

	do 
	{
		pos1 = rand() % n ;
		pos2 = rand() % n ;
	} while (pos1 == pos2) ;
	
	if (pos1 > pos2) { tmp = pos1 ; pos1 = pos2 ; pos2 = tmp; }

	for (j = 0 ; j < n ; j ++)
		flag[j] = 0 ;
	for (j = pos1; j <= pos2; j++)
		flag[father.queen[j]] = 1 ;

	for(i = 0, j = 0 ; i < n ; i++)
	{
		if (i < pos1 || i > pos2) {
			while (flag[mother.queen[j]]) j++ ;
			baby->queen[i] = mother.queen[j] ;
			j ++ ;
		}
		else baby->queen[i] = father.queen[i] ;
	}
	UpdateFitnessScore (baby) ;
}

void CrossOver () 
{
	int i ;
	int father, mother ;
	Population p[30 + MAX_QUEENS / 10] ;
	int count ;

	totFitness = 0 ;
	for (i = 0 ; i < size ; i++)
		totFitness += population[i].Fitness ;
	
	for (count = 0 ; count < size ; count++)
	{
		father = RouletteWheelSelection () ;
		mother = RouletteWheelSelection () ;
		CrossOverFM (population[father], population[mother], &p[count]) ; // 杂交,后代保存
	}

	for (count = 0 ; count < size ; count++)
		population[count] = p[count] ;
	
}

void PrintQueens (Population p)
{	
	int i, j ;  	
	printf("One solution looks like : \n") ;
	for (i = 0 ; i < n ; i++)
	{
		for (j = 0 ; j < n ; j++)
		{
			if (j == p.queen[i]) printf ("%d  ",j+1);
			else printf ("0  ") ;
		}
		printf ("\n") ;
	}
}

void main ()
{
	while(true)
	{
		int count=0;
		double secs ;
		init() ;	  
		CreateMultiStartPopulation() ;
			
		while (1)
		{
			count++;
			qsort(population, size, sizeof(Population), compare) ;
			MultiMutate (&population[0]) ;
			MultiMutate (&population[1]) ;
			if (population[0].Fitness == goal || population[1].Fitness ==  goal)
				break ;
			CrossOver () ;
		} 
		end = clock () ;
		time (&end_time) ;
		printf ("End:  \t %s", ctime(&end_time));
		secs = (double)(end - start) / CLOCKS_PER_SEC ;
        printf("Calculations took %.3lf second%s.\n", secs, (secs < 1 ? "" : "s"));
		printf("Generation is %d\n",count);
		PrintQueens(population[0].Fitness == goal ? population[0] : population[1]) ;
	}

}