基于PSO算法的工序问题求解

Halcom · 发表于 2017-3-15 23:25:06

一、问题概述

假设有10段工序，一共需要5个技工，每段工序持续的时间不同，技工每小时计费也不同，但技工必须呆到自己负责的工序结束了才能走。（当然，中间不需要技工参加的工序，也是要付出成本的）最终想要得到使成本最低的工序排序。

工序	1	3	5	7	9	2	4	6	8	10	工人成本
技工 a	*	*			*			*	*	*	20
技工 b	*	*	*	*	*	*	*				5
技工 c				*		*			*		4
技工 d	*		*			*		*			10
技工 e					*		*		*		4
工序时间	1	2	3	1	1	1	1	1	2	2

* 表示技工参与到的工序

右列是每个工人的成本，下方是每道工序持续的时间。

二、求解目标

如上表，再此假设工序排列下，因技工要呆到需要他的工序始末，所以总成本如下推得：

Ca=(1+2+3+1+1+1+1+1+2+2)*20

Cb=(1+2+3+1+1+1+1)*5

Cc=(1+1+1+1+1+2)*4

……

总成本=Ca+Cb+Cc+Cd+Ce=… （优化的最终目标）

例如：

解（1）：

工序	1	3	5	2	6	7	4	9	8	10	工人成本
技工 a	*	*			*			*	*	*	20
技工 b	*	*	*	*		*	*	*			5
技工 c				*		*			*		4
技工 d	*		*	*	*						10
技工 e							*	*	*		4
工序时间	1	2	3	1	1	1	1	1	2	2

Ca=(1+2+3+1+1+1+1+1+2+2)*20= 300

Cb =(1+2+3+1+1+1+1+1) *5=55

Cc =(1+1+1+1+1+2)*4=28

Cd =(1+2+3+1+1)*10 = 80

Ce =(1+1+2)*4 = 16

总成本=Ca+Cb+Cc+Cd+Ce= 479

解(2)：

工序	1	3	10	6	9	8	5	2	7	4	工人成本
技工 a	*	*	*	*	*	*					20
技工 b	*	*			*		*	*	*	*	5
技工 c						*		*	*		4
技工 d	*			*			*	*			10
技工 e					*	*				*	4
工序时间	1	2	2	1	1	2	3	1	1	1

Ca=(1+2+2+1+1+2)*20= 180

Cb =(1+2+2+1+1+2+3+1+1+1) *5=75

Cc =(2+3+1+1)*4=28

Cd =(1+2+2+1+1+2+3+1)*10 = 130

Ce =(1+2+3+1+1+1)*4 = 36

总成本=Ca+Cb+Cc+Cd+Ce= 449

C语言代码如下：

