进化计算(Evolutionary Computation,简称EC)是人工智能、计算数学与生物学三个热门学科相结合的一种新型计算理论,主要用于研究传统计算方法难以求解的优化与设计问题。进化计算的具体方法形式称为进化算法(Evolutionary Algorithm,简称EA,又译为演化算法)。本博士论文课题主要研究属于进化计算中的两个重要分支：进化算法的理论基础与进化优化算法的改进。研究对象为满足生成与测试(generate-and-test)方法框架的进化算法或仿生算法,在本文统称为进化算法。 目前,EA已经广泛地应用于工程设计等多个领域中,但是其理论基础研究的成果较少。EA的理论基础研究包括三方面的内容:EA的数学建模、收敛性分析和时间复杂度,但这三方面的研究工作均尚不完善。其一,EC领域至今仍未有较通用的数学模型作为EA研究的基础,而且EA的性能评价缺乏有效的数学工具。其二,由于收敛性决定了EA算法是否能最终求得全局最优解,EC学术界曾提出了不少EA的收敛性分析结果。然而其结论都是基于计算迭代时间趋于无穷假设下得到的,因此目前收敛性分析结论难以用于指导实际应用。其三,收敛时间决定了EA收敛到全局最优解的计算迭代次数,是评估EA算法时间复杂度的关键指标。近年来,EA的期望计算迭代时间分析是EC领域研究的一大热点,目前已有成果主要是针对求解组合优化问题的EA。但针对许多常用EA(如进化规划和蚁群算法等)的时间复杂度研究结论却很少。另外,理论研究成果的缺乏导致多数EA改进设计的理论依据不足,不利于算法的应用和推广。 本课题主要建立了等态与等同两类关系模型,并提出了相应的进化算法收敛性和收敛时间分析理论。基于等态模型及其理论,研究分析了遗传算法和粒子群算法两类算法的收敛性,并提出了改进的新算法。基于等同模型及其理论,研究分析了进化规划算法与蚁群算法的收敛时间,并提出相应的改进算法。研究的主要创新工作如下： 1、建立了“等态关系模型”,用于分析EA的收敛性特征,即满足等态等价关系的EA具有等价的收敛性,从而从收敛性意义上实现了EA的严格分类。在等价关系基础上,建立了弱态和强态的偏序关系,从而实现了一种对比EA收敛性的数学工具,并且得出EA收敛性改进设计的基本思想：设计比原算法更为强态的EA。等态关系模型可以成为EA收敛性对比和改进研究的新型数学模型。 2、建立了“等同关系模型”,以研究EA的收敛时间特征,即满足等同等价关系的EA具有相同的收敛时间。因此,该模型从平均时间复杂度意义上实现了EA的严格分类。基于等同关系模型,本研究建立了EA的期望收敛时间分析理论,并提出了EA性能对比不等式；从而实现了一种估算和比较EA期望收敛时间的数学工具,并得出EA收敛速度改进的基本思想：设计期望收敛时间较少的EA。等同关系模型可以成为EA时间复杂度分析和改进研究的新型数学模型。 3、利用创新点1中的等态关系模型及相应结论,本研究从新的角度分析了进化算法的收敛性。为了使研究更具完整性,研究各选择一个离散例子(遗传算法)和一个连续例子(粒子群算法),对比分析了这两类算法的收敛性,并给出了相应的改进方案。研究结果设计了求解广义旅行商问题的混合染色体遗传算法(Hybrid Chromosome Genetic Algorithm for Generalized Traveling Sells man Problems,简称HCGA),比已有9种同类算法收敛性更强。研究还设计了比现有9种粒子群算法收敛性更强的榜样学习粒子群算法(Example Learning Particle Swarm Optimization,简称ELPSO)。 4、利用创新点2中的期望收敛时间分析理论,分析了4种常用进化规划算法的期望收敛时间。研究还根据理论分析结果并针对现有进化规划算法的不足,设计了一种个体差异进化规划算法(Individual Difference Evolutionary Programming,简称IDEP),并通过理论和实验证明了IDEP比现有4种进化规划算法收敛速度更快。这是研究理论结果应用于连续优化EA的一个体现。 5、利用创新点2中的期望收敛时间分析理论,提出了蚁群算法(Ant Colony Optimization,简称ACO)期望收敛时间的一般分析理论,初步解决了ACO研究中关于算法收敛速度分析的公开问题。为了得到具有指导意义的结论,研究揭示了ACO算法期望收敛时间与信息素之间的关系,提出了一种基于信息素比率的ACO期望收敛时间估算方法,并给出了5个ACO算法的案例分析。研究还以理论分析为依据,设计了自适应权重参数蚁群系统算法(Adaptive Weight Ant Colony System,简称AWACS),改进了经典ACS在求解TSP问题的性能。这是研究理论结果应用于离散优化EA的一个体现。