进化算法与复杂问题求解

生物进化过程是自然的、并行发生的、鲁棒的优化过程，优化的目标是对环境的自适应。生物种群通过遗传复制和优胜劣汰的自然选择过程，使新生种群达到适应环境的最优状态，显示出对自然环境的自适应能力和自身结构的优化能力。从19世纪50年代开始，研究者一直在追寻可持续的进化计算方法来解决复杂的问题。受进化论和种群遗传学的启发，进化计算使用基于种群的搜索技术，通过对当前种群进行基因重组、变异和选择操作来生成新的种群，并逐步使种群进化到最优或近似最优的状态，从而实现全局优化的目的^[4]。

1958年，Friedberg^[5]在自动程序设计研究项目中就提出了通过指令交换和指令变异使程序进化的设计思想。1962年，Bremermann^[6]首先将二进制编码、变异和重组技术应用到线性规划和凸规划问题中，并提出了估计最优变异概率和克服早熟收敛的必要性。同年，生物学家Frase^[7]在从事计算机模拟自然遗传系统的研究过程中，也提出了和现代遗传算法相似的概念和思想，但他并未认识到自然遗传系统可以转化为人工遗传算法。正如Bäck^[8]所指出，由于这些算法的设计缺陷和缺乏有效的计算平台，这些早期研究的思想和成果并未引起广泛关注，但这些基础研究使得科学家们提出了模拟人脑和生物种群的智能求解问题的思想。前者强调个体的智能，导致了人工神经网络和基于知识的经典人工智能的发展；后者则强调种群基因多样性、群体学习功能和自适应进化特点，模拟自然界生物进化智能，导致了以遗传算法（Genetic Algorithm，GA）、遗传编程（Genetic Programming，GP）、进化策略（Evolution Strategies，ES）和进化规划（Evolutionary Programming，EP）为典型代表的进化算法的形成。

进化算法是以达尔文的进化论思想为基础，通过模拟生物进化过程和进化机制求解问题的自组织、自适应人工智能技术，是一种有启发性的反复搜索方法。该方法以体现群体搜索和群体中个体之间信息交换两大策略的交叉和变异算子为主，为每个个体提供优化的机会，从而使整个群体在优胜劣汰的选择机制下保证了进化的趋势^[9]。其优越性主要表现在：①进化算法在搜索过程中不容易陷入局部最优，即使在所定义的适应度函数是不连续、非规则或有噪声的情况下，算法也能以很大的概率找到全局最优解；②进化算法由于其固有的并行性，非常适合于巨量并行机；③进化算法采用自然进化机制来表现复杂的现象，能够快速、可靠地解决非常困难的问题；④由于进化算法容易介入到已有模型中并具有可扩展性，以及易于结合其他技术等特点，目前已经在最优化、机器学习和并行处理等领域得到了越来越广泛的应用。作为进化基础的普遍原则，自然选择已经被充分地建立。自然进化过程的基本算法特征已经激发了进化计算的产生，即设计人工进化算法。简言之，所有的进化算法能用以下的算法结构概括：(www.xing528.com)

返回最优解

当前，以不确定性、非线性、时间不可逆为内涵，以复杂问题为研究对象的科学新范式得到学术界的普遍认同。由于进化算法能有效地求解NP难解问题以及非线性、多峰函数优化和多目标优化问题，从而得到了科研工作者的广泛关注，并被称为21世纪的先进计算技术。进化计算的理论研究正在深入，应用日趋广泛，进化计算正在从单一的模拟进化的算法发展成为集生命科学、优化、统计学、人工智能和计算机科学于一体的交叉学科，其研究除了从原理上彻底认识算法的内部机制，为算法的改进和应用提供理论依据，还扩展进化算法的应用领域，使部分研究成果呈现商品化的趋势。