文档介绍:目录
1 前言 1
2 需求分析 1
1
1
1
1
3 概要设计与详细设计 1
2
3
4 编码与实现 4
4
6
5 课程设计总结 15
参考文献 ...15
致谢 15
1 前言
使用C语言编程,设计一个有效的算法,模拟蚂蚁觅食的过程。
2 需求分析
(1)各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。
(2)当一只找到食物以后,它会向环境释放一种信息素,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物。
(3)有些蚂蚁并没有象其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果令开辟的道路比原来的其他道路更短,那么,渐渐,更多的蚂蚁被吸引到这条较短的路上来。
(4)最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着。
(1)构建二维数组将每条路径的信息素量、相应路径的信息素增量和城市距离放入其中。
(2)输入两个城市间的坐标,并得到两个城市间的最近距离。
(3)画出所有模块的流程图;
(4)编写代码;
(5)程序分析与调试。
(1)WINDOWS2000/XP系统
(2)
C语言
3 概要设计与详细设计
。
开始
初始化各参数,输入城市坐标
为各蚂蚁设置其固定的起始城市
每只蚂蚁开始访问,并记录其访问的路径及长度
和处在同一次迭代的其他蚂蚁路径相比,是否是最优?
将其存为系统求解结果
Y
更新路径上的信息素
N
迭代是否结束?
N
Y
是否对结果进行检验?
用户进行测试检验
Y
结束
N
系统流程图
。
蚂蚁访问过程
从起始城市出发,并将初始城市设为被访问
选择一个未访问的城市,开始判断
是否符合?
N
Y
计算其转移概率,用得出的概率赌***方式选择候选路径
访问该城市,并设置其为被访问
Y
所有城市是否访问完?
出口
N
4 编码与实现
程序开始运行,蚂蚁们开始从窝里出动了,寻找食物;他们会顺着屏幕爬满整个画面,直到找到食物再返回窝。
其中,‘D’点表示食物,‘A’表示窝,白色块表示障碍物,‘+’就是蚂蚁了。
预期的结果:各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后,它会向环境释放一种信息素,吸引其他的蚂蚁过来,这样越来越多的蚂蚁会找到食物!有些蚂蚁并没有象其它蚂蚁一样总重复同样的路,他们会另辟蹊径,如果令开辟的道路比原来的其他道路更短,那么,渐渐,更多的蚂蚁被吸引到这条较短的路上来。最后,经过一段时间运行,可能会出现一条最短的路径被大多数蚂蚁重复着。
1、范围:蚂蚁观察到的范围是一个方格世界,蚂蚁有一个参数为速度半径(一般是3),那么它能观察到的范围就是3*3个方格世界,并且能移动的距离也在这个范围之内。
2、环境:蚂蚁所在的环境是一个虚拟的世界,其中有障碍物,有别的蚂蚁,还有信息素,信息素有两种,一种是找到食物的蚂蚁洒下的食物信息素,一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。
3、觅食规则:在每只蚂蚁能感知的范围内寻找是否有食物,如果有就直接过去。否则看是否有信息素,并且比较在能感知的范围内哪一点的信息素最多,这样,它就朝信息素多的地方走,并且每只蚂蚁多会以小概率犯错误,从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样,只不过它对窝的信息素做出反应,而对食物信息素没反应。
4、移动规则:每只蚂蚁都朝向信息素最多的方向移,并且,当周围没有信息素指引的时候,蚂蚁会按照自己原来运动的方向惯性的运动下去,并且,在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈,它会记住最近刚走过了哪些点,如果发现要走的下一点已经在最近走过了,它就会尽量避开。
5、避障规则:如果蚂蚁要移动的方向有障碍物挡住,它会随机的选择另一个方向,并且有信息素指引的话,它会按照觅食的规则行为。
6、播撒信息素规则:每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多,并随着它走远的距离,播撒的信息素越来越少。
图1
图2
假设蚂蚁每经过一处所留下的信息单位为1,则经过36个时间单位后,所有
开始一起出发的蚂蚁都经过不同路径从D点得到了食物,此时ABD的路线往返了2趟,每一处的信息素为4个单位,而从ACD的路线往返了一趟,每一处的信息素