第9章　思维进化算法

9.1　思维进化算法的提出

思维进化算法（Mind-Evolution-Algorithm，MEA）是1998年由孙承意提出的一种新的进化算法^[36]。该算法模仿人类思维中趋同、异化两种思维模式交互作用，旨在推动思维进化过程。同遗传算法相比，思维进化算法采用了不同的进化操作和运行机制，而使其具有以下的特点。

（1）把群体划分为子群体，通过趋同和异化操作使局部开采与整体勘探相辅相成，协调发展。

（2）利用局部和全局公告板记忆子群体和环境的信息，以便指导趋同与异化向着有利的方向进行。

（3）采用多子群体并行进化机制，具有本质上的并行性。

（4）通过趋同算子实现个体之间、子群体之间的学习，体现了向前者和优胜者学习的机制。

（5）易扩充，可移植性强。

思维进化算法已用于优化计算、图像处理、系统建模等方面。

9.2　思维进化算法的基本思想

思维进化算法的提出是通过对简单遗传算法的深入分析，认为导致遗传算法存在早熟、计算代价高等问题，以及性能改进效果显著的主要原因如下。

（1）单一的一个基因可能同时影响一系列表象，而某一表象可能是由许多基因的交互作用决定的，由于多表象性和多基因性的交互影响，遗传操作的结果一般是不可预知的，使得难以控制进化的方向，造成GA性能改进变得困难。

（2）由于遗传算法是模拟生物进化的过程，而生物进化没有记忆，因此有关产生个体的信息包含在个体所携带的染色体的集合及染色体编码的结构中。GA进化过程中获得的信息都保存在当前群体中的个体里，如果在进化过程中没有遗传给后代，将导致优良个体信息的丧失。若GA没有充分利用从环境得到的信息指导进化的方向，则导致GA的计算效率较低。

（3）勘探与开发利用功能协调配合差。遗传算法用随机方法生成初始群体，采用变异和交叉算子在搜索空间进行“勘探”，利用选择算子对群体中的信息进行“开发”利用。但是这两种作用的配合难以确保“探测”与“开采”功能始终协调得最好。个体描述方式的特殊化及操作算子的复杂性，使得问题的初始化及控制参数的合理选择存在一定的困难，从而导致群体的多样性与选择压力难以达到有效平衡。这是造成算法过早收敛、搜索效率低的主要原因。

通过分析人类思维过程和自然进化过程，我们认为人类思维的进步速度远高于生物进化的原因有如下两点。

（1）向前人和优胜者学习。在人类的进步过程中，产生了科学，并以书籍等形式记载供后人学习。信息的快速交流使人类能够共享他人的成功经验、研究成果。由于这些知识的积累和交流，使得近二三百年人类的思维进步越来越快。

（2）不断地探索与创新。在学习前人和优胜者经验的同时，人们不断地改变自己的思维方式，另辟蹊径，探索新的领域。正是思维上的这种方式，使新概念、新科学、新技术、新方法不断涌现。

思维进化算法认为，有两种思维模式普遍存在于各个领域的人们的思维活动中，称为趋同和异化：趋同指的是采用现有的、他人思维模式或方法解决问题，但可能不是完全机械地模仿别人；异化指的是摆脱常规思维方式，提出解决问题的新观点、新方法、新途径或提出新问题、开拓新领域。这两种不同的思维模式的交互作用推动人类思维越来越快地进步。模拟人类思维过程的趋同和异化方式是思维进化算法的基本思想。

9.3　思维进化算法的描述

思维进化算法由群体、子群体、个体、公告板、特征提取系统等部分组成，其系统结构如图9.1所示。下面介绍MEA的基本概念及定义。

（1）环境：所求问题的解空间和信息空间，即所有可能的解及其所携带的知识的集合。

（2）适应度函数：对所求问题的解的适应性进行度量的函数，对每一个解给出其数值评价，也称评价函数。

（3）个体和胜者：个体表示所求问题的每一个可能解。在MEA中，每个个体都可以拥有自己的知识，并管理它们。每个个体都有其自己的性格，如有保持自己成功经验的趋势，或者有向其他个体学习的趋势。胜者指的是这样的个体，它依据适应度函数计算出的评价值高于解空间中其他的个体。

（4）群体、初始群体和子群体：进化过程的每一代中所有个体的集合称为群体。初始群体是指算法初始化以后，个体在解空间中随机散布，然后计算得到每个个体的得分，一些得分高的个体成为胜者，并以它们为中心形成初始群体。优胜子群体记录全局竞争中的优胜者的信息，临时子群体记录全局竞争的中间过程。

