auto.cpp

使用改进的遗传算法实现简单的高校排课

             sqlUpdate += teac_cls_num_tmp[k];
             sqlUpdate += "where Teacher_ID =";
             sqlUpdate += tec_id[k];

             ADOQuery8->Close();
             ADOQuery8->SQL->Clear();
             ADOQuery8->SQL->Add(sqlUpdate);
             ADOQuery8->ExecSQL();
        }
    }
}

void __fastcall TAutoForm::initpop()
{
	int j,j1;
	for(j=0;j<popsize;j++)
	{
            for(j1=0;j1<lchrom;j1++)
            {
                oldpop[j].chrom[j1]=1+Random(25);
            }
            check(oldpop[j].chrom);
            oldpop[j].fitness=objfunc(oldpop[j].chrom);
            oldpop[j].parent1=0;
            oldpop[j].parent2=0;
            oldpop[j].xsite=0;
        }
}

__fastcall TAutoForm::objfunc(int *a)
{
     int i,j,k,f;
        int dispersion=1;           //课程分散度
        int Cdispersion=0;          //课表分散度
        int optimization=0;         //课程优化度
        int Coptimization=0;        //课表优化度
        int x=0;
        int y=0;
        int *g;
        for(i=0;i<10;i++)
        {
            int m=chromize[i];      //课时数
            int n=priority[i];      //优先级
            int t=0;
            int p=0;
            y=x+m;
            if(m==0) break;
            else
            {
                if (m==1)
                {
                    dispersion=1;   //只有一个课时
                    if(a[k]%5==0)t=1;
                    else t=(6-a[k]%5);
                    p=t;
                    optimization=p*n;
                }
                else
                {
                    
                    dispersion=1;
                    g=&a[x];
                    order(g,m);
                    for(j=x;j<y-1;j++)             //两个及以上课时
                    {
                        int d=abs(a[j]-a[j+1]);
                        dispersion=dispersion* d;
                        if(d<5) dispersion=0;     //一门课放在一天，罚
                        else dispersion+=(d*1);   //间隔越多，奖励越多
                    }
                    for(k=x;k<y;k++)
                    {
                        t=0;
                        if(a[k]%5==0)t=1;
                        else t=(6-a[k]%5);
                        p+=t;
                        
                     }
                     optimization=p*n;
                }

            }
            x=x+m;                              //下一次扫描起点位置
            Cdispersion+=dispersion;            //课程分散度累加成课表分散度
            Coptimization+=optimization;        //课程优化度累加成课表优化度
        }
        f=Cdispersion+Coptimization;
        return (f);
}

void __fastcall TAutoForm::statics(struct pp* pop)
{
	int j;
	sumfitness=pop[0].fitness;
	min=pop[0].fitness;
	max=pop[0].fitness;
	maxpp=0;
	minpp=0;
	for(j=1;j<popsize;j++)
	{
		sumfitness+=pop[j].fitness;
		if(pop[j].fitness>max)
		{
			max=pop[j].fitness;
			maxpp=j;
		}
		if(pop[j].fitness<min)
		{
			min=pop[j].fitness;
			minpp=j;
		}
	}
	avg=sumfitness/popsize;
}

void __fastcall TAutoForm::generation()
{
	unsigned int j,mate1,mate2;
	j=0;
	do
	{
		mate1=select();
		mate2=select();
		crossover(oldpop[mate1].chrom,oldpop[mate2].chrom,j);
		check(newpop[j].chrom);
		check(newpop[j+1].chrom);

        newpop[j].fitness=objfunc(newpop[j].chrom);
	    newpop[j].parent1=mate1;
            newpop[j].parent2=mate2;
            newpop[j].xsite=jcross;
        
        newpop[j+1].fitness=objfunc(newpop[j+1].chrom);
	    newpop[j+1].parent1=mate1;
            newpop[j+1].parent2=mate2;
            newpop[j+1].xsite=jcross;
        j+=2;
	}while(j<popsize);
}

