#include<iostream>
#include<fstream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<sys/types.h>
#include<sys/timeb.h>
#include<algorithm>
#include<vector>
#include <ctime>
#define K 1000
#define MAX 10000
double cost[K][K];
int stat[K][K];
int *b_p,*l_p;
double best,last;
using namespace std;
void cal(int number,int n_w,int n_e,int **ptr,double *f,double cost[K][K],int stat[K][K])//计算一个排列的指标函数
{
double *e=new double[n_e];//记录设备占用情况
int *w=new int[n_w];//记录工作进入第几个工序
double max=0;
for(int i=0;i<number;i++)
{
double time=0;
for(int k=0;k<n_e;k++)
e[k]=0;
for(int k=0;k<n_w;k++)
w[k]=-1;
for(int k=0;k<n_w*n_e;k++)
{
w[ptr[i][k]]++;
if(e[stat[ptr[i][k]][w[ptr[i][k]]]]==0)
{
e[stat[ptr[i][k]][w[ptr[i][k]]]]=cost[ptr[i][k]][stat[ptr[i][k]][w[ptr[i][k]]]];
}
else
{
time+=e[stat[ptr[i][k]][w[ptr[i][k]]]];
for(int n=0;n<n_e;n++)
if((e[n]!=0)&&(n!=stat[ptr[i][k]][w[ptr[i][k]]]))
{
if(e[n]>=e[stat[ptr[i][k]][w[ptr[i][k]]]])
e[n]-=e[stat[ptr[i][k]][w[ptr[i][k]]]];
else e[n]=0;
}
e[stat[ptr[i][k]][w[ptr[i][k]]]]=cost[ptr[i][k]][stat[ptr[i][k]][w[ptr[i][k]]]];
}
}
max=0;
for(int n=0;n<n_e;n++)
if(e[n]>max)
max=e[n];
f[i]=time+max;
}
}
struct node
{
double result;
int number;
};
bool greater(node n1,node n2)//按照从大到小排序以便再次选择染色体进入种群
{
return n1.result<n2.result;
}
void change(int **ptr,int first,int second,int n_w,int n_e)//copy染色体2到染色体1
{
for(int i=0;i<n_w*n_e;i++)
ptr[first][i]=ptr[second][i];
}
void get_best(double *f,int **ptr,int number,int n_w,int n_e)//得到群体中指标函数最好的
{
int temp=-1;
for(int i=0;i<number;i++)
if(f[i]<best)
{
best=f[i];
temp=i;
}
if(temp!=-1)
for(int i=0;i<n_w*n_e;i++)
b_p[i]=ptr[temp][i];
}
void ga(int n_w,int n_e,int number)//遗传算法
{
//////////////////////////////////////////////////
unsigned int seedVal;
struct timeb timeBuf;
ftime(&timeBuf);
seedVal=((((unsigned int)timeBuf.time&0xFFFF)+
(unsigned int)timeBuf.millitm)^
(unsigned int)timeBuf.millitm);
srand((unsigned int)seedVal);
// srand(unsigned(time(0)));
/////////////////////////////////////////////////
best=MAX;last=MAX+1;
int **ptr=new int *[number];
b_p=new int[n_w*n_e];
l_p=new int[n_w*n_e];
double *f=new double[number];
int *n_w1=new int[n_w];
int *n_w2=new int[n_w];
vector<node> trial;
int *n_f=new int[number];
int s_f=0,left=0;
double sum=0;
int count=0;
for(int i=0;i<number;i++)
{
ptr[i]=new int[n_w*n_e];
for(int k=0;k<n_w*n_e;k++)
ptr[i][k]=0;
}
int position;
for(int n=0;n<number;n++)
for(int i=0;i<n_w;i++)
for(int k=0;k<n_e;k++)
{
position=rand();
position%=n_w*n_e;
while(ptr[n][position]!=0)
{
position=rand();
position%=n_w*n_e;
}
ptr[n][position]=i;
}
cal(number,n_w,n_e,ptr, f,cost,stat);
get_best(f,ptr,number,n_w,n_e);
while(count<100)
{
if(best<last)
last=best;
for(int i=0;i<n_w*n_e;i++)
l_p[i]=b_p[i];
count++;
sum=0;s_f=0;
for(int n=0;n<number;n++)
sum+=f[n];
for(int n=0;n<number;n++)
{
f[n]=(1-f[n]/sum)*number;
n_f[n]=floor(f[n]);
f[n]-=floor(f[n]);
s_f+=n_f[n];
}
if(s_f<number)
{
left=number-s_f;
trial.clear();
for(int temp=0;temp<number;temp++)
{
if(temp<left)
{
node n1;
n1.result=f[temp];
n1.number=temp;
trial.push_back(n1);
}
else
{
sort(trial.begin(),trial.end(),greater);
if(f[temp]>(trial.begin())->result)
{
trial.erase(trial.begin());
node n1;
n1.result=f[temp];
n1.number=temp;
trial.push_back(n1);
}
}
}
for(vector<node>::iterator iter=trial.begin();iter!=trial.end();iter++)
n_f[iter->number]++;
}
for(int i=0;i<n_w;i++)
{
if(n_f[i]==0)
{
for(int k=0;k<n_w;k++)
if(n_f[k]>1)
{
n_f[k]--;
change(ptr,i,k,n_w,n_e);
break;
}
}
}
for(int i=0;i<number/2;i++)//i and i+number/2 exchange
{
for(int n=0;n<n_w;n++)
{
n_w1[n]=0;
n_w2[n]=0;
}
int wei=rand()%(n_w*n_e);
while(wei==n_w*n_e-1)
wei=rand()%(n_w*n_e);
int *temp=new int[n_e*n_w-wei];
for(int nn=0;nn<wei;nn++)
{
n_w1[ptr[i][nn]]++;
n_w2[ptr[i+number/2][nn]]++;
}
int ww=0;
for(int nn=wei;nn<n_w*n_e;nn++)
for(;ww<n_w*n_e;ww++)
{
if(n_w1[ptr[i+number/2][ww]]<n_e)
{
temp[nn-wei]=ptr[i+number/2][ww];
n_w1[ptr[i+number/2][ww]]++;
ww++;
break;
}
}
ww=0;
for(int nn=wei;nn<n_w*n_e;nn++)
for(;ww<n_w*n_e;ww++)
{
if(n_w1[ptr[i][ww]]<n_e)
{
ptr[i+number/2][nn]=ptr[i][ww];
n_w1[ptr[i][ww]]++;
ww++;
break;
}
}
for(int nn=wei;nn<n_w*n_e;nn++)
ptr[i][nn]=temp[nn-wei];
for(int nn=0;nn<2;nn++)
if(rand()%1000/(double)1000<=0.002)
{
if(nn=0)
{
int bianyi1=rand()%(n_w*n_e);
int bianyi2=rand()%(n_w*n_e);
while(bianyi1==bianyi2)
bianyi2=rand()%(n_w*n_e);
int tt=ptr[i][bianyi1];
ptr[i][bianyi1]=ptr[i][bianyi2];
ptr[i][bianyi2]=tt;
}
else
{
int bianyi1=rand()%(n_w*n_e);
int bianyi2=rand()%(n_w*n_e);
while(bianyi1==bianyi2)
bianyi2=rand()%(n_w*n_e);
int tt=ptr[i+number/2][bianyi1];
ptr[i+number/2][bianyi1]=ptr[i+number/2][bianyi2];
ptr[i+number/2][bianyi2]=tt;
}
}
}
cal(number,n_w,n_e,ptr, f,cost,stat);
get_best(f,ptr,number,n_w,n_e);
}
}
void main()
{
int n_w,n_e,number,attemp;
cout<<"pleast input the number of work and equipment and the number of group and the attemp"<<endl;
cin>>n_w>>n_e>>number>>attemp;
cout<<"please input the scheduling matrix and the cost matrix"<<endl;
for(int i=0;i<n_w;i++)
for(int k=0;k<n_e;k++)
cin>>stat[i][k];
for(int i=0;i<n_w;i++)
for(int k=0;k<n_e;k++)
cin>>cost[i][k];
while(attemp!=0)
{
attemp--;
ga(n_w,n_e,number);
if(best>last)
{
cout<<"the least cost is "<<last<<endl;
cout<<"the route is ";
for(int i=0;i<n_e*n_w;i++)
cout<<l_p[i]<<" ";
cout<<endl;
}
else
{
cout<<"the least cost is "<<best<<endl;
cout<<"the route is ";
for(int i=0;i<n_e*n_w;i++)
cout<<b_p[i]<<" ";
cout<<endl;
}
best=MAX;last=MAX+1;
}
}
/*
#include<iostream>
#include<list>
#include<cmath>
#include<algorithm>
#include<ctime>
using namespace std;
#define MAX 101
#define NUM 10 //种群的个体数量
#define SUM 100//定义种群的进化次数
const double pe=0.0001;//变异的概率
int n,m;//n为工件个数，m为机器数目
int ts;//记录所需的最大时间
int s[MAX][MAX];//s[i][j]表示工件i的第j个工序在s[i][j]的机器上运行
int cost[MAX][MAX];//cost[i][j]表示工件i的第j个工序的耗费时间
int group[NUM+1][MAX*MAX];//存储种群的染色体
int F[NUM+1];//用于记录种群的各个染色体适应值
int Index[NUM+1];//用于排序各个染色体的适应值
double p[NUM+1];//用于记录种群的各个染色体的选择概率
int sk[NUM+1];//用于进化时所需要的某个染色体被选取的次数
int temp[NUM+1][MAX*MAX];//暂存染色体
struct range{//定义一个时间区间的结构体
int l,r;
range(int t1=0,int t2=0){
l=t1;
r=t2;
}
};
list<range> Time[MAX];//用于求解f函数的值
int f(int a[]){//计算该染色体的适应值
int num[MAX];//num[i]记录第i个工件运行到第num[i]个工序上
int last[MAX];//记录工件i的上一次的结束的时间
int i;
for(i=1;i<=n;i++){
num[i]=1;
last[i]=0;
}
for(i=1;i<=m;i++){
Time[i].clear();
range t(0,0);
Time[i].push_back(t);
}
int k=n*m;
list<range>::iterator it;
list<range>::iterator tk;
for(i=1;i<=k;i++){
int p=s[a[i]][num[a[i]]];//得出当前要得到的机器
int cur=a[i];//�
评论0