gatest.cpp

求VC++基于遗传算法的流水线车间调度问题

// GATest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
//#include <GATest.h>
#include <stdio.h>
#include <iostream.h>
#include <math.h>
 #include <stdlib.h> 
#include <time.h> 


/*工件加工时间数组*/
int t[5][4]={{3,4,5,3},{9,5,8,3},{5,7,9,2},{2,5,9,1},{7,8,2,3}};
/*总体适应度值*/
float sumfit=0;  
int sumtime=0;   //种群总加工时间
/*染色体编码*/
int vold[10][5];
int totaltime[10]; /*各染色体加工总时间*/
int waittime[10]={0,0,4,0,5,0,6,0,0,0};/*各染色体加工等待时间*/
float voldfitness[10]={0,0,0,0,0,0,0,0,0,0};   /*记录染色体适应度*/
int comp;   /*记录历次迭代最优染色体的加工时间*/

struct chromnode    /*设计结构体使染色体和其适应度函数相关联*/
{	
	int chrom[5]; 
	float fitness;
}bestchrom,wrostchrom;

chromnode chrompop[10];   /*种群数组*/
chromnode newchrompop[10];    /*新种群数组*/
chromnode midchrompop[7];/*迭代中间优等种群*/


int temp[5][4];  /*按染色体工件序列加工时间矩阵*/
int tstart[5][4];  /*按染色体工件序列开始加工时间矩阵*/
int tover[5][4];   /*按染色体工件序列结束加工时间矩阵*/
int mupos[4][2];   /*记录染色体变异基因位位置*/

/*函数声明部分*/
int rndom(); /*在整数low和high之间产生一个随机整数*/
void randomsel(float* array,int num);     /*生成0－1之间的浮点数*/
void murandom(int posarray[1][2]);  /*产生二维随机数组记录染色体变异位置*/

void initialpop(int &v);    /*种群初始化*/
bool retreat(int i,int j);    /*查看染色体中是否有重复*/
int calcutime(int array[5][4]);    /*计算各染色体排列树的相关加工时间*/

void copychrom(chromnode &chromx,chromnode &chromy);    /*将chromy复制到chromx*/
void dispchrom(chromnode node,FILE *fp);       /*输出染色体的值*/
void dispchrompop(chromnode structarray[10],FILE *fp);       /*输出各染色体种群中的所有染色体的值*/
void reversechrom(int array[5],int posx,int posy);   /*将两个位置之间的染色体顺序倒置*/
void chromsort(chromnode pop[10]);    /*对染色体种群进行排序*/
void relatearray(int testchr[5]);  /*按照染色体序列将加工时间数组重新排列*/
void calfitness(int array[10][5]);      /*以数组为参数计算种群适应度的值并排序*/
void calchromfit(chromnode pop[10]);    /*以种群为参数计算种群适应度值——calfitness，并排序*/
int fittotime(chromnode para);   /*求出染色体适应度的加工时间*/
void caloptchrompt(chromnode pop[10]);     /*求出种群中最优染色体*/

void preselect(double pmsum[10],double randarray[10],int sortarray[10]);   /*确定选择染色体位置*/
void select(chromnode pop[10],chromnode subpop[10]);    /*选择算子*/
void mutation(chromnode pop[1]);    /*变异算子*/
void generate(chromnode pop[10],chromnode subpop[10]);     /*迭代产生新一代种群*/



int max(int a,int b)
{
	if(a>=b)
		return a;
	else
		return b;
}

int min(int a,int b)
{
	if(a<=b)
		return a;
	else
		return b;
}


int rndom() /*在整数low和high之间产生一个随机整数*/
{
     
     
     return (rand()%5+1) ;
	 
 
}

void randomsel(double* array,int num)
{
	for(int i = 0; i < num; i++) 
	{ 
	double fRand = (double)(rand()%1000)/1000 ;   //将随机数映射到0 -- 1区间内
		array[i] = fRand; 

	} 


}

void murandom(int posarray[4][2])   /*产生二维随机数组记录染色体变异位置*/
{
	for(int i=0;i<4;i++)
	{
		int posx=0;
		int posy=0;
		while(posx==posy)
		{
			posx=rand()%5;
			posy=rand()%5;
		}
		posarray[i][0]=min(posx,posy);
		posarray[i][1]=max(posx,posy);
		
	}

}

bool retreat(int i,int j)    /*查看染色体中是否有重复*/
{
	for(int t = 0;t < j;t++)
		{
			int seek = vold[i][t];
			
			if(seek == vold[i][j])
			{
				return true;
			}
			 
         }
	return false;
}


