请选择 进入手机版 | 继续访问电脑版

Hello Mat

 找回密码
 立即注册
查看: 6620|回复: 0

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

[复制链接]

1288

主题

1514

帖子

90

金钱

管理员

Rank: 9Rank: 9Rank: 9

积分
22589
发表于 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
  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<stdlib.h>
  4. #include<time.h>
  5. #include<math.h>
  6. #include"gx_fun.h"  // 适应度函数头文件
  7. #include"cross_gx.h"  // 交叉函数头文件

  8. /* PSO粒子群算法中的两个参数 */
  9. #define sizepop 5000     /* 表示种群数 */
  10. #define itermax 100     /* 进化次数 */
  11. #define num_g 10       /* 10个工序--粒子个体数目  */  
  12. #define num_w 5        /* 5个技工 */

  13. extern double gx[7][11] ={{1,2,3,4,5,6,7,8,9,10,0},
  14.                                                 {1,0,1,0,0,1,0,1,1,1,20},
  15.                                                 {1,1,1,1,1,0,1,0,1,0,5},
  16.                                                 {0,1,0,0,0,0,1,1,0,0,4},
  17.                                                 {1,1,0,0,1,1,0,0,0,0,10},
  18.                                                 {0,0,0,1,0,0,0,1,1,0,4},
  19.                                                 {1,1,2,1,3,1,1,2,1,2,0}};
  20. void main(void)
  21. {
  22.         typedef long clock_t;
  23.         clock_t start,finish;
  24.         double duration;
  25.         start = clock();  //启动计时
  26.         srand((unsigned int)time(NULL));  //随机种子
  27.         srand(time(0));  // 初始化随机种子
  28.         // 变量声明
  29.         int tabu[sizepop][num_g],path[sizepop][num_g],i,j,k,step,kk;  // 禁忌表
  30.         int path1[num_g],path2[num_g],zbest[num_g],gbest[sizepop][num_g];
  31.         double pd[num_g],pk[num_g],pd_s=0,rk,spk;
  32.         double fitness[sizepop],bestfitness,fitnessgbest[sizepop],fitnesszbest;

  33.         // 产生初始粒子和速度
  34.         for(i=0;i<sizepop;i++)
  35.         {
  36.                 for(j=0;j<num_g;j++)
  37.                 {
  38.                         path[i][j] = 1;   // 初始化
  39.                         path2[j] = 1;   // 初始化
  40.                         if(j==int(0))
  41.                                 tabu[i][j] = 0; //初始化        
  42.                         else
  43.                                 tabu[i][j] = 1; //初始化
  44.                 }
  45.                
  46.         }

  47.         // 随机得到path序列
  48.         for(k=0;k<sizepop;k++)
  49.         {
  50.                 for(step=0;step<num_g-1;step++)
  51.                 {
  52.                         pd_s=0;
  53.                         for(kk=0;kk<num_g;kk++)
  54.                         {
  55.                                 pd_s = pd_s + double(tabu[k][kk]); // 求和
  56.                                 pd[kk] = tabu[k][kk];      // 取值
  57.                         }
  58.                         for(kk=0;kk<num_g;kk++)
  59.                         {
  60.                                 pk[kk] = double(pd[kk])/double(pd_s);     // 归一化
  61.                         }
  62.                         rk = double(rand())/double(RAND_MAX); //0-1随机数
  63.                         spk=0;  j=0; // 初始化
  64.                         while(j<=num_g-1)
  65.                         {
  66.                                 if(rk < spk+pk[j])
  67.                                         break;
  68.                                 else
  69.                                 {
  70.                                         spk=spk+pk[j];
  71.                                         j=j+1;
  72.                                         if(j>num_g-1)
  73.                                                 j=num_g-1;
  74.                                 }
  75.                         }
  76.                         tabu[k][j] = 0;       // 初始化
  77.                         path[k][step+1]=j+1;  // 随机产生一个种群
  78.                 }
  79.                 for(i=0;i<num_g;i++)  {path1[i] = path[k][i];}

  80.                 fitness[k] = gx_fun(path1);// 适应度值 = 计算总成本
  81.                 //printf("适应度值:%lf\n",fitness[k]);
  82.         }

  83.         // 找最好的粒子种群--初始化
  84.         bestfitness = fitness[0];         // 最小成本--初始化
  85.         for(i=0;i<sizepop;i++)
  86.         {
  87.                 for(j=0;j<num_g;j++)
  88.                 {
  89.                         if(i==0)
  90.                         {
  91.                                 zbest[j] = path[i][j];   // 全局最佳--初始化
  92.                         }
  93.                         gbest[i][j] = path[i][j];    // 个体最佳--初始化
  94.                 }
  95.                 fitnessgbest[i] = fitness[i];   // 个体最佳适应度值--初始化
  96.         }
  97.         fitnesszbest = bestfitness;        // 全局最佳适应度值--初始化

  98.         //while(fitnesszbest>449)//
  99.         for(i=0;i<itermax;i++)
  100.         {
  101.                 for(j=0;j<sizepop;j++)
  102.                 {
  103.                         //交叉算子
  104.                         for(k=0;k<num_g;k++)
  105.                         {
  106.                                 path1[k] = path[j][k];
  107.                                 //printf("%d\t",path1[k] );
  108.                         }
  109.                         cross_gx(path1,zbest);    // 全局最优个体交叉
  110.                         cross_gx(path1,gbest[j]); // 个体最优交叉
  111.                         // 适应度值更新
  112.                         fitness[j] = gx_fun(path1);// 适应度值 = 计算总成本
  113.                         
  114.                         // 个体最优更新
  115.                         if(fitness[j] < fitnessgbest[j])
  116.                         {
  117.                                 for(k=0;k<num_g;k++)
  118.                                 {
  119.                                         path[j][k] = path1[k];
  120.                                         gbest[j][k] = path1[k];
  121.                                 }
  122.                                 fitnessgbest[j] = fitness[j];
  123.                         }
  124.                         // 群体最优更新
  125.                         if(fitness[j] < fitnesszbest)
  126.                         {
  127.                                 for(k=0;k<num_g;k++)
  128.                                 {
  129.                                         zbest[k] = path1[k];
  130.                                         path[j][k] = path1[k];
  131.                                 }
  132.                                  fitnesszbest = fitness[j];
  133.                         }

  134.                 }
  135.         printf("寻优结果:\n");
  136.         for(k=0;k<num_g;k++)
  137.                 printf("%d\t",zbest[k] );
  138.         printf("适应度值(总成本):%lf\n",fitnesszbest);
  139.         printf("\n\n");  // 输出显示
  140.         }
  141.         printf("\n\n");  // 输出显示
  142.         printf("最优适应度值(总成本):%lf\n",fitnesszbest);
  143.         printf("\n");  // 输出显示
  144.         printf("最优工序\n");
  145.         for(k=0;k<num_g;k++)
  146.                 printf("%d\t",zbest[k] );
  147.         finish = clock(); // 结束计时
  148.         duration=(double)(finish-start)/CLOCKS_PER_SEC;
  149.         printf("\n");  // 输出显示
  150.         printf("程序执行时间:%lf\n",duration);    // 程序执行时间输出显示
  151.         //system("pause");    // 消除屏幕一闪即消失的情况
  152. }
