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

关于蚁群算法的研究是当今比较热门的课题。首先，本文在原有蚁群算法的基础上，得到一种改进的蚁群优化算法，并且应用它求解了几个经典的组合优化问题，取得了不错的效果；接着，我们首次将蚁群算法的思想应用到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问题-简单图的最大独立集问题，进一步的，为了满足蚁群算法的算法要求，我们将简单图的最大独立集问题转化为超图的一个最小边覆盖问题，最后用蚁群算法给出了该算法的求解方案。实验表明，该算法是正确可行的。

点击标签浏览更多相关技术资料资源：