蚁群优化专业技能训练报告.docx

专业技能训练报告学 院： 计算机学院 课程名称： C程序设计综合实践 完成时间：2015年 6月19日目 录第1部分 实训题目与要求.11. 问题提出.22. 功能要求.23. 任务分工.3第2部分 设计实训题目功能.41. 总体设计.42. 算法设计.53. 数据结构.64. 程序代码设计.65. 测试与调试.12 第3部分 实训总结.131.个人总结.132.结束语.13 附录 A 程序清单.13 C程序设计综合实践评分表.30第1部分 实训题目与要求（1）问题提出用经典蚁群算法求解旅行商问题旅行商问题（Traveling Salesman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。本课题要求利用经典蚁群算法求解旅行商问题。（2）功能要求重复显示如下图所示的主菜单，在主菜单中选择任意一项，均实现相应功能。. 请输入选项编号(03): .1建立城市信息文件 .2设定相关参数 .3寻优计算 .0退出系统 . 如上图用经典蚁群算法求解旅行商问题主菜单在主菜单中选择1，建立一个城市信息文件，用于存放城市的坐标等数据。在主菜单中选择2，可以设定蚁群算法相关的一些参数，如蚁群中蚂蚁的个数，信息素挥发系数等。在主菜单中选择3，即可进行TSP问题寻优计算，要求追加本次设定的参数及最终计算结果到一个文本文件中。在主菜单中选择0，显示结束信息（如“感谢使用本软件！已正常退出，按任意键结束！”），按任意键后，退出本系统。说明：可以根据实际情况适当增减主菜单中的菜单项，如增加一些创新功能项等。(3)任务分工本组有2人，我和传昇。在刚开始，我们都一起查询了许多资料，比如蚁群优化【1】、蚁群算法原理及其应用【2】等等，了解基本的运行方式和主要函数。成员分工吴超益1. 主要编程蚁群的运行核心函数，如进行轮盘选择、城市距离、随机抽取、更新环境信息素、/蚂蚁进行搜索、蚂蚁寻优等函数代码。2. 整合俩人的分工的代码，使其总代码能更好的完成，实现功能。3. 修改、更改报告，上交工作结果。李传昇1. 主要编译蚁群的界面和其他复合函数，比如主要界面、进入选择的系统选项、建立城市信息文件、查看相关参数等函数代码。2. 撰写城市信息文件的信息文本并测试程序。3. 负责制作、修改报告，上交工作结果。(4)实验目的 1.通过C语言综合实践，更加熟练链表、文件、循环、结构体、函数、数组、选择语、数组、顺序的函数。 2.有助于学生了解群体智能（SI）计算，激发其学习计算机科学的兴趣，为其进一步深造打下一定基础并提前开启一道门径，在此基础上可以进一步研究粒子群算法、遗传算法、蛙跳算法、人工鱼算法、野草算法、蜂群算法等。第2部分 设计实训题目功能(1) 总设计1. 首先打开软件窗口将显示主菜单内容其中有4个选项，分别是【0】 退出系统【1】 建立城市信息文件【2】 设定相关参数【3】 寻优计算。2.在显示的窗口中选择【1】调用city_information_file()，进入【建立城市信息，件】 ，在进入时，系统自动读取city.txt文件的城市信息，并把城市坐标储存在X,Y的两个数组里。接下来可以选择您想做的事【3】 建立城市坐标信息【2】修改某个城市信息【1】查看城市坐标信息【0】 返回主菜单 3.接下来返回主菜单后，您可以选择【2】，调用Check_parameters()【查看相关参数】，下图所示4.当然，您可以在第二步后，直接选择【3】（或者在第三步后选择【3】），系统将调用fand_calculation()【寻优计算】自动进行寻优计算，计算出最短路径长度、最优路径，如图所示，在【100】后面的601就是最短路径长度4.5.6. 最后会将相关参数，最优路径保存在city_way.txt文本文件里。在接下下来会跳回主菜单，如果您觉得这不是最理想的数据，您可以继续选【3】，直到出现你自认最合理的数据后，在主菜单选择【0】退出系统。（2）算法设计1.main()函数2. city_information_file()（建立城市信息文件） 此函数能调用city.txt文件内城市信息，将城市坐标保存到X,Y的两个数组，该函数还可以修改某个城市信息，查看城市信息、建立城市信息的功能。3.Check_parameters()（设定相关参数）此函数是查询蚁群优化算法的设定的参数，启发因子、期望因子、信息素残留参数、蚂蚁数量ant 、迭代次数R、城市数目，由于防止相关参数设置不合理导致系统瘫痪或不能寻找到最优解，系统已经自动设定相关的参数。4. fand_calculation()（寻优算法） 此函数是该编程最核心的部分，实现用经典蚁群算法解决旅行商问题的解法。在进入fand_calculation()，是首先进入CTsp:InitData()，将蚂蚁最优路径长度设为最大值，初始化环境信息素，计算城市与城市间的距离。随后调用srand(nSeed)获得一个随机数，决定蚂蚁从哪个城市开始。接下来进入CAnt:ChooseNextCity()选择下一个城市，在进入下个城市前涉及到一个经典算法1，如下图：在得到概率，进入CAnt:Move()蚂蚁在城市移动，进入UpdateTrial()进行更新环境信息素，最新的环境信息素 = 留存的信息素 + 新留下的信息素，再进行CAnt:ChooseNextCity()选择下一个城市，如此反复进行下去，到蚂蚁访问全部城市。SCAnt:Search()蚂蚁搜索一次，在执行SCAnt:Search()前CAnt:Init()（初始化蚂蚁搜索前调用）。在进行以上的步奏，直到迭代次数满。进入CTsp:Search()寻找最优路径的长度，再返回fand_calculation()打印最优路径，返回主菜单。流程如下：（3） 数据结构const double a=1.0; /启发因子，信息素的重要程度const double b=2.0; /期望因子，城市间距离的重要程度const double ROU=0.5; /信息素残留参数const int ant=40; /蚂蚁数量const int R=100; /迭代次数const int N_CITY_COUNT=72; /城市数量const double DBQ=100.0; /总的信息素const double MAX=10e9; /一个标志数double g_TrialN_CITY_COUNTN_CITY_COUNT; /城市间信息素，就是环境信息素double g_DistanceN_CITY_COUNTN_CITY_COUNT; /城市间距离int x10000;/城市横坐标int y10000;/城市纵坐标void city_information_file()/建立城市信息文件.FILE *fp;char s10010,sel10; int i,n100,m100,g100,d,p;while(1) puts(ttt=);puts(ttt查看城市坐标信息请按【1】);puts(ttt修改某个城市信息请按【2】);puts(ttt建立城市坐标信息请按【3】);puts(ttt返回主菜单请按【0】!); puts(ttt=);printf(ttt选择是：); if(fp=fopen(city.txt,r)=NULL) printf(找不到该文件!); exit(0); for(i=0;iN_CITY_COUNT;i+) fscanf(fp,%d%s%d%d,&gi,si,&ni,&mi); xi=ni;yi=mi; fclose(fp);scanf(%s,sel); if(!(strcmp(sel,1)=0|strcmp(sel,0)=0|strcmp(sel,2)=0|strcmp(sel,3)=0) system(CLS); printf(ttt对不起，您输入错误，请重新输入: n); else if(sel0=1) system(CLS);printf(=n); printf(输出的分别是城市序号，城市名，X横坐标和Y纵坐标:n);printf(=n); for(i=0,p=1;iN_CITY_COUNT;i+,p+)if(p%3=0) printf(城市%d %s %d %dn,gi,si,ni,mi);else printf(城市%d %s %d %d ,gi,si,ni,mi);puts(n);system(pause);system(CLS);else if(sel0=2) fp=fopen(city.txt,w+);system(CLS);printf(=n); printf(输出的分别是城市序号，城市名，X横坐标和Y纵坐标:n);printf(=n); for(i=0,p=1;iN_CITY_COUNT;i+,p+)if(p%3=0) printf(城市%d %s %d %dn,gi,si,ni,mi);else printf(城市%d %s %d %d ,gi,si,ni,mi);puts(n);printf(ttt请输入您想修改城市的编号：);scanf(%d,&d);for(i=0;iN_CITY_COUNT;i+)if(i=d-1)puts(ttt您想修改原城市信息：);printf(ttt%d %s %d %dn,gi,si,ni,mi);printf(ttt请输入新的城市名、横坐标和纵坐标：);scanf(%s%d%d,si,&ni,&mi); xi=ni;yi=mi;for(i=0;iN_CITY_COUNT;i+) fprintf(fp,%d %s %d %dn,gi,si,ni,mi);fclose(fp);getchar();system(CLS);else if(sel0=3) system(CLS);puts(=);printf(请依次输入 %d 个城市名，横坐标，纵坐标：n,N_CITY_COUNT);fp=fopen(city.txt,w+);for(i=0;iN_CITY_COUNT;i+)printf(请输入第%d个城市信息：n,i+1);scanf(%s%d%d,si,&ni,&mi);xi=ni;yi=mi;for(i=0;iN_CITY_COUNT;i+) fprintf(fp,%d %s %d %dn,i+1,si,ni,mi); fclose(fp);system(pause);system(CLS); else system(CLS); break;void Check_parameters()/查看相关参数. puts(nnnnn); puts(ttt); printf(ttt 启发因子 : %.1fn,a); printf(ttt 期望因子 : %.1fn,b); printf(ttt 信息素残留参数 : %.1fn,ROU); printf(ttt 蚂蚁数量ant : %dn,ant); printf(ttt 迭代次数R : %dn,R); printf(ttt 城市数目 ：%dn,N_CITY_COUNT); puts(ttt); system(pause);system(CLS);void fand_calculation()/寻优算法 FILE *fp; time_t tm; /用当前时间点初始化随机种子，防止每次运行的结果都相同 time(&tm); unsigned int nSeed=(unsigned int)tm; srand(nSeed); int i; CTsp tsp; /开始搜索 tsp.InitData(); /初始化 tsp.Search(); /开始搜索 char cBuf128;if(fp=fopen(cit_way.txt,a+)=NULL)/把最佳路径保存到city_way.txt文件里printf(找不到文本文件！n);fprintf(fp,相关参数：n);fprintf(fp, 启发因子 : %.1fn,a); fprintf(fp, 期望因子 : %.1fn,b); fprintf(fp, 信息素残留参数 : %.1fn,ROU); fprintf(fp, 蚂蚁数量ant : %dn,ant); fprintf(fp, 迭代次数R : %dn,R); fprintf(fp, 城市数目 ：%dn,N_CITY_COUNT);fprintf(fp,最佳路径：n); printf(n最优路径是 :n); /输出结果 for ( i=0;iN_CITY_COUNT;i+) sprintf(cBuf,%02d,tsp.m_cBestAnt.m_nPathi+1); if(i%10=0&i!=0)fprintf(fp,%dn,tsp.m_cBestAnt.m_nPathi+1);elsefprintf(fp,%d,tsp.m_cBestAnt.m_nPathi+1); if (i % 10 = 0) printf(n); printf(cBuf); fprintf(fp,n);putchar(n);putchar(n); putchar(n);puts(已经把最优路径保存在cit_way.txt里);fclose(fp);system(pause);system(CLS);int main(void)/主调函数，主要界面char sel10,w10;system(color 2A);system(color 2E);while(1)/循环选择，直到选0退出循环printf(nnnnnn);printf(ttt*n);printf(ttt请输入选项编号(03):n); printf(ttt*n); printf(ttt.1建立城市信息文件.n); printf(ttt.2设定相关参数.n);printf(ttt.3寻优计算.n); printf(ttt.0退出系统 .n);printf(ttt*n);printf(ttt选择是：); scanf(%s,sel);if(!(strcmp(sel,1)=0|strcmp(sel,2)=0|strcmp(sel,3)=0|strcmp(sel,0)=0)system(CLS);printf(ttt对不起，您输入错误，请重新输入: n);continue;if(sel0=0)/退出的确定puts(ttt#);puts(ttt您确定要退出吗?); puts(ttt确定请按1,否则请按其它键！);puts(ttt#);printf(ttt选择是：);scanf(%s,w);if(strcmp(w,1)=0)printf(“感谢使用本软件！已正常退出，按任意键结束！”n);break;else system(CLS);elseswitch(sel0)/进入选择的系统选项 case 1: system(CLS);city_information_file();break;/建立城市信息文件. case 2: system(CLS);Check_parameters();break;/查看相关参数. case 3: system(CLS);fand_calculation();break;/寻优计算.return 0;完整程序请参见附录A7. 测试与调试内容：包括合法与非法的测试数据、预期结果、实测结果。要求按照如下表格形式。测试数据类型测试数据预期结果实测结果合法数据主界面显示进入界面，并显示出内容成功显示出内容，并可以进一步执行操作建立城市信息文件读取文件内容成功读取文本文件城市信息，并可以进行下一步修改序号3，城市名广州，坐标分别为52，64的城市信息进入修改界面，输入相关数据，并保存在原文件里面成功修改城市信息，改为，城市名广州，坐标分别为64，52设定相关参数显示相关参数成功显示对应的相关参数，并可以进行下一步寻优算法系统自动计算最优路径成功算出最优路径、最短路程，并保存在city_way.txt文件里非法数据进入建立城市信息界面，选择2修改城市信息，未正确输入信息并强制关闭软件city.txt文件内的城市信息被完全删除打开city.txt文件，里面没有内容进入主界面选择4不能进入下一步系统提示错误，并要求重新输入进入查询相关参数后，选择12312不能 进行下一步系统提示错误，并要求重新输入第3部分 实训总结（1） 个人总结：（吴超益）收获：没有尝试就放弃永远不会成功。勇于挑战，就算输了，也输的值，输的光荣。学习到几个新的编码函数如iostream、time.h、cons等等，对Java，C+有初步的了解，学到NP难问题的初步知识。面对:当知道有C语言综合实践的时候，我原本只想选个比较简单的题目来做的。首先是完成题目以至于不会挂科，其次是熟练C语言的运用，最后提升自己的编码能力。毕竟C语言是学习其他电脑编码（比如c+，c#，jave）的基础。但是到老师公布题目等级，看着大家都有选择三级题目的意向，他们能完成三级的题目，为什么我不能呢?都是同个老师教的，都是同个教室，都是同样的时间，他们能，我一样能，而且我在这门科目付出的时间不比别人少。我毅然选择了三级的蚁群优化。在完成作业的过程中，困难接踵而至，资料缺乏，知识有限，时间有限等等问题困扰着我。有时候会后悔自己选择了太难的题目，开始怀疑自己的能力，感觉个人能力的渺小。对自己的能力不能正确地认识。而当我克服种种困难，不足，终于成功编写出代码。 困难：不懂C+，Java等高级编程，没有资料，对于蚁群基本了解匮乏，不懂蚁群的算法，时间有限。解决：向图书馆借C+,Jave书看，购买蚁群优化书，上网学习所需的知识，好好利用时间（2） 结束语感谢我的队友（李传胜）共同克服困难完成这次作业，感谢同班同学大力的支持，感谢师兄的点化，感谢老师的教导。谢谢您们！附录A 程序清单#include#include#include #include #include const double a=1.0; /启发因子，信息素的重要程度const double b=2.0; /期望因子，城市间距离的重要程度const double ROU=0.5; /信息素残留参数const int ant=40; /蚂蚁数量const int R=100; /迭代次数const int N_CITY_COUNT=72; /城市数量const double DBQ=100.0; /总的信息素const double MAX=10e9; /一个标志数double g_TrialN_CITY_COUNTN_CITY_COUNT; /城市间信息素，就是环境信息素double g_DistanceN_CITY_COUNTN_CITY_COUNT; /城市间距离int x10000;/城市横坐标int y10000;/城市纵坐标void city_information_file()/建立城市信息文件.FILE *fp;char s10010,sel10; int i,n100,m100,g100,d,p;while(1) puts(ttt=);puts(ttt查看城市坐标信息请按【1】);puts(ttt修改某个城市信息请按【2】);puts(ttt建立城市坐标信息请按【3】);puts(ttt返回主菜单请按【0】!); puts(ttt=);printf(ttt选择是：); if(fp=fopen(city.txt,r)=NULL) printf(找不到该文件!); exit(0); for(i=0;iN_CITY_COUNT;i+) fscanf(fp,%d%s%d%d,&gi,si,&ni,&mi); xi=ni;yi=mi; fclose(fp);scanf(%s,sel); if(!(strcmp(sel,1)=0|strcmp(sel,0)=0|strcmp(sel,2)=0|strcmp(sel,3)=0) system(CLS); printf(ttt对不起，您输入错误，请重新输入: n); else if(sel0=1) system(CLS);printf(=n); printf(输出的分别是城市序号，城市名，X横坐标和Y纵坐标:n);printf(=n); for(i=0,p=1;iN_CITY_COUNT;i+,p+)if(p%3=0) printf(城市%d %s %d %dn,gi,si,ni,mi);else printf(城市%d %s %d %d ,gi,si,ni,mi);puts(n);system(pause);system(CLS);else if(sel0=2) fp=fopen(city.txt,w+);system(CLS);printf(=n); printf(输出的分别是城市序号，城市名，X横坐标和Y纵坐标:n);printf(=n); for(i=0,p=1;iN_CITY_COUNT;i+,p+)if(p%3=0) printf(城市%d %s %d %dn,gi,si,ni,mi);else printf(城市%d %s %d %d ,gi,si,ni,mi);puts(n);printf(ttt请输入您想修改城市的编号：);scanf(%d,&d);for(i=0;iN_CITY_COUNT;i+)if(i=d-1)puts(ttt您想修改原城市信息：);printf(ttt%d %s %d %dn,gi,si,ni,mi);printf(ttt请输入新的城市名、横坐标和纵坐标：);scanf(%s%d%d,si,&ni,&mi); xi=ni;yi=mi;for(i=0;iN_CITY_COUNT;i+) fprintf(fp,%d %s %d %dn,gi,si,ni,mi);fclose(fp);getchar();system(CLS);else if(sel0=3) system(CLS);puts(=);printf(请依次输入 %d 个城市名，横坐标，纵坐标：n,N_CITY_COUNT);fp=fopen(city.txt,w+);for(i=0;iN_CITY_COUNT;i+)printf(请输入第%d个城市信息：n,i+1);scanf(%s%d%d,si,&ni,&mi);xi=ni;yi=mi;for(i=0;iN_CITY_COUNT;i+) fprintf(fp,%d %s %d %dn,i+1,si,ni,mi); fclose(fp);system(pause);system(CLS); else system(CLS); break;void Check_parameters()/查看相关参数. puts(nnnnn); puts(ttt); printf(ttt 启发因子 : %.1fn,a); printf(ttt 期望因子 : %.1fn,b); printf(ttt 信息素残留参数 : %.1fn,ROU); printf(ttt 蚂蚁数量ant : %dn,ant); printf(ttt 迭代次数R : %dn,R); printf(ttt 城市数目 ：%dn,N_CITY_COUNT); puts(ttt); system(pause);system(CLS);/返回指定范围内的随机整数int rnd(int nLow,int nUpper) return nLow+(nUpper-nLow)*rand()/(RAND_MAX+1);/返回指定范围内的随机浮点数double rnd(double dbLow,double dbUpper) double dbTemp=rand()/(double)RAND_MAX+1.0); return dbLow+dbTemp*(dbUpper-dbLow);/返回浮点数四舍五入取整后的浮点数double ROUND(double dbA) return (double)(int)(dbA+0.5);/定义蚂蚁类class CAntpublic: CAnt(void); CAnt(void);public: int m_nPathN_CITY_COUNT; /蚂蚁走的路径 double m_dbPathLength; /蚂蚁走过的路径长度 int m_nAllowedCityN_CITY_COUNT; /没去过的城市 int m_nCurCityNo; /当前所在城市编号 int m_nMovedCityCount; /已经去过的城市数量public: int ChooseNextCity(); /选择下一个城市 void Init(); /初始化 void Move(); /蚂蚁在城市间移动 void Search(); /搜索路径 void CalPathLength(); /计算蚂蚁走过的路径长度;CAnt:CAnt(void)CAnt:CAnt(void)/初始化函数，蚂蚁搜索前调用void CAnt:Init() int i; for ( i=0;iN_CITY_COUNT;i+) m_nAllowedCityi=1; /设置全部城市为没有去过 m_nPathi=0; /蚂蚁走的路径全部设置为0 /蚂蚁走过的路径长度设置为0 m_dbPathLength=0.0; /随机选择一个出发城市 m_nCurCityNo=rnd(0,N_CITY_COUNT); /把出发城市保存入路径数组中 m_nPath0=m_nCurCityNo; /标识出发城市为已经去过了 m_nAllowedCitym_nCurCityNo=0; /已经去过的城市数量设置为1 m_nMovedCityCount=1; /选择下一个城市,返回值 为城市编号int CAnt:ChooseNextCity() /计算当前城市和没去过的城市之间的信息素总和 int nSelectedCity=-1,i; double dbTotal=0.0; double probN_CITY_COUNT; /保存各个城市被选中的概率 for (i=0;i 0.0) /总的信息素值大于0 dbTemp=rnd(0.0,dbTotal); /取一个随机数 for ( i=0;iN_CITY_COUNT;i+) if (m_nAllowedCityi = 1) /城市没