本文忽略了对于模拟退火的算法的理论讲解，读者可参考相关的博文或者其他相关资料，本文着重于算法的实现:
/*****************************************************************************
** Copyright: NEW NEU laboratory
** File name: SA_工作指派问题
** Description:模拟退火算法解决工作指派问题
** Author: 1702--GCJ
** Version: 1.0
** Date: 2017/10/4
** History: 无
*****************************************************************************/ #include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include "time.h"
#include "math.h" /*----------------------------------------------------
@brief 参数配置区
*/
#define WORK_NUM 100 //工作数量
#define WORKER_NUM 100 //工人数量
#define INIT_TEM (60 + WORK_NUM * 10) //初始温度
#define END_TEM 60 //终止温度
#define De_TEM 2 //降温函数
#define INTER_WHILE 500 //内循环次数 类似于邻居个数 typedef int ElementType;
ElementType **Time; //存储工人工作时间 指针
ElementType CurrentTem; //当前温度 //定义解的存储类型 向量形式
typedef struct _Solve{
ElementType *initSolution; //初始解 //每个元素对应的序号表示工人 总序号表示工人总数 内部元素表示工人对应的工作
ElementType *currentSolution; //当前解
ElementType * optimalSolution; //最优解
ElementType *tempSolution; //临时解
ElementType OptimalSolutionValue; //记录最优解 (总时间)
ElementType CurrentSolutionValue; //记录上次的值
ElementType NextSolutionValue ; //记录交换后的总时间 }StrSolve;//存储解结构 StrSolve * SolutionSpace ; //解空间（包含当前解和初始解）指针 typedef struct _Tabu{
int smallNum;
int bigNum; //存储数量大的元素
}Tabu; //禁忌表结构 typedef struct _MotionTable{
Tabu tabu; //存储改变的元素
ElementType changedistance; //改变的距离
}MotionTable;//记录2opt邻域移动信息 /*************************************************
**Function: MemBlockWork
**Description: 申请存储工人工作时间的空间
**Calls: 无
**Called By: ReadDataTxt()
**Input: 无
**Output: 无
**Return: 指向存储工人工作时间的指针
**Others: 无
*************************************************/
ElementType ** MemBlockWork(); /*************************************************
**Function: ReadDataTxt
**Description: 从txt文档中读取工人工作时间数据
**Calls: MemBlockWork()
**Called By: main()
**Input: 无
**Output: 无
**Return: void
**Others: 里面直接用的全局变量 指针Time
*************************************************/
void ReadDataTxt(); /*************************************************
**Function: CreateSolutionSpace
**Description: 创建并初始化解空间
**Calls: 无
**Called By: Init2Opt()
**Input: worker_num 工人数量
**Output: 无
**Return: StrSolve *指针变量
**Others: 不用这块内存的时候要逐一释放掉 ！
*************************************************/
StrSolve *CreateSolutionSpace(int worker_num); /*************************************************
**Function: GetInitSolution
**Description: 获得初始解
**Calls: 无
**Called By: Init2Opt()
**Input: StrSolve * 指针变量
**Output: 无
**Return: StrSolve *指针变量
**Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解 ！ 工人工作不能重复及数组空间的数字不能重复
*************************************************/
void GetInitSolution(StrSolve * strSolve); /*************************************************
**Function: Get2optSolution
**Description: 得到1个2邻域解 用tempSolution来存储
**Calls:
**Called By: SA()
**Input: solutionSpace 解空间指针
**Output: 无
**Return: void
**Others: 随机数要注意！
*************************************************/
void Get2optSolution( StrSolve * solutionSpace ); /*************************************************
**Function: Init2Opt
**Description: 初始化SA需要用的值
**Calls: CreateSolutionSpace() GetInitSolution()
**Called By: main()
**Input: 无
**Output: 无
**Return: void
**Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解 ！ 不知道为什么只能在Main函数中调用否则 会出现段错误
*************************************************/
void Init2Opt(); /*************************************************
**Function: GetSumTime
**Description: 获取当前解的总工作时间
**Calls:
**Called By: SA()
**Input: distance 存储工人工作时间的矩阵指针 Solution 解指针
**Output: 无
**Return: 总工作时间
**Others: 里面用到了WORKER_NUM 宏
*************************************************/
int GetSumTime( ElementType **distance,ElementType * Solution); /*************************************************
**Function: SA
**Description: 模拟退火算法
**Calls: GetSumTime() Get2optSolution() memcpy() rand() exp()
**Called By: main()
**Input: solutionSpace 解空间指针
**Output: 最优值信息 工人工作分配
**Return: 无
**Others:
*************************************************/
void SA( StrSolve *solutionSpace); /*************************************************
**Function: MemFree
**Description: 释放申请的动态内存
**Calls: free()
**Called By: main()
**Input: distance 存储工人工作时间矩阵 strSolve 解空间的指针
**Output: 无
**Return: void
**Others: 这里也可以一步一步的释放掉 各自的指针 因为就用一个.c所以释放内存的操作都在这里进行
*************************************************/
void MemFree(ElementType ** distance,StrSolve *strSolve); /*******************************************************************************MAIN函数*************************************/
int main(int argc,char *argv[])
{
clock_t start, finish;
double duration; //设置随机数种子 为以后使用rand()做准备
srand((unsigned int)time());
Init2Opt(); //从读取数据开始的起始时间
start = clock(); //将工人工作时间的数据存储到Time指向的空间中
ReadDataTxt(Time); //模拟退火算法开始
SA(SolutionSpace); //第二次用模拟退火
// memcpy( SolutionSpace->currentSolution,SolutionSpace->optimalSolution,sizeof(ElementType)*WORKER_NUM );
// memcpy( SolutionSpace->initSolution,SolutionSpace->optimalSolution,sizeof(ElementType)*WORKER_NUM );
// memcpy( SolutionSpace->tempSolution,SolutionSpace->optimalSolution,sizeof(ElementType)*WORKER_NUM );
// GetInitSolution(SolutionSpace);//初始化解
// SA(SolutionSpace); //结束时间
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
printf("\n SA算法运行时间:%.4f秒 \n",duration); //释放申请的内存
MemFree(Time,SolutionSpace); return ;
} /*************************************************
**Function: MemBlockWork
**Description: 申请存储工人工作时间的空间
**Calls: 无
**Called By: ReadDataTxt()
**Input: 无
**Output: 无
**Return: 指向存储工人工作时间的指针
**Others: 无
*************************************************/
ElementType ** MemBlockWork()
{
ElementType ** Distance;
int i=; //动态申请一块内存存储工人工作时间
Distance = (ElementType **)malloc(sizeof(ElementType *)* WORKER_NUM);
for(i = ;i< WORKER_NUM; i++){
Distance[i] = (ElementType *)malloc(sizeof (ElementType )* WORK_NUM);
}
return Distance;
} /*************************************************
**Function: ReadDataTxt
**Description: 从txt文档中读取工人工作时间数据
**Calls: MemBlockWork()
**Called By: main()
**Input: 无
**Output: 无
**Return: void
**Others: 里面直接用的全局变量 指针Time
*************************************************/
void ReadDataTxt()
{
// FILE *fpRead=fopen("F:\\GCJ\\Desktop\\智能优化方法作业\\data.txt","r");
FILE *fpRead=fopen("data.txt","r"); //从data.txt中读取数据
int i,j;
if(fpRead==NULL){
printf("open file data.txt failed!\n");
exit();
}
Time = MemBlockWork(); //申请一块存储城市数量空间
for( i = ;i < WORKER_NUM; i++ ){
for(j= ;j < WORK_NUM ;j++ ){
fscanf(fpRead,"%d",&Time[i][j]);//自动读取数据 只要自己能够控制好存储位置即可
// printf("Time[%d][%d] = %d ",i,j,Time[i][j]);
}
}
fclose(fpRead);
} /*************************************************
**Function: CreateSolutionSpace
**Description: 创建并初始化解空间
**Calls: 无
**Called By: Init2Opt()
**Input: worker_num 工人数量
**Output: 无
**Return: StrSolve *指针变量
**Others: 不用这块内存的时候要逐一释放掉 ！
*************************************************/
StrSolve *CreateSolutionSpace(int worker_num)
{
int i;
StrSolve *strSolve = (StrSolve *)malloc( sizeof(StrSolve) ) ;
strSolve->initSolution = ( ElementType *)malloc(sizeof(ElementType)* worker_num );
strSolve->currentSolution = ( ElementType *)malloc(sizeof(ElementType)* worker_num );
strSolve->optimalSolution = ( ElementType *)malloc(sizeof(ElementType)* worker_num );
strSolve->tempSolution = ( ElementType *)malloc(sizeof(ElementType)* worker_num ); //初始化解空间
for(i = ;i< worker_num;i++){
strSolve->initSolution[i] = (ElementType);
strSolve->currentSolution[i] = (ElementType);
strSolve->optimalSolution[i] = (ElementType);
strSolve->tempSolution[i] = (ElementType);
}
strSolve->CurrentSolutionValue = ;
strSolve->NextSolutionValue = ;
strSolve->OptimalSolutionValue = ; return strSolve;
} /*************************************************
**Function: GetInitSolution
**Description: 获得初始解
**Calls: 无
**Called By: Init2Opt()
**Input: StrSolve * 指针变量
**Output: 无
**Return: StrSolve *指针变量
**Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解 ！ 工人工作不能重复及数组空间的数字不能重复
*************************************************/
void GetInitSolution(StrSolve * strSolve)
{
int i;
//产生0- WORK_NUM-1 (工作数量减1) 之间的随机数不能重复
//默认从0号工作顺序开始
for( i = ;i < WORKER_NUM;i++){
strSolve->initSolution[i] = i;
strSolve->currentSolution[i] = i;
strSolve->optimalSolution[i] = i;
strSolve->tempSolution[i] = i;
} } /*************************************************
**Function: Get2optSolution
**Description: 得到1个2邻域解 用tempSolution来存储
**Calls:
**Called By: SA()
**Input: solutionSpace 解空间指针
**Output: 无
**Return: void
**Others: 随机数要注意！
*************************************************/
void Get2optSolution( StrSolve * solutionSpace )
{
//产生一个 0 - - WORKER-1之间的随机数 表示交换工人对应的工作数 [0,WORKER)
MotionTable motiontable;
ElementType temp;
// ElementType changeDistance;
int rand1,rand2;
// rand1 = (CityNum-1) *rand()/(RAND_MAX + 1.0);
rand1 = rand()%WORKER_NUM; //[0,WORKER_NUM)
rand2 = rand()%WORKER_NUM;
while( rand2 == rand1 ) //必须产生两个不同的随机数
rand2 = rand()%WORKER_NUM; //记录交换的两个工人编号
motiontable.tabu.smallNum = (rand2 >rand1)? rand1:rand2;
motiontable.tabu.bigNum = (rand2 >rand1)? rand2:rand1; //更新当前解 //用临时解作为j解
temp = solutionSpace->tempSolution[ motiontable.tabu.smallNum ];
solutionSpace->tempSolution[ motiontable.tabu.smallNum] = solutionSpace->tempSolution[ motiontable.tabu.bigNum ];
solutionSpace->tempSolution[ motiontable.tabu.bigNum ] = temp; // motiontable->changedistance = Get2OptChangeDistance( &motiontable->tabu ,strSolve->tempSolution ); } /*************************************************
**Function: Init2Opt
**Description: 初始化SA需要用的值
**Calls: CreateSolutionSpace() GetInitSolution()
**Called By: main()
**Input: 无
**Output: 无
**Return: void
**Others: 这里在初始化解的时候可以用其他元启发式算法得出一个较好的解 ！ 不知道为什么只能在Main函数中调用否则 会出现段错误
*************************************************/
void Init2Opt()
{
SolutionSpace = CreateSolutionSpace(WORKER_NUM);//创建解空间
GetInitSolution(SolutionSpace);//初始化解
} /*************************************************
**Function: GetSumTime
**Description: 获取当前解的总工作时间
**Calls:
**Called By: SA()
**Input: distance 存储工人工作时间的矩阵指针 Solution 解指针
**Output: 无
**Return: 总工作时间
**Others: 里面用到了WORKER_NUM 宏
*************************************************/
int GetSumTime( ElementType **distance,ElementType * Solution)
{
//只要保证Solution 里面的值不一样即可算出
int i;
int SumLevel = ;
for(i = ; i < WORKER_NUM ; i++){
SumLevel += distance[ i ][ Solution[i] ];
} return SumLevel;
} /*************************************************
**Function: SA
**Description: 模拟退火算法
**Calls: GetSumTime() Get2optSolution() memcpy() rand() exp()
**Called By: main()
**Input: solutionSpace 解空间指针
**Output: 最优值信息 工人工作分配
**Return: 无
**Others:
*************************************************/
void SA( StrSolve *solutionSpace)
{
int i;//当前内循环次数
ElementType ChangeValue = ;
double rand1; //更新初始值和最优解/值
solutionSpace->OptimalSolutionValue = GetSumTime( Time,solutionSpace->initSolution );
solutionSpace->CurrentSolutionValue = solutionSpace->OptimalSolutionValue;
// memcpy( solutionSpace->optimalSolution,solutionSpace->initSolution,sizeof(ElementType)* WORKER_NUM );//初始化的时候已经完成 //设定当前温度为初始温度
CurrentTem = INIT_TEM;
while( CurrentTem >= END_TEM){ for( i = ;i < INTER_WHILE ;i++){ //获取 2邻域一个解 //里面修改了临时解的邻域 在下面的if else if else 处理应对好了
Get2optSolution( solutionSpace ); //计算目标值改变大小
solutionSpace->NextSolutionValue = GetSumTime( Time,solutionSpace->tempSolution );
ChangeValue = solutionSpace->NextSolutionValue - solutionSpace->CurrentSolutionValue ; //Metropolis准则
if( ChangeValue < ){//接受该解 //更新当前解 //不用更新临时解了 因为已经更新好了
memcpy( solutionSpace->currentSolution,solutionSpace->tempSolution,sizeof(ElementType)*WORKER_NUM );
solutionSpace->CurrentSolutionValue = solutionSpace->NextSolutionValue; //判断是否更新最优解
if( solutionSpace->CurrentSolutionValue < solutionSpace->OptimalSolutionValue ){ //更新最优解
memcpy( solutionSpace->optimalSolution,solutionSpace->currentSolution,sizeof(ElementType)*WORKER_NUM );
solutionSpace->OptimalSolutionValue = solutionSpace->CurrentSolutionValue;
}
}/*Metropolis 准则 end*/
else if( exp ( -(1.00*ChangeValue)/CurrentTem ) > (rand1 = rand()/(RAND_MAX+1.0) ) ){ //如果大于随机数 那么也接受该点 //更新当前解 //不用更新临时解了 因为已经更新好了
memcpy( solutionSpace->currentSolution,solutionSpace->tempSolution,sizeof(ElementType)*WORKER_NUM );
solutionSpace->CurrentSolutionValue = solutionSpace->NextSolutionValue; //判断是否更新最优解 //实际上在这里肯定不会更新的 但是先不改了
if( solutionSpace->CurrentSolutionValue < solutionSpace->OptimalSolutionValue ){
//更新最优解
memcpy( solutionSpace->optimalSolution,solutionSpace->currentSolution,sizeof(ElementType)*WORKER_NUM );
solutionSpace->OptimalSolutionValue = solutionSpace->CurrentSolutionValue;
}
}
else{//没有满足准则的时候 就要更新临时解为原来的currentSolution 因为获得2邻域解的时候修改了tempSolution memcpy( solutionSpace->tempSolution,solutionSpace->currentSolution,sizeof(ElementType)*WORKER_NUM ); }/*if ...else if ..else end*/ }/*for end 内循环*/ //更新降温函数 根据外层的循环次数而定
CurrentTem -= De_TEM; } /*while end*/ //输出历史最优值及工作分配
printf("\n工人工作时间最优值为:%d\n",solutionSpace->OptimalSolutionValue);
printf("工人分配的工作为:\n");
for( i = ;i < WORKER_NUM; i++){
printf("工人:%d 分配工作:%d\n",i+,+solutionSpace->optimalSolution[i]);
}
printf("\n工人工作时间最优值为:%d\n",solutionSpace->OptimalSolutionValue);
} /*************************************************
**Function: MemFree
**Description: 释放申请的动态内存
**Calls: free()
**Called By: main()
**Input: distance 存储工人工作时间矩阵 strSolve 解空间的指针
**Output: 无
**Return: void
**Others: 这里也可以一步一步的释放掉 各自的指针 因为就用一个.c所以释放内存的操作都在这里进行
*************************************************/
void MemFree(ElementType ** distance,StrSolve *strSolve)
{
int i=;
int j = ; //释放矩阵元素存储区
for(i = ;i < WORKER_NUM; i++){
free( distance[i] );
}
free(distance); //释放解空间
free(strSolve->initSolution);
free(strSolve->currentSolution);
free(strSolve->optimalSolution);
free(strSolve->tempSolution);
free(strSolve); }
下面是试验的结果图:
相关资源（源码包+数据+报告）可在下面网址下载：
http://download.****.net/download/geself/10191272
运行环境：windows7
IDE : DEVC++