auto.cpp

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

//---------------------------------------------------------------------------

#include <vcl.h>
#pragma hdrstop

#include "auto.h"
#include<time.h>
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<math.h>
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TAutoForm *AutoForm;
//---------------------------------------------------------------------------
__fastcall TAutoForm::TAutoForm(TComponent* Owner)
        : TForm(Owner)
{
}
//---------------------------------------------------------------------------

void __fastcall TAutoForm::FormClose(TObject *Sender, TCloseAction &Action)
{
     Action = caFree;
}

void __fastcall TAutoForm::ComboBox1Change(TObject *Sender)
{
    AnsiString temp, tmp;

    ListBox1->Clear();
    if (ComboBox1->Text == "1年级")
    {
         grade = 1;
    }
    else if (ComboBox1->Text == "2年级")
    {
         grade = 2;
    }
    else if (ComboBox1->Text == "3年级")
    {
         grade = 3;
    }
    else if (ComboBox1->Text == "4年级")
    {
         grade = 4;
    }

    ADOQuery1->Close();
    ADOQuery1->SQL->Clear();
    ADOQuery1->SQL->Add("select * From Class");
    ADOQuery1->SQL->Add("where Grade = :Grade");
    ADOQuery1->Parameters->ParamByName("Grade")->Value=grade;
    ADOQuery1->Open();
    if(ADOQuery1->RecordCount!=0)
    {
        ADOQuery1->First();
        while(!ADOQuery1->Eof)
        {
            tmp = ADOQuery1->FieldByName("Name")->AsString;
            ListBox1->AddItem(tmp, this);
            ADOQuery1->Next();
         }
    }
}
//---------------------------------------------------------------------------



void __fastcall TAutoForm::ListBox1Click(TObject *Sender)
{
    int  find = 0;

    int  total_curse = 0;
    AnsiString temp;
    int  ins = ListBox1->ItemIndex;

    ADOTable1->Active = false;
    ADOQuery1->Close();
    ADOQuery1->SQL->Clear();
    ADOQuery1->SQL->Add("select * From Class");
    ADOQuery1->SQL->Add("where Grade = :Grade");
    ADOQuery1->Parameters->ParamByName("Grade")->Value=grade;
    ADOQuery1->Open();
    if(ADOQuery1->RecordCount!=0)
    {
        ADOQuery1->First();
        while(!ADOQuery1->Eof)
        {
            temp = ADOQuery1->FieldByName("Name")->AsString;
            if (find == ins)
               break;
            ADOQuery1->Next();
            find ++;
         }
    }
    Edit1->Text = temp;
    ADOTable1->Filtered = true;
    ADOTable1->Filter = "班级 = '" + temp + "'";
    ADOTable1->Active = true;

    ADOQuery1->Close();
    ADOQuery1->SQL->Clear();
    ADOQuery1->SQL->Add("select * From plans");
    ADOQuery1->SQL->Add("where 班级 = :Grade");
    ADOQuery1->Parameters->ParamByName("Grade")->Value=temp;
    ADOQuery1->Open();
    if(ADOQuery1->RecordCount!=0)
    {
        ADOQuery1->First();
        while(!ADOQuery1->Eof)
        {
            total_curse += ADOQuery1->FieldByName("周课时")->AsInteger;
            ADOQuery1->Next();
         }
    }
    Edit2->Text = IntToStr(total_curse);

    ADOQuery1->Close();
    ADOQuery1->SQL->Clear();
    ADOQuery1->SQL->Add("select * From plans");
    ADOQuery1->SQL->Add("where 班级 = :Grade");
    ADOQuery1->Parameters->ParamByName("Grade")->Value=temp;
    ADOQuery1->Open();
    if(ADOQuery1->RecordCount!=0)
    {
        ADOQuery1->First();
        int i=0;
        while(!ADOQuery1->Eof)
        {
            chromize[i]= ADOQuery1->FieldByName("周课时")->AsInteger;
            i++;
            ADOQuery1->Next();
         }
    }

    ADOQuery1->Close();
    ADOQuery1->SQL->Clear();
    ADOQuery1->SQL->Add("select * From plans");
    ADOQuery1->SQL->Add("where 班级 = :Grade");
    ADOQuery1->Parameters->ParamByName("Grade")->Value=temp;
    ADOQuery1->Open();
    if(ADOQuery1->RecordCount!=0)
    {
        ADOQuery1->First();
        int i=0;
        while(!ADOQuery1->Eof)
        {

            priority[i]= ADOQuery1->FieldByName("课程优先级")->AsInteger;
            i++;
            ADOQuery1->Next();
         }
    }

}
//---------------------------------------------------------------------------
//生成初始群体
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;
	}
}
void __fastcall TAutoForm::Button1Click(TObject *Sender)
{
     long int gen,k,j;
	float oldmax;
	int oldmaxpp;
        maxgen=20;
        int max;
        if(!(oldpop=(class pp*)malloc(maxpop*sizeof(class pp))))
	{
		printf("no memory!\n");
		return;
	}
	if(!(newpop=(class pp*)malloc(maxpop*sizeof(class pp))))
	{
		printf("no memory!\n");
		return;
	}
	if(!(p1=(struct pp*)malloc(sizeof(struct pp))))
	{
		printf("no memory!\n");
		return;
	}  
	for(k=0;k<maxpop;k++)
		oldpop[k].chrom[0]=0;
	for(k=0;k<maxpop;k++)
		newpop[k].chrom[0]=0;
	gen=0;
        popsize=10;

	initialize();
	system("cls");
        getchar();
        do
	{
		gen=gen+1;
		oldmax=max;
		oldmaxpp=maxpp;
		generation();
		statics(newpop);
		if(max<oldmax)
		{
                    for(j=0;j<lchrom;j++)//?
                        newpop[minpp].chrom[j]=oldpop[oldmaxpp].chrom[j];
                        newpop[minpp].fitness=oldpop[oldmaxpp].fitness;
                        statics(newpop);
		}
		//report(gen);
		p1=oldpop;
                pcross=0.9;
                oldpop=newpop;
		newpop=p1;
		getchar();
	}while(gen<maxgen);
        max=maxpp;
	Edit3->Text="3";//newpop[max].chrom;//->AsString;
        free(p1);
	free(oldpop);
	free(newpop);
	exit(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);
}