__fastcall TAutoForm::select()
{
	float rand1,partsum;
	int j;
	partsum=0;
	j=0;
	rand1=random1()*sumfitness;
	do
	{
		partsum=partsum+oldpop[j].fitness;
		j+=1;
	}while((partsum<rand1)&&(j<popsize));
	return j-1;
}

void __fastcall TAutoForm::crossover(int *a,int *b,int k5)
{
	int j;
	if(flip(pcross))
	{
		jcross=Random(lchrom-1);
		ncross+=1;
	}
	else
		jcross=lchrom;
	if(jcross!=lchrom)
	{
		for(j=0;j<jcross;j++)
		{
			newpop[k5].chrom[j]=a[j];
		    newpop[k5+1].chrom[j]=b[j];
		}
        for(j=jcross;j<lchrom;j++)
		{
			newpop[k5].chrom[j]=(b[j]);
		    newpop[k5+1].chrom[j]=(a[j]);
		}
	}
	else
	{
		for(j=0;j<lchrom;j++)
		{
			newpop[k5].chrom[j]=a[j];
		    newpop[k5+1].chrom[j]=b[j];
		}
	}

}

void __fastcall TAutoForm::randomize1()
{
	int i;
	for(i=0;i<lchrom;i++)
		oldrand[i]=Random(30001)/30000.0;
	jrand=0;
}

__fastcall TAutoForm::random1()
{
	jrand+=1;
	if(jrand>=lchrom)
	{
		jrand=0;
		randomize1();
	}
	return oldrand[jrand];
}

__fastcall TAutoForm::flip(float probability)
{
    float pp;
	pp=Random(20001)/20000.0;
	if(pp<=probability)
		return 1;
	return 0;
}

__fastcall TAutoForm::length(int *a)
{
    int m=0;
    int i;
    for(i=0;i<10;i++)
    {
        m=m+a[i];
    }
    return(m);
}

 __fastcall TAutoForm::order(int *b,int l)
{
	
	
	int i,j,t;
	for(i=0;i<l-1;i++)
	   for(j=0;j<l-i-1;j++)
	      if(b[j]>b[j+1])
		  {
		      t=b[j];
                      b[j]=b[j+1];
		      b[j+1]=t;
		  }
	return 0;
}
void __fastcall TAutoForm::check(int *a)
{
	int i,j,m,n,k;
	int c[26]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25};
	m=a[0];
	c[m]=0;
	for(i=1;i<lchrom;i++)
	{
		for(j=0;j<i;j++)
		{	
			if (a[i]==a[j])
			{
				do
				{
				    n=1+Random(25);
					a[i]=c[n];
				}while (c[n]==0);
				c[n]=0;
			}
			else
			{
				k=a[i];
				c[k]=0;
			}
		}
	}
}

void __fastcall TAutoForm::initialize()
{
	//initdata();
        /*chromize[0]=3;
        chromize[1]=2;
        chromize[2]=2;
        chromize[3]=1;
        priority[0]=3;
        priority[1]=2;
        priority[2]=2;
        priority[3]=1; */
        //lchrom=length(chromize);
	initpop();
	statics(oldpop);
	//initreport();
}

void __fastcall TAutoForm::pause()
{
    int i,j,k;
    for(i=0;i<10000;i++)
        for(j=0;j<10000;j++)
            for(k=0;k<10;k++);
}

__fastcall TAutoForm::Random(unsigned long n)
{
    randSeed=multiplier*randSeed+adder;
    return (unsigned short)((randSeed>>16)%n);
}


/***************
                         ADOQuery5->First();
                         while(!ADOQuery5->Eof)
                         {
                             tmp_tec_id =  ADOQuery5->FieldByName("Teac_ID")->AsInteger;
                             if (tec_id[k] == tmp_tec_id )  *已经安排教师上课**
                             {
                                 flag = 1;
                                 break;
                             }
                             else if (tmp_tec_id == 0 || tmp_tec_id == NULL) **还没有安排教师**
                             {
                                 break;
                             }
                             ADOQuery5->Next();
                         }
                                                 break;
                     }
                     if (flag == 1)
                     {
                        break;
                     }
*************/