原创:工作指派问题解决方案---模拟退火算法C实现

本文忽略了对于模拟退火的算法的理论讲解，读者可参考相关的博文或者其他相关资料，本文着重于算法的实现:
  1 /*****************************************************************************
  2 **    Copyright: NEW NEU laboratory
  3 **    File name: SA_工作指派问题 
  4 **    Description:模拟退火算法解决工作指派问题
  5 **    Author: 1702--GCJ 
  6 **    Version: 1.0
  7 **    Date: 2017/10/4
  8 **    History: 无
  9 *****************************************************************************/
 10 
 11 #include"stdio.h"
 12 #include"stdlib.h"
 13 #include"string.h"
 14 #include "time.h"
 15 #include "math.h"
 16 
 17 /*----------------------------------------------------
 18             @brief 参数配置区 
 19 */
 20 #define WORK_NUM        100         //工作数量
 21 #define WORKER_NUM    100         //工人数量
 22 #define INIT_TEM        (60 + WORK_NUM * 10)    //初始温度
 23 #define END_TEM        60        //终止温度
 24 #define De_TEM            2        //降温函数
 25 #define INTER_WHILE    500        //内循环次数 类似于邻居个数 
 26 
 27 typedef int ElementType;
 28 ElementType **Time;            //存储工人工作时间 指针 
 29 ElementType CurrentTem;        //当前温度
 30     
 31 //定义解的存储类型 向量形式 
 32 typedef struct _Solve{
 33     ElementType *initSolution;            //初始解 //每个元素对应的序号表示工人 总序号表示工人总数 内部元素表示工人对应的工作 
 34     ElementType *currentSolution;        //当前解 
 35     ElementType * optimalSolution;    //最优解 
 36     ElementType *tempSolution;            //临时解   
 37     ElementType  OptimalSolutionValue;        //记录最优解 (总时间) 
 38     ElementType  CurrentSolutionValue;        //记录上次的值 
 39     ElementType  NextSolutionValue    ;        //记录交换后的总时间
 40         
 41 }StrSolve;//存储解结构 
 42 
 43 StrSolve * SolutionSpace ;             //解空间（包含当前解和初始解）指针 
 44 
 45 typedef struct _Tabu{
 46     int smallNum;
 47     int bigNum;        //存储数量大的元素 
 48 }Tabu; //禁忌表结构 
 49 
 50 typedef struct _MotionTable{
 51     Tabu  tabu;                                //存储改变的元素 
 52     ElementType changedistance;        //改变的距离 
 53 }MotionTable;//记录2opt邻域移动信息 
 54 
 55 /*************************************************
 56 **Function: MemBlockWork
 57 **Description: 申请存储工人工作时间的空间 
 58 **Calls: 无
 59 **Called By: ReadDataTxt() 
 60 **Input: 无
 61 **Output: 无 
 62 **Return: 指向存储工人工作时间的指针 
 63 **Others: 无
 64 *************************************************/
 65 ElementType ** MemBlockWork();
 66  
 67 /*************************************************
 68 **Function: ReadDataTxt
 69 **Description: 从txt文档中读取工人工作时间数据
 70 **Calls: MemBlockWork() 
 71 **Called By: main()
 72 **Input: 无
 73 **Output: 无 
 74 **Return: void 
 75 **Others: 里面直接用的全局变量 指针Time
 76 *************************************************/
 77 void ReadDataTxt();
 78 
 79 /*************************************************
 80 **Function: CreateSolutionSpace
 81 **Description: 创建并初始化解空间
 82 **Calls: 无  
 83 **Called By:  Init2Opt()
 84 **Input: worker_num  工人数量 
 85 **Output: 无 
 86 **Return: StrSolve  *指针变量 
 87 **Others: 不用这块内存的时候要逐一释放掉 ！ 
 88 *************************************************/
 89 StrSolve *CreateSolutionSpace(int worker_num);
 90 
 91 /*************************************************
 92 **Function: GetInitSolution
 93 **Description: 获得初始解
 94 **Calls: 无  
 95 **Called By:  Init2Opt()
 96 **Input: StrSolve * 指针变量 
 97 **Output: 无 
 98 **Return: StrSolve  *指针变量 
 99 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ！ 工人工作不能重复及数组空间的数字不能重复 
100 *************************************************/ 
101 void GetInitSolution(StrSolve * strSolve);
102 
103 /*************************************************
104 **Function: Get2optSolution
105 **Description: 得到1个2邻域解 用tempSolution来存储 
106 **Calls:  
107 **Called By:  SA()
108 **Input:  solutionSpace 解空间指针  
109 **Output: 无 
110 **Return: void 
111 **Others: 随机数要注意！ 
112 *************************************************/
113 void Get2optSolution( StrSolve * solutionSpace );
114 
115 /*************************************************
116 **Function: Init2Opt
117 **Description: 初始化SA需要用的值 
118 **Calls:   CreateSolutionSpace()  GetInitSolution()
119 **Called By:  main()
120 **Input: 无 
121 **Output: 无 
122 **Return: void
123 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ！ 不知道为什么只能在Main函数中调用否则 会出现段错误 
124 *************************************************/ 
125 void Init2Opt();
126 
127 /*************************************************
128 **Function: GetSumTime
129 **Description: 获取当前解的总工作时间 
130 **Calls: 
131 **Called By:  SA()
132 **Input:    distance 存储工人工作时间的矩阵指针 Solution 解指针  
133 **Output: 无 
134 **Return: 总工作时间 
135 **Others: 里面用到了WORKER_NUM 宏 
136 *************************************************/
137 int GetSumTime( ElementType **distance,ElementType * Solution);
138 
139 /*************************************************
140 **Function: SA
141 **Description: 模拟退火算法 
142 **Calls: GetSumTime() Get2optSolution()  memcpy()  rand()  exp()
143 **Called By:  main()
144 **Input:    solutionSpace 解空间指针 
145 **Output: 最优值信息 工人工作分配 
146 **Return: 无
147 **Others: 
148 *************************************************/
149 void SA( StrSolve *solutionSpace);
150 
151 /*************************************************
152 **Function: MemFree
153 **Description: 释放申请的动态内存 
154 **Calls: free()
155 **Called By:  main()
156 **Input: distance 存储工人工作时间矩阵      strSolve  解空间的指针 
157 **Output: 无 
158 **Return: void
159 **Others: 这里也可以一步一步的释放掉 各自的指针 因为就用一个.c所以释放内存的操作都在这里进行 
160 *************************************************/ 
161 void MemFree(ElementType ** distance,StrSolve *strSolve);
162 
163 /*******************************************************************************MAIN函数*************************************/
164 int main(int argc,char *argv[])
165 {
166     clock_t start, finish;
167     double  duration;
168     
169     //设置随机数种子 为以后使用rand()做准备 
170    srand((unsigned int)time(0));
171     Init2Opt();
172 
173    //从读取数据开始的起始时间 
174     start = clock();
175     
176     //将工人工作时间的数据存储到Time指向的空间中 
177     ReadDataTxt(Time);
178     
179     //模拟退火算法开始 
180     SA(SolutionSpace);
181     
182     //第二次用模拟退火 
183 //    memcpy( SolutionSpace->currentSolution,SolutionSpace->optimalSolution,sizeof(ElementType)*WORKER_NUM );
184 //    memcpy( SolutionSpace->initSolution,SolutionSpace->optimalSolution,sizeof(ElementType)*WORKER_NUM );
185 //    memcpy( SolutionSpace->tempSolution,SolutionSpace->optimalSolution,sizeof(ElementType)*WORKER_NUM );
186 //    GetInitSolution(SolutionSpace);//初始化解 
187 //    SA(SolutionSpace);
188 
189     //结束时间    
190     finish = clock();
191     duration = (double)(finish - start) / CLOCKS_PER_SEC; 
192     printf("
           SA算法运行时间:%.4f秒       
",duration);
193     
194     //释放申请的内存 
195     MemFree(Time,SolutionSpace);
196     
197    return 0;  
198 } 
199 
200 /*************************************************
201 **Function: MemBlockWork
202 **Description: 申请存储工人工作时间的空间 
203 **Calls: 无
204 **Called By: ReadDataTxt() 
205 **Input: 无
206 **Output: 无 
207 **Return: 指向存储工人工作时间的指针 
208 **Others: 无
209 *************************************************/
210 ElementType ** MemBlockWork()
211 {
212     ElementType ** Distance; 
213     int i=0;
214     
215     //动态申请一块内存存储工人工作时间 
216     Distance = (ElementType **)malloc(sizeof(ElementType *)* WORKER_NUM);
217     for(i = 0;i< WORKER_NUM; i++){
218         Distance[i] = (ElementType *)malloc(sizeof (ElementType )* WORK_NUM);
219     }
220     return Distance;
221 }
222 
223 /*************************************************
224 **Function: ReadDataTxt
225 **Description: 从txt文档中读取工人工作时间数据
226 **Calls: MemBlockWork() 
227 **Called By: main()
228 **Input: 无
229 **Output: 无 
230 **Return: void 
231 **Others: 里面直接用的全局变量 指针Time
232 *************************************************/
233 void ReadDataTxt()
234 {
235     //     FILE *fpRead=fopen("F:\GCJ\Desktop\智能优化方法作业\data.txt","r"); 
236     FILE *fpRead=fopen("data.txt","r");  //从data.txt中读取数据 
237     int i,j;
238     if(fpRead==NULL){  
239           printf("open file data.txt failed!
");
240        exit(1);
241     }
242     Time = MemBlockWork();    //申请一块存储城市数量空间         
243     for( i = 0;i < WORKER_NUM; i++ ){
244         for(j=0 ;j < WORK_NUM ;j++ ){
245             fscanf(fpRead,"%d",&Time[i][j]);//自动读取数据 只要自己能够控制好存储位置即可 
246 //            printf("Time[%d][%d] = %d ",i,j,Time[i][j]);
247         }
248     } 
249     fclose(fpRead);
250 }
251 
252 /*************************************************
253 **Function: CreateSolutionSpace
254 **Description: 创建并初始化解空间
255 **Calls: 无  
256 **Called By:  Init2Opt()
257 **Input: worker_num  工人数量 
258 **Output: 无 
259 **Return: StrSolve  *指针变量 
260 **Others: 不用这块内存的时候要逐一释放掉 ！ 
261 *************************************************/
262 StrSolve *CreateSolutionSpace(int worker_num)
263 {
264     int i;
265     StrSolve *strSolve = (StrSolve *)malloc( sizeof(StrSolve) ) ;
266     strSolve->initSolution = ( ElementType *)malloc(sizeof(ElementType)* worker_num );
267     strSolve->currentSolution = ( ElementType *)malloc(sizeof(ElementType)* worker_num );
268     strSolve->optimalSolution = ( ElementType *)malloc(sizeof(ElementType)* worker_num );
269     strSolve->tempSolution = ( ElementType *)malloc(sizeof(ElementType)* worker_num );
270     
271     //初始化解空间 
272     for(i = 0;i< worker_num;i++){
273         strSolve->initSolution[i] = (ElementType)0;
274         strSolve->currentSolution[i] = (ElementType)0;
275         strSolve->optimalSolution[i] = (ElementType)0;
276         strSolve->tempSolution[i] = (ElementType)0;
277     }
278     strSolve->CurrentSolutionValue  = 0;
279     strSolve->NextSolutionValue  = 0;
280     strSolve->OptimalSolutionValue  = 0; 
281     
282     return strSolve;
283  } 
284  
285 /*************************************************
286 **Function: GetInitSolution
287 **Description: 获得初始解
288 **Calls: 无  
289 **Called By:  Init2Opt()
290 **Input: StrSolve * 指针变量 
291 **Output: 无 
292 **Return: StrSolve  *指针变量 
293 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ！ 工人工作不能重复及数组空间的数字不能重复 
294 *************************************************/ 
295 void GetInitSolution(StrSolve * strSolve)
296 { 
297     int i;
298     //产生0- WORK_NUM-1 (工作数量减1) 之间的随机数不能重复 
299     //默认从0号工作顺序开始 
300     for( i = 0;i < WORKER_NUM;i++){
301         strSolve->initSolution[i] = i;
302         strSolve->currentSolution[i] = i;
303         strSolve->optimalSolution[i] = i;
304         strSolve->tempSolution[i] = i;
305     }
306         
307 }
308 
309 /*************************************************
310 **Function: Get2optSolution
311 **Description: 得到1个2邻域解 用tempSolution来存储 
312 **Calls:  
313 **Called By:  SA()
314 **Input:  solutionSpace 解空间指针  
315 **Output: 无 
316 **Return: void 
317 **Others: 随机数要注意！ 
318 *************************************************/
319 void Get2optSolution( StrSolve * solutionSpace )
320 {
321     //产生一个 0 - - WORKER-1之间的随机数  表示交换工人对应的工作数 [0,WORKER) 
322     MotionTable motiontable; 
323     ElementType temp;
324 //    ElementType changeDistance;
325     int rand1,rand2;
326 //    rand1 = (CityNum-1) *rand()/(RAND_MAX + 1.0);
327     rand1 = rand()%WORKER_NUM;            //[0,WORKER_NUM) 
328     rand2 = rand()%WORKER_NUM;
329     while(  rand2 == rand1 )        //必须产生两个不同的随机数 
330         rand2 = rand()%WORKER_NUM; 
331             
332     //记录交换的两个工人编号 
333     motiontable.tabu.smallNum  = (rand2 >rand1)? rand1:rand2;
334     motiontable.tabu.bigNum =     (rand2 >rand1)? rand2:rand1;
335 
336     //更新当前解 //用临时解作为j解 
337     temp = solutionSpace->tempSolution[ motiontable.tabu.smallNum ];
338     solutionSpace->tempSolution[ motiontable.tabu.smallNum] = solutionSpace->tempSolution[ motiontable.tabu.bigNum ];
339     solutionSpace->tempSolution[ motiontable.tabu.bigNum ] = temp;
340     
341 //    motiontable->changedistance = Get2OptChangeDistance( &motiontable->tabu ,strSolve->tempSolution ); 
342          
343 }
344 
345 /*************************************************
346 **Function: Init2Opt
347 **Description: 初始化SA需要用的值 
348 **Calls:   CreateSolutionSpace()  GetInitSolution()
349 **Called By:  main()
350 **Input: 无 
351 **Output: 无 
352 **Return: void
353 **Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解  ！ 不知道为什么只能在Main函数中调用否则 会出现段错误 
354 *************************************************/ 
355 void Init2Opt()
356 {
357     SolutionSpace = CreateSolutionSpace(WORKER_NUM);//创建解空间 
358     GetInitSolution(SolutionSpace);//初始化解 
359 }
360 
361 /*************************************************
362 **Function: GetSumTime
363 **Description: 获取当前解的总工作时间 
364 **Calls: 
365 **Called By:  SA()
366 **Input:    distance 存储工人工作时间的矩阵指针 Solution 解指针  
367 **Output: 无 
368 **Return: 总工作时间 
369 **Others: 里面用到了WORKER_NUM 宏 
370 *************************************************/
371 int GetSumTime( ElementType **distance,ElementType * Solution)
372 {
373     //只要保证Solution 里面的值不一样即可算出 
374     int i;
375     int SumLevel = 0;
376     for(i = 0; i < WORKER_NUM ; i++){
377         SumLevel += distance[ i ][ Solution[i] ];
378     } 
379     
380     return SumLevel; 
381 }
382 
383 /*************************************************
384 **Function: SA
385 **Description: 模拟退火算法 
386 **Calls: GetSumTime() Get2optSolution()  memcpy()  rand()  exp()
387 **Called By:  main()
388 **Input:    solutionSpace 解空间指针 
389 **Output: 最优值信息 工人工作分配 
390 **Return: 无
391 **Others: 
392 *************************************************/
393 void SA( StrSolve *solutionSpace)
394 {
395     int i;//当前内循环次数 
396     ElementType ChangeValue = 0;
397     double rand1; 
398     
399     //更新初始值和最优解/值
400     solutionSpace->OptimalSolutionValue = GetSumTime( Time,solutionSpace->initSolution );
401     solutionSpace->CurrentSolutionValue = solutionSpace->OptimalSolutionValue; 
402 //    memcpy( solutionSpace->optimalSolution,solutionSpace->initSolution,sizeof(ElementType)* WORKER_NUM );//初始化的时候已经完成 
403     
404     //设定当前温度为初始温度 
405     CurrentTem = INIT_TEM;
406     while( CurrentTem >= END_TEM){
407         
408         for( i = 0;i < INTER_WHILE ;i++){
409             
410             //获取 2邻域一个解 //里面修改了临时解的邻域 在下面的if else if else 处理应对好了 
411             Get2optSolution( solutionSpace );
412              
413             //计算目标值改变大小
414             solutionSpace->NextSolutionValue = GetSumTime( Time,solutionSpace->tempSolution );
415             ChangeValue = solutionSpace->NextSolutionValue - solutionSpace->CurrentSolutionValue ;
416             
417             //Metropolis准则
418             if( ChangeValue < 0 ){//接受该解 
419             
420                 //更新当前解 //不用更新临时解了 因为已经更新好了 
421                 memcpy( solutionSpace->currentSolution,solutionSpace->tempSolution,sizeof(ElementType)*WORKER_NUM );
422                 solutionSpace->CurrentSolutionValue = solutionSpace->NextSolutionValue;
423             
424                 //判断是否更新最优解 
425                 if( solutionSpace->CurrentSolutionValue < solutionSpace->OptimalSolutionValue ){
426                         
427                         //更新最优解
428                         memcpy( solutionSpace->optimalSolution,solutionSpace->currentSolution,sizeof(ElementType)*WORKER_NUM );
429                         solutionSpace->OptimalSolutionValue = solutionSpace->CurrentSolutionValue;
430                 } 
431             }/*Metropolis 准则 end*/ 
432             else if( exp ( -(1.00*ChangeValue)/CurrentTem ) >  (rand1 = rand()/(RAND_MAX+1.0) ) ){ //如果大于随机数 那么也接受该点 
433                 
434                 //更新当前解 //不用更新临时解了 因为已经更新好了 
435                 memcpy( solutionSpace->currentSolution,solutionSpace->tempSolution,sizeof(ElementType)*WORKER_NUM );
436                 solutionSpace->CurrentSolutionValue = solutionSpace->NextSolutionValue;
437             
438                 //判断是否更新最优解 //实际上在这里肯定不会更新的 但是先不改了 
439                 if( solutionSpace->CurrentSolutionValue < solutionSpace->OptimalSolutionValue ){
440                         //更新最优解
441                         memcpy( solutionSpace->optimalSolution,solutionSpace->currentSolution,sizeof(ElementType)*WORKER_NUM );
442                         solutionSpace->OptimalSolutionValue = solutionSpace->CurrentSolutionValue;
443                 } 
444             }
445             else{//没有满足准则的时候 就要更新临时解为原来的currentSolution 因为获得2邻域解的时候修改了tempSolution 
446             
447                 memcpy( solutionSpace->tempSolution,solutionSpace->currentSolution,sizeof(ElementType)*WORKER_NUM );
448     
449             }/*if ...else if ..else end*/
450             
451         }/*for end 内循环*/     
452         
453     //更新降温函数    根据外层的循环次数而定 
454     CurrentTem -=     De_TEM;    
455     
456     } /*while end*/
457     
458     //输出历史最优值及工作分配 
459     printf("
工人工作时间最优值为:%d
",solutionSpace->OptimalSolutionValue);
460     printf("工人分配的工作为:
");
461     for( i = 0;i < WORKER_NUM; i++){
462         printf("工人:%d 分配工作:%d
",i+1,1+solutionSpace->optimalSolution[i]);
463     }
464         printf("
工人工作时间最优值为:%d
",solutionSpace->OptimalSolutionValue);
465 } 
466 
467 /*************************************************
468 **Function: MemFree
469 **Description: 释放申请的动态内存 
470 **Calls: free()
471 **Called By:  main()
472 **Input: distance 存储工人工作时间矩阵      strSolve  解空间的指针 
473 **Output: 无 
474 **Return: void
475 **Others: 这里也可以一步一步的释放掉 各自的指针 因为就用一个.c所以释放内存的操作都在这里进行 
476 *************************************************/ 
477 void MemFree(ElementType ** distance,StrSolve *strSolve)
478 {
479     int i=0;
480     int j = 0;
481     
482     //释放矩阵元素存储区 
483     for(i = 0;i < WORKER_NUM; i++){
484         free( distance[i] );
485     }
486     free(distance);
487     
488     //释放解空间
489     free(strSolve->initSolution);
490     free(strSolve->currentSolution);
491     free(strSolve->optimalSolution);
492     free(strSolve->tempSolution);
493     free(strSolve); 
494 
495 }
View Code

 下面是试验的结果图:

相关资源（源码包+数据+报告）可在下面网址下载：

http://download.csdn.net/download/geself/10191272

运行环境：windows7

IDE        :  DEVC++

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/newneul/p/7629836.html