高级自然计算理论与应用

第1章 绪论 自然界中的智能行为是普遍存在、纷繁多样、相互协同的自治主体的微观行为在宏观领域的一种表现。通常，每个主体的功能单一，形式确定，机理相对简单。然而，这些主体能够建立相互间的动态连接，取得功能上的相互依赖和相互支持，使得整个群体的功能多样，形式模糊，机理复杂。受这些现象的启发，构造一个具有一定智能机制的信息处理系统时，除了研究如何提升核心构件的性能外，还应考虑系统中各组成部分之间的相互作用关系，以及系统与外界联系方式的多样性和协同性。与此相对应，设计一个具有学习与自适应能力的计算模型时，也应注重算子和自治体设计方面的多样性，功能之间的互补性和工作过程之间的协同性等问题。 自然计算是以自然界中客观存在的一些实体，或自然现象反映出的内在作用机理、功能和特点为基础，研究其蕴涵的信息处理机制，进而抽象出相应的计算模型。这种计算模型通常是一类具有自适应、自组织、自学习能力的模型，能够处理传统计算方法难以解决的一些复杂问题。目前已有的自然计算模型，如进化计算等，其研究工作大多注重结果分析，而忽略了模型实现的中间过程，这使得人们对智能行为的本质剖析还不够完善。此外，硬件性能越来越高的计算机虽然为人们完成各类信息处理任务提供了强有力的工具，但待处理任务的空间维度和复杂程度越来越高，求解这些任务依然面临诸多困难。若计算模型的全局搜索能力不强、性能不完备，即使借助再强大的计算机也无法从根本上解决问题。这促使人们在不断提升计算工具性能的同时，积极地探索和设计性能更为优异的计算模型。因此，如何有效地利用有限的计算资源解决复杂问题，成为当前研究人员关注的热点。 优化问题广泛存在于科学与工程等多个领域，*早可追溯到古希腊时期的极值求解问题，如等周问题等。优化问题是指在一系列解决方案或参数值中寻找*佳方案或参数值，往往来源于现实世界中的复杂问题，如结构设计、生产调度、经济分配和系统控制等。因此，如何高效地求解复杂优化问题成为热点。 随着科技的不断进步，现实世界中的优化问题也变得越来越复杂，传统的优化方法已难以满足需求。尤其是求解一些复杂优化问题时，传统优化方法无法在合理时间内找到*优解或近似*优解，探索一种具有通用性、高效并行性和智能特性的进化算法成为研究热点（Eiben et al.，2015）。有鉴于此，受自然界中某些现象或过程的启发，研究人员开发了多种进化算法（evolutionary algorithms， EAs）。与传统的穷举法和基于微积分的算法相比，进化算法是一种具有广泛适用性和高度鲁棒性的全局优化算法，具有自学习、自适应、自组织等特性，不受特定问题性质的限制，能处理传统算法难以解决的复杂优化问题。然而，处理复杂优化问题时，进化算法依然存在早熟收敛和停滞问题，制约其在实际优化问题中的应用。同时，根据“没有免费午餐定理”（Wolpert et al.，1997），不存在一种对任何问题都能达到较好优化效果的通用方法。 为了有效求解复杂优化问题，人们提出了一系列以进化算法为代表的自然启发式计算模型，其发展时间轴如图 1.1所示。根据启发背景的不同，自然启发式算法大致可分为两类：基于生物进化、交替过程或概念的启发式算法和基于生物社会行为的启发式算法。前者主要包括遗传算法（genetic algorithm，GA）（Holland， 1975）、差分进化（ differential evolution，DE）算法（ Storn et al.，1995）、和声搜索（ harmony search， HS）算法（ Geem et al.， 2001）、生物地理学优化（biogeography-based optimization，BBO）算法（Simon，2008）、化学反应优化（chemical reaction optimization，CRO）算法（ Lam et al.，2010）、教学优化（teaching-learning-based optimization，TLBO）算法（ Rao et al.，2012）、回溯搜索算法（backtracking search algorithm，BSA）（Civicioglu，2013）等。后者往往源自生物的各种社会行为或习性，如觅食行为和迁徙行为等，包括粒子群优化（particle swarm optimization，PSO）算法（Kennedy et al.，1995）、蚁群优化（ant colony optimization，ACO）算法（ Dorigo et al.，1996）、人工蜂群（ artificial bee colony， ABC）算法（ Karaboga et al.，2007）、布谷鸟搜索（ cuckoo search，CS）算法（ Yang et al.，2009，2010）、灰狼优化（ grey wolf optimizer，GWO）算法（ Mirjalili et al.， 2014）等。显然，这些算法的涌现进一步推动了自然启发式计算模型的发展，并为解决复杂的函数优化与工程优化问题提供了新的思路和方案。 图1.1 自然启发式计算模型的发展时间轴 1.1优化问题的数学模型 求解优化问题的过程中，首先需要描述所求问题并建立相应的数学模型。一个优化问题的数学模型通常包括三个要素：决策变量、目标函数和约束条件。 优化问题的数学模型可以表示为 （1.1） 式中，Y=f(x)为目标函数；x为决策变量； D为决策变量的维数；gi(x)≤0 (i=1，2， ， m)为m个不等式型约束条件； hj(x)=0(j=1，2， ， n)为n个等式型约束条件；min表示对目标函数求*小化；s.t.表示受约束。满足约束条件的数值所构成的集合称为可行域。目标*大化问题可转化为*小化问题，即 min f(x)与 max[-f(x)]等价。显然，数学模型（1.1）具有普遍意义。 根据决策变量的取值类型，优化问题可分为连续（函数）优化问题与离散（组合）优化问题。若决策变量的取值在一定区间内连续变化，则称为连续（函数）优化问题，否则称为离散（组合）优化问题，如旅行商问题、背包问题等。根据目标函数的数目，优化问题又可分为单目标优化问题与多目标优化问题。单目标优化问题具有唯一的评价标准，而多目标优化问题的各个目标不统一，甚至存在冲突，其解称为 Pareto*优解集或非支配解集。此外，根据决策变量的取值是否存在限制条件，优化问题还可分为约束优化问题与无约束优化问题。求解约束优化问题时，不仅要保证所获得的解为*优解或近似*优解，还要保证该解满足相应的约束限制。 1.2进化算法概述 20世纪 60年代以来，通过模拟生物进化过程的基本特征，人们设计出求解复杂优化问题的一系列有效算法，这些算法受到了广泛关注，在此基础上形成了一类新型启发式优化方法——进化计算（evolutionary computation，EC）。人们将进化计算的具体实现方法与形式称为进化算法。进化算法是以达尔文的进化论思想为基础，通过模拟生物进化过程的基本特征与机制，从而求解复杂优化问题的一种人工智能技术。生物进化是通过繁殖、变异、竞争和选择实现的，而在此基础上提出的进化算法则是通过选择、重组和变异这三种基本操作来实现优化问题的求解。进化算法主要包括遗传算法、进化策略（evolution strategies）、遗传规划（genetic programming，GP）和进化规划（ evolution programming）四种典型方法。 遗传算法产生较早，现已比较成熟。进化策略和进化规划在实际生产和科学研究中的应用也非常广泛，已应用于机器学习、神经网络训练、连续函数优化、模式识别、系统辨识和智能控制等众多领域。选择、交叉、变异是遗传算法的主要基因操作，而在进化策略和进化规划中，选择、变异是其主要的进化机制。从适应度的角度来说，遗传算法注重选择优秀的父代，认为优秀的父代产生优秀的子代，而进化策略和进化规划则注重选择优秀的子代。遗传规划和遗传算法强调父代对子代的遗传链，而进化规划和进化策略则注重子代本身的行为特性，即行为链。进化规划和进化策略适用于连续优化问题，一般不采用二进制编码，抛弃了运算过程中的“编码—解码”过程。进化策略以确定的机制产生用于繁殖的父代，而进化规划和遗传算法则依赖于个体适应度和概率。此外，进化规划把编码结构抽象为种群之间的相似，而进化策略则把编码结构抽象为个体之间的相似。 1.2.1进化算法的产生和发展 进化算法的产生和发展过程大致如下所述。 20世纪 50年代后期，生物学家开始采用计算机来模拟生物的遗传系统，现代进化算法的某些标识方式在这些工作中得以运用。 1961年，Fraser（1961）尝试使用3组5位的0/1字符串表示方程的三个参数。1965年，Fogel（1998）在计算机中采用多个个体组成的群体来进行计算，并正式提出了进化规划。但是，当时的操作算子只包含变异。1965年，Rechenberg（1973）正式提出了进化策略，*初的进化策略只有一个个体，进化操作也只限于变异。 1968年，Holland（1975）在研究自适应系统时，提出系统本身与外部环境相互协调的遗传算法，并使用模式理论对其进行分析证明，使其成为遗传算法的主要理论基础。随后， Bagley（1967）采用复制、交叉、变异等手段研究了国际象棋的对弈策略，并正式使用了“遗传算法”一词。 1975年，Holland出版了专著《自然界和人工系统的适应性》，全面介绍了遗传算法。同年，Schwefel（1977）进一步完善了进化策略，并采用了多个个体组成的群体参与进化，其基因操作算子包括重组和变异。1987年，Lawrence进一步总结了遗传算法的经验，出版了《遗传算法和模拟退火》一书，详细介绍了遗传算法。1989年，Goldberg出版了《搜索、优化和机器学习中的遗传算法》一书，全面、系统地介绍了遗传算法，进一步推动了该计算方法的发展和应用。 1992年，Koza出版了《遗传规划——应用自然选择的计算机程序设计》一书，系统地介绍了遗传规划的由来和应用，使遗传规划成为进化算法的又一个重要分支。1994年，作为遗传规划的奠基人， Koza出版了他的第二部专著《遗传规划Ⅱ：可再用程序的自动发现》。该书提出了自动定义函数的新概念，并在遗传规划中引入子程序。同年，由 Kinnear担任主编，汇集众多研究工作者关于遗传规划经验和技术的《遗传规划进展》一书顺利出版。 1.2.2进化算法的基本步骤 进化算法是一种基于生物遗传和自然选择等生物种群进化机制的优化算法。在原始问题的优化模型建立后，首先需要对问题的解进行编码。该算法在*优解的搜索过程中，先从原始问题的一组解出发搜索到另一组较好的解，再从这组较好的解出发进一步改进。在搜索过程中，进化算法利用结构化和随机性的信息，使*满足目标的个体获得*大的生存可能。从本质上，进化算法是一种概率型的寻优算法。 一般来说，进化算法包括以下步骤：给定一组初始解；计算当前这组解的适应度；从这组解中选择一定数量的解作为计算下一代解的基础；对这些解进行操作，得到下一代解；若这些解满足要求则停止，否则将一系列操作后得到的解作为当前解，重新进行迭代操作。 以遗传算法为例，其工作步骤可概括如下： （1）用二进制的0/1字符编码当前工作对象； （2）随机产生N个由0/1字符组成的初始个体； （3）计算种群中个体的适应度，并作为衡量个体优劣的标志； （4）通过复制操作，将优秀个体放入下一代种群，实现“优胜劣汰”； （5）交叉操作，产生新个体； （6）对某个字符进行变异运算，即将字符由1变为0，或由0变为1，变异字符的位置随