📄 gafu.c

📁 用遗传算法实现任务分配优化的源程序。
💻 C
字号:
/*************************************************/

#include "stdio.h"
#include "math.h"
#include "stdlib.h"
#include "time.h"

/**************************************************/
#define	POPUNUM	30
#define Pm      0.03
#define Pc      0.85
#define MAXTASK 12
#define MAXTEAM 3
#define MAXGEN 500
#define EPSL 0.001
/**************************************************/
int popu[2*POPUNUM][3][MAXTASK];
int fit[2*POPUNUM];
double ave_fit;
int handle_time[MAXTASK]={2,4,2,4,3,6,3,6,1,2,1,2};
static int MM[12][12]={0,0,0,0,0,0,0,0,0,0,0,0,
                       0,0,0,0,0,0,0,0,0,0,0,0,
					   0,0,0,0,0,0,0,0,0,0,0,0,
					   0,0,0,0,0,0,0,0,0,0,0,0,
					   1,0,0,0,0,0,0,0,0,0,0,0,
					   0,1,0,0,0,0,0,0,0,0,0,0,
					   0,0,1,0,0,0,0,0,0,0,0,0,
					   0,0,0,1,0,0,0,0,0,0,0,0,
					   0,0,0,0,1,0,0,0,0,0,0,0,
					   0,0,0,0,0,1,0,0,0,0,0,0,
					   0,0,0,0,0,0,1,0,0,0,0,0,
                       0,0,0,0,0,0,0,1,0,0,0,0};

int gen;

/**************************************************/

void ini();
void repare();
void cross();
void mutation();
void select();
void cacu_fit();

main()
{
int i,j;
double prev_ave_fit=0.0;
	ini();
	gen=0;
	while(1/*gen<MAXGEN*/)
	{
		ave_fit=0.0;
		cross();
		mutation();
		repare();
		cacu_fit();
		printf("GEN=%d;\tave_fit=%f\n",gen,ave_fit);
		if(fabs(prev_ave_fit-ave_fit)<EPSL)
		{
			select();
			break;
		}
		prev_ave_fit=ave_fit;
		select();
		gen++;
	}
	printf("TOTAL_GEN=%d;\n",gen);
	for(i=0;i<MAXTEAM;i++)
	{
		switch(i)
		{
		case 0:
			printf("task_array=%d;\n",i);
			break;
		case 1:
			printf("team_number=%d;\n",i);
			break;
		case 2:
			printf("task_team=%d;\n",i);
			break;
		default:
			break;
		}
		for(j=0;j<MAXTASK;j=j+4)
		{
				printf("%d\t%d\t%d\t%d\n",popu[0][i][j],popu[0][i][j+1],popu[0][i][j+2],popu[0][i][j+3]);
		}
	}
}

void ini()
{
	int temp,i,j,m;
	srand( (unsigned)time( NULL ) );
/*	srand(1);*/
	/*------------------------------
	初始化任务串	popu[][0][]
	-------------------------------*/
	for(m=0;m<POPUNUM;m++)
	{
		for(i=0;i<MAXTASK;i++)
		{
//			printf("i:%d\t",i);
			 temp = (int)floor(1.*rand()/RAND_MAX*(MAXTASK-1));
			if(i!=0)
			{
				for(j=0;j<i;j++)
				{
					if(popu[m][0][j]==temp)
					{
//						printf("!!!!\t%d\t%d\t%d\n",popu[m][0][j],j,temp);
						temp = (temp+1) % MAXTASK;
						j=-1;
					}
				}
			}
			popu[m][0][i]=temp;	
//			printf("%d\n",popu[m][0][i]);
									
		}
	}
	/*------------------------------
	初始化任务分配串 popu[][1][]
	-------------------------------*/
/*	for(m=0;m<POPUNUM;m++)
	{
		for(i=0;i<MAXTASK;i++)
		{
			temp = (int)floor(1.*rand()/RAND_MAX*(MAXTEAM));
		
			popu[m][1][i]=temp;
//			printf("%d\n",popu[m][1][i]);
						
		}
	}
*/
	/*------------------------------
	初始化任务组别 popu[][2][]
	-------------------------------*/
	for(m=0;m<POPUNUM;m++)
	{
		for(i=0;i<MAXTASK;i++)
		{
			if(popu[m][0][i]<4 && popu[m][0][i]>=0)
				popu[m][2][i]=1;
			if(popu[m][0][i]<8 && popu[m][0][i]>=4)
				popu[m][2][i]=2;
			if(popu[m][0][i]<12 && popu[m][0][i]>=8)
				popu[m][2][i]=3;			
//			printf("%d\n",popu[m][2][i]);
		}
	}
}
/***********************
 *		修补功能       *
 ***********************/
