基于PSO算法的工序问题求解
一、 问题概述假设有10段工序，一共需要5个技工，每段工序持续的时间不同，技工每小时计费也不同，但技工必须呆到自己负责的工序结束了才能走。（当然，中间不需要技工参加的工序，也是要付出成本的）最终想要得到使成本最低的工序排序。工序13579246810工人成本
技工 a** * ***20
技工 b******* 5
技工 c * * * 4
技工 d* * * * 10
技工 e * * * 4
工序时间1231111122
* 表示技工参与到的工序右列是每个工人的成本，下方是每道工序持续的时间。
二、求解目标 如上表，再此假设工序排列下，因技工要呆到需要他的工序始末，所以总成本如下推得：Ca=(1+2+3+1+1+1+1+1+2+2)*20Cb=(1+2+3+1+1+1+1)*5Cc=(1+1+1+1+1+2)*4……总成本=Ca+Cb+Cc+Cd+Ce=… （优化的最终目标）
例如：解（1）：
工序13526749810工人成本
技工 a** * ***20
技工 b**** *** 5
技工 c * * * 4
技工 d* *** 10
技工 e *** 4
工序时间1231111122
Ca=(1+2+3+1+1+1+1+1+2+2)*20= 300Cb =(1+2+3+1+1+1+1+1) *5=55Cc =(1+1+1+1+1+2)*4=28Cd =(1+2+3+1+1)*10 = 80Ce =(1+1+2)*4 = 16总成本=Ca+Cb+Cc+Cd+Ce= 479
解(2)：
工序13106985274工人成本
技工 a****** 20
技工 b** * ****5
技工 c * ** 4
技工 d* * ** 10
技工 e ** *4
工序时间1221123111
Ca=(1+2+2+1+1+2)*20= 180Cb =(1+2+2+1+1+2+3+1+1+1) *5=75Cc =(2+3+1+1)*4=28Cd =(1+2+2+1+1+2+3+1)*10 = 130Ce =(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 ={{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,path,i,j,k,step,kk;// 禁忌表
int path1,path2,zbest,gbest;
double pd,pk,pd_s=0,rk,spk;
double fitness,bestfitness,fitnessgbest,fitnesszbest;
// 产生初始粒子和速度
for(i=0;i<sizepop;i++)
{
for(j=0;j<num_g;j++)
{
path = 1; // 初始化
path2 = 1; // 初始化
if(j==int(0))
tabu = 0; //初始化
else
tabu = 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); // 求和
pd = tabu; // 取值
}
for(kk=0;kk<num_g;kk++)
{
pk = double(pd)/double(pd_s); // 归一化
}
rk = double(rand())/double(RAND_MAX); //0-1随机数
spk=0;j=0; // 初始化
while(j<=num_g-1)
{
if(rk < spk+pk)
break;
else
{
spk=spk+pk;
j=j+1;
if(j>num_g-1)
j=num_g-1;
}
}
tabu = 0; // 初始化
path=j+1;// 随机产生一个种群
}
for(i=0;i<num_g;i++){path1 = path;}
fitness = gx_fun(path1);// 适应度值 = 计算总成本
//printf("适应度值：%lf\n",fitness);
}
// 找最好的粒子种群--初始化
bestfitness = fitness; // 最小成本--初始化
for(i=0;i<sizepop;i++)
{
for(j=0;j<num_g;j++)
{
if(i==0)
{
zbest = path; // 全局最佳--初始化
}
gbest = path; // 个体最佳--初始化
}
fitnessgbest = fitness; // 个体最佳适应度值--初始化
}
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 = path;
//printf("%d\t",path1 );
}
cross_gx(path1,zbest); // 全局最优个体交叉
cross_gx(path1,gbest); // 个体最优交叉
// 适应度值更新
fitness = gx_fun(path1);// 适应度值 = 计算总成本
// 个体最优更新
if(fitness < fitnessgbest)
{
for(k=0;k<num_g;k++)
{
path = path1;
gbest = path1;
}
fitnessgbest = fitness;
}
// 群体最优更新
if(fitness < fitnesszbest)
{
for(k=0;k<num_g;k++)
{
zbest = path1;
path = path1;
}
fitnesszbest = fitness;
}
}
printf("寻优结果:\n");
for(k=0;k<num_g;k++)
printf("%d\t",zbest );
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 );
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;
double gx_fun(int path)
{
int i,j,k,flag;
long int mapf;
double gx1,cb=0,s;
for(j=0;j<num_g;j++)
{
for(i=0;i<num_w+2;i++)
{
gx1 = gx-1]; // 将gx数组重新排序
}
}
for(i=0;i<num_w;i++) //5个技工
{
mapf=0;// 最小值初始化
mapf=-100;// 最大值初始化
for(j=0;j<num_g;j++)//10个工序
{
flag=0; // 初始化
s = 0;
}
}
for(i=1;i<=num_w;i++) //5个技工
{
k=0;
for(j=0;j<num_g;j++)//10个工序
{
if(gx1==double(1.0)) // 带*为1
{
flag=j; //记录下标
//printf("%d \t",flag);
k=k+1;
}
}
//printf("\n");
}
// 对flag元素求最大值和最小值
for(i=0;i<num_w;i++)
{
for(j=0;j<num_g;j++)
{
mapf=flag;//求最小值
if(flag>mapf)
mapf=flag;//求最大值
}
//printf("%d,%d\t",mapf,mapf);
//printf("\n");
}
for(i=0;i<num_w;i++)
{
for(j=0;j<num_g;j++)
{
if(j>=mapf && j<=mapf)
{
s=gx1*gx;
//printf("%lf \t",s);
}
else
s=0;
}
}
for(i=0;i<num_w;i++)
{
for(j=0;j<num_g;j++)
{
cb = double(s) + 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;
void cross_gx(int path1,int path)
{
int j,j1,j2,j3,j4,j5,i=0,k,mm=0;
int pathnew,jiaocha;
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 = -2;
jiaocha = -2;
}
for(i=j3-1;i<j4;i++)
{
pathnew = path;
}
k=0;
for(i=0;i<num_g;i++)
{
mm=1;
for(j=j3-1;j<j4;j++)
{
if(path1==path)
mm=0;
}
if(mm==1)
{
jiaocha = path1;
k=k+1;
}
}
k=0;
for(i=0;i<j3-1;i++)
{
pathnew = jiaocha;
k=k+1;
}
for(i=j4;i<num_g;i++)
{
pathnew = jiaocha;
k=k+1;
}
for(i=0;i<num_g;i++)
{
path1 = pathnew;
}
}
cross_gx.h#ifndef _CROSS_GX_H_
#define _CROSS_GX_H_
void cross_gx(int path1[],int path[]);// 适应度函数
#endif
页:
[1]