蚂蚁的启示作文篇1

【关键词】蚁群算法；自主复制；最短路径

1.引言

随着智能交通概念的发展和应用，在城市交通网中查找最短路径问题成为了一个研究热点。最短路径是指在一个权值图中找出两节点之间拥有最小权值的路径。许多学者都对最短路径问题进行了大量的研究，并取得了不小收获，如经典的Dijkstra算法。蚁群算法[1]是近年来提出的一种新型的模拟进化算法，本文将改进蚁群算法用于解决最短路径问题。

2.蚁群算法简介

2.1基本原理

蚁群算法是通过模拟自然界蚂蚁觅食行为来求解优化组合问题的仿生算法。意大利学者M.Dorigo于1992在博士论文中第一次提出蚁群算法概念。其原理在于：自然界的蚂蚁群在寻觅食物的过程中，会在途经道路上释放信息素，并根据道路已有信息素选择路径。经过一段时间的搜索，道路信息素浓度不断更新和消散而最终收敛于某条最短路径，此过程表现出了蚂蚁群体自组织、自动学习的能力。算法本质是一种正反馈机制[2]，蚂蚁倾向于选择信息素浓度较大的路径作为自己移动方向。因此环境是否变化，蚁群总能挑选合适路径，实现选择最短路径的目的。

2.2数学模型

设定标记[3]如下：m表示蚁群个体数量；dij表示位置i和j之间的距离；ηij（t）表示启发函数，即由位置i转移到j的启发程度；τij（t）表示t时刻边（i，j）上信息素量，τij（t）=C，C取常数；Δτij表示一组蚂蚁遍历完成后位置i到j间新产生的信息素量；Pijk表示蚂蚁k的转移概率，j是未访问的节点；tablek表示蚂蚁k下一步允许运行的节点集合。

①初始时刻t=0，各条路径信息素浓度相等，蚂蚁k在运动过正中根据各条路径信息素浓度计算转移概率

其中α是信息启发因子，β是期望启发因子，然后蚂蚁k会根据概率P选择下一步节点，其中Pijk表示该节点被蚂蚁k选中的概率。

②为了防止路径信息素过多造成残存信息屏蔽启发信息，在一组蚂蚁遍历完成后，要对残存信息素进行更新[4]，更新规则为：

