基于LabVIEW平台的SMT贴片机路径优化的说研究.pdf - 第41页
湖北工业大学硕士学位论文 图４．２蚁群算法的程序结构流程图 蚁群算法根据上述公式，当循环的次数达到实现定义好的ＮＣｍａｘ时或者所有 的蚂蚁都选择了同一种路径方式时，整个程序终止。其程序的基本步骤如下： １初始化 参数初始化令ｔ＝０和循环次数ＮＣ＝０，设置最大循环次数ＮＣ眦ｘ，将ｍ只蚂蚁 随机地放到ｎ个城市，将每条边（ｉ，ｊ）上的信息素设为一个常数，且△％；０，将 出发点城市设置到禁忌表中 ２迭代过程 Ｗｈｉｌｅ ｎｏｔ结束条件ｄｏ ３７
湖北工业大学硕士学位论文
通常设置０＜ＪＤ＜１；△％表示本次循环中路径（ｉ，ｊ）上的信息素增量，△ｔ，‘表示
第Ｋ只蚂蚁在本次循环中留在路径（ｉ，ｊ）上的信息量。
根据信息素更新策略不同，Ｍ．Ｄｏｒｉｇｏ提出三种不同的基本蚁群算法模型啪１，
分别是Ａｎｔ—Ｃｙｃｌｅ模型，Ａｎｔ—Ｑｕａｎｔｉｔｙ模型及Ａｎｔ—Ｄｅｎｓｉｔｙ模型，其差别在于△％‘
的求法不同口１ｌ。
在Ａｎｔ—Ｃｙｃｌｅ模型中
ｆ
Ｑ
若第ｋ只蚂蚁在本次循环中经过（ｉ，ｊ）
△％‘一Ｊ
ｔ
（４．４）
Ｌ
Ｏ
否则
式中，Ｑ表示信息素强度，它在一定程度上影响算法的收敛速；ｋ表示第只蚂
蚁在本次循环中所走路径的总长度。
在Ａｎｔ—Ｑｕａｎｔｉｔｙ模型中
△％‘２｛，三二ｋ只蚂蚁在ｔ和ｔ＋１经过（ｉ，ｊ）
（４．５）
△巧。：ｒ
Ｑ
若第ｋ只蚂蚁在ｔ和”１经过（ｉ’ｊ）
。４ｑ
１…。’
式（４．５）和式（４．６）利用的是局部信息，即蚂蚁完成一步后更新路径上的信息
素；而式（４．４）利用的是全局信息，即蚂蚁完成一个循环后更新所有路径上的信息
４．４基本蚁群算法的实现
湖北工业大学硕士学位论文
图４．２蚁群算法的程序结构流程图
蚁群算法根据上述公式，当循环的次数达到实现定义好的ＮＣｍａｘ时或者所有
的蚂蚁都选择了同一种路径方式时，整个程序终止。其程序的基本步骤如下：
１初始化
参数初始化令ｔ＝０和循环次数ＮＣ＝０，设置最大循环次数ＮＣ眦ｘ，将ｍ只蚂蚁
随机地放到ｎ个城市，将每条边（ｉ，ｊ）上的信息素设为一个常数，且△％；０，将
出发点城市设置到禁忌表中
２迭代过程
Ｗｈｉｌｅ
ｎｏｔ结束条件ｄｏ
３７
湖北工业大学硕士学位论文
ｆｏｒ
ｉ＝ｌ
ｔｏ
ｎ一１
Ｄｏ（遍历所有城市）
ｆｏｒ ｋ＝１
ｔｏ
Ｍ
Ｄｏ（对Ｍ只蚂蚁循环）
ｆｏｒ
ｊ＝ｌ
ｔｏ
ｎ
Ｄｏ（对ｎ个城市循环）
根据公式（４．２）和（４．３），蚂蚁ｋ选择下一个城市ｊ，将蚂蚁ｋ移
动到城市ｊ，把城市ｊ置入禁忌列表纪６‰；
ｅｎｄ
ｅｎｄ
ｅｎｄ
计算所有蚂蚁求得的回路距离，根据公式（４．２），（４．３）和（４．５），
更新路径（ｉ，ｊ）上的信息激素；
Ｎｃ＝ｎｃ＋１：
Ｅｎｄ
ｗｈｉｌｅ
３输出结果，结束算法。
４．５基本蚁群算法的优缺点
基本蚁群算法具有很强的发现解的能力，这是因为该算法不仅利用了正反馈
原理ｂ羽，在一定程度上可以加快进化过程，而且是一种本质上并行的算法，不同
个体之间不断进行信息交流和传递，从而能够相互协作，有利于发现较好解。具
有如下的优点：
（１）分布式本质并行算法，它是一种基于种群的进化算法，本质上具有并行
性，易于并行实现。
（２）具有较强的鲁棒性，对其模型稍加修改，便可以应用于其他问题。
（３）易于与其他方法结合，基本蚁群算法很容易与多种启发式算法结合，以
改善算法的性能。
（４）其优化过程不依赖于优化问题本身的严格数学性质，如连续性，可导性
及目标函数和约束函数的精确数学描述。
（５）是一类概率型的全局搜索方法，这种非确定性使算法能够有更多的机会
求得全局最优解∞１。
基本蚁群算法是一种有效的随机搜索算法，但也存在一些缺陷Ⅲ１
（１）与其他方法相比，该算法一般需要较长的时间。
（２）该算法易出现停滞现象，即搜索进行到一定程度后，所有个体所发现的
解完全一致，不能对解空间进一步搜索，不利于发现更好的解。