1.1研究目的

进化算法是一种仿生学算法，其设计的灵感源自于达尔文提出的进化论，依据物竞天择，适者生存的自然选择机制模拟自然界中生物自然进化的现象。其基本的思想是：先随机生成一个由若干个个体组成的群体，其中每一个个体对应于搜索空间中的一个搜索点；然后按照适应值函数计算群体中每一个个体的适应值，再根据一定的选择机制选择优秀的个体进行交叉、变异操作进行繁殖产生后代，得到的子个体进入下一代群体。

进化算法因具有较强的通用性和全局搜索能力，对所求解的优化问题的数学性质要求较低，在系统模拟、函数优化、机器学习、自动控制等科学研究和工程计算中得到广泛的应用。

研究人员已经在进化算法的应用方面取得了较为丰富的研究结果，然而其理论研究工作还任重而道远，其中涉及到的许多问题目前仍然悬而未决。相比于对进化算法的应用研究，其理论方面的研究工作显得更加紧迫和重要。对于进化算法的有效性，我们从理论上知之甚少。为什么进化算法在处理不同的优化问题上，计算性能差距很大，是哪些因素影响了进化算法计算问题的性能。因此本文采取从进化算法的平均近似误差的方面分析进化算法的性能。

1.2研究意义

尽管进化算法因其良好的性能而在实践中获得广泛应用，但其理论工作却远远落后实验研究工作。由于进化算法源于启发式思想并且包含复杂的随机行为，使得很难对其进行理论分析，因而目前还缺乏严格的理论基础，尤其是当进化算法作为优化算法应用时性能缺乏理论保障。进化算法在计算不同的优化问题中，进化算法计算问题的性能差距很大。因此，对进化算法进行理论分析，分析其求解不同问题的收敛效率，对进化算法的设计和应用具有重要的指导作用。为了更好地与算法设计相结合，本题目考虑以平均近似误差作为评价算法收敛效率的指标，分析其与问题规模、算法迭代次数等因素的关系，对算法的理论分析结果可以为算法的设计和应用提供更好的理论依据。

1.3国内外研究现状分析

进化算法兴起于20世纪六十年代，蓬勃发展于20世纪八十年代和九十年代，最终形成人工智能领域的一个分支-进化计算。自提出以来，进化算法已经被成功应用于大量优化问题的求解并且获得了很好的效果，其中包括工程实践问题和经典组合优化问题。但在理论上，我们对进化算法的优化性能了解不多，进化算法复杂的随机行为使得严密的理论研究难以展开。在进化算法理论研究中，一个重要的贡献是由Wolpert和Macready提出的没有免费午餐定理，该定理告诉我们对于任意两个算法它们在所有可能的优化问题上的平均性能是等同的。

早期的进化算法理论主要针对在拟布尔函数上的性能展开研究，Muhlenbein首次给出(1 1)EA算法在一个简单拟布尔函数OneMax上的期望运行时间上界，之后一系列关于(1 1)EA在不同拟布尔函数上的理论分析结果被获得。后来发展到在P类问题上的性能研究，Neumann和Wegener首次对(1 1)EA算法在最小生成树问题上进行理论分析并证明了(1 1)EA能够有效的求解最小生成树问题。Scharnow、Tinnefeld和Wegener研究了(1 1)EA算法在排序问题和单源最短路径上的时间复杂度，指出了(1 1)EA算法在五个基于排序问题的适应值地形上表现出良好的性能。再后来发展到在NP-完全(难)组合优化问题上的性能研究，Oliveto等人使用概率方法从理论上研究(1 1)EA算法在顶点覆盖问题和集合覆盖问题上的近似性能，并与近似算法(VerCov)相比较。最近，Lai等人研究了（1 1）EA算法在最小标签生成树上的性能，说明了无论单目标进化算法还是多目标进化算法都能获得一定的近似保障。虽然NP-完全(难)组合优化问题在计算机科学理论领域中占有重要地位，但进化算法在NP-完全(难)组合优化问题上的理论成果还很有限。

2. 研究的基本内容与方案

2.1研究的基本内容