其中ρ（ρ∈[0，1））表示信息素挥发系数，Δτijk（t）表示本轮循环中蚂蚁k在位置i和j之间新增的信息素量，Q表示信息素强度，Lk表示本轮循环中蚂蚁k走过路径的总长度。

③经过若干轮的循环之后，该算法会收敛，蚂蚁在信息素正反馈的指引之下最终会选出一条优化路径作为全局最优解。

3.改进蚁群算法算法

3.1蚁群算法的不足

蚁群算法是一类基于多主体智能算法，然而利用蚁群算法求解最短路径问题的过程中，会出现如下两类问题[5]：

蚁群算法在搜索过程中使用多次迭代，且每次迭代需要多只蚂蚁共同搜索，并需要对比分析多次迭代结果，降低了算法收敛速度。

算法过度依赖信息素的正反馈作用，随着信息素浓度的增强，算法容易陷入局部最优，即搜索循环达到一定程度后，由于局部产生的信息素浓度增加，造成蚂蚁个体都趋向于局部最优解，降低了算法的全局搜索能力。

针对上述问题，为了降低蚁群算法的迭代次数和增强全局最优解的搜索能力，本文提出了自主复制蚁群算法。

3.2自主复制蚁群算法

自主复制蚁群算法（AC-ACO）是改进蚁群的转移策略，在传统蚁群算法中，蚂蚁面临多条路径时是通过自身设定的转移函数挑选出某条路径作为下一跳选择，其选择过程具有一定的随机性，但是蚂蚁的随机选择会影响到其他蚂蚁个体，显然为了增强算法的全局搜索能力必须降低其影响的程度，所以AC-ACO算法设定当蚂蚁面临多条路径选择时，会根据选择路径的数量自主复制出相同数目的蚂蚁个体，每条蚂蚁选择其中一条道路作为自己的选择，同时蚂蚁分泌一种标记信息素用于标记该道路已经被经过，标记信息素的作用是禁止其他蚂蚁在随后的时间内经过该路径。具体描述[6]如图1所示：

（1）蚂蚁记录自己经过的所有节点以及下一跳节点的信息，且蚂蚁爬行匀速爬行。

（2）初始时刻，从起始节点P1处派出一直蚂蚁A1，并在P1处分泌标记信息素。

（3）某一时刻蚂蚁At到达下一跳节点PK，如果节点PK没有信息素痕迹则蚂蚁At分泌标记信息素，如果已经存在标记信息素，则杀死蚂蚁At。

（4）某一时刻处于节点Pt处的蚂蚁At面临n条路径选择时，蚂蚁At复制产生Aa，Ab，Ac，Ad…An，共计n个蚂蚁，并杀死蚂蚁At，新产生的蚂蚁选择n条路径中的某一条作为自己前进路线。

（5）重复3、4步，直至某只蚂蚁Ao到达终止节点Pm后，终止程序。此时蚂蚁Ao经过的路径即为最短路径的解。

3.3仿真结果及分析

仿真参数如下，模拟一个规模N*N的表格，表格左下角为起始点，右上角为目的点，赋予表格的每条边一到十随机不等的权值，设定蚁群算法最大迭代次数10次，蚂蚁个数20只，信息启发因子为0.5，期望启发因子为1，初始时刻道路信息素浓度为0，信息素挥发因子为0.3，使用AC-ACO算法和蚁群算法模拟寻路过程，并统计算法消耗的时间及最终路径的权值大小，仿真数据如图2所示：

从图2中可以看出在时间特性上，AC-ACO算法消耗的时间明显低于蚁群算法，且随着网格规模的不断增大，算法消耗时间基本呈现线性增长，这是因为算法自身采取的分裂策略和标记信息素策略，减少了蚁群迭代次数和重复搜索的可能，降低了指数级增长可能性，提高了算法的性能。此外在道路权值方面，采用AC-ACO算法最终解的权值也普遍低于蚁群算法，这主要是因为蚁群算法在搜索过程中存在局部最优的可能，而在全局范围内失去了最优特性，但是自主复制蚁群算法的分裂策略增强了全局搜索能力，实现了真正的最短路径。

4.结语

本文提出了一种求解最短路径的改进蚁群算法——AC-ACO，并通过仿真实验证明，使用该算法能够在在较短的时间内求的更加合理的最短路径问题的解，比传统蚁群算法具有更强的可靠性。

参考文献

[1]MarcoDorigo，LucaMariaGambardella.Antcoloniesforthetravellingsalesmanproblem[J].Biosystems，1997.

[2]林海波，颜学峰，钱锋.基于蚁群算法的TSP的改进求解算法[J].计算机与数字工程，2006（34）2.

[3]程世娟，卢伟，陈虬.基于蚁群算法的最短路径搜索方法研究[J].科学技术与工程，2007（7）21.

[4]张杰慧，何中市，王健，黄学全.基于自适应蚁群算法的组合式特征选择算法[J].系统仿真学报，2009（21）6.

[5]黄贵玲，高西全，靳松杰，谈飞洋.基于蚁群算法的最短路径问题的研究和应用[J].计算机工程与应用，2007.

蚂蚁的启示作文篇2

有人说，人是世界上最聪明的动物，但我不这样认为。人虽然聪明，但在很多时候，很多方面，人往往还要向其他动物，包括一些比较低级的动物学习、借鉴，学习、借鉴其他动物的优点、长处。人类的很多发明创造，都是来自于动物的启示。如飞机得益于鸟儿、跟踪潜艇得益于响尾蛇、人工冷光得益于萤火虫、超声定位器得益于蝙蝠、鼠标得益于老鼠等等等等。不仅如此，人类的许多思想、智慧，最初都是源于某些动物的习性启示。不信？请读下列数文以验证之。（李弗不）

蚂蚁推了幸福一把朱成玉

夏日的黄昏，在地面上总能看到那样的场景，一只又一只蚂蚁，往来穿梭，细细的触角上顶着一粒米饭，就像一个人扛着一袋大米那样，艰难却无比欢欣地奔向自己的巢穴。

我常常会为那样的场景愣神，一动不动地看它们良久，甚至替它们守护那样一个运送粮食的通道，不让任何一个过失的脚步毁灭它们删繁就简的生活。

有一天，看到一个叫付显武的诗人写了这样一首关于蚂蚁的诗，令我心生感动。

“更多的时候是一粒米饭在搬动光阴

在熟悉的黄昏

一粒米饭顶着暮色慢慢回家

蚂蚁只是安装在米饭上的轮子

蚂蚁只是推了幸福一把”

多么精确的描述，短短几行，却点中生活的要穴，为生活按摩，为生活止痛。

在蚂蚁眼里，生活就是一粒米饭，在我们眼里，又何尝不是。

那只蚂蚁何尝不是一个微型的我自己呢？每天早出晚归，为了生计奔波劳碌。在生活面前，每个穷人都扮演着“小马拉大车”的角色，前路漫漫，而且都是上坡。

即便如此，我的快乐依然无处不在。刚走进巷子，我家的狗就会跑出来迎接我，蹦着高的往我怀里窜。走到家门口，看着灯光明亮，闻着饭香弥漫，不管多累，都会抛却脑后。洗完脸，泡完脚，妻已把饭菜端上了桌，并烫好了一壶酒，陪着我慢慢地吃，唠唠家长里短。孩子迫不及待地拿出刚写的作文读给我听：我的爸爸，是天底下最辛劳的爸爸，为了我们的家，像蜜蜂一样勤勤恳恳，像蚂蚁一样忙忙碌碌……半杯酒没到，我已微醉，美美地看着妻和孩子，那是属于我的最美的风景。

其实幸福都是微小而琐碎的，温暖，闪着光芒。诗人大卫在鉴赏那首诗的时候阐述过这样的思想，他说：“你肯定见过一粒米饭在前进，因为它有一只蚂蚁作为轮子；你肯定见过山道上背着柴火艰难行进的母亲，因为她有慈爱作为轮子；你肯定见过天空在飘动，因为太阳和月亮是它两个不同规格的轮子；你肯定在生活面前流下过卑微的泪水，你肯定咬着牙前进，因为你的心是永不生锈的轮子。好好过日子吧，谁人不是一只蚂蚁？我们要做的就是把生活这粒米饭向前推进，哪怕只有一寸――那也是幸福的一寸。”

我愿意做那样一只渺小的蚂蚁，轻轻地，轻轻地，推着一个个叫做幸福的日子。

――选自《妇女》（2013年第5期，有删节）

蚂蚁的启示作文篇3

Abstract:Intheprocessofprintcircuitboard(PCB)production,thesurfacemountisanextremelyimportantstep,itsspeeddirectlyaffectstheproductionefficiency.Thisarticlemainlyaimsatthesurfacemounttechnologyquestionandcarriesontheantalgorithmoptimizationtosurfacemounttechnologyoptimization,andproposestheimprovementstrategy,causesittobesuitabletothesurfacemount.

关键词:贴片机;路径优化;蚁群算法

Keywords:surfacemount;routeoptimization;antalgorithm

中图分类号:TP273文献标识码:A文章编号:1006-4311(2010)25-0148-03

0引言

随着电子产品装配技术的不断发展进步,表面组装技术(SMT)得到了越来越广泛的应用,如今在我国投入使用的表面组装生产线的数量已经相当庞大。表面组装生产线的使用,使得电子产品装配较之手工装配发生了质的飞跃,生产效率提高,产品可靠性增强,极大地降低生产成本,为厂家带来可观的经济效益。同时,在应用过程中人们也对表面组装设备提出更多的要求,提高表面组装生产线的装配效率就是其中之一[1]。

本文对贴片机装配工艺优化进行了研究,旨在对包含多个贴片头、多种类型元件的印刷电路板(PCB)贴装工艺提出一种性能较好、复杂度较低、易于实现的优化方案,以缩短PCB的装配时间,提高SMT系统的生产效率。

1贴片机的工作过程

无论是全自动贴片机还是手动贴片机,无论是高速贴片机还是中低速贴片机,它的总体结构均有类似之处,图1是一种通用贴片机的内部结构示意图。考虑到现今应用最多的是四嘴贴片机,本文以四嘴贴片机为例进行论述。

其工作过程如下:PCB由传送带入口送入,传送带将PCB送到工作位置并夹紧。然后,贴装头根据系统的拾取贴装数据执行贴装操作。首先贴装头移动至喂料器(即元器件拾取位置),吸嘴吸取4个元器件,然后贴装头移动到第1个器件的装配位置将器件1贴装,再移动至第2个器件贴装的位置将器件2贴装,直至4个器件贴装完毕。完成这样一组元器件拾取和贴装动作的过程,称为拾取贴装循环。然后贴装头又移动元器件喂料器上拾取下一组4个要贴装的元器件,再移到PCB的贴装位置上分别完成这4个元器件的贴装。在整个PCB贴装过程中,贴装头不断地重复这样的拾取贴装循环,直到PCB上的所有待贴装元器件全部贴装完毕。其间,在处理尺寸不同的元器件时,如果贴装头上的当前吸嘴不能拾取某种尺寸的元器件时,贴装头还必须运动到换嘴站自动更新吸嘴或者是暂停操作,让操作人员手动更换吸嘴[2]。

因此,合理安排元器件贴装次序,优化贴片机贴装路径,缩短贴装时间,必然有益于提升表面组装生产线的装配速度。贴片机贴装路径优化问题描述如下:已知印制板上各个元器件的装配位置,寻求一个贴片机头遍历这些装配位置的路径,要求开销最小。该问题与典型的TSP问题相似,TSP的简单形象描述是:给定n个城市的集合{0,1,2,…,n-1}及城市之间环游的花费Cij(0in-1,0jn-1,i≠j)。TSP问题是指找到一条经过每个城市一次且回到起点的最小花费的环游。若将每个顶点看成是图上的节点,花费Cij为连接顶点Vi,Vj边上的权,则TSP问题就是在一个具有n个点的完全图上找到一条花费最小的回路。

2蚁群算法的基本原理

蚁群算法(AntColonyAlgorithm,ACA)是继模拟退火算法、遗传算法、禁忌搜索(TabuSearch)算法、人工神经网络算法等元启发式搜索算法以后的又一种应用于组合优化问题的启发式搜索算法[3]。蚂蚁属于群居昆虫,个体行为极其简单,而群体行为却相当复杂。相互协作的一群蚂蚁很容易找到从蚁巢到食物源的最短路径,而单个蚂蚁则不能。数学及计算机方面的专家和工程师把这种超越生物本身的模型转化成了一项有用的优化和控制算法――蚁群算法。

基本蚁群算法的寻优机制包括两个基本阶段:适应阶段和协作阶段。在适应阶段,各候选解根据积累的信息不断调整自身结构,路径上经过的蚂蚁越多,信息量越大,则该路径越容易被选择;时间越长,信息量会越小。在协作阶段,候选解之间通过信息交流,以期望产生性能更好的解。

3蚁群算法应用于TSP问题的数学某型

设bi(t)表示t时刻位于元素i的蚂蚁数目,τij(t)为t时刻路径(i,j)上的信息量,n表示TSP规模,m为蚁群中蚂蚁的数目,则m=b(t);Γ=τ(t)ci,cjC是t时刻集合C中元素(城市)两两连接lij上残留信息的集合。在初始时刻各条路径上信息量相等,并设τij(0)=const,基本蚁群算法的寻优是通过有向图g=(C,L,Γ)实现的[4]。

蚂蚁k(k=1,2,…,m)在运动过程中,根据各条路径上的信息量决定其转移方向。这里用禁忌表tabukkk(k=1,2,…,m)来记录蚂蚁k当前所走过的城市,集合随着babuk进行过程作动态调整。在搜索过程中,蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。p(t)表示在t时刻蚂蚁k由元素(城市)i转移到元素(城市)j的状态转移概率

p(t)=,ifj∈allowed0,else(1)

式中,allowedk=Ctabuk表示蚂蚁k下一步允许选择的城市;α为信息启发式因子,表示轨迹的相对重要性,反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用;β为期望启发式因子,表示能见度的相对重要性,反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中受重视程度;η(t)为启发函数,其表达式如下

η(t)=(2)

式中,d表示相邻两个城市之间的距离[5]。

经过n个时刻,当蚂蚁完成了一次循环之后,在进行下一次环游之前,计算每一只蚂蚁所走过的路径长度,并保存最短路径L=min(L,k=1,2,…m)。此时,信息素的更新过程被引发。信息素更新时,首先所有路径上信息素量都按照一个统一的比例减少,以模拟信息素的挥发;之后蚁群中的每只蚂蚁都按照一个和它在该次环游中所求得解的质量(如:经过路径总长度)有关的函数释放相应份量的信息素到相应路径上。

用参数1-ρ表示信息素挥发程度,蚁群每完成一次环游,各路径上的信息素含量应根据式(3)作调整:

τ(t+n)=(1-ρ)•τ(t)+Δτ(3)

Δτ=Δτ

Δτ=f(L)当第k只蚂蚁在时刻t和t+1之间经过ij时0其它(4)

其中,Δτ表示第k只蚂蚁在本次环游中留在路径ij上的信息素含量,Δτ表示本次环游中路径ij上的信息素的增量,Lk表示第k只蚂蚁在本次环游中所走过的路径的长度。

之后,蚁群进入下一轮环游。当环游次数达到设定值m时算法结束,最短路径为Lmin=minLk。

4表面贴装路径优化问题建模

对于表面贴装路径优化问题来说,贴装序列的优化与贴装路径的优化在本质上是一致的。贴装过程的核心就是取贴循环,包括取料、校正和贴放三个步骤。

4.1简化问题为了便于研究将贴片机结构做适当简化,设定贴片机拾取元器件都在同一位置完成,且每次取四个元器件,并根据实际问题增加一些约束:

①由于抛料率非常低(

②贴片头的移动速度为一常数,忽略加(减)速对循环时间的影响。

③喂料器容量足够,保证每次都能成功吸到元件。

④仅有在B点正下方一个喂料器。

⑤忽略从取料(点A)到CCD(点B)的时间。

⑥每次换吸嘴使用的时间相同,即花销相同。

记G=(C,A,d)为赋权图,C=C,C,…C为顶点集(即元件所在位置坐标),其中v0为贴片头初始位置,n为元件总数,A为边集,各顶点间的权值为dij(dij>0,dij≠∞,i,j∈V),每个贴片头的吸嘴数为4。若共产生K条路径来解决此问题,则用集合Rk表示第k条路径,nk为该集合中元件的个数,集合中的元素rki表示在第k条路径中第i个被贴装元件的序号。令r=r=0表示贴片机贴片头初始位置v0。

则贴片机贴装路径优化问题归纳为:寻找元器件贴装的次序C,C…,C,使得以下的目标函数最小。

F(C)=d(C,C)-d(C,C)+d(C,C)+d(C,C)+is(5)

式中:Ci(i=1,2,…,n)代表第i个装配的元器件的坐标;d(Ci,Ci+1)表示两装配位置之间的几何距离,其中d(Ci,Ci+1)=,C0表示贴片机拾取元器件位置的坐标,s表示换吸嘴时的花销,i表示换吸嘴的次数[6]。

4.2算法改进因为贴片机在装贴期间,处理尺寸不同的元器件时,如果贴装头上的当前吸嘴不能拾取某种尺寸的元器件时,贴装头还必须运动到换嘴站自动更新吸嘴或者是暂停操作,让操作人员手动更换吸嘴。为了减少更换吸嘴所用的花销,在每次选择要贴装的元器件时,即选择下一个路径时,优先选择使用同类吸嘴的元器件。因此修改状态转移概率公式(1)为

p(t)=,ifj∈allowed0,else(6)

与公式(1)相比增加了[uij(t)]γ,其中γ为期望启发式因子,表示换吸嘴的花销的相对重要性,反映了贴片机在装贴过程中启发信息在选择贴片顺序中的受重视程度,其值越大,则该状态转移概率越接近贪心规则:uij(t)为启发函数,其表达式如下

uij(t)=(7)

为Sij从第i个贴片位置向第j个贴片位置转移时,需要换吸嘴的时间花销。更换吸嘴的花销越大,则uij(t)越小,选择概率p(t)越小。

无论以何种方法更新信息素,都可能导致搜索停滞。若在某个贴装位置上的选择的信息素轨迹量明显高于其他的选择,停滞现象就会发生。若根据式(6)进行概率选择,贴片机将更倾向于这个解元素,使得该元素上的信息素量进一步增强,从而贴片机将重复建立同一个解,对搜索空间的探索将停止。为了避免这一状态,对信息素的最大值和最小值进行限制,使任何一个τij,都有τminτijτmax。在这里令τ=•,τ=,P为构造最优解的概率。因此经修改的轨迹信息素的更新方程如下:

τij(t+1)=ρτij(t)+Δτij(t)(8)

Δτij(t)=Δτ(t)(9)

其中,Δτ(t)表示第k次贴装路径循环在本次循环中留在路径上(i,j)上的信息量[7]。在改进的算法中,如果第k次循环中贴片机经过了(i,j),则Δτ(t)=,否则,Δτ(t)=0。公式中,Q表示信息素的强度,它在一定程度上影响算法的收敛速度;Lk表示第k次循环中所走的路径的总长度与更换吸嘴所用的花销的总和。

4.3算法的实现步骤①参数初始化。令时间t=0和循环次数Nc=0,设置最大循环次数Ncmax,将m只蚂蚁置于n个元素上,初始化有向图每条边(i,j)权数和是否需要额外开销的标志位(即元素的尺寸是否相等,是否需要更换吸嘴),以及每条边的信息量τij(t)=const,其中const表示常数,且初始时刻τij(0)=0,初始化τmax,τmin。初始化额外花销(即更换吸嘴的花销)cost,Ik第k只蚂蚁的额外开销(即更换吸嘴)的次数,初始化为0。②循环次数NcNc+1。③蚂蚁的禁忌表索引号k=1。④蚂蚁数目kk+1。⑤蚂蚁个体根据状态转移概率公式(6)计算的概率选择元素j,IkIk+(i,j)的额外开销,j∈C-tabus,并记录当前的最好解。⑥修改禁忌表指针ss+1,即选择好元素之后将蚂蚁移动到新的元素,并把该元素移动到该蚂蚁个体的禁忌表中。⑦若集合C中元素未遍历完,即k

算法的时间复杂度为O(k•m•n2)。

5结束语

蚁群算法是一种新型的模拟进化算法,其研究才刚刚开始。本文将改进的蚁群算法应用到贴装机的路径优化中去,根据贴装机的拾取贴装循环提出了适应于贴装机路径优化的数学模型,考虑贴装头往返于取料点和元器件之间的路径,从而使贴装头的总体运动路径最短,提高了算法的运行效率,加快了算法的收敛速度。[8]但是,针对多贴片头,多喂料器、单生产线多机平衡、多机多生产线平衡优化等问题,还有待下一阶段继续研究。

参考文献:

[1]曾成,徐红.贴片机贴装路径优化研究.现代制造工程,2007,(3):81-83.

[2]宣大荣,韦文兰,王德贵.表面组装技术.北京:电子工业出版社,1994.

[3]段海滨.蚁群算法原理及其应用[M].北京:科学出版社,2005.1-43.

[4]ColorniA,DorigoM,ManiezzoV,etal.Distributedoptimizationbyantcolonies[A].Proceedingsofthe1stEuropeanConferenceonArtificial,1991,134-142.

[5]LEUMC,WONGH,JIZ.Planningofcomponentplacement/insertionsequenceandfeedersetupinPCBassemblyusinggeneticalgorithm[J].JournalofElectronicPackaging,1993,115(4):424-432.

[6]ELLISSKP,VITESFJ,KOBZAJE.Optimizingtheperformanceofasurfacemountplacementmachine[J].IEEETransactionsonElectronicsPackagingManufacturing,2001,24,(3):160-170.

蚂蚁的启示作文篇4

在一个风和日丽的下午，我在花园的草坪上看见了一个蚁穴，我正想看看蚂蚁是怎样搬东西的，于是跑回家拿了几粒花生米来，放在蚁穴前，心想：过一会应该会有蚂蚁来搬吧。

正如我所料，不一会，一只小蚂蚁看见了这粒又香又大的花生米，它禁不住引诱，急忙跑了出来，东看看，西瞧瞧，于是想把这粒花生米搬走，可是它怎么搬也搬不动，我看了看，想伸出手去帮它，可是，就在这时，又出现了一只蚂蚁，我沿着它来的路线一看，原来它是从另一头蚁穴来的，显然比小蚂蚁大得多。一场大战开始了，它们为了一粒花生米互相撕咬，争夺。

我看不下去了连忙又扔了一粒花生米下去，希望它们能停止战斗，可它们无动于衷，继续撕咬着，争夺着……

我正想要不要去帮它们呢？就在这时两只蚂蚁的伙伴从两个不同的方向走来，它们个个来势凶猛，准备和对方战个你死我活。

真正的战斗才开始，一群蚂蚁冲向另一群蚂蚁，形成一片混乱，他们打起来了，为了食物，它们努力奋战。到底会是哪方赢呢？我津津有味地看着。

可最后还是蚁穴离花生米比较近的蚂蚁群获胜了，毕竟它们兄弟来的比较多，最后还把那两粒花生米抬了回去，获得了最终的胜利。

蚂蚁的启示作文篇5

关键词：蚁群算法运输问题大规模

中图分类号：TP301.6文献标识码：A文章编号：1007-9416（2016）11-0135-01

运输问题是一类应用广泛的现实问题。康特洛维奇和希契科克对于该问题进入了深入的研究，故而运输问题又称为“康-希问题”。对于运输问题，最经典的数学模型如下：设某种物资有m个产地Ai，其产量分别为ai，i=1，2，...，m。有n个销地Bj，其销量分别为bj，j=1，2，...，n。已知由产地Ai到销地Bj运输单位物资的运价为cij。现在要确定总运费最小的运输方案。本文主要考虑现实中粮食收购点向粮食存储仓运输的问题。

1推广运输问题及其数学模型

用决策变量xij表示产地Ai到销地Bj的运量，对应的数学模型可以归结为如下：

由上可见，运输问题可以归结为一个线性规划问题。当然可以用经典的单纯形法求解，但由于其本身的特性，一般利用表上作业法，从而更简单更有效的解决。

本文针对现实中粮食收购点向粮食存储仓运输的问题，由于问题本身的特殊性，即没有产销的约束，所有的粮食都可以被收购。同时，不同的粮食存储仓收购的价格不一样，与粮食收购点的路程不一样会导致运输成本不一样。设S={s1，...，sm}是所有粮食收购点的集合，D={d1，...，dn}是所有粮食存储仓的集合。S，DV，其中V是所有的节点结合。G=（S∪D，Ω）是一个路径的网络，ΩE是所有链接S，D两个集合的所有可行路径，Volij是Si到Dj的运输量，VCij是对应的可变成本。对应的数学模型为：

其中Volij表示从节点i到节点j的运输量。Bij是一个0，1变量，用来表示从节点i到节点j的边是否被选取。E表示网络中的所有节点，T表示既不是起点也不是终点的节点集合。约束条件主要是对于每一个节点而言，必须是进出平衡的。而最短路进问题随着路径的增多，起计量指数增加。为了求解这个优化问题，引入智能算法-蚁群算法来解决。

2蚁群算法

蚁群算法是一种基于蚂蚁在寻觅食物的过程中对于路径选择优化而提出的一种群智能算法，最初主要对于解决TSP问题。基本蚁群算法寻优机制包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择；时间越长，信息量越小；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。

bi（t）表示t时刻位于元素i的蚂蚁数目；τij（t）为t时刻路径（i，j）上的信息量；N表示TSP的规模；dij表示相邻两个城市之间的距离；m为蚁群中蚂蚁的总数目，则m=Σ（bi（t）|i=1，2，…，n）；pkij（t）表示在t时刻蚂蚁k由元素（城市）i转移到元素（城市）j的状态转移概率；

在初始时刻各条路径上信息量，并设τij（0）=const，蚂蚁k（k=1，2，…，m）在运动过程中，根据各条路径上的信息量决定其转移方向。这里用tabuk（k=1，2，…，m）来记录蚂蚁k当前所走过的城市，集合随着tabuk进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率。

Allowedk={C-tabuk}表示蚂蚁k下一步允许选择的城市；α为信息启发式因子；β为期望启发式因子，其值越大，则该状态转移概率越接近于贪心规则；启发函数ηij（t）=1/dij；显然，该启发函数表示蚂蚁从元素（城市）i转移到元素（城市）j的期望程度。

为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市的遍历后，要对残留信息进行更新。由此，t+n时刻在路径（i，j）上的信息量可按如下规则进行调整：

式中，ρ表示信息素挥发系数，则1-ρ表示信息素残留因子，为了防止信息的无限积累，ρ的取值范围为：[0，1）；τij（t）表示本次循环中路径（i，j）上的信息素增量，初始时刻τij（0）=0，τijk（t）表示第k只蚂蚁在本次循环留在路径（i，j）上的信息量。

3改进蚁群算法求解推广运输问题

3.1蚁群算法的改进

传统的蚁群算法都是蚂蚁随机的从出发地搜索到目的地。本文基于两边向中间搜索的策略，在产地到销地各放置相应个数的蚂蚁，同时向中间搜索。搜索过的节点放入禁忌表，如果有两个蚂蚁搜索到同一个节点，本次搜索过程完毕。这样通过两组蚂蚁独立的搜索，一方面增强了搜索的随机性，一方面加快了算法收敛的速度，可以更快更优的求解。

3.2算法流程

Step1：利用改进蚁群算法，不考虑运输量，求解最短路径。

Step2：按产地到销地最大化配送。已空的产地或则已满的销地划去。

Step3：重复1，2，直到所有的产销配送完成。

通过问题求解，我们会发现，其实传统的运输问题是推广问题的一种特殊情况，即考虑产销地的单位物资运价是固定的。推广之后，更有灵活性和实际意义，因为一般只可以知道单位物资单位路程的运价。

参考文献

[1]马宇红，姚婷婷，张芳芳.多车场多车型车辆调度问题及其遗传算法[J].数学的实践与认识.2014，（2）：107-114.

[2]谢金宝.有供需要求运输问题的数学模型及算法[J].中国铁道科学，2009，（5）.

蚂蚁的启示作文篇6

关键词：蚁群算法；蚁密系统；蚁量系统；蚁周系统；信息素

中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)05-11324-02

1前言

蚁群算法(AntColonyAlgorithm)[1]是20世纪90年代由意大利学者DorigoM等首先提出并称之为蚁群系统（AntColonySystem）。它是一种基于种群的模拟进化算法，具有很强的全局优化能力和本质上的并行性。该算法用于解决TSP问题[2]、JSP问题[3]、QAP问题[4]，已取得了较好的结果。本文以TSP问题为例，通过仿真实验分析蚁群系统的性能及参数设置，最后归纳出一种参数优化规则，对蚁群系统的广泛应用具有重要的意义。

2基本蚁群算法

TSP问题是一种典型的组合优化问题，下面我们就以平面上n个城市的TSP问题为例来说明蚁群算法模型[5,6]。

在算法开始时，m只蚂蚁按某种规则（如随机）置于n个城市上，位于城市i上的蚂蚁以p(t)为概率函数选择下一个城市。公式（1.1）给出蚂蚁k由城市i转移到j的概率。

其中，tabuk(k=1,2,…m)用来记录蚂蚁k当前所走过的城市，τij(t)表示t时刻在城市i与j路径上的信息素浓度。ηij(t)表示蚂蚁从城市i转移到城市j的期望值。启发函数α和β反映了信息素和启发函数的相对重要性。

在每只蚂蚁走完一步或完成一次搜索循环后，要按一定规则对路径上的信息素进行更新。在t+n时刻，路经上的信息素可以按公式（1.2）的规则进行调整。

其中，ρ(0≤ρ

2蚁群系统模型

2.1三种蚁群系统模型

在对不同性质的问题求解时，蚁群算法模型的定义也有所不同。根据信息素更新策略的不同，DorigoM提出了三种不同的蚁群算法模型[7]，分别称为蚁密系统（Ant-DensitySystem）、蚁量系统（Ant-QuantitySystem）和蚁周系统（Ant-CycleSystem）。

在蚁密系统模型中，一只蚂蚁在经过路径(i,j)上释放的信息素增量为Q（Q为常量），如公式（2.1）所示。

在蚁量系统模型中，一只蚂蚁在经过路径（i,j）上释放的信息素增量为Q/dij，如公式（2.2）所示。

公式（2.2）中Q是常量，dij表示城市i、j之间的距离，信息素增量与路径(i,j)的长度成反比。

在蚁周系统模型中，用Δτ(t,t+n)表示蚂蚁k所走过的路径上信息素增量，如公式（2.3）所示。

其中，(t,t+n)表示蚂蚁经过n步完成一次循环，Lk表示第k只蚂蚁在本次循环中所走的路径的总长度。信息素增量与具体的dij无关，只与Q和搜索路线有关。

2.2蚁群系统模型对比

蚁密模型、蚁量模型与蚁周模型是在基本蚁群算法模型基础上，针对不同性质的应用而提出的，三种模型的状态转移概率计算方法相同，都充分利用了路径上的信息素及路径的启发信息。但在路径搜索过程中，路径上信息素的更新方式存在一定的差异，主要表现在以下几个方面：

(1)信息素增量不同。蚁密系统模型信息素增量为固定值Q；而在蚁量系统模型中，信息素增量的值为Q/dij，与路径(i,j)的长度有关；在蚁周系统模型中，信息素增量为Q/Lk，它与具体的dij无关，只与Q和搜索路线有关。

(2)信息素更新时刻不同。蚁密模型和蚁量模型的信息素更新是在蚁群前进过程中进行的。蚂蚁每完成一步移动（从城市i到达城市j）后更新所有路径上的信息素；蚁周系统模型是在第k只蚂蚁完成一次路径搜索后，对每条路径(i,j)进行信息素的更新。

(3)信息素更新形式不同。蚁密模型和蚁量模型利用蚂蚁所走路径(i,j)上的信息进行更新，其信息素更新机制采用的是局部信息更新；蚁周系统模型的信息素增量与本次搜索的整体路径有关，因此属于全局信息更新。

3蚁群系统模型的性能分析及参数优化

3.1蚁群系统模型的性能分析

蚁密、蚁量和蚁周系统模型由于采用的信息素更新策略不同，性能存在一定的差异。信息素更新过程中，各参数的设置是影响结果的一个关键。下面通过仿真试验对三种模型在TSP问题求解中的性能表现进行分析。

蚁群算法中各参数α、β、ρ的作用是紧密耦合的，它们对算法性能起着关键作用。如果α、β、ρ的组合参数配置不当，会导致求解速度很慢且所得解质量特别差，因此，在仿真实验中α、β、ρ值的恰当选取对算法性能具有重要的影响。

本实验中的TSP数据来源于TSPLIB中的Oliver30TSP，采用1000次循环作为算法终止的条件，默认的参数设置为α＝1，β=1，ρ=0.3，Q=300，在得到备选路径概率的情况下，蚂蚁运用随机选择策略确定下一步要到达的城市。实验策略为对测试参数设置一组值，其他保持默认值，每组数据实验10次，取其平均值比较三类模型的性能。

被测试的值为：α∈{0,0.5,1,2,5}，β∈{0,1,2,5,10,20}，ρ∈{0.3,0.5,0.7,0.9}。

表1蚁密系统实验结果

表2蚁量系统实验结果

表3蚁周系统实验结果

通过对以上实验结果的统计分析，得出在本实验中α、β、ρ三个参数的最佳配置段值。蚁密系统的最佳参数配置为：α=1，β=10，ρ=0.9；蚁量系统的最佳参数配置为：α=1，β=5，ρ=0.9；蚁周系统的最佳参数配置为：α=1，β=5，ρ=0.5。

通过进一步分析，可以得到以下结论：

(1)三种模型中，参数α=1时所得解的质量和稳定性都是最好的。

(2)三种模型中，β值在1~5之间逐渐增大，3种模型所得解质量越来越高。

(3)α与β的取值不当，可能导致早熟收敛，产生局部较优路径，而不是全局最优解。因此，启发信息和信息素轨迹强度的结合是十分必要的。

(4)在蚁密系统和蚁量系统中，ρ的值越大，解的质量越好，在蚁周系统中ρ在0.5左右结果比较好。

(5)三类模型对参数表现出了不同的敏感程度，但只有对ρ的敏感度最高，这也正是由于三种模型的信息素更新机制不同所造成的。

3.2蚁群系统的参数优化

本文通过仿真实验测试了蚁密系统、蚁量系统和蚁周系统的性能。实验结果表明三种模型都能在一定程度上搜索到满足要求的解，但是参数的设置对解的质量有非常显著的影响，因此在实际应用中除了根据需要确定采用哪一种算法模型，还应优化参数的设置。

在保证能获得解前提下，为了提高计算速度，依据蚁群算法参数设置的规律，本文归纳出蚁群模型中优化参数设置的规则：“满足且最优组合”。

(1)首先根据经验设置参与实验的各参数α、β、ρ的取值范围，确定α、β、ρ的各参数段值；

(2)根据本文分析的参数设置规律，选取α、β、ρ的“满足”参数组合；

(3)通过淘汰实验法，去掉“满足”参数组合中的次优组合，确定α、β、ρ的“满足且最优”参数组合；

(4)对“满足且最优”组合进一步进行参数调整：平衡启发式因子，微调挥发因子；

(5)平衡启发式因子，调整信息启发式因子α、期望启发式因子β，确定二者比较恰当的组合参数值；

(6)挥发因子微调，根据解的趋势调整信息素挥发因子ρ的值。

通过以上步骤，可以在有限次数的实验中确定参数α、β、ρ参数设置，有效地保证实验结果的有效性。

4结束语

蚁群系统模型的建立使得蚁群算法广泛地应用在组合优化、人工智能、通讯等多个领域。本文对三类模型进行分析研究，通过仿真实验分析了蚁群系统的性能及参数影响，并提出了优化参数设置的方法原则，对于解决不同规模的TSP问题具有一定的参考价值，对用蚁群系统模型解决其他领域的问题也具有一定的指导意义。

参考文献：

[1]MDorigo,VManiezzo,AColorni.AntSystem:OptimizationbyAColonyofcooperatingAgents[J].IEEETransactionsonsystem,Man,andCybemetics,PartB,1996,26(1).

[2]李勇,段正澄,动态蚁群算法求解TSP问题[M].计算机工程与应用,2003.10,3-106.

[3]AColoni,MDorigo,VManiezzo.AntsystemforJob-shopscheduling[J].BelgianJ.ofOperationsResearchStatisticsandComputerScience,1994,34(1):39-53.

[4]VittorioManiezzo,AlertoColorin.Theantsystemappliedtothequadraticassignmentproblem.KnowledgeandDataEngineering,IEEETransactionson,11(5),september/October1999.

[5]李士勇,蚁群算法及其应用[M].哈尔滨工业大学出版社,2004.9.

[6]张静乐,王世卿,王乐.具有新型遗传特征的蚁群算法[M].微计算机信息,2006.