使用人工智能的遗传算法来解N皇后问题

				// Queen.cpp: implementation of the Queen class.
				//
				//////////////////////////////////////////////////////////////////////
				
				#include "stdafx.h"
				#include "Queen_GA.h"
				#include "Queen.h"
				
				#ifdef _DEBUG
				#undef THIS_FILE
				static char THIS_FILE[]=__FILE__;
				#define new DEBUG_NEW
				#endif
				
				//////////////////////////////////////////////////////////////////////
				// Construction/Destruction
				//////////////////////////////////////////////////////////////////////
				
				Queen::Queen(int N,int iteration,float mutate,int iChBoard)
				{
					clear();
					srand( (unsigned)time(0) );// 设置随机数种子
					Population=N;
					Iteration=iteration;
					MutationRate=mutate;
					ChessBoradLenght=iChBoard;
				}
				
				Queen::~Queen()
				{
				
				}
				
				
				void Queen::initialColony() //随机生成初始群体,ChromosomMatrix[i][j]的每一列表示一个染色体，ChromosomeMatrix[i][j]表示第j个染色体的第i行的皇后所在的位置
				{
					int random;
					bool bCheck;
					for (int index=0;index					{
						for (int a=0;a						{
							random=rand();
							bCheck=1;
							for(int b=0;b								if(random%ChessBoradLenght==ChromosomeMatrix[b][index])	bCheck=0;
								if(bCheck)ChromosomeMatrix[a][index]=random%ChessBoradLenght;
								else a--;
						}
					}
				
				}
				
				int Queen::costFuction(int K)//计算第K个染色体的适应值，值越小适应度越强，为0时适应度最大，矩阵每一列表示一个染色体
				{
					int costValue=0;
					int m,n;
					int i,j;
					for(i=0;i					{	
						j=ChromosomeMatrix[i][K];
						m=i+1;
						n=j-1;
						while(m=0)
						{
							if(area[m][n]==1)//该位置有皇后
							{
								costValue++;//有一对皇后互相攻击，costValue加1
							}
							m++;
							n--;
						}
				
						m=i+1;
						n=j+1;
						while(m						{		
							if(area[m][n]==1)
							{
								
								costValue++;//有一对皇后互相攻击，costValue加1
							}
							m++;
							n++;
						}
				
						
				
						m=i-1;
						n=j-1;
						while(m>=0 && n>=0)
						{		
							if(area[m][n]==1)
							{
								
								costValue++;//有一对皇后互相攻击，costValue加1
							}
							m--;
							n--;
						}
						
				
						m=i-1;
						n=j+1;
						while(m>=0 && n						{		
							if(area[m][n]==1)
							{
								
								costValue++;//有一对皇后互相攻击，costValue加1
							}
							m--;
							n++;
						}
					}
				
					return costValue;
				
				}
				
				void Queen::chromosomeSort()  //对每一代的染色体从适应度的好到坏排序
				{
					bool k=1;
					int Temp;
					while(k)
					{
						k=0;
						for(int i=0;i						{
							if(CostMatrix[i]>CostMatrix[i+1])	
							{
								Temp=CostMatrix[i];
								CostMatrix[i]=CostMatrix[i+1];
								CostMatrix[i+1]=Temp;
								
							for(int j=0;j							{
								Temp=ChromosomeMatrix[j][i];
								ChromosomeMatrix[j][i]=ChromosomeMatrix[j][i+1];
								ChromosomeMatrix[j][i+1]=Temp;
							}			
							k=1;
							}
						}
					}
				
				}
				
				void Queen::mating()//父代交配繁殖新一代
				{
					int TempMatrix[30][2];
					int TempMatrix0[30],TempMatrix1[30];
					int Temp,j,k;
				
					for (int index=0;index						for (int t=0;t						{
							
							for(int i=0;i							{
								TempMatrix0[i]=ChromosomeMatrix[i][2*index];
								TempMatrix1[i]=ChromosomeMatrix[i][2*index+1];
							}
							for (i=0;i								if(CrossOverMatrix[i][2*index+t]==0)
								{
									for (j=0;j										if(TempMatrix0[j]!=100)	
										{
											TempMatrix[i][t]=TempMatrix0[j];
											Temp=TempMatrix0[j];
											TempMatrix0[j]=100;
											j=ChessBoradLenght-1;
										
											for (k=0;k											{
												if (TempMatrix1[k]==Temp)
												{
													TempMatrix1[k]=100;
													k=ChessBoradLenght-1;
												}
											}
										}
								}
								else
								{
									for (j=0;j										if(TempMatrix1[j]!=100)	
										{
											TempMatrix[i][t]=TempMatrix1[j];
											Temp=TempMatrix1[j];
											TempMatrix1[j]=100;
											j=ChessBoradLenght-1;
										
											for (k=0;k											{
												if (TempMatrix0[k]==Temp)
												{
													TempMatrix0[k]=100;
													k=ChessBoradLenght-1;
												}
											}
										}
								}
				
						for(i=0;i							ChromosomeMatrix[i][2*index+Population/2+t]=TempMatrix[i][t];
						
						}
				
				
				}
				
				void Queen::generateCrossOverMatrix()//生成交配位
				{
					// generate a matrix with random 0's and 1's
					int randomCrossOver;
					for (int index=0;index					{	for (int a=0;a						{
							randomCrossOver=rand();
							CrossOverMatrix[a][index]=randomCrossOver%2;
						}
					}
				}
				
				void Queen::mutate()    //变异
				{
					// a random for selecting chromosome
					// a random for selecting genes from selected chromosome
				
					int randomChromosome;
					int randomGen0,randomGen1;
					int Temp;
					// the following formula is a mutation formula to obtain the number of Mutation
					int NumberOfMutation=int(MutationRate*(Population-1)*ChessBoradLenght);
					
					for(int k=0;k					{
						randomChromosome=0;
						while((randomChromosome=rand()%Population)==0);// random chromosome exept number 0
							
						randomGen0=rand()%ChessBoradLenght;// random genes from chromosome
						while((randomGen1=rand()%ChessBoradLenght)==randomGen0);
						
						// Apply Mutation
						Temp=ChromosomeMatrix[randomGen0][randomChromosome];
						ChromosomeMatrix[randomGen0][randomChromosome]=ChromosomeMatrix[randomGen1][randomChromosome];
						ChromosomeMatrix[randomGen0][randomChromosome]=Temp;
					}
				
				}
				
				void Queen::clear()         //重置棋盘
				{
					for(int i=0;i					{
						for (int j=0;j							area[i][j]=0;
					}
				
				}
				
				void Queen::fillChess(int K)
				{
					// to Fill Area with Desired Solution Matrix
					clear();
					for(int i=0;i				
				}