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::Button1Click(TObject *Sender)
{
     int   flag = 0;
     long  i,gen,k,j;
     int   p;
     float oldmax;
     int   oldmaxpp;
     int   max;

     int   temp=1, tmp =0;
     int   cous_tmp[100];
     int   cous_per[10];
     int   cous_pri[10];
     int   class_room_cap[100];
     int   class_room_num[100];
     int   cls_id_arry[100], cls_total_num;
     int   cous_num;
     int   next_start;
     int   cls_id, cou_id, tim_num, cls_cap, room_num;
     int   tec_id[20], tmp_tec_id, teac_assi_tmp[20], teac_cls_num_tmp[20];

     gen=0;

     AnsiString    cls_name, head_tech;
     AnsiString sqlStr;

     pcross = 0.9;

     /***求班级编号及总数***/
     ADOQuery6->Close();
     ADOQuery6->SQL->Clear();
     ADOQuery6->SQL->Add("select distinct Class_ID From Class");
     ADOQuery6->Open();
     if(ADOQuery6->RecordCount!=0)
     {
         i = 0;
         ADOQuery6->First();
         while(!ADOQuery6->Eof)
         {
             cls_id_arry[i] = ADOQuery6->FieldByName("Class_ID")->AsInteger;
             i++;
             ADOQuery6->Next();
         }
         cls_total_num = i;
     }

     /***求教室数和各个教室的容量教室编号***/
     ADOQuery3->Close();
     ADOQuery3->SQL->Clear();
     ADOQuery3->SQL->Add("select * From room");
     ADOQuery3->Open();
     if(ADOQuery3->RecordCount != 0)
     {
          ADOQuery3->First();
          i = 0;
          while(!ADOQuery3->Eof)
          {
              class_room_cap[i] = ADOQuery3->FieldByName("Room_Capacity")->AsInteger;;
              class_room_num[i] = ADOQuery3->FieldByName("Room_Num")->AsInteger;;
              ADOQuery3->Next();
              i++;
          }
          room_num = i;
     }
     
     for (p = 0; p<cls_total_num; p++)
     {
         popsize=10;
         maxgen = 440*(p+1);
         
         ADOQuery1->Close();
         ADOQuery1->SQL->Clear();
         ADOQuery1->SQL->Add("select * From plans");
         ADOQuery1->SQL->Add("where Class_ID = :ID");
         ADOQuery1->Parameters->ParamByName("ID")->Value = cls_id_arry[p];
         ADOQuery1->Open();
         if(ADOQuery1->RecordCount!=0)
         {
            ADOQuery1->First();
            i=0;
            while(!ADOQuery1->Eof)
            {
                chromize[i] = ADOQuery1->FieldByName("Cper_Week")->AsInteger;
                cous_per[i] = chromize[i];
                course_id[i] = ADOQuery1->FieldByName("Course_ID")->AsInteger;
                cous_tmp[i] = course_id[i];
                priority[i] = ADOQuery1->FieldByName("Course_Priority")->AsInteger;
                cous_pri[i] =  priority[i];
                i++;
                ADOQuery1->Next();
            }
         }
         cous_num = i;

         oldpop=(struct pp*)malloc(maxpop*sizeof(struct pp));

         newpop=(struct pp*)malloc(maxpop*sizeof(struct pp));

         p1=(struct pp*)malloc(sizeof(struct pp));

         lchrom=length(chromize);

         for(k=0;k<popsize;k++)
            for(i=0;i<lchrom;i++)
               oldpop[k].chrom[i]=0;
         for(k=0;k<popsize;k++)
            for(i=0;i<lchrom;i++)
                newpop[k].chrom[i]=0;


         initialize();
         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);
                 }
             }
             p1=oldpop;

             oldpop=newpop;
             newpop=p1;
         }while(gen<maxgen);
         max=maxpp;

         /**计算cou_id**/
         int x = 0, n = 0;
         i = 0;
         for (j = 0; j<cous_num; j++)
         {
             n = chromize[j];
             for (i = x; i<x+n; i++)
             cous_tmp[i] = course_id[j];
             x = x+n;
         }

         /***填充课程表***/
         for(i=0;i<lchrom;i++)
         {
             ADOQuery1->Close();
             ADOQuery1->SQL->Clear();

             cls_id   = cls_id_arry[p];
             ADOQuery2->Close();
             ADOQuery2->SQL->Clear();
             ADOQuery2->SQL->Add("select * From Class");
             ADOQuery2->SQL->Add("where Class_ID = :Cls_ID");
             ADOQuery2->Parameters->ParamByName("Cls_ID")->Value= cls_id;
             ADOQuery2->Open();
             if (ADOQuery2->RecordCount == 1)
             {
                 cls_cap = ADOQuery2->FieldByName("Class_Cap")->AsInteger;
             }
             else
             {
             }

             for (j=0; j<room_num;)
             {
                 if (class_room_cap[j]-cls_cap<=15)
                 {
                     /****检查同时间段和已经排好的其他班级教室是否冲突****/
                     ADOQuery7->Close();
                     ADOQuery7->SQL->Clear();
                     ADOQuery7->SQL->Add("select * From CTable");
                     ADOQuery7->SQL->Add("where Time_Num = :Tim_Num");
                     ADOQuery7->SQL->Add("and Room_Num = :Room_No");
                     ADOQuery7->Parameters->ParamByName("Tim_Num")->Value= newpop[max].chrom[i];
                     ADOQuery7->Parameters->ParamByName("Room_No")->Value= class_room_num[j];
                     ADOQuery7->Open();
                     if (ADOQuery7->RecordCount != 0)
                     {
                         j++;
                         continue;
                     }
                     else  if (ADOQuery7->RecordCount == 0)
                         break;
                 }
             }
         
             cou_id    = cous_tmp[i]; /**课程编号**/
             /***考虑多个老师教授一门课程的情况***/
             ADOQuery4->Close();
             ADOQuery4->SQL->Clear();
             ADOQuery4->SQL->Add("select * From teacher");
             ADOQuery4->SQL->Add("where Teac_Cousid = :Tec_Couid");
             ADOQuery4->Parameters->ParamByName("Tec_Couid")->Value= cou_id;
             ADOQuery4->Open();
             if(ADOQuery4->RecordCount != 0)
             {
                 k = 0;
                 ADOQuery4->First();
                 while(!ADOQuery4->Eof)
                 {
                     tec_id[k] =  ADOQuery4->FieldByName("Teacher_ID")->AsInteger;
                     teac_assi_tmp[k] = ADOQuery4->FieldByName("Teac_assi")->AsInteger;
                     teac_cls_num_tmp[k] = ADOQuery4->FieldByName("Teac_cls_num")->AsInteger;;
                     ADOQuery4->Next();
                     k++;
                 }
             }
             /***选择教师***/
             for (k=0; k<ADOQuery4->RecordCount; k++)
             {
                 int choice =0;
                 choice = k;
                 tmp_tec_id = 0;
                 if (teac_assi_tmp[k] == 0)  /**该教师从来没有安排课程  则得到 k 值**/
                 {
                     break;
                 }
                 else if (teac_assi_tmp[k] == 1)
                 {
                     /*该教师已经安排课程如果还能继续任课则还可以选择*/
                     /*同一个班同一门课程需要同一个教师授课*/
                     /**当一个教师可以代课的班级数为零 则不能选择**/
                     ADOQuery5->Close();
                     ADOQuery5->SQL->Clear();
                     ADOQuery5->SQL->Add("select * From CTable");
                     ADOQuery5->SQL->Add("where Class_ID = :Cls_ID");
                     ADOQuery5->SQL->Add("and Course_ID = :Cou_ID");
                     ADOQuery5->SQL->Add("and Teac_ID = :Tec_ID");
                     ADOQuery5->Parameters->ParamByName("Cls_ID")->Value= cls_id;
                     ADOQuery5->Parameters->ParamByName("Cou_ID")->Value= cou_id;
                     ADOQuery5->Parameters->ParamByName("Tec_ID")->Value= tec_id[choice]; /*???*/
                     ADOQuery5->Open();
                     if (ADOQuery5->RecordCount!=0) /***教师已经任同一个班同一门课程***/
                     {
                        break;
                     }
                     else  if (ADOQuery5->RecordCount==0) /**教师没有任该班课程**/
                     {
                         int q;
                         /***如果教授同一门课程的其他老师还没有任课则选择下一个还没有安排上课的老师***/
                         for (q = k+1; q<ADOQuery4->RecordCount; q++)
                         {
                             if (teac_assi_tmp[q] == 0)  /**该教师从来没有安排课程  则得到 k 值**/
                             {
                                  choice = q;
                                  break;
                             }
                         }
                         if (q == ADOQuery4->RecordCount)/*所有教师都安排班级*/
                         {
                             /***如果所有教师都有班级安排上课 那么选择还可以代其他班级课程的老师任课***/
                             int max = teac_cls_num_tmp[0];
                             for ( int m = 0; m<ADOQuery4->RecordCount; m ++)
                             {
                                 if (teac_cls_num_tmp[m] >0)
                                 {
                                     if (teac_cls_num_tmp[m] > max)
                                     {
                                         choice = m;
                                         max = teac_cls_num_tmp[m];
                                     }
                                 }
                             }
                             /**课程时间没有冲突那么该教师可以选择**
                             ****
                                 如何判断？？？？
                              ****/
                             //k = choice;
                             break;
                        }
                     }
                 }
             }

             tim_num   = newpop[max].chrom[i];
             sqlStr =  "INSERT INTO CTable VALUES (";
             sqlStr += cls_id;
             sqlStr += ",";
             sqlStr += cou_id;
             sqlStr += ",";
             sqlStr += tim_num;
             sqlStr += ",";
             sqlStr += class_room_num[j];
             sqlStr += ",";
             sqlStr += tec_id[k];
             sqlStr += ")";
             ADOQuery1->SQL->Add(sqlStr);
             ADOQuery1->ExecSQL();
             /***更新教师信息表***/
             /***先查询到教师的授课信息***/
             AnsiString sqlUpdate;
             teac_assi_tmp[k] = 1;
             teac_cls_num_tmp[k] -=1;

             sqlUpdate = "update teacher set teac_assi =";
             sqlUpdate += teac_assi_tmp[k];
             sqlUpdate += ",teac_cls_num =";