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