（5）公告板：为个体之间和子群体之间交流信息提供了环境和机会，在算法中有局部公告板和全局公告板。公告板包含3类基本信息（或称为必要信息）：个体或子群体的序号、动作、得分。根据需要，还可以包含其他信息，如前若干代群体或个体的信息。

序号是算法对操作对象的编号。动作是指被执行的进化操作，动作的描述因领域而异。个体的得分是个标量，它是环境依据适应度函数对个体动作的评价。子群体的得分按该子群体中胜者的得分计算。

这些信息就是个体或群体得到的关于环境的知识。公告板中的信息根据应用的不同可以按不同的要求排序。子群体中的个体在局部公告板记录各自的信息。全局公告板用于记录各子群体信息。

（6）进化操作：包括趋同和异化两个基本算子。下面给出它们的定义。

【定义9.1】　在子群体范围中，个体竞争成为胜者的过程称为趋同。

趋同是一个局部竞争的过程，在这个过程中个体的信息在局部公告板中记录。在MEA中将完成这一趋同过程的操作称为趋同（算子）。在数值优化中，趋同操作的实现方法是，在子群体前一代的胜者附近按正态分布散布新一代的个体，并计算这些个体的得分，其中得分最高的个体是本子群体的新的胜者。胜者的得分作为该子群体的得分。该正态分布可以表示为N（X，Σ），其中X是正态分布的中心向量，Σ是该正态分布的协方差矩阵，当各维变量相互独立时，该矩阵为对角矩阵，在迭代的第i代，其对角元素记为｛σ_id｝，其中d=1，2，3，…是解空间的维数。

一个子群体在趋同过程中，若不再产生新的胜者，则称该子群体已经成熟（Maturation）。当子群体成熟时，该子群体的趋同过程结束。子群体从诞生到成熟的期间称为生命期（Lifecycle）。子群体成熟的判别准则如下。

如果一个子群体在连续M代中的得分增长小于给定的ε，即

max（Δf t=i-M+1，i-M+2，…，i-1；M-1＜i＜∞）＜ε（9.1）

则认为此子群体在第i代成熟，其中Δf_t为子群体在第t代得分增长。

【定义9.2】　在整个解空间中，各子群体为成为胜者而竞争，不断地探测解空间中新的点，这个过程称为异化。

异化有两个含义。一是各子群体进行全局竞争，若一个临时子群体的得分高于某个成熟的优胜子群体的得分，则该优胜子群体被获胜的临时子群体替代，原优胜子群体中的个体被释放；若一个成熟的临时子群体的得分低于任意一个优胜子群体的得分，则该临时子群体被废弃，其中的个体被释放。二是被释放的个体在全局范围内重新进行搜索并形成新的临时群体。

在算法开始时，所有的个体进行全局搜索，并形成若干子群体，即产生初始群体及子群体。显然，异化是一个全局竞争的过程，其结果是得到一个全局最优解。在MEA中将完成这种异化过程的操作称为异化（算子）。

趋同和异化在MEA运行过程中要反复进行，直到满足算法终止运行的条件。定义9.1和定义9.2是从竞争的角度定义的，类似地，也可以从解空间的搜索角度进行定义。趋同进行局部搜索，异化进行全局搜索。从另一个角度分析，趋同可以看作是对局部信息开发利用，异化可以看作是全局性的探测。

9.4　思维进化算法的实现步骤及流程

在思维进化算法流程描述中所用到的符号及说明如表9.1所示。

在数值优化问题中，思维进化算法用伪代码表示如下。

关于上面思维进化算法的学习步骤如下。

（1）初始群体的个体在解空间中随机散布，计算每个个体的得分。

（2）选出N_S个得分最高的个体，即胜者，公布在全局公告板上，并排序；其余为失败者，其中一些失败者在胜者周围散布，形成N_S个优胜子群体。

（3）其余失败者随机地在解空间散布，再在其中选择N_T个胜者，形成N_T个临时子群体。

（4）趋同学习是在每个子群体中进行的（包括优胜子群体和临时子群体）。子群体中的个体以子群体的胜者为中心进行随机散布，它们在胜者周围进行搜索、相互竞争，产生新的胜者。每个个体的信息公布在局部公告板上。每个子群体中胜者的得分作为该子群体的得分。

（5）异化操作是在全局范围内进行的。如果一些临时子群体的得分高于一个成熟的一般子群体，那么临时子群体将取代一般子群体。被取代的子群体中的个体在空间中重新散布，形成新的临时子群体。

（6）收敛的判别。如果此次过程不收敛，则重复步骤（4）和步骤（5）。

思维进化算法的流程如图9.2所示。