int calcutime(int array[5][4])    /*计算各染色体排列树的相关加工时间*/
{
	
	for(int m=0;m<5;m++)     /*计算机器加工工件的开始时间和结束时间*/
	{
		for(int n=0;n<4;n++)
			{
				   /*对每条染色体中的第一个工件的加工时间的计算*/
				
					if(m==0&&n==0)tstart[m][n]=0;      //机器最先开始时间为0
					
					if(m==0&&n>0)
					{
						tover[m][n-1] = tstart[m][n-1] + array[m][n-1];
						tstart[m][n] = tover[m][n-1];
						if(n==3)tover[m][n]=tstart[m][n]+array[m][n];

					}
					
					if(m>0&&n==0)
					{
						tstart[m][n]=tover[m-1][n];
						tover[m][n]=tstart[m][n]+array[m][n];   
					
					}
					
					
					if(m>0&&n>0)
					{
						tstart[m][n]=max(tover[m][n-1],tover[m-1][n]);    /*只有当此刻机器加工结束并且此刻需要加工的工件在前一个机器上已经加工完毕时才可以继续加工*/
						tover[m][n]=tstart[m][n]+array[m][n];
					}

			}
			
		}

		int totaltime=tover[4][3];
		return totaltime;
		
}

int calwaittime(int array[5][4])
{
	int wtime=0;
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<4;j++)
		{
			if(i>=1)
			{
				if(array[i-1][j+1] > array[i][j])
				wtime = wtime + array[i-1][j+1]-array[i][j];
			}
		}
	}

	return wtime;

}

void copychrom(chromnode &chromx,chromnode &chromy)    /*将chromy复制到chromx*/
{
	for(int w=0;w<5;w++)
	{
		chromx.chrom[w]=chromy.chrom[w];
	}
	chromx.fitness=chromy.fitness;
}


void reversechrom(int array[5],int posx,int posy)   /*将两个位置之间的染色体顺序倒置*/
{
	int temp;
	while(posx<=posy)
	{
		temp=array[posx];
		array[posx]=array[posy];
		posx++;
		array[posy]=temp;
		posy--;
	}
}


void chromsort(chromnode pop[10])    /*对染色体种群进行排序*/
{
	chromnode tpsn;    /*染色体交换中转站*/
	for(int i=0;i<9; i++)
	{
		tpsn.fitness = pop[i].fitness ;
	
		for(int j=i+1;j<10;j++)
		{
			if(pop[i].fitness <= pop[j].fitness  )
			{	
				copychrom(tpsn,pop[j]);
				copychrom(pop[j],pop[i]);
				copychrom(pop[i],tpsn);
			}
		}
		
	}

}


void relatearray(int testchr[5])  /*按照染色体序列将加工时间数组重新排列*/
{
	for(int m=0;m<5;m++)
		{
			
			int tpos=testchr[m]-1;

			for(int n=0;n<4;n++)
			{					
				temp[m][n]=t[tpos][n];
				
			}

		}
     
}


void calfitness(int array[10][5])      /*以数组为参数计算种群适应度的值并排序*/
{
		int testchrom[5]={0,0,0,0,0};  /*存储群体中的染色体序列*/
	

	for(int i=0;i<10;i++)
	{
		for(int j=0;j<5;j++)
		{
			testchrom[j]=array[i][j];
			relatearray(testchrom);   /*重组加工时间数组*/
			chrompop[i].chrom[j]=array[i][j];							/*将当前染色体序列复制到种群结构体*/
		}
			totaltime[i] = calcutime(temp);      /*计算当前染色体适应度（加工总时间）*/
			//waittime[i] = calwaittime(tover);
			voldfitness[i]=1/(float)totaltime[i];
			
	}
	chromsort(chrompop);

	
}


void calchromfit(chromnode pop[10])    /*以种群为参数计算种群适应度值——calfitness，并排序*/
{
	int dupli[10][5];
	for(int i=0;i<10;i++)
	{
		for(int j=0;j<5;j++)
		{
			dupli[i][j]=pop[i].chrom[j];
		}
	}
	calfitness(dupli);
	
	for(int k=0;k<10;k++)
	pop[k].fitness = voldfitness[k];
	/*for(int k=0;k<10;k++)
	{
		pop[k].fitness = float(100-voldfitness[k]*100);
		if(pop[k].fitness>80)pop[k].fitness-=10;
		else if(pop[k].fitness <50)pop[k].fitness+=10;

	}*/
	
}

int  fittotime(chromnode para)   /*求出染色体适应度的加工时间*/
{
	int stake[5];
	int time;
	for(int i=0;i<5;i++)