void repare()
{
int temp,m,i,j,k;
int pre_pos,cur_pos,pre_zb,cur_zb;

	/*-------主任务修补----------*/
	for(m=0;m<2*POPUNUM;m++)
	{
		//---固定第一个任务------
		popu[m][0][0]=0;
		/*----重复任务修补----*/
		for(i=1;i<MAXTASK;i++)
		{
			temp=popu[m][0][i];	
			for(j=0;j<i;j++)
			{
				if(popu[m][0][j]==temp)
				{
					temp = (temp+1) % MAXTASK;
					j=-1;
				}
			}
			popu[m][0][i]=temp;	
		}
		/*----前驱修补----*/
		for(i=1;i<MAXTASK;i++)
		{
			for(j=0;j<i;j++)
			{
				if(MM[popu[m][0][j]][popu[m][0][i]]==1)
				{
					temp=popu[m][0][i];
					for(k=i-1;k>=j;k--)
						popu[m][0][k+1]=popu[m][0][k];
					popu[m][0][j]=temp;		
				}
			}
		}
	}
	//--------相应组别修补---------
	for(m=0;m<2*POPUNUM;m++)
	{
		for(i=0;i<MAXTASK;i++)
		{
			if(popu[m][0][i]<4 && popu[m][0][i]>=0)
				popu[m][2][i]=1;
			if(popu[m][0][i]<8 && popu[m][0][i]>=4)
				popu[m][2][i]=2;
			if(popu[m][0][i]<12 && popu[m][0][i]>=8)
				popu[m][2][i]=3;			
		}
	}
	//-------辅助修补(任务所在组-处理机修补)-------------
	for(m=0;m<2*POPUNUM;m++)
	{
		for(i=0;i<MAXTASK;i++)
		{
			switch(popu[m][2][i])
			{
			case 1:
				popu[m][1][i]=1;
				break;
			case 2:
				popu[m][1][i]=2;
				break;
			case 3:
				popu[m][1][i]=3;
				break;
			default:	
				break;
			}
		}
	}
	//-------根据前驱任务顺序修补当前任务顺序-------
	for(m=0;m<2*POPUNUM;m++)
	{
		for(i=0;i<MAXTASK;i++)
		{
			pre_pos=0;
			cur_pos=0;
			for(j=0;j<i;j++)
			{
				if(MM[popu[m][0][i]][popu[m][0][j]]==1)
				{
					pre_zb=popu[m][2][j];
					for(k=0;k<=j;k++)
					{
						if(popu[m][2][k]==pre_zb)
							pre_pos++;
					}
					cur_zb=popu[m][2][i];
					for(k=0;k<MAXTASK;k++)
					{
						if(popu[m][2][k]==cur_zb)
						{
							cur_pos++;
							if(cur_pos==pre_pos)
							{
								temp=popu[m][0][i];
								popu[m][0][i]=popu[m][0][k];
								popu[m][0][k]=temp;
								break;
							}
						}
					}
					break;
				}
			}
		}
	}
	//-------各任务处理时间更改修补-----------
	for(m=0;m<2*POPUNUM;m++)
	{
		for(i=0;i<MAXTASK;i++)
		{
			switch(popu[m][0][i])
			{
			case 0:
				handle_time[popu[m][0][i]]=2;
				break;
			case 1:
				handle_time[popu[m][0][i]]=4;
				break;
			case 2:
				handle_time[popu[m][0][i]]=2;
				break;
			case 3:
				handle_time[popu[m][0][i]]=4;
				break;
			case 4:
				handle_time[popu[m][0][i]]=3;
				break;
			case 5:
				handle_time[popu[m][0][i]]=6;
				break;
			case 6:
				handle_time[popu[m][0][i]]=3;
				break;
			case 7:
				handle_time[popu[m][0][i]]=6;
				break;
			case 8:
				handle_time[popu[m][0][i]]=1;
				break;
			case 9:
				handle_time[popu[m][0][i]]=2;
				break;
			case 10:
				handle_time[popu[m][0][i]]=1;
				break;
			case 11:
				handle_time[popu[m][0][i]]=2;
				break;
			default:	
				break;
			}
		}
	}
}