视频：链接：https://pan.baidu.com/s/16wFcXCHcJInK-fZyJCkW6g 密码：onaz

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include"gx_fun.h" // 适应度函数头文件
#include"cross_gx.h" // 交叉函数头文件
/* PSO粒子群算法中的两个参数 */
#define sizepop 5000 /* 表示种群数 */
#define itermax 100 /* 进化次数 */
#define num_g 10 /* 10个工序--粒子个体数目 */
#define num_w 5 /* 5个技工 */
extern double gx[7][11] ={{1,2,3,4,5,6,7,8,9,10,0},
{1,0,1,0,0,1,0,1,1,1,20},
{1,1,1,1,1,0,1,0,1,0,5},
{0,1,0,0,0,0,1,1,0,0,4},
{1,1,0,0,1,1,0,0,0,0,10},
{0,0,0,1,0,0,0,1,1,0,4},
{1,1,2,1,3,1,1,2,1,2,0}};
void main(void)
{
typedef long clock_t;
clock_t start,finish;
double duration;
start = clock(); //启动计时
srand((unsigned int)time(NULL)); //随机种子
srand(time(0)); // 初始化随机种子
// 变量声明
int tabu[sizepop][num_g],path[sizepop][num_g],i,j,k,step,kk; // 禁忌表
int path1[num_g],path2[num_g],zbest[num_g],gbest[sizepop][num_g];
double pd[num_g],pk[num_g],pd_s=0,rk,spk;
double fitness[sizepop],bestfitness,fitnessgbest[sizepop],fitnesszbest;
// 产生初始粒子和速度
for(i=0;i<sizepop;i++)
{
for(j=0;j<num_g;j++)
{
path[i][j] = 1; // 初始化
path2[j] = 1; // 初始化
if(j==int(0))
tabu[i][j] = 0; //初始化
else
tabu[i][j] = 1; //初始化
}
}
// 随机得到path序列
for(k=0;k<sizepop;k++)
{
for(step=0;step<num_g-1;step++)
{
pd_s=0;
for(kk=0;kk<num_g;kk++)
{
pd_s = pd_s + double(tabu[k][kk]); // 求和
pd[kk] = tabu[k][kk]; // 取值
}
for(kk=0;kk<num_g;kk++)
{
pk[kk] = double(pd[kk])/double(pd_s); // 归一化
}
rk = double(rand())/double(RAND_MAX); //0-1随机数
spk=0; j=0; // 初始化
while(j<=num_g-1)
{
if(rk < spk+pk[j])
break;
else
{
spk=spk+pk[j];
j=j+1;
if(j>num_g-1)
j=num_g-1;
}
}
tabu[k][j] = 0; // 初始化
path[k][step+1]=j+1; // 随机产生一个种群
}
for(i=0;i<num_g;i++) {path1[i] = path[k][i];}
fitness[k] = gx_fun(path1);// 适应度值 = 计算总成本
//printf("适应度值：%lf\n",fitness[k]);
}
// 找最好的粒子种群--初始化
bestfitness = fitness[0]; // 最小成本--初始化
for(i=0;i<sizepop;i++)
{
for(j=0;j<num_g;j++)
{
if(i==0)
{
zbest[j] = path[i][j]; // 全局最佳--初始化
}
gbest[i][j] = path[i][j]; // 个体最佳--初始化
}
fitnessgbest[i] = fitness[i]; // 个体最佳适应度值--初始化
}
fitnesszbest = bestfitness; // 全局最佳适应度值--初始化
//while(fitnesszbest>449)//
for(i=0;i<itermax;i++)
{
for(j=0;j<sizepop;j++)
{
//交叉算子
for(k=0;k<num_g;k++)
{
path1[k] = path[j][k];
//printf("%d\t",path1[k] );
}
cross_gx(path1,zbest); // 全局最优个体交叉
cross_gx(path1,gbest[j]); // 个体最优交叉
// 适应度值更新
fitness[j] = gx_fun(path1);// 适应度值 = 计算总成本
// 个体最优更新
if(fitness[j] < fitnessgbest[j])
{
for(k=0;k<num_g;k++)
{
path[j][k] = path1[k];
gbest[j][k] = path1[k];
}
fitnessgbest[j] = fitness[j];
}
// 群体最优更新
if(fitness[j] < fitnesszbest)
{
for(k=0;k<num_g;k++)
{
zbest[k] = path1[k];
path[j][k] = path1[k];
}
fitnesszbest = fitness[j];
}
}
printf("寻优结果:\n");
for(k=0;k<num_g;k++)
printf("%d\t",zbest[k] );
printf("适应度值（总成本）：%lf\n",fitnesszbest);
printf("\n\n"); // 输出显示
}
printf("\n\n"); // 输出显示
printf("最优适应度值（总成本）：%lf\n",fitnesszbest);
printf("\n"); // 输出显示
printf("最优工序\n");
for(k=0;k<num_g;k++)
printf("%d\t",zbest[k] );
finish = clock(); // 结束计时
duration=(double)(finish-start)/CLOCKS_PER_SEC;
printf("\n"); // 输出显示
printf("程序执行时间：%lf\n",duration); // 程序执行时间输出显示
//system("pause"); // 消除屏幕一闪即消失的情况
}

复制代码

gx_fun.cpp

