1.3 知识导向的智能优化算法
智能优化算法是当前研究的热点问题，其主要缺点是容易出现早熟收敛和收敛速度慢。导致这些缺点的一个重要原因就是智能优化算法中缺乏明确的导向因子。国内外学者一方面通过传统人工智能手段和特定知识模型来实现对智能优化算法的进化引导，同时也采用具有双层进化机制的文化算法对智能优化算法进行引导。
1.3.1 传统人工智能引导的智能优化算法
采用传统人工智能手段对智能优化算法进行引导，如采用禁忌搜索[3]、文化算法[4]和机器学习[5]来控制进化等[6]。在具体实施时，必须首先抽取一些进化过程中尽可能一般和重要的规则，利用禁忌搜索、文化算法和机器学习等算法进行学习，然后根据学习得到的规则控制个体进化。这些工作的缺点在于很难找到尽可能一般和重要的规则，而且这些规则缺乏全局性，没有考虑到随着个体的进化，个体所处的环境也在不断变化，因而相应的规则也应该变化[6]。
为了平衡进化过程中选择操作正向作用和交叉（变异）操作破坏性影响，范磊等采用归纳学习方法来引导进化过程[7]：采用归纳学习方法从进化历史进程中抽取出能反映过去进化的错误和成功的规则，进而用它们来引导后续进化过程，保证在避免重复错误的同时加速进化。基于函数优化和布局求解的实验验证了其有效性。
曹先彬等借鉴个体进化的生命周期性，提出了一种基于生命期引导的生态进化模型[8]。基于此模型的算法在个体生命期的各个阶段设置了相应的引导算子，使个体在整个生命期都基于其生态特征而被引导进化。实验结果验证了其优越性。
为了提高粒子群算法中粒子搜索全局最优解的准确度，岑宇森等提出了基于知识空间的分组式粒子群算法[9]。该算法使用k-means算法对粒子群进行分组，利用较小的最大飞行速度加强粒子在组内的局部搜索能力，并将“知识空间”的概念引入到分组中，由知识空间中的粒子来引导群中粒子前往更好的解空间搜索。
李亚男等在遗传算法中采用专家知识辅助寻优，并将该改进遗传算法应用到无功规划优化中[10]。依据专家知识对少数被选中的个体动态形成本厂、站的就地无功／电压控制的有效变量集进行人工调整，可改善遗传算法的局部寻优能力。对某实际系统的计算表明，结合专家知识的遗传算法能够更有效地找到全局最优。
柴啸龙将领域知识通过禁忌连接集的形式加入蚁群规划算法中[11]，相邻动作层的很多互斥信息通过禁忌连接集只需计算一次，不进入主循环计算中，这样可以较好地提升算法的执行效率。实例分析表明这一策略是有效的。
1.3.2 特定知识模型引导的智能优化算法
采用特定知识模型对智能优化算法进行引导时，在智能优化算法运行之初就已确定了知识的基本形式，相关知识按照固定规则随着算法演化而不断调整，然后采用已获得知识来指导后续个体的进化。采用特定知识模型对智能优化算法进行引导也可理解为演化与学习之间的交互（interaction between evolution and learning）[12-17]。
根据现有文献，研究人员一般通过以下两种途径来实现演化和学习之间的交互[18]：学习已获得个体的一些优良特征，采用这些优良特征来改进后续产生的个体；学习已获得个体的一些不良特征，采取措施防止这些不良特征出现在后续个体中。现有研究表明：演化和学习之间的交互是可能的，可采用多种途径来实现演化和学习之间的交互，例如版本空间（version space）[19]、基于案例的记忆单元[20]、Q-学习系统（Q-learning system）[21]，[22]和AQ-学习系统（AQ-learning system）[23]等。通过演化和学习之间的交互可有效提高智能优化方法的优化效率[18]。
1.3.2.1 采用记忆单元对智能优化算法进行引导
很多学者尝试采用记忆单元（memory cell）来实现演化和学习之间的交互。Chung和Reynolds将个体优良特征看作是信念（beliefs），将这些信念保存到记忆单元中，采用这些信念来改进后续个体[24]。Branke将一些已获得的较优个体保存到记忆单元中，采用这些较优个体来改进后续个体[25]。
Gantovnik等采用记忆单元在遗传算法中实现演化和学习之间的交互[26]，[27]，并使用这种改进遗传算法来解决混合变量优化设计问题。Louis和Li采用带有记忆单元的遗传算法来求解旅行商问题[28]。Yang采用基于记忆单元的移民方式在遗传算法中实现演化和学习之间的交互[29]，[30]，并使用这种改进遗传算法求解动态优化问题。
苏淼等采用免疫记忆方式在蚁群算法中实现演化和学习之间的交互[31]，并使用这种改进蚁群算法来求解武器目标分配问题。Acan使用外部记忆单元（external memory）在蚁群算法中实现演化和学习之间的交互[32]。在此基础上，Acan在外部存储器中加入了局部置换（partial permutations）功能[33]，进一步提高了改进蚁群算法的效率。Shamsipur使用外部记忆单元在蚁群算法中实现演化和学习之间的交互[34]。
1.3.2.2 基于案例对智能优化算法进行引导
很多学者也采用案例（case）在智能优化方法中实现演化和学习之间的交互[20]，[35]，[36]。Louis和McDonnell采用案例推理（case-based reasoning）方法从案例记忆单元（case-based memory cell）中选择特征来改进后续个体[20]。Louis和Li在遗传算法中采用案例注入方式来实现演化和学习之间的交互[35]，并使用这种改进遗传算法来求解旅行商问题。Rasheed和Hirsh采用案例学习方式在遗传算法中实现演化和学习之间的交互[36]。Babbar-Sebens和Minsker提出了一种基于案例的宏观交互式遗传算法（case-based micro interactive genetic algorithm）[37]，主要通过案例记忆单元和案例推理来实现演化和学习之间的交互。
1.3.2.3 采用学习演化模型对智能优化算法进行引导
不同于基于达尔文进化论的演化计算方法，学习演化模型（learnable evolution model，LEM）主要采用机器学习方法来指导整个演化进程。Coletti对学习演化模型进行了初步研究[38]，Wojtusiak研究了学习演化模型中的约束优化问题[39]，Kaufman和Michalski采用学习演化模型来解决热交换器设计问题[40]，Jourdan等使用学习演化模型来解决多目标水系统设计问题[41]，Domanski等采用学习演化模型来求解优化设计问题[42]。目前，学习演化模型的最新版本为LEM3。Wojtusiak和Michalski应用LEM3来解决复杂函数优化问题[43]。
近年来，越来越多的学者开始使用学习演化模型在智能优化方法中实现演化和学习之间的交互[18]，[23]。Michalski等在总结学习演化模型最新进展[44]的基础上，在智能优化方法中采用学习模型来实现演化和学习之间的交互[45]。在Michalski构建的学习演化模型中，主要采用机器学习方法来实现演化和学习之间的交互[23]。Ho等采用学习型遗传框架（learnable genetic architecture，LEGA）来实现演化和学习之间的交互[18]。Wojtusiak设计了一种可用于多种智能优化方法的LEM3系统[46]。
1.3.2.4 采用神经网络对智能优化算法进行引导
针对遗传算法个体进化缺乏明确导向的缺点，顾慧等提出了一种基于知识模型的改进遗传算法[6]：利用神经网络的学习功能，从当前两代个体的信息中获取一定知识，用于控制下一代某些个体的进化。该算法既保留了遗传操作算子，同时利用神经网络构造相应的知识模型，用于引导个体进化，使得改进遗传算法既保留了遗传算法强大的全局随机搜索能力，又具有神经网络的自学习能力和强鲁棒性。
1.3.3 具有双层进化机制的文化算法
文化算法模拟人类社会的文化进化过程，由实现个体进化的种群空间和实现知识更新的信度空间构成。文化算法通过信度空间实现对进化信息的有效提取和管理，并利用进化信息指导种群空间的进化过程。文化算法可实现隐含进化信息的显性归纳和描述，在种群空间之上扩展信度空间，以独立实施知识管理，实现知识进化过程。目前文化算法已被成功用于解决农业进化、概念学习、实值函数优化和制造装配过程的重新设计等问题。已经证明，在文化加速进化作用下的进化远优于单纯依靠基因遗传的生物进化[47]。
在传统进化算法的基础上，文化算法通过构建信度空间来提取隐含在进化过程中的各类信息，并以知识形式加以存储，最终用于指导进化过程，其基本结构如图1.2所示[48]。文化算法由种群空间、信度空间和接口函数构成一种双层进化结构。上层信度空间中的知识进化是以底层种群空间中的个体进化为基础，且知识是个体经验的高度概括。该双层进化结构体现为个体微观进化和知识宏观进化两个不同粒度的进化层面[48]。
图1.2 文化算法的基本结构
- 种群空间用于实现基于种群的进化算法。一方面对个体进行评价，并面向种群实施进化操作；另一方面将优良个体作为样本提供给信度空间。
- 信度空间通过接受函数从已评价种群中选取样本个体，在知识更新函数的作用下，提取样本个体所携带的隐含信息，并以知识形式加以概括、描述和储存。各类知识通过影响函数作用于种群空间，从而实现对进化操作的引导。
- 接受函数和影响函数为上层知识模型和下层进化过程提供了作用通道，称为接口函数。
1.3.3.1 种群空间
随着智能计算研究的不断深入，遗传算法、进化规划、遗传规划、粒子群优化算法及微分进化算法等诸多智能优化方法被引入种群空间。
- 遗传算法最早被引入种群空间。Reynolds等针对概念学习问题，采用基于遗传算法的种群空间，讨论了信度空间的知识构成[49]。采用遗传算法的优点在于，知识对进化过程的引导作用可体现在不同进化算子上。
- 进化规划仅采用变异算子，知识对进化过程的影响程度易于观察和分析。Jin使用基于进化规划的文化算法解决非线性约束优化问题[50]，将信度元的概念引入到信度空间。
- 遗传规划采用遗传操作来动态改变程序所描述的问题模型，采用遗传规划作为种群空间的文化算法，在软件工程、基于代理模型的策略优化问题中得到较好应用[51]。
- 有学者采用粒子群优化算法作为种群空间，分析了在信度空间各类知识进行交流的情况下个体间的信息传播[52]，[53]。
- 微分进化本质上是一类基于概率分析的进化算法，研究人员将微分进化引入文化算法的种群空间，用于解决非线性约束优化和多目标优化等问题[54]，[55]。
- 交互式进化计算是一类由人参与个体评价的算法。研究人员将该算法引入种群空间，通过提取人的认知和偏好等知识来缩小搜索空间，加速进化收敛[56]。
1.3.3.2 信度空间
信度空间的核心在于知识如何描述和更新。种群空间采用的进化策略不同和应用领域不同，相应的知识形式也有所不同。一般而言，信度空间知识被划分为5类：状况知识、规范知识、拓扑知识、领域知识和历史知识[50]，[56-58]。这5类知识本质上都是进化过程中隐含信息的显性描述，但在某些需要人参与的实际优化问题中，反映人类经验的常识知识也对进化过程具有重要引导作用。
根据底层种群进化层提供的信息来源及其特征，也有学者将知识划分为常识知识、进化知识和评价知识三部分，分别用来存储以对象形式描述的显性常识知识、以特征向量形式描述的进化过程隐含知识和以代理模型形式描述的用户评价隐含知识[59]，从而拓展了知识描述形式，丰富了知识内容。
1.3.3.3 接受函数
接受函数从种群空间选取较优个体提交给信度空间用于知识更新，其研究核心在于选取较优个体数目。目前，已有的接受函数有3类：固定比率接受函数、动态接受函数和模糊接受函数[48]。这3类接受函数各有特点，在实际应用中应根据具体优化问题进行选择。
1.3.3.4 影响函数
影响函数的主要作用是使用信度空间中各类知识引导种群进化。进化初期，种群探索整个搜索空间，此时规范知识及拓扑知识处于控制地位，一方面限定探索区域，另一方面引导搜索趋于具有高属性值的单元。进化中期，更新状况知识和规范知识，进一步缩小搜索范围，并重新划分拓扑知识，引导种群在更小粒度单元上进行搜索。进化后期，搜索集中在某一局部区域，容易导致早熟收敛，于是引入历史知识，帮助种群跳出局部较优点。在整个进化过程中，领域知识一直为种群进化提供进化方向的指引。从知识对进化过程的引导作用可以看出，影响函数的关键问题在于各类知识何时作用于种群及其所引导的种群比例。在各类知识的引导作用下，文化算法显示出了优于以往进化算法的收敛性、搜索能力及对环境的适应能力。