void cross()
{
 int	temp,s,s1,s2,i,j;
 double	p;
	for(i=0;i<POPUNUM;i=i+2)
	{
		s1=(int)floor(1.*rand()/RAND_MAX*(POPUNUM-1));
		p=1.*rand()/RAND_MAX;
		if(p<Pc)
		{
			while(1)
			{
				s2=(int)floor(1.*rand()/RAND_MAX*(POPUNUM-1));
				if(s1!=s2)
					break;
			}
			for(j=0;j<MAXTASK;j++)
			{
				popu[POPUNUM+i][0][j]=popu[s1][0][j];
				popu[POPUNUM+i+1][0][j]=popu[s2][0][j];
			}
			s=(int)floor(1.*rand()/RAND_MAX*(MAXTASK-1));
			for(j=s;j<MAXTASK;j++)
			{
				temp=popu[POPUNUM+i][0][j];
				popu[POPUNUM+i][0][j]=popu[POPUNUM+i+1][0][j];
				popu[POPUNUM+i+1][0][j]=temp;
			}
		}
	}
}
/*两点间随机反转变异*/
void mutation()
{
double	p;
int	s1,s2,i,j,temp[MAXTASK];
	for(i=0;i<2*POPUNUM;i++)
	{	
		p=1.*rand()/RAND_MAX;
		if(p<Pm)
		{
			s1=(int)floor(1.*rand()/RAND_MAX*(MAXTASK-1));
			s2=(int)floor(1.*rand()/RAND_MAX*(MAXTASK-1));
			for(j=min(s1,s2);j<=max(s1,s2);j++)
				temp[j]=popu[i][0][j];
			for(j=min(s1,s2);j<=max(s1,s2);j++)
				popu[i][0][j]=temp[max(s1,s2)+min(s1,s2)-j];
//		printf("\n$$$$$$$   s1=%d\ts2=%d\n",s1,s2);
		}
	}
}
void select()
{
	int i,j,k,l;
	int temp,arrtemp[MAXTEAM][MAXTASK];
	for(i=0;i<POPUNUM*2;i++)
	{
		for(j=i+1;j<POPUNUM*2;j++)
			if(fit[i]<fit[j])
			{
				temp=fit[i];
				fit[i]=fit[j];
				fit[j]=temp;
				/* popu[i][k][l]与popu[j][k][l]互换*/
				for(k=0;k<MAXTEAM;k++)
					for(l=0;l<MAXTASK;l++)
					{
						arrtemp[k][l]=popu[i][k][l];
						popu[i][k][l]=popu[j][k][l];
						popu[j][k][l]=arrtemp[k][l];
					}
			}
	}
}
void cacu_fit()
{
int n,i,j;
int sigma_handle_time,prev_task,dmax,sigma_fit;
int start_time[MAXTASK],end_time[MAXTASK],d[MAXTEAM];
	
	/*所有任务处理时间和*/
	sigma_handle_time=0;
	for(i=0;i<MAXTASK;i++)
	{
		sigma_handle_time +=handle_time[i];
		end_time[i]=0;
	}
	/* caculate fitness */
	sigma_fit=0;
	for(n=0;n<POPUNUM*2;n++)
	{
		for(i=0;i<MAXTEAM;i++)
		{
			d[i]=0;
		}
		for(i=0;i<MAXTASK;i++)
		{
			end_time[i]=0;
		}
		for(i=0;i<MAXTASK;i++)
		{
			prev_task=popu[n][0][i];
			for(j=0;j<MAXTASK;j++)
			{
				if(MM[popu[n][0][i]][j]==1)
				{
					prev_task=j;
					break;
				}
			}
			start_time[popu[n][0][i]]=max(end_time[prev_task],d[popu[n][1][i]]);
			end_time[popu[n][0][i]]=start_time[i]+handle_time[popu[n][0][i]];
			d[popu[n][1][popu[n][0][i]]]=end_time[popu[n][0][i]];
		}
		dmax=d[0];	/*最大调度长度*/
		for(i=0;i<MAXTEAM;i++)
			if(d[i]>dmax)
				dmax=d[i];
//		fit[n]=sigma_handle_time-d[2];

		fit[n]=sigma_handle_time-dmax;
/*		printf("gen=%d\tn=%d\n",gen,n);
		printf("dmax=%d\tfit=%d\n",dmax,fit[n]);
*/		sigma_fit +=fit[n];
	}
	ave_fit=1.0*sigma_fit/(2*POPUNUM);
}
💿 文件大小 122 K
👤 上传用户 yiranshamaoer
📂 所属分类人工智能/神经网络
🏷️ 相关标签

#算法 #分配 #源程序
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -