仿生随机搜索启发式算法如演化算法和蚁群算法是一类通用的流行算法,它是通过模拟自然界现象、过程和一些生物特征提出来的。这些算法已被广泛地用于解决大量的各种实际问题并且获得了很好的效果。这些算法易于实施并且可以应用到结构不是很清楚的优化问题上。演化算法是受到物种的自然演变的启发而提出的,演化算法通过迭代应用变异、重组和选择算子对问题的解进行优化。蚁群算法来源于真正的蚂蚁具有通过交换信息素从它们的巢穴到食物源的众多路径中找到最短路径的能力。许多实证研究已经证明了这类算法在许多问题上是非常有效的,但是离彻底理解算法的运行机制还是很遥远的。本文从理论研究的角度对演化算法和蚁群算法进行了分析。本文分析了单目标演化算法和蚁群算法在组合优化问题上的近似性能,也分析了多目标演化算法在拟布尔函数上的时间复杂度。本文主要采用常用的随机分析方法和工具进行分析。本文的主要贡献如下:(1)最大独立集问题是图论中的一个经典组合优化问题,也是一类NP完全问题。基于目前的计算理论,除非P=NP,最大独立集问题将不存在多项式时间的确定性算法。许多学者设计出一些有效的近似算法来求解最大独立集问题。演化算法是一类公认的有效的随机算法,其近似性能的理论分析相对较少。本文从理论上分析了一个简单的爬山演化算法(1+1)EA求解最大独立集问题的近似性能。证明了(1+1)EA能够在多项式的期望时间内获得该问题的近似比。对于一类特殊的独立集问题——k-Set Packing问题,本文证明了(1+1)EA可以在多项式期望时间内获得该问题的近似比。最后,文中给出了一个最大独立集问题的实例,并说明在该实例上(1+1)EA能获得比3-flip局部搜索方法更优的解。在这个实例上3-flip局部搜索算法会陷入局部最优,而(1+1)EA能够在多项式期望运行时间找到该实例的全局最优解。(2)长时间以来,演化算法已经被成功的应用于解决多目标最优化问题。然而多目标演化算法(MOEAs)的理论研究主要限于简单的多目标演化算法(SEMO)。Pareto存档演化策略(PAES)是一种简单但重要的多目标演化算法,它是来源于对电信问题的研究。本文首次分析了PAES算法在拟布尔函数上的运行时间,证明了当SEMO算法采用一种简单的变异算子时,PAES算法在PATH函数的性能优于SEMO算法。然而,我们可以发现该算法在著名的LOTZ函数上却不能以压倒性的概率获得它的整个Pareto前沿。之后,本文提出一种改进的Pareto存档演化策略(IPAES)并且证明了IPAES算法可以在多项式运行时间内找到整个LOTZ函数的Pareto前沿。最后,本文分析了IPAES算法采用两种不同的局部变异算子在拟布尔函数上的性能。基于上述分析,我们可以发现对于不同的问题选择合适的局部搜索算子是非常重要的。(3)本文也研究了两种蚁群算法在一类特殊旅行商问题上的近似性能。这类旅行商问题的特点是任意的两个城市之间的距离是1或者2,我们称这种问题是TSP(1,2)问题,这是一个NP完全问题。本文证明了两种蚁群算法能在多项式的运行时间内获得TSP(1,2)问题的3/2的近似比,同时也研究了信息素和启发式信息对算法性能的影响。最后,文中构造了一个TSP(1,2)问题实例并且证明了蚁群算法在这个实例上的性能优于局部搜索算法。