文档介绍：重庆大学
硕士学位论文
蚁群优化算法及其在FPGA分段与布线设计中的应用
姓名:何鲜洋
申请学位级别:硕士
专业:计算数学
指导教师:龚劬
20060501
重庆大学硕士学位论文中文摘要
摘要
关于蚁群算法的研究是当今比较热门的课题。首先,本文在原有蚁群算法的
基础上,得到一种改进的蚁群优化算法,并且应用它求解了几个经典的组合优化
问题,取得了不错的效果;接着,我们首次将蚁群算法的思想应用到 FPGA 的分
段问题求解中,取得了较匹配算法、Kruskal 算法更优的结果;最后,我们将蚁群
算法拓展到 FPGA 的布线问题求解中,实验数据显示该算法得到的结果比较满意。
在第二章,我们提出了一个改进蚁群算法。蚁群算法的改进主要在两个方面:
下一条边的选择概率以及信息素更新规则。这里我们改进了信息素的更新规则,
将模拟退火算法中用于跳出局部最优的 Metropolis 准则应用到蚁群的信息素更新
过程,使得每个循环完成后,需要改变信息素的边集合的基数在一个合适的范围
内,不会太多,也不会太少。接着,我们将该改进算法应用到 10,30,50,75 城市的
TSP 问题求解中,实验数据表明,该算法具有较强的寻优能力,与模拟退火算法
以及改进前的蚁群算法相比,性能有了提高。
在第三章,我们首次将蚁群算法的思想应用到 FPGA 的分段设计中。我们知
道 FPGA 不同于一般的集成电路块,它的连接是段间的逻辑开关来完成,如果开
关太少,则该 FPGA 芯片的布线灵活性将大大减弱,另一方面,由于开关具有较
高的电阻和电容,如果开关较多,就会引起系统的时延,这便有了 FPGA 的分段
问题。有文献给出了求 FPGA 分段问题的算法,该算法类似于求最小生成树的
Kruskal 算法,效果比已有的匹配算法好。我们给出了反例说明该算法不是精确算
法,其最优性结论及证明欠严密。接着,我们将蚁群算法与 Prim 算法相结合,得
到一个基于 Prim 算法的蚁群算法,并且将它应用于分段问题的求解。实验表明,
新算法取得了比匹配算法和 Kruskal 算法更优的结果,效果比较令人满意。
在第四章,我们将蚁群算法应用到 FPGA 的 K-布线问题中。当 K 大于 2 时,
K-布线问题是一个 NP 完全问题。我们首先将该问题转化为一个经典的 NP 问题-
简单图的最大独立集问题,进一步的,为了满足蚁群算法的算法要求,我们将简
单图的最大独立集问题转化为超图的一个最小边覆盖问题,最后用蚁群算法给出
了该算法的求解方案。实验表明,该算法是正确可行的。
关键词:群体智能;蚂蚁系统;蚁群优化算法;TSP;FPGA;FPGA分段问题;
FPGA 布线问题;最大独立集
I
重庆大学硕士学位论文英文摘要
ABSTRACT
Ant colony algorithm was a novel simulated evolutionary algorithm which was
used to binatorial optimization problems. At first, this thesis introduces a new
search method based on Metropolis rules, which is applied to a classical optimization
problem. Many simulation results are given to illustrate the power of the approach.
Next , Ant Colony System (ACS) algorithm is used in the segmentation design of FPGA
for the first time. At last, ACS algorithm is used to resolve the K-routing problem of
FPGA.
In chapter 2, we present a modified ACS. Resent development of some heuristic
algorithms were discussed. The focus was laid on the improvements of ACS algorithm
based on the analysis of the performances of both simulated annealing (SA) and AC for
the traveling salesman pr