#include<stdio.h>
#include<math.h>
/* 适应度函数 */
/*全局变量*/
#define num_g 10 /* 10个工序--粒子个体数目 */
#define num_w 5 /* 5个技工 */
extern double gx[7][11];
double gx_fun(int path[num_g])
{
int i,j,k,flag[num_w][num_g];
long int mapf[num_w][2];
double gx1[num_w+2][num_g],cb=0,s[num_w][num_g];
for(j=0;j<num_g;j++)
{
for(i=0;i<num_w+2;i++)
{
gx1[i][j] = gx[i][path[j]-1]; // 将gx数组重新排序
}
}
for(i=0;i<num_w;i++) //5个技工
{
mapf[i][0]=0; // 最小值初始化
mapf[i][1]=-100; // 最大值初始化
for(j=0;j<num_g;j++) // 10个工序
{
flag[i][j]=0; // 初始化
s[i][j] = 0;
}
}
for(i=1;i<=num_w;i++) //5个技工
{
k=0;
for(j=0;j<num_g;j++) // 10个工序
{
if(gx1[i][j]==double(1.0)) // 带*为1
{
flag[i-1][k]=j; //记录下标
//printf("%d \t",flag[i-1][k]);
k=k+1;
}
}
//printf("\n");
}
// 对flag元素求最大值和最小值
for(i=0;i<num_w;i++)
{
for(j=0;j<num_g;j++)
{
mapf[i][0]=flag[i][0]; //求最小值
if(flag[i][j]>mapf[i][1])
mapf[i][1]=flag[i][j]; //求最大值
}
//printf("%d,%d \t",mapf[i][0],mapf[i][1]);
//printf("\n");
}
for(i=0;i<num_w;i++)
{
for(j=0;j<num_g;j++)
{
if(j>=mapf[i][0] && j<=mapf[i][1])
{
s[i][j]=gx1[num_w+1][j]*gx[i+1][num_g];
//printf("%lf \t",s[i][j]);
}
else
s[i][j]=0;
}
}
for(i=0;i<num_w;i++)
{
for(j=0;j<num_g;j++)
{
cb = double(s[i][j]) + double(cb);// 计算成本
}
}
//printf("%lf \t",cb);
return cb;
}

复制代码

gx_fun.h

#ifndef _GX_FUN_H_
#define _GX_FUN_H_
double gx_fun(int path[]); // 适应度函数
#endif

复制代码

cross_gx.cpp

#include<stdio.h>
#include<math.h>
#include<time.h>
#include<stdlib.h>
/* 适应度函数 */
/*全局变量*/
#define num_g 10 /* 10个工序--粒子个体数目 */
#define num_w 5 /* 5个技工 */
extern double gx[7][11];
void cross_gx(int path1[num_g],int path[num_g])
{
int j,j1,j2,j3,j4,j5,i=0,k,mm=0;
int pathnew[num_g],jiaocha[num_g];
double randk;
srand((unsigned int)time(NULL)); //随机种子
srand(time(0)); // 初始化随机种子
randk = double(rand())/double(RAND_MAX); //0-1随机数
j1 = int(ceil(num_g*randk));
//printf("%d\n",j1 );
randk = double(rand())/double(RAND_MAX); //0-1随机数
j2 = int(ceil(num_g*randk));
//j1和j2最小值
if(j1<=j2)
{
j3 = j1;
j4 = j2; //最大值
}
else
{
j3 = j2;
j4 = j1; //最大值
}
for(j=0;j<num_g;j++)
{
pathnew[j] = -2;
jiaocha[j] = -2;
}
for(i=j3-1;i<j4;i++)
{
pathnew[i] = path[i];
}
k=0;
for(i=0;i<num_g;i++)
{
mm=1;
for(j=j3-1;j<j4;j++)
{
if(path1[i]==path[j])
mm=0;
}
if(mm==1)
{
jiaocha[k] = path1[i];
k=k+1;
}
}
k=0;
for(i=0;i<j3-1;i++)
{
pathnew[i] = jiaocha[k];
k=k+1;
}
for(i=j4;i<num_g;i++)
{
pathnew[i] = jiaocha[k];
k=k+1;
}
for(i=0;i<num_g;i++)
{
path1[i] = pathnew[i];
}
}

复制代码

cross_gx.h

#ifndef _CROSS_GX_H_
#define _CROSS_GX_H_
void cross_gx(int path1[],int path[]); // 适应度函数
#endif

复制代码

		自动登录	找回密码
密码			立即注册