复制代码

gx_fun.cpp
  1. #include<stdio.h>
  2. #include<math.h>
  3. /* 适应度函数 */
  4. /*全局变量*/
  5. #define num_g 10       /* 10个工序--粒子个体数目  */  
  6. #define num_w 5        /* 5个技工 */
  7. extern double gx[7][11];

  8. double gx_fun(int path[num_g])
  9. {
  10.         int i,j,k,flag[num_w][num_g];
  11.         long int mapf[num_w][2];
  12.         double gx1[num_w+2][num_g],cb=0,s[num_w][num_g];
  13.         
  14.         for(j=0;j<num_g;j++)
  15.         {
  16.                 for(i=0;i<num_w+2;i++)
  17.                 {
  18.                         gx1[i][j] = gx[i][path[j]-1]; // 将gx数组重新排序
  19.                 }
  20.         }

  21.         for(i=0;i<num_w;i++) //5个技工
  22.         {
  23.                 mapf[i][0]=0;  // 最小值初始化
  24.                 mapf[i][1]=-100;  // 最大值初始化
  25.                 for(j=0;j<num_g;j++)  //  10个工序
  26.                 {
  27.                         flag[i][j]=0;    // 初始化
  28.                         s[i][j] = 0;
  29.                 }
  30.         }

  31.         for(i=1;i<=num_w;i++) //5个技工
  32.         {
  33.                 k=0;
  34.                 for(j=0;j<num_g;j++)  //  10个工序
  35.                 {
  36.                         if(gx1[i][j]==double(1.0)) // 带*为1
  37.                         {
  38.                                 flag[i-1][k]=j; //记录下标
  39.                                 //printf("%d \t",flag[i-1][k]);
  40.                                 k=k+1;
  41.                         }
  42.                 }
  43.                 //printf("\n");
  44.         }

  45.         // 对flag元素求最大值和最小值
  46.         for(i=0;i<num_w;i++)
  47.         {
  48.                 for(j=0;j<num_g;j++)
  49.                 {
  50.                         mapf[i][0]=flag[i][0];  //求最小值
  51.                         if(flag[i][j]>mapf[i][1])
  52.                                 mapf[i][1]=flag[i][j];  //求最大值
  53.                 }
  54.                 //printf("%d,%d  \t",mapf[i][0],mapf[i][1]);
  55.                 //printf("\n");
  56.         }

  57.         for(i=0;i<num_w;i++)
  58.         {
  59.                 for(j=0;j<num_g;j++)
  60.                 {
  61.                         if(j>=mapf[i][0] && j<=mapf[i][1])
  62.                         {
  63.                                 s[i][j]=gx1[num_w+1][j]*gx[i+1][num_g];
  64.                                 //printf("%lf \t",s[i][j]);
  65.                         }
  66.                         else
  67.                                 s[i][j]=0;
  68.                 }
  69.         }
  70.         
  71.         for(i=0;i<num_w;i++)
  72.         {
  73.                 for(j=0;j<num_g;j++)
  74.                 {
  75.                         cb = double(s[i][j]) + double(cb);// 计算成本
  76.                 }
  77.         }
  78.         //printf("%lf  \t",cb);
  79.         return cb;

  80. }
