蚁群算法应用(运输问题)

《蚁群算法应用(运输问题)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、蚁群算法基本原理图表示蚂蚁觅食的线路，为蚁穴,为食源，从到有两条线路可走，是长路径，是短路径.蚂蚁走过一条路线以后，在地面上会留下信息素气味，后来蚂蚁就是根据留在地面上这种气味的强度选择移动的方向.图（）表示起始情况，假定蚁穴中有只蚂蚁，分别用表示，Ｂ为食源.开始时蚁穴中蚂蚁向食源移动，由于路线和上均没有蚂蚁通过，在这两条路线上都没有信息素气味，因此蚂蚁选择这两条线路的机会均等.令蚁选择线路，蚁选择线路，假定蚂蚁移动的速度相同，当蚁到达食源时，蚁还在途中，如图（）.蚁到达食源以后就返回，这时从返回也有两条线路选择，哪一条线路上信息素的气味重就选择哪一条.因为蚁还在途

2、中，没有到达终点，这时在线路上靠近端处，蚁还没有留下信息素气味，所以蚁返回蚁穴的线路只有一个选择，就是由原路返回.当蚁返回时，蚁开始出发，蚁的线路选择必定是，因为这时上气味浓度比上重(上已有蚂蚁两次通过)，如图（）所示.当蚁到达食源时,蚁返回线路必然选择，如图（）所示.如此继续下去，沿线路上移动的蚂蚁越来越多，这就是巢穴到食源的最短路线，蚂蚁根据线路上留下信息素浓度的大小，确定在路线上移动的方向，蚁群向信息素浓度重的线路集聚的现象称为正反馈.蚂蚁算法正是基于正反馈原理的启发式算法.二、蚁群觅食中的简单规则每只蚂蚁并不是像我们想象的需要知道整个信息，他们其实只关心很小范围

3、内的局部信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来.这就是人工生命、复杂性科学解释的规律.那么，这些简单规则是什么呢？下面给出比较详细的说明.（1）范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是个方格世界，并且能移动的距离也在这个范围之内.（2）环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素.每个蚂蚁都仅仅能感知它范围内的环境信息.环境以一定的

4、速率让信息素消失.（3）觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去.否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不总是往信息素最多的点移动.蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应.（4）移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动.为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最

5、近走过了，它就会尽量避开.（5）避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为.（6）播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候散发的信息素最多，并随着它走的距离越远，播撒的信息素越来越少.在蚁群算法中，需要定义人工蚂蚁的概念，人工蚂蚁具有双重特性，首先，它们是真实蚂蚁行为特征的一种抽象，通过对真实蚂蚁行为的观察，将蚁群行为中的智能化因素赋予人工蚂蚁；另一方面，为了解决实际问题，人工蚂蚁必须具备真实蚂蚁一些所不具备的特性.归纳起来看，它有如下的主要特征.(1)人工蚁与真实蚁一样，都是一个需要合作的

6、群体问题的解决需要通过人工蚁的合作来完成，人工蚁群通过相互协调与合作从而有可能找到全局最优方案，而每只人工蚁的单独行动只可能找到局部最优解.(2)人工蚁和真实蚁一样，都要完成一个共同的任务人工蚁与真实蚁一样，都要寻找一个从源节点（巢穴）到目的节点（食物源）之间的最短路径（或最小代价），人工蚂蚁与真实蚂蚁一样都不能跳跃，必须在相邻节点之间移动，直至遍历所有可能路径，为了减少计算复杂度并寻找出最短路径，需要记录当前路径.(3)人工蚁与真实蚁一样都通过使用信息素进行间接通信真实蚂蚁在经过的路径上留下信息素，人工蚁则不断修改更新在其所经过的路径上存储的信息，是一种模拟自然界中的

7、信息素轨迹更新的过程.(4)人工蚁利用真实蚁觅食行为中的自催化机制—正反馈当一些路径上通过的蚂蚁越来越多时，路径上留下的信息素轨迹也越来越多，使得信息素强度变大，根据蚂蚁群倾向于选择信息强度大的特点，后来的蚂蚁选择该路径的概率也越高，从而增加了该路径的信息素强度，这称之为自催化过程，自催化机制利用信息素作为反馈，通过对系统演化过程中较优解的增强作用，使得问题的解向着全局最优的方向逐步接近.(5)信息素的挥发机制在蚁群算法中设置一种挥发机制，类似于真实信息素的挥发，这种机制需要蚂蚁忘记过去，不受过去经验的过分约束，有利于指引蚂蚁朝着新的方向