论文摘要
全局优化问题,特别是组合优化问题,是科学研究与工程计算中最基本的问题之一,这类问题的求解一直是算法研究领域的热点问题。全局优化方法一般分为确定型和随机型方法,确定型方法在数学理论上较为完善,但难以应用,而传统的随机型方法对于复杂的全局优化问题又难以解决,这时启发式算法的引入使得随机型方法和整个全局优化方法得到了新的发展,尤其是元启发式算法。蚁群优化算法（Ant Colony Optimization,简称ACO）作为一种新的元启发式算法,具有分布式计算、自组织、正反馈以及贪心启发等特点,使其能够成功解决许多NP-hard组合优化问题。ACO算法作为一种全局搜索算法,其全局优化性能的优劣在很大程度上与参数的正确选择有关。但由于ACO算法参数之间的关联性,使得最优参数组合成为一个极其复杂的优化问题,目前还没有形成完善的理论依据,一般都是根据经验来确定参数值。而禁忌搜索算法（Tabu Search,简称TS）以其灵活的禁忌表和相应的禁忌准则来避免重复迂回搜索,具有强大的全局优化性能。所以为弥补ACO算法易出现停滞现象和陷入局部最优这一缺陷,本文将ACO算法与TS算法组合起来,提出了基于禁忌搜索的蚁群优化算法（Tabu Search Based Ant Colony Optimization,简称TSBACO）,并将该算法用于求解最大独立集问题。实验表明:禁忌搜索策略的引入,不仅提高了TSBACO算法的全局优化性能而且还提高了搜索效率。为了增强超大规模集成电路（VLSI）系统运行时的可靠性与稳定性,需要在电路设计中引入容错技术增强系统的容错能力。在VLSI阵列的容错技术中,一般有冗余法和降阶法两种重构方法,这两种方法都属于NP-hard问题。本文是通过冗余法来解决这一问题的,根据阵列中缺陷单元的分布情况,构造相应的矛盾图模型,将阵列的重构问题转化为求解矛盾图的独立集问题。通过TSBACO算法对矛盾图的独立集进行求解且使得所求独立集大小恰为缺陷单元个数,找出合理的补偿通道来完成阵列的重构问题。实验分析表明该重构方法是简单有效的。为进一步验证TSBACO算法在求解组合优化问题方面的实用性和有效性,本文将其应用于网络流量测量中的有效测量点选择问题。通过对图论中最小顶点覆盖模型的研究,网络流量测量点选择问题可以抽象为最小弱顶点覆盖问题,而求解该问题是一个NP-hard问题,于是本文又提出了一种求解最小弱顶点覆盖问题的TSBACO算法。比较现有的求解算法,实验结果表明:本文提出的TSBACO算法能够发现更小的弱顶点覆盖集,且具有更好的可扩展性,是网络流量测量中的一种有效测量点选择算法。