复制代码
gx_fun.h
  1. #ifndef _GX_FUN_H_
  2. #define _GX_FUN_H_

  3. double gx_fun(int path[]);  // 适应度函数

  4. #endif
复制代码


cross_gx.cpp
  1. #include<stdio.h>
  2. #include<math.h>
  3. #include<time.h>
  4. #include<stdlib.h>
  5. /* 适应度函数 */
  6. /*全局变量*/
  7. #define num_g 10       /* 10个工序--粒子个体数目  */  
  8. #define num_w 5        /* 5个技工 */
  9. extern double gx[7][11];

  10. void cross_gx(int path1[num_g],int path[num_g])
  11. {
  12.         int j,j1,j2,j3,j4,j5,i=0,k,mm=0;
  13.         int pathnew[num_g],jiaocha[num_g];
  14.         double randk;
  15.         srand((unsigned int)time(NULL));  //随机种子
  16.         srand(time(0));  // 初始化随机种子
  17.         randk = double(rand())/double(RAND_MAX); //0-1随机数
  18.         j1 = int(ceil(num_g*randk));
  19.         //printf("%d\n",j1 );
  20.         randk = double(rand())/double(RAND_MAX); //0-1随机数
  21.         j2 = int(ceil(num_g*randk));
  22.         //j1和j2最小值
  23.         if(j1<=j2)
  24.         {
  25.                 j3 = j1;
  26.                 j4 = j2; //最大值
  27.         }
  28.         else
  29.         {
  30.                 j3 = j2;
  31.                 j4 = j1; //最大值
  32.         }

  33.         for(j=0;j<num_g;j++)
  34.         {
  35.                 pathnew[j] = -2;
  36.                 jiaocha[j] = -2;
  37.         }

  38.         for(i=j3-1;i<j4;i++)
  39.         {
  40.                 pathnew[i] = path[i];
  41.         }
  42.         k=0;
  43.         for(i=0;i<num_g;i++)
  44.         {
  45.                 mm=1;
  46.                 for(j=j3-1;j<j4;j++)
  47.                 {
  48.                         if(path1[i]==path[j])
  49.                                 mm=0;
  50.                 }
  51.                 if(mm==1)
  52.                 {
  53.                         jiaocha[k] = path1[i];
  54.                         k=k+1;
  55.                 }
  56.         }
  57.         k=0;
  58.         for(i=0;i<j3-1;i++)
  59.         {
  60.                 pathnew[i] = jiaocha[k];
  61.                 k=k+1;
  62.         }
  63.         for(i=j4;i<num_g;i++)
  64.         {
  65.                 pathnew[i] = jiaocha[k];
  66.                 k=k+1;
  67.         }
  68.         for(i=0;i<num_g;i++)
  69.         {
  70.                 path1[i] = pathnew[i];
  71.         }
  72. }
复制代码
cross_gx.h
  1. #ifndef _CROSS_GX_H_
  2. #define _CROSS_GX_H_

  3. void cross_gx(int path1[],int path[]);  // 适应度函数

  4. #endif
复制代码





算法QQ  3283892722
群智能算法链接http://halcom.cn/forum.php?mod=forumdisplay&fid=73
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Python|Opencv|MATLAB|Halcom.cn ( 蜀ICP备16027072号 )

GMT+8, 2024-3-29 20:26 , Processed in 0.241088 second(s), 21 queries .

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表