进化算法已广泛地应用于各种优化问题,但现有进化算法很少使用历史个体及其空间分布信息而具有较大的随机性。这使得算法存在搜索效率低下,需要计算大量适应度值而不适用于费时等高昂代价的优化问题。基于代理模型的进化算法虽然使用历史个体构建代理模型来计算近似适应度值,但代理模型精度会随着问题复杂性增加而逐渐下降。为此,本文结合历史空间信息,提出了一种基于距离度量的进化算法框架。该框架通过分层策略增加了各区域内个体交互概率以加速优良个体的产生,并根据距离度量结果进行采样以替换当前种群的较差个体。该框架充分结合历史空间信息,有效地提高了进化算法的收敛速度和求解精度。本文进一步以遗传算法为例分析了结合历史信息的进化算法的先进性和可行性,通过分层策略、改进的遗传操作和多粒度空间策略提出了一种多粒度遗传算法。该算法将分层策略应用于当前种群并执行相应的遗传操作,以加速优秀个体的产生。随后,算法通过基于完全随机树的多粒度空间策略将可行域划分为多个子空间,并根据空间划分结果来增加稀疏空间和当前最优解所在子空间的搜索强度。实验结果表明,多粒度遗传算法可以提高收敛速度和求解精度,减少达到收敛条件的迭代次数,从而提高了算法对费时等优化问题的适应性。为了改进多粒度空间策略对空间精确分析带来的低效问题,本文通过聚类方式来近似地拟合整个可行域,从而提出了基于k-means的改进遗传算法。该算法采用基于聚类的空间划分策略对空间进行分析,将历史个体进行分类以得到近似的空间划分结果,并加速稀疏空间和当前最优解所在子空间的搜索概率。该算法虽然在某些情况下的收敛速度和求解精度略低于多粒度遗传算法,但减少了空间划分所需的时间。