北京科技大学计算智能实验报告三.pdf

北京科技大学实验报告 学院：自动化学院 专业： 班级： 姓名： 学号： 实验日期：2018 年 6 月19 日 实验名称：计算智能基础实验三 实验目的：熟悉并掌握蚁群算法的原理，作用以及算法流程，使用 matlab 语言 编写蚁群算法求解TSP 旅行商问题。 实验仪器：matlab R2014a 软件 实验原理： 蚁群算法的基本原理: 1.蚂蚁在路径上释放信息素。 2.碰到还没走过的路口，就随机挑选一条路走。同时，释放与路径长度有关的信 息素。 3.信息素浓度与路径长度成反比。后来的蚂蚁再次碰到该路口时，就选择信息素 浓度较高路径。 4.最优路径上的信息素浓度越来越大。 5.最终蚁群找到最优寻食路径。 需要设定的一些参数： 蚂蚁数量： 设M 表示城市数量，m 表示蚂蚁数量。m 的数量很重要，因为m 过大时，会导 致搜索过的路径上信息素变化趋于平均，这样就不好找出好的路径了；m 过小时， 易使未被搜索到的路径信息素减小到0 ，这样可能会出现早熟，没找到全局最优 解。一般上，在时间等资源条件紧迫的情况下，蚂蚁数设定为城市数的1.5 倍较 稳妥。 信息素因子： 信息素因子反映了蚂蚁在移动过程中所积累的信息量在指导蚁群搜索中的相对 重要程度，其值过大，蚂蚁选择以前走过的路径概率大，搜索随机性减弱；值过 小，等同于贪婪算法，使搜索过早陷入局部最优。实验发现，信息素因子选择[1, 4] 区间，性能较好。 启发函数因子： 启发函数因子反映了启发式信息在指导蚁群搜索过程中的相对重要程度，其大小 反映的是蚁群寻优过程中先验性和确定性因素的作用强度。过大时，虽然收敛速 度会加快，但容易陷入局部最优；过小时，容易陷入随机搜索，找不到最优解。 实验研究发现，当启发函数因子为[3,4.5]时，综合求解性能较好。 信息素挥发因子： 信息素挥发因子表示信息素的消失水平，它的大小直接关系到蚁群算法的全局搜 索能力和收敛速度。实验发现，当属于[0.2，0.5]时,综合性能较好。 信息素常数： 这个参数为信息素强度，表示蚂蚁循环一周时释放在路径上的信息素总量，其作 用是为了充分利用有向图上的全局信息反馈量，使算法在正反馈机制作用下以合 理的演化速度搜索到全局最优解。值越大，蚂蚁在已遍历路径上的信息素积累越 快，有助于快速收敛。实验发现，当值属于[10,1000]时，综合性能较好。 最大迭代次数： 最大迭代次数值过小，可能导致算法还没收敛就已结束；过大则会导致资源浪费。 一般最大迭代次数可以取100 到500 次。一般来讲，建议先取200，然后根据执 行程序查看算法收敛的轨迹来修改取值。 基于TSP 问题的基本蚁群算法： TSP 求解中，假设蚁群算法中的每只蚂蚁是具有以下特征的简单智能体：每次周 游，每只蚂蚁在其经过的支路（i,j ）上都留下信息素。蚂蚁选择城市的概率与城 市之间的距离和当前连接支路上所包含的信息素余量有关。ƒ 为了强制蚂蚁进行 合法的周游，直到一次周游完成后，才允许蚂蚁游走已访问过的城市（这可由禁 忌表来控制）。 组合参数设计策略： 通常可以按照以下策略来进行参数组合设定： 1. 确定蚂蚁数目，蚂蚁数目与城市规模之比约为1.5； 2. 参数粗调，即调整取值范围较大的α,β 及Qα,β 及Q； 3. 参数微调，即调整取值范围较小的ρ 蚁群算法流程图： 实验内容与步骤： 实验内容：给出用蚁群算法求解一个四城市的TSP 问题的执行步骤，四个城市A 、 B、C、D 之间的距离矩阵如下： 假设蚂蚁种群的规模m=3,参数α=1，β=2. ρ=0.5 。 基本步骤：首先进行初始化，再为每只蚂蚁随机选择出发城市，为每只蚂蚁选择 下城市，记录蚂蚁走过的路径，构造路径，信息素更新，以此循环进行直至输出 全局最优结果并结束程序。 实验数据： 实验数据处理： clc; m=3; %蚂蚁个数 n=4; %城市个数 a=1; %预先设置的参数 b=2; %预先设置的参数 c=0.5; %信息素蒸发率 G=1000; %迭代次数 Q=100; N=1; T1=ones(n,n); T2=zeros(m,n); X=zeros(G,n); Y=inf.*ones(G,1); d=[+inf 3 1 2;3 +inf 5 4;1 5 +inf 2;2 4 2 +inf]