《蚁群优化专业技能训练报告》由会员分享，可在线阅读，更多相关《蚁群优化专业技能训练报告（35页珍藏版）》请在金锄头文库上搜索。
1、0专业技能训练报告学 院： 计算机学院 课程名称： C 程序设计综合实践 完成时间：2015 年 6 月 19 日目 录第 1 部分 实训题目与要求.11. 问题提出.22. 功能要求.23. 任务分工.3第 2 部分 设计实训题目功能.41. 总体设计.42. 算法设计.513. 数据结构.64. 程序代码设计.65. 测试与调试.12第 3 部分 实训总结.131.个人总结.132.结束语.13附录 A 程序清单.13 C 程序设计综合实践评分表.30第 1 部分 实训题目与要求（1）问题提出用经典蚁群算法求解旅行商问题旅行商问题（Traveling Salesman Problem，TS
2、P）又译为旅行推销员问题、货郎担问题，简称为 TSP 问题，是最基本的路线问题，该问题2是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。本课题要求利用经典蚁群算法求解旅行商问题。（2）功能要求重复显示如下图所示的主菜单，在主菜单中选择任意一项，均实现相应功能。. 请输入选项编号(03): .1建立城市信息文件 .2设定相关参数 .3寻优计算 .0退出系统 . 如上图用经典蚁群算法求解旅行商问题主菜单在主菜单中选择 1，建立一个城市信息文件，用于存放城市的坐标等数据。在主菜单中选择 2，可以设定蚁群算法相关的一些参数，如蚁群中蚂蚁的个数，信息素挥发系数等。在
3、主菜单中选择 3，即可进行 TSP 问题寻优计算，要求追加本次设定的参数及最终计算结果到一个文本文件中。在主菜单中选择 0，显示结束信息（如 “感谢使用本软件！已正常退出，按任意键结束！”），按任意键后，退出本系统。说明：可以根据实际情况适当增减主菜单中的菜单项，如增加一些创新功能项等。(3)任务分工本组有 2 人，我和传昇。在刚开始，我们都一起查询了许多资料，比如蚁群优化【1】、蚁群算法原理及其应用【2】等等，了解基本的运行方式和主要函数。成员 分工吴超益1. 主要编程蚁群的运行核心函数，如进行轮盘选择、城市距离、随机抽取、更新环境信息素、/蚂蚁进行搜索、蚂蚁寻优等函数代码。2. 整合俩人的
4、分工的代码，使其总代码能更好的完成，实现功能。33. 修改、更改报告，上交工作结果。李传昇1. 主要编译蚁群的界面和其他复合函数，比如主要界面、进入选择的系统选项、建立城市信息文件、查看相关参数等函数代码。2. 撰写城市信息文件的信息文本并测试程序。3. 负责制作、修改报告，上交工作结果。(4)实验目的1.通过 C 语言综合实践，更加熟练链表、文件、循环、结构体、函数、数组、选择语、数组、顺序的函数。 2.有助于学生了解群体智能（SI）计算，激发其学习计算机科学的兴趣，为其进一步深造打下一定基础并提前开启一道门径，在此基础上可以进一步研究粒子群算法、遗传算法、蛙跳算法、人工鱼算法、野草算法、蜂
5、群算法等。第 2 部分 设计实训题目功能(1) 总设计1. 首先打开软件窗口将显示主菜单内容其中有 4 个选项，分别是【0】 退出系统【1】 建立城市信息文件【2】 设定相关参数【3】 寻优计算。2.在显示的窗口中选择【1】调用 city_information_file()，进入【建立城市信息，件】 ，在进入时，系统自动读取 city.txt 文件的城市信息，并把城市坐标储存在 X,Y的两个数组里。接下来可以选择您想做的事【3】 建立城市坐标信息【2】修改某个城市信息4【1】查看城市坐标信息【0】 返回主菜单 3.接下来返回主菜单后，您可以选择【2】 ，调用 Check_parameters
6、()【查看相关参数】 ，下图所示4.当然，您可以在第二步后，直接选择【3】 （或者在第三步后选择【3】 ） ，系统将调用 fand_calculation()【寻优计算】自动进行寻优计算，计算出最短路径长度、最优路径，如图所示，在【100】后面的 601 就是最短路径长度4.5.6. 最后会将相关参数，最优路径保存在 city_way.txt 文本文件里。在接下下来会跳回主菜单，如果您觉得这不是最理想的数据，您可以继续选【3】 ，直到出现你自认最合理的数据后，在主菜单选择【0】退出系统。（2）算法设计1.main()函数52. city_information_file()（建立城市信息文件）
7、此函数能调用 city.txt 文件内城市信息，将城市坐标保存到 X,Y 的两个数组，该函数还可以修改某个城市信息，查看城市信息、建立城市信息的功能。3.Check_parameters()（设定相关参数）此函数是查询蚁群优化算法的设定的参数， 启发因子、 期望因子、信息素残main（ 主 界 面 ）city_information_file()（ 建 立 城 市 信 息 文 件fand_calculation()（ 寻 优 算 法 ）Check_parameters()（ 设 定 相 关 参 数 ）city_information_file()（ 建 立 城 市 信 息 文 件）修 改 某
8、个 城 市 信 息 查 看 城 市 坐 标 信 息 建 立 城 市 坐 标 信 息6留参数、蚂蚁数量 ant 、迭代次数 R、城市数目，由于防止相关参数设置不合理导致系统瘫痪或不能寻找到最优解，系统已经自动设定相关的参数。4. fand_calculation()（寻优算法）此函数是该编程最核心的部分，实现用经典蚁群算法解决旅行商问题的解法。在进入 fand_calculation()，是首先进入 CTsp:InitData()，将蚂蚁最优路径长度设为最大值，初始化环境信息素，计算城市与城市间的距离。随后调用 srand(nSeed)获得一个随机数，决定蚂蚁从哪个城市开始。接下来进入 CAnt
9、:ChooseNextCity()选择下一个城市，在进入下个城市前涉及到一个经典算法 1，如下图：在得到概率，进入 CAnt:Move()蚂蚁在城市移动，进入 UpdateTrial()进行更新环境信息素，最新的环境信息素 = 留存的信息素 + 新留下的信息素，再进行CAnt:ChooseNextCity()选择下一个城市，如此反复进行下去，到蚂蚁访问全部城市。SCAnt:Search()蚂蚁搜索一次，在执行 SCAnt:Search()前 CAnt:Init()（初始化蚂蚁搜索前调用） 。在进行以上的步奏，直到迭代次数满。进入 CTsp:Search()寻找最优路径的长度，再返回 fand_
10、calculation()打印最优路径，返回主菜单。流程如下：7（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_COU
11、NTN_CITY_COUNT; /城市间信息素，就是环境信息素double g_DistanceN_CITY_COUNTN_CITY_COUNT; /城市间距离fand_calculation()（ 寻 优 算 法 ）CAnt:ChooseNextCity()（ 选 择 下 一 个 城 市 ）CTsp:UpdateTrial()(更 新 环 境 信 息 素)CAnt:Move()（ 蚂 蚁 在 城 市 间 移 动）CAnt:Search()(蚂 蚁 进 行 搜 索 一 次)CAnt:Init()（ 初 始 化 蚂 蚁 搜 索 前调 用 ）CAnt:CalPathLength()(计 算 路 径
12、 长 度)CTsp:Search()(最 优 的 路 径 长 度)输 出 打 印 结 果srand(nSeed)（ 获 得 随机 数 ）CTsp:InitData()(初 始 化 数 据)8int 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;i#include#include #include #include const double a=1.0; /启发因子，信息素的重要程度const d
