2.1蚁群算法的基本原理
蚁群优化算法是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，从而逐渐的逼近最优路径，找到最优路径。
蚂蚁在觅食过程时，是以信息素作为媒介而间接进行信息交流，当蚂蚁从食物源走到蚁穴，或者从蚁穴走到食物源时，都会在经过的路径上释放信息素，从而形成了一条含有信息素的路径，蚂蚁可以感觉出路径上信息素浓度的大小，并且以较高的概率选择信息素浓度较高的路径。
人工蚂蚁的搜索主要包括三种智能行为：
（1）蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择，因此在蚁群算法中建立禁忌表进行模拟。
（2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素
的物质，当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择，这样信息素就成为蚂蚁之间进行通信的媒介。
（3）蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素数量也就越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，而通过的蚂蚁比较少的路径上的信息素会随着时间的推移而挥发，从而变得越来越少。3.3.1蚂蚁系统
蚂蚁系统是最早的蚁群算法。其搜索过程大致如下：
在初始时刻，m只蚂蚁随机放置于城市中，各条路径上的信息素初始值相等，设为：j（0）0为信息素初始值，可设0 m L m，L m是由最近邻启发式方法构
造的路径长度。其次，蚂蚁k（k 1,2丄m），按照随机比例规则选择下一步要转
移的城市，其选择概率为:
[ij (t)] [ j (t)]
[is (t)] [ is (t)]
s allowed k
0,否则
其中，ij 为边(i, j)上的信息素，ij 1d ij 为从城市i 转移到城市j 的启发式 因子，
allowed k 为蚂蚁k 下一步被允许访问的城市集合。
为了不让蚂蚁选择已经访问过的城市，采用禁忌表 tabu k 来记录蚂蚁k 当前
所走过的城市。经过t 时刻，所有蚂蚁都完成一次周游，计算每只蚂蚁所走过的 路径长度，并保存最短的路径长度，同时，更新各边上的信息素。首先是信息素 挥发，其次是蚂蚁在它们所经过的边上释放信息素，其公式如下：
ij
(1 ) ij ，其中 为信息素挥发系数，且0
1。
m
ij ij
j
k
，其中i ：是第k 只蚂蚁向它经过的边释放的信息素，定义
k 1
斗 k 1/d j ,如果边(i,j)在路径T k 上
为：ik ij
( 3.2)
j
0,否则
根据(3.2)可知，蚂蚁构建的路径长度d j 越小，则路径上各条边就会获得 更多的信息素，则在以后的迭代中就更有可能被其他的蚂蚁选择。
蚂蚁完成一次循环后，清空禁忌表，重新回到初始城市，准备下一次周游。 大量的仿真实验发现，蚂蚁系统在解决小规模 TSP 问题时性能尚可，能较 快的发现最优解，但随着测试问题规模的扩大，AS 算法的性能下降的比较严重， 容易出现停滞现象。因此，出现了大量的针对其缺点的改进算法。 3.3.2精英蚂蚁系统
精英蚂蚁系统［11］是对基本AS 算法的第一次改进，它首先由 Dorigo 等人中 提出，它的设计思想是对算法每次循环之后给予最优路径额外的信息素量。 找出
这个解的蚂蚁称为精英蚂蚁。
将这条最优路径记为T bs ( best-so-far tour )。针对路径T bs 的额外强化是通过 向T bs 中的每一条边增加e/L bs 大小的信息素得到的，其中e 是一个参数，它定义 了给予路径T bs 的权值大小，L bs 代表了 T bs 的长度。这样相应的信息素的更新公 式如式(3.3):
m
ij
(t 1) (1 ) ij (t)
i ：
(t) e j s (t)
k 1
其中，ik (t)的定义方法跟以前的相同，
b
s
(t)的定义则如式(3.4)：
allowed k
p k (t) (3.3)
bs/+、
1L
bs , if(i,j) T bs
ij (t)
L
0,
otherwise
Dorigo 等人的文章列举的计算结果表明，使用精英策略并选取一个适当的 e 值将 使得AS 算法不但可以得到更好的解，而且能够在更少的迭代次数下得到一些更 好的解。
3.3.3最大-最小蚂蚁系统
最大-最小蚂蚁系统（MM AS ［13-15］）是到目前为止解决TSP 问题最好的ACO 算法方案之一。MM AS 算法是在AS 算法的基础之上，主要作了如下的改进：（1） 为避免算法过早收敛于局部最优解，将各条路径可能的外激素浓度限制于 路径上的信息量远大于其余路径， 避免所有蚂蚁都集中到同一条路径上；（2）强 调对最优解的利用。每次迭代结束后，只有最优解所属路径上的信息被更新， 从 而更好地利用了历史信息；（3）信息素的初始值被设定为其取值范围的上界。在
算法的初始时刻， 取较小的值时，算法有更好的发现较好解的能力。 所有蚂蚁
完成一次迭代后，按（3.5）式对路径上的信息作全局更新：
ij
t 1 1 j t
b
est
t , 0,1 （ 3.5）
best 龟f ,如果边i,j 包含在最优路径中 （36
）
ij
L
（ 3.6） 0, 否则
允许更新的路径可以是全局最优解， 或本次迭代的最优解。实践证明逐渐增 加全局最优解的使用频率，会使该算法获得较好的性能。 3.3.4基于排序的蚁群算法
基于排序的蚂蚁系统（AS rank ）［16］是对AS 算法的一种改进。其改进思想是： 在每次迭代完成后，蚂蚁所经路径将按从小到大的顺序排列，即 L 1（t ） L 2（t ） L m
（t ）。算法根据路径长度赋予不同的权重，路径长度越短权重
越大。全局最优解的权重为 w ，第r 个最优解的权重为max 0, w r ，则AS rank 的信息素更新规则为：
w 1
ij
（t 1） （1 ） ij （t ） 「w
r ij r t w j b t ,
0,1 （ 37
）
其中，j t
1/L r t ， j b t 1/L gb
3.3.5蚁群系统
(3.4)
max
，超出这个范围的值被强制设为 min 或者是 可以有效地避免某条
蚁群系统（ACS [12]）是由Dorigo 等人提出来的改进的蚁群算法，它与 AS 的不同之处主要体现在三个方面：（1）采用不同的路径选择规则，能更好地利用 蚂蚁所积累的搜索经验。（2）信息素挥发和信息素释放动作只在至今最优路径的 边上执行，即每次迭代之后只有至今最优蚂蚁被允许释放信息素；
（3）除了全局
信息素更新规则外，还采用了局部信息素更新规则。
0 else
其中，q 是均匀分布在区间01中的一个随机变量，q 0 0 q 0 1是一个参数，J 是根据（3.9）给出的概率分布产生出来的一个随机变量（其中
1）0
ACS 的全局信息素更新规则为：
j
1 j
ib
s
， i,j T bs （3.10）
「1.c bs
（3.11）
ACS 的局部信息素更新规则方式定义：
在路径构建过程中，蚂蚁每经过一条边 i,j ，都将立刻调用这条规则更新 该边上的信息素：
j
1 j 0 （3.12）
其中， 和0是两个参数， 满足0 1， 0是信息素量的初始值。局部更新
的作用在于，蚂蚁每一次经过边 i,j ，该边的信息素j 将会减少，从而使得其 他蚂蚁选
中该边的概率相对减少。
在ACS 中，位于城市i 的蚂蚁k ， 根据伪随机比例规则选择城市
j 作为下一
个访问的城市。路径选择规则由下面式子给出：
arg max il il
,如果q q °
j
l allowed k
(3.8)
J ，
否则
j
t
ij
t
if j allowed k
p k t
is
t is t (3.9) s allowed k
一、 一个星期七天 Sunday
Monday Saturday 二、
一年十二个月 January February June July December
三、 一年四季 1. spri ng 2. summer 3. autu mn 四、 容易拼写错的数字 1. eighth 第八 2. ninth 第九 3. forty twen tieth 第二十
四、 亲属称呼
1. daughter (女儿)
2. niece (女性晚辈) Tuesday Wed nesday Thursday Friday
March April May
August September October
4. wi nter
四十4. twelfth 第十二
辈兄弟姐妹)5. aunt ( 女性长辈)
6. uncle ( 五、 以下动词加-ed 或-ing 要双写最后一个字母 1. regret (regretted, regrett ing) (con trolled, con trolli ng) 控希 9 3. admit (admitted, admitti ng) occurri ng) 出现
5. prefer (preferred, preferri ng) referri ng) 提至 U
7. forget (forgetti ng ) 忘t 记 (permitted, permitt ing) 允许 9. equip (equipped, equipp ing) 注意：quarrel, signal, travel 英语) 3. nephew （男性晚辈）
4. 男性长辈）
后悔 承认 宁愿 装备
中的I 可双写 六、 部分过去式和过去分词不规则变化的动词 1. broadcast (broadcast, broadcast)广播 跑
3. forbid (forbade, forbidde n)禁止 forgive n) 原谅 5. freeze (froze, froze n) 6. hang (作“绞死”讲， 7. lie - lied - lied laid 放置 8. seek (sought, sought) shaken)发抖 10. sing (sa ng, sung) sunk/sunken)下沉 2. control November
5.
cousin (同 4. occur (occurred, 6. refer (referred, 8. permit
（英国英语）也可不双写（美国 结冰 是规则的；作“悬挂”讲， 说谎; lie — lay---lain 寻求 唱歌 12. spread (spread, spread) 传播 游泳
14. tear (tore, torn)
撕碎
2. flee (fled, fled)逃 4. forgive (forgave, 其过去式过去分词都是hung ） 躺下 lay-laid- 9. shake (shook, 11. sin k (sa
nk,
13. swim (swam, swum)
16.wear( wore;
worn）穿/戴
17. hold （held, held ）18.make （made,
made）
19. keep （kept, kept）
七、意思相近的词
1. check （核对）/ examine（检查” test （测试）
2. receive （收到）/ accept （接受）
3. destroy （毁坏；毁灭）/ damag（破坏）
4. celebrate（庆祝”con gratulate （祝贺）
5. wear sth / dress sb 穿衣
八、注意形容词变名词时的拼写变化
1. long —length 长度
2. wide —width 宽度
3. high —height 高度
4. strong —strength 力量
九、以-ic结尾的动词，应先把-ic变为-ick，再加ing或ed
1. pic nic （pic ni cked, pic nicking）野餐
十、个别名词的复数拼写
1. German (Germans)德国人
2. gulf (gulfs) 海湾
3. handkerchief (handkerchiefs) 手帕roof (roofs) 房顶
4. hero (英雄)，potato ( 土豆)，tomato (西红柿)等有生命的以-o结尾的名词变复数时要加-es。
十、注意动词变名词时的拼写变化
1. succeed —success 成功
2.
pronounce -— pronun ciati on 发音
3. expla in —expla nati on 解释
4. decide —decisi on 决定
5. en ter — entrance 进入
6. permit —permissi on 允许
7. con sider —con siderati on 考虑8. expect —expectati on 期待
9. discover —discovery 发现10. bury —burial 埋葬
11. con clude —con clusi on 得出结论12. arrive ——arrival 至U达
13. weigh --weight 重量14. describe —descripti on 描述
15. lose —loss 损失16. anxious---anxiety 焦虑
十二、注意形容词变副词时的拼写变化
1. beautiful 美丽的一beautifully
2. possible 可能的一possibly
3. practical 实际的一practically
4. particular 特别的—particularly
5. successful 成功的一successfully
十三、其它必背单词
1. abroad 国夕卜
2. abse nee n. 缺席（abse nt adj.）
3.
accept 接受）
4. accide nt 事故（accide ntal adj.
偶然
的，accide ntally adv. 偶然地)
5. achievement 成就（achieve v. 获得)
6. address 地址
7. admire钦佩
蚁群算法简述及实现 1 蚁群算法的原理分析 蚁群算法是受自然界中真实蚁群算法的集体觅食行为的启发而发展起来的一种基于群体的模拟进化算法,属于随机搜索算法,所以它更恰当的名字应该叫“人工蚁群算法”,我们一般简称为蚁群算法。M.Dorigo等人充分的利用了蚁群搜索食物的过程与著名的TSP问题的相似性,通过人工模拟蚁群搜索食物的行为来求解TSP问题。 蚂蚁这种社会性动物,虽然个体行为及其简单,但是由这些简单个体所组成的群体却表现出及其复杂的行为特征。这是因为蚂蚁在寻找食物时,能在其经过的路径上释放一种叫做信息素的物质,使得一定范围内的其他蚂蚁能够感觉到这种物质,且倾向于朝着该物质强度高的方向移动。蚁群的集体行为表现为一种正反馈现象,蚁群这种选择路径的行为过程称之为自催化行为。由于其原理是一种正反馈机制,因此也可以把蚁群的行为理解成所谓的增强型学习系统(Reinforcement Learning System)。 引用M.Dorigo所举的例子来说明蚁群发现最短路径的原理和机制,见图1所示。假设D 和H之间、B和H之间以及B和D之间(通过C)的距离为1,C位于D和B的中央(见图1(a))。现在我们考虑在等间隔等离散世界时间点(t=0,1,2……)的蚁群系统情况。假设每单位时间有30只蚂蚁从A到B,另三十只蚂蚁从E到D,其行走速度都为1(一个单位时间所走距离为1),在行走时,一只蚂蚁可在时刻t留下浓度为1的信息素。为简单起见,设信息素在时间区间(t+1，t+2)的中点(t+1.5)时刻瞬时完全挥发。在t=0时刻无任何信息素,但分别有30只蚂蚁在B、30只蚂蚁在D等待出发。它们选择走哪一条路径是完全随机的,因此在两个节点上蚁群可各自一分为二,走两个方向。但在t=1时刻,从A到B的30只蚂蚁在通向H的路径上(见图1(b))发现一条浓度为15的信息素,这是由15只从B走向H的先行蚂蚁留下来的;而在通向C的路径上它们可以发现一条浓度为30的信息素路径,这是由15只走向BC的路径的蚂蚁所留下的气息与15只从D经C到达B留下的气息之和(图1(c))。这时,选择路径的概率就有了偏差,向C走的蚂蚁数将是向H走的蚂蚁数的2倍。对于从E到D来的蚂蚁也是如此。 （a）（b）（c） 图1 蚁群路径搜索实例 这个过程一直会持续到所有的蚂蚁最终都选择了最短的路径为止。 这样,我们就可以理解蚁群算法的基本思想:如果在给定点,一只蚂蚁要在不同的路径中选择,那么,那些被先行蚂蚁大量选择的路径(也就是信息素留存较浓的路径)被选中的概率就更大,较多的信息素意味着较短的路径,也就意味着较好的问题回答。
蚁群算法浅析 摘要：介绍了什么是蚁群算法，蚁群算法的种类，对四种不同的蚁群算法进行了分析对比。详细阐述了蚁群算法的基本原理，将其应用于旅行商问题，有效地解决了问题。通过对旅行商问题C++模拟仿真程序的详细分析，更加深刻地理解与掌握了蚁群算法。 关键词：蚁群算法；旅行商问题；信息素；轮盘选择 一、引言 蚁群算法（Ant Colony Optimization, ACO），是一种用来在图中寻找优化路径的算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。 蚁群算法成功解决了旅行商问题（Traveling Salesman Problem, TSP）：一个商人要到若干城市推销物品，从一个城市出发要到达其他各城市一次而且最多一次最后又回到第一个城市。寻找一条最短路径，使他从起点的城市到达所有城市一遍，最后回到起点的总路程最短。若把每个城市看成是图上的节点，那么旅行商问题就是在N个节点的完全图上寻找一条花费最少的回路。 最基本的蚁群算法见第二节。目前典型的蚁群算法有随机蚁群算法、排序蚁群算法和最大最小蚁群算法，其中后两种蚁群算法是对前一种的优化。本文将终点介绍随机蚁群算法。 二、基本蚁群算法 （一）算法思想 各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素。因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就找到了。 蚁群算法的基本思想如下图表示：
蚁群算法的改进与应用 摘要：蚁群算法是一种仿生优化算法，其本质是一个复杂的智能系统，它具有较强的鲁棒性、优良的分布式计算机制和易于与其他方法结合等优点。但是现在蚁群算法还是存在着缺点和不足,需要我们进一歩改进,如：搜索时间长、容易出现搜索停滞现象、数学基础还不完整。本文首先说明蚁群算法的基本思想,阐述了蚁群算法的原始模型及其特点，其次讨论如何利用遗传算法选取蚁群算法的参数，然后结合对边缘检测的蚁群算法具体实现过程进行研究分析，最后对本论文所做的工作进行全面总结,提出不足之处,并展望了今后要继续研究学习的工作内容。 关键词：蚁群算法;边缘检测;阈值;信息素;遗传算法; 1 前言 蚁群算法是近年来提出的一种群体智能仿生优化算法，是受到自然界中真实的蚂蚁群寻觅食物过程的启发而发现的。蚂蚁之所以能够找到蚁穴到食物之间的最短路径是因为它们的个体之间通过一种化学物质来传递信息，蚁群算法正是利用了真实蚁群的这种行为特征，解决了在离散系统中存在的一些寻优问题。该算法起源于意大利学者 Dorigo M 等人于 1991 年首先提出的一种基于种群寻优的启发式搜索算法，经观察发现，蚂蚁在寻找食物的过程中其自身能够将一种化学物质遗留在它们所经过的路径上，这种化学物质被学者们称为信息素。这种信息素能够沉积在路径表面，并且可以随着时间慢慢的挥发。在蚂蚁寻觅食物的过程中，蚂蚁会向着积累信息素多的方向移动，这样下去最终所有蚂蚁都会选择最短路径。该算法首先用于求解著名的旅行商问题（Traveling Salesman Problem，简称 TSP）并获得了较好的效果，随后该算法被用于求解组合优化、函数优化、系统辨识、机器人路径规划、数据挖掘、网络路由等问题。 尽管目前对 ACO 的研究刚刚起步，一些思想尚处于萌芽时期，但人们已隐隐约约认识到，人类诞生于大自然，解决问题的灵感似乎也应该来自大自然，因此越来越多人开始关注和研究 ACO，初步的研究结果已显示出该算法在求解复杂优化问题（特别是离散优化问题）方面的优越性。虽然 ACO 的严格理论基础尚未奠定，国内外的有关研究仍停留在实验探索阶段，但从当前的应用效果来看，这种自然生物的新型系统寻优思想无疑具有十分光明的前景。但该算法存在收敛速度慢且容易出现停滞现象的缺点，这是因为并不是所有的候选解都是最优解，而候选解却影响了蚂蚁的判断以及在蚂蚁群体中，单个蚂蚁的运动没有固定的规则，是随机的，蚂蚁与蚂蚁之间通过信息素来交换信息，但是对于较大规模的优化问题，这个信息传递和搜索过程比较繁琐，难以在较短的时间内找到一个最优的解。 由于依靠经验来选择蚁群参数存在复杂性和随机性,因此本文最后讨论如何利用遗传算法选取蚁群算法的参数。遗传算法得到的蚁群参数减少了人工选参的不确定性以及盲目性。 2 基本蚁群算法 2.1 蚁群算法基本原理 根据仿生学家的研究结果表明,单只蚂蚁不能找到从巢穴到食物源的最短路 径,而大量蚂蚁之间通过相互适应与协作组成的群体则可以,蚂蚁是没有视觉的,但是是通过蚂蚁在它经过的路径上留下一种彼此可以识别的物质,叫信息素,来相互传递信息,达到协作的。蚂蚁在搜索食物源的过程中,在所经过的路径上留下信息素,同时又可以感知并根据信息素的浓度来选择下一条路径,一条路径上的浓度越浓,蚂蚁选择该条路径的概率越大,并留下信息素使这条路径上的浓度加强,这样会有更多的蚂蚁选择次路径。相反,信息素浓度少的路
蚁群算法原理及在TSP 中的应用 1 蚁群算法（ACA ）原理 1.1 基本蚁群算法的数学模型 以求解平面上一个n 阶旅行商问题(Traveling Salesman Problem ，TSP)为例来说明蚁群算法ACA （Ant Colony Algorithm ）的基本原理。对于其他问题，可以对此模型稍作修改便可应用。TSP 问题就是给定一组城市，求一条遍历所有城市的最短回路问题。 设()i b t 表示t 时刻位于元素i 的蚂蚁数目，()ij t τ为t 时刻路径(,)i j 上的信息量，n 表示TSP 规模，m 为蚁群的总数目，则1()n i i m b t ==∑；{(),}ij i i t c c C τΓ=?是t 时刻集合C 中元素(城市)两两连接ij t 上残留信息量的集合。在初始时刻各条路径上信息量相等，并设 (0)ij const τ=，基本蚁群算法的寻优是通过有向图 (,,)g C L =Γ实现的。 蚂蚁(1,2,...,)k k m =在运动过程中，根据各条路径上的信息量决定其转移方向。这里用禁忌表(1,2,...,)k tabu k m =来记录蚂蚁k 当前所走过的城市，集合随着 k tabu 进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路 径的启发信息来计算状态转移概率。()k ij p t 表示在t 时刻蚂蚁k 由元素(城市)i 转移 到元素(城市)j 的状态转移概率。 ()*()()*()()0k ij ij k k ij ij ij s allowed t t j allowed t t p t αβ αβτητη??????????? ∈?????=????? ??? ∑若否则 (1) 式中，{}k k allowed C tabuk =-表示蚂蚁k 下一步允许选择的城市；α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间协作性越强；β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁选择路径中的重视程度，其值越大，则该状态转移概率越接近于贪心规则；()ij t η为启发函数，其表达式如下： 1 ()ij ij t d η= (2)
2.1 蚁群算法的基本原理 蚁群优化算法是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，从而逐渐的逼近最优路径，找到最优路径。 蚂蚁在觅食过程时，是以信息素作为媒介而间接进行信息交流，当蚂蚁从食物源走到蚁穴，或者从蚁穴走到食物源时，都会在经过的路径上释放信息素，从而形成了一条含有信息素的路径，蚂蚁可以感觉出路径上信息素浓度的大小，并且以较高的概率选择信息素浓度较高的路径。 (a) 蚁穴 1 2 食物源 A B (b) 人工蚂蚁的搜索主要包括三种智能行为： （1）蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选择，因此在蚁群算法中建立禁忌表进行模拟。 （2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素的物质，当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择，这样信息素就成为蚂蚁之间进行通信的媒介。 （3）蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源，但整个蚁群进行搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素数量也就越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一步增加该路径的信息素强度，而通过的蚂蚁比较少的路径上的信息素会随着时间的推移而挥发，从而变得越来越少。3.3.1蚂蚁系统 蚂蚁系统是最早的蚁群算法。其搜索过程大致如下： 在初始时刻，m 只蚂蚁随机放置于城市中， 各条路径上的信息素初始值相等，设为：0(0)ij ττ=为信息素初始值，可设0m m L τ=，m L 是由最近邻启发式方法构 造的路径长度。其次，蚂蚁(1,2,)k k m = ，按照随机比例规则选择下一步要转
摘要 许多实际工程问题可以抽象为相应的组合优化问题，TSP问题是作为所有组合优化问题的范例而存在的，它已成为并将继续成为测试组合优化新算法的标准问题。从理论上讲，使用穷举法可以求解出TSP问题的最优解；但是对现有的计算机来说，让它在如此庞大的搜索空间中寻求最优解，几乎是不可能的。所以，各种求TSP问题近似解的算法应运而生了，本文所描述的蚁群算法（AC）也在其中。 目前已出现了很多的启发式算法，而蚁群算法作为一种新型的启发式算法，已成功地应用于求解TSP问题。蚂蚁通过分泌信息素来加强较好路径上信息素的浓度，同时按照路径上的信息素浓度来选择下一步的路径：好的路径将会被越来越多的蚂蚁选择，因此更多的信息素将会覆盖较好的路径；最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。 本文介绍了基本蚁群算法概念、原理及蚁群算法的特点，再根据蚁群算法的缺点做出了优化。采用轮盘赌选择代替了基本框架中通过启发式函数和信息素选择路径，改进蚁群算法的信息素传递参数，让整个算法更快速的找到最优解。其次，采用最大最小优化系统限制最大值和最小值，让整个系统更快收敛，得到最优解。 关键字：蚁群算法，TSP问题，启发式函数，轮盘算法，最大最小优化
ABSTRACT Many practical engineering problems can be abstracted as corresponding combinatorial optimization problem, TSP problem is an example of all as a combinatorial optimization problem, it has become and will continue to be a new combinatorial optimization algorithm of standard test problems. In theory, using the exhaustion method can solve the TSP problem optimal solution; But for the existing computer, let it in such a large search space to seek the optimal solution, it is almost impossible. So, all kinds of algorithm arises at the historic moment, the approximate solution of the TSP problem described in this paper, ant colony algorithm (AC) is among them. Has appeared a lot of heuristic algorithm and ant colony algorithm as a kind of new heuristic algorithm, has been successfully used in solving TSP problems. Ant secretion by pheromones to strengthen the good path pheromone concentration, at the same time according to the path to choose the next path pheromone concentration: good paths will be more and more ants to choose, so that more information will cover good path; Eventually all the ants on a good path. This positive feedback based on the pheromone of ant principle is the key to the whole algorithm. This paper introduces the basic concept of ant colony algorithm, principle and characteristics of ant colony algorithm, according to the disadvantages of ant colony algorithm optimization. Adopting roulette selection instead of the basic framework by heuristic function and choose path pheromone, pheromone passing parameters of improved ant colony algorithm, make the whole algorithm find the optimal solution more quickly. Second, limiting the maximum and the minimum maximum minimum optimization system, make the whole system faster convergence and the optimal solution is obtained. Keywords: ant colony algorithm, the TSP problem, a heuristic function, roulette algorithm, maximum_minimum optimization
《智能计算—蚁群算法基本综述》 班级：研1102班 专业：计算数学 姓名：刘鑫 学号： 1107010036 2012年
蚁群算法基本综述 刘鑫 （西安理工大学理学院，研1102班，西安市，710054） 摘要:蚁群算法( ACA)是一种广泛应用于优化领域的仿生进化算法。ACA发展背景着手，分析比较国内外ACA研究团队与发展情况立足于基本原理,分析其数学模型,介绍了六种经典的改进模型，对其优缺点进行分析，简要总结其应用领域并对其今后的发展、应用做出展望。 关键词:蚁群；算法；优化；改进；应用 0引言 专家发现单个蚂蚁只具有一些简单的行为能力。但整个蚁群却能完成一系列复杂的任务。这种现象是通过高度组织协调完成的1991年。意大利学者M.Dorigo 首次提出一种新型仿生算法ACA。研究了蚂蚁的行为。提出其基本原理及数学模型。并将之应用于寻求旅行商问题(TSP)的解。 通过实验及相关理论证明,ACA有着有着优化的选择机制的本质。而这种适应和协作机制使之具有良好的发现能力及其它算法所没有的优点。如较强的鲁棒性、分布式计算、易与其他方法结合等；但同时也不应忽略其不足。如搜索时间较长，若每步进行信息素更新，计算仿真时所占用CPU时间过长：若当前最优路径不是全局最优路径，但其信息素浓度过高时。靠公式对信息素浓度的调整不能缓解这种现象。会陷人局部收敛无法寻找到全局最优解：转移概率过大时，虽有较快的收敛速度，但会导致早熟收敛。所以正反馈原理所引起的自催化现象意在强化性能好的解，却容易出现停滞现象。笔者综述性地介绍了ACA对一些已有的提出自己的想法，并对其应用及发展前景提出了展望。 1 蚁群算法概述 ACA源自于蚁群的觅食行为。S.Goss的“双桥”实验说明蚂蚁总会选择距食物源较短的分支蚂蚁之间通过信息素进行信息的传递,捷径上的信息素越多,吸引的蚂蚁越多。形成正反馈机制,达到一种协调化的高组织状态该行为称集体自催化目前研究的多为大规模征兵，即仅靠化学追踪的征兵。 1 .1 蚁群算法的基本原理
社会性动物的群集活动往往能产生惊人的自组织行为，如个体行为显得盲目的蚂蚁在组成蚁群后能够发现从蚁巢到食物源的最短路径。生物学家经过仔细研究发现蚂蚁之间通过一种称之为“外激素”的物质进行间接通讯、相互协作来发现最短路径。受其启发，1991年由意大利学者 M. Dorigo，V. Maniezzo 和 A. Colorni 通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。本文阐述了算法的基本原理及特性以及一些优化的蚁群算法，阐述了蚁群算法在数据挖掘中的应用,最后总结了蚁群算法在数据挖掘应用中尚待解决的问题。 关键词: 蚁群算法; 蚁群优化; 数据挖掘 正文文字大小：大中小 1 蚁群算法原理 自1991年由意大利学者 M. Dorigo，V. Maniezzo 和 A. Colorni 通过模拟蚁群觅食行为提出了一种基于种群的模拟进化算法——蚁群优化。该算法的出现引起了学者们的极大关注，蚁群算法的特点： ①其原理是一种正反馈机制或称增强型学习系统; 它通过【最优路径上蚂蚁数量的增加→信息素强度增加→后来蚂蚁选择概率增大→最优路径上蚂蚁数量更大增加】达到最终收敛于最优路径上L ②它是一种通用型随机优化方法, 它吸收了蚂蚁的行为特(内在搜索机制) , 它是使用人工蚂蚁仿真(也称蚂蚁系统) 来求解问题L但人工蚂蚁决不是对实际蚂蚁的一种简单模拟, 它融进了人类的智能L人工蚂蚁有一定的记忆; 人工蚂蚁不完全是瞎的; 人工蚂蚁生活的时空是离散的L ③它是一种分布式的优化方法, 不仅适合目前的串行计算机, 而且适合未来的并行计算机L ④它是一种全局优化的方法, 不仅可用于求解单目标优化问题, 而且可用于求解多目标优化问题L ⑤它是一种启发式算法, 计算复杂性为o (Nc*n2*m) , 其中Nc 是迭代次数, m 是蚂蚁数目, n 是目的节点数目L 蚁群发现最短路径的原理和机制[1] 下面用图 1解释蚁群发现最短路径的原理和机制。 如图 1(a)所示，在蚁巢和食物源之间有两条道路 Nest-A-B-D-Food 和Nest-A-C-D-Food，其长度分别为 4 和 6。单位时间内蚂蚁可移动一个单位长度的距离。开始时所有路径上都没有外激素。 如图 1(b)，在 t=0 时刻，20 只蚂蚁从蚁巢出发移动到 A。由于路径上没有外激素，它们以
蚁群算法在物流系统优化中的应用 ——配送中心选址问题 LOGO https://www.doczj.com/doc/5b16866383.html,
框架 蚁群算法概述 蚁群算法模型 物流系统中配送中心选择问题 蚁群算法应用与物流配送中心选址 算法举例
蚁群算法简介 ?蚁群算法(Ant Algorithm简称AA)是近年来刚刚诞生的随机优化方法，它是一种源于大自然的新的仿生类算法。由意大利学者Dorigo最早提出，蚂蚁算法主要是通过蚂蚁群体之间的信息传递而达到寻优的目的，最初又称蚁群优化方法(Ant Colony Optimization简称ACO)。由于模拟仿真中使用了人工蚂蚁的概念，因此亦称蚂蚁系统(Ant System，简称AS)。
蚁群觅食图1 ?How do I incorporate my LOGO and URL to a slide that will apply to all the other slides? –On the [View]menu, point to [Master],and then click [Slide Master]or [Notes Master].Change images to the one you like, then it will apply to all the other slides. [ Image information in product ] ?Image : www.wizdata.co.kr ?Note to customers : This image has been licensed to be used within this PowerPoint template only. You may not extract the image for any other use.
蚁群算法综述 摘要群智能算法是一种新兴的人工智能方法，已成为越来越多研究者的关注焦点。蚁群算法是群智能算法的一个重要的分支，是意大利学者M. Dorigo通过模拟蚁群觅食行为提出的[1]。本文首先介绍了群智能的概念及特点，然后介绍基本蚁群算法的原理及其优缺点。在此基础上又介绍了两种针对基本蚁群算法的改进算法，最后针对蚁群算法的应用做了简要的介绍。 关键词群智能；蚁群算法；改进算法 Abstract Swarm intelligence is a newly developing method in the field of artificial intelligence. It has become the focus of more and more researchers. Ant colony algorithm is an important branch of Swarm intelligent algorithm. It was proposed by an Italian scholar M. Dorigo through simulating the foraging behaviors of ant colony. This paper first introduced the concept and characteristic of swarm intelligence, and then introduced the principle of basic ant colony algorithm and their advantages and disadvantages. On this basis, I introduce five improved algorithms of basic ant colony algorithm and the application of ant colony algorithm. 【Key words】Swarm intelligence; Ant colony algorithm; Improved algorithm 1.引言 1.1 群智能的特点 群智能有如下特点和优点[2]： (1) 群体中相互合作的个体是分布的(Distributed)，这样更能够适应当前网络环境下的工作状态。 (2) 没有中心的控制与数据，这样的系统更具有鲁棒性(Robust)，不会由于某一个或者某几个个体的故障而影响整个问题的求解。 (3) 可以不通过个体之间直接通信，而是通过非直接通信进行合作，这样的系统具有更好的可扩充性(Scalability)。 (4) 由于系统中个体的增加而增加的系统通信开销在这里是十分小的，系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性(Simplicity)。 1.2 蚁群算法的基本思想 现实生活中单个蚂蚁的能力和智力非常简单，但它们能通过相互协调、分工、合作来完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为，尤其是蚂蚁有能力在没有任何可见提示的条件下找到从蚁穴到食物源的最短路径，并且能随环境的变化而变化地搜索新的路径，产生新的选择。这是因为蚂蚁在其走过的路上会分泌一种信息素，其他的蚂蚁能够感知这种物质的存在和强度，并以此指导自己的运动方向，使其倾向于朝着信息素强度高的方向移动。蚁群算法就是从自然界中真实蚂蚁觅食的群体行为中得到启发而提出的。在蚁群算法中为了实现对真实蚂蚁的抽象，提出了人工蚁的概念。人工蚁和真实蚂蚁有如下相同点：（1）人工蚁和蚂蚁一样，是一群相互