/*功能函数:遗传算法部分*/
#include <stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#define Tr 2 //电梯走过一层所需时间
#define Ts 4 //电梯停一层上下客所需时间
#define TOTAL_FLR 32
#define POPSIZE 10 //定义种群的大小
#define MAXGENER 50
#define CHROMLEN 8 //定义个体的软色体个数
#define maxgeneration 20
int zhonqun[POPSIZE][CHROMLEN];
int generation; //当前执行的世代数
//int maxgeneration; //最大世代数
int best_index; //最好的染色体索引序号
int worst_index; //最差的染色体索引序号
int c_best_index; //当前最佳染色体索引号
int sum[11];
float fitness[11];
int bestindividual[10];
int worstindividual[10];
int currentbest[10];
double pc=0.0; //交叉率
double pm=0.0; //变异率
struct CAR
{
int dir;
int flr;
int door;
int psg_num;
//uint8 psg_ID[CAPACITY];
int weight;
int up_stop_flr[TOTAL_FLR+1];
int dn_stop_flr[TOTAL_FLR+1];
int cc_stop_flr[TOTAL_FLR+1];
int occupied; //标示轿厢内被占据的位子
}Car;
struct HallCall
{
int id;
int flr;
int dir;
int aim;
int price_type;
float price_value;
}HC[2500+1];
struct HuTi
{
int QiCen;
int FangX;
int DaoCen;
} HT[9];
int Alog_WT(int HC_dir, int HC_flr, int Car_dir, int Car_flr, int up_stop_flr[32], int dn_stop_flr[32], int cc_stop_flr[32]); //函数:Alog_WT实现候梯时间,同时作为适应度函数
void PopInit(int a,int b); //生成初始种群
void EvaluatePop(); //适应度函数:计算每个个体的总的候梯时间,以及每个个体的适应度
void Find_bw(); //寻找最坏和最差的染色体
void Generate_next_Pop(); //产生下一代种群
void Select_Operator(); //选择操作
void Crossover_Operator(); //交叉操作
void Mutation_Operator(); //变异操作
void Perform_Evolution(); //进行演变进化
void main()
{
generation=0;
printf("welcome to use GA!\n");
PopInit(POPSIZE,CHROMLEN);
printf("thank you !");
EvaluatePop();
while(generation<maxgeneration)
{
generation++;
Generate_next_Pop();
EvaluatePop();
//Perform_Evolution(); //程序调到这个时候会变成死循环,要好好找找原因
}
}
/*功能函数:初始种群的生成 函数名:PopInit() 参数: a(种群的个数), b(个体的长度)*/
void PopInit(int a,int b)
{
int n,i,j,m,k;
int individual[CHROMLEN];
srand((unsigned)time(NULL));
for(i=0;i<a;i++)
{
for(k=0;k<CHROMLEN;k++)
individual[k]=0;
for(m=1;m<=CHROMLEN;m++)
{
n=(int)rand()%CHROMLEN;
if(individual[n]==0)
individual[n]=m;
else
{
do
n=(int)rand()%CHROMLEN;
while(individual[n]!=0);
individual[n]=m;
}
}
for(j=0;j<b;j++)
zhonqun[i][j]=individual[j];
}
for(i=0;i<a;i++)
{
for(j=0;j<b;j++)
printf("%3d",zhonqun[i][j]);
printf("\n");
}
}
//函数:Find_bw()实现寻找最佳和最差的染色体
void Find_bw()
{
int i,tem;
//找到最佳的染色体
tem=abs(sum[1]);
for(i=2;i<=10;i++)
{
if(abs(sum[i])>tem)
{
tem=abs(sum[i]);
best_index=i-1;
}
}
for(i=2;i<=10;i++)
{
if(abs(sum[i])<tem)
{
tem=abs(sum[i]);
worst_index=i-1;
}
}
if(generation==0)
{
c_best_index=best_index;
}
else if(abs(sum[best_index+1])>abs(sum[c_best_index+1]))
{
c_best_index=best_index;
}
}
void Perform_Evolution()
{
int i;
if(fitness[best_index]>fitness[c_best_index])
{
for(i=0;i<CHROMLEN;i++)
{
currentbest[i]=zhonqun[best_index][i];
}
}
else
for(i=0;i<CHROMLEN;i++)
{
worstindividual[i]=zhonqun[c_best_index][i];
}
}
//函数:Generate_next_Pop()生成子代种群(A.选择; B.交叉; C.变异)
void Generate_next_Pop()
{
Select_Operator();
Crossover_Operator();
Mutation_Operator();
}
//函数:Select_Operator()实现选择操作
void Select_Operator()
{
int i,j, index;
double p;
double cfitness[POPSIZE];
int newpop[POPSIZE][CHROMLEN];
srand((unsigned)time(NULL));
for(i=0;i<POPSIZE;i++)
cfitness[i]=fitness[i+1];
for(i=1;i<POPSIZE;i++)
cfitness[i]=cfitness[i-1]+cfitness[i];
for(i=0;i<POPSIZE;i++)
{
p=rand()%1000/1000.0; //得到千分位小数
index=0;
while (p>cfitness[index])
{
index++;
}
for(j=0;j<CHROMLEN;j++)
{
newpop[i][j]=zhonqun[index][j];
}
}
for(i=0;i<POPSIZE;i++)
{
for(j=0;j<CHROMLEN;j++)
zhonqun[i][j]=newpop[i][j];
}
}
//函数:Crossover_Operator() 实现交叉操作
void Crossover_Operator()
{
int m,n,i,j,k,r1,r2,temp,tem;
srand((unsigned)time(NULL));
m=2+(int)rand()%6;
n=1+(int)rand()%9;
//生成两个不同的随机数
if(m==n)
n=m+1;
//测试时用的函数,移植到开发板上时不用
for(k=0;k<8;k++)
printf("%3d",zhonqun[m][k]);
printf("\n");
//测试时用的函数,移植到开发板上时不用
for(k=0;k<8;k++)
printf("%3d",zhonqun[n][k]);
printf("\n");
r1=(int)rand()%6;
printf("r1=%3d\n",r1);//测试时用的函数,移植到开发板上时不用
for(i=0;i<8;i++)
if(zhonqun[m][r1]==zhonqun[n][i])
{ temp=i;
printf("temp=%3d\n",temp);
}
for(i=0;i<8;i++)
if(zhonqun[n][temp+1]==zhonqun[m][i])
{ r2=i;
printf("r2=%3d\n",r2);
}
//倒位操作程序部分
if(r1==r2)
{
tem=zhonqun[m][0];
zhonqun[m][0]=zhonqun[m][7];
zhonqun[m][7]=tem;
}
if(r2>r1)
{
if((r2-r1+1)%2 !=0) //判断要交换的个数是奇数个还是偶数个 :不等于0时为奇数个
{
while(r1!=r2)
{
tem=zhonqun[m][r1];
zhonqun[m][r1]=zhonqun[m][r2];
zhonqun[m][r2]=tem;
r1++;
r2--;
}
}
else //为偶数时
{
while((r2-r1)>0)
{
tem=zhonqun[m][r1];
zhonqun[m][r1]=zhonqun[m][r2];
zhonqun[m][r2]=tem;
r1++;
r2--;
}
}
}
//if(r1>r2)
else
{
if((r1-r2+1)%2 !=0) //判断要交换的个数是奇数个还是偶数个 :不等于0时为奇数个
{
while(r1!=r2)
{
tem=zhonqun[m][r2];
zhonqun[m][r2]=zhonqun[m][r1];
zhonqun[m][r1]=tem;
r1--;
r2++;
}
}
else //为偶数时
{
while((r1-r2)>0)
{
tem=zhonqun[m][r2];
zhonqun[m][r2]=zhonqun[m][r1];
zhonqun[m][r1]=tem;
r1++;
r2--;
}
}
}
//测试时用的函数,移植到开发板上时不用
for(k=0;k<8;k++)
printf("%3d",zhonqun[m][k]);
printf("\n");
}
//函数:Mutation_Operator() 变异操作
void Mutation_Operator()
{
int i,j,k,m,r1,r2,tem;
srand((unsigned)time(NULL));
m=(int)rand()%9;
r1=1+(int)rand%6;
r2=(int)rand%8;
if(r1==r2)
{
r2=r1+1;
}
//printf("the %3d time\n",j);
printf("r1=%3d\nr2=%3d\n",r1,r2);
//测试时用的函数,移植到开发板上时不用
for(k=0;k<8;k++)
printf("%3d",zhonqun[m][k]);
printf("\n");
//倒位操作程序部分
if(r1==r2)
{
tem=zhonqun[m][0];
zhonqun[m][0]=zhonqun[m][7];
zhonqun[m][7]=tem;
}
if(r2>r1)
{
if((r2-r1+1)%2 !=0) //判断要交换的个数是奇数个还是偶数个 :不等于0时为奇数个
{
while(r1!=r2)
{
tem=zhonqun[m][r1];
zhonqun[m][r1]=zhonqun[m][r2];
zhonqun[m][r2]=tem;
r1++;
r2--;
}
}
else //为偶数时
{
while((r2-r1)>0)
{
tem=zho