蚁群优化算法及其在fpga分段与布线设计中的应用

《蚁群优化算法及其在fpga分段与布线设计中的应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、重庆大学硕士学位论文1绪论成一个寻求连接树的问题。有一种办法是先将多端点线网分成几个两端点线网，然后分别采用最短路径方法加以求解，这种方法的结果不太好。另一种方法是用最小生成树来求解线网的连接。最自然的方法是用斯坦纳(Steiner)树来求解布线问题。斯坦纳树是一棵连接特定要求点集合和一些其它成为斯坦纳点的连接树，其中斯坦纳点的数量是任意的。由于它具有比其它方法求得的连接树总长更小的优点，往往被用来作为在总体布线中构造连接树的方法。然而，所有的斯坦纳问题都是NP-困难的。因此，没有高效的办法找到最优结果。另一种方法是用矩形斯坦纳树(

2、RectilinearSteinerTrees,RST)来为总体布线问题建模。这种直接在布线平面上寻找矩形路径，但是RST问题也是NP一困难的。[37]这种方法的优点是人们能够且已经找到有效的、高效的启发算法，但是这种方法很难运用到多层BBL布图模式的总体布线中，原因是BBL布图中，允许有些层上有障碍，而另一些层上无障碍，很难将RST结果转化为实际的布线。2)最大独立集的求解方法最大独立集问题的可以在超图中讨论，也可以在超图的特殊形式－简单图中进行讨论，本文讨论的是在简单图中的最大独立集。简单图中的最大独立集问题[38]是NPC难题

3、，对于它的求解一般都是从一些近似算法，启发式算法入手。[39]A.Jagota用神经网络的方法给出了它的求解方案，王知人与和王玉峰用模拟退火[40][10]算法给出了其求解方案，李有梅用蚁群优化算法给出了该问题的求解方案,而杨铀从独立集中结点间不含边入手，先求得极大独立集，求得一定数目的极大独[41]立集后再在这些极大独立集里面挑出结点最多的极大独立集作为最大独立集。1.3论文的主要研究内容下面我们给出本论文的主要内容和安排。1.3.1论文的主要工作1)基于Metropolis准则的蚁群优化改进算法本文提出一种基于Metropoli

4、s准则的蚁群优化改进算法，它是将模拟退火算法中Metropolis准则应用到蚁群优化算法的信息素更新机制中。我们将此改进算法应用到TSP问题的求解中，实验结果显示本文的方法较没改进的蚂蚁系统和单纯的模拟退火算法具有明显的优势。2)将蚁群算法与Prim算法相结合求解FPGA的布线问题本文提出将蚁群算法与Prim算法相结合的思想对FPGA的分段设计问题进行求解。首先找出了用Kruskal的最小支撑树算法求解该问题得到的解是最优解的证明的不完善。在此基础上，将Prim算法与蚁群算法相结合，得到了较好的结果。3)用蚁群算法给出FPGA布线问

5、题的一个有效算法4重庆大学硕士学位论文1绪论本文用蚁群算法给出了FPGA布线问题的一个近似有效算法。FPGA的布线问题可以转化为一个求无向图中最大独立集的问题，求出最大独立集后，再转换回去，就得到一个布线方法。在这里，我们将蚁群算法应用到一个新的方向：最大独立集的求解中。通过实验结果表明，该算法可以在规定的时间内，得到比较满意的解。1.3.2论文安排第一章为绪论，主要介绍本论文的意义及课题来源，分析国内外相关研究的现状，为论文研究指明方向；第二章从蚁群优化算法的原理出发，将它与模拟退火算法中的Metropolis准则相结合，提出了一

6、种改进的蚁群优化算法；第三章对FPGA分段问题已有算法进行学习，提出一种基于Prim算法的蚁群优化算法来对该问题进行求解；第四章我们将FPGA的布线问题转化为一个最大独立集的求解问题，然后用蚁群优化算法对该问题进行求解。第五章给出论文总结以及展望。1.4本章小结本章首先在选题背景基础上就本论文的意义及课题来源进行了阐述，接着综述了与课题相关的国内外研究现状，分析了相关研究领域有待深入研究的内容。最后介绍了本论文的研究内容以及布局安排。5重庆大学硕士学位论文2基于Metropolis准则的蚁群优化算法2基于Metropolis准则的蚁

7、群优化算法蚁群优化算法提出不久，就受到许多学者的前来，但是此方法也存在着一些缺点：1.当问题规模较大时，算法效率下降得很快，需要较长的搜索时间；2.容易出现停滞现象(stagnationbehavior)，即搜索到一定程度后，所有个体所发现的解完全一致，蚁群不能进一步对解空间进行搜索，从而容易陷入局部最优。对它进行改进就是一个非常重要的问题。模拟退火算法(SimulatedAnnealingAlgorithm，简称SA)是20世纪80年代初由Kirkpatrick提出的，它是基于MenteCarlo迭代求解策略的一种随机寻优算法，[

8、42]其出发点是基于物理中固体物质的退火过程与一般组合问题之间的相似性。本文提出的基于Metropolis准则的蚁群优化算法就是将二者的一些思想相结合，得到了较好的结果。2.1蚁群优化算法2.1.1蚂蚁系统(